More Web Proxy on the site http://driver.im/

research-article

Rich Vehicle Routing Problem: Survey

Authors:

Jose Caceres-Cruz,

Daniel Guimarans,

Angel A. JuanAuthors Info & Claims

ACM Computing Surveys (CSUR), Volume 47, Issue 2

Article No.: 32, Pages 1 - 28

https://doi.org/10.1145/2666003

Published: 19 December 2014 Publication History

Abstract

The Vehicle Routing Problem (VRP) is a well-known research line in the optimization research community. Its different basic variants have been widely explored in the literature. Even though it has been studied for years, the research around it is still very active. The new tendency is mainly focused on applying this study case to real-life problems. Due to this trend, the Rich VRP arises: combining multiple constraints for tackling realistic problems. Nowadays, some studies have considered specific combinations of real-life constraints to define the emerging Rich VRP scopes. This work surveys the state of the art in the field, summarizing problem combinations, constraints defined, and approaches found.

References

[1]

P. Amorim, S. N. Parragh, F. Sperandio, and B. Almada-Lobo. 2012. A rich vehicle routing problem dealing with perishable food: A case study. TOP 22, 2 (2012), 1--20.

[2]

R. Baldacci, E. Bartolini, A. Mingozzi, and R. Roberti. 2010. An exact solution framework for a broad class of vehicle routing problems. Computational Management Science 7, 3 (2010), 229--268.

[3]

R. Baldacci, E. Bartolini, A. Mingozzi, and A. Valletta. 2011a. An exact algorithm for the period routing problem. Operations Research 59, 1 (2011), 228--241.

Digital Library

[4]

R. Baldacci, M. Battarra, and D. Vigo. 2008. Routing a heterogeneous fleet of vehicles. In The Vehicle Routing Problem: Latest Advances and New Challenges, B. Golden, S. Raghavan, and E. Wasil (Eds.). Operations Research/Computer Science Interfaces, Vol. 43. Springer, 3--27.

[5]

R. Baldacci, M. Battarra, and D. Vigo. 2009. Valid inequalities for the fleet size and mix vehicle routing problem with fixed costs. Networks 54, 4 (2009), 178--189.

Digital Library

[6]

R. Baldacci and A. Mingozzi. 2009. A unified exact method for solving different classes of vehicle routing problems. Mathematical Programming 120, 2 (2009), 347--380.

Digital Library

[7]

R. Baldacci, A. Mingozzi, and R. Roberti. 2012. Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints. European Journal of Operational Research 218, 1 (2012), 1--6.

[8]

R. Baldacci, A. Mingozzi, and R. Wolfler-Calvo. 2011b. An exact method for the capacitated location-routing problem. Operations Research 59, 5 (2011), 1284--1296.

Digital Library

[9]

R. Baldacci, P. Toth, and D. Vigo. 2010. Exact algorithms for routing problems under vehicle capacity constraints. Annals of Operations Research 175, 1 (2010), 213--245.

[10]

M. Battarra. 2011. Exact and heuristic algorithms for routing problems. 4OR 9 (2011), 421--424.

[11]

M. Battarra, M. Monaci, and D. Vigo. 2009. An adaptive guidance approach for the heuristic solution of a minimum multiple trip vehicle routing problem. Computers & Operations Research 36, 11 (2009), 3041--3050.

Digital Library

[12]

T. Bektaş and G. Laporte. 2011. The pollution-routing problem. Transportation Research Part B: Methodological 45, 8 (2011), 1232--1250.

[13]

A. Bettinelli, A. Ceselli, and G. Righini. 2011. A branch-and-cut-and-price algorithm for the multi-depot heterogeneous vehicle routing problem with time windows. Transportation Research Part C: Emerging Technologies 19, 5 (2011), 723--740.

[14]

M. C. Bolduc, J. Renaud, and B. Montreuil. 2006. Synchronized routing of seasonal products through a production/distribution network. Central European Journal of Operations Research 14, 2 (2006), 209--228.

[15]

O. Bräysy and M. Gendreau. 2005a. Vehicle routing problem with time windows, part I: Route construction and local search algorithms. Transportation Science 39, 1 (2005), 104--118.

Digital Library

[16]

O. Bräysy and M. Gendreau. 2005b. Vehicle routing problem with time windows, part II: Metaheuristics. Transportation Science 39, 1 (2005), 119--139.

Digital Library

[17]

A. Ceselli, G. Righini, and M. Salani. 2009. A column generation algorithm for a rich vehicle-routing problem. Transportation Science 43, 1 (2009), 56--69.

Digital Library

[18]

G. Clarke and J. W. Wright. 1964. Scheduling of vehicles from central depot to number of delivery points. Operations Research 12, 4 (1964), 568--581.

Digital Library

[19]

J. F. Cordeau, M. Gendreau, and G. Laporte. 1997. A Tabu search heuristic for periodic and multi-depot vehicle routing problems. Networks 30, 2 (1997), 105--119.

[20]

J. F. Cordeau and G. Laporte. 2003. A Tabu search heuristic for the static multi-vehicle dial-a-ride problem. Transportation Research Part B: Methodological 37, 6 (2003), 579--594.

[21]

J. F. Cordeau, G. Laporte, and A. Mercier. 2001. A unified Tabu search heuristic for vehicle routing problems with time windows. Journal of the Operational Research Society 52, 8 (2001), 928--936.

[22]

J. F. Cordeau, G. Laporte, and A. Mercier. 2004. Improved Tabu search algorithm for the handling of route duration constraints in vehicle routing problems with time windows. Journal of the Operational Research Society 55, 5 (2004), 542--546.

[23]

T. G. Crainic, G. C. Crisan, M. Gendreau, N. Lahrichi, and W. Rei. 2009a. A concurrent evolutionary approach for rich combinatorial optimization. In Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference: Late Breaking Papers. 2017--2022.

Digital Library

[24]

T. G. Crainic, G. C. Crisan, M. Gendreau, N. Lahrichi, and W. Rei. 2009b. Multi-thread integrative cooperative optimization for rich combinatorial problems. In Proceedings of the IEEE International Symposium on Parallel & Distributed Processing (IPDPS). 1--8.

Digital Library

[25]

G. Dantzig and J. H. Ramser. 1959. The truck dispatching problem. Management Science 6, 1 (1959), 80--91.

Digital Library

[26]

R. Dechter and J. Pearl. 1985. Generalized best-first search strategies and the optimality of A&ast;. J. ACM 32, 3 (1985), 505--536.

Digital Library

[27]

E. Demir, T. Bektaş, and G. Laporte. 2012a. An adaptive large neighborhood search heuristic for the Pollution-Routing Problem. European Journal of Operational Research 223, 2 (2012), 346--359.

[28]

E. Demir, T. Bektaş, and G. Laporte. 2012b. The bi-objective pollution-routing problem. European Journal of Operational Research 232, 3 (2012), 464--478.

[29]

E. Demir, T. Bektaş, and G. Laporte. 2014. A review of recent research on green road freight transportation. European Journal of Operational Research 237, 3 (2014), 775--793.

[30]

U. Derigs and T. Döhmer. 2005. Router: A fast and flexible local search algorithm for a class of rich vehicle routing problems. In Operations Research Proceedings 2004, H. Fleuren, D. Hertog, and P. Kort (Eds.). Vol. 2004. Springer, 144--149.

[31]

U. Derigs, M. Pullmann, and U. Vogel. 2013. A short note on applying a simple LS/LNS-based metaheuristic to the rollon-rolloff vehicle routing problem. Computers & Operations Research 40, 3 (2013), 867--872.

Digital Library

[32]

G. Desaulniers, J. Desrosiers, and M. M. Solomon. 2005. Column Generation. Springer.

[33]

K. F. Doerner and V. Schmid. 2010. Survey: Matheuristics for rich vehicle routing problems. In Hybrid Metaheuristics, M. Blesa, C. Blum, G. Raidl, A. Roli, and M. Sampels (Eds.). Lecture Notes in Computer Science, Vol. 6373. Springer, 206--221.

Digital Library

[34]

M. Dorigo and L. M. Gambardella. 1997. Ant colonies for the travelling salesman problem. BioSystems 43, 2 (1997), 73--81.

[35]

European Commission EC. 2008. Greening Transport. Communication from the Commission to the European Parliament and the Council SEC(2008) 2206. European Union.

[36]

European Commission EC. 2011. Roadmap to a single European transport area: Towards a competitive and resource efficient transport system. Impact assessment. White Paper SEC(2011) 358. European Union.

[37]

B. Eksioglu, A. Volkan-Vural, and A. Reisman. 2009. The vehicle routing problem: A taxonomic review. Computers & Industrial Engineering 57, 4 (2009), 1472--1483.

Digital Library

[38]

S. Erdoğan and E. Miller-Hooks. 2012. A green vehicle routing problem. Transportation Research Part E: Logistics and Transportation Review 48, 1 (2012), 100--114.

[39]

A. Fügenschuh. 2006. The vehicle routing problem with coupled time windows. Central European Journal of Operations Research 14, 2 (2006), 157--176.

[40]

M. R. Garey and D. S. Johnson. 1979. Computers and intractability: a guide to the theory of NP-Completeness. W.H. Freeman & Co.

Digital Library

[41]

M. Gendreau, J. Y. Potvin, O. Bräumlaysy, G. Hasle, and A. Løkketangen. 2008. Metaheuristics for the vehicle routing problem and its extensions: A categorized bibliography. In The Vehicle Routing Problem: Latest Advances and New Challenges, B. Golden, S. Raghavan, and E. Wasil (Eds.). Operations Research/Computer Science Interfaces, Vol. 43. Springer, 143--169.

[42]

A. Goel. 2010. A column generation heuristic for the general vehicle routing problem. In Learning and Intelligent Optimization, C. Blum and R. Battiti (Eds.). Lecture Notes in Computer Science, Vol. 6073. Springer, 1--9.

Digital Library

[43]

A. Goel and V. Gruhn. 2005. Large neighborhood search for rich VRP with multiple pickup and delivery locations. In Proceedings of the 18th Mini EURO Conference on VNS (MEC-VNS).

[44]

A. Goel and V. Gruhn. 2006. Solving a dynamic real-life vehicle routing problem. In Operations Research Proceedings 2005, H. D. Haasis, H. Kopfer, and J. Schönberger (Eds.). Operations Research Proceedings, Vol. 2005. Springer, 367--372.

[45]

A. Goel and V. Gruhn. 2008. A general vehicle routing problem. European Journal of Operational Research 191, 3 (2008), 650--660.

[46]

B. L. Golden, A. Assad, L. Levy, and F. Gheysens. 1984. The fleet size and mix vehicle routing problem. Computers & Operations Research 11, 1 (1984), 49--66.

[47]

B. L. Golden, S. Raghavan, and E. A. Wasil. 2008. The Vehicle Routing Problem: Latest Advances and New Challenges. Springer.

[48]

I. Gribkovskaia and G. Laporte. 2008. One-to-many-to-one single vehicle pickup and delivery problems. In The Vehicle Routing Problem: Latest Advances and New Challenges, Bruce Golden, S. Raghavan, and Edward Wasil (Eds.). Springer, 359--377.

[49]

C. Groër, B. Golden, and E. Wasil. 2010. A library of local search heuristics for the vehicle routing problem. Mathematical Programming Computation 2, 2 (2010), 79--101.

[50]

D. Guimarans. 2012. Hybrid Algorithms for Solving Routing Problems. Ph.D. Dissertation. Universitat Autònoma Barcelona.

[51]

D. Guimarans, R. Herrero, D. Riera, A. A. Juan, and J. J. Ramos. 2011. Combining probabilistic algorithms, constraint programming and Lagrangian relaxation to solve the vehicle routing problem. Annals of Mathematics and Artificial Intelligence 62, 3--4 (2011), 299--315.

Digital Library

[52]

P. E Hart, N. J Nilsson, and B. Raphael. 1968. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics 4, 2 (1968), 100--107.

[53]

R. F. Hartl, G. Hasle, and G. K. Janssens. 2006. Special issue on rich vehicle routing problems. Central European Journal of Operations Research 14, 2 (2006), 103--104.

[54]

H. Hashimoto, T. Ibaraki, S. Imahori, and M. Yagiura. 2006. The vehicle routing problem with flexible time windows and traveling times. Discrete Applied Mathematics 154, 16 (2006), 2271--2290.

Digital Library

[55]

H. Hashimoto, M. Yagiura, and T. Ibaraki. 2008. An iterated local search algorithm for the time-dependent vehicle routing problem with time windows. Discrete Optimization 5, 2 (2008), 434--456.

Digital Library

[56]

G. Hasle and O. Kloster. 2007. Industrial vehicle routing. In Geometric Modelling, Numerical Simulation, and Optimization, G. Hasle, K. A. Lie, and E. Quak (Eds.). Springer, 397--435.

[57]

G. Hasle, O. Kloster, E. J. Nilssen, A. Riise, and M. Smedsrud. 2005. Scalable and instance robust metaheuristics for a rich VRP model. In ROUTE 2005 - International Workshop on Vehicle Routing and Intermodal Transportation.

[58]

G. Hasle, A. Løkketangen, and S. Martello. 2006. Rich models in discrete optimization: Formulation and resolution (ECCO XVI). European Journal of Operational Research 175, 3 (2006), 1752--1753.

[59]

A. Hoff. 2006. Heuristics for Rich Vehicle Routing Problem. Ph.D. Dissertation. Molde University College.

[60]

A. Hoff, I. Gribkovskaia, G. Laporte, and A. Løkketangen. 2009. Lasso solution strategies for the vehicle routing problem with pickups and deliveries. European Journal of Operational Research 192, 3 (2009), 755--766.

[61]

A. Hoff, A. G. Lium, A. Løkketangen, and T. G. Crainic. 2010. A metaheuristic for stochastic service network design. Journal of Heuristics 16, 5 (2010), 653--679.

Digital Library

[62]

A. Hoff and A. Løkketangen. 2006. Creating lasso-solutions for the traveling salesman problem with pickup and delivery by Tabu search. Central European Journal of Operations Research 14, 2 (2006), 125--140.

[63]

A. Hoff and A. Løkketangen. 2007. A Tabu search approach for milk collection in western Norway using trucks and trailers. In Proceedings of the 6th Triennial Symposium on Transportation Analysis.

[64]

T. Ibaraki, S. Imahori, M. Kubo, T. Masuda, T. Uno, and M. Yagiura. 2005. Effective local search algorithms for routing and scheduling problems with general time-window constraints. Transportation Science 39, 2 (2005), 206--232.

Digital Library

[65]

Y. Ileri, M. Bazaraa, T. Gifford, G. Nemhauser, J. Sokol, and E. Wikum. 2006. An optimization approach for planning daily drayage operations. Central European Journal of Operations Research 14, 2 (2006), 141--156.

[66]

S. Irnich. 2008. A unified modeling and solution framework for vehicle routing and local search-based metaheuristics. INFORMS Journal on Computing 20, 2 (2008), 270--287.

Digital Library

[67]

A. A. Juan, J. Faulin, S. Grasman, and K. Govindan. 2014. Special issue on rich and real-life vehicle routing problems. International Journal of Advanced Operations Management 6, 1 (2014), 1--3.

[68]

A. A. Juan, J. Faulin, S. Grasman, D. Riera, J. Marull, and C. Mendez. 2011. Using safety stocks and simulation to solve the vehicle routing problem with stochastic demands. Transportation Research Part C: Emerging Technologies 19, 5 (2011), 751--765.

[69]

A. A. Juan, J. Faulin, R. Ruiz, B. B. Barrios, and S. Caballe. 2010. The SR-GCWS hybrid algorithm for solving the capacitated vehicle routing problem. Applied Soft Computing 10, 1 (2010), 215--224.

Digital Library

[70]

A. A. Juan, J. Goentzel, and T. Bektaş. 2014a. Routing fleets with multiple driving ranges: Is it possible to use greener fleet configurations&quest; Applied Soft Computing 21 (2014), 84--94.

[71]

A. A. Juan, S. Grasman, J. Caceres-Cruz, and T. Bektaş. 2014b. A simheuristic algorithm for the single-period stochastic inventory-routing problem with stock-outs. Simulation Modelling Practice and Theory 46 (2014), 40--52.

[72]

A. L. Kok, C. M. Meyer, H. Kopfer, and J. M. J. Schutten. 2010. A dynamic programming heuristic for the vehicle routing problem with time windows and European community social legislation. Transportation Science 44, 4 (2010), 442--454.

Digital Library

[73]

H. W. Kopfer, J. Schönberger, and H. Kopfer. 2014. Reducing greenhouse gas emissions of a heterogeneous vehicle fleet. Flexible Services and Manufacturing Journal 26, 1--2 (2014), 221--248.

[74]

R. E. Korf. 1985. Depth-first iterative-deepening: An optimal admissible tree search. Artificial Intelligence 27, 1 (1985), 97--109.

Digital Library

[75]

R. Lahyani, M. Khemakhem, F. Semet, and H. Chabchoub. 2012. Taxonomy for rich vehicle routing problems. In Proceedings of the 1st International IEEE Conference on Logistics Operations Management.

[76]

S. Lannez, C. Artigues, J. J. Damay, and M. Gendreau. 2010. Column generation heuristic for a rich arc routing problem. In Proccedings of the 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS’10), Vol. 14. 130--141.

[77]

G. Laporte. 2007. What you should know about the vehicle routing problem. Naval Research Logistics 54 (2007), 811--819.

[78]

G. Laporte. 2009. Fifty years of vehicle routing. Transportation Science 43, 4 (2009), 408--416.

Digital Library

[79]

G. Laporte, M. Gendreau, J. Y. Potvin, and F. Semet. 2000. Classical and modern heuristics for the vehicle routing problem. International Transactions in Operational Research 7, 4--5 (2000), 285--300.

[80]

G. Laporte, P. Toth, and D. Vigo. 2013. Vehicle routing: Historical perspective and recent contributions. EURO Journal on Transportation and Logistics 2, 1--2 (2013), 1--4.

[81]

J. K. Lenstra and A. H. G. Rinnooy-Kan. 1981. Complexity of vehicle routing and scheduling problems. Networks 11, 2 (1981), 221--227.

[82]

H. Li and A. Lim. 2001. A metaheuristic for the pickup and delivery problem with time windows. In Proceedings of the 13th International Conference on Tools with Artificial Intelligence. IEEE, 160--167.

Digital Library

[83]

C. Lin, K. L. Choy, G. T. S. Ho, S. H. Chung, and H. Y. Lam. 2014. Survey of green vehicle routing problem: Past and future trends. Expert Systems with Applications 41, 4 (2014), 1118--1138.

Digital Library

[84]

H. R. Lourenço, O. C. Martin, and T. Stützle. 2010. Iterated local search: Framework and applications. In Handbook of Metaheuristics, M. Gendreau and J. Y. Potvin (Eds.). International Series in Operations Research & Management Science, Vol. 146. Springer, 363--397.

[85]

J. M. D. Magalhães and J. P. Sousa. 2006. Dynamic VRP in pharmaceutical distribution - a case study. Central European Journal of Operations Research 14, 2 (2006), 177--192.

[86]

A. G. Nikolaev and S. H. Jacobson. 2010. Simulated annealing. In Handbook of Metaheuristics, M. Gendreau and J. Y. Potvin (Eds.). International Series in Operations Research & Management Science, Vol. 146. Springer, 1--39.

[87]

J. Oppen, A. Løkketangen, and J. Desrosiers. 2010. Solving a rich vehicle routing and inventory problem using column generation. Computers & Operations Research 37, 7 (2010), 1308--1317.

Digital Library

[88]

J. Orozco. 2011. A Microscopic Traffic Simulation Based Decision Support System for Real-Time Fleet Management. Ph.D. Dissertation. Universitat Politècnica de Catalunya.

[89]

P. Pellegrini. 2005. Application of Two Nearest Neighbor Approaches to a Rich Vehicle Routing Problem. Technical Report TR/IRIDIA/2005-15. IRIDIA, Université Libre de Bruxelles, Brussels, Belgium.

[90]

P. Pellegrini, D. Favaretto, and E. Moretti. 2007. Multiple ant colony optimization for a rich vehicle routing problem: A case study. In Knowledge-Based Intelligent Information and Engineering Systems, B. Apolloni, R. J. Howlett, and L. Jain (Eds.). Lecture Notes in Computer Science, Vol. 4693. Springer, 627--634.

Digital Library

[91]

V. Pillac, M. Gendreau, C. Guéret, and A. Medaglia. 2013. A review of dynamic vehicle routing problems. European Journal of Operational Research 225, 1 (2013), 1--11.

[92]

D. Pisinger and S. Ropke. 2007. A general heuristic for vehicle routing problems. Computers & Operations Research 34, 8 (2007), 2403--2435.

Digital Library

[93]

E. Prescott-Gagnon, G. Desaulniers, and L. M. Rousseau. 2012. Heuristics for an oil delivery vehicle routing problem. Flexible Services and Manufacturing Journal (2012), 1--24.

[94]

C. Prins. 2004. A simple and effective evolutionary algorithm for the vehicle routing problem. Computers & Operations Research 31, 12 (2004), 1985--2002.

[95]

M. Reimann and H. Ulrich. 2006. Comparing backhauling strategies in vehicle routing using ant colony optimization. Central European Journal of Operations Research 14, 2 (2006), 105--123.

[96]

J. Rieck and J. Zimmermann. 2010. A new mixed integer linear model for a rich vehicle routing problem with docking constraints. Annals of Operations Research 181, 1 (2010), 337--358.

[97]

A. E. Rizzoli, R. Montemanni, E. Lucibello, and L. M. Gambardella. 2007. Ant colony optimization for real-world vehicle routing problems. Swarm Intelligence 1, 2 (2007), 135--151.

[98]

S. Ropke and D. Pisinger. 2006a. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation Science 40, 4 (2006), 455--472.

Digital Library

[99]

S. Ropke and D. Pisinger. 2006b. A unified heuristic for a large class of vehicle routing problems with backhauls. European Journal of Operational Research 171, 3 (2006), 750--775.

[100]

L. Ruinelli. 2011. Column Generation for a Rich VRP: VRP with Simultaneous Distribution, Collection and Pickup-and-Delivery. Ph.D. Dissertation. University of Applied Sciences and Arts of Southern Switzerland.

[101]

C. G. Santillán, L.C. Reyes, M. L. M. Rodríguez, J. J. G. Barbosa, O. C. López, G. R. Zarate, and P. Hernández. 2012. Variants of VRP to optimize logistics management problems. In Logistics Management and Optimization through Hybrid Artificial Intelligence Systems, O. Zezzatti, C. A. Ochoa, C. Chira, A. Hernandez, and M. Basurto (Eds.). Vol. 2012. IGI Global, 207--237.

[102]

V. Schmid, K. F. Doerner, and G. Laporte. 2013. Rich routing problems arising in supply chain management. European Journal of Operational Research 224, 3 (2013), 435--448.

[103]

P. Shaw. 1998. Using constraint programming and local search methods to solve vehicle routing problems. In Proceedings of the 4th International Conference on Principles and Practice of Constraint Programming (CP-98) (Lecture Notes in Computer Science), M. Maher and J. F. Puget (Eds.), Vol. 1520. 417--431.

Digital Library

[104]

K. C. Sinha and S. Labi. 2011. Transportation Decision Making: Principles of Project Evaluation and Programming. Wiley.

Digital Library

[105]

M. M. Solomon. 1987. Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research 35, 2 (1987), 254--265.

Digital Library

[106]

K. Sörensen. 2006. Route stability in vehicle routing decisions: A bi-objective approach using metaheuristics. Central European Journal of Operations Research 14, 2 (2006), 193--207.

[107]

T. Stützle and H. Hoos. 1997. MAX-MIN ant system and local search for the traveling salesman problem. In Proceedings of the IEEE International Conference on Evolutionary Computation. 309--314.

[108]

A. Subramanian. 2012. Heuristic, Exact and Hybrid Approaches for Vehicle Routing problems. Ph.D. Dissertation. Universidade Federal Fluminense.

[109]

A. Subramanian, P. H. V. Penna, E. Uchoa, and L. S. Ochi. 2012. A hybrid algorithm for the heterogeneous fleet vehicle routing problem. European Journal of Operational Research 221, 2 (2012), 285--295.

[110]

E. G. Talbi. 2009. Metaheuristics: From Design to Implementation. John Wiley & Sons, Inc.

Digital Library

[111]

P. Toth and D. Vigo. 2002. An overview of vehicle routing problems. In The Vehicle Routing Problem, P. Toth and D. Vigo (Eds.). SIAM - Society for Industrial and Applied Mathematics, Philadelphia, USA, 1--26.

Digital Library

[112]

S. Ubeda, F. J. Arcelus, and J. Faulin. 2011. Green logistics at Eroski: A case study. International Journal of Production Economics 131, 1 (2011), 44--51.

[113]

M. Vallejo, P. A. Vargas, and D. W. Corne. 2012. A fast approximative approach for the vehicle routing problem. In Proceedings of the 12th UK Workshop on Computational Intelligence (UKCI). IEEE, 1--8.

[114]

H. Van Essen, A. Schroten, M. Otten, D. Sutter, C. Schreyer, R. Zandonella, M. Maibach, and C. Doll. 2011. External Costs of Transport in Europe. Technical Report 11.4215.50. CE Delft, Delft, Netherlands.

[115]

P. Van Hentenryck. 1989. Constraint Satisfaction in Logic Programming. MIT Press.

Digital Library

[116]

T. Vidal, T. G. Crainic, M. Gendreau, and C. Prins. 2013a. Heuristics for multi-attribute vehicle routing problems: A survey and synthesis. European Journal of Operational Research 231, 1 (2013), 1--21.

[117]

T. Vidal, T. G. Crainic, M. Gendreau, and C. Prins. 2013b. A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows. Computers & Operations Research 40, 1 (2013), 475--489.

Digital Library

[118]

T. Vidal, T. G. Crainic, M. Gendreau, and C. Prins. 2013c. A unified solution framework for multi-attribute vehicle routing problems. European Journal of Operational Research 234, 3 (2013), 658--673.

[119]

M. Wen. 2010. Rich Vehicle Routing Problems and Applications. Ph.D. Dissertation. Technical University of Denmark.

[120]

M. Wen, J. F. Cordeau, G. Laporte, and J. Larsen. 2010. The dynamic multi-period vehicle routing problem. Computers & Operations Research 37, 9 (2010), 1615--1623.

Digital Library

[121]

M. Wen, E. Krapper, J. Larsen, and T. K. Stidsen. 2011. A multilevel variable neighborhood search heuristic for a practical vehicle routing and driver scheduling problem. Networks 58, 4 (2011), 311--322.

Digital Library

[122]

M. Wen, J. Larsen, J. Clausen, J. F. Cordeau, and G. Laporte. 2008. Vehicle routing with cross-docking. Journal of the Operational Research Society 60, 12 (2008), 1708--1718.

[123]

B. Yu and Z. Zhen-Yang. 2011. An ant colony optimization model: The period vehicle routing problem with time windows. Transportation Research Part E: Logistics and Transportation Review 47, 2 (2011), 166--181.

Cited By

Choi EAhn J(2025)Multi-Agent Grouping and Routing with Cooperative TasksJournal of Aerospace Information Systems10.2514/1.I01147822:3(163-176)Online publication date: Mar-2025
https://doi.org/10.2514/1.I011478
Santos RMoraes TEsteve ASilva Júnior OAmorim J(2024)Aplicação de VRP spreadsheet solver otimização de rotas DM distribuidora de bebidas do estado do Rio de JaneiroRevista de Gestão e Secretariado10.7769/gesec.v15i12.459015:12(e4590)Online publication date: 27-Dec-2024
https://doi.org/10.7769/gesec.v15i12.4590
Cook WHeld SHelsgaun K(2024)Constrained Local Search for Last-Mile RoutingTransportation Science10.1287/trsc.2022.118558:1(12-26)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1287/trsc.2022.1185
Show More Cited By

Index Terms

Rich Vehicle Routing Problem: Survey

Recommendations

A general heuristic for vehicle routing problems

We present a unified heuristic which is able to solve five different variants of the vehicle routing problem: the vehicle routing problem with time windows (VRPTW), the capacitated vehicle routing problem (CVRP), the multi-depot vehicle routing problem (...
A tabu search heuristic for the truck and trailer routing problem

Two new construction heuristics and a tabu search heuristic are presented for the truck and trailer routing problem, a variant of the vehicle routing problem. Computational results indicate that the heuristics are competitive to the existing approaches. ...
The open vehicle routing problem: Algorithms, large-scale test problems, and computational results

In the open vehicle routing problem (OVRP), a vehicle does not return to the depot after servicing the last customer on a route. The description of this variant of the standard vehicle routing problem appeared in the literature over 20 years ago, but ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Computing Surveys

ACM Computing Surveys Volume 47, Issue 2

January 2015

827 pages

ISSN:0360-0300

EISSN:1557-7341

DOI:10.1145/2658850

Editor:
Sartaj Sahni
Department of Computer and Information Science and Engineering/University of Florida/Gainesville

Issue’s Table of Contents

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 December 2014

Accepted: 01 August 2014

Revised: 01 August 2014

Received: 01 November 2013

Published in CSUR Volume 47, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Ministerio de Economía y Competitividad

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

223
Total Citations
View Citations
3,738
Total Downloads

Downloads (Last 12 months)270
Downloads (Last 6 weeks)35

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Choi EAhn J(2025)Multi-Agent Grouping and Routing with Cooperative TasksJournal of Aerospace Information Systems10.2514/1.I01147822:3(163-176)Online publication date: Mar-2025
https://doi.org/10.2514/1.I011478
Santos RMoraes TEsteve ASilva Júnior OAmorim J(2024)Aplicação de VRP spreadsheet solver otimização de rotas DM distribuidora de bebidas do estado do Rio de JaneiroRevista de Gestão e Secretariado10.7769/gesec.v15i12.459015:12(e4590)Online publication date: 27-Dec-2024
https://doi.org/10.7769/gesec.v15i12.4590
Cook WHeld SHelsgaun K(2024)Constrained Local Search for Last-Mile RoutingTransportation Science10.1287/trsc.2022.118558:1(12-26)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1287/trsc.2022.1185
Tuma NOstermeier MHübner A(2024)Optimal Transportation Planning for a Do-It-Yourself Retailer with a Zone-Based TariffINFORMS Journal on Applied Analytics10.1287/inte.2023.002054:4(312-328)Online publication date: Jul-2024
https://doi.org/10.1287/inte.2023.0020
Zheng YHao QWang JGao CChen JJin DLi Y(2024)A Survey of Machine Learning for Urban Decision Making: Applications in Planning, Transportation, and HealthcareACM Computing Surveys10.1145/369598657:4(1-41)Online publication date: 22-Nov-2024
https://dl.acm.org/doi/10.1145/3695986
Zhang YLi J(2024)An Improved Harmony Search Algorithm for the VRPTWProceedings of the 2024 10th International Conference on Computing and Artificial Intelligence10.1145/3669754.3669820(425-430)Online publication date: 26-Apr-2024
https://dl.acm.org/doi/10.1145/3669754.3669820
Wen HLin YWu LMao XCai THou YGuo SLiang YJin GZhao YZimmermann RYe JWan H(2024)A Survey on Service Route and Time Prediction in Instant Delivery: Taxonomy, Progress, and ProspectsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.344130936:12(7516-7535)Online publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1109/TKDE.2024.3441309
Saeed RAli EAbdelhaq MAlsaqour RAhmed FSaad A(2024)Energy Efficient Path Planning Scheme for Unmanned Aerial Vehicle Using Hybrid Generic Algorithm-Based Q-Learning OptimizationIEEE Access10.1109/ACCESS.2023.334445512(13400-13417)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2023.3344455
Osaba EVillar-Rodriguez EAsla A(2024)Solving a real-world package delivery routing problem using quantum annealersScientific Reports10.1038/s41598-024-75572-114:1Online publication date: 21-Oct-2024
https://doi.org/10.1038/s41598-024-75572-1
Thakur GPal AMittal NYajid MGared F(2024)A significant exploration on meta-heuristic based approaches for optimization in the waste management route problemsScientific Reports10.1038/s41598-024-64133-114:1Online publication date: 27-Jun-2024
https://doi.org/10.1038/s41598-024-64133-1
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents