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.

Accepted:

DOI: 10.1051/ro/2014030

Keywords: Vehicle Routing, VRP, classification, notation

^{1}; Rachid, Mais Haj

^{2}; Bloch, Christelle

^{3}; Chatonnay, Pascal

^{3}

@article{RO_2015__49_1_161_0, author = {Cherif-Khettaf, Wahiba Ramdane and Rachid, Mais Haj and Bloch, Christelle and Chatonnay, Pascal}, title = {New {Notation} and {Classification} {Scheme} for {Vehicle} {Routing} {Problems}}, journal = {RAIRO - Operations Research - Recherche Op\'erationnelle}, pages = {161--194}, publisher = {EDP-Sciences}, volume = {49}, number = {1}, year = {2015}, doi = {10.1051/ro/2014030}, mrnumber = {3349122}, zbl = {1310.90011}, language = {en}, url = {http://archive.numdam.org/articles/10.1051/ro/2014030/} }

TY - JOUR AU - Cherif-Khettaf, Wahiba Ramdane AU - Rachid, Mais Haj AU - Bloch, Christelle AU - Chatonnay, Pascal TI - New Notation and Classification Scheme for Vehicle Routing Problems JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2015 SP - 161 EP - 194 VL - 49 IS - 1 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ro/2014030/ DO - 10.1051/ro/2014030 LA - en ID - RO_2015__49_1_161_0 ER -

%0 Journal Article %A Cherif-Khettaf, Wahiba Ramdane %A Rachid, Mais Haj %A Bloch, Christelle %A Chatonnay, Pascal %T New Notation and Classification Scheme for Vehicle Routing Problems %J RAIRO - Operations Research - Recherche Opérationnelle %D 2015 %P 161-194 %V 49 %N 1 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ro/2014030/ %R 10.1051/ro/2014030 %G en %F RO_2015__49_1_161_0

Cherif-Khettaf, Wahiba Ramdane; Rachid, Mais Haj; Bloch, Christelle; Chatonnay, Pascal. New Notation and Classification Scheme for Vehicle Routing Problems. RAIRO - Operations Research - Recherche Opérationnelle, Volume 49 (2015) no. 1, pp. 161-194. doi : 10.1051/ro/2014030. http://archive.numdam.org/articles/10.1051/ro/2014030/

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

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

, and ,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

, and ,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).

Industrial aspects and literature survey: Combined inventory management and routing. Comput. Oper. Res. 37 (2010) 1515–1536. | DOI | MR | Zbl

, , , and ,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.

A tabu search algorithm for the split delivery vehicle routing problem. Transp. Sci. 40 (2006) 64–73. | DOI

, and ,Static pickup and delivery problems: a classification scheme and survey. Top 15 (2007) 1–31. | DOI | MR | Zbl

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

, and ,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).

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

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

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

,A new subtour elimination constraint for the vehicle routing problem. Eur. J. Oper. Res. 91 (1995) 573–586. | Zbl

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

, and ,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.

Hybrid discrete particle swarm optimization algorithm for capacitated vehicle routing problem. J. Zhejiang University Science A 7 (2006) 607–614. | DOI | Zbl

, and ,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).

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

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

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

The truck dispatching problem. Manage. Sci. 6 (1959) 80–91. | DOI | MR | Zbl

and ,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

Heuristic approaches for the fleet size and mix vehicle routing problem with time windows. Transp. Sci. 41 (2007) 516–526. | DOI

, , and ,A classification scheme for vehicle routing and scheduling problems. Eur. J. Oper. Res. 46 (1990) 322–332. | DOI | Zbl

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

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

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

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

, , and ,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

, , and ,Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discrete Math. 5 (1977) 287–326. | DOI | MR | Zbl

, , and ,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).

A hybrid genetic algorithm for the multi-depot vehicle routing problem. Engrg. Appl. Artificial Intell. 21 (2008) 548–557. | DOI

, , and ,Industrial aspects and literature survey: Fleet composition and routing. Comput. Oper. Res. 37 (2010) 2041–2061. | DOI | MR | Zbl

, , , and ,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).

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

and ,A tabu search heuristic for the dynamic transportation of patients between care units. Eur. J. Oper. Res. 214 (2011) 442–452. | DOI | Zbl

, , and ,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).

Competitive Memetic Algorithms for Arc Routing Problems. Ann. Oper. Res. 131 (2004) 159–185. | DOI | MR | Zbl

, and ,Evolutionary algorithms for periodic arc routing problems. Eur. J. Oper. Res. 165 (2005) 535–553. | DOI | Zbl

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

,Classical and modern heuristics for the vehicle routing problem. Int. Trans. Oper. Res. 7 (2000) 285–300. | DOI | MR

, , and ,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).

A memetic algorithm for the vehicle routing problem with time windows. Rairo-Oper. Res. 42 (2008) 415–431. | DOI | Numdam | MR | Zbl

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

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

The fleet size and mix vehicle routing problem with time windows. J. Oper. Res. Soc. 50 (1999) 721–732. | DOI | Zbl

and ,A memetic algorithm for the multi-compartment vehicle routing problem with stochastic demands. Comput. Oper. Res. 37 (2010) 1886–1898. | DOI | MR | Zbl

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

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

Efficient stochastic hybrid heuristics for the multi-depot vehicle routing problem. Robot. Comput. Integr. Manuf. 26 (2010) 564–569. | DOI

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

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

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

and ,Max-plus algebra modeling for a public transport system. Cyberm. Syst. 36 (2005) 165–180. | DOI | Zbl

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

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

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

,Multi-objective genetic algorithms for vehicle routing problem with time windows. Appl. Intell. 24 (2006) 17–30. | DOI

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

,A survey on pickup and delivery problems. Journal für Betriebswirtschaft 58 (2008) 81–117. | DOI

, and ,A survey on pickup and delivery problems. Journal für Betriebswirtschaft 58 (2008) 21–51. | DOI

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

and .A review of dynamic vehicle routing problems. Eur. J. Oper. Res. 225 (2013) 1–11. | DOI | MR | Zbl

, , and ,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.

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.

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

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

, and ,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.

An improved petal heuristic for the vehicle routeing problem. J. Oper. Res. Soc. 47 (1996) 329–336. | DOI | Zbl

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

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

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

and ,Rich routing problems arising in supply chain management. Eur. J. Oper. Res. 224 (2013) 435–448. | DOI | Zbl

, and ,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

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

,A hybrid genetic algorithm for multidepot and periodic vehicle routing problems. Oper. Res. 60 2012 611–624. | DOI | Zbl

, , , and ,Heuristics for multi-attribute vehicle routing problems: A survey and synthesis. Eur. J. Oper. Res. 231 (2013) 1–21. | DOI | Zbl

, , and ,Vehicle routing. Handbooks in Operation Research Management Science 14 (2005) 367–428.

, , and ,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).

*Cited by Sources: *