Abstract
The vehicle routing problem requires mostly meta-heuristics to find approximate solutions. Congestion makes it hard for planners to find good routes because travel times are uncertain. The problem is handled by building scenarios with a range of possible travel times to represent the uncertainty. The main goal is to find a robust solution, which performs “well” in bad scenarios. The experiments show that robust results are obtained in a computationally reasonable time, which means that the concept can be used by practitioners. Most applications are commercial, but also social applications exist. An earthquake or a flood might lead to road disruptions. Higher traffic delays appear due to lower speed on flooded roads or due to time spent on finding alternative routes. Routing like evacuation of wounded or delivery of food is hardly studied. The work is inspired by the 2011 flooding in Thailand.
TopIntroduction
Vehicle Routing Problems (VRPs) are a class of combinatorial problems which are challenging to the scientific society of operations researchers. On the one hand, this popularity is due to the high level of difficulty of finding optimal solutions to the problems of a rather large size. On the other hand, the popularity relates to the fact that this problem appears in many practical situations and mostly in a variant which is even much harder than the classical VRP.
From a computational point of view, the field of Operations Research, during decades, has spent an enormous effort on the Traveling Salesman Problem (TSP). The importance that the TSP got from the scientific community deals with the wealth of applications, but even more by the fact that it is a typical problem in its genre: combinatorial optimization. While the problem setting of a TSP is easy to understand in terms of minimizing a total distance with some constraints, the problem has not been solved satisfying some formal standards of efficiency. A selection of the abundance of literature on the TSP, its history, its variants and its solution methods has been published in the classical book, edited by Lawler, Lenstra, Rinnooy Kan, and Shmoys (1985).
The last chapter in that book is dedicated to the Vehicle Routing Problem (Christofides, 1985). The vehicle routing is of higher complexity than the TSP as it concerns a (previously unknown) number of vehicles (and not just one salesman) and it takes capacity of the vehicles into consideration. That chapter opens the door to researchers in the field of combinatorial optimization to take up the challenge to look for efficient solution methods for a problem which is much more complex than the TSP.
The basic version of the VRP is called the capacitated VRP. All customers relate to deliveries, have fixed demands, known in advance and cannot be split. The vehicles are identical, leave from and return to a single depot and only the capacity is considered as a vehicle-related constraint. The objective is to minimize the total cost (expressed in terms of total distance, or total travel time, or total number of vehicles). Due to its interest from the transport and logistics industry, the VRP needed to be enriched with more features from the real world.
While each application might introduce its case-specific constraints leading to multiple variants on the VRP, a number of classical variants appear abundant in literature. Four classical extensions are formulated in Toth and Vigo (2002), which relate to the following practical aspects: maximal route-length (distance-constrained VRP), time windows (VRP with time windows), separated line-haul and backhaul customers (VRP with backhauls), and mixed services (VRP with pick-up and delivery).
In the distance-constrained VRP the capacity constraint of a route is replaced by (or combined with) a maximum length or time of the route. In the VRP with time windows a time interval (called a time window), defined by a lower and an upper bound, and a service time is associated with each customer. The service at the customer should start within the time window and the vehicle stops at the customer’s site for a time period, called the service time. In the VRP with backhauls the set of customers is divided into two subsets: line-haul customers and backhaul customers. Line-haul customers require a quantity of product to be delivered and are served first, while backhaul customers require a quantity of product to be picked up and are served after the line-haul customers in the route. In the VRP with pickup and delivery each customer is associated with a quantity of product to be delivered and a quantity of product to be picked up (operated in that sequence).
Before moving into solution methods for these variants, a few interesting review papers should be mentioned to the interested reader. Laporte (2009) reports on fifty years research on VRP from a historical perspective. Next to Toth and Vigo (2002b) mentioned earlier, full books on the topic and its recent advances include Cordeau, Laporte, Savelsbergh, and Vigo (2007) and Golden, Raghavan, and Wasil (2008).
Key Terms in this Chapter
Disaster Transport Management: Includes organized activities to address problems created by unusual event, like flooding, fires, hurricanes, and crashes. It may relate to vehicle problems related to people (for example evacuations, search and rescue operations), but also to goods like delivery of emergency supplies (water, food, medical care) and of transportation infrastructure repair.
Travel Time Uncertainty: Relates mostly to the mechanism through which causes the travel time not to be a deterministic value (for example congestion or road disruption). For goods transport, the uncertainty is like a constraint for dispatchers, which in passenger traffic it relates to choices of routes or of modes of transport.
Time Window: An interval in time during which an activity can or must take place. In the case of routing problems with delivery of goods mostly it relates to the event of start of delivery. In some cases however the end of the activity also needs to fall within the interval.
Robust Solution Methods: Optimization methods in which a certain measure of robustness is looked for against uncertainty (for example in travel time). The uncertainty is represented as deterministic variability of the parameters of the problem (for example lower and upper bound of an interval of travel time of a link in the traffic network).
Insertion Heuristic: A popular method for solving a variety of scheduling or routing problems. It can serve as method for finding quickly a feasible solution, without a guarantee of good quality, or as a feasible starting solution for improvement methods, like meta-heuristics. In vehicle routing it constructs the solution by repeatedly inserting an unrouted customer into a partially constructed route or as a first customer in an additional route.
Local Search Descent (LSD) Method: A method to find a local minimum or maximum of a function. With a specified continuous function the gradient descent method is an effective method. In a discrete environment, like in combinatorial optimization, the idea to perturb a current solution (looking for neighboring solutions) and to look in an iterated way for improving solutions until a local minimum is found.
Fleet Management: The management of the transportation fleet of a logistics service provider. It includes vehicles of different modes of transport like road, rail, inland waterway and air transport. But mostly it relates to decision in road transport in which vehicles of different size or with different characteristics are used for planned transport activities (heterogeneous fleet of vehicles).
Vehicle Routing Problem: A combinatorial optimization and integer programming problem looking to service (pick-up or delivery of goods) a number of customers with a predetermined fleet of vehicles.