The Location Routing Problem (LRP)

Anmol Pahwa

This blog is the 3rd and the final part of a 3-part blog series on Operations Research (OR) in Transportation Engineering. In the previous blog, we explored the Vehicle Routing Problem (VRP). In this blog, we take the problem yet another level up by introducing multi-level decision-making with the Location Routing Problem (LRP).

The growth of e-commerce has bridged the gap between the consumer and the retailer, bringing prosperity for both. 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. To contend with growing market pressures, e-retailers continuously review their distribution strategy, reorganizing operations and revising plans when necessary. This process includes strategic decision-making (long-term decisions such as facility location choices), tactical (medium-term decisions such as inventory management), operational (short-term decisions such as vehicle routing), or even a combination of the three (e.g., location-inventory-routing problem). The Location Routing Problem entails one such combination of decisions, in particular, the long-term strategic choice of locating facilities and short-term operational choice pertaining to vehicle routing. 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 Location Routing Problem is to determine the optimal order of visits to the customer nodes from select depots 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 Location Routing Problem with 100 customers spread randomly across the region, one central depot located near the geographic center having a large delivery truck capable of serving all customers in a single delivery tour, 4 smaller depots (micro-hubs) each with one cargo-bike capable of serving only a subset of customers in a single delivery tour.

VRP instance with 100 customer nodes, one central depot with large delivery truck, and 4 micro-hubs with cargo-bikes

Formulating the problem

Given, a graph \(\small G = (D,C,A)\) with set of depot nodes \(\small D\) with capacity \(\small q_d\), operational cost \(π\scriptsize^o_d\) (per unit demand), fixed cost \(π\scriptsize^f_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 Location Routing Problem is to develop least cost routes starting and ending at the depot nodes using select depot nodes and 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_{d\in D}{\left(\pi_d^f+\pi_d^o\sum_{v\in V_d}\sum_{r\in R_v}{z_{cr}q_c}\right)y_d}+\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\)

Depot-use constraints:

\(\small\quad\quad\quad y_d\le\sum_{v\in V_d} y_v\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \forall\ 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\)

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\)

Depot-use:

\(\small\quad\quad\quad y_{d\ \ }\in\left\{0,1\right\}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \forall\ 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 Location 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
– random depot removal: removed customer nodes from randomly selected depots
– 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
– related depot removal: for a randomly selected depot, removes customer nodes from most related* depots
– 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**
– worst depot removal: removes customer nodes from depots with low-utilization**
until n (10% to 40%) customer nodes have been removed from the solution
* In the context of LRP, relatedness of two 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 Location 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 – Location Routing Problem.

Now lets solve the 100 customer node Location Routing introduced at the start of this blog. Recall, given a set of depot nodes and a set of customer nodes, the objective of a Location Routing Problem is to determine the optimal order of visits to the customer nodes from select depots using select vehicles that results in least cost. The Adaptive Large Neighborhood Search meta-heuristic begins with a completely randomized initial solution with all 5 depots in use to serve 100 customers amounting to a total cost of 1033.9 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 cargo-bikes from 4 micro-hubs thus amounting to a total cost of 268.6 monetary units.

A completely randomized initial solution
(Total Cost: 1033.9; Depots Used: 5)

Iterating through ALNS meta-heuristic
(First 60 iterations only)

Optimal solution developed by the ALNS meta-heuristic
(Total Cost: 268.6; Depots Used: 4)

This concludes the 3 part blog series on Operations Research in Transportation Engineering. That being said, the field of Operations Research is vast, and as discussed in the previous blog – 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.

Leave a Reply