New Notation and Classification Scheme for Vehicle Routing Problems

Cherif-Khettaf, Wahiba Ramdane; Rachid, Mais Haj; Bloch, Christelle; Chatonnay, Pascal

RAIRO - Operations Research - Recherche Opérationnelle, Special ROADEF 2013, Tome 49 (2015) no. 1, pp. 161-194.

Vehicle Routing Problems have been some of the most studied problems in combinatorial optimisation because they have many applications in transportation and supply chain. They are usually known as Vehicle Routing Problems or VRPs. The related literature is quite large and diverse both in terms of variants of the problems and in terms of solving approaches. To identify the different variants of routing problems, authors generally use initialisms, in which various prefixes and suffixes indicate the presence of different assumptions or constraints. But this identification based on initialisms is inefficient. For example, two variants of a problem may be identified by the same abbreviation, whereas different abbreviations may be assigned to the same problem. This paper proposes a new notation and a new formalism to identify and to classify instances of routing problems. This contribution aims at filling in the gaps of the current identification system. The goal is to allow everyone to position his work accurately in the literature, and to easily identify approaches and results comparable to his research. The proposed notation is inspired by the scheduling formalism. It has four fields ($\pi /\alpha /\beta /\gamma$), respectively describing the type and horizon of the problem, the system structure, resources and demands, constraints and objectives to be optimized. 26 papers from the literature chosen for their disparity are classified using this notation to illustrate its usefulness and a software tool is proposed to make its use easier.

E. Alba and B. Dorronsoro, Solving the vehicle routing problem by using cellular genetic algorithms, in Evolutionary Computation in Combinatorial Optimization. Springer (2004) 11–20. | Zbl

F. Alonso, M.J. Alvarez and J.E. Beasley, A tabu search algorithm for the periodic vehicle routing problem with multiple vehicle trips and accessibility restrictions. J. Oper. Res. Soc. 59 (2007) 963–976. | DOI | Zbl

G.B. Alvarenga, G.R. Mateus and G. De Tomi, A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows. Comput. Oper. Res. 34 (2007) 1561–1584. | DOI | Zbl

M. Ambrosini, T. Caruso, S. Foresti and G. Righini, A GRASP for the pickup and delivery problem with rear loading. Information Technology Department, Technical Report 65 (2004).

H. Andersson, A. Hoff, M. Christiansen, G. Hasle and A. Løkketangen, Industrial aspects and literature survey: Combined inventory management and routing. Comput. Oper. Res. 37 (2010) 1515–1536. | DOI | MR | Zbl

V. André, N. Grangeon and S. Norre, Chapter 15: Combination of a metaheuristic and a simulation model for the scheduling of resource-constrained transport activities. Metaheuristics for Production Scheduling (2013) 401–432.

C. Archetti, M.G. Speranza and A. Hertz, A tabu search algorithm for the split delivery vehicle routing problem. Transp. Sci. 40 (2006) 64–73. | DOI

G. Berbeglia, J.-F. Cordeau, I. Gribkovskaia and G. Laporte, Static pickup and delivery problems: a classification scheme and survey. Top 15 (2007) 1–31. | DOI | MR | Zbl

J. Berger, M. Barkaoui and O. Braysy, A route-directed hybrid genetic approach for the vehicle routing problem with time windows. Infor-Inform. Syst. Oper. Res. 41 (2003) 179–194.

L. Bianchi, M. Birattari, M. Chiarandini, M. Manfrin, M. Mastrolilli, L. Paquete, O. Rossi-Doria and T. Schiavinotto, Metaheuristics for the vehicle routing problem with stochastic demands, In Parallel Problem Solving from Nature-PPSN VIII, Springer (2004) 450–460.

J. Blazewicz, K.H. Ecker, G. Schmidt and J. Weglarz, Scheduling in computer and manufacturing systems. Elsevier (1996).

N. Boysen, M. Fliedner and A. Scholl, Sequencing mixed-model assembly lines: Survey, classification and model critique. Eur. J. Oper. Res. 192 (2009) 349–373. | DOI | MR | Zbl

N. Boysen, M. Fliedner and A. Scholl, A classification of assembly line balancing problems. Eur. J. Oper. Res. 183 2007 674–693. | DOI | Zbl

O. Bräysy, A reactive variable neighborhood search for the vehicle-routing problem with time windows. INFORMS J. Comput. 15 (2003) 347–368. | DOI | MR | Zbl

L. Caccetta, Achuthan N.R. and S.P. Hill, A new subtour elimination constraint for the vehicle routing problem. Eur. J. Oper. Res. 91 (1995) 573–586. | Zbl

V. Cacchiani, V.C. Hemmelmayr and F. Tricoire, A set-covering based heuristic algorithm for the periodic vehicle routing problem. Discrete Appl. Math. 163 (2014) 53–64. | DOI | MR | Zbl

M. Chabrol, M. Gourgand and P. Leclaire, Modelling of a routing problem in real traffic conditions, in Proc. International Conference on Computers & Industrial Engineering CIE’09 (2009) 1114–1118.

A.-L. Chen, G.-K. Yang and Z.-M. Wu, Hybrid discrete particle swarm optimization algorithm for capacitated vehicle routing problem. J. Zhejiang University Science A 7 (2006) 607–614. | DOI | Zbl

R. Chevrier, P. Canalda, P. Chatonnay and D. Josselin, Modelling of a routing problem in real traffic conditions, in Proc. of the IEEE Intelligent Transportation Systems Conference, 2006, ITSC ’06 (2006) 1096–1101.

C.H. Christiansen, Elements of Vehicle Routing under uncertainty. Aarhus School of Business, Department of Business Studies (2007).

J.-F. Cordeau and G. Laporte, The dial-a-ride problem (DARP): Variants, modeling issues and algorithms. Oper. Res. Soc. 1 (2003) 89–101. | MR | Zbl

J.-F. Cordeau and M. Maischberger, A parallel iterated tabu search heuristic for vehicle routing problems. Comput. Oper. Res. 39 (2012) 2033–2050. | DOI

J.-F. Cordeau and G. Laporte, Tabu search heuristics for the vehicle routing problem. Springer (2005). | MR | Zbl

G.B. Dantzig and H. Ramser John, The truck dispatching problem. Manage. Sci. 6 (1959) 80–91. | DOI | MR | Zbl

G.G.B. Dantzig, R. Fulkerson and S. Johnson, Solution of a large-scale traveling-salesman problem. J. Oper. Res. Soc. Am. (1954) 393–410. | MR

M. Dell’Amico, M. Monaci, C. Pagani and D. Vigo, Heuristic approaches for the fleet size and mix vehicle routing problem with time windows. Transp. Sci. 41 (2007) 516–526. | DOI

M. Desrochers, J.K. Lenstra and M.W.P. Savelsbergh. A classification scheme for vehicle routing and scheduling problems. Eur. J. Oper. Res. 46 (1990) 322–332. | DOI | Zbl

B. Eksioglu, A.V. Vural and A. Reisman, The vehicle routing problem: A taxonomic review. Comput. Ind. Engrg. 57 (2009) 1472–1483. | DOI

A. El Fallahi, C. Prins and R. Wolfler Calvo, A memetic algorithm and a tabu search for the multi-compartment vehicle routing problem. Comput. Oper. Res. 35 (2008) 1725–1741. | DOI | Zbl

P. Francis and K. Smilowitz, Modeling techniques for periodic vehicle routing problems. Transp. Res. Part B: Methodological 40 (2006) 872–884. | DOI

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

G. Gutiérrez-Jarpa, G. Desaulniers, G. Laporte and V. Marianov, A branch-and-price algorithm for the vehicle routing problem with deliveries, selective pickups and time windows. Eur. J. Oper. Res. 206 (2010) 341–349. | DOI | Zbl

R.L. Graham, E.L. Lawler, J.K. Lenstra and A.H.G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discrete Math. 5 (1977) 287–326. | DOI | MR | Zbl

N. Hayari, M.-A. Manier, C. Bloch and A. El Moudni, Un algorithme évolutionniste pour le problème de tournées sélectives avec contraintes de fenêtre de temps, in 4${}^e$ Conférence Francophone de Modélisation et Simulation MOSIM (2003).

W. Ho, G.T.S. Ho, P. Ji and H.C.W. Lau, A hybrid genetic algorithm for the multi-depot vehicle routing problem. Engrg. Appl. Artificial Intell. 21 (2008) 548–557. | DOI

A. Hoff, H. Andersson, M. Christiansen, G. Hasle and A. Løkketangen, Industrial aspects and literature survey: Fleet composition and routing. Comput. Oper. Res. 37 (2010) 2041–2061. | DOI | MR | Zbl

H. Housroum, Une approche génétique pour la résolution du problème VRPTW dynamique. Ph.D. thesis, Université d Artois, Laboratoire de Génie Informatique et d Automatique (2005).

W. Jih and Y. Hsu, A family competition genetic algorithm for the pickup and delivery problems with time window. Bull. College Engrg. 90 (2004) 121–130.

Y. Kergosien, C. Lenté, D. Piton and J.-C. Billaut, A tabu search heuristic for the dynamic transportation of patients between care units. Eur. J. Oper. Res. 214 (2011) 442–452. | DOI | Zbl

P. Lacomme and C. Prins, Algorithmes de découpage pour les problémes de tournées de véhicules Vehicle Routing, in 6${}^e$ Conférence Francophone de Modélisation et Simulation MOSIM (2006).

P. Lacomme, C. Prins and W. Ramdane-Chérif, Competitive Memetic Algorithms for Arc Routing Problems. Ann. Oper. Res. 131 (2004) 159–185. | DOI | MR | Zbl

P. Lacomme, C. Prins and W. Ramdane-Chérif, Evolutionary algorithms for periodic arc routing problems. Eur. J. Oper. Res. 165 (2005) 535–553. | DOI | Zbl

G. Laporte, Fifty years of vehicle routing. Transp. Sci. 43 (2009) 408–416. | DOI

G. Laporte, M. Gendreau, J.-Y. Potvin and F. Semet, Classical and modern heuristics for the vehicle routing problem. Int. Trans. Oper. Res. 7 (2000) 285–300. | DOI | MR

A. Le Bouthillier, Modélisation UML pour une architecture cooperative appliquée au problème de tournées de véhicules avec fenêtres de temps. Master thesis de Montréal, Département d’informatique et de recherche opérationnelle (2000).

F.-H. Liu and S.-Y. Shen, A method for vehicle routing problem with multiple vehicle types and time windows, in proceedings of the National Science Council Republic of China Part A Phys. Sci. Engrg. 23 (1999) 526–536.

A. Larsen, The dynamic vehicle routing problem. Ph.D. thesis, Institute of Mathematical Modelling, Technical University of Denmark (2000).

N. Labadi, C. Prins and M. Reghioui, A memetic algorithm for the vehicle routing problem with time windows. Rairo-Oper. Res. 42 (2008) 415–431. | DOI | Numdam | MR | Zbl

H.C. Lau, M. Sim and K.M. Teo, Vehicle routing problem with time windows and a limited number of vehicles. Eur. J. Oper. Res. 148 (2003) 559–569. | DOI | MR | Zbl

http://neo.lcc.uma.es/radi-aeb/WebVRP.

F.-H. Liu and S.-Y. Shen, The fleet size and mix vehicle routing problem with time windows. J. Oper. Res. Soc. 50 (1999) 721–732. | DOI | Zbl

J.E. Mendoza, B. Castanier, C. Guéret, A.L. Medaglia and N. Velasco, A memetic algorithm for the multi-compartment vehicle routing problem with stochastic demands. Comput. Oper. Res. 37 (2010) 1886–1898. | DOI | MR | Zbl

H. Min, V. Jayaraman and R. Srivastava, Combined location-routing problems: A synthesis and future research directions. Eur. J. Oper. Res. 108 (1998) 1–15. | DOI | Zbl

A. Mingozzi, The multi-depot periodic vehicle routing problem, in Abstraction, Reformulation and Approximation, Springer (2005) 347–350.

M. Mirabi, S.M.T. Fatemi Ghomi and F. Jolai, Efficient stochastic hybrid heuristics for the multi-depot vehicle routing problem. Robot. Comput. Integr. Manuf. 26 (2010) 564–569. | DOI

G. Mosheiov, Vehicle routing with pick-up and delivery: tour-partitioning heuristics. Comput. Ind. Engrg. 34 (1998) 669–684. | DOI

M. Mourgaya and F. Vanderbeck, The periodic vehicle routing problem: classification and heuristic. Rairo-Oper. Res. 40 (2006) 169–194. | DOI | Numdam | Zbl

M.-A. Manier and C. Bloch, A classification for hoist scheduling problems. Int. J. Flex. Manuf. Syst. 15 (2003) 37–55. | DOI

A. Nait-Sidi-Moh, M.-A. Manier, A. El Moudni and H. Manier, Max-plus algebra modeling for a public transport system. Cyberm. Syst. 36 (2005) 165–180. | DOI | Zbl

A.G. Najera, A genetic algorithm for the capacitated vehicle routing problem. Working paper, School of Computer Science, University of Birmingham (2007).

A. Olivera and O. Viera, Adaptive memory programming for the vehicle routing problem with multiple trips. Comput. Oper. Res. 34 (2007) 28–47. | DOI | MR | Zbl

I.H. Osman, Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Ann. Oper. Res. 41 (1993) 421–451. | DOI | Zbl

B. Ombuki, B.J. Ross and F. Hanshar, Multi-objective genetic algorithms for vehicle routing problem with time windows. Appl. Intell. 24 (2006) 17–30. | DOI

G. Pankratz, A grouping genetic algorithm for the pickup and delivery problem with time windows. Oper. Res. Spectrum 27 (2005) 21–41. | DOI | MR | Zbl

S.N. Parragh, K.F. Doerner and R.F. Hartl, A survey on pickup and delivery problems. Journal für Betriebswirtschaft 58 (2008) 81–117. | DOI

S.N. Parragh, K.F. Doerner and R.F. Hartl, A survey on pickup and delivery problems. Journal für Betriebswirtschaft 58 (2008) 21–51. | DOI

G. Perboli and R. Tadei. New families of valid inequalities for the two-echelon vehicle routing problem. Electronic Notes in Discrete Mathematics 36 (2010) 639–646. | DOI | Zbl

V. Pillac, M. Gendreau, C. Guéret and A.L. Medaglia, A review of dynamic vehicle routing problems. Eur. J. Oper. Res. 225 (2013) 1–11. | DOI | MR | Zbl

C. Prins, Two memetic algorithms for heterogeneous fleet vehicle routing problems. Engineering Applications of Artificial Intelligence 22 (2009) 916–928. | DOI

C. Prins and S. Bouchenoua, A memetic algorithm solving the vrp, the carp and general routing problems with nodes, edges and arcs, in Recent Advances in Memetic Algorithms, edited by WilliamE. Hart, J.E. Smith and N. Krasnogor. vol. 166 of Studies in Fuzziness and Soft Computing. Springer: Berlin Heidelberg (2005) 65–85.

C. Prins, A simple and effective evolutionary algorithm for the vehicle routing problem. Comput. Oper. Res. 31 (2004) 1985–2002. | DOI | MR | Zbl

M.-C. Portmann and A. Vignier, Performances’s study on crossover operators keeping good schemata for some scheduling problems, in Proc. of the Genetic and Evolutionary Computation Conference (GECCO ’00), Las Vegas, Nevada, USA (2000) 331–338.

J.-Y. Potvin, State-of-the art review – evolutionary algorithms for vehicle routing. INFORMS J. Computing 21 (2009) 518–548. | DOI | MR | Zbl

P. Prosser, P.J. Kilby and P. Shaw, A comparison of traditional and constraint-based heuristic methods on vehicle routing problems with side constraints. Constraints 5 (2000) 389–414. | DOI | MR | Zbl

H.N. Psaraftis. Dynamic vehicle routing: Status and prospects. Ann. Oper. Res. 61 (1995) 143–164. | DOI | Zbl

Y. Rahmani, A. Oulamara, W.R. Cherif and others, Multi-products Location-Routing problem with Pickup and Delivery, in Proc. of the IEEE ICALT’2013 (2013) 155–122.

Y. Rahmani, A. Oulamara, W.R. Cherif and others. Multi-products Location-Routing problem with Pickup and Delivery: Two-Echelon model, in Proc. of the 11th IFAC Workshop on Intelligent Manufacturing Systems (2013).

W. Ramdane Cherif, Evolutionary Algorithms for Capacitated Arc Routing problems with Time Windows, in Proc. of the 12th Symposium on Information Control Problems in Manufacturing INCOM$\text{'}$06 3 (2006) 355–360.

J. Renaud, F.F. Boctor and G. Laporte, An improved petal heuristic for the vehicle routeing problem. J. Oper. Res. Soc. 47 (1996) 329–336. | DOI | Zbl

M. Salari, P. Toth and A. Tramontani, An ILP improvement procedure for the Open Vehicle Routing Problem. Comput. Oper. Res. 37 (2010) 2106–2120. | DOI | Zbl

A.H.G. Rinnooy Kan, Machine Scheduling Problems: Classification, Complexity and Computations. Nijhoff (1976). | Zbl

S. Ropke and D. Pisinger, A unified heuristic for a large class of vehicle routing problems with backhauls. Eur. J. Oper. Res. 171 (2006) 750–775. | DOI | Zbl

V. Schmid, K.F. Doerner and G. Laporte, Rich routing problems arising in supply chain management. Eur. J. Oper. Res. 224 (2013) 435–448. | DOI | Zbl

S. Salhi and G. Nagy, A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling. J. Oper. Res. Soc. (1999) 1034–1042. | Zbl

Z. Shen, F. Ordónez and M.M. Dessouky, The minimum unmet demand stochastic vehicle routing problem (2006).

K. Sørensen, A framework for robust and flexible optimization using metaheuristics with applications in supply chain design. Ph.D. thesis, Universiteit Antwerpen Faculteit Toegepaste Economische Wetenschappen (2003).

J. Tavares, P. Machado, F.B. Pereira and E. Costa, On the influence of GVR in vehicle routing, in Proc. of the 2003 ACM symposium on Applied Computing (2003) 753–758.

P. Toth and D. Vigo, The vehicle routing problem, Monographs on Discrete Mathematics and Applications, 9, 367 pages (2002). | Zbl

F. Tricoire, Vehicle and personnel routing optimization in the service sector: application to water distribution and treatment. 4OR 5 (2007) 165–168. | DOI | Zbl

T. Vidal, T.G. Crainic, M. Gendreau, N. Lahrichi and W. Rei, A hybrid genetic algorithm for multidepot and periodic vehicle routing problems. Oper. Res. 60 2012 611–624. | DOI | Zbl

T. Vidal, T.G. Crainic, M. Gendreau and C. Prins, Heuristics for multi-attribute vehicle routing problems: A survey and synthesis. Eur. J. Oper. Res. 231 (2013) 1–21. | DOI | Zbl

D. Vigo, J.-F. Cordeau, G. Laporte and M.W.P. Savelsbergh, Vehicle routing. Handbooks in Operation Research Management Science 14 (2005) 367–428.

D.S. Vianna, L.S. Ochi and L.M.A. Drummond, Parallel Hybrid Evolutionary Metaheuristic for the Period Vehicle Routing Problem, in Proc. of IEEE 13th International Parallel Processing Symposium/10th Symposium on Parallel and Distributed Processing (IPPS/SPDP ’99) (1999).