Abstract
One of the most significant problems of supply chain management is the distribution of products between locations, most known as the Vehicle Routing Problem (VRP). The vehicle routing problem is one of the most challenging problems in the field of combinatorial optimization. Dantzig and Ramser first introduced the VRP in 1959. They proposed the first mathematical programming formulation. In 1964 Clarke and Wright proposed an effective greedy heuristic that improved Dantzig and Ramser approach. Since then, hundreds of models and algorithms were proposed for the optimal and approximate solution of the different versions of the VRP. In this paper, we present an annotated bibliography of the vehicle routing problem and its variant.
Similar content being viewed by others
References
Alba, E., and Dorronsoro, B., (2004), “Solving the Vehicle Routing Problem by Using Cellular Genetic Algorithms”, Conference on Evolutionary Computation in Combinatorial Optimization, EvoCOP’04, LNCS vol. 3004, pp. 11–20, Portugal, Springer-Verlag.
Alba, E., Dorronsoro, B., (2005), “Computing Nine New Best-So-Far Solutions for Capacitated VRP with a Cellular Genetic Algorithm”, Information Processing Letters, In press.
Alba, E., and Dorronsoro, B., (2006), “Computing Nine New Best-So-Far Solutions for Capacitated VRP with a Cellular Genetic Algorithm”, Information Processing Letters, Vol. 98 (6), pp. 225–230.
Altinkemer, K., and Gavish, B., (1991), “Parallel Savings Based Heuristics for the Delivery Problem”, Operations Research, vol. 39 (3), pp. 456–469.
Alvarenga, G.B., Mateus, G.R., and de Tomi, G., (2007), “A Genetic and Set Partitioning Two-Phase Approach for the Vehicle Routing Problem with Time Windows” Computers & Operations Research, Vol. 34 (6), pp. 1561–1584.
Arbelaitz, O., Rodriguez, C., and Zamakola, I. (2001), “Low Cost Parallel Solutions for the VRPTW Optimization Problem”, 2001 International Conference on Parallel Processing Workshops. IEEE Computer Society. Valencia, Spain. pp. 176–181.
Assad, A.A., (1988), “Modeling and Implementation Issues in Vehicle Routing” B.L. Golden, A.A. Assad (Eds.), Vehicle Routing: Methods and Studies, North Holland, Amsterdam, pp. 7–46.
Badeau, P., Guertin F., Gendreau M., Potvin, J.-Y., and Taillard, E., (1997), “A Parallel Tabu Search Heuristic for the Vehicle Routing Problem with Time Windows”, Transportation Research Part C: Emerging Technology, Vol. 5 (2), pp. 109–122.
Baker, E., and Schaffer, J., (1986), “Solution Improvement heuristics for the vehicle routing and scheduling problem with time windows constraints”, American Journal of Mathematics and Management Science, Vol. 6, pp. 261–300.
Baker, B.M., and Ayechew, M.A., (2003), “A Genetic Algorithm for the Vehicle Routing Problem”, Computers and Operations Research, Vol. 30 (5), pp. 787–800.
Baptista, S., Oliveira, R.C., and Zúquete, E., (2002), “A Period Vehicle Routing Case Study”, European Journal of Operational Research, Vol. 139, pp. 220–229, Elsevier.
Barbarosoglu, G., and Ozgur, D., (1999), “A Tabu Search Algorithm for the Vehicle Routing Problem”, Computers & Operations Research, Vol. 26 (3), pp. 255–270.
Beasley, J., (1983), “Route First — Cluster Second Methods for Vehicle Routing”, Omega Vol. 11, pp. 403–408.
Beltrami, E., and Bodin, L., (1974), “Networks and Vehicle Routing for Municipal Waste Collection”, Networks Vol. 4, pp. 65–94.
Berger, J., and Mohamed B., (2003), “A Hybrid Genetic Algorithm for the Capacitated Vehicle Routing Problem”. In: Proceedings of the Genetic and Evolutionary Computation Conference, Chicago, pp. 646–656.
Bianchessi, N., and Righini, G., (2007), “Heuristic Algorithms for the Vehicle Routing Problem with Simultaneous Pick-Up and Delivery”, Computers & Operations Research, Vol. 34 (2), pp 578–594.
Bodin, L., and Golden, B., (1981), “Classification in Vehicle Routing and Scheduling”, Networks Vol. 11, pp. 97–108.
Bodin, L., Golden, B., Assad, A.A., and Ball, M., (1983), “The State of the Art in the Routing and Scheduling of Vehicles and Crews”, Computers and Operation Research, Vol. 10, pp. 63–212.
Braca, J., Bramel, J., Posner, B., and Simchi Levi, D., (1994), “A Computerized Approach to the New York City School Bus Routing Problem”, Technical Report, Columbia University.
Bramel, J., Li, C.L., and Simchi-Levi, D., (1993), “Probabilistic analysis of a vehicle routing problem with time windows”, American Journal of Mathematics and Management Science, Vol. 13, pp. 267–322.
Bramel, J., and Simchi-Levi, D., (2002), “Set — Covering — Based Algorithms for the Capacitated VRP”. P. Toth, D. Vigo. The Vehicle Routing Problem, Monographs on Discrete Mathematics and Applications 9, pp. 85–108, Siam.
Brandao, J., (1998), “Metaheuristic for the Vehicle Routing Problem with Time Windows”, Metaheuristics: Advances and Trends in Local Search Paradigms for Optimization, Editors Voss, S., Martello, S., Osman, I. H., and Roucairol, C., Kluwer Academic Publishers, Boston, pp. 19–36.
Brandao, J., (2004), “A Tabu Search Algorithm for the Open Vehicle Routing Problem”, European Journal of Operational Research, Vol. 157 (3), pp. 552–564.
Brandao J., (2006), “A New Tabu Search Algorithm for the Vehicle Routing Problem with Backhauls”, European Journal of Operational Research, Vol. 173 (2), pp. 540–555.
Bräysy, O., and Gendreau, M., (2001), “Tabu Search Heuristics for the Vehicle Routing Problem with Time Windows”. Internal Report STF42 A01022, SINTEF Applied Mathematics, Department of Optimisation, Oslo, Norway.
Breedam, A.V., (2001), “Comparing Descent Heuristics and Metaheuristics for the Vehicle Routing Problem”, Computers & Operations Research, Vol. 28 (4), 289–315.
Breedam, A.V., (2002), “A Parametric Analysis of Heuristics for the Vehicle Routing Problem with Side-Constraints”, European Journal of Operational Research, Vol. 137 (2), pp. 348–370.
Bullnheimer, B., Hartl, R.F., and Strauss, C., (1997), “Applying the Ant System to the Vehicle Routing Problem”. Paper presented at 2nd International Conference on Metaheuristics, Sophia-Antipolis, France.
Bullnheimer B., Hartl P.F., and Strauss, C., (1999) “An Improved Ant System Algorithm for the Vehicle Routing Problem”. Annals Operations Research, Vol. 89, pp. 319–328.
Caretto, C., and Baker, B., (2002), “A GRASP Interactive Approach to the Vehicle Routing Problem with Backhauls”, Essays and Surveys on Metaheuristics, Editors Ribeiro, C. C., and Hansen, P., Kluwer Academic Publishers, Norwell, pp. 185–199.
Casco, D.O., Golden, B.L., and Wasil, E.A., (1988), “Vehicle Routing with Backhauls: Models, Algorithms, and Case Studies”. B.L. Golden, A.A. Assad (eds.) Vehicle Routing: Methods and Studies, pp. 127–147, North Holland, Amsterdam.
Chao, I.M., (2002), “A Tabu Search Method for the Truck and Trailer Routing Problem”, Computers and Operations Research, Vol. 29, pp. 33–51.
Chao, I.M., Golden, B.L., and Wasil, E., (1993), “A New Heuristic for the Multi-Depot Vehicle Routing Problem that Improves upon Best-Known Solutions”, American Journal of Mathematics and Management Science, Vol. 13 (3–4), pp. 371–406.
Chaovalitwongse, W., Kim, D., and Pardalos, P.M., (2003), “GRASP with a New Local Search Scheme for Vehicle Routing Problems with Time Windows”, Journal of Combinatorial Optimization, Vol. 7, pp. 179–207.
Chiang, W.C., and Russell, R.A. (1996), “Simulated Annealing Metaheuristics for the Vehicle Routing Problem with Time Windows”, Metaheuristics in Combinatorial Optimization. Annals of Operations Research, Vol. 63, pp. 3–27.
Chiang, W.C., and Russell, R.A., (2004), “Integrating Purchasing and Routing in a Propane Gas Supply Chain”, European Journal of Operational Research, Vol. 154, pp. 710–729.
Chitty, D.M., and Hernandez, M.L., (2004), “A Hybrid Ant Colony Optimisation Technique for Dynamic Vehicle Routing”, K. Deb et al. (Eds.): GECCO 2004, LNCS 3102, Springer-Verlag, pp. 48–59.
Choi, E., and Tcha, D., (2007), “A Column Generation Approach to the Heterogeneous Fleet Vehicle Routing Problem”, Computers & Operations Research, Vol. 34 (7), pp. 2080–2095.
Christofides, N., Mignozzi, A., and Toth, P., (1979), “The Vehicle Routing Problem”, N. Christofides, A. Mignozzi, P. Toth, C. Sandi (Eds.), Combinatorial Optimization, Ch. 11, Wiley, Chichester.
Christofides N., Mignozzi, A. and Toth, P., (1981), “Exact Algorithms for the Vehicle Routing Problem Based on Spanning Tree and Shortest Path Relaxation”, Mathematical Programming, Vol. 19, pp. 255–282.
Christofides, N., (1985), “Vehicle Routing”, E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, D.B. Shmoys (Eds.), The Traveling Salesman Problem, Ch. 12, pp. 431–448, Wiley, Chichester.
Christofides, N., and Beasley, J., (1984), “Multiperiod Rrouting Problems”, Networks, Vol. 14, pp. 237–256.
Clarke, G., and Wright, J., (1964), “Scheduling of Vehicles from a Central Depot to a Number of Delivery Points, Operations Research, Vol. 12, pp. 568–581.
Cordeau, J.-F., Laporte, G., and Mercier, A., (2001), “A Unified Tabu Search Heuristic for Vehicle Routing Problems with Time Windows”, Journal of the Operational Research Society, Vol. 52, pp. 928–936.
Cordeau, J.F., Gendreau, M., and Laporte, G., (1997), A Tabu Search Heuristic for the Periodic and Multi-Depot Vehicle Routing Problem. Networks, Vol. 30, pp. 105–119.
Cordeau, J.F., Deasulniers, G., Desrosiers, J., Solomon, M.M., and Soumis, F., (2002), “VRP with Time Windows”, P. Toth, D. Vigo (Eds.), The Vehicle Routing Problem, Monographs on Discrete Mathematics and Applications 9, pp. 157–193, Siam.
Cordeau, J.F., Gendreau, M., Laporte, G., Potvin, J.Y., and Semet, F., (2002), “A Guide to Vehicle Routing Heuristics”, Journal of the Operational Research Society, Vol. 53, pp. 512–522.
Cordeau, J.F., Gendreau, M., Hertz, A., Laporte, G., and Sormany, J.S., (2005), “New Heuristics for the Vehicle Routing Problem”, In A. Langevine and D. Riopel, (Eds.), Logistics Systems: Design and Optimization, Wiley and Sons, pp. 279–298.
Cordone, R., and Calvo, R.W., (2001), “A Heuristic for the Vehicle Routing Problem with Time Windows”, Journal of Heuristics, Vol. 7 (2), pp. 107–129.
Crainic, T.G., and Laporte, G. (Eds.), (1998), “Fleet Management and Logistics”, Kluwer Academic Publishers.
Crevier, B., Cordeau, J.F., and Laporte, G., (2007), “The Multi-Depot Vehicle Routing Problem with Inter-Depot Routes”, European Journal of Operational Research, Vol. 176 (2), pp. 756–773.
Cullen, F., Jarvis, J., and Ratliff, D., (1981), “Set Partitioning — Based Heuristics for Interactive Ruting”, Networks, Vol. 11, pp. 125–144.
Coy, S.P., Golden, B.L., Runger, G.C. and Wasil, E.A., (2001), “Using Experimental Design to Effective Parameter Settings for Heuristics”, Journal of Heuristics, Vol. 7 (1), pp. 77–97.
Czech, Z.J., and Czarnas, P., (2002), “Parallel Simulated Annealing for the Vehicle Routing Problem with Time Windows”, 10th Euromicro Workshop on Parallel, Distributed and Network-based Processing, Canary Islands — Spain, January 9–11, pp. 376–383.
Dantzig, G.B., and Ramser, R.H., (1959), “The Truck Dispatching Problem”. Management Science, Vo. 6, pp. 80–91.
Deif, I., and Bodin, L., (1984), “Extension of the Clarke and Wright Algorithm for Solving the Vehicle Routing Problem with Backhauling”, Proceedings of the Babson Colledge Conference on Software Uses in Transportation and Logistics Management, Editor Kidder, A., Babson Park, MA, pp. 75–96.
Desaulniers, G., Desrosiers, J., Erdmann, A., Solomon, M.M., and Soumis, F., (2002), “VRP with Pickup and Delivery”, P. Toth, D. Vigo (Eds.), The Vehicle Routing Problem, Monographs on Discrete Mathematics and Applications 9, pp. 225–242, Siam.
Desrochers, M., and Verhoog, T.W. (1989), “A Matching Based Savings Algorithm for the Vehicle Routing Problem”, Les Cahiers du GERAD G-89-04, Ecole des Hautes Etudes Commerciales de Montreal.
Desrochers, M., Desrosiers, J., and Solomon, M.M., (1992), “A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows”, Operation Research, Vol. 40, pp. 342–354.
Desrochers, M., Lenstra, J.K., and Savelsbergh, M.W.P., (1990), “A Classification Scheme for Vehicle Routing and Scheduling Problems”, European Journal of Operational Research, Vol. 46, pp. 322–332.
Desrochers, M., Lenstra, J.K., Sawelsberg, M.W., and Soumis, F., (1988), “Vehicle Routing with Time Windows: Optimization and Approximation”, B.L. Golden, A.A. Assad (Eds.), Vehicle Routing: Methods and Studies, pp. 65–84, North Holland, Amsterdam.
Desrosiers, J., Dumas, Y., and Soumis, F., (1986), “A Dynamic Programming Solution of the Large Scale Single Vehicle Dial - A — Ride problem with Time Windows”, American Journal of Mathematics and Management Science, Vol. 6, pp. 301–325.
Desrosiers, J., Dumas, Y., Solomon, M.M., and Soumis, F., (1995), “Time Constraints Routing and Scheduling”, M.O. Ball, T.L. Magnanti, C.L. Momma, G.L. Nemhauser (Eds.), Network Routing, Handbooks in Operations Research and Management Science 8, pp. 35–139, North Holland, Amsterdam.
Doerner, K., Gronalt, M., Hartl, R., Reimman, M., Strauss, C., and Stummer, M., (2002), “SavingsAnts for the Vehicle Routing Problem”, In Cagnoni, S., (Ed.), EvoWorkshops02, LNCS 2279, Springer-Verlag, pp. 11–20.
Dondo, R., and Cerdá, J., (2007), “A Cluster-Based Optimization Approach for the Multi-Depot Heterogeneous Fleet Vehicle Routing Problem with Time Windows”, European Journal of Operational Research, Vol. 176 (3), pp. 1478–1507.
Drummond, L.M.A., Ochi, L.S., and Vianna, D.S., (2001), “An Asynchronous Parallel Metaheuristic for the Period Vehicle Routing Problem”, Future Generation Computer Systems, Vol. 17, pp. 379–386.
Dueck, G., (1993), “New Optimization Heuristics: The Great Deluge Algorithm and the Record-To-Record Travel”, Journal of Computational Physics, Vol. 104, pp. 86–92.
Dueck, G., and Scheurer, T., (1990), “Threshold Accepting: A General Purpose Optimization Algorithm”, Journal of Computational Physics, Vol. 90, pp. 161–175.
Eilon, S., Watson-Gandy, C., and Christofides, N., (1971), “Distribution Management”, Griffin, London.
Fisher, M.L., (1994), “Optimal Solution of Vehicle Routing Problems Using Minimum k — Trees”, Operations Research, Vol. 42, pp. 626–642.
Fisher, M.L., (1995), “Vehicle Routing”, M.O. Ball, T.L. Magnanti, C.L. Momma, G.L. Nemhauser (Eds.), Network Routing, Handbooks in Operations Research and Management Science 8, pp. 1–33, North Holland, Amsterdam.
Fisher, M., and Jaikumar, R. (1981), “A Generalized Assignment Heuristic for Vehicle Routing”, Networks, Vol. 11, pp. 109–124.
Foster, B.A., and Ryan, D.M., (1976), “An Integer Programming Approach to the Vehicle Scheduling Problem”, Operations Research, Vol. 27, pp. 367–384.
Francis, P., and Smilowitz, K., (2006), “Modeling Techniques for Periodic Vehicle Routing Problems Transportation Research Part B: Methodological”, Vol. 40 (10), pp. 872–884.
Gambardella, L.M., Taillard, E., and Agazzi, G., (1999), “MACS-VRPTW: A Multiple Ant Colony System for Vehicle Routing Problems with Time Windows”, In D. Corne, M. Dorigo and F. Glover, (Eds.), New Ideas in Optimization. McGraw-Hill.
Gaskell, T., (1967), “Bases for Vehicle Fleet Scheduling”, Operations Research Quarterly, Vol. 18, pp. 281–287.
Gendreau, M., Hertz, A., and Laporte, G., (1994), “A Tabu Search Heuristic for the Vehicle Routing Problem”, Management Science, Vol. 40, pp. 1276–1290.
Gendreau, M., Laporte, G., and Potvin, J-Y., (1997), “Vehicle Routing: Modern Heuristics”, E.H.L. Aarts, J.K. Lenstra (Eds.), Local Search in Combinatorial Optimization, pp. 311–336, Wiley, Chichester.
Gendreau, M., Laporte, G., Musaraganyi, C., and Taillard, E.D., (1999), “A Tabu Search Heuristic for the Heterogeneous Fleet Vehicle Routing Problem”, Computers & Operations Research, Vol. 26 (12), pp. 1153–1173.
Gendreau, M., Laporte, G., and Potvin, J.Y., (2002), “Metaheuristics for the VRP”, P. Toth, D. Vigo (Eds.), The Vehicle Routing Problem, Monographs on Discrete Mathematics and Applications 9, pp. 129–154, Siam.
Gendreau, M., Laporte, G., and Séguin, R., (1996), “Stochastic Vehicle Routing”, European Journal of Operational Research, Vol. 88 (1), pp. 3–12.
Gillet, B., and Miller, L. (1974), “A Heuristic Algorithm for the Vehicle — Dispatch Problem”, Operations Research, Vol. 22, pp. 340 -349.
Gillet, B., and Johnson, J. (1976), “Multiterminal Vehicle Dispatch Algorithm”, Omega, Vol. 4, pp. 711–718.
Goetschalckx, M., and Jacobs-Blecha, C., (1989), “The Vehicle Routing with Backhauls”, European Journal of Operational Research, Vol. 42, pp. 39–51.
Golden, B.L., and Assad, A.A., (1986), “Vehicle Routing with Time Windows Constraints”, American Journal of Mathematics and Management Science, Vol. 6, pp. 251–260.
Golden, B.L., and Assad, A.A., (Eds.) (1988), “Vehicle Routing: Methods and Studies”, North Holland, Amsterdam.
Golden, B.L., Wassil, E., Kelly, J., and Chao, I.M., (1998), “The Impact of Metaheuristics on Solving the Vehicle Routing Problem: Algorithms, Problem Sets, and Computational Results”, T.G. Crainic, G. Laporte (Eds.), Fleet Management and Logistics, pp. 33–56, Kluwer, Academic Publishers.
Gribkovskaia, I., Halskau, O., Laporte, G., and Vlček, M., (2006), “General Solutions to the Single Vehicle Routing Problem with Pickups and Deliveries”, European Journal of Operational Research, In Press, Corrected Proof, Available online 7 July 2006.
Haimovich, M., Rinnoy Kan, A.H.G., Stougie, L., (1988), “Analysis of Heuristic for Vehicle Routing Problems”, B.L. Golden and A.A. Assad (Eds.), Vehicle Routing: Methods and Studies, pp. 47–61, North-Holland, Amsterdam.
Haugland, D., Ho, S.C., and Laporte, G., (2006), “Designing Delivery Districts for the Vehicle Rrouting Problem with Sochastic Demands”, European Journal of Operational Research, In Press, Corrected Proof, Available online 30 June 2006.
Haughton, M., and Stenger, A., (1997), “Semi-Variable Delivery Routes and the Efficiency of Outbound Logistics”, International Journal of Physical Distribution and Logistics Management, Vol. 27, pp. 459–474.
Hirota, K., Dong, F., Chen, K., and Takama, Y., (2002), “Vehicle Routing, Scheduling and Dispatching System Based on HIMS Model”, N.R. Pal and M. Sugeno (Eds.), AFSS 2002, LNAI 2275, Springer-Verlag, pp. 76–84.
Hjorring, C., (1995), “The Vehicle Routing Problem and Local Search Metaheuristics”, Ph.D. thesis, Department of Engineering Science, The University of Auckland.
Hornberger, J., and Gehring, H., (1999), “Two Evolutionary Metaheuristics for the Vehicle Routing Problems with Time Windows”, INFOR, Vol. 37, pp. 297–318.
Hsu, C.I., Hung, S.F., and Li, H.C., (2007), “Vehicle Routing Problem with Time-Windows for Perishable Food Delivery”, Journal of Food Engineering, Vol. 80 (2), pp. 465–475.
Hwang, H-S., (2002), “An Improved Model for Vehicle Routing Problem with Time Constraint Based on Genetic Algorithm”, Computers and Industrial Engineering, pp. 1–9.
Irnich, S., Funke, B., and Grünert, T., (2006), “Sequential Search and its Application to Vehicle-Routing Problems”, Computers & Operations Research, Vol. 33 (8), pp. 2405–2429.
Jaillet, P., and Odoni, A.R., (1988), “The Probabilistic Vehicle Routing Problem”, B.L. Golden, A.A. Assad (Eds.), Vehicle Routing: Methods and Studies, pp. 293–318, North Holland, Amsterdam.
Jaszkiewicz, A., and Kominek, P., (2003), “Genetic Local Search with Distance Preserving Recombination Operator for a Vehicle Routing Problem”, European Journal of Operational Research, Vol. 151, pp. 352–364.
Katoh, N., and Yano, T., (2006), “An Approximation Algorithm for the Pickup and Delivery Vehicle Routing Problem on Trees”, Discrete Applied Mathematics, Vol 154 (16), pp. 2335–2349.
Kilby, P., Prosser, P., and Shaw, P., (1999), “Guided Local Search for the Vehicle Routing Problem with Time Windows”, Voss, S., Martello, S., Osman, I. H., and Roucairol, C., (Eds.), Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, Kluwer Academic Publishers, Boston, pp. 473–486.
Kontoravdis, G., and Bard, J.F., (1995), “A GRASP for the Vehicle Routing Problem with Time Windows”, ORSA Journal on Computing, Vol. 7, pp. 10–23.
Kytöjoki, J., Nuortio, T., Bräysy, O. and Gendreau, M., (2005), “An Efficient Variable Neighborhood Search Heuristic for Very Large Scale Vehicle Routing Problems”, Computers & Operations Research, In Press, Corrected Proof.
Laporte, G., (1992), “The Vehicle Routing Problem: An Overview of Exact and Approximate Algorithms”, European Journal of Operational Research, Vol. 59, pp. 345–358.
Laporte, G., (1997), “Vehicle Routing”, M.D. Amico, F. Maffioli, S. Martello (Eds.), Annotated Bibliographies in Combinatorial Optimization, pp. 223–240, Wiley, Chichester.
Laporte, G., and Louveaux, F., (1998), “Solving Stochastic Routing Problems with the Integer L — Shaped Method”. T.G. Crainic, G. Laporte (Eds.), Fleet Management and Logistics, pp. 159–167, Kluwer, Academic Publishers.
Laporte, G., and Nobert, Y., (1987), “Exact Algorithms for the Vehicle Routing Problem”, S. Martello, G. Laporte, M. Minoux, C. Ribeiro (Eds), Surveys in Combinatorial Optimization, Annals of Discrete Mathematics 31, pp. 147–184, North-Holland, Amsterdam.
Laporte G., and Osman I.H., (1995), “Routing Problems: A bibliography”. Annals of Operations Research, Vol. 61, pp, 227–262.
Laporte, G., and Semet, F., (2002), “Classical Heuristics for the Capacitated VRP”, P. Toth, D. Vigo. (Eds.) The Vehicle Routing Problem, Monographs on Discrete Mathematics and Applications 9, pp. 109–128, Siam.
Laporte, G., Nobert, Y., and Desrochers, M., (1985), “Optimal Routing Under Capacity and Distance Restrictions”, Operations Research Vol. 33, pp. 1050–1073.
Laporte, G., Gendreau, M., Potvin, J.-Y., and Semet, F., (2000), “Classical and Modern Heuristics for the Vehicle Routing Problem”, International Transactions in Operational Research, Vol. 7 (4–5), pp. 285–300.
Lenstra, J. K., and Rinnoy Kan, A.H.G., (1981), “Complexity of Vehicle Routing and Scheduling Problems”. Networks Vol. 11, pp. 221 -227.
Li, F., Golden, B., and Wasil, E., (2005), “Very Large-Scale Vehicle Routing: New Test Problems, Algorithms and Results”, Computers and Operations Research, Vol. 32 (5), pp. 1165–1179.
Li, F., Golden, B. and Wasil, E., (2006a), “The Open Vehicle Routing Problem: Algorithms, Large-Scale Test Problems, and Computational Results”, Computers & Operations Research, In Press, Corrected Proof.
Li, F., Golden, B. and Wasil, E., (2006b). “A Record-To-Record Travel Algorithm for Solving the Heterogeneous Fleet Vehicle Routing Problem”, Computers & Operations Research, In Press, Corrected Proof.
Li, H., and Lim, A., (2003), “Local Search with Annealing-Like Restarts to Solve the VRPTW”, European Journal of Operational Research, Vol. 150, pp. 115–127.
Li, Z., Guo, S., Wang, F., and Lim, A., (2004), “Improved GRASP with Tabu Search for Vehicle Routing with Both Time Window and Limited Number of Vehicles”, R. Orchard et al. (Eds.), IEA/AIE 2004, LNAI 3029, Springer-Verlag, pp. 552–561.
Lim, A., and Wang, F., (2004), “A Smoothed Dynamic Tabu Search Embedded GRASP for m-VRPTW”, In Proceedings of the 16th IEEE International Conference on Tools with Artificial Intelligence (ICTAI 2004).
Liu, F.H.F., and Shen, S.Y., (1999), “A Route-Neighborhood-Based Metaheuristic for Vehicle Routing Problem with Time Windows”, European Journal of Operational Research, Vol. 118, pp. 485–504.
Lysgaard, J., Letchford, A.N., and Eglese, R.W., (2004), “A New Branch-and-Cut Algorithm for Capacitated Vehicle Routing Problems”, Mathematical Programming, Ser. A, Vol. 100, pp. 423–445.
Magnanti, T., (1981), “Combinatorial Optimization and Vehicle Fleet Planning: Perspectives and Prospects”, Networks, Vol. 11, pp. 179–213.
Marinakis, Y., and Migdalas, A., (2002), “Heuristic Solutions of Vehicle Routing Problems in Supply Chain Management”, Combinatorial and Global Optimization, P.M. Pardalos et al. (Eds.), Scientific World, pp. 205–235.
Marinakis, Y., Migdalas, A. and Pardalos, P.M., (2006a), “A New Bilevel Formulation for the Vehicle Routing Problem and a Solution Method Using a Genetic Algorithm”, Journal of Global Optimization, (in print-Available on line).
Marinakis, Y., Migdalas, A. and Pardalos, P.M., (2006b), “Multiple Phase Neighborhood Search GRASP for the Vehicle Routing Problem”, (submitted in Computational Management Science).
Marinakis, Y., Marinaki, M., and Migdalas, A., (2006c), “A Hybrid Genetic — GRASP — ENS Algorithm for the Vehicle Routing Problem”, (submitted in Asia Pacific Journal of Operational Research).
Marinakis, Y., and Marinaki, M., (2006), “Expanding Neighborhood Search for the Vehicle Routing Problem”, (submitted in OR Spectrum).
Matsatsinis, N.F., (2004) “Towards a Decision Support System for the Ready Concrete Distribution System: A Case of a Greek Company”, European Journal of Operational Research, Vol. 152, pp. 487–499.
Mazzeo, S., and Loiseau, I., (2004), “An Ant Colony Algorithm for the Capacitated Vehicle Routing”, Electronic Notes in Discrete Mathematics, Vol. 18, pp. 181–186.
Mester, D., and Braysy, O., (2004), “Active Guided Evolution Strategies for the Large Scale Vehicle Routing Problems with Time Windows”, Computers and Operations Research, Vol. 63, pp. 1593–1614.
Mester, D., and Braysy, O., (2005), “Active-Guided Evolution Strategies for Large-Scale Capacitated Vehicle Routing Problems”, Computers & Operations Research, In Press, Corrected Proof.
Mester, D., Bräysy, O. and Dullaert, W., (2007), “A Multi-Parametric Evolution Strategies Algorithm for Vehicle Routing Problems”, Expert Systems with Applications, Vol. 32 (2), pp. 508–517.
Modares, A., Somhom, S., and Enkawa, T., (1999), “A Self-Organizing Neural Network Approach for Multiple Traveling Salesman and Vehicle Routing Problems”, International Transactions in Operational Research, Vol. 6 (6), pp. 591–606.
Mole, R., and Jameson, S., (1976), “A Sequential Route-Building Algorithm Employing A Generalized Savings Criterion”, Operation Research Quarterly, Vol. 27, pp. 503–511.
Mosheiov, G., (1998), “Vehicle Routing with Pick-Up and Delivery: Tour-Partitioning Heuristics”, Computers & Industrial Engineering, Vol. 34 (3), pp. 669–684.
Mourgaya, M., and Vanderbeck, F., (2006), “Column Generation Based Heuristic for Tactical Planning in Multi-Period Vehicle Routing”, European Journal of Operational Research, In Press, Corrected Proof.
Naddef, D., and Rinaldi, G., (2002), “Branch and cut Algorithms for the Capacitated VRP”, P. Toth, D. Vigo, (Eds.), The Vehicle Routing Problem, Monographs on Discrete Mathematics and Applications 9, pp. 52–84.
Nag, B., Golden, B.L., and Assad, A.A., (1988), “Vehicle Routing with Site Dependencies”, Golden, B.L., and Assad, A.A., (Eds.), Vehicle Routing: Methods and Studies, North Holland, Amsterdam, pp. 149–159.
Nanry, W.P., and Barnes, J.W., (2000), “Solving the Pickup and Delivery Problem with Time Windows Using Reactive Tabu Search”, Transportation Research Part B: Methodological, Vol. 34 (2), pp. 107–121.
Ochi, L.S., Vianna, D.S., Drummond, L.M.A., and Victor, A.O., (1998), “A Parallel Evolutionary Algorithm for the Vehicle Routing Problem with Heterogeneous Fleet”, Future Generation Computer Systems, Vol. 14 (5–6), pp. 285–292.
Osman, I.H., (1993), “Metastrategy Simulated Annealing And Tabu Search Algorithms For The Vehicle Routing Problem”, F. Glover, M. Laguna, E. Taillard, D. de Werra (Eds.), Tabu Search, Annals of Operation Research 41, pp. 421–451, Baltzer, Amsterdam.
Ozdamar, L., Ekinci, E., and Küçükyazici, B. (2004), “Emergency Logistics Planning in Natural Disasters”, Annals of Operations Research, Vol. 129, pp. 217–245, Kluwer Academic Publishers.
Potvin, J.Y., and Bengoi, S., (1996), “The Vehicle Routing Problem with Time Windows — Part II: Genetic Search”, INFORMS Journal on Computing, Vol. 8, pp. 165–172.
Potvin, J.Y., and Rousseau, J.M., (1993), “A Parallel Route Building Algorithm for the Vehicle Routing and Scheduling Problem with Time Window Constraints”, European Journal of Operational Research, Vol. 66, pp. 331–340.
Potvin, J.Y., and Robillard, C., (1995), “Clustering for Vehicle Routing with a Competitive Neural Network”. Neurocomputing, Vol. 8, pp. 125–139.
Potvin, J.Y., Kervahut, T., Garcia, B.L., and Rousseau, J.M., (1996), “The Vehicle Routing Problem with Time Windows — Part I: Tabu Search”, INFORMS Journal on Computing, Vol. 8, pp. 158–164.
Powell, W.B., (1988), “A Comparative Review of Alternative Algorithms for the Dynamic Vehicle Allocation Problem”. B.L. Golden, A.A. Assad (Eds.) Vehicle Routing: Methods and Studies, pp. 249–291, North Holland, Amsterdam.
Powel, W.B., Jaillet, P., and Odoni, A.R., (1995), “Stochastic and Dynamic Network and Routing”, M.O. Ball, T.L. Magnanti, C.L. Momma, G.L. Nemhauser (Eds.), Network Routing, Handbooks in Operations Research and Management Science 8, pp. 141–295, North Holland, Amsterdam.
Prins, C., (2002), “Efficient Heuristics for the Heterogeneous Fleet Multitrip VRP with Application to a Large-Scale Real Case”, Journal of Mathematical Modelling and Algorithms, Vol. 1, pp. 135–150, Kluwer Academic Publishers.
Prins, C., (2004), “A Simple And Effective Evolutionary Algorithm for the Vehicle Routing Problem”. Computers and Operations Research, Vol. 31, pp. 1985–2002.
Psaraftis, H.N., (1988), “Dynamic Vehicle Routing Problems”, B.L. Golden, A.A. Assad (Eds.) Vehicle Routing: Methods and Studies, pp. 223–248, North Holland, Amsterdam.
Rego, C., (1998), “A Subpath Ejection Method for the Vehicle Routing Problem”, Management Science, Vol. 44, pp. 1447–1459.
Rego, C., (2001), “Node-Ejection Chains for the Vehicle Routing Problem: Sequential and Parallel Algorithms”, Parallel Computing, Vol. 27 (3), pp. 201–222.
Rego, C., and Roucairol, C., (1996), “A Parallel Tabu Search Algorithm Using Ejection Chains for the Vehicle Routing Problem”, I.H. Osman, J.P. Kelly (Eds.), Metaheuristics: theory and Applications, pp. 661–675, Kluwers, Boston.
Reimann, M., Stummer, M., and Doerner, K., (2002), “A Savings Based Ant System for the Vehicle Routing Problem”. In: Proceedings of the Genetic and Evolutionary Computation Conference, New York, pp. 1317–1326.
Reimann, M., Doerner, K., and Hartl, R.F., (2003), “Analyzing a Unified Ant System for the VRP and Some of Its Variants”. S. Cagnoni et al. (Eds.), EvoWorkshops 2003, LNCS 2611, pp. 300–310, Springer-Verlag Berlin Heidelberg.
Reimann, M., Doerner, K., and Haiti, R.F., (2004), “D-Ants: Savings Based Ants Divide And Conquer The Vehicle Routing Problem”. Computers and Operations Research, Vol. 31 (4), pp. 563–591.
Renaud, J., Laporte, G., and Boctor, F.F., (1996), “A Tabu Search Heuristic for the Multi-Depot Vehicle Routing Problem”, Computers & Operations Research, Vol. 23 (3), pp. 229–235.
Renaud, J. and Boctor, F.F, (2002), “A Sweep-Based Algorithm for the Fleet Size and Mix Vehicle Routing Problem”, European Journal of Operational Research Vol. 140, pp. 618–628.
Rochat, Y., and Taillard, E.D., (1995), “Probabilistic Diversification and Intensification in Local Search for Vehicle Routing”, Journal of Heuristics, Vol. 1, pp. 147–167.
Ropke, S., and Pisinger, D., (2006), “A Unified Heuristic for a Large Class of Vehicle Routing Problems with Backhauls”, European Journal of Operational Research, Vol. 171 (3), pp. 750–775.
Rousseau, L.M., Gendreau, M., Pesant, G., and Focacci, F., (2004), “Solving VRPTWs with Constraint Programming Based Column Generation”, Annals of Operation Research Vol. 130, pp. 199–216, Kluwer Academic Publishers.
Ruland, K.S., and Rodin, E.Y., (1997). “The Pickup and Delivery Problem: Faces and Branch-and-Cut Algorithm”, Computers Mathematical Applications, Vol. 33 (12), pp. 1–13.
Ruiz, R., Maroto, C., and Alcaraz, J., (2004), “A Decision Support System for a Real Vehicle Routing Problem”, European Journal of Operational Research, Vol. 153, pp. 593–606.
Russell, R., (1995), “Hybrid Heuristics for the Vehicle Routing Problem with Time Windows”, Transportation Science, Vol. 29, pp. 156–166.
Russell, R.A., and Chiang, W.C., (2006), “Scatter Search For The Vehicle Routing Problem With Time Windows”, European Journal of Operational Research, Vol. 169 (2), pp 606–622.
Salhi, S., and Sari, M., (1997), “A Multi-Level Composite Heuristic For The Multi-Depot Vehicle Fleet Mix Problem”, European Journal of Operational Research, Vol. 103(1), pp. 95–112.
Sambracos, E., Paravantis, J.A., Tarantilis, C.D., and Kiranoudis, C.T., (2004), “Dispatching of Small Containers via Coastal Freight Liners: The Case of the Aegean Sea”, European Journal of Operational Research, Vol. 152, pp. 365–381.
Secomandi, N., (2000), “Comparing Neuro-Dynamic Programming Algorithms for the Vehicle Routing Problem with Stochastic Demands”, Computers and Operations Research, Vol. 27, pp. 1201–1225.
Semet, F., and Taillard, E., (1993). “Solving Real Life Vehicle Routing Problems Efficiently Using Tabu Search”, Annals of Operational Research, Vol. 41, pp. 469–488.
Solomon, M.M., (1987), “Algorithms for the Vehicle Routing and Scheduling Problem with Time Windows Constraints”, Operation Research, Vol. 35, pp. 254–265.
Solomon, M.M., Baker, E., and Schaffer, J., (1988). “Vehicle Routing and Scheduling Problem with Time Windows Constraints”, B.L. Golden, A.A. Assad (Eds.), Vehicle Routing: Methods and Studies, pp. 85–105, North Holland, Amsterdam.
Stewart, W.R., and Golden, B.L., (1984), “A Lagrangean Relaxation Heuristic for the Vehicle Routing”, European Journal of Operational Research, Vol. 15, pp. 84–88.
Swihart, M.R., and Papastavrou, J.D., (1999), “A Stochastic and Dynamic Model for the Single-Vehicle Pick-Up and Delivery Problem”, European Journal of Operational Research, Vol. 114 (3), pp. 447–464.
Taillard, E.D., (1993), “Parallel Iterative Search Methods for Vehicle Routing Problems”, Network Vol. 23, pp. 661–676.
Taillard, E.D., Badeau, P., Gendreau, M., Guertin, F., and Potvin, J.Y., (1997), “A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows”, Transportation science, Vol. 31, pp. 170–186.
Taillard, E.D., Gambardella, L.M., Gendreau, M., and Potvin, J.Y., (2001), “Adaptive Memory Programming: A Unified View of Metaheuristics”, European Journal of Operational Research, Vol. 135 (1), pp. 1–16.
Tan, K.C., Cheong, C.Y., and Goh, C.K., (2007), “Solving Multiobjective Vehicle Routing Problem with Stochastic Demand via Evolutionary Computation”, European Journal of Operational Research, Vol. 177 (2), pp. 813–839.
Tan, K.C., Ou, K., and Lee, L.H., (2001), “A Messy Genetig Algorithm for the Vehicle Routing Problem with Time Windows Constraints”, IEEE Congress on Evolutionary Computation (CEC’01), pp. 679–686.
Tarantilis, C.D., (2005), “Solving the Vehicle Routing Problem with Adaptive Memory Programming Methodology”, Computers and Operations Research, Vol. 32 (9), pp. 2309–2327.
Tarantilis, C.D., and Kiranoudis, C.T., (2002), “Boneroute: An Adaptive Memory-Based Method for Effective Fleet Management”. Annals of Operations Research, Vol. 115 (1), pp. 227–241.
Tarantilis, C.D., and Kiranoudis, C.T., (2005), “A Flexible Adaptive Memory-Based Algorithm for Real-Life Transportation Operations: Two Case Studies from Dairy And Construction Sector”, European Journal of Operational Research, In Press, Corrected Proof.
Tarantilis, C.D., Kiranoudis, C.T., and Vassiliadis, V.S., (2002a), “A Backtracking Adaptive Threshold Accepting Metaheuristic Method for the Vehicle Routing Problem”. System Analysis Modeling Simulation (SAMS), Vol. 42 (5), pp. 631–644.
Tarantilis, C.D., Kiranoudis, C.T., and Vassiliadis, V.S., (2002b), “A List Based Threshold Accepting Algorithm for the Capacitated Vehicle Routing Problem”, International Journal of Computer Mathematics, Vol. 79 (5), pp. 537–553.
Tarantilis, C.D., Diakoulaki, D., and Kiranoudis, C.T., (2004), “Combination of Geographical Information System and Efficient Routing Algorithms for Real Life Distribution Operations”, European Journal of Operational Research, Vol. 152, pp. 437–453.
Tavakkoli-Moghaddam, R., Saremi, A.R., and Ziaee, M.S., (2006), “A Memetic Algorithm for a Vehicle Routing Problem with Backhauls”, Applied Mathematics and Computation, Vol. 181 (2), pp. 1049–1060.
Tian, Y., Song, J., Yao, D., and Hu, J. (2003), “Dynamic Vehicle Routing Problem Using Hybrid Ant System”, The Proceedings of the 2003 IEEE International Conference on Intelligent Transportation Systems, Vol. 2, pp. 970–974.
Thangiah, S.R., (1993), “Vehicle Routing with Time Windows using Genetic Algorithms”, Technical Report SRU-CpSc-TR-93-23, Slippery Rock University, PA.
Thangiah, S.R., Nygard, K.E., and Juell, P.L., (1991), “Gideon: A Genetic Algorithm System for Vehicle Routing with Time Windows”. In Proceedings of the Seventh Conference on Artificial Intelligence Applications, pp. 322–325.
Thangiah, S.R., Potvin, J.Y., and Tong, S., (1996), “Heuristic Approaches to Vehicle Routing with Backhauls and Time Windows”, Computers & Operations Research, Vol. 23 (11), pp. 1043–1057.
Toth, P., and Vigo, D., (1997), “An Exact Algorithm for the Vehicle Routing Problem with Backhauls”, Transportation Science, Vol. 31 (4), pp. 372–385.
Toth, P., and Vigo, D., (1998), “Exact Solutions for the Vehicle Routing Problem”, T.G. Crainic, G. Laporte (Eds.), Fleet Management and Logistics, pp. 1–31, Kluwer, Academic Publishers.
Toth, P., and Vigo, D., (1999), “A Heuristic Algorithm for the Symmetric and Asymmetric Vehicle Routing Problems with Backhauls”, European Journal of Operational Research, Vol. 113 (3), pp. 528–543.
Toth, P., and Vigo, D., (2001), “Models, Relaxations and Exact Approaches for the Capacitated Vehicle Routing Problem”, Discrete Applied Mathematics, Vol. 123, pp. 487–512.
Toth, P., and Vigo, D., (2002a), “Branch and Bound Algorithms for the capacitated Vehicle Routing Problems” P. Toth, D. Vigo. (Eds.), The Vehicle Routing Problem, Monographs on Discrete Mathematics and Applications 9, pp. 29–51, Siam.
Toth, P., and Vigo, D., (2002b), “The Vehicle Routing Problem”, Monographs on Discrete Mathematics and Applications 9, Siam.
Toth, P., and Vigo, D., (2002c), “An Overview of Vehicle Routing Problems”, P. Toth, D. Vigo. (Eds.), The Vehicle Routing Problem, Monographs on Discrete Mathematics and Applications 9, pp. 1–26, Siam.
Toth, P., and Vigo, D., (2002d), “VRP with Backhauls”, P. Toth, D. Vigo. (Eds.), The Vehicle Routing Problem, Monographs on Discrete Mathematics and Applications 9, pp. 195–224, Siam.
Toth, P., and Vigo, D., (2003), “The Granular Tabu Search (and its Application to the Vehicle Routing Problem)”, INFORMS Journal on Computing, Vol. 15(4), pp. 333–348.
Tung, D.V., and Pinnoi, A., (2000), “Vehicle Routing-Scheduling for Waste Collection in Hanoi”, European Journal of Operational Research, Vol. 125, pp. 449–468.
Tzoreff, T.H., Granot, D., Granot, F., and Soisic, G., (2002), “The Vehicle Routing Problem with Pickups and Deliveries on Some Special Graphs”, Discrete Applied Mathematics, Vol. 116 (3), pp. 193–229.
Wade, A., and Salhi, S., (2003), “An Ant System Algorithm for the Mixed Vehicle Routing Problem with Backhaul”. Metaheuristics: Computer Decision-Making, Resende, M.G.C., and de Sousa, J.P., (Eds.), Kluwer Academic Publishers, Boston, pp. 699–719.
Wark, P., and Holt, J., (1994), “A Repeated Matching Heuristic for the Vehicle Routing Problem”, Journal of the Operational Research Society, Vol. 45, pp. 1156–1167.
Willard, J.A.G. (1989), “Vehicle Routing Using r-Optimal Tabu Search”. Master Thesis, The Management School, Imperial College, London.
Wren, A., and Holiday, A., (1972), “Computer Scheduling of Vehicles from One or More Depots to a Number of Delivery Points”, Operations Research Quarterly, Vol. 23, pp. 333–344.
Zografos, K.G., and Androutsopoulos, K.N., (2004), “A Heuristic Algorithm for Solving Hazardous Materials Distribution Problems”, European Journal of Operational Research, Vol. 152, pp. 507–519, Elsevier.
Xu, J., and Kelly, J.P., (1996), “A New Network Flow-Based Tabu Search Heuristic for the Vehicle Routing Problem”, Transportation Science, Vol. 30, pp. 379–393.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Marinakis, Y., Migdalas, A. Annotated bibliography in vehicle routing. Oper Res Int J 7, 27–46 (2007). https://doi.org/10.1007/BF02941184
Issue Date:
DOI: https://doi.org/10.1007/BF02941184