A Column-Generation-Based Exact Algorithm to Solve the Full-Truckload Vehicle-Routing Problem

Toygar Emre () and Rizvan Erol
Additional contact information
Toygar Emre: Department of Industrial Engineering, Faculty of Engineering, Cukurova University, Saricam 01330, Adana, Turkey
Rizvan Erol: Department of Industrial Engineering, Faculty of Engineering, Cukurova University, Saricam 01330, Adana, Turkey

Mathematics, 2025, vol. 13, issue 5, 1-32

Abstract: This study addresses a specialized variant of the full-truckload delivery problem inspired by a Turkish logistics firm that operates in the liquid transportation sector. An exact algorithm is proposed for the relevant problem, to which no exact approach has been applied before. Multiple customer and trailer types, as well as washing operations, are introduced simultaneously during the exact solution process, bringing new aspects to the exact algorithm approach among full-truckload systems in the literature. The objective is to minimize transportation costs while addressing constraints related to multiple time windows, trailer types, customer types, product types, a heterogeneous fleet with limited capacity, multiple departure points, and various actions such as loading, unloading, and washing. Additionally, the elimination or reduction of waiting times is provided along transportation routes. In order to achieve optimal solutions, an exact algorithm based on the column generation method is proposed. A route-based insertion algorithm is also employed for initial routes/columns. Regarding the acquisition of integral solutions in the exact algorithm, both dynamic and static sets of valid inequalities are incorporated. A label-setting algorithm is used to generate columns within the exact algorithm by being accelerated through bi-directional search, ng-route relaxation, subproblem selection, and heuristic column generation. Due to the problem-dependent structure of the column generation method and acceleration techniques, a tailored version of them is included in the solution process. Performance analysis, which was conducted using artificial input sets based on the real-life operations of the logistics firm, demonstrates that optimality gaps of less than 1% can be attained within reasonable times even for large-scale instances relevant to the industry, such as 120 customers, 8 product and 8 trailer types, 4 daily time windows, and 40 departure points.

Keywords: vehicle routing; full-truck load; column generation; labeling algorithms; construction heuristic (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2025
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/13/5/876/pdf (application/pdf)
https://www.mdpi.com/2227-7390/13/5/876/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:13:y:2025:i:5:p:876-:d:1606403

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().