Bibliography on VRP

Algorithms

Exact Algorithms

Branch and Bound

  • U. Blasum, and W. Hochstättler. “Application of the Branch and Cut Method to the Vehicle Routing Problem”. Technical Report zaik2000-386, Centre of Applied Computer Science, University of Cologne, Germany. 2000. Download
  • M. L. Fisher, “Optimal Solution of Vehicle Routing Problems Using Minimum K-trees”, Operations Research 42, 626-642, 1994.
  • L. Ladányi, T.K. Ralphs, and L.E. Trotter Jr. “Branch, Cut, and Price: Sequential and Parallel, in Computational Combinatorial Optimization”. D. Naddef and M. Juenger, eds., Springer, Berlin . 2001. Download
  • E. K. Lee and J. E. Mitchell. “Branch-and-bound methods for integer programming”. in the Encyclopedia of Optimization, Kluwer Academic Publishers. 1998.
  • P. Toth, D. Vigo. “Branch-and-bound algorithms for the capacitated VRP”. In: Toth, P., Vigo, D. (Eds.), The Vehicle Routing Problem. SIAM: Philadelphia, pp. 29-52. 2001.

Branch and Cut

  • P. Augerat, J.M. Belenguer, E. Benavent, A. Corberán, D. Naddef, G. Rinaldi. “Computational Results with a Branch and Cut Code for the Capacitated Vehicle Routing Problem”, Research Report 949-M, Universite Joseph Fourier, Grenoble, France.
  • U. Blasum and W. Hochstattler. “Application of the Branch and Cut Method to the Vehicle Routing Problem”, Zentrum fur Angewandte Informatik Koln Technical Report zpr2000-386 (2000).
  • R. Fukasawa, M.P. de Aragao, M. Reis and E. Uchoa. “Robust Branch-and-Cut-and-Price for the Vehicle Routing Problem”, Relatorios de Pesquisa em Engenharia de Producao RPEP Vol. 3 No. 8 (2003).
  • R. Fukasawa, J. Lysgaard, M.P. de Aragao, M. Reis, E. Uchoa and R.F. Werneck. “Robust Branch-and-Cut-and-Price for the Capacitated Vehicle Routing Problem”, D. Bienstock and G. Nemhauser (Eds.): IPCO 2004, LNCS 3064, Springer-Verlag, pp. 1–15, 2004.
  • J. Lysgaard, A.N. Letchford, and R.W. Eglese. “A New Branch-and-cut Algorithm for Capacitated Vehicle Routing Problems”, Math. Program., Ser. A 100: 423–445, Springer-Verlag, 2004.
  • T.K. Ralphs, L. Kopman, W.R. Pulleyblank, and L.E. Trotter Jr. “On the Capacitated Vehicle Routing Problem”, Mathematical Programming Series B 94 (2003), 343.
  • K.M. Wenger. “Generic Cut Generation Methods for Routing Problems”, Ph.D Dissertation, Institute of Computer Science, University of Heidelberg, Germany, ISBN 3-8322-2545-5, Shaker Verlag,http://www.shaker.de (2003). (bibtex)

Heuristics

Clarke and Wright

  • G. Clarke and J. Wright “Scheduling of vehicles from a central depot to a number of delivery points”, Operations Research, 12 #4, 568-581, 1964.

Fisher and Jaikumar

  • M. L. Fisher and R. Jaikumar. “A Generalized Assignment Heuristic for Vehicle Routing”. Networks, 11:109-124, 1981.

Matching Based Algorithm

  • K. Altinkemer, and B.Gavish. “Parallel Savings Based Heuristic for the Delivery Problem”. Operations Research, 39:456-469, 1991.
  • M. Desrochers, and T. W. Verhoog. “A Matching Based Savings Algorithm for the Vehicle Routing Problem”. Les Cahiers du GERAD G-89-04, École des Hautes Études Commerciales de Montréal, 1989.

Multi-Route Improvement

  • G. A. P. Kinderwater and M. W. P. Savelsbergh. “Vehicle Routing: Handling Edge Exchanges”. In E. H. L. Aarts and J. K. Lenstra (eds), Local Search in Combinatorial Optimization Wiley, Chichester. 1997.
  • P. M. Thompson and H. N. Psaraftis. “Cyclic Transfer Algorithms for the Multivehicle Routing and Scheduling Problems”, Operations Research 41:935-946. 1993.
  • A. Van Breedam. “An Analysis of the Behavior of Heuristics for the Vehicle Routing Problem for a Selection of Problems with Vehicle-Related. Customer-Related, and Time-Related Constraints”. Ph.D. dissertation, University of Antwerp. 1994.

Petal

  • D. M. Ryan, C. Hjorring and F. Glover. “Extensions of the Petal Method for Vehicle Routing”. Journal of the Operational Research Society,44:289-296, 1993.

Sweep

  • B. E. Gillet and L. R. Miller. “A Heuristic Algorithm for the Vehicle Dispatch Problem”. Operations Research, 22:340-349, 1974.
  • A. Wren. “Computers in Transport Planning and Operation”. Ian Allan, London, 1971.
  • A. Wren and A. Holliday. “Computer Scheduling of Vehicles from One or More Depots to a Number of Delivery Points”. Operational Research Quarterly, 23:333-344, 1972.
  • J. Renaud and F.F. Boctor. “A Sweep-Based Algorithm for the Fleet Size and Mix Vehicle Routing Problem”, European Journal of Operational Research 140: 618-628, Elsevier, 2002.

Taillard

  • I. H. Osman. “Metastrategy Simulated Annealing and Tabu Search Algorithms for the Vehicle Routing Problem”. Annals of Operations Research 41:421-451. 1993.
  • É. D. Taillard. “Parallel Iterative Search Methods for Vehicle Routing Problems”. Networks 23, 661-673. 1993.
  • A. Volgenant and R. Jonker. “The Symmetric Traveling Salesman Problem and Edge Exchange in Minimal 1-Trees”. European Journal of Operational Research 12:394-403. 1983.

Metaheuristics

Ant System

  • B. Bullnheimer, R. F. Hartl and C. Strauss. “Applying the Ant System to the Vehicle Routing Problem”. Paper presented at 2nd International Conference on Metaheuristics, Sophia-Antipolis, France. 1997. Download
  • B. Bullnheimer, R.F. Hartl and C. Strauss. “An Improved Ant system Algorithm for the Vehicle Routing Problem”. Paper presented at the Sixth Viennese workshop on Optimal Control, Dynamic Games, Nonlinear Dynamics and Adaptive Systems, Vienna (Austria), May 21-23, 1997, to appear in: Annals of Operations Research (Dawid, Feichtinger and Hartl (eds.): Nonlinear Economic Dynamics and Control, 1999. Download
  • M. Dorigo “Optimization, Learning and Natural Algorithms” Ph.D. Thesis, Politecnico di Milano, Italy, in Italian.1992
  • L. M. Gambardella, E. Taillard, G. Agazzi, “MACS-VRPTW: A Multiple Ant Colony System for Vehicle Routing Problems with Time Windows”, In D. Corne, M. Dorigo and F. Glover, editors, New Ideas in Optimization. McGraw-Hill, 1999 Download
  • Doerner, K., Gronalt, M., Hartl, R., Reimman, M., Strauss, C., Stummer, M.: SavingsAnts for the vehicle routing problem. In Cagnoni, S., ed.: EvoWorkshops02. LNCS 2279, Springer-Verlag (2002) 11–20 Download
  • M. Reimann, K. Doerner, and R.F. Hartl “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, 2003. Springer-Verlag Berlin Heidelberg 2003 Download
  • M. Reimann, K. Doerner, and R.F. Hartl. “D-ants: savings based ants divide and conquer the vehicle routing problem”. Computers & Operations Research 31, 563-591. 2004.
  • Y. Tian, J. Song, D. Yao and J. Hu, “Dynamic vehicle routing problem using hybrid ant system”, The Proceedings of the 2003 IEEE Intemational Confuence on Intelligent Transportation Systems, Page(s): 970- 974 vol.2. 2003.

Constraint Programming

  • P. Shaw. “Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems”, Proceedings of the Fourth International Conference on Principles and Practice of Constraint Programming (CP ’98), M. Maher and J.-F. Puget (eds.), Springer-Verlag, 417-431. 1998. Download
  • L-M. Rousseau, M. Gendreau, G. Pesant and F. Focacci. “Solving VRPTWs with Constraint Programming Based Column Generation”, Annals of Operation Research 130, 199-216, Kluwer Academic Publishers, 2004.

Simulated Annealing

  • O. Arbelaitz, C. Rodriguez and I. Zamakola. “Low Cost Parallel Solutions for the VRPTW Optimization Problem”, 2001 International Conference on Parallel Processing Workshops. IEEE Computer Society. Valencia, Spain. pp. 176-181, 2001.
  • P. Czarnas, Z.J. Czech and P. Gocyla. “Parallel Simulated Annealing for Bicriterion Optimization Problems”, R. Wyrzykowski et al. (Eds.): PPAM 2003, LNCS 3019, Springer-Verlag, pp. 233–240, 2004.
  • Z.J. Czech, P. Czarnas. “Parallel simulated annealing for the vehicle routing problem with time windows”. 10th Euromicro Workshop on Parallel, Distributed and Network-based Processing, Canary Islands – Spain, 376-383 (January 9-11, 2002). Download

Deterministic Annealing

  • G. Dueck and T. Scheurer. “Threshold Accepting: A General Purpose Optimization Algorithm”. Journal of Computational Physics, 90:161-175. 1990.
  • G. Dueck. “New Optimization Heuristics :The Great Deluge Algorithm and the Record-To-Record Travel”. Journal of Computational Physics, 104:86-92. 1993.

Genetic Algorithms

  • Alba, E., Dorronsoro, B. “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. 2004.
  • Alba, E., Dorronsoro, B. “Computing Nine New Best-So-Far Solutions for Capacitated VRP with a Cellular Genetic Algorithm”, Information
    Processing Letters    , In press. 2005. Download
  • Berger, J., Barkaoui, M. “A hybrid genetic algorithm for the capacitated vehicle routing problem”. In Cantú-Paz, E., ed.: GECCO03. LNCS 2723, Illinois, Chicago, USA, Springer-Verlag. 2003. 646–656
  • J. Berger, M. Barkaoui and O. Bräysy. “A Parallel Hybrid Genetic Algorithm for the Vehicle Routing Problem with Time Windows”. Working paper, Defense Research Establishment Valcartier, Canada. 2001. Download
  • O. Bräysy, and M. Gendreau “Genetic Algorithms for the Vehicle Routing Problem with Time Windows”. Internal Report STF42 A01021, SINTEF Applied Mathematics, Department of Optimization, Oslo, Norway. 2001. Download
  • D. Goldberg. “Genetic Algorithms in Search, Optimization, and Machine Learning”. Addison Wesley Publishing Company Inc, Ney York. 1989.
  • J. H. Holland. “Adaptation in Natural and Artificial Systems”. University of Michigan Press, Ann Arbor. 1975.
  • A. Jaszkiewicz and P. Kominek. “Genetic Local Search with Distance Preserving Recombination Operator for a Vehicle Routing Problem”, European Journal of Operational Research 151:352-364, Elsevier, 2003.
  • W. Jih, and J.Y. Hsu. “Dynamic Vehicle Routing Using Hybrid Genetic Algorithms”. In Proceedings of the 1999 IEEE International Conference on Robotics & Automation. Detroit, Michigan. May 1999. Download
  • K. A. De Jong. “An Analysis of the Behavior of a Class of Genetic Adaptative Systems”. Ph.D. thesis, University of Michigan, U.S.A. 1975.
  • A. Lim, and F. Wang. “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). 2004. Download
  • M. J. W. Morgan, and C. L. Mumford. “Capacitated Vehicle Routing: perturbing the landscape to fool and algorithm”, IEEE Congress on Evolutionary Computation (CEC) Edinburgh, Scotland, 2005, 2271-2277.
  • F. B. Pereira, J. Tavares, P. Machado, and E. Costa, GVR: a New Genetic Representation for the Vehicle Routing Problem, In Proceedings of the 13th Irish Conference on Artificial Intelligence and Cognitive Science
    (AICS 2002), pp. 95-102, Limerick, Ireland, 12-13 September, 2002. Download
  • P. Machado, J. Tavares, F. B. Pereira, and E. Costa, Vehicle Routing Problem: Doing it the Evolutionary Way, In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2002), pp. 690, New York, USA,
    9-13 July, 2002. Download
  • Prins, C. “A simple and eective evolutionary algorithm for the vehicle routing problem”. Volume 31, Issue 12, October, Pages 1985-2002, 2004.
  • K.C. Tan, K. Ou and L.H. Lee. “A Messy Genetig Algorithm for the Vehicle Routing Problem with Time Windows Constraints”, IEEE Congress on Evolutionary Computation (CEC’01), pp. 679-686, 2001.
  • J. Tavares, F. B. Pereira, P. Machado, and E. Costa, Crossover and Diversity: A Study about GVR, In Proceedings of the Analysis and Design of Representations and Operators (ADoRo’2003) a bird-of-a-feather workshop at the 2003 Genetic and Evolutionary Computation Conference (GECCO-2003), Chicago, Illinois, USA, 12-16 July, 2003.Download
  • J. Tavares, F. B. Pereira, P. Machado, and E. Costa, On the Influence of GVR in Vehicle Routing, In Proceedings of the 2003 ACM Symposium On Applied Computing (SAC 2003) – Evolutionary Computation And Optimization Track, pp.753-758, Melbourne, Florida, USA, 9-13 March, 2003. Download
  • S.R. Thangiah. Vehicle Routing with Time Windows using Genetic Algorithms, Technical Report SRU-CpSc-TR-93-23, Computer Science Department, Slippery Rock University, Slippery Rock, PA. 1993. Download
  • S. R. Thangiah, K. E. Nygard, and P. L. Juell. Gideon: A genetic algorithm system for vehicle routing with time windows. In Proceedings of the Seventh Conference on Artificial Intelligence Applications, pages 322–325, Miami, Florida, 1991.
  • K.Q. Zhu. “A Diversity-Controlling Adaptive Genetic Algorithm for the Vehicle Routing Problem with Time Windows”, 15th IEEE International Conference on Tools with Artificial Intelligence (ICTAI’03), Sacramento, California, USA, pp 176-183, 2003.
  • K.Q. Zhu and Z. Liu. “Empirical Study of Population Diversity in Permutation-Based Genetic Algorithm”, K. Deb et al. (Eds.): GECCO 2004, LNCS 3103, Springer-Verlag, pp. 420–421, 2004.

Tabu Search

  • A. Amberg, W. Domschke and S. Voss (2000). Multiple Center Capacitated Arc Routing Problems: A Tabu Search Algorithm using Capacitated Trees. European Journal of Operational Research 124, 360-376. Download
  • P. Badeau, M. Gendreau, F. Guertin, J.-Y. Potvin and E. Taillard. “A Parallel Tabu Search Heuristic for the Vehicle Routing Problem with Time Windows”. Transportation Research – C 5, 109-122. 1997. Download
  • O. Bräysy, and M. Gendreau. “Tabu Search Heuristics for the Vehicle Routing Problem with Time Windows”. Internal Report STF42 A01022, SINTEF Applied Mathematics, Department of Optimisation, Oslo, Norway. 2001. Download
  • J.-F. Cordeau, G. Laporte, A. Mercier. “A unified tabu search heuristic for vehicle routing problems with time windows”. Journal of the Operational Research Society 52, 928-936. 2001.
  • F. Glover. “Future Paths for Integer Programming and Links to Artificial Intelligence”.Computers and Operations Research, 13:533-549. 1986
  • J. Homberger, and H. Gehring. “Two Evolutionary Metaheuristics for the Vehicle Routing Problems with Time Windows”. INFOR 37, 297-318. 1999. Download
  • J. Kelly and J. P. Xu. “A Network Flow-Based Tabu Search Heuristic for the Vehicle Routing Problem”. Transportation Science, 30:379-393. 1996.
  • C. Rego, (2001) Node Ejection Chains for the Vehicle Routing Problem: Sequential and Parallel Algorithms. Parallel-Computing 27, 201-222. Download
  • Y. Rochat and È. D. Taillard. “Probabilistic Diversification and Intensification in Local Search for Vehicle Routing”. Journal of Heuristics, 1:147-167. 1995.
  • É. D. Taillard, P. Badeau, M. Gendreau, F. Guertin, J.Y. Potvin, “A tabu search heuristic for the vehicle routing problem with soft time windows”, Transportation science 31, 1997, 170-186. Download
  • S. R. Thangiah, I. H. Osman, T. Sun, Hybrid Genetic Algorithm Simulated Annealing and Tabu Search Methods for Vehicle Routing Problem with Time Windows, Technical Report 27, Computer Science Department, Slippery Rock University, 1994. Download
  • P. Toth and D. Vigo. “The Granular Tabu Search (and its Application to the Vehicle Routing Problem)”. Working Paper, DEIS, University of Bologna. 1998.

Other Heuristics and Metaheuristics

  • J. Antes, and U. Derigs. “A New Parallel Tour Construction Algorithm for the Vehicle Routing Problem with Time Windows”. Working Paper, Department of Economics and Computer Science, University of Köln, Germany. 1995. Download
  • D. Applegate, W. Cook, S. Dash and A. Rohe. “Solution of a Min-Max Vehicle Routing Problem”. Working Paper, Algorithms and Optimization Department, ATT Labs. To appear in INFORMS Journal on Computing. 2001.Download
  • A. Bachem, W. Hochstättler and M. Malich. “The Simulated Trading Heuristic for Solving Vehicle Routing Problems”. Discrete Applied Mathematics 65, 47-72. 1996. Download
  • B. De Backer, V. Furnon, P. Shaw, P. Kilby, and P. Prosser. Solving Vehicle Routing Problems Using Constraint Programming and Metaheuristics. Journal of Heuristics, 6:501-523, 2000. Download
  • R. Bent, and P. Van Hentenryck. A Two-Stage Hybrid Local Search for the Vehicle Routing Problem with Time Windows. Technical Report CS-01-06, Department of Computer Science, Brown University, USA. 2001. Download
  • D. Bertsimas, and D. Simchi-Levi. “The New Generation of Vehicle Routing Research: Robust Algorithms Addressing Uncertainty”. Operations Research 44, 286-304. 1996. Download
  • J. Bramel, and D. Simchi-Levi. “Probabilistic Analysis and Practical Algorithms for the Vehicle Routing Problem with Time Windows”. Operations Research 44, 501-509. 1992. Download
  • J. B. Bramel and D. Simchi-Levi. “A location Based Heuristic for General Routing Problems”. Operations Research, 43:649-660, 1995. Download
  • J. Bramel, and D. Simchi-Levi. “On the Effectiveness of Set Partitioning Formulations for the Vehicle Routing Problem”. Operations Research 45, 295-301. 1997. Download
  • O. Bräysy and M. Gendreau. “Metaheuristics for the Vehicle Routing Problem with Time Windows”. SINTEF Applied Mathematics, Research Council of Norway. 2001. Download
  • O. Bräysy and M. Gendreau. “Route Construction and Local Search Algorithms for the Vehicle Routing Problem with Time Windows”.SINTEF Applied Mathematics, Research Council of Norway. 2001. Download
  • O. Bräysy,”A Reactive Variable Neighborhood Search Algorithm for the Vehicle Routing Problem with Time Windows”. To be published in INFORMS Journal on Computing. 2001. Download
  • O. Bräysy, and M. Gendreau. “Route Construction and Local Search Algorithms for the Vehicle Routing Problem with Time Windows”. Internal Report STF42 A010214, SINTEF Applied Mathematics, Department of Optimisation, Oslo, Norway. 2001. Download
  • Y. Caseau, F. Laburthe and G. Silverstein. “A Meta-Heuristic Factory for Vehicle Routing Problems”, J. Jaffar (Ed.): CP’99, LNCS 1713, Springer-Verlag, pp. 144-159, 1999.
  • M. Charikar, S. Khuller and B. Raghavachari. “Algorithms for Capacitated Vehicle Routing”. SIAM Journal on Computing 31, 665-682. 2001. Download
  • A.V. Donati, R. Montemanni, L.M. Gambardella and A.E. Rizzoli, “Integration of a Robust Shortest Path Algorithm with a Time Dependent Vehicle Routing Model and Applications” . International Symposium on Computational Intelligence for Measurement Systems and Applications (CIMSA 2003), Lugano, Switzerland, 26-31, 2003.
  • L. M. Gambardella. “Vehicle Routing Problems (VRPs)”. Technische Universiteit Eindhoven. Short Course; November 28-29 2000. Download
  • M. Gendreau, G. Laporte, and J.-Y. Potvin. “Metaheuristics for the vehicle routing problem”. Technical Report CRT-963, Centre de Recherche sur les Transports, Université de Montréal, jan 1994. Download
  • M. Gendreau, P. Soriano and L. Salvail. “Metaheuristics for the vehicle routing problem”. In Lenstra, J. and Aarts, E., editors, Local Search Algorithms, Chichester. John Wiley and Sons.
  • L.C.T. Gomes and F.J. Zuben. “Vehicle Routing Based on Self-Organization with and without Fuzzy Inference”, Proceedings of the IEEE International Conference on Fuzzy Systems (FUZZ-IEEE’2002), vol. 2, in the 2002 IEEE World Congress on Computational Intelligence (WCCI’2002), Honolulu, Hawaii, pp. 1310-1315, 2002.
  • V. Gorodetski, O. Karsaev and V. Konushy. “Multi-agent System for Resource Allocation and Scheduling”, V. Marík et al. (Eds): CEEMAS 2003, LNAI 2691, Springer-Verlag, pp. 236-246, 2003.
  • M. Gronalt, R.F. Hartl and M. Reimann. “New Savings Based Algorithms for Time Constrained Pickup and Delivery of Full Truckloads”, European Journal of Operational Research 151: 520-535, Elsevier, 2003.
  • K. Jeevan Madhu and S. Saxena, “Parallel Algorithms for Vehicle Routing Problems”, Proceedings of Fifth International Conference on High Performance Computing, 17-20 December, 1998, Madras, India. Download
  • P. Kilby, P. Prosser and P. Shawn. “A Comparison of Traditional and Constraint-Based Heuristic Methods on Vehicle Routing Problems with Side Constraints”, Constraints 5, 389-414, Kluwer Academic Publishers, 2000.
  • G. Laporte, M. Gendreau, J-Y. Potvin, F. Semet. “Classical and Modern Heuristics for the vehicle routing problem”. International Transaction in Operational Research, vol. 7, pp. 285-300, 2000. Download
  • G. Laporte and F. Semet. “Classical Heuristics for the Vehicle Routing Problem”. Les Cahiers du GERAD, G98-54, Group for Research in Decision Analysis, Montreal, Canada. 1998. Download
  • A.N. Letchford, R.W. Eglese and J. Lysgaard. “Multistars, partial multistars and the capacitated vehicle routing problem”, Math. Program., Ser. A 94: 21–40, 2002.
  • Z. Li1, S. Guo1, F. Wang and A. Lim. “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, 2004.
  • H. Li and A. Lim. “Local Search with Annealing-Like Restarts to Solve the VRPTW”, European Journal of Operational Research 150: 115-127, Elsevier, 2003.
  • Y. Marinakis and A. Migdalas. “Heuristic Solutions of Vehicle Routing Problems in Supply Chain Management”. 2001. Download
  • D. Mester and O. Bräysy. “Active Guided Evolution Strategies for Large Scale Vehicle Routing Problems with Time Windows”. Computers & Operations Research 32, 1593-1614. 2005.
  • D. Mester and O. Bräysy. “Active Guided Evolution Strategies for Large Scale Vehicle Routing Problem”. Working Paper, University of Haifa, Israel. 2004.
  • N. Mukai, J. Feng and T. Watanabe. “Heuristic Approach Based on Lambda-Interchange for VRTPR-Tree on Specific Vehicle Routing Problem with Time Windows”, R. Orchard et al. (Eds.): IEA/AIE 2004, LNAI 3029,
    Springer-Verlag, pp. 229-238, 2004.
  • G. Nikolakopoulou, S. Kortesis, A. Synefaki and R. Kalfakakou. “Solving a Vehicle Routing Problem by Balancing the Vehicles Time Utilization”, European Journal of Operational Research 152: 520-527, Elsevier, 2004.
  • Mikael Nilsson. “Parameter Tuning Experiments of Population-based Algorithms”, Bachelor Thesis, Mid Sweden University, 2011.
  • H. Paessens. “The Savings Algorithm for the Vehicle Routing Problem”. Eur. J. Oper. Res. 34:336. 1988.
  • C. Prins. “Efficient Heuristics for the Heterogeneous Fleet Multitrip VRP with Application to a Large-Scale Real Case”, Journal of Mathematical Modelling and Algorithms 1: 135-150, Kluwer Academic Publishers,
    2002.
  • K. Qili and K. Ong.”A reactive method for real time dynamic vehicle routing problem”, 12th ICTAI 2000, Vancouver, Canada, 2000. 18 Download
  • C. Rego and P. Leão. “A Scatter Search Tutorial for Graph-Based Permutation Problems”. 2001. Download
  • J. Schulze, T. Fahle. “A parallel algorithm for the vehicle routing problem with time window constraints”, Technical Report, University of Paderborn, 1997; to appear in Ann. Oper. Res. Download
  • J. Sniezek and L. Bodin, “Cost Models for Vehicle Routing Problems”. Proceedings of the 35th Hawaii International Conference on System Sciences (HICSS-35’02), Hawaii, pp 83-94, 2002.
  • T. Takeno, Y. Tsujimura and G. Yamazaki, “A Single-Phase Method Based on Evolution Calculation for Vehicle Routing Problem”. Fourth International Conference on Computational Intelligence and Multimedia Applications (ICCIMA’01), Yokusike City, Japan, pp. 103-117, 2001.
  • V. Tam and L.C.Y. Tseng, “Effective Heuristics to Solve Pickup and Delivery Problems with Time Windows”. 15th IEEE International Conference on Tools with Artificial Intelligence (ICTAI’03), Sacramento, California, USA, IEEE Computer Society, 184-188, 2003.
  • V. Tam and K.T. Ma, “Combining Meta-Heuristics to Effectively Solve the Vehicle Routing Problems with Time Windows”. Artificial Intelligence Review, vol. 21, iss. 2, pp. 87-112(26) Kluwer Academic Publishers, 2004.
  • C. D. Tarantilis. “Solving the vehicle routing problem with adaptive memory programming methodology. Computers & Operations Research, in press. 2004.
  • C.D. Tarantilis and C.T. Kiranoudis. “BoneRoute: An Adaptive Memory-Based Method for Effective Fleet Management”, Annals of Operations Research 115: 227-241, Kluwer Academic Publishers, 2002.
  • C.D. Tarantilis, C.T. Kiranoudis and V.S. Vassiliadis. “A Threshold Accepting Metaheuristic for the Heterogeneous Fixed Fleet Vehicle Routing Problem”, European Journal of Operational Research 152: 148-158, Elsevier, 2004.
  • A. Van Breedam. “Comparing Descent Heuristics and Metaheuristics for the Vehicle Routing Problem”, Computers & Operations Research 28: 289-315, 2001.
  • A. Van Breedam. “A Parametric Analysis of Heuristics for the Vehicle Routing Problem with Side-Constraints”, European Journal of Operational Research 137: 348-370, Elsevier, 2002.

Multi-Objective Approaches

  • Tan, K. C., Lee, T. H., Chew, Y. H. and Lee, L. H. (2003). “A hybrid multiobjective evolutionary algorithm for solving truck and trailer vehicle routing problems”, IEEE Congress on Evolutionary Computation 2003, Canberra, Australia, 8-12 December, pp. 2134-2141.
  • N. Jozefowiez, F. Semet and E-G. Talbi. “Parallel and Hybrid Models for Multi-objective Optimization: Application to the Vehicle Routing Problem”, J.J. Merelo Guervós et al. (Eds.): PPSN VII, LNCS 2439, Springer-Verlag, pp. 271–280, 2002.
  • S. Sa’adah, P. and B. Paechter. “Improving Vehicle Routing Using a Customer Waiting Time Colony”, J. Gottlieb and G.R. Raidl (Eds.): EvoCOP 2004, LNCS 3004, Springer-Verlag, pp. 188–198, 2004.

Problems

NP-Problem

  • S. A. Cook. “The complexity of theorem proving procedures”. Proceedings, Third Annual ACM Symposium on the Theory of Computing, ACM, New York, 1971, 151-158
  • S. A. Cook. “The P versus NP Problem”. Manuscript prepared for the Clay Mathematics Institute for the Millennium Prize Problems. April, 2000. Download
  • Alan Turing. “On computable numbers with an application to the entscheidnungs problem”. Proc. London Math. Soc. ser. 2, 42:230–265, 1936-7.

VRP

  • L. Bianchi,”Notes on Dynamic Vehicle Routing – The State of Art”. Technical Report, IDSIA-05-01, IDSIA, Switzerland. 2000. Download
  • W. Burrows. “The Vehicle Routing Problem with Loadsplitting: A Heuristic Approach”. In 24th Annual Conference of the Operational Research Society of New Zealand, pages 33-38, 1988.
  • G. B. Dantzig and R.H. Ramser. “The Truck Dispatching Problem”. Management Science 6, 80–91. 1959
  • T. Duncan. “Experiments in the use of Neighborhood Search Techniques for Vehicle Routing”. BCS Expert Systems. 1995. Download
  • F. Maffioli. “The vehicle routing problem: A book review”, Quarterly Journal of the Belgian, French and Italian Operations Research Societies (4OR) 1: 149–153, Springer-Verlag, 2003.
  • J. K. Lenstra, A.H.G. Rinnooy Kan, “Complexity of vehicle routing and scheduling problems”, Networks, 11, pp. 221-227. 1981
  • B. L. Golden, A. A. Assad (Eds.): “Vehicle Routing: Methods and Studies, Studies in Management Science and Systems”, Vol. 16, Elsevier Science Publ., Amsterdam, 1988, 7-45.
  • G. Reinelt: “TSPLIB – A Traveling Salesman Problem Library”,ORSA Journal on Computing 3 , 376-384. 1991.
  • P. Toth, D. Vigo: “The Vehicle Routing Problem”. Monographs on Discrete Mathematics and Applications. SIAM, Philadelphia. 2001.

CVRP

  • F. Li, B. Golden, E. Wasil. Very large-scale vehicle routing: new test problems, algorithms, and results. Computers & Operations Research, in press. 2004.
  • T. Ralphs, J. Hartman and M. Galati. “Capacitated Vehicle Routing and Some Related Problems”. Some CVRP Slides. Rutgers University. 2001. Download
  • T.K. Ralphs, L. Kopman, W.R. Pulleyblank, and L.E. Trotter Jr. “On the Capacitated Vehicle Routing Problem”. Math. Program., Ser. B 94: 343–359, Springer-Verlag, 2003. Preliminary version: Download

DVRP

  • D.M. Chitty and M.L. Hernandez. “A Hybrid Ant Colony Optimisation Technique for Dynamic Vehicle Routing”, K. Deb et al. (Eds.): GECCO 2004, LNCS 3102, Springer-Verlag, pp. 48–59, 2004.
  • Y. Tian, J. Song, D. Yao and J. Hu. “Dynamic Vehicle Routing Problem Using Hybrid Ant System”, Proceedings of the 2003 IEEE Intemational Confuence on Intelligent Transportation Systems. pp 970-974. 2003.

MDVRP

  • C. Hjorring. “The Vehicle Routing Problem and Local Search Metaheuristics”, Chapter 2. PhD thesis, Department of Engineering Science, The University of Auckland, 1995. Download

PVRP

  • E. Angelelli and M.G. Speranza. “The Periodic Vehicle Routing Problem with Intermediate Facilities”, European Journal of Operational Research 137:233-247, Elsevier, 2002.
  • S. Baptista, R.C. Oliveira and E. Zúquete. “A Period Vehicle Routing Case Study”, European Journal of Operational Research 139:220-229, Elsevier, 2002.

SDVRP

  • M. Dror, G. Laporte, P. Trudeau, ”Vehicle routing with split deliveries”, Discrete Appl. Math. 50, 239-254 (1994).
  • C. Archetti, R. Mansini, M.G. Speranza – “The Split Delivery Vehicle Routing Problem with Small Capacity”, Tecnical Report n. 201,Department of Quantitative Methods, University of Brescia 2001. Download

SVRP

  • G. Laporte, and F.V. Louveaux. “Solving Stochastic Routing Problems with the Integer L-shaped Method”. In Fleet Management and Logistics, T.G. Crainic and G. Laporte (eds.), 159-167, Kluwer Academic Publishers, Boston. 1998. Download

VRPB

  • Cumhur Alper Gelogullari. “Vehicle Routing Problem with Backhauls”. Power Point Presentation Download
  • M. Goetschalckx, and Jacobs-Blecha, C.”The Vehicle Routing Problem with Backhauls: An Effective Heuristic Based on the Generalized Assignment Problem with Ring Metric Norm”. Material Handling Research Center Technical Report TR-88-13.
  • M. Goetschalckx, and Jacobs-Blecha, C. “The Vehicle Routing Problem with Backhauls: An Optimization Based Approach” .Proceedings of the 2nd Industrial Engineering Research Conference, May 26-27, 1993, Los Angeles, California, pp. 504-509.
  • C. Jacobs-Blecha, and M. Goetschalckx. “The vehicle routing problem with backhauls: properties and solution algorithms”. Technical Report, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia. Presented at the National Transportation Research Board, January 13-15, 1992, Washington DC. Download

VRPPD

  • Gribkovskaia, Irina ; Halskau, Øyvind ; Bugge Myklebost, Kim N. “Models for Pick-up and Deliveries from Depots with Lasso Solutions” Download
  • G. Righini, “Approximation algorithms for the vehicle routing problem with pick-up and delivery”, Note del Polo – Ricerca 33, Polo Didattico e di Ricerca di Crema, Università degli Studi di Milano, Luglio 2000 Download

VRPSF

  • J.F. Bard, L. Huang, M. Dror, and P. Jaillet, “A Branch and Cut Algorithm for the VRP with Satellite Facilities”, IIE Transactions 30, pp 821-834 Download

VRPPD

  • Cordeau, J.-F., Desaulniers, G., Desrosiers, J., Solomon, M.M., Soumis, F. “VRP with Time Windows”. In P. Toth and D. Vigo (eds.): The Vehicle Routing Problem, SIAM Monographs on Discrete Mathematics and Applications, vol. 9, Philadelphia, PA, 157-193. 2002. Download
    (534KB)
  • M. M. Solomon. “Algorithms for the Vehicle Routing Problem with Time Windows”. Transportation Science, 29(2), pp. 156-166. 1995.
  • H.C. Lau, M. Sim and K.M. Teo. “Vehicle Routing Problem with Time Windows and a Limited Number of Vehicles”, European Journal of Operational Research 148: 559-569, Elsevier, 2003.
  • L.H. Lee, K.C. Tan, K. Ou and Y.H. Chew. “Vehicle Capacity Planning System: A Case Study on Vehicle Routing Problem With Time Windows”, IEEE Transactions on Systems, Man and Cybernetics, Part A, 33(2), 169-178, 2003.
  • A. Rhalibi and G. Kelleher. “An Approach to Dynamic Vehicle Routing, Rescheduling and Disruption Metrics”, Systems, man and cybernetics. Proceedings (SMCC’03), Washigton D.C., U.S.A., 3613-3618, 2003.
  • Russell RA. Hybrid heuristics for the vehicle routing problem with time windows. Transportation Science 29: 156–66. 1995.

Other Variants

  • G. Ghiani, F. Guerriero, G. Laporte amd R. Musmanno. “Real-Time Vehicle Routing: Solution Concepts, Algorithms and Parallel Computing Strategies”, European Journal of Operational Research 151: 1-11, Elsevier, 2003.
  • H. Glaab. “A New Variant of a Vehicle Routing Problem: Lower and Upper Bounds”, European Journal of Operational Research 139: 557-577, Elsevier, 2002.
  • G. M. GIAGLIS, I. MINIS, A. TATARAKIS, V. ZEIMPEKIS . “Minimizing Logistics Risk through Real-Time Vehicle Routing and Mobile Technologies: Research To-Date and Future Trends”, International Journal of Physical Distribution and Logistics Management, Vol. 34, No. 9, pp.749-764. 2004.Download

Real World Applications

  • G.W. Kinney Jr., R.R. Hill, J.T. Moore. “Devising a Quick-running heuristic for an unmanned aerial vehicle (UAV) routing system “, Operational ^M Research Society 1-11, 2004.
  • R.W. Harder, R.R. Hill, J.T. Moore. “A Java universal vehicle router for routing unmanned aerial vehicles “, International Transaction in Operational ^M Research 11, 259-275, 2004.
  • S. Baptista, R.C. Oliveira and E. Zúquete. “A Period Vehicle Routing Case Study”, European Journal of Operational Research 139:220-229, Elsevier, 2002.
  • W-C. Chiang and R.A. Russell. “Integrating Purchasing and Routing in a Propane Gas Supply Chain”, European Journal of Operational Research 154: 710-729, Elsevier, 2004.
  • K. Hirota, F. Dong, K. Chen and Y. Takama. “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, 2002.
  • B. Kazak and K. Altinkemer. “Optimization of Multi-Feeder (Depot) Printed Circuit Board Manufacturing with Error Guarantees”, European Journal of Operational Research 150: 370-394, Elsevier, 2003.
  • N.F. Matsatsinis. “Towards a Decision Support System for the Ready Concrete Distribution System: A Case of a Greek Company”, European Journal of Operational Research 152: 487-499, Elsevier, 2004.
  • L. Özdamar, E. Ekinci and B. Küçükyazici. “Emergency Logistics Planning in Natural Disasters”, Annals of Operations Research 129: 217-245, Kluwer Academic Publishers, 2004.
  • R. Ruiz, C. Maroto and J. Alcaraz. “A Decision Support System for a Real Vehicle Routing Problem”, European Journal of Operational Research 153: 593-606, Elsevier, 2004.
  • E. Sambracos, J.A. Paravantis, C.D. Tarantilis and C.T. Kiranoudis. “Dispatching of Small Containers via Coastal Freight Liners: The Case of the Aegean Sea”, European Journal of Operational Research 152: 365-381, Elsevier, 2004.
  • C.D. Tarantilis, D. Diakoulaki and C.T. Kiranoudis. “Combination of Geographical Information System and Efficient Routing Algorithms for Real Life Distribution Operations”, European Journal of Operational Research 152: 437-453, Elsevier, 2004.
  • D.V. Tu and A. Pinnoi. “Vehicle Routing-Scheduling for Waste Collection in Hanoi”, European Journal of Operational Research 125: 449-468, Elsevier, 2000.
  • K.G. Zografos and K.N. Androutsopoulos. “A Heuristic Algorithm for Solving Hazardous Materials Distribution Problems”, European Journal of Operational Research 152: 507-519, Elsevier, 2004.