Corresponding Author: Miguel Jaller
Vehicle Routing Problem (VRP) is a classic operations research problem, wherein the objective is to find the set of routes that minimize the transportation cost for a fleet of vehicles departing from a depot, visiting a set of points (customers), each demanding certain quantity of goods. These delivery vehicles may have a fixed capacity and each route may be constrained to a threshold (based on time or distance). A VRP must have at least one of these two constraints, however, if neither of the two constraints are imposed then the VRP simply becomes a Traveling Salesman Problem (TSP). In the classic VRP, the depot is the distribution center – the vehicles fill the cargo at the depot and deliver it to the customers. However, this problem can also be reversed, wherein the depot is the collection center, as in the case of waste collection.
Originally designed by Dantzig and Ramser (1959) as The Truck Dispatching Problem, VRP has gained a lot of popularity since then and continues to be a highly researched topic. Ever since its introduction, VRP has been solved for various different applications such as multi-depot VRP, dynamic VRP, open VRP, LIFO VRP etc., employing Linear Programming (LP), heuristics and meta-heuristics. In this study however, we develop the classic capacitated, time-constrained VRP and solve it using Evolutionary Algorithms (EA).
With the advent of different delivery vehicle types and technology, one can think of this problem as a fleet design problem, wherein the objective is to solve the VRP in order to design the fleet and determine the set of routes such that the total transportation cost is minimized. This fleet design pertains to both the size – the number of vehicles required, and the mix – the type of vehicles in the feet. Hence the objective of this study is to replicate typical Business to Consumer (B2C) last-mile operations under different set of consumer demand conditions and solve VRP using EA, thereby designing the fleet and determining the optimal set of tours.
Figure 1. VRP tours for 100 customers in a 10 x 10 service region
We solved the VRP for 100 customers in a 10 x 10 service region, with depot located at the center of this service region. Each of these customers demand a certain quantity of goods (1-5 boxes), supplied by vehicles with a fixed capacity. These delivery vehicles can either be Internal Combustion Engine (ICE) vehicles or Electric Vehicles (EV). Hence the fleet can be a mix of the two types of vehicles. Figure 1 shows the resulting tours for the fleet. The fleet requirement to serve 100 customers comprises of 2 ICEs and 2 EVs, as can be seen from the figure. It is interesting to note that the longer and demanding tours have been allocated to EVs and not ICEs despite of ICEs having a higher range and capacity. This can be accounted to the fact that the per mile operation cost of EVs is smaller compared to ICEs, thus if and when a tour can be catered with an EV, without violating any constraints (capacity or range), then an EV must be deployed. It is important to note that although the results presented here do not completely represent the actual consumer demand, however, this study presents a good platform to extend the work to real life data, with much higher consumer demand, and a warehouse located outside the service region.
References
Dantzig, G. B., & Ramser, J. H. (1959). The Truck Dispatching Problem. Management Science, 6(1), 80-91.