The mathematical formulation introduced on this part will use the identical equations introduced by Toth & Vigo (2002) within the mannequin therein known as the “three-index car circulate formulation”.
Contemplate a set V of nodes (calls for and depot) and a set Ok of automobiles. We’ll use lowercase i and j to point node indexes and lowercase okay to point car indexes. As this mannequin is legitimate for the uneven case, allow us to assume the nodes are a part of a whole directed graph G(V, A) with arcs A. On this downside, there’s a single depot node listed by 0 and all automobiles have the identical capability Q. Contemplate two teams of choice variables:
- x_{i, j, okay}: Is a binary variable that signifies an lively arc from node i to node j carried out by car okay.
- y_{i, okay}: Is a binary variable that signifies that the demand from node i is fulfilled by car okay.
Contemplate our goal to reduce the price worth related to lively arcs. Complete length or distance are typical examples. Say the price of traversing the arc i, j is cᵢⱼ. The target perform might be acknowledged as the next.
We additionally want to incorporate constraints that guarantee:
- Every buyer i is visited as soon as, due to this fact has one lively arc which begins from it and one which arrives on it.
- If any arc variable listed by car okay goes into one node i or out of it, the demand q of this node is assigned to car okay.
- The whole demand assigned to a car should not exceed its capability Q.
- Precisely |Ok| nodes begin on the depot and arrive on the depot.
- There aren’t any subtours… Nonetheless, the variety of subtours is probably too massive to be enumerated from the beginning. We’ll dive into extra element about methods to do it.
As typical for Python tutorials, allow us to begin our hands-on half by importing the libraries used on this part:
import time
from itertools import cycleimport numpy as np
from scipy.spatial.distance import pdist, squareform
import matplotlib.pyplot as plt
import matplotlib as mpl
import networkx as nx
import pyomo.environ as pyo
from pyomo.contrib.appsi.solvers.highs import Highs
And now allow us to instantiate a random downside with N demand nodes. On this instance, the depot node is assumed to be the primary node (index 0), so we guarantee its corresponding demand can be zero.
np.random.seed(42) # Outcomes ought to be all the time the identicalN = 10
calls for = np.random.randint(1, 10, dimension=N)
calls for[0] = 0
capability = 15
n_vehicles = 4
coordinates = np.random.rand(N, 2)
distances = squareform(pdist(coordinates, metric="euclidean"))
distances = np.spherical(distances, decimals=4) # keep away from numerical errors
The variety of vital automobiles might be calculated by utilizing a Bin Packing Drawback. An instance of methods to carry out it is usually included within the full supply code.
There are two approaches for modeling an issue in pyomo: Summary and Concrete fashions. Within the first strategy, the algebraic expressions of the issue are outlined earlier than some knowledge values are provided, whereas, within the second, the mannequin occasion is created instantly as its parts are outlined. Yow will discover extra about these approaches within the library documentation or within the e-book by Bynum et al. (2021). All through this text, we are going to undertake the Concrete mannequin formulation.
mannequin = pyo.ConcreteModel()
Allow us to instantiate the units of demand nodes V, arcs A, and automobiles Ok. Discover that the depot node is included within the set of nodes V as within the authentic mathematical formulation.
mannequin.V = pyo.Set(initialize=vary(len(calls for)))
mannequin.A = pyo.Set(initialize=[(i, j) for i in model.V for j in model.V if i != j])
mannequin.Ok = pyo.Set(initialize=vary(n_vehicles))
Now our parameters for capability, demand load, and arc prices.
mannequin.Q = pyo.Param(initialize=capability)
mannequin.q = pyo.Param(mannequin.V, initialize={i: d for (i, d) in enumerate(calls for)})
mannequin.c = pyo.Param(mannequin.A, initialize={(i, j): distances[i, j] for (i, j) in mannequin.A})
We additionally should embody constraints beforehand listed. First allow us to implement them utilizing the standard Pyomo signature: perform(mannequin, *area).
def arcs_in(mannequin, i):
if i == mannequin.V.first():
return sum(mannequin.x[:, i, :]) == len(mannequin.Ok)
else:
return sum(mannequin.x[:, i, :]) == 1.0def arcs_out(mannequin, i):
if i == mannequin.V.first():
return sum(mannequin.x[i, :, :]) == len(mannequin.Ok)
else:
return sum(mannequin.x[i, :, :]) == 1.0
def vehicle_assignment(mannequin, i, okay):
return sum(mannequin.x[:, i, k]) == mannequin.y[i, k]
def comp_vehicle_assignment(mannequin, i, okay):
return sum(mannequin.x[i, :, k]) == mannequin.y[i, k]
def capacity_constraint(mannequin, okay):
return sum(mannequin.y[i, k] * mannequin.q[i] for i in mannequin.V) <= mannequin.Q
After which incorporate them into our mannequin.
mannequin.arcs_in = pyo.Constraint(mannequin.V, rule=arcs_in)
mannequin.arcs_out = pyo.Constraint(mannequin.V, rule=arcs_out)
mannequin.vehicle_assignment = pyo.Constraint(mannequin.V, mannequin.Ok, rule=vehicle_assignment)
mannequin.comp_vehicle_assignment = pyo.Constraint(mannequin.V, mannequin.Ok, rule=comp_vehicle_assignment)
mannequin.capacity_constraint = pyo.Constraint(mannequin.Ok, rule=capacity_constraint)
Discover that I didn’t embody the subtour elimination constraints but. We should always take into account all doable permutations of the N nodes taking okay at a time and these might be prohibitively massive to enumerate even for reasonable dimension cases. Alternatively, in our answer process, we are going to recursively embody subtour elimination constraints every time a brand new answer is discovered if we confirm that this answer produces subtours. In some industrial solvers, these are known as “lazy constraints” and might be integrated straight into the solver by way of callback.
First allow us to create a perform that, given a subtour, all remaining nodes, a node from the subtour, and a car, returns a Pyomo expression equivalent to the mathematical formulation beforehand acknowledged. Additionally, allow us to embody a ConstraintList to which we are going to embody new parts as we proceed with the answer.
def subtour_elimination(mannequin, S, Sout, h, okay):
nodes_out = sum(mannequin.x[i, j, k] for i in S for j in Sout)
return mannequin.y[h, k] <= nodes_outmannequin.subtour_elimination = pyo.ConstraintList()
We should create some capabilities that may, given an answer, return subtours created (in the event that they exist). To take action, we are going to first create an inventory of lively arcs within the mannequin utilizing the find_arcs perform. This checklist might be used to create an incomplete directed graph utilizing the Networkx DiGraph class. And the find_subtours perform ought to return a checklist of units of linked parts.
def find_arcs(mannequin):
arcs = []
for i, j in mannequin.A:
for okay in mannequin.Ok:
if np.isclose(mannequin.x[i, j, k].worth, 1):
arcs.append((i, j))
return arcsdef find_subtours(arcs):
G = nx.DiGraph(arcs)
subtours = checklist(nx.strongly_connected_components(G))
return subtours
Our objective is to eradicate teams of linked parts that don’t embody the depot node. So within the subsequent step, we are going to create capabilities that iterate over the checklist of units, and embody new constraints if the set of parts doesn’t embody the depot node. This can use the strategy add of the ConstraintList class.
def eliminate_subtours(mannequin, subtours):
proceed = False
for S in subtours:
if 0 not in S:
proceed = True
Sout = {i for i in mannequin.V if i not in S}
for h in S:
for okay in mannequin.Ok:
mannequin.subtour_elimination.add(
subtour_elimination(mannequin, S, Sout, h, okay)
)
return proceed
And now we’ve got all the pieces able to suggest an answer process that iteratively solves the MIP, verifies if the present answer has subtours, and, in that case, contains new constraints to eradicate them. In any other case, the answer discovered is perfect.
def solve_step(mannequin, solver):
sol = solver.resolve(mannequin)
arcs = find_arcs(mannequin)
subtours = find_subtours(arcs)
time.sleep(0.1)
proceed = eliminate_subtours(mannequin, subtours)
return sol, proceed def resolve(mannequin, solver):
proceed = True
whereas proceed:
sol, proceed = solve_step(mannequin, solver)
return sol
Now allow us to instantiate the solver and resolve our mannequin. The Highs solver is on the market in Pyomo (examine the imports) if the highspy package deal is put in. So be certain to run a pip set up highspy .
solver = Highs()
solver.highs_options = {
"log_file": "Highs.log",
"mip_heuristic_effort": 0.2,
"mip_detect_symmetry": True,
"mip_rel_gap": 1e-6,
}answer = resolve(mannequin, solver)
Yet another perform to seek out the excursions created and we’re able to plot outcomes.
def find_tours(mannequin):
excursions = []
for okay in mannequin.Ok:
node = 0
excursions.append([0])
whereas True:
for j in mannequin.V:
if (node, j) in mannequin.A:
if np.isclose(mannequin.x[node, j, k].worth, 1):
node = j
excursions[-1].append(node)
break
if node == 0:
break
return excursions
Wonderful outcomes for the small occasion with a complete of 10 nodes. Nonetheless, even for this small occasion, the solver took virtually half a minute to acquire the answer and the complexity will increase considerably with extra demand factors. Happily, there are specialised algorithms publicly obtainable to seek out good high quality options for a lot bigger cases in a brief computational time. Allow us to check out them within the subsequent part.
