Skip to main content
SpringerLink
Log in

Robust vehicle routing problem with deadlines and travel time/demand uncertainty

  • General Paper
  • Published:
Journal of the Operational Research Society

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Figure 1
Figure 2
Figure 3

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.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • Bertsimas D and Sim M (2003). Robust discrete optimization and network flows. Mathematical Programming 98: 49–71.

    Article  Google Scholar 

  • Bertsimas D and Sim M (2004). The price of robustness. Operations Research 52: 35–53.

    Article  Google Scholar 

  • Bertsimas D and Simchi-Levi D (1996). A new generation of vehicle routing research: Robust algorithms, addressing uncertainty. Operations Research 42: 286–304.

    Article  Google Scholar 

  • Bertsimas D, Pachamanova D and Sim M (2004). Robust linear optimization under general norms. Operations Research Letters 32: 510–516.

    Article  Google Scholar 

  • Campbell AM and Thomas BW (2008). Probabilistic traveling salesman problem with deadlines. Transportation Science 42: 1–21.

    Article  Google Scholar 

  • Campbell AM and Thomas BW (2009). Runtime reduction techniques for the probabilistic traveling salesman problem with deadlines. Computers & Operations Research 36: 1231–1248.

    Article  Google Scholar 

  • Chabrier A (2006). Vehicle routing problem with elementary shortest path based column generation. Computers & Operations Research 33: 2972–2990.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • Cheung RK and Hang DD (2003). A time-window sliding procedure for driver-task assignment with random service times. IIE Transactions 35: 433–444.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • Fisher ML, Jornsten KO and Madsen OBG (1997). Vehicle routing with time windows: Two optimization algorithms. Operations Research 45: 488–492.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • Gendreau M, Hertz A and Laporte G (1994). A tabu search heuristic for the vehicle routing problem. Management Science 40: 1276–1290.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • Gendreau M, Laporte G and Seguin R (1996a). Stochastic vehicle routing. European Journal of Operational Research 88: 3–12.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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).

    Article  Google Scholar 

  • Irnich S and Desaulniers G (2004). Shortest Path Problems with Resource Constraints. Springer: New York.

    Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • Kolen AWJ, Kan AHGR and Trienekens HWJM (1987). Vehicle routing with time windows. Operations Research 35: 266–273.

    Article  Google Scholar 

  • Lin S and Kernighan B (1973). An effective heuristic algorithm for the traveling-salesman problem. Operations Research 21: 498–516.

    Article  Google Scholar 

  • Rego C (1998). A subpath ejection method for the vehicle routing problem. Management Science 44: 1447–1459.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • Solomon MM (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research 35: 254–265.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • Toth P and Vigo D (2002). The vehicle routing problem. SIAM 9: 5–10.

    Google Scholar 

  • 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.

    Article  Google Scholar 

Download references

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

  1. ETRI, Daejeon, Republic of Korea

    C Lee

  2. Hankuk University of Foreign Studies, Gyeonggi-do, Republic of Korea

    K Lee

  3. KAIST, Daejeon, Republic of Korea

    S Park

Authors
  1. C Lee
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. K Lee
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. S Park
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to S Park.

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

Reprints 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

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1057/jors.2011.136

Keywords

Search

Navigation