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

Rodolfo Dondo


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.



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

Texto completo:

PDF/A (English)


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.

e-ISSN 2175-8018

Creative Commons License
IJIE - Iberoamerican Journal of Industrial Engineering foi licenciada sob uma Licença Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

Iberoamerican Journal of Industrial Engineering. Universidade Federal de Santa Catarina. Departamento de Engenharia de Produção e Sistemas. Florianópolis, SC, Brasil.

Para entrar em contato com a equipe editorial do IJIE, encaminhe um e-mail para periodico.ijie@gmail.com ou ijie@contato.ufsc.br