The Vehicle Routing Problem (VRP)

Anmol Pahwa

This blog is the 2nd part of a 3-part blog series on Operations Research (OR) in Transportation Engineering. In the previous blog, we explored the simple yet complex Traveling Salesman Problem (TSP). In this blog, we take the problem one level up and explore another commonly studied problem in logistics, particularly urban logistics – the Vehicle Routing Problem (VRP).

On August 11, 1994 the first ever internet-based retail transaction took place, and since then e-commerce has completely transformed our shopping experience. What used to be a trip down to the store is now a hassle-free delivery one click away. This has enabled e-retailers to reach closer to its consumers thus driving higher revenues and profits. However, in a quest to achieve even larger profits and market share, e-retailers compete to offer consumers cheaper shipping, expedited deliveries, free returns, and other lucrative deals. In such a competitive and consumer-centric environment, how do the e-commerce companies manage their daily delivery operations? This is essentially what the Vehicle Routing Problem, one of the most fundamental problems in urban logistics and operations research, tries to answer. To be more precise, given a set of depot nodes each with a set of delivery vehicles each with a certain fixed and operational cost, and a set of customer nodes each with certain demand and service time-window, the objective of a Vehicle Routing Problem is to determine the optimal order of visits to the customer nodes using select vehicles that results in least total cost (fixed and operational cost) while accounting for depot capacity, vehicle capacity, driver working-hours, and customers’ delivery time-windows. The figure below is one such example of the Vehicle Routing Problem with the depot located near the geographic center and 100 customers spread across the region.

VRP instance with 100 customer nodes to visit from the depot node
(Instance: c201 Solomon)

Formulating the problem

Below is the formulation for a Capacitated Vehicle Routing Problem with Time-Windows and Heterogeneous Fleet of delivery vehicles operating Multiple Routes (C-VRP-TW-HF-MR).

Given, a graph \(\small G = (D,C,A)\) with set of depot nodes \(\small D\) with capacity \(\small q_d\), and fleet of delivery vehicles \(\small V_d\) with capacity \(\small q_v\), range \(\small l_v\), speed \(s\small_v\), refueling time \(\tau\scriptsize^f_v\), service time at the depot node \(\tau\scriptsize^d_v\) (per unit demand), service time at the customer node \(\tau\scriptsize^c_v\), operational cost \(π\scriptsize^o_v\) (per unit distance traveled), fixed cost \(π\scriptsize^f_v\), working hours \(\small w_v\) for every vehicle \(\small v \in V_d\) for every depot \(\small d \in D\); set of customer nodes \(\small C\) with demand \(\small q_c\), delivery time window \(\small[t\scriptsize^e_c, \small t\scriptsize^l_c \small]\) for every customer \(\small c \in C\); set of arcs \(\small A\) with length \(\small l_{ij}\ \forall\ (i,j) \in A\), the objective of the Vehicle Routing Problem is to develop least cost routes starting and ending at the depot nodes using select vehicles such that every customer node is visited exactly once while accounting for depot capacity, vehicle capacity, vehicle range, driver working-hours, and customers’ time-windows.

Objective function: minimize total cost (fixed and operational cost)

\(\small\quad \min{z=\sum_{v\in V}{\left(\pi_v^f+\pi_v^o\sum_{\left(i,j\right)\in A}{l_{ij}\sum_{r\in R_v} x_{ij}^r}\right)y_v}}\)

Subject to,
Service constraint: every customer node must be visited exactly once

\(\small\quad\quad\quad \sum_{d\in D}\sum_{v\in V_d}\sum_{r\in R_v} z_{cr}=1\ \ \ \ \ \ \ \ \ \ \ \ \ \ \forall\ c\in C\)

Flow conservation: at every node, the outgoing vehicle flow should balance the incoming vehicle flow.

\(\small\quad\quad\quad \sum_{i\in T_j} x_{ij}^r=\sum_{k\in H_j} x_{jk}^r\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \forall\ j\in\left\{D\cup C\right\};r\in R_v;v\in V_d;d\in D\)

Allocation constraints:

\(\small\quad\quad\quad z_{cr}=\sum_{v\in V_d}\sum_{j\in H_c} x_{cj}^r\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \forall\ c\in C;r\in R_v;v\in V_d;d\in D\)

Vehicle-use constraints:

\(\small\quad\quad\quad y_v\le\sum_{j\in H_d} x_{dj}^v\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \forall\ v\in V_d;d\in D\)

Route length evaluation:

\(\small\quad\quad\quad l_r=\sum_{i\in T_j} x_{ij}^rl_{ij}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \forall\ j\in\left\{D\cup C\right\};r\in R_v;v\in V_d;d\in D\)

Route load evaluation:

\(\small\quad\quad\quad q_r=\sum_{c\in C} z_{cr}q_c\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \forall\ c\in C;r\in R_v;v\in V_d;d\in D\ \)

Vehicle capacity constraint:

\(\small\quad\quad\quad \sum_{c\in C}{q_cz_{cr}}\le q_vy_v\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \forall\ v\in V_d;d\in D\)

Depot capacity constraint:

\(\small\quad\quad\quad \sum_{c\in C}{q_c\sum_{v\in V_d}\sum_{r\in R_v} z_{cr}}\le q_dy_d\ \ \ \ \ \ \forall\ d\in D\)

Vehicle range constraint:

\(\small\quad\quad\quad \sum_{d\in D}\sum_{v\in V_d}\sum_{r\in R_v} l_r\le l_v\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \forall\ v\in V_d;d\in D\)

Route start time constraint:

\(\small\quad\quad\quad t_{r_1}^s=0\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \forall\ v\in V_d;d\in D\)
\(\small\quad\quad\quad t_{r_k}^s=t_{r_{k-1}}^e+{\tau_v^fl_r}/{l_v}+\tau_v^dq_r\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \forall\ r\in R_v;v\in V_d;d\in D\)

Route end time constraint:

\(\small\quad\quad\quad t_{r_k}^e=t_{r_k}^s+{l_r}/{s_v}+\tau_v^c\sum_{c\in C} z_{cr}\ \ \ \ \ \ \ \ \ \forall\ r\in R_v;v\in V_d;d\in D\)

Driver working hours constraint:

\(\small\quad\quad\quad t_{r_K}^e\le w_v\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \forall\ v\in V_d;d\in D\)

Customer node arrival time constraint:

\(\small\quad\quad\quad t_c^a+M\left(1-x_{dc}^r\right)\geq t_r^s+x_{dc}^r{l_{dc}}/{s_v}\ \ \ \forall\ c\in H_d;r\in R_v;v\in V_d;d\in D\)
\(\small\quad\quad\quad t_c^a+M\left(1-x_{ic}^r\right)\geq t_i^d+x_{ic}^r{l_{ic}}/{s_v}\ \ \ \ \ \forall\ i\in T_c \setminus D;c\in C;r\in R_v;v\in V_d;d\in D\ \)

Customer node departure time constraint:

\(\small\quad\quad\quad t_c^d\geq t_c^a+\max{\left(t_c^a,\ t_c^e\right)}+\tau_c^v\ \ \ \ \ \ \ \ \ \ \ \ \ \ \forall\ c\in C\)

Customer node time-window constraint:

\(\small\quad\quad\quad t_c^a\le t_c^l\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \forall\ c\in C\)

Binary constraints,
Arc-use:

\(\small\quad\quad\quad x^r_{ij\ }\in\left\{0,1\right\}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \forall\ \left(i,j\right)\in A;r\in R_v;v\in V_d;d\in D\)

Vehicle-use:

\(\small\quad\quad\quad y_{v\ }\ \in\left\{0,1\right\}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \forall\ v\in V_d;d\in D\)

Customer node allocation:

\(\small\quad\quad\quad z_{cr\ }\in\left\{0,1\right\}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \forall\ c\in C;r\in R_v;v\in V_d;d\in D\)

Where,

\(\small\quad\quad\quad T_j\ =\left\{i;\left(i,j\right)\in A\right\}\)
\(\small\quad\quad\quad H_j=\left\{k;\left(j,k\right)\in A\right\}\)
\(\small\quad\quad\quad R_v=\left\{r_1,r_2,\ldots,r_k,\ldots,\ r_K\right\}\ \ \ \ \ \ \ \ \ \ \forall\ v\in V_d;d\in D\)

Solution methodology

The Vehicle Routing Problem, like the Traveling Salesman Problem, falls in the category of combinatorial optimization problem, wherein the aim is to find “best combination of objects from a given set of objects to achieve a certain objective given certain constraints”. Hence, again,I employed the Adaptive Large Neighborhood Search (ALNS) meta-heuristic which works on destroy and repair principle and thus iteratively removes and re-inserts nodes into the solution using certain removal and insertion heuristics. In every iteration of the ALNS meta-heuristic, one removal heuristic and then one insertion heuristic is chosen “adaptively”, i.e., based on their performance in improving the quality of the solution in previous iterations. The removal heuristic first removes a “large” chunk of nodes from the solution (10% to 40%) and the insertion heuristic then re-inserts these open nodes back into the solution thus “searching” through the “neighborhood” (solution space). Hence, the name – Adaptive Large Neighborhood Search.

The removal heuristics include,
– random node removal: removes customer nodes randomly from the solution
– random route removal: removes customer nodes from randomly selected routes
– random vehicle removal: removes customer nodes from randomly selected vehicles
– related node removal: for a randomly selected customer node, removes most related* customer nodes
– related route removal: for a randomly selected route, removes customer nodes from most related* routes
– related vehicle removal: for a randomly selected vehicle, removes customer nodes from most related* vehicles
– worst node removal: removes customer nodes that render highest reduction in cost on removal
– worst route removal: removes customer nodes from routes with low-utilization**
– worst vehicle removal: removes customer nodes from vehicles with low-utilization**
until n (10% to 40%) customer nodes have been removed from the solution
* In the context of VRP, relatedness of two customer nodes is defined by their geographic proximity, temporal proximity, and their respective demand quantities; relatedness of two routes is defined by the respective length, travel time, and load on the routes; and relatedness of two vehicles is defined by relatedness of the routes of the two vehicles.
** Low-utilization refers to low use with respect to capacity

The insertion heuristics on the other hand compute cost of inserting an open customer node at every possible position in the solution, thereby identifying least insertion cost and corresponding best insertion position for every open customer node*, and then,
– best insertion: inserts randomly selected open customer node
– greedy insertion: inserts customer nodes in increasing order of least insertion cost
– regret insertion: iteratively inserts customer nodes with highest regret cost**
at their best positions until all open customer nodes have been inserted into the solution.
* Note, after every iteration of the insertion heuristic, the least insertion cost and corresponding best insertion position for the remaining open customer nodes needs to be re-computed.
** Notice how best and greedy insertion heuristics are myopic in nature. The last few open customer nodes inserted using these methods tend to have significantly high insertion cost due to the solution being nearly full (almost complete). Regret insertion on the other hand accounts for inserting an open customer node at kth (typically k = 2, 3) best position instead of its best position, and in doing so, it inserts the open customer node with the highest regret cost.

Thus, using the above mentioned removal and insertion heuristics, in every iteration of Adaptive Large Neighborhood, the current solution is destroyed and repaired to create a new solution. If the newly created solution is better than the current solution, then this new solution is set as the current solution. If the newly created solution is also better than the best solution, then this new solution is set as the best solution. However, if the newly created solution is worse than the current solution, then only with certain (low) probability the new solution is set as the current solution. Performance scores for the removal and insertion heuristic used in this iteration are updated based on the quality of the newly created solution in comparison to the quality of current solution and the best solution.

In addition to the removal and insertion heuristic, the ALNS meta-heuristic employs local search heuristics after every few iterations. These local search heuristics make “small” adjustments to the solution, unlike the removal and insertion heuristics which make “large” changes to the solution. These local search heuristics include,
– move: randomly select a customer node and move it to its best position in the solution
– 2-opt: randomly select 2 arcs and reconfigure them
(for instance, arcs A—>B and I—>J in A—>B—>C…H—>I—>J could be reconfigured as A—>I—>H…C—>B—>J)
– split: split routes by moving a randomly selected depot node at its best position in the solution
– swap: randomly select 2 customer nodes and swap their positions.

Developing the solution to the Vehicle Routing Problem

To develop the Adaptive Large Neighborhood Search meta-heuristic with removal, insertion, and local search heuristics for the Vehicle Routing Problem, I used Julia Programing Language, a relatively new programing language (developed in 2012) perfectly suited for computational science. Interested readers can checkout the GitHub Repo – Vehicle Routing Problem.

Now lets solve the 100 customer node Vehicle Routing Problem introduced at the start of this blog. Recall, given a set of depot nodes and a set of customer nodes, the objective of a Vehicle Routing Problem is to determine the optimal order of visits to the customer nodes using select vehicles that results in least cost. The Adaptive Large Neighborhood Search meta-heuristic begins with a completely randomized initial solution with 26 vehicles deployed to serve 100 customers amounting to a total cost of 4701.6 monetary units. In every iteration then, the ALNS meta-heuristic destroys a large chunk of the solution and consequently repairs to create a new solution. This destroy and repair principle can be seen in action below. Finally, after only a few iterations of ALNS meta-heuristic, a good solution to the problem (locally optimal) can be achieved by efficiently routing just 3 vehicles thus amounting to a total cost of 591.6 monetary units.

A completely randomized initial solution
(Total Cost: 4701.6; Vehicles Used: 26)

Iterating through ALNS meta-heuristic
(Total Iterations: 20)

Optimal solution developed by the ALNS meta-heuristic
(Total Cost: 591.6; Vehicles Used: 3)

From our discussion above, one may notice the similarities in solution procedure for solving the Traveling Salesman Problem and the Vehicle Routing Problem. However, unlike the Traveling Salesman Problem, the Vehicle Routing Problem develops the optimal order of visits while additionally accounting for customers’ demand and time-windows, drivers’ working-hours, as well as depot and vehicle capacities. Yet, the rise of e-commerce brings additional challenges in routing delivery vehicles and thus more recent developments in the domain of routing problems includes time-dependent routing wherein travel time between nodes varies through the day, stochastic routing wherein certain elements of the delivery environment are known incompletely, dynamic routing wherein certain elements of the delivery environment are not known at all. We will tackle some of these issues in future blog as part of my dissertation, but for the next and the last blog in this Operations Research in Transportation Engineering series, we will take the problem yet another level up by introducing multi-level decision-making with the Location Routing Problem (LRP).

1 Comment

  1. Would love to learn more about this and how I can help with your research in addressing the continuing concerns regarding the e commerce delivery process of items with the environmental variations; more specifically how to account for the missing environment information and the solution to find a delivery path within a specific cost and vehicle range. Thanks for sharing your wisdom and knowledge, I look forward to hearing from you.

    Reply

Leave a Reply