Abstract
In this article, we investigate the vehicle routing problem with deadlines, whose goal is to satisfy the requirements of a given number of customers with minimum travel distances while respecting both of the deadlines of the customers and vehicle capacity. It is assumed that the travel time between any two customers and the demands of the customer are uncertain. Two types of uncertainty sets with adjustable parameters are considered for the possible realizations of travel time and demand. The robustness of a solution against the uncertain data can be achieved by making the solution feasible for any travel time and demand defined in the uncertainty sets. We propose a Dantzig-Wolfe decomposition approach, which enables the uncertainty of the data to be encapsulated in the column generation subproblem. A dynamic programming algorithm is proposed to solve the subproblem with data uncertainty. The results of computational experiments involving two well-known test problems show that the robustness of the solution can be greatly improved.
Similar content being viewed by others
References
Augerat P, Belenguer J, Benavent E, Corberan A, Naddef D and Rinaldi G (1995). Computational results with a branch and cut code for the capacitated vehicle routing problem. Technical Report RR949-M, Artemis-Imag, Grenoble, France.
Barnhart C, Johnson EL, Nemhauser GL, Savelsbergh MWP and Vance PH (1998). Branch-and-price: Column generation for solving huge integer programs. Operations Research 46: 316–329.
Barnhart C, Hane CA and Vance PH (2000). Using branch-and-price-and-cut to solve origin-destination integer multicommodity flow problems. Operations Research 48: 318–326.
Berger J and Barkaoui M (2003). A new hybrid genetic algorithm for the capacitated vehicle routing problem. Journal of the Operational Research Society 54: 1254–1262.
Bertsimas D and Sim M (2003). Robust discrete optimization and network flows. Mathematical Programming 98: 49–71.
Bertsimas D and Sim M (2004). The price of robustness. Operations Research 52: 35–53.
Bertsimas D and Simchi-Levi D (1996). A new generation of vehicle routing research: Robust algorithms, addressing uncertainty. Operations Research 42: 286–304.
Bertsimas D, Pachamanova D and Sim M (2004). Robust linear optimization under general norms. Operations Research Letters 32: 510–516.
Campbell AM and Thomas BW (2008). Probabilistic traveling salesman problem with deadlines. Transportation Science 42: 1–21.
Campbell AM and Thomas BW (2009). Runtime reduction techniques for the probabilistic traveling salesman problem with deadlines. Computers & Operations Research 36: 1231–1248.
Chabrier A (2006). Vehicle routing problem with elementary shortest path based column generation. Computers & Operations Research 33: 2972–2990.
Chang TS, Wan YW and Ooi WT (2009). A stochastic dynamic traveling salesman problem with hard time windows. European Journal of Operational Research 198: 748–759.
Cheung RK and Hang DD (2003). A time-window sliding procedure for driver-task assignment with random service times. IIE Transactions 35: 433–444.
Christiansen C and Lysgaard J (2007). A branch-and-price algorithm for the capacitated vehicle routing problem with stochastic demands. Operations Research Letters 35: 773–781.
Cordeau J, Gendreau M, Laporte G, Potvin J and Semet F (2002). A guide to vehicle routing heuristics. Journal of the Operational Research Society 53: 512–522.
Desrochers M. (1986). La fabrication d′horaires de travail pour les conducteurs d′autobus par une methode de generation de colonnes. PhD Thesis, Centre de recherche sur les Transports, Publication #470, Universite de Montreal, Canada.
Dethloff J (2002). Relation between vehicle routing problems: An insertion heuristic for the vehicle routing problem with simultaneous delivery and pick-up applied to the vehicle routing problem with backhauls. Journal of the Operational Research Society 53: 115–118.
Dorigo M, Maniezzo V and Colorni A (1996). Ant system: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man and Cybernetics 26: 29–41.
Fisher ML, Jornsten KO and Madsen OBG (1997). Vehicle routing with time windows: Two optimization algorithms. Operations Research 45: 488–492.
Fukasawa R, Longo H, Lysgaard J, De Aragao MP, Reis M, Uchoa E and Werneck RF (2006). Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Mathematical Programming 106: 491–511.
Gendreau M, Hertz A and Laporte G (1994). A tabu search heuristic for the vehicle routing problem. Management Science 40: 1276–1290.
Gendreau M, Laporte G and Seguin R (1995). An exact algorithm for the vehicle routing problem with stochastic demands and customers. Transportation Science 29: 143–155.
Gendreau M, Laporte G and Seguin R (1996a). Stochastic vehicle routing. European Journal of Operational Research 88: 3–12.
Gendreau M, Laporte G and Seguin R (1996b). A tabu search heuristic for the vehicle routing problem with stochastic demands and customers. Operations Research 44: 469–477.
Hvattum LM, Lokketangen A and Laporte G (2006). Solving a dynamic and stochastic vehicle routing problem with a sample scenario hedging heuristic. Transportation Science 40: 421–438.
Ioachim I, Gelinas S, Soumis F and Desrosiers J (1998). A dynamic programming algorithm for the shortest path problem with time windows and linear node costs. Networks 31: 193–204, Wiley Online Library).
Irnich S and Desaulniers G (2004). Shortest Path Problems with Resource Constraints. Springer: New York.
Jula H, Dessouky M and Ioannou PA (2006). Truck route planning in nonstationary stochastic networks with time windows at customer locations. IEEE Transactions on Intelligent Transportation Systems 7: 51–62.
Kohl N and Madsen OBG (1997). An optimization algorithm for the vehicle routing problem with time windows based on Lagrangian relaxation. Operations Research 45: 395–406.
Kolen AWJ, Kan AHGR and Trienekens HWJM (1987). Vehicle routing with time windows. Operations Research 35: 266–273.
Lin S and Kernighan B (1973). An effective heuristic algorithm for the traveling-salesman problem. Operations Research 21: 498–516.
Rego C (1998). A subpath ejection method for the vehicle routing problem. Management Science 44: 1447–1459.
Russell RA and Urban TL (2008). Vehicle routing with soft time windows and Erlang travel times. Journal of the Operational Research Society 59: 1220–1228.
Solomon MM (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research 35: 254–265.
Sungur I, Ordonez F and Dessouky M (2008). A robust optimization approach for the capacitated vehicle routing problem with demand uncertainty. IIE Transactions 40: 509–523.
Tan KC, Cheong CY and Goh CK (2007). Solving multiobjective vehicle routing problem with stochastic demand via evolutionary computation. European Journal of Operational Research 177: 813–839.
Toth P and Vigo D (2002). The vehicle routing problem. SIAM 9: 5–10.
Yu B, Yang Z and Xie J (2010). A parallel improved ant colony optimization for multi-depot vehicle routing problem. Journal of the Operational Research Society 62: 183–188.
Acknowledgements
The authors would like to thank several anonymous referees for their numerous and very helpful comments and suggestions. This research is supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education, Science and Technology (2009-0088465).
Author information
Authors and Affiliations
Corresponding author
Additional information
Correction
In an earlier version of this article S Park's affiliation was wrongly given as ETRI. The correct affiliation, KAIST, is shown in this final version of the article.
Rights and permissions
About this article
Cite this article
Lee, C., Lee, K. & Park, S. Robust vehicle routing problem with deadlines and travel time/demand uncertainty. J Oper Res Soc 63, 1294–1306 (2012). https://doi.org/10.1057/jors.2011.136
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/jors.2011.136