Publication Type
Journal Article
Version
acceptedVersion
Publication Date
5-2021
Abstract
This paper studies the integration of the vehicle routing problem with cross-docking (VRPCD). The aim is to find a set of routes to deliver products from a set of suppliers to a set of customers through a cross-dock facility, such that the operational and transportation costs are minimized, without violating the vehicle capacity and time horizon constraints. A two-phase matheuristic based on column generation is proposed. The first phase focuses on generating a set of feasible candidate routes in both pickup and delivery processes by implementing an adaptive large neighborhood search algorithm. A set of destroy and repair operators are used in order to explore a large neighborhood space. The second phase focuses on solving the set partitioning model to determine the final solution. The proposed matheuristic is tested on the available benchmark VRPCD instances and compared with the state-of-the-art algorithms. Experimental results show the competitiveness of the proposed matheuristic as it is able to improve the best known solutions for 80 instances and to obtain the same results for the remaining 10 instances, with an average improvement of 12.6%. On new and larger instances, our proposed matheuristic maintains its solution quality within acceptable CPU times and outperforms a pure ALNS algorithm. We also explicitly analyze the performance of the matheuristic considering the solution quality and CPU time.
Keywords
Adaptive large neighborhood search, Cross-docking, Matheuristic, Scheduling, Set-partitioning formulation, Vehicle routing problem
Discipline
Artificial Intelligence and Robotics | Operations Research, Systems Engineering and Industrial Engineering | Theory and Algorithms
Research Areas
Intelligent Systems and Optimization
Publication
Applied Soft Computing
Volume
103
First Page
1
Last Page
13
ISSN
1568-4946
Identifier
10.1016/j.asoc.2021.107163
Publisher
Elsevier
Embargo Period
7-11-2021
Citation
GUNAWAN, Aldy; WIDJAJA, Audrey Tedja; VANSTEENWEGEN, Pieter; and YU, Vincent F..
A matheuristic algorithm for the vehicle routing problem with cross-docking. (2021). Applied Soft Computing. 103, 1-13.
Available at: https://ink.library.smu.edu.sg/sis_research/6039
Copyright Owner and License
Authors
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Additional URL
https://doi.org/10.1016/j.asoc.2021.107163
Included in
Artificial Intelligence and Robotics Commons, Operations Research, Systems Engineering and Industrial Engineering Commons, Theory and Algorithms Commons