Typical problem and execution method
A graph consisting of a set of n points (city) $ V $ $ G = (V, E) $ and a circuit that goes through all the points once when the cost for each side is given. Find the one that minimizes the sum of costs (such as distance) on the sides.
usage
Signature: tsp(nodes, dist=None, method=None)
Docstring:
Traveling salesman problem
input
nodes:point(Coordinates when dist is not specified)List of
dist: (i,j)A dictionary with the key and distance as the value
method:Method of calculation(ex. 'ortools')
output
Distance and point number list
python
from ortoolpy import tsp
tsp([(2, 0), (1, 2), (0, 1), (3, 1), (2, 2)])[1]
result
[0, 2, 1, 4, 3]
python
# pandas.DataFrame
from ortoolpy.optimization import Tsp
Tsp('data/node1.csv')[1]
| id | x | y | demand | |
|---|---|---|---|---|
| 0 | 0 | 5 | 1 | 0 |
| 3 | 3 | 1 | 0 | 1 |
| 5 | 5 | 0 | 4 | 1 |
| 2 | 2 | 1 | 5 | 1 |
| 1 | 1 | 8 | 5 | 1 |
| 4 | 4 | 8 | 0 | 1 |
If " method ='ortools' "is added, the solver (approximate solution) of Google OR-Tools is used.
--Install Google OR-Tools with pip install or tools.
--The element of the distance matrix (dist) should be an integer.
python
import numpy as np
from scipy.spatial import distance
from ortoolpy import tsp
np.random.seed(0)
nodes = np.random.rand(20, 2) * 1000 #20 cities
dist = distance.cdist(nodes, nodes).astype(int) #Distance matrix
print(tsp(nodes, dist, method='ortools')) #Approximate solution
print(tsp(nodes, dist)) #Exact solution (reference)
The sum of costs (4099) is larger than the exact solution (4072.0) on the second line.
Result (sum of costs and list of point numbers)
(4099, [0, 11, 3, 6, 9, 10, 19, 4, 5, 18, 1, 14, 7, 17, 12, 8, 13, 15, 2, 16])
(4072.0, [0, 2, 16, 14, 7, 17, 12, 8, 13, 15, 11, 3, 6, 9, 10, 19, 4, 5, 1, 18])
Recommended Posts