A branch-and-price method for the vehicle routing problem with cross-docking and time windows


  • Rodolfo Dondo Universidad Nacional del Litoral


Supply-chain management, Cross-docking, Vehicle routing, Columns generation


One important factor in supply chain management is to efficiently control the supply chain flows. Due to its importance, many companies are trying to develop efficient methods to increase customer satisfaction and reduce costs. Cross-docking is considered a good method to reduce inventory and improve responsiveness. The Vehicle Routing Problem with Cross-Docking and Time Windows (VRP-CD-TW) consists on designing the minimum-cost set of routes to serve a given set of transportation requests while respecting constraints on vehicles capacity, customer time windows and using transfers on a cross-docking base. Each customer must be visited just once and mixed tours comprising pick-up and delivery stops are not allowed. For a given vehicle, the designed pick-up tour must precede its delivery tour. In this work, we model the VRP-CD-TW assuming that all feasible orders are known in advance. We present a new mixed integer program to model the VRP-CD-TW and reformulate it via Dantzig–Wolfe decomposition to later develop a column generation procedure. The proposed branch-and-price algorithm shows encouraging results on solving some Solomon-based instances.   10.13084/2175-8018.v05n10a02 

Biografia do Autor

Rodolfo Dondo, Universidad Nacional del Litoral

Dr., en Ingeniería Química Profesor Adjunto


BOYSEN, N.; FLIEDNER, M. Cross-dock scheduling: classification, literature review and research agenda. Omega, v. 38, p. 413-422, 2010.

LEE, Y.; JUNG, W.J.; LEE, K.M. Vehicle Routing Scheduling for Cross-Docking in the Supply Chain. Computers & Industrial Engineering, v. 51, p. 247-256, 2006.

YU, W.; EGBELU, P. Scheduling of Inbound and Outbound Trucks in Cross-Docking Systems with Temporary Storage. European Journal of Operational Research, v. 184, p. 377-396, 2008.

WEN, M.; LARSEN, J.; CLAUSEN, J.; CORDEAU, J.-F.; LAPORTE, G. Vehicle routing with cross-docking. Journal of the Operational Research Society, v. 60, p. 708-1718, 2009.

LIAO, CH.-J.; LIN, Y.; SHIH, S.C. Vehicle routing with cross-docking in the supply chain. Expert Systems with Applications, v. 37, p. 6868-6873, 2010.

BOLOORI ARABANI A., FATEMI GHOMI S. AND M. ZANDIEH. Meta-heuristics implementation for scheduling of trucks in a cross-docking system with temporary storage. Expert Systems with Applications, v. 38, p. 1964-1979, 2011.

SOLOMON, M. Algorithms for the vehicle routing and scheduling problem with time window constraints. Operations Research, v. 32, p. 254-265, 1987.