oga

oga logo
LinkedIn
mail

900 848 508

Vehicle Route Optimization.
Origins and variants

1. The Origins, the Travelling Salesman Problem (TSP)

The Travelling Salesman Problem (TSP) answers the following question: given a list of cities and the distances between each pair of cities, what is the shortest possible route[1] that visits each city exactly once and at the end returns to the city of origin? The problem was first formulated in 1930 and is one of the most studied optimization problems. It is used as a test for many optimization methods. Although the problem is computationally complex, a large number of heuristics and exact methods are known, so it is possible to solve concrete approaches to the problem from one hundred to thousands of cities. One possible simplification is the ‘symmetric TSP’, in which the distance between a pair of cities is the same in both directions, forming a technically so-called “undirected” graph. This problem halves the number of possible solutions. In the ‘asymmetric TSP’, there may be no roads in both directions or the distances may be different, forming a “directed graph”. Traffic accidents, one-way streets, and airfares for cities with different round-trip costs are examples of how this asymmetry can influence the problem. In the original (asymmetric) problem there are N! possible routes (factorial of N), although it can be simplified since given a route we might not care about the starting point and this would reduce the number of routes to be examined by a factor of N, leaving (N-1)! If, in addition, the direction in which the traveler moves does not matter, the number of routes to be examined is again reduced by a factor of 2. Therefore, a total of (N-1)! / 2 possible routes would have to be considered, evaluated or compared. In practice, for a commuter problem with 5 cities there would be (5-1)!/2 = 12 different routes and we do not need a computer to find the best route, but as soon as we increase the number of cities the possibilities grow exponentially:
  • For 10 cities there are (10-1)!/2=181,440 different routes.
  • For 30 cities there are more than 4*10^30 possible routes. A computer calculating one million routes per second would need 10^17 years to solve it. In other words, if it had started calculating at the beginning of the creation of the universe (about 13.4 billion years ago) it would not have been finished yet.
It can be seen that, for each new city we incorporate, the number of routes is multiplied by the factor N and grows exponentially[2].
Travelling Salesman Problem (TSP)

1.    The classic VRP, the capacitated one

The capacitated vehicle routing optimization problem (CVRP) is a variant of the TSP that aims to answer problems that do not fit with the TSP due to the emergence of new constraints: What is the optimal set of routes for a fleet of vehicles that should satisfy the demands of a given set of customers taking into account the capacity of the vehicles?

The first definition appeared in a paper by George Dantzig and John Ramser in 1959, where they proposed an algorithmic approach and applied it to gasoline deliveries. The problem required the delivery of a certain product, stored in a single location or warehouse, to customers who have a certain demand. The fundamental objective was to minimize the total cost of the routes traced. In 1964, Clarke and Wright improved on Dantzig and Ramser’s approach by using a greedy approach known as the savings algorithm.

El VRP clásico, el capacitado
Source: ‘Minimizing the Carbon Footprint for the Time-Dependent Heterogeneous-Fleet Vehicle Routing Problem with Alternative Paths’ by Wan-Yu Liu, Chun-Cheng Lin, Ching-Ren Chiu, You-Song Tsao and Qunwei Wang.

1.    VRP Variants

The following is a brief description of the main variants of the classic problem discussed in the previous sections. This list is not exhaustive, but defines particularities, functionalities or new constraints that differentiate it from the others and that arise naturally to meet the real needs of logistics operators. However, in real life, your route optimization problem may include all or almost all these constraints or variants that we will see below.

3.1.   VRP with Time Windows (VRPTW)

VRP with time windows is the same problem as VRP with the additional constraint that in VRPTW a time window is associated with each customer in which the customer has to be supplied. The goal has traditionally been to minimize the vehicle fleet and the sum of travel time and waiting time needed to supply all customers in the required hours, but there are other approaches in which time windows are allowed to be missed or relaxed (at the cost of improving the main optimization criterion).

VRP with Time Windows (VRPTW)
Source: ‘A Hybrid Genetic Algorithm for the Periodic Vehicle Routing Problem with Time Windows’ by Michel Tolouse, Teodor Gabriel Crainic and Phuong Nguyen.

3.2.   VRP with Backhauls (VRPB)

The Vehicle Routing Problem with Backhaul (VRPB) is a VRP in which customers can demand or return some commodities. Thus in the VRPPB it is necessary to take into account that the commodities that customers return to the delivery vehicle must fit in it. The critical assumption is that all deliveries must be made on each route before any pickup can be made. This is due to the fact that vehicles are loaded from the rear, and rearranging loads on the delivery point lanes is not considered economical or feasible. The quantities to be delivered and to be picked up are fixed and known in advance. The VRPB is similar to the VRP with Pick-Up and Delivery with the restriction that, in the case of the VRPB, all deliveries on each route must be completed before pick-ups are made.

The optimization objective or criterion has traditionally been minimization of total distance traveled but could be other.

VRP with Backhauls (VRPB)

3.3.   VRP with Pickup and Delivery (VRPPD)

The vehicle routing with pickup and delivery problem (VRPPD) is a VRP in which customers are expected to return some goods. Thus, in the VRPPD it is necessary to take into account that the goods that customers return to the delivery vehicle must fit in it. This constraint makes the planning problem more difficult and may result in poor utilization of vehicle capacities, increased travel distances or the need for more vehicles.

Therefore, it is usually considered that there are constrained situations where all delivery demands start from the depot and all pick-up demands are brought back to the depot, so that there are no exchanges of goods between customers. Another alternative is to relax the restriction that all customers have to be visited exactly once. Another common simplification is to consider that each vehicle must deliver all goods before picking them up.

The objective has traditionally been to minimize the vehicle fleet and the sum of travel time, with the restriction that the vehicle must have sufficient capacity to carry the goods to be delivered and those to be picked up from the customers to be returned to the depot.

3.4.   Periodic VRP (PVRP)

In classical VRP, typically the planning period is a single day. In the case of the Periodic Vehicle Routing Problem (PVRP), the classical VRP is generalized by extending the planning period to M days. The objective is thus to minimize the vehicle fleet and the sum of the travel time required to supply all customers in M days.

A solution is feasible if all VRP constraints are satisfied. In addition, a vehicle cannot return to the depot the same day it leaves. During the M-day period, each customer must be visited at least once.

In the following figure we simulate that each route color is performed on a different day.

Periodic VRP (PVRP)
Source: ESRI Community - 'Vehicle Routing Problem with orders taking multiple days'

3.5.   Multi-Depot VRP (MDVRP)

They arise when a company has several depots from which it can serve its customers. If the customers are clustered around depots, then the distribution problem should be modeled as a set of independent VRP problems. However, if the customers and depots are intermingled, then a multi-depot vehicle distribution problem (MDVRP) must be solved.

An MDVRP requires the assignment of customers to depots. A fleet of vehicles is based at each depot. Each vehicle originates from a depot, serves the customers assigned to that depot, and returns to the same depot. The objective of the problem is to serve all customers while minimizing the number of vehicles and travel distance.

Multi-Depot VRP (MDVRP)

3.6.   Split Delivery VRP (SDVRP)

In the split delivery vehicle routing problem (SDVRP), more than one vehicle is allowed to serve a customer, so that a customer’s demand can be split among several vehicles on different routes.

Split Delivery VRP (SDVRP)
Source: ‘The split delivery vehicle routing problem with minimum delivery amounts’ by Damon Gulczynski, Bruce Golden and Edward Wasil.

3.7.   VRP with Satellite Facilities (VRPSF)

An important aspect of the vehicle routing problem (VRP) that has been largely overlooked is the use of satellite facilities to replenish vehicles during a route. When possible, satellite refueling allows drivers to continue making deliveries until the end of their shift without necessarily having to return to the central depot. This situation arises mainly in the distribution of fuels and certain retail items.

VRP with Satellite Facilities (VRPSF)
Source: ‘Production, Replenishment and Inventory Policies for Perishable Products in a Two-Echelon Distribution Network’, by Mingyuan Wei, Hao Guan, Yunhan Liu, Benhe Gao and Canrong Zhang.

3.8.   Site Dependent VRP (SDVRP)

In the site-dependent vehicle routing problem (SDVRP), a heterogeneous fleet of vehicles is used to serve a set of customers, but there are compatibility dependencies between customer sites and vehicle types. The goal is to carefully select an allowable vehicle type for each customer.

 

3.9.   Stochastic VRP (SVRP)

The vehicle routing problem is stochastic when the demands at individual delivery (pickup) locations behave as random variables, and routes must be defined before the values of these random variables are known.

Stochastic VRP (SVRP)
Source: ‘A survey on metaheuristics for stochastic combinatorial optimization’, by Leonora Bianchi, Marco Dorigo, Luca Maria Gambardella and Walter Gutjahr.

3.10.   Dynamic VRP (DVRP)

The dynamic routing problem (DVRP) is one of the important variants of the VRP. Its objective is to design the optimal set of routes for a fleet of vehicles in order to serve a given set of customers while new customer orders arrive during the completion of the earliest scheduled workday.

Source: ‘Dynamic Vehicle Routing Problem for Medical Emergency Management’ by Jean-Charles Créput, Amir Hajjam, A. Koukam and Olivier Kuhn.

3.11.   Capacitated Arc Routing Problem (CARP)

The capacitated arc routing problem (CARP) is a well-known combinatorial problem that requires the identification of the minimum total distance traveled by a set of vehicles to service a given set of roads subject to vehicle capacity constraints. It is a suitable approach when several points must be visited on the same street (to deliver mail, for example).

Capacitated Arc Routing Problem (CARP)

References

  • Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management science, 6(1), 80-91.
  • Golden, B. L., & Wong, R. T. (1981). Capacitated arc routing problems.Networks, 11(3), 305-315.
  • Pullen, H. G. M., & Webb, M. H. J. (1967). A computer application to a transport scheduling problem.The computer journal, 10(1), 10-13.
  • Fisher, M. L., & Jaikumar, R. (1981). A generalized assignment heuristic for vehicle routing.Networks, 11(2), 109-124.
  • Dumas, Y., Desrosiers, J., & Soumis, F. (1991). The pickup and delivery problem with time windows.European journal of operational research, 54(1), 7-22.
  • Beltrami, E. J., & Bodin, L. D. (1974). Networks and vehicle routing for municipal waste collection.Networks, 4(1), 65-94.
  • Ball, M. O., Golden, B. L., Assad, A. A., & Bodin, L. D. (1983). Planning for truck fleet size in the presence of a common‐carrier option.Decision Sciences, 14(1), 103-120.
  • Dror, M., & Trudeau, P. (1989). Savings by split delivery routing.Transportation Science, 23(2), 141-145.
  • Dror, M., & Ball, M. (1987). Inventory/routing: Reduction from an annual to a short‐period problem.Naval Research Logistics (NRL), 34(6), 891-905.
  • Nag, B. L. (1988). Golden, and AA Assad. Vehicle Routing with Site Dependencies. Vehicle Routing: Methods and Studies, BL Golden and AA Assad, Eds.
  • Gendreau, M., Laporte, G., & Séguin, R. (1995). An exact algorithm for the vehicle routing problem with stochastic demands and customers.Transportation science, 29(2), 143-155.
  • Psaraftis, H. N. (1980). A dynamic programming solution to the single vehicle many-to-many immediate request dial-a-ride problem.Transportation Science, 14(2), 130-154.

[1] Original optimization criterion (total distance traveled) but the TSP can be solved with any other criteria.
[2] Therefore, the problem belongs to the class of NP-complete problems.

Categories

Latests articles

Acerca del autor

Autor
Alfredo García
Senior Optimization Consultant en oga

Professor at the Pablo de Olavide University (UPO) and PhD in Mathematics from the University of Seville. Senior Optimization Consultant at oga.

Passionate about Mathematics, as a fundamental science, but especially about Applied Mathematics. What motivates him most is solving real problems and that is why, after more than 20 years of experience, he has worked in Pure Mathematics, Operations Research, Multiobjective Optimization, Evolutionary Computation and finally in Machine Learning and Business Analytics.

También podría interesarte