mortar board
Vehicle Routing #001

Research and Practise.com

All you need to know, all in one place

The scientific and industrial communities are often unaware of the work of each other. We aim to provide a service where you can find all the information you require, for a specicific specialisation, all on the same web site. We would welcome suggestions for other areas.

Your advert could be here - take a look at our advertising rates
Your advert could be here - take a look at our advertising rates

Vehicle Routing: Surveys

The Vehicle Routing Problem has received a great deal of interest from both the scientific and the industrial community. As a result a significant number of survey papers have been written and there have also been several surveys of software that is available. On this page we have listed all the resources that we are aware of. If you believe that something is missing, we would like to hear from you. Please email us at admin@researchandpractise.com.

Software Surveys

  1. Vehicle Routing Software Survey. This article appeared in OR/MS Today in February 2010 (and is available online).

  2. Vehicle Routing Software Survey. This article appeared in OR/MS Today in February 2008 (and is available online).

  3. On the Road to Service. This article appeared in OR/MS Today in August 2000 (and is available online).

Book Chapters

  1. Powell W.B., Jaillet P. and Amadeo Odoni A. (1995) Network Routing, volume 8, in Stochastic and Dynamic Networks and Routing, pp 141-295. Elsevier Science, Amsterdam
  2. Gendreau M. and Potvin J-Y. (1998) Fleet Management and Logistics, in Dynamic Vehicle Routing and Dispatching, pp 115- 26. Kluwer Academic Publishers
  3. Psaraftis H.N. (1988) Vehicle Routing: Methods and Studies, in Dynamic Vehicle Routing Problems, pp 223-248. Elsevier Science Publishers B.V. (North Holland)

Scientific Journals

Show All Abstracts Hide All Abstracts

  1. Laporte G. (2009) Fifty Years of Vehicle Routing. Transportation Science, In Press. doi:10.1287/trsc.1090.0301  (what is a doi? A doi (Document Object Identifier) is a unique identifier for journal papers. This provides direct access to the location where the original article is published using the URL http://dx.doi/org/xxxx (replacing xxx with the doi))
    Show Abstract
    Abstract: The Vehicle Routing Problem (VRP) was introduced 50 years ago by Dantzig and Ramser under the title “The Truck Dispatching Problem.” The study of the VRP has given rise to major developments in the fields of exact algorithms and heuristics. In particular, highly sophisticated exact mathematical programming decomposition algorithms and powerful metaheuristics for the VRP have been put forward in recent years. The purpose of this article is to provide a brief account of this development.

  2. Potvin J-Y (2009) Evolutionary Algorithms for Vehicle Routing. INFORMS Journal on Computing, 21(4), pp 518-548. doi:10.1287/ijoc.1080.0312  (what is a doi? A doi (Document Object Identifier) is a unique identifier for journal papers. This provides direct access to the location where the original article is published using the URL http://dx.doi/org/xxxx (replacing xxx with the doi))
    Show Abstract
    Abstract: This paper is a survey of the literature on applications of evolutionary algorithms for vehicle routing problems. It reports on genetic algorithms, evolution strategies, and particle swarm optimization when applied to the classical capacitated vehicle routing problem and many of its variants. The performance of evolutionary algorithms is also compared with the best alternative problem-solving approaches on benchmark instances.

  3. Marinakis1 Y. and Migdalas A. (2007) Annotated Bibliography in Vehicle Routing. Operational Research, 7(1), pp 27-46. doi:10.1007/BF02941184  (what is a doi? A doi (Document Object Identifier) is a unique identifier for journal papers. This provides direct access to the location where the original article is published using the URL http://dx.doi/org/xxxx (replacing xxx with the doi))
    Show Abstract
    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.

  4. Bräysy O. and Gendreau M. (2005) Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms. Transportation Science, 39(1), pp 104-118 doi:10.1287/trsc.1030.0056  (what is a doi? A doi (Document Object Identifier) is a unique identifier for journal papers. This provides direct access to the location where the original article is published using the URL http://dx.doi/org/xxxx (replacing xxx with the doi))

    A version of this paper can be downloaded from here.
    Show Abstract
    Abstract: This paper presents a survey of the research on the vehicle routing problem with time windows (VRPTW). The VRPTW can be described as the problem of designing least cost routes from one depot to a set of geographically scattered points. The routes must be designed in such a way that each point is visited only once by exactly one vehicle within a given time interval, all routes start and end at the depot, and the total demands of all points on one particular route must not exceed the capacity of the vehicle. Both traditional heuristic route construction methods and recent local search algorithms are examined. The basic features of each method are described, and experimental results for Solomon’s benchmark test problems are presented and analyzed. Moreover, we discuss how heuristic methods should be evaluated and propose using the concept of Pareto optimality in the comparison of different heuristic approaches. The metaheuristic methods are described in the second part of this article.

  5. Bräysy O. and Gendreau M. (2005) Vehicle Routing Problem with Time Windows, Part II: Metaheuristics. Transportation Science, 39(1), pp 119-139 doi:10.1287/trsc.1030.0057  (what is a doi? A doi (Document Object Identifier) is a unique identifier for journal papers. This provides direct access to the location where the original article is published using the URL http://dx.doi/org/xxxx (replacing xxx with the doi))

    This paper can be downloaded from here.
    Show Abstract
    Abstract: This paper surveys the research on the metaheuristics for the Vehicle Routing Problem with Time Windows (VRPTW). The VRPTW can be described as the problem of designing least cost routes from one depot to a set of geographically scattered points. The routes must be designed in such a way that each point is visited only once by exactly one vehicle within a given time interval; all routes start and end at the depot, and the total demands of all points on one particular route must not exceed the capacity of the vehicle. Metaheuristics are general solution procedures that explore the solution space to identify good solutions and often embed some of the standard route construction and improvement heuristics described in the first part of this article. In addition to describing basic features of each method, experimental results for Solomon’s benchmark test problems are presented and analyzed.

  6. 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, 7, pp 285-300 doi:10.1111/j.1475-3995.2000.tb00200.x  (what is a doi? A doi (Document Object Identifier) is a unique identifier for journal papers. This provides direct access to the location where the original article is published using the URL http://dx.doi/org/xxxx (replacing xxx with the doi))

    This paper can be downloaded from here.
    Show Abstract
    Abstract: This article is a survey of heuristics for the Vehicle Routing Problem. It is divided into two parts: classical and modern heuristics. The ®rst part contains well-known schemes such as, the savings method, the sweep algorithm and various two-phase approaches. The second part is devoted to tabu search heuristics which have proved to be the most successful metaheuristic approach. Comparative computational results are presented.

  7. Bertsimas D.J. and Simchi-Levi D. (1996) A New Generation of Vehicle Routing Research: Robust Algorithms, Addressing Uncertainty. Operations Research, 44(2), pp 286-304. doi:10.1287/opre.44.2.286  (what is a doi? A doi (Document Object Identifier) is a unique identifier for journal papers. This provides direct access to the location where the original article is published using the URL http://dx.doi/org/xxxx (replacing xxx with the doi))
    Show Abstract
    Abstract: In recent years new insights and algorithms have been obtained for the classical, deterministic vehicle routing problem as well as for natural stochastic and dynamic variations of it. These new developments are based on theoretical analysis, combine probabilistic and combinatorial modeling, and lead to new algorithms that produce near-optimal solutions, and a deeper understanding of uncertainty issues in vehicle routing. In this paper, we survey these new developments with an emphasis on the insights gained and on the algorithms proposed.

  8. Psaraftis H.N. (1995) Dynamic vehicle routing: Status and prospects. Annals of Operations Research, 61, pp 143-164. doi:10.1007/BF02098286  (what is a doi? A doi (Document Object Identifier) is a unique identifier for journal papers. This provides direct access to the location where the original article is published using the URL http://dx.doi/org/xxxx (replacing xxx with the doi))
    Show Abstract
    Abstract: Although most real-world vehicle routing problems are dynamic, the traditional methodological arsenal for this class of problems has been based on adaptations of static algorithms. Still, some important new methodological approaches have recently emerged. In addition, computer-based technologies such as electronic data interchange (EDI), geographic information systems (GIS), global positioning systems (GPS), and intelligent vehicle-highway systems (IVHS) have significantly enhanced the possibilities for efficient dynamic routing and have opened interesting directions for new research. This paper examines the main issues in this rapidly growing area, and surveys recent results and other advances. The assessment of possible impact of new technologies and the distinction of dynamic problems vis-à-vis their static counterparts are given emphasis.

  9. Laporte G. (1992) The vehicle routing problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59(3), pp 345-358. doi:10.1016/0377-2217(92)90192-C  (what is a doi? A doi (Document Object Identifier) is a unique identifier for journal papers. This provides direct access to the location where the original article is published using the URL http://dx.doi/org/xxxx (replacing xxx with the doi))
    Show Abstract
    Abstract: In this paper, some of the main known results relative to the Vehicle Routing Problem are surveyed. The paper is organized as follows: (1) definition; (2) exact algorithms; (3) heuristic algorithms; (4) conclusion.

  10. Solomon M.M. and Jacques Desrosiers J. (1988) Survey Paper - Time Window Constrained Routing and Scheduling Problems. Transportation Science, 22(1), pp 1-13. doi:10.1287/trsc.22.1.1  (what is a doi? A doi (Document Object Identifier) is a unique identifier for journal papers. This provides direct access to the location where the original article is published using the URL http://dx.doi/org/xxxx (replacing xxx with the doi))
    Show Abstract
    Abstract: We have witnessed recently the development of a fast growing body of research focused on vehicle routing and scheduling problem structures with time window constraints. It is the aim of this paper to survey the significant advances made for the following classes of routing problems with time windows: the single and multiple traveling salesman problem, the shortest path problem, the minimum spanning tree problem, the generic vehicle routing problem, the pickup and delivery problem including the dial-a-ride problem, the multiperiod vehicle routing problem and the shoreline problem. Having surveyed the state-of-the-art in this area, we then offer some perspectives on future research.

Conference Papers

  1. Wang F., Tao Y. and Shi N. (2009) A Survey on Vehicle Routing Problem with Loading Constraints, in 2009 International Joint Conference on Computational Sciences and Optimization (CSO 2009), vol. 2, pp.602-606. doi:110.1109/CSO.2009.127  (what is a doi? A doi (Document Object Identifier) is a unique identifier for journal papers. This provides direct access to the location where the original article is published using the URL http://dx.doi/org/xxxx (replacing xxx with the doi))
    Show Abstract
    Abstract: In the classical Vehicle Routing Problem (VRP), a fleet of vehicles is available to serve a set of customers with known demand. Each customer is visited by exactly one vehicle as well as the objective is to minimize the total distance or the total charge incurred. Recent years have seen increased attention on VRP integrated with additional loading constraints, known as 2L-CVRP or 3L-CVRP. In this paper we present a survey of the state-of-the-art on 2L-CVRP/3L-CVRP.

    Books

    There are a number of books, which we have listed on the Getting Started page, which contain survey material. The books are:

    1. Toth P. and Vigo D. (eds) (2002) The Vehicle Routing Problem. Siam Monographs on Discrete Mathematics and Applications
    2. Golden B., Raghaven S. and Wasil E. (eds) (2008) The Vehicle Routing Problem: Latest Advances and Challenges. Springer. doi:10.1007/978-0-387-77778-8  (what is a doi? A doi (Document Object Identifier) is a unique identifier for scientific publications. This provides direct access to the location where the original article is published using the URL http://dx.doi/org/xxxx (replacing xxx with the doi))

    More details about the contant of these books can be seen in the books section of the Getting Started page.

We hope you found this page useful and we welcome your feedback. If you have any comments, please email us at admin@researchandpractise.com.

If you would like to be informed when changes are made to these pages please join our mailing list.