Combinatorial optimization-typical problem-traveling salesman problem

Typical problem and execution method

Traveling salesman problem

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.

Execution method

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

How to use the Google OR-Tools solver

If " method ='ortools' "is added, the solver (approximate solution) of Google OR-Tools is used.

Caution

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

data

Recommended Posts

Combinatorial optimization-typical problem-traveling salesman problem
Combinatorial optimization-typical problem-knapsack problem
Combinatorial optimization-typical problem-n-dimensional packing problem
Combinatorial optimization-Typical problem-Vertex cover problem
Combinatorial optimization-Typical problem-Stable matching problem
Combinatorial optimization-typical problem-generalized allocation problem
Combinatorial optimization-typical problem-maximum matching problem
Combinatorial optimization-Typical problem-Secondary allocation problem
Combinatorial optimization-typical problem-shortest path problem
Combinatorial optimization-typical problem-combinatorial auction problem
Combinatorial optimization-typical problem-maximum flow problem
Combinatorial optimization-typical problem-set cover problem
Combinatorial optimization-typical problem-weight matching problem
Combinatorial optimization-Typical problem-Facility placement problem
Combinatorial optimization-typical problem-job shop problem
Combinatorial optimization-typical problem-maximum cut problem
Combinatorial optimization-typical problem-work scheduling problem
Combinatorial optimization-Typical problem-Minimum spanning tree problem
Combinatorial optimization-Typical problem-Maximum stable set problem
Combinatorial optimization-typical problem-minimum cost flow problem
Combinatorial optimization-typical problem-Chinese postal delivery problem
Combinatorial optimization-Typical problem-Transportation route (delivery optimization) problem
Combinatorial optimization-minimum cut problem
Combinatorial optimization-Typical problem-Facility placement problem with no capacity constraints
About the traveling salesman problem
Combinatorial optimization-typical problems and execution methods
Simulated Annealing and Traveling Salesman Problem
About the Ordered Traveling Salesman Problem