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.
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.
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.
Christofides N and Eilon S (1969). An algorithm for the vehicle dispatching problem . Opl Res Quart 20: 309–318.
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.
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.
Filar JA, Manyem P and White K (2001). How airlines and airports recover from schedule perturbations: A survey . Ann Opns Res 108: 315–333.
Fisher ML (1994). Optimal solution of vehicle routing problems using minimum K-trees . Opns Res 42: 626–642.
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.
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.
Gendreau M, Hertz A and Laporte G (1994). A tabu search heuristic for the vehicle routing problem . Mngt Sci 40: 1276–1290.
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.
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.
Hall NG and Potts C (2004). Rescheduling for new orders . Opns Res 52: 440–453.
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.
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.
Li JQ, Mirchandani PB and Borenstein D (2007b). The vehicle rescheduling problem: Model and algorithms . Networks 50: 211–229.
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.
Li JQ, Mirchandani PB and Borenstein D (2009b). Real-time vehicle rerouting problems with time windows . Eur J Opl Res 194: 711–727.
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.
Psaraftis HN (1988). Vehicle Routing: Methods and Studies, Chapter Dynamic Vehicle Routing Problems . Elsevier Science Publishers B.V: North Holland.
Psaraftis HN (1995). Dynamic vehicle routing: Status and prospects . Ann Opns Res 61: 143–164.
Qi X, Bard JF and Yu G (2004). Supply chain coordination with demand disruptions . Omega 32: 301–312.
Solomon MM (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints . Opns Res 35: 254–265.
Teodorović D and Guberinić S (1984). Optimal dispatching strategy on an airline network after a schedule perturbation . Eur J Opl Res 15: 178–182.
Teodorović D and Stojković G (1995). Model to reduce airline schedule disturbances . J Trans Eng 121: 324–331.
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.
Yang J, Qi X and Yu G (2005). Disruption management in production planning . Nav Res Log 52: 420–442.
Yu G and Qi X (2004). Disruption Management: Framework, Models and Applications . World Scientific Publishing Co. Pte Ltd: Singapore.
Zhu G, Bard JF and Yu G (2005). Disruption management for resource-constrained project scheduling . J Opl Res Soc 56: 365–381.
Acknowledgements
This research was partly supported by the National Natural Science Foundation of China (NSFC, 70671108).
Author information
Authors and Affiliations
Rights 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
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/jors.2010.19