The Vehicle Routing Problem: Latest Advances and New Challenges

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

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 modeling. Furthermore, several interesting variations of the problem have been studied. We survey the latest research within the area of arc routing focusing mainly on the CARP and its variants.

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.

This chapter presents an 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 modeling 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.

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 the objective is to minimize the total distance traveled. 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.

An 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 recent years to help solve these larger instances. We focus on the probabilistic traveling salesman problem and the recently introduced probabilistic traveling 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.

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.

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

This chapter examines the evolution of research on dynamic vehicle routing problems (DVRP). We de?ne the DVRP and show how it is di?erent 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 o?er our conclusions and suggest directions for future research.

We consider online Vehicle Routing Problems (VRPs). 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 VRPs. We then consider the online Traveling 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 realisticcompetitive ratios.

Capacitated vehicle routing problems (CVRPs) 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 to build high-quality models that exploit the tree structure of the problem that can also be easily implemented within the framework of a modeling 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.

In this chapter, we use genetic algorithms (GAs) 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 nonlinear. The GOP is more difficult than the OP, which is itself NP-hard. An effective heuristic using artificial neural networks (ANNs), however, has been designed to solve the GOP. In this chapter, we show that a straightforward GA can yield comparable results.

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-traveled limit. We present a Local Search algorithm for VRP, based on the exploration of an exponential neighborhood by solving an Integer Linear Programming (ILP) problem. Our starting point is the following refinement heuristic procedure proposed 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 neighborhood proposed in this method, and investigate the Column Generation Problem associated with the Linear Programming (LP) relaxation of the ILP formulation corresponding to the neighborhood. In particular, we propose a two-phase approach for the neighborhood exploration, which first reduces the neighborhood size through a simple heuristic criterion, and then explores the reduced neighborhood 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.

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

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

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.

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

Multi-objective optimization knows a fast growing interest for both academic researches 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.

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.

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 customer’s meter. This changes the problem for a meter reader from a traveling 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.

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

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.

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 % of the world’s deep-sea general cargo is transported in containers and some routes are even containerized up to 100 %. 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 transshipment 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.