Modeling Refueling in Vehicle Routing Problem in OR-Tools

Question

As the title suggests, I am working on a problem that pertains to single-vehicle routing, where certain vertices in V are not mandatory to be visited, but are useful for refueling the vehicle. The other vertices must be visited exactly once.

For this I am using the OR-Tools GLOP Linear Solver (Python), wherein I have modeled the entire problem as a matrix of binary variables Xij over all i and over all j belonging to V. Xij = 1 if vehicle goes from vertex i to j.

Create X matrix

# G is an adjacency matrix
    for i in range(len(G)):
        temp=[]
        for j in range(len(G[i])):
            temp.append(solver.BoolVar(str(i)+','+str(j)))
        X.append(temp)

Objective Function

# The objective function states that the cost of the entire travel should be minimum
    # I think summation of X[i][j]*G[i][j] over all i and all j should be minimum
    objective=solver.Objective()
    for i in range(len(G)):
        for j in range(len(G[i])):
            objective.SetCoefficient(X[i][j], G[i][j]) # multipling the path variable with corresponding weight

How do I model the refueling aspect of the problem? That the vehicle is refueled at certain vertices? The MILP that I am trying to solve for utilises variables like 'amount of fuel left at a vertex' etc to find the optimal route. How do I introduce these variables into the code? Am I using the wrong tool for the job?

Answer 1

I have worked on this problem, but with the multi-vehicle version, during my master's degree. I will reformulate the problem described by you, but formally, present a very naive MILP formulation, and give a brief literature review you can rely on concerning this problem.

Problem definition

Let $D(V = C \cup R \cup \{0\}, A)$ be a metric weighted complete digraph; we must assume this property since the presented formulation requires it; where the nodes set is composed of three disjoint sets:

• $C$ the customers set, i.e. nodes mandatorily must be visited;
• $R$ the recharge/fuel stations set, i.e nodes eventually may be visited whenever the vehicle must refuel/recharge; and
• $\{0\}$ the set containing only the depot node, from where the vehicle departs and returns.

Furthermore, let

• $d_{ij} \in \mathbb{R}^{+}$ be the arc $(i, j) \in A$ distance, that is, the distance between node $i$ and $j$ $\forall i, j \in V : i \neq j$;
• $f_{ij} \in \mathbb{R}^{+}$ be the arc $(i, j) \in A$ required fuel, that is, the amount of fuel the vehicle will spend to go from node $i$ to $j$ $\forall i, j \in V : i \neq j$; and
• $\beta \in \mathbb{R}^{+}$ be the vehicle fuel capacity, i.e., the vehicle can spend at most $\beta$ of fuel without stopping to recharge.

A solution for our problem is composed of a walk on $D$ visiting all the nodes in $C$, such that the vehicle fuel capacity is always respected. The Figure below, from C.A. Gencel and B. Keçeci (2019) shows a solution example.

The circles are the customers, the squares are our fuel stations, and the triangle is the depot.

MILP formulation

Now let's take a look at a naive formulation.

Variables

Our formulation has the following variables:

• $x_a \in \mathbb{N}$ the amount of time the arc $a \in A$ is used in the solution; and
• $e_i \in \mathbb{R}^{+}$ the vehicle remaining amount of fuel at customer $i \in C$.

Objective function

We seek for minimizing the solution cost (distance).

min $\sum_{a \in A} x_a d_a$ (1)

Constraints

The flow constraints: the amount of entering arcs equates to the number of exiting arcs.

$\sum_{a \in \delta^{+}(i)} x_a = \sum_{a \in \delta^{-}(i)} x_a \quad \forall i \in V$ (2)

Every customer and the depot; $C_0 = C \cup \{0\}$; must be visited exactly once.

$\sum_{a \in \delta^{+}(i)} x_a = 1 \quad \forall i \in C_0$ (3)

The amount of remaining fuel of the vehicle at a given customer must be enough to traverse the next arc, i.e. to reach the next selected node. Note that, by (2) and (3), $x_{ij} \in \mathbb{B}$ $\forall (i, j) \in A : i \in C_0 \vee i \in C_0$.

$e_i \geqslant \sum_{a \in \delta^{+}(i)} x_a f_a \quad \forall i \in C_0$ (4)

The amount of fuel must be decremented whenever the vehicle leaves the depot, or a fuel station, and goes to a customer.

$\beta - \sum_{r \in R \cup \{0\}} x_{ri} f_{ri} \geqslant e_i \quad \forall i \in C$ (5)

The amount of fuel also must be decremented whenever the vehicle departs from one customer to another. These constraints, famously known as Miller-Tucker-Zemlin (MTZ) constraints, prohibit subcycles composed by customers only.

$e_j \leqslant e_i - x_{ij} f_{ij} + \beta (1 - x_{ij}) \quad \forall i, j \in C : i \neq j$ (6)

Arcs with fuel consumption greater than $\beta$ never will be used.

$x_a = 0 \quad \forall a \in A : f_a > \beta$ (7)

The final solution must be a single connected component. The below constraints are an adaptation of the so-called Dantzig-Fulkerson-Johnson constraints. These constraints might be, depending on your background, a little bit tough to understand, but I think some sketches of graph drawings on a paper sheet will suffice to make you see the validity of this constraint set.

$\sum_{a \in \delta^{+}(S)} x_a \geqslant 1 \quad \forall S \subseteq V \backslash \{0\} : S \cap C \neq \emptyset$ (8)

And finally, the domain constraints.

$x \in \mathbb{N}^{|A|}$ (9)

$e \in \mathbb{R}^{+|C|}$ (10)

I must warn you that, although very simple and didactic, this is a very weak formulation. I have conducted some experiments with a formulation similar to this one for this problem on its multi-vehicle version, and the results were very poor, at least for the proposed instances (Masters dissertation).

A brief literature review

In this section, I will give a very short literature review that can guide you on future endeavors concerning this problem. The problem you are facing is formally called the Traveling Salesman Problem with Hotel Selection (TSPHS). Follows some papers, in chronological order, regarding this problem:

• P. Vansteenwegen, W. Souffriau and K. Sörensen (2012);
• M. Castro, et al. (2013);
• M. Castro, et al. (2015);
• M. Radmanesh, et al. (2016);

There are more recent papers about this problem, that you can find by googling . If you want to dive even further into this, you can check out some strongly related problems, such as the Black and White Traveling Salesman Problem and the Green-Vehicle Routing Problem (the multi-vehicle TSPHS version). Regarding this last one, you can find some papers in my Google Scholar.

Answer 2

Welcome to ORSE. You may have to use Integer optimization framework for such binary/integer model and also you can also explore or-tool's Vehicle routing example that can fit your use-case with minor changes.