Source code for qiskit_optimization.applications.vehicle_routing

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