# This code is part of a Qiskit project.
#
# (C) Copyright IBM 2018, 2025.
#
# This code is licensed under the Apache License, Version 2.0. You may
# obtain a copy of this license in the LICENSE.txt file in the root directory
# of this source tree or at http://www.apache.org/licenses/LICENSE-2.0.
#
# Any modifications or derivative works of this code must retain this
# copyright notice, and modified files need to carry a notice indicating
# that they have been altered from the originals.
"""An application class for the vehicle routing problem."""
from __future__ import annotations
import itertools
import random
import networkx as nx
import numpy as np
from docplex.mp.model import Model
from qiskit_optimization.algorithms import OptimizationResult
from qiskit_optimization.problems.quadratic_program import QuadraticProgram
from qiskit_optimization.translators import from_docplex_mp
from .graph_optimization_application import GraphOptimizationApplication
[docs]
class VehicleRouting(GraphOptimizationApplication):
"""Optimization application for the "vehicle routing problem" [1] based on a ``NetworkX`` graph.
References:
[1]: "Vehicle routing problem", https://en.wikipedia.org/wiki/Vehicle_routing_problem
"""
def __init__(
self,
graph: nx.Graph | np.ndarray | list,
num_vehicles: int = 2,
depot: int = 0,
) -> None:
"""
Args:
graph: A graph representing a problem. It can be specified directly as a
`NetworkX <https://networkx.org/>`_ graph,
or as an array or list format suitable to build out a NetworkX graph.
num_vehicles: The number of vehicles
depot: The index of the depot node where all the vehicle depart
"""
super().__init__(graph)
self._num_vehicles = num_vehicles
self._depot = depot
[docs]
def to_quadratic_program(self) -> QuadraticProgram:
"""Convert a vehicle routing problem instance into a
:class:`~qiskit_optimization.problems.QuadraticProgram`
Returns:
The :class:`~qiskit_optimization.problems.QuadraticProgram` created
from the vehicle routing problem instance.
"""
mdl = Model(name="Vehicle routing")
n = self._graph.number_of_nodes()
x = {}
for i in range(n):
for j in range(n):
if i != j:
x[(i, j)] = mdl.binary_var(name=f"x_{i}_{j}")
mdl.minimize(
mdl.sum(
self._graph.edges[i, j]["weight"] * x[(i, j)]
for i in range(n)
for j in range(n)
if i != j
)
)
# Only 1 edge goes out from each node
for i in range(n):
if i != self.depot:
mdl.add_constraint(mdl.sum(x[i, j] for j in range(n) if i != j) == 1)
# Only 1 edge comes into each node
for j in range(n):
if j != self.depot:
mdl.add_constraint(mdl.sum(x[i, j] for i in range(n) if i != j) == 1)
# For the depot node
mdl.add_constraint(
mdl.sum(x[i, self.depot] for i in range(n) if i != self.depot) == self.num_vehicles
)
mdl.add_constraint(
mdl.sum(x[self.depot, j] for j in range(n) if j != self.depot) == self.num_vehicles
)
# To eliminate sub-routes
node_list = [i for i in range(n) if i != self.depot]
clique_set = []
for i in range(2, len(node_list) + 1):
for comb in itertools.combinations(node_list, i):
clique_set.append(list(comb))
for clique in clique_set:
mdl.add_constraint(
mdl.sum(x[(i, j)] for i in clique for j in clique if i != j) <= len(clique) - 1
)
op = from_docplex_mp(mdl)
return op
[docs]
def interpret(self, result: OptimizationResult | np.ndarray) -> list[list[list[int]]]:
"""Interpret a result as a list of the routes for each vehicle
Args:
result : The calculated result of the problem
Returns:
A list of the routes for each vehicle
"""
x = self._result_to_x(result)
n = self._graph.number_of_nodes()
idx = 0
edge_list = []
for i in range(n):
for j in range(n):
if i != j:
if x[idx]:
edge_list.append([i, j])
idx += 1
route_list: list[list[list[int]]] = []
for k in range(self.num_vehicles):
i = 0
start = self.depot
route_list.append([])
while i < len(edge_list):
if edge_list[i][0] == start:
if edge_list[i][1] == self.depot:
# If a loop is completed
route_list[k].append(edge_list.pop(i))
break
# Move onto the next edge
start = edge_list[i][1]
route_list[k].append(edge_list.pop(i))
i = 0
continue
i += 1
if edge_list:
route_list.append(edge_list)
return route_list
def _draw_result(
self,
result: OptimizationResult | np.ndarray,
pos: dict[int, np.ndarray] | None = None,
) -> None:
"""Draw the result with colors
Args:
result: The calculated result for the problem
pos: The positions of nodes
"""
import matplotlib as mpl
route_list = self.interpret(result)
nx.draw(self._graph, with_labels=True, pos=pos)
nx.draw_networkx_edges(
self._graph,
pos,
edgelist=self._edgelist(route_list),
width=8,
alpha=0.5,
edge_color=self._edge_color(route_list),
edge_cmap=mpl.colormaps["plasma"],
)
def _edgelist(self, route_list: list[list[list[int]]]):
# Arrange route_list and return the list of the edges for the edge list of
# nx.draw_networkx_edges
return [edge for k in range(len(route_list)) for edge in route_list[k]]
def _edge_color(self, route_list: list[list[list[int]]]):
# Arrange route_list and return the list of the colors of each route
# for edge_color of nx.draw_networkx_edges
return [k / len(route_list) for k in range(len(route_list)) for edge in route_list[k]]
@property
def num_vehicles(self) -> int:
"""Getter of num_vehicles
Returns:
The number of the vehicles
"""
return self._num_vehicles
@num_vehicles.setter
def num_vehicles(self, num_vehicles: int) -> None:
"""Setter of num_vehicles
Args:
num_vehicles: The number of vehicle
"""
self._num_vehicles = num_vehicles
@property
def depot(self) -> int:
"""Getter of depot
Returns:
The node index of the depot where all the vehicles depart
"""
return self._depot
@depot.setter
def depot(self, depot: int) -> None:
"""Setter of depot
Args:
depot: The node index of the depot where all the vehicles depart
"""
self._depot = depot
[docs]
@staticmethod
# pylint: disable=undefined-variable
def create_random_instance( # pylint: disable=too-many-positional-arguments
n: int,
low: int = 0,
high: int = 100,
seed: int | None = None,
num_vehicle: int = 2,
depot: int = 0,
) -> VehicleRouting:
"""Create a random instance of the vehicle routing problem.
Args:
n: the number of nodes.
low: The minimum value for the coordinate of a node.
high: The maximum value for the coordinate of a node.
seed: the seed for the random coordinates.
num_vehicle: The number of the vehicles
depot: The index of the depot node where all the vehicle depart
Returns:
A VehicleRouting instance created from the input information
"""
random.seed(seed)
pos = {i: (random.randint(low, high), random.randint(low, high)) for i in range(n)}
graph = nx.random_geometric_graph(n, np.hypot(high - low, high - low) + 1, pos=pos)
for w, v in graph.edges:
delta = [graph.nodes[w]["pos"][i] - graph.nodes[v]["pos"][i] for i in range(2)]
graph.edges[w, v]["weight"] = np.rint(np.hypot(delta[0], delta[1]))
return VehicleRouting(graph, num_vehicle, depot)