Maths and the Logistics of Vehicle Routing

Here’s an example problem I was working on with some colleagues. Let’s consider a pretty specific setup for a logistical vehicle routing problem. Say we have a bunch of factories located around a city, and each has finished working on some components that we want to bring together at a main warehouse. We want to find the most efficient way to get those components to the warehouse but to complicate things we also have a limited fleet of trucks that are spread out around the factories. We have fewer trucks than we have factories, so some factories will have to rely on their components being picked up by trucks coming from others. For this problem we’ll look at the case that each factory only has one or two components, each of fairly uniform size; but this is all fairly easily generalisable to when this isn’t the case. Also, we only consider the case where the truck fleet has enough capacity to carry all of the components without requiring multiple trips.

Full Mathematical Model

The first thing we’ll do is try to fully describe this problem in mathematical terms. Applied mathematics is really about trying to capture and model the real world so we can use the powerful techniques developed in pure mathematics. Experienced users of applied mathematics will be jumping to model this with integer linear programming. This means it’s an optimisation problem with integers involved where the constraints defining the problem are linear expressions; while that might not seem intuitive immediately we’ll be able to see why that is soon.

Defining the resources

The first step is to define what we know about our setup. Let’s say $T$ is our set of $m$ trucks, $F$ is our set of $n$ factories, $w$ is the warehouse. For convenience, we define the locations $L = F\cup w$, the set of factories and the warehouse. We also know the cost of travelling between two places $c$. The cost can be the distance between two places, the time taken to travel, the monetary cost associated with that leg, or any other cost we want to define. For instance, $c_{f,w}$ is the cost of a truck going from factory $f$ straight to the warehouse. We know the number of components at a factory $f$, which we’ll call $p_f$. We have the number of components that truck $t$ can carry, which we’ll call $q_t$. We also know which factories our trucks start at, which we’ll encode in $\lambda$. If truck $t$ starts at factory $f$, we write $\lambda_t=f$.

Decision variables

Optimisation at its core is about decision making. So if we’re going to define a problem, we want to know exactly how to interpret an answer to make a decision. Really what we want to know is whether we use a certain truck (because the most efficient solution might be to ignore some of the trucks), and the route for each truck. Let’s define them.

• $a_t$ is $1$ if truck $t$ is used and $0$ otherwise
• $x_{t,i,j}$ is 1 if truck $t$ travels from point $i$ to point $j$, and $0$ if not. The points to pick from will be the factories and the warehouse. By putting together all the segments that truck $t$ travels along, we can construct its entire route.

We also need to define some extra variables to keep track of how full the trucks are. While this isn’t really a decision to be made, it’ll come in handy later.

• $u_{t,i,j}$ is equal to the number of components that truck $t$ transports from point $i$ to point $j$.

Objective function

This is an optimisation problem, so we need to define what we’re actually going to optimise for. While there are a number of candidates, the simplest (and usually most useful) option is just to say that we want to minimise the total amount of travelling that’s done across all the trucks. That way the best solution won’t use trucks that we won’t need, and we don’t have trucks driving to opposite ends of the city if we don’t need them to. Whether we want to define that travelling as distance travelled, time taken, or fuel used will be up to each project. We could go a step further here and include the cost of manpower and the trucks involved, but that’s simply incorporated into the model here on a project by project basis. Here’s how we write it in mathematical terms: $$\min \sum_{t\in T}\sum_{i,j\in L}c_{i,j}x_{t,i,j}$$ We can read this as for each truck sum up the cost of each leg multiplied by whether the truck travelled that leg (0 or 1). Take the sum of these terms for each truck, then minimise the result. Optionally, we could also model the case where there is a fixed cost for using each truck. Let’s say if we use truck $t$, there is a fixed cost of $b_t$. In this case, we would want the leg costs $a_t$ to be measured in the same units, so monetary costs would be best as opposed to distance or time. We would then alter the objective function to $$\min \sum_{t\in T}\sum_{i,j\in L}c_{i,j}x_{t,i,j} + \sum_{t\in T}b_t a_t$$

Constraints

In order to convert the real world problem into a mathematical format, it is extremely useful to think of the rules of the problem as geometric constraints to the objective function. In this problem, we will see that all the constraints are linear expressions, which is a highly desirable property of a problem as it makes them easily solvable. So let’s go step by step through the problem, describing what we want to achieve, a more explicit way of describing it, then the mathematical expression.

Firstly, we define the domains of the variables that we defined before. \begin{align} a_t &\in \text{{0,1}} && \forall t\in T \newline x_{t,i,j} &\in \text{{0,1}} && \forall t\in T,\ \forall i,j\in L \newline u_{t,i,j} &\in \mathbb{N} && \forall t\in T,\ \forall i,j\in L \end{align}

We want to ensure that all the components are picked up. The way we do this is by measuring the change in the number of components that trucks are carrying as they pass through the factories. For each factory, the total change of components across all the trucks must sum to the number of components at the factory. \begin{equation} \sum_{t\in T}\left(\sum_{j\in L}u_{t,f,j} - \sum_{i\in L}u_{t,i,f}\right) = p_f,\qquad \forall f\in F \end{equation}

Now we don’t allow a truck to travel from one location to the same location as one leg. That is, for each truck and location, the truck cannot travel from the location to the same location. \begin{equation} x_{t,i,i} = 0,\qquad \forall t\in T,\ \forall i\in L \end{equation}

This next equation will include two pieces of information. A truck can’t transport any components down a leg if it cannot travel down that leg. When $x_{t,i,j}=0$, then $u_{t,i,j}=0$. Also the most components that the truck can take down a leg is the capacity of the truck. When $x_{t,i,j}=1$, $u_{t,i,j}\le q_t$. We combine these as \begin{equation} u_{t,i,j} \le q_tx_{t,i,j},\qquad \forall t\in T,\ \forall i,j\in L \end{equation}

We’ll need a few equations to describe the paths that the trucks are allowed to travel down. We only want trucks to travel out of locations that they travelled into in the first place, so we don’t get trucks appearing or disappearing. For each truck, at each factory except its starting location, the number of times the truck enters the factory is equal to the number of times the truck leaves the factory. \begin{equation} \sum_{i\in F}x_{t,i,f} = \sum_{j\in F}x_{t,f,j},\qquad \forall t\in T,\ \forall f\in F,\ f\ne \lambda_t \end{equation}

However, we do want trucks to appear at their starting factory if we use them. For each truck, the number of legs travelled out of its starting factory is 1 if we use it or 0 otherwise, so equal to $a_t$. Similarly, we want each truck arriving at the warehouse once if we use them. \begin{align} \sum_{j\in F}x_{t,\lambda_t,j} &= a_t, && \forall t\in T \newline \sum_{i\in F}x_{t,i,w} &= a_t, && \forall t\in T \end{align}

Also, we don’t want trucks entering their starting factories or leaving the warehouse \begin{align} \sum_{i\in F}x_{t,i,\lambda_t} &= 0, && \forall t\in T \newline \sum_{j\in F}x_{t,w,j} &= 0, && \forall t\in T \end{align}

So to summarise: If we use a truck $(a_t=1)$, then it must appear at factory $\lambda_t$, not return to $\lambda_t$, and arrive at and not leave the warehouse $w$. A truck can only enter a factory if and only if it leaves it, and cannot travel from one factory to itself. A truck can only carry goods down a leg if it is travelling down that leg, up to a maximum of its capacity. All components are picked up by a truck, and since all trucks must arrive at the warehouse, all the components arrive as well. Note that all of these equations are linear expressions. That is, variables are only ever added to each other, never multiplied.

Solving the problem

This set of variables, objective function and constraints completely describes the problem. We can now code the problem up using embedded modelling languages such as JuMP in Julia or PuLP in Python. Then we can use solvers such as Gurobi or CPLEX to find the optimal solutions.

However, at this point we run into a problem. It turns out that this takes extremely long times to solve for anything over about 100 components. That’s because there are two coupled problems that we’re trying to solve. It’s both an assignment problem and a routing problem. We want to decide which components get picked up by which trucks, but also what the optimal route is for the trucks to get to the factory. The way the problem is described, these two elements are directly linked to one another, compounding the computation time needed to solve them. Now we could use more advanced decomposition techniques to simplify things, but instead lets try and decouple things with a heuristic solution.

Heuristic Model

What we’re going to do here is sacrifice having the best solution that takes to long to find in favour of getting a good solution that we can find quickly. We decouple the problem by splitting it into two stages: assignment and routing. First we decide which trucks are going to pick up which components (in a suboptimal but still good manner), then we find the fastest routes for each truck individually to pick them all up. This is opposed to the full model where we calculate all these things optimally at the same time, so the routing choice affects the assignment choice and vice versa.

Step 1: Assignment

We need a good way to assign components to trucks. One way we can think about this is to reduce some penalty associated with a truck picking up a component. We want larger penalties if the truck has to travel far out of its way, and smaller if the components are directly on the way to the warehouse.

The penalty we use I will refer to as the elliptical detour cost. For a truck starting at factory $f$, the penalty for the truck picking up a component at factory $j$ is $$d_E(f,j) = c_{f,j} + c_{j,w} - c_{f,w}$$ The penalty is the direct path the truck would have to travel to pick up the the component and go to the warehouse minus the cost of travelling straight from the factory to the warehouse. Essentially this measures how much extra the truck would have to travel if we only considered that that one component. If we use distance as our cost function, a constant penalty would describe an ellipse of locations with foci at the factory and the warehouse. A smaller ellipse would correspond to travelling less out of the way on the way to the factory, so that’s what we aim to minimise.

Now we can fully model this assignment subproblem. The decision variables we will use are - $a_t$ is $1$ if truck $t$ is used and $0$ otherwise - $s_{t,f}$ is the number of components that truck $t$ picks up from factory $f$

Our new objective function is to minimise the penalty associated with picking up each component. $$\min \sum_{t\in T}\left(b_tc_t + \sum_{j\in F}s_{t,j}d_E(\lambda_t,j)\right)$$

For our constraints, we first define the domain of the variables: \begin{align} a_t &\in \text{{0,1}} && \forall t\in T \newline s_{t,j} &\in \mathbb{N} && \forall t\in T,\ \forall j\in F \end{align}

We require that all the components are picked up. \begin{equation} \sum_{t\in T}s_{t,j}=p_j,\qquad \forall j\in F \end{equation}

We only use pick components up with a truck if we use a truck, up to a maximum of its capacity. \begin{equation} \sum_{j\in F}s_{t,j}\le q_ta_t,\qquad \forall t\in T \end{equation}

We can solve this optimisation problem fairly quickly. Note that we’ve reduced the complexity from $O(mn^2)$ variables and $O(mn^2)$ equations to $O(mn)$ variables and $O(mn)$ equations.

Step 2: Routing

Now that we know which truck picks up which components, all we have to do is figure out the best route for each truck to take. Note that this can be worked out independently for each truck. It essentially involves modifying the routing equations in the full mathematical model. This requires $m$ repititions of a problem with $O(n^2)$ variables and $O(n)$ equations, and is fairly fast to solve.

All in all, this heuristic worked fairly well on dummy problems, and allowed us to solve problems with well over 200 factories involved.