A Demon Algorithm for the Vehicle Routing Problem with Cross-Docking
Gültekin Kuyzu  1, 2, *@  , Hakan Yurtdaş  3@  
1 : TOBB University of Economics and Technology  (TOBB ETU)  -  Website
Department of Industrial Engineering, Ankara -  Turkey
2 : Zaragoza Logistics Center  (ZLC)  -  Website
MIT-Zaragoza International Logistics Program, Zaragoza -  Spain
3 : Gazi University  (GU)  -  Website
Graduate Program in Operations Research, Ankara -  Turkey
* : Corresponding author

We study the vehicle routing problem with cross-docking (VRPCD), which can be seen as a variant of the pickup and delivery problem with a required transfer point. In cross-docking, the goods picked up at supply points must be consolidated and reloaded to delivery vehicles at an intermediate facility (i.e. a cross-dock) before being delivered to demand points. In this setting, coordinated routing of the collection and delivery vehicles is crucial. The objective of the VRPCD is to identify a set of collection and delivery routes via a cross-dock with minimum total cost, given a set of supply and demand points with known demands, ensuring that the vehicle capacities are not exceed and each delivery vehicle departs only after all of the goods to be loaded to it are brought to the cross-dock. We propose a demon algorithm, which can be viewed as a generalization of simulated annealing, for solving the VRPCD. Our computational experiments on benchmark instances we found in the literature show that the demon algorithm can find high quality solutions very efficiently, outperforming previously proposed methods.

Online user: 1 RSS Feed