Combinatorial optimization-typical problem-Chinese postal delivery problem

Typical problem and execution method

Chinese postal delivery problem

In an undirected graph, find the smallest path that always passes through all edges once and returns to the original point.

Execution method

usage


Signature: chinese_postman(g_, weight='weight')
Docstring:
Chinese postal delivery problem
input
    g:Graph
    weight:Weight attribute character
output
Distance and vertex list

python


#CSV data
import pandas as pd, networkx as nx, matplotlib.pyplot as plt
from ortoolpy import chinese_postman, graph_from_table, networkx_draw
tbn = pd.read_csv('data/node0.csv')
tbe = pd.read_csv('data/edge0.csv')
g = graph_from_table(tbn, tbe, multi=True)[0]
networkx_draw(g)
plt.show()
print(chinese_postman(g))

result


(36.0, [(0, 4), (4, 5), (5, 4), (4, 3), (3, 2), (2, 3), (3, 0),
        (0, 5), (5, 1), (1, 2), (2, 0), (0, 1), (1, 0)])

image.png

python


# pandas.DataFrame
from ortoolpy.optimization import ChinesePostman
ChinesePostman('data/edge0.csv')[1]
node1 node2 capacity weight
0 0 4 2 2
1 4 5 2 1
2 4 5 2 1
3 3 4 2 4
4 2 3 2 3
5 2 3 2 3
6 0 3 2 2
7 0 5 2 4
8 1 5 2 5
9 1 2 2 5
10 0 2 2 4
11 0 1 2 1
12 0 1 2 1

python


#Random number data
import math, networkx as nx, matplotlib.pyplot as plt
from ortoolpy import chinese_postman, networkx_draw
g = nx.random_graphs.fast_gnp_random_graph(10, 0.3, 1)
g = nx.MultiGraph(g)
pos = nx.spring_layout(g)
for i, j, k in g.edges:
    g.adj[i][j][k]['weight'] = math.sqrt(sum((pos[i] - pos[j])**2))
networkx_draw(g, nx.spring_layout(g))
plt.show()
print(chinese_postman(g))

result


(7.054342373467126, [(0, 4), (4, 8), (8, 6), (6, 9), (9, 7), (7, 4),
                     (4, 9), (9, 3), (3, 7), (7, 5), (5, 4), (4, 6),
                     (6, 1), (1, 2), (2, 5), (5, 1), (1, 0)])

image.png

data

Recommended Posts

Combinatorial optimization-typical problem-Chinese postal delivery problem
Combinatorial optimization-Typical problem-Transportation route (delivery optimization) 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-bin packing problem
Combinatorial optimization-Typical problem-Secondary allocation 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-traveling salesman 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-minimum cut problem
Codeiq milk delivery route problem