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: Getting Started

If you are new to vehicle routing and don't really know where to start, then this page is for you. We have tried to highlight some of the resources that will be of interest to those new to the area; whether you are an industrialist, a researcher or just have a general interest in vehicle routing. We have split this page into various sections. It is likely that you will draw from a number of them.

Don't forget to also look at other areas of this web site as there is a lot of information here.

If you know of a good resource for those new to vehicle routing, please let us know (email: admin@researchandpractise.com) so that we can can consider including it.

Show All Abstracts Hide All Abstracts

Scientific Papers (reverse chronological order)

The following papers are those that we believe provide good starting points for those new to the area.

  1. Yeun L.C., Ismail W.R., Omar K. and Zirour M. (2008) Vehicle Routing Problem: Models and Solutions. Journal of Quality Measurement and Analysis, 4(1), pp 205-218.

    This paper can be downloaded from here.
    Show Abstract
    Abstract: The Vehicle Routing Problem (VRP) is a well known problem in operational research where customers of known demands are supplied by one or several depots. The objective is to find a set of delivery routes satisfying some requirements or constraints and giving minimal total cost. The VRP has drawn enormous interests from many researchers during the last decades because of its vital role in planning of distribution systems and logistics in many sectors such as garbage collection, mail delivery, snow ploughing and task sequencing. The VRP is divided into many types. The important problems are VRP with Time Windows, VRP with Pick-Up and Delivery and Capacitated VRP. Recently many exact methods have been used to solve the VRP such as exact algorithms based on linear programming techniques and guided local search. Besides that, heuristic techniques have received wide interests in researchers’ effort to solve large scale VRPs. Among the recently applied heuristic techniques are genetic algorithm, evolution strategies and neural networks.

  2. Laporte G. (2007) What you should know about the vehicle routing problem. Naval Research Logistics, 54(8), pp 811-819. doi:10.1002/nav.20261  (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 Vehicle Routing Problem (VRP), the aim is to design a set of m minimum cost vehicle routes through n customer locations, so that each route starts and ends at a common location and some side constraints are satisfied. Common applications arise in newspaper and food delivery, and in milk collection. This article summarizes the main known results for the classical VRP in which only vehicle capacity constraints are present. The article is structured around three main headings: exact algorithms, classical heuristics, and metaheuristics

  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. (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.

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

Web Articles

The following are links are to articles that are available on the web.

  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 has been made available online).

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

  4. Keep on Trucking. This article is a feature column from the Monthly Essays on Methematical Topics. It provides a very nice introduction to Vehicle Routing, provides some background and also gives a nice description of the Clarke-Wright heuristic.

Web Pages

  1. Networks and Vehicle Routing.
  2. The VRP Web.
  3. If you know of any other web pages that would be useful to those new to vehicle routing, please let us know (email: admin@researchandpractise.com).

Books (reverse chronological order)

  1. Bruce Golden, S. Raghaven and Edward Wasil have edited an excellent book called The Vehicle Routing Problem: Latest Advances and New Challenges. The full citation is:

    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))



    Part I of the book consists of 9 chapters which are collected under the heading of Overviews and Surveys. The chapters in this book are as follows:



    1. Baldacci R., Battarra M. and Vigo D. Routing a Heterogeneous Fleet of Vehicles, pp 3-27. doi:10.1007/978-0-387-77778-8_1  (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))
      Show Abstract
      Abstract: In the well-known Vehicle Routing Problem (VRP) a set of identical vehicles, based at a central depot, is to be optimally routed to supply customers with known demands subject to vehicle capacity constraints.
      An important variant of the VRP arises when a fleet of vehicles characterized by different capacities and costs is available for distribution activities. The problem is known as the Mixed Fleet VRP or as the Heterogeneous Fleet VRP.
      This chapter gives an overview of approaches from the literature to solve heterogeneous VRP’s. In particular, we classify the different variants described in the literature and, as no exact algorithm has been presented for any variants of heterogeneous VRP, we review the lower bounds and the heuristic algorithms proposed. Computational results, comparing the performance of the different heuristic algorithms on benchmark instances, are also discussed.
    2. Wøhlk S. A Decade of Capacitated Arc Routing, pp 29-48. doi:10.1007/978-0-387-77778-8_2  (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))
      Show Abstract
      Abstract: Arc Routing is the arc counterpart to node routing in the sense that focus regarding service and resource constraints are on the arcs and not on the nodes. The key problem within this area is the Capacitated Arc Routing Problem (CARP), which is the arc routing counterpart to the vehicle routing problem. During the last decade, arc routing has been a relatively active research area with respect to lower bounding procedures, solution approaches and modelling. Furthermore, several interesting variations of the problem have been studies. We survey the latest research within the area of arc routing focusing mainly on the CARP and its variants.
    3. Bertazzi L., Savelsbergh M. and Speranza M. G. Inventory Routing, pp 49-72. doi:10.1007/978-0-387-77778-8_3  (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))
      Show Abstract
      Abstract: In this chapter, we introduce inventory routing problems. Inventory routing problems are among the more important and more challenging extensions of vehicle routing problems, in which inventory control and routing decisions have to be made simultaneously. The objective is to determine distribution policies that minimize the total cost, i.e., the sum of inventory holding and transportation costs, while avoiding stock-outs and respecting storage capacity limitations. All inventory routing problems have some common characteristics, but they may also have a number of significantly different characteristics. As a result, a variety of solution approaches has been developed. We discuss the various characteristics of inventory routing problems in order to create an understanding of and instill an appreciation for the complexities of inventory routing problems.
    4. Francis P. M., Smilowitz K. R. and Tzur M. The Period Vehicle Routing Problem and its Extension, pp 73-102. doi:10.1007/978-0-387-77778-8_4  (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))
      Show Abstract
      Abstract: This chapter presents and overview of the Period Vehicle Routing Problem, a generalization of the classic vehicle routing problem in which driver routes are constructed over a period of time. We survey the evolution of the PVRP and present a synopsis of modelling and solution methods, including classical heuristics, metaheuristics, and mathematical programming based methods. We review three important variants of the problem: the PVRP with Time Windows, the Multi-Depot PVRP, and the PVRP with Service Choice. We present case studies and highlight related implementation issues, including metrics that quantify the operational complexity of implementing periodic delivery routes. Finally, we discuss potential directions for future work in the area.
    5. Archetti C. and Speranza M. G. The Split Delivery Vehicle Routing Problem: A Survey, pp 103-122. doi:10.1007/978-0-387-77778-8_5  (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))
      Show Abstract
      Abstract: In the classical Vehicle Routing Problem (VRP) a fleet of capacitated vehicles is available to serve a set of customers with known demand. Each customer is required to be visited by exactly one vehicle and then objective is to minimize the total distance travelled. In the Split Delivery Vehicle Routing Problem (SDVRP) the restriction that each customer has to be visited exactly once is removed, i.e., split deliveries are allowed. In this chapter we present a survey of the state-of-the-art on the SDVRP.
    6. Campbell A. M. and Thomas B. W. Challenges and Advances in A Priori Routing, pp 123-142. doi:10.1007/978-0-387-77778-8_6  (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))
      Show Abstract
      Abstract: As a priori route is a route which specifies an ordering of all possible customers that a particular driver may need to visit. The driver may then skip those customers on the route who do not receive a delivery. Despite the prevalence of a priori routing, construction of these routes still presents considerable challenges. Exact methods are limited to small problem sizes, and even heuristic methods are intractable in the face of real-world-sized instances. In this chapter, we will review some of the ideas that have emerged in the recent years to help solve these larger instances. We focus on the probabilistic travelling salesman problem and the recently introduced probabilistic travelling salesman problem with deadlines and discuss how objective-function approximations can reduce computation time without significantly impacting solution quality. We will also present several open research questions in a priori routing.
    7. Gendreau M., Potvin J-Y., Braysy O., Hasle G. and Løkketangen A. Metaheuristics for the Vehicle Routing Problem and its Extensions: A Categorized Bibliography, pp 143-169. doi:10.1007/978-0-387-77778-8_7  (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))
      Show Abstract
      Abstract: We provide a categorized bibliography of metaheuristics for solving the vehicle routing problem and its extensions. The categories are based on various types of metaheuristics and vehicle routing problems.
    8. Crainic T G.. Parallel Solution Methods for Vehicle Routing Problems, pp 172-198. doi:10.1007/978-0-387-77778-8_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))
      Show Abstract
      Abstract: Parallel solution methods contribute to efficiently address large and complex combinatorial optimization problems, vehicle routing problems in particular. Parallel exact and heuristic methods for VRP variants are increasingly being proposed, and the pace seems to increase in recent years. “New” strategies have been proposed and many of the best known solutions to classical formulations have thus been obtained. This chapter describes and discusses then main strategies used to parallelize exact and metaheuristic solution methods for vehicle routing problems. It also provides an up-to-date survey of contributions to this rapidly evolving field and points to a number of promising research directions.
    9. Larsen A., Madsen O.B.G. and Solomon M.M. Recent Developments in Dynamic Vehicle Routing Systems, pp 199-218. doi:10.1007/978-0-387-77778-8_9  (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))
      Show Abstract
      Abstract: This chapter examines the evolution of research on dynamic vehicle routing problems (DVRP). We define the DVRP and show how it is different from the traditional static vehicle routing problem. We then illustrate the technological environment required. Next, we discuss important characteristics of the problem, including the degree of dynamism, elements relevant for the system objective, and evaluation methods for the performance of algorithms. The chapter then summarizes research prior to 2000 and focuses on developments from 2000 to present. Finally, we offer our conclusions and suggest directions for future research.

    Part II of the book (New Directions on Modeling and Algorithms) has 11 chapters.



    1. Jaillet P. and Wagner M. R Online Vehicle Routing Problems: A Survey, pp 221-237. doi:10.1007/978-0-387-77778-8_10  (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))
      Show Abstract
      Abstract: We consider online Vehicle Routing Problems (VRP’s). The problems are online because the problem instance is revealed incrementally. After providing motivations for the consideration of such online problems, we first give a detailed summary of the most relevant research in the area of online VRP’s. We then consider the online Travelling Salesman Problem (TSP) with precedence and capacity constraints and give an online algorithm with a competitive ratio of at most 2. We also consider an online version of the TSP with m salesmen and we give an online algorithm that has a competitive ratio of 2, a result that is best possible. We also study polynomial-time algorithms for these problems. Finally, we introduce the notion of disclosure dates, a form of advanced notice which allows for more realistic competitive ratios.
    2. Chandran B. and Raghavan S. Modeling and Solving the Capacitated Vehicle Routing Problem on Trees, pp 239-261. doi:10.1007/978-0-387-77778-8_11  (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))
      Show Abstract
      Abstract: Capacitated vehicle routing problems (CVRP’s) form the core of logistics planning and are hence of great practical and theoretical interest. This chapter considers the CVRP on trees (TCVRP), a problem that often naturally arises in railway, river and rural road networks. Our objective is build high-quality models that exploit the tree structure of the problem that can also be easily implemented within the framework of a modelling language (a feature desired by practitioners) like AMPL, GAMS or OPL. We present two new integer programming models for the TCVRP that explicitly take advantage of the tree structure of the graph. The two models are implemented using the AMPL model building language, and compared along several metrics – computation time, quality of the linear programming relaxation, and scalability – to examine their relative strengths.
    3. Wang X., Golden B.L. and Wasil E.A. Using a Genetic Algorithm to Solve the Generalized Orienting Problem, pp 263-274. doi:10.1007/978-0-387-77778-8_12  (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))
      Show Abstract
      Abstract: In this chapter, we use genetic algorithms (GA’s) to solve the generalized orienteering problem (GOP). In the orienteering problem (OP), we are given a transportation network in which a start point and an end point are specified, and other points have associated scores. Given a fixed amount of time, the goal is to determine a path from start to end through a subset of the other locations in order to maximize the total path score. In the GOP, each point has a score with respect to a number of attributes (e.g.; natural beauty, historical significance, cultural and educational attractions and business opportunities) and the overall objective function is non-linear. The GOP is more difficult than the OP, which it itself NP-hard. An effective heuristic using artificial neural networks (ANN’s) however has been designed to solve the GOP. In this chapter, we show that a straightforward GA can yield comparable results.
    4. Toth P. and Tramontani A. An Integer Linear Programming Local Search for Capacitated Vehicle Routing Problems, pp 275-295. doi:10.1007/978-0-387-77778-8_13  (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))
      Show Abstract
      Abstract: In this chapter we address the classical Vehicle Routing Problem (VRP), where (at most) k minimum-cost routes through a central depot are constructed to cover all customers while satisfying, for each route, both a capacity and a total distance travelled limit. We present a Local Search algorithm for VRP, based on the exploration of an exponential neighbourhood by solving an Integer Linear Programming (ILP) problem. Our starting point is the following refinement heuristic procedure purposed by De Franceschi et al.: given an initial solution to be possibly improved, (a) select several customers from the current solution , and build the restricted solution obtained from the current one by extracting (i.e.; short cutting) the selected customers.; (b) reallocate the extracted customers to the restricted solution by solving an ILP problem, in the attempt of finding a new improved solution. We present a generalization of the neighbourhood proposed in this method, and investigate the Column Generation Problem associated with the Linear Programming (LP) relaxation of the ILP formulation corresponding to the neighbourhood. In particular, we propose a two-phase approach for the neighbourhood exploration, which first reduces the neighbourhood size through a simple heuristic criterion, and then explores the reduced neighbourhood by solving the corresponding ILP formulation through the (heuristic) solution of the Column Generation Problem associated with its LP relaxation. We report computational results on capacitated VRP instances from the literature (with/without distance constraints), which are usually used as benchmark instances for the considered problem. In several cases, the proposed algorithm is able to find the new best known solution in the literature.
    5. Pessoa A., Poggi de Aragão M. and Uchoa E. Robust Branch-Cut-Price Algorithms for Vehicle Routing Problems, pp 297-325. doi:10.1007/978-0-387-77778-8_14  (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))
      Show Abstract
      Abstract: This chapter presents techniques for constructing robust Branch-Cut and-Price algorithms on a number of Vehicle Routing Problem variants. The word ‘robust’ stresses the effort of controlling the worst-cast complexity of the pricing subproblem, keeping it pseudo-polynomial. Besides summarizing older research on the topic, some promising new lines of investigation are also presented, specially the development of new families of cuts over large extended formulations. Computational experiments over benchmark instances from ACVRP, COVRP, CVRP and HFVRP variants are provided.
    6. Cordeau J-F., Laporte G. and Ropke S. Recent Models and Algorithms for One-to-One Pickup and Delivery Problems, pp 327-357. doi:10.1007/978-0-387-77778-8_15  (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))
      Show Abstract
      Abstract: In one-to-one Pickup and Delivery Problems (PDPs), the aim is to design a set of least cost vehicle routes starting and ending at a common depot in order to satisfy a set of pickup and delivery requests between location pairs, subject to side constraints. Each request originates at one location and is destines for one other location. These requests apply to the transportation of goods or people, in which case the problem is often called the dial-a-ride problem. In recent years, there have been several significant developments in the area of exact and heuristic algorithms for PDP’s. The purpose of this chapter is to report on these developments. It contains two main sections devoted to single vehicle and multi-vehicle problems, respectively. Each section is subdivided into two parts, one on exact algorithms and one on heuristics.
    7. Gribkovskaia I. and Laporte G. One-to-Many-to-One Single Vehicle Pickup and Delivery Problems, pp 359-377. doi:10.1007/978-0-387-77778-8_16  (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))
      Show Abstract
      Abstract: In One-to-Many-to-One Single Vehicle Pickup and Delivery Problems a vehicle based at the depot must make deliveries and pickups at customers locations before returning to the depot. Several variants can be defined according to the demand structures and sequencing rules imposed on pickups and deliveries. In recent years there has been an increased interest in this family of problems. New formulations and efficient heuristics capable of yielding generation solutions (unrestricted in shape) have been proposed. In addition, some new and interesting extensions have been analyzed, including problems with selective pickups and problems with capacitated customers. The purpose of this chapter is to review these developments.
    8. Agatz N, Campbell A.M., Fleischmann M. and Martin Savelsbergh Challenges and Opportunities in Attended Home Delivery, pp 379-396. doi:10.1007/978-0-387-77778-8_17  (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))
      Show Abstract
      Abstract: In this chapter, we focus on home delivery, and, more specifically, on attended home delivery, where the consumer must be present for the delivery. To provide a high service level and to avoid delivery failures as much as possible, it is customary in attended home delivery services for the company to offer the customer a choice of narrow delivery time slots. The objective of this chapter is to highlight and illustrate issues arising in attended home delivery related to these time slots and to present and discuss promising approaches for addressing some of them. We will use Peapod, one of the more successful e-grocers, as an illustrative example.
    9. Petersen B., Pisinger D. and Spoorendonk S. Chvátal-Gomory Rank-1 Cuts Used in Dantzig-Wolfe Decomposition of the Vehicle Routing Problem with Time Windows, pp 397-420. doi:10.1007/978-0-387-77778-8_18  (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))
      Show Abstract
      Abstract: This chapter shows how Chvátal-Gomory (CG) rank-1 cuts can be used in a Branch-and-Cut-and –Price algorithm for the Vehicle Routing Problem with Time Windows (VRPTW). Using Dantzig-Wolfe decomposition we split the problem into a Sat Partitioning Problem as master problem and an Elementary Shortest Path Problem with Resource Constraints as pricing problem. To strengthen the formulation we derive general CG rank-1 cuts based on the master problem formulation. Adding these cuts to the master problem means that an additional resource is added to the pricing problem for each cut. This increases the complexity of the label algorithm used to solve the pricing problem since normal dominance tests become weak when many resources are present and hence most labels are incomparable. To over-come this problem we present a number of improved dominance tests exploiting the step-like structure of the objective function of the pricing problem. Computational experiments are reported on the Solomon test instances showing that the addition of CG rank-1 cuts improves the lower bounds significantly and makes it possible to solve a majority of the instances in the root node of the branch-and-bound tree. This indicates that CG rank-1 cuts may be essential for solving future large-scale VRPTW problems where we cannot expect that the branching process will close the gap between lower and upper bounds in reasonable time.
    10. Hempsch C. and Irnich S. Vehicle Routing Problems with Inter-Tour Resource Constraints, pp 421-444. doi:10.1007/978-0-387-77778-8_19  (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))
      Show Abstract
      Abstract: Inter-tour constraints are constraints in a vehicle-routing problem (VRP) on globally limited resources that different vehicles compete for. Real-world examples are a limited number of ‘long’ tours, where long is defined with respect to the travelled distance, the number of docking stations or processing capacities for incoming goods at the destination depot can be modelled by means of inter-tour resource constraints based on the giant-tour representation and resource constrained paths. Furthermore, solving the model by efficient local search techniques is addressed: Tailored pre-processing procedures and feasibility tests are combined into local-search algorithms, that are attractive from a worst-case point of view and are superior to traditional search techniques in the average case. In the end, the chapter provides results for some new types of studies where VRP’s with time-varying processing capacities are analyzed.
    11. Jozefowiez N., Semet F. and Talbi E. From Single-Objective to Multi-Objective Vehicle Routing Problems: Motivations, Case Studies, and Methods, pp 445-471. doi:10.1007/978-0-387-77778-8_20  (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))
      Show Abstract
      Abstract: Multi-objective optimisation knows a fast growing interest for both academic researchers and real life problems. An important domain is the one of vehicle routing problems. In this chapter, we present the possible motivations for applying multi-objective optimization on vehicle routing problems and the potential uses and benefits of doing so. To illustrate this fact, we also describe two problems, namely the vehicle routing problem with route balancing and the bi-objective covering tour problem. We also propose a two-phased approach based on the combination of a multi-objective evolutionary algorithm and single-objective techniques that respectively provide diversification and intensification for the search in the objective space. Examples of implementation of this method are provided on the two problems.

    Part III of the book (Practical Appplications) has 5 chapters.



    1. Wong R.T. Vehicle Routing for Small Package Delivery and Pickup Services, pp 475-485. doi:10.1007/978-0-387-77778-8_21  (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))
      Show Abstract
      Abstract: Small package shipping is a vital component of national and international transportation. This chapter gives an overview of such services by discussing the operations of a ‘typical’ service day. We compare and contrast the characteristics of the routing problem encountered in small package shipping with the classical vehicle routing problem. The discussion of these routing issues also leads us to describe several new variants and offshoots of the classical vehicle routing problem that may be of interest to researchers.
    2. Shuttleworth R., Golden B.L., Smith S. and Wasil E. Advances in Meter Reading: Heuristic Solution of the Close Enough Traveling Salesman Problem over a Street Network, pp 487-501. doi:10.1007/978-0-387-77778-8_22  (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))
      Show Abstract
      Abstract: The use of automated meter reading (AMR) with radio frequency identification (RFID) technology allows utility companies to read utility meters from a distance. Therefore, a utility company does not need to visit every customer. Rather, it must get within a certain radius of the customer in order to read the customers meter. This changes the problem for a meter reader from a travelling salesman problem (TSP) to a close enough TSP (CETSP) over a realistic street network. In this project, we teamed with RouteSmart Technologies, Inc., a leading logistics solution provider, to propose and implement several heuristic approaches that look promising for this new problem class. In particular, the solutions generated from the proposed heuristics are compared to solutions from a rural postman problem solver (where every customer must be visited) and the improvements are documented.
    3. Bostel N., Dejax P., Guez P. and Tricoire F. Multiperiod Planning and Routing on a Rolling Horizon for Field Force Optimization Logistics, pp 503-525. doi:10.1007/978-0-387-77778-8_23  (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))
      Show Abstract
      Abstract: We address the problem of the planning and routing of technician visits to customers in the field, for maintenance or service logistics activities undertaken by utilities. The plans must be designed over a multi period, rolling horizon and updated daily. We have developed a memetic algorithm and a column generation/branch and bound heuristic in order to optimize an initial plan over a static horizon. We have then adapted our procedures to cope with a rolling horizon context, when a new plan has to be determined after the execution of each first daily period of the previous plan. We have tested our procedures on realistic data from the water distribution sector, and obtained good solutions in a reasonable amount of time. We show in particular the advantage of reutilization of partial solutions from the previous plan for the optimization of each new plan. Directions for further research are then indicated.
    4. Doerner K.F. and Hartl R.F. Health Care Logistics, Emergency Preparedness, and Disaster Relief: New Challenges for Routing Problems with a Focus on the Austrian Situation, pp 527-550. doi:10.1007/978-0-387-77778-8_24  (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))
      Show Abstract
      Abstract: This chapter discusses several transportation problems arising in the field of health care logistics, emergency preparedness and disaster relief. The underlying basic problems are vehicle routing, dial-a-ride, warehouse location routing, covering tour and inventory routing problems. However several additional constraints and real world characteristics enrich the basic problems. The problems are introduced and discussed in the context of their applications with a focus on the Austrian situation.
    5. Stahlbock R. and Voß S. Vehicle Routing Problems and Container Terminal Operations - An Update of Research, pp 551-589. doi:10.1007/978-0-387-77778-8_25  (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))
      Show Abstract
      Abstract: Containers came into the market for international conveyance of sea freight almost five decades ago. The breakthrough was achieved with large investments in specially designed ships, adapted seaport terminals with suitable equipment, and availability of containers. Today over 60 per cent of the worlds deep sea-general cargo is transported in containers and some routes are even containerized up to 100 per cent. Seaport container terminals face a high demand for advanced optimization methods. A crucial competitive advantage is the rapid turnover of the containers, which corresponds to an efficient handling of containers as well as to a decrease of the costs of the transhipment processes. One of the key concerns in this respect refers to various types of equipment at container terminals devoted to the routing of containers to achieve high productivity. For instance, a variety of vehicles is used for the horizontal transport at the quayside and at the landside.
      In this chapter we provide a comprehensive survey on routing problems that have arisen in the container terminal domain, such as how to route automated guided vehicles, new technologies such as double rail mounted gantry cranes etc. This opens up new challenges for the field. The chapter strives to summarize the research results for the vehicle routing problem and its variants regarding container terminals.
  2. Paolo Toth and Daniele Vigo edited an excellent book called The Vehicle Routing Problem. The full citation is:

    Toth P. and Vigo D. (eds) (2002) The Vehicle Routing Problem. Siam Monographs on Discrete Mathematics and Applications



    For those new to the area, chapter 1 is likely to be the most informative as it provides an overview of vehicle routing problems.

    You can also view most of chapter 1 (as well as a lot of other parts of the book) online through Google books.

    Amazon also has some further details.

    For completeness, here is a list of the chapters in the book. The chapters do not have abstracts, which is why we cannot provide them.

    1. Toth P. and Vigo D. An Overview of Vehicle Routing Problems, pp 1-26
    2. Toth P. and Vigo D. Branch-and-Bound Algorithms for the Capacitated VRP, pp 29-51
    3. Naddef D. and Rinaldi G. Branch-and-Cut Algorithms for the Capacitated VRP, pp 53-84
    4. Bramel J. and Simchi-Levi D. Set-Covering-Based Algorithms for the Capacitated VRP, pp 85-108
    5. Laporte G. and Semet F. Classical Heuristics for the Capacitated VRP, pp 109-128
    6. Gendreau M., Laporte G. and Potvin J-Y. Metaheuristics for the Capacitated VRP, pp 129-154
    7. Cordeau J-F., Desaulniers G., Desrosiers J., Solomon M.M. and Soumis F. VRP with Time Windows, pp 157-193
    8. Toth P. and Vigo D. VRP with Backhauls, pp 195-224
    9. Desaulniers G., Desrosiers J., Erdmann A. Solomon M.M. and Soumis F. VRP with Pickup and Delivery, pp 225-242
    10. Golden B.L., Assad A.A. and Wasil E.A. Routing Vehicles in the Real World: Aplications in the Solid Waste, Beverage, Food, Diary, and Newspaper Industries, pp 245-286
    11. Sniezek J., Bodin L., Levy L. and Ball M. Capacitated Arc Routing Problem with Vehicle-Site Dependencies: The Philadelphia Experience, pp 287-308
    12. Campbell A.M., Clarke L.W. and Savelsbergh M.W.P. Inventory Routing in Practice, pp 309-330
    13. Hadjiconstantinou E. and Roberts D. Routing Under Uncertainty: An Application in the Scheduling of Field Engineers, pp 331-352
    14. Baker E.K. Evolution of Microcomputer-Based Vehicle Routing Software: Case Studies in the United States, pp 353-361

    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.