Skip to main content
Log in

Disruption management of the vehicle routing problem with vehicle breakdown

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

Abstract

This paper introduces a new class of problem, the disrupted vehicle routing problem (VRP), which deals with the disruptions that occur at the execution stage of a VRP plan. The paper then focuses on one type of such problem, in which a vehicle breaks down during the delivery and a new routing solution needs to be quickly generated to minimise the costs. Two Tabu Search algorithms are developed to solve the problem and are assessed in relation to an exact algorithm. A set of test problems has been generated and computational results from experiments using the heuristic algorithms are presented.

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

Access this article

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

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Akturk MS and Gorgulu E (1999). Match-up scheduling under a machine breakdown . Eur J Opl Res 112: 81–97.

    Article  Google Scholar 

  • Augerat P, Belenguer JM, 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 RR 949-M. Universite Joseph Fourier, Grenoble, France.

  • Bertsimas DJ and Simchi-Levi D (1996). A new generation of vehicle routing research: Robust algorithms addressing uncertainty . Opns Res 44: 286–304.

    Article  Google Scholar 

  • Christofides N and Eilon S (1969). An algorithm for the vehicle dispatching problem . Opl Res Quart 20: 309–318.

    Article  Google Scholar 

  • Christofides N, Mingozzi A and Toth P (1979). The vehicle routing problem . In: Christofides N, Mingozzi A, Toth P and Sandi L (eds). Combinatorial Optimization. Wiley: Chichester, UK, pp. 315–338.

    Google Scholar 

  • Clausen J, Larsen A and Larsen J (2005). Disruption management in the airline industry—concepts, models and methods. Technical Report. Informatics and Mathematical Modelling, Technical University of Denmark. DTU.

  • Eden C, Williams T, Ackermann F and Howick S (2002). On the nature of disruption and delay in major projects . J Opl Res Soc 51: 291–300.

    Article  Google Scholar 

  • Filar JA, Manyem P and White K (2001). How airlines and airports recover from schedule perturbations: A survey . Ann Opns Res 108: 315–333.

    Article  Google Scholar 

  • Fisher ML (1994). Optimal solution of vehicle routing problems using minimum K-trees . Opns Res 42: 626–642.

    Article  Google Scholar 

  • Fu Z, Eglese R and Li LYO (2005). A new tabu search heuristic for the open vehicle routing problem . J Opl Res Soc 56: 267–274.

    Article  Google Scholar 

  • Fu Z, Eglese R and Li LYO (2006). Corrigendum: A new tabu search heuristic for the open vehicle routing problem . J Opl Res Soc 57: 1018.

    Article  Google Scholar 

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

    Article  Google Scholar 

  • Gendreau M and Potvin JY (1998). Dynamic vehicle routing and dispatching . In: Crainic T and Laporte G (eds). Fleet Management and Logistics 1998. Kluwer: Boston, pp. 115–126.

    Chapter  Google Scholar 

  • Ghiani G, Guerriero F, Laporte G and Musmanno R (2003). Real-time vehicle routing: Solution concepts, algorithms and parallel computing strategies . Eur J Opl Res 151: 1–11.

    Article  Google Scholar 

  • Hall NG and Potts C (2004). Rescheduling for new orders . Opns Res 52: 440–453.

    Article  Google Scholar 

  • Kohl K, Larsen A, Larsen J, Ross A and Tiourine S (2004). Airline disruption management—perspectives, experiences and outlook. Carmen Research and Technology Report. CRTR-0407, September 2004.

  • Letchford AN, Lysgaard J and Eglese RW (2007). A branch-and-cut algorithm for the capacitated open vehicle routing problem . J Opl Res Soc 58: 1642–1651.

    Article  Google Scholar 

  • Li JQ, Mirchandani PB and Borenstein D (2004). Parallel auction algorithm for bus rescheduling. Proceedings of the 9th International Conference on Computer-Aided Scheduling of Public Transport, San Diego, California, USA.

  • Li JQ, Borenstein D and Mirchandani PB (2007a). A decision support system for the single-depot vehicle rescheduling problem . Comput Opns Res 34: 1008–1032.

    Article  Google Scholar 

  • Li JQ, Mirchandani PB and Borenstein D (2007b). The vehicle rescheduling problem: Model and algorithms . Networks 50: 211–229.

    Article  Google Scholar 

  • Li JQ, Mirchandani PB and Borenstein D (2009a). A Lagrangian heuristic for the real-time vehicle rescheduling problem . Transport Res E-Log 45: 419–433.

    Article  Google Scholar 

  • Li JQ, Mirchandani PB and Borenstein D (2009b). Real-time vehicle rerouting problems with time windows . Eur J Opl Res 194: 711–727.

    Article  Google Scholar 

  • Powell WB, Jaillet P and Odoni A (1995). Stochastic and dynamic networks and routing . In: Ball MO, Magnanti TL, Monma CL and Nemhauser GL (eds). Handbooks in Operations Research and Management Science 1995. Network Routing Elsevier: Amsterdam, pp. 141–296.

    Google Scholar 

  • Psaraftis HN (1988). Vehicle Routing: Methods and Studies, Chapter Dynamic Vehicle Routing Problems . Elsevier Science Publishers B.V: North Holland.

    Google Scholar 

  • Psaraftis HN (1995). Dynamic vehicle routing: Status and prospects . Ann Opns Res 61: 143–164.

    Article  Google Scholar 

  • Qi X, Bard JF and Yu G (2004). Supply chain coordination with demand disruptions . Omega 32: 301–312.

    Article  Google Scholar 

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

    Article  Google Scholar 

  • Teodorović D and Guberinić S (1984). Optimal dispatching strategy on an airline network after a schedule perturbation . Eur J Opl Res 15: 178–182.

    Article  Google Scholar 

  • Teodorović D and Stojković G (1995). Model to reduce airline schedule disturbances . J Trans Eng 121: 324–331.

    Article  Google Scholar 

  • Xia YS, Qi XT and Yu G (2002). Real-time production and inventory disruption management under the continuous rate economic production quantity model Working paper. Red McCombs School of Business: The University of Texas at Austin.

  • Xiao T, Yu G, Sheng Z and Xia Y (2005). Coordination of a supply chain with one-manufacturer and two-retailers under demand promotion and disruption management decisions . Ann Opns Res 135: 87–109.

    Article  Google Scholar 

  • Yang J, Qi X and Yu G (2005). Disruption management in production planning . Nav Res Log 52: 420–442.

    Article  Google Scholar 

  • Yu G and Qi X (2004). Disruption Management: Framework, Models and Applications . World Scientific Publishing Co. Pte Ltd: Singapore.

    Book  Google Scholar 

  • Zhu G, Bard JF and Yu G (2005). Disruption management for resource-constrained project scheduling . J Opl Res Soc 56: 365–381.

    Article  Google Scholar 

Download references

Acknowledgements

This research was partly supported by the National Natural Science Foundation of China (NSFC, 70671108).

Author information

Authors and Affiliations

Authors

Rights and permissions

Reprints and permissions

About this article

Cite this article

Mu, Q., Fu, Z., Lysgaard, J. et al. Disruption management of the vehicle routing problem with vehicle breakdown. J Oper Res Soc 62, 742–749 (2011). https://doi.org/10.1057/jors.2010.19

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

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

Keywords

Navigation