dwave.optimization.generators.traveling_salesperson#

traveling_salesperson(distance_matrix: _SupportsArray[dtype[Any]] | _NestedSequence[_SupportsArray[dtype[Any]]] | bool | int | float | complex | str | bytes | _NestedSequence[bool | int | float | complex | str | bytes]) Model[source]#

Generate a model encoding a traveling-salesperson problem.

The traveling salesperson is, for a given a list of cities and distances between each pair of cities, to find the shortest possible route that visits each city exactly once and returns to the city of origin.

Parameters:

distance_matrix – A symmetric array-like where distance_matrix[n, m] is the distance between city n and m. Represents the (known and constant) distances between every possible pair of cities: in real-world problems, such a matrix can be generated from an application with access to an online map. Note that distance_matrix is symmetric because the distance between city n to city m is the same regardless of the direction of travel.

Returns:

A model encoding the traveling-salesperson problem.

Typically, solver performance strongly depends on the size of the solution space for your modelled problem: models with smaller spaces of feasible solutions tend to perform better than ones with larger spaces. A powerful way to reduce the feasible-solutions space is by using variables that act as implicit constraints. This is analogous to judicious typing of a variable to meet but not exceed its required assignments: a Boolean variable, x, has a solution space of size 2 (\(\{True, False\}\)) while an integer variable, i, might have a solution space of over 4 billion values.

The model generated uses a dwave.optimization.Model.list class as the decision variable being optimized, with permutations of this ordered list representing possible itineraries through the required cities.

The dwave.optimization.Model.list class used to represent the decision variable as an ordered list is implicitly constrained in the possible values that can be assigned to it; for example, compare a model representing five cities as five variables of type int, \(i_{Rome}, i_{Turin}, i_{Naples}, i_{Milan}, i_{Genoa}\), where \(i_{Rome} = 2\) means Rome is the third city visited, versus a model using an ordered list, \((city_0, city_1, city_2, city_3, city_4)\). The first model must explicitly constrain solutions to those that select a value between 0 to 4 for each decision variable with no repetitions; such constraints are implicit to the ordered-list variable.

The objective is to minimize the distance traveled. Permutations of indices \((0, 1, 2, ...)\) that order distance_matrix represent itineraries that travel from list-element \(i\) to list-element \(i+1\) for \(i \in [0, N-1]\), where \(N\) is the length of the list (and the number of cities). Additionally, the problem requires a return to the city of origin (first element of the list) from the last city visited (the last element of the list).