Vehicle routing problem

Short description: Optimization problem

A figure illustrating the vehicle routing problem

The vehicle routing problem (VRP) is a combinatorial optimization and integer programming problem which asks "What is the optimal set of routes for a fleet of vehicles to traverse in order to deliver to a given set of customers?" It generalises the travelling salesman problem (TSP). It first appeared in a paper by George Dantzig and John Ramser in 1959, in which the first algorithmic approach was written and was applied to petrol deliveries. Often, the context is that of delivering goods located at a central depot to customers who have placed orders for such goods. The objective of the VRP is to minimize the total route cost. In 1964, Clarke and Wright improved on Dantzig and Ramser's approach using an effective greedy algorithm called the savings algorithm.

Determining the optimal solution to VRP is NP-hard, so the size of problems that can be optimally solved using mathematical programming or combinatorial optimization may be limited. Therefore, commercial solvers tend to use heuristics due to the size and frequency of real world VRPs they need to solve.

VRP has many direct applications in industry. Vendors of VRP routing tools often claim that they can offer cost savings of 5%–30%.

Setting up the problem

The VRP concerns the service of a delivery company. How things are delivered from one or more depots which has a given set of home vehicles and operated by a set of drivers who can move on a given road network to a set of customers. It asks for a determination of a set of routes, S, (one route for each vehicle that must start and finish at its own depot) such that all customers' requirements and operational constraints are satisfied and the global transportation cost is minimized. This cost may be monetary, distance or otherwise.

The road network can be described using a graph where the arcs are roads and vertices are junctions between them. The arcs may be directed or undirected due to the possible presence of one way streets or different costs in each direction. Each arc has an associated cost which is generally its length or travel time which may be dependent on vehicle type.

To know the global cost of each route, the travel cost and the travel time between each customer and the depot must be known. To do this our original graph is transformed into one where the vertices are the customers and depot, and the arcs are the roads between them. The cost on each arc is the lowest cost between the two points on the original road network. This is easy to do as shortest path problems are relatively easy to solve. This transforms the sparse original graph into a complete graph. For each pair of vertices i and j, there exists an arc (i,j) of the complete graph whose cost is written as [math]\displaystyle{ C_{ij} }[/math] and is defined to be the cost of shortest path from i to j. The travel time [math]\displaystyle{ t_{ij} }[/math] is the sum of the travel times of the arcs on the shortest path from i to j on the original road graph.

Sometimes it is impossible to satisfy all of a customer's demands and in such cases solvers may reduce some customers' demands or leave some customers unserved. To deal with these situations a priority variable for each customer can be introduced or associated penalties for the partial or lack of service for each customer given

The objective function of a VRP can be very different depending on the particular application of the result but a few of the more common objectives are:

• Minimize the global transportation cost based on the global distance travelled as well as the fixed costs associated with the used vehicles and drivers
• Minimize the number of vehicles needed to serve all customers
• Least variation in travel time and vehicle load
• Minimize penalties for low quality service
• Maximize a collected profit/score.

VRP variants

A map showing the relationship between common VRP subproblems.

Several variations and specializations of the vehicle routing problem exist:

• Vehicle Routing Problem with Profits (VRPP): A maximization problem where it is not mandatory to visit all customers. The aim is to visit once customers maximizing the sum of collected profits while respecting a vehicle time limit. Vehicles are required to start and end at the depot. Among the most known and studied VRPP, we cite:
  • The Team Orienteering Problem (TOP) which is the most studied variant of the VRPP,
  • The Capacitated Team Orienteering Problem (CTOP),
  • The TOP with Time Windows (TOPTW).
• Vehicle Routing Problem with Pickup and Delivery (VRPPD): A number of goods need to be moved from certain pickup locations to other delivery locations. The goal is to find optimal routes for a fleet of vehicles to visit the pickup and drop-off locations.
• Vehicle Routing Problem with LIFO: Similar to the VRPPD, except an additional restriction is placed on the loading of the vehicles: at any delivery location, the item being delivered must be the item most recently picked up. This scheme reduces the loading and unloading times at delivery locations because there is no need to temporarily unload items other than the ones that should be dropped off.
• Vehicle Routing Problem with Time Windows (VRPTW): The delivery locations have time windows within which the deliveries (or visits) must be made.
• Capacitated Vehicle Routing Problem: CVRP or CVRPTW. The vehicles have a limited carrying capacity of the goods that must be delivered.
• Vehicle Routing Problem with Multiple Trips (VRPMT): The vehicles can do more than one route.
• Open Vehicle Routing Problem (OVRP): Vehicles are not required to return to the depot.
• Inventory Routing Problem (IRP): Vehicles are responsible for satisfying the demands in each delivery point
• Multi-Depot Vehicle Routing Problem (MDVRP): Multiple depots exist from which vehicles can start and end.
• Vehicle Routing Problem with Transfers (VRPWT): Goods can be transferred between vehicles at specially designated transfer hubs.
• Electric Vehicle Routing Problem (EVRP): These are special VRP that take as an extra constraint the battery capacity of electric vehicles into account.

Several software vendors have built software products to solve various VRP problems. Numerous articles are available for more detail on their research and results.

Although VRP is related to the Job Shop Scheduling Problem, the two problems are typically solved using different techniques.

Exact solution methods

There are three main different approaches to modelling the VRP

1. Vehicle flow formulations—this uses integer variables associated with each arc that count the number of times that the edge is traversed by a vehicle. It is generally used for basic VRPs. This is good for cases where the solution cost can be expressed as the sum of any costs associated with the arcs. However it can't be used to handle many practical applications.
2. Commodity flow formulations—additional integer variables are associated with the arcs or edges which represent the flow of commodities along the paths travelled by the vehicles. This has only recently been used to find an exact solution.
3. Set partitioning problem—These have an exponential number of binary variables which are each associated with a different feasible circuit. The VRP is then instead formulated as a set partitioning problem which asks what is the collection of circuits with minimum cost that satisfy the VRP constraints. This allows for very general route costs.

Vehicle flow formulations

The formulation of the TSP by Dantzig, Fulkerson and Johnson was extended to create the two index vehicle flow formulations for the VRP

[math]\displaystyle{ \text{min} \sum_{i\in V}\sum_{j \in V}c_{ij}x_{ij} }[/math]

subject to

[math]\displaystyle{ \sum_{i \in V}x_{ij}=1 \quad \forall j \in V\backslash \left \{ 0 \right \} }[/math]

(1)

[math]\displaystyle{ \sum_{j \in V}x_{ij}=1 \quad \forall i \in V\backslash \left \{ 0 \right \} }[/math]

(2)

[math]\displaystyle{ \sum_{i \in {V\backslash \left \{ 0 \right \}}}x_{i0}=K }[/math]

(3)

[math]\displaystyle{ \sum_{j \in {V\backslash \left \{ 0 \right \}}}x_{0j}=K }[/math]

(4)

[math]\displaystyle{ \sum_{i\notin S}\sum_{j\in S} x_{ij}\ge r(S), ~~\forall S \subseteq V\setminus \{0\}, S\neq \emptyset }[/math]

(5)

[math]\displaystyle{ x_{ij}\in \{0,1\} \quad \forall i,j \in V }[/math]

(6)

In this formulation [math]\displaystyle{ c_{ij} }[/math] represents the cost of going from node [math]\displaystyle{ i }[/math] to node [math]\displaystyle{ j }[/math], [math]\displaystyle{ x_{ij} }[/math] is a binary variable that has value [math]\displaystyle{ 1 }[/math] if the arc going from [math]\displaystyle{ i }[/math] to [math]\displaystyle{ j }[/math] is considered as part of the solution and [math]\displaystyle{ 0 }[/math] otherwise, [math]\displaystyle{ K }[/math] is the number of available vehicles and [math]\displaystyle{ r(S) }[/math] corresponds to the minimum number of vehicles needed to serve set [math]\displaystyle{ S }[/math]. We are also assuming that [math]\displaystyle{ 0 }[/math] is the depot node.

Constraints 1 and 2 state that exactly one arc enters and exactly one leaves each vertex associated with a customer, respectively. Constraints 3 and 4 say that the number of vehicles leaving the depot is the same as the number entering. Constraints 5 are the capacity cut constraints, which impose that the routes must be connected and that the demand on each route must not exceed the vehicle capacity. Finally, constraints 6 are the integrality constraints.

One arbitrary constraint among the [math]\displaystyle{ 2|V| }[/math] constraints is actually implied by the remaining [math]\displaystyle{ 2|V|-1 }[/math] ones so it can be removed. Each cut defined by a customer set [math]\displaystyle{ S }[/math] is crossed by a number of arcs not smaller than [math]\displaystyle{ r(S) }[/math](minimum number of vehicles needed to serve set [math]\displaystyle{ S }[/math]).

An alternative formulation may be obtained by transforming the capacity cut constraints into generalised subtour elimination constraints (GSECs).

[math]\displaystyle{ \sum_{i\in S}\sum_{j\in S}x_{ij} \leq |S|-r(S) }[/math]

which imposes that at least [math]\displaystyle{ r(S) }[/math]arcs leave each customer set [math]\displaystyle{ S }[/math].

GCECs and CCCs have an exponential number of constraints so it is practically impossible to solve the linear relaxation. A possible way to solve this is to consider a limited subset of these constraints and add the rest if needed. Identification of the needed constraints is done via a separation procedure. Efficient exact separation methods for such constraints (based on mixed integer programming) have been developed.

A different method again is to use a family of constraints which have a polynomial cardinality which are known as the MTZ constraints, they were first proposed for the TSP and subsequently extended by Christofides, Mingozzi and Toth.

[math]\displaystyle{ u_j-u_i\geq d_j-C(1-x_{ij}) ~~~~~~\forall i,j \in V\backslash\{0\}, i\neq j~~~~\text{s.t. } d_i +d_j \leq C }[/math]

[math]\displaystyle{ 0 \leq u_i \leq C-d_i ~~~~~~\forall i \in V\backslash \{0\} }[/math]

where [math]\displaystyle{ u_i,~i \in V \backslash \{0\} }[/math] is an additional continuous variable which represents the load left in the vehicle after visiting customer [math]\displaystyle{ i }[/math] and [math]\displaystyle{ d_i }[/math] is the demand of customer [math]\displaystyle{ i }[/math]. These impose both the connectivity and the capacity requirements. When [math]\displaystyle{ x_{ij}=0 }[/math] constraint then [math]\displaystyle{ i }[/math] is not binding' since [math]\displaystyle{ u_i\leq C }[/math] and [math]\displaystyle{ u_j\geq d_j }[/math] whereas [math]\displaystyle{ x_{ij} = 1 }[/math] they impose that [math]\displaystyle{ u_j \geq u_i +d_j }[/math].

These have been used extensively to model the basic VRP (CVRP) and the VRPB. However, their power is limited to these simple problems. They can only be used when the cost of the solution can be expressed as the sum of the costs of the arc costs. We cannot also know which vehicle traverses each arc. Hence we cannot use this for more complex models where the cost and or feasibility is dependent on the order of the customers or the vehicles used.

Manual versus automatic optimum routing

There are many methods to solve vehicle routing problems manually. For example, optimum routing is a big efficiency issue for forklifts in large warehouses. Some of the manual methods to decide upon the most efficient route are: Largest gap, S-shape, Aisle-by-aisle, Combined and Combined + While Combined + method is the most complex, thus the hardest to be used by lift truck operators, it is the most efficient routing method. Still the percentage difference between the manual optimum routing method and the real optimum route was on average 13%.

Metaheuristic

Due to the difficulty of solving to optimality large-scale instances of vehicle routing problems, a significant research effort has been dedicated to metaheuristics such as Genetic algorithms, Tabu search, Simulated annealing and Adaptive Large Neighborhood Search (ALNS). Some of the most recent and efficient metaheuristics for vehicle routing problems reach solutions within 0.5% or 1% of the optimum for problem instances counting hundreds or thousands of delivery points. These methods are also more robust in the sense that they can be more easily adapted to deal with a variety of side constraints. As such, the application of metaheuristic techniques is often preferred for large-scale applications with complicating constraints and decision sets.

Classification of solution strategies

Most solutions to the vehicle routing problems can be classified as one of the following approaches:

See also

• Chinese postman problem
• Vehicle rescheduling problem
• Arc routing
• List of graph theory topics

Further reading

• Oliveira, H.C.B.de; Vasconcelos, G.C. (2008). "A hybrid search method for the vehicle routing problem with time windows". Annals of Operations Research 180: 125–144. doi:10.1007/s10479-008-0487-y. 
• Frazzoli, E.; Bullo, F. (2004). "Decentralized algorithms for vehicle routing in a stochastic time-varying environment". 43rd IEEE Conference on Decision and Control, 14-17 Dec. 2004, Nassau, Bahamas. 4. IEEE. doi:10.1109/CDC.2004.1429220. ISBN 0-7803-8682-5. 
• Psaraftis, H.N. (1988). "Dynamic vehicle routing problems". Vehicle Routing: Methods and Studies 16: 223–248. http://www.martrans.org/documents/2008/rst/dvrp%20psaraftis%2088.pdf. 
• Bertsimas, D.J.; Van Ryzin, G. (1991). "A Stochastic and Dynamic Vehicle Routing Problem in the Euclidean Plane". Operations Research 39 (4): 601–615. doi:10.1287/opre.39.4.601. 
• "Heuristics for multi-attribute vehicle routing problems: A survey and synthesis". European Journal of Operational Research 231 (1): 1–21. 2013. doi:10.1016/j.ejor.2013.02.053. https://www.cirrelt.ca/documentstravail/cirrelt-2012-05.pdf. 
• Hirotaka, Irie; Wongpaisarnsin, Goragot; Terabe, Masayoshi; Miki, Akira; Taguchi, Shinichirou (2019). "Quantum Annealing of Vehicle Routing Problem with Time, State and Capacity". arXiv:1903.06322 [quant-ph].