A matheuristic algorithm for the vehicle routing problem with cross-docking

• Main Authors: GUNAWAN, Aldy, WIDJAJA, Audrey Tedja, VANSTEENWEGEN, Pieter, YU, Vincent F.
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2021
• Subjects: Adaptive large neighborhood search; Cross-docking; Matheuristic; Scheduling; Set-partitioning formulation; Vehicle routing problem; Artificial Intelligence and Robotics; Operations Research, Systems Engineering and Industrial Engineering; Theory and Algorithms
• Online Access: https://ink.library.smu.edu.sg/sis_research/6039; https://ink.library.smu.edu.sg/context/sis_research/article/7042/viewcontent/Matheuristics_algorithm_2021_av_ASC.pdf
• Institution: Singapore Management University

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.