[PYTHON] Traveling salesman problem practice collection ③ ~ Non-random map edition ~
Traveling Salesman Problem Practice Collection ① ~ Full Search ~ Traveling Salesman Problem Practice Collection (2) ~ Nearest Neighbor Search Method ~
Last time, the approximate solution of TSP was obtained while suppressing the amount of calculation by the neighborhood search method. It would be more fun to do something like finding a route on an actual map.
Non-random map
About Prefectural Office Location Map from latitude and longitude.
Coordinate_map
While using csv.reader, define a function Coordinate_map that picks up latitude and longitude and generates City.
def lines(text): return text.strip().splitlines()
def Coordinate_map(lines, delimiter=',', lat_col=0, long_col=1, lat_scale=91, long_scale=80):
"""Make a set of cities from the text.
Longitude / latitude_scale,lat_Treat as x · y Cartesian coordinates from scale.
The source can be a file or a list of sentences."""
return frozenset(City(long_scale * float(row[long_col]),
lat_scale * float(row[lat_col]))
for row in csv.reader(lines, delimiter=delimiter, skipinitialspace=True))
lat_col = 0 and long_col = 1 are parameters that select which part of the given list should be included as latitude and longitude. In addition, lat_scale and long_scale are parameters of the degree of separation when converting from latitude and longitude to a pseudo xy Cartesian coordinate system. For example, the difference of 1 degree in longitude near the equator and the difference of 1 degree in longitude near the pole are different. Also, as the north latitude increases, it moves north, but when the south latitude increases, it moves south. When you are in the west, make fine adjustments by adding minus.
Prefectural office location map
As mentioned above, set the map from the information of Prefectural Office Location. Set JPN_map.
JPN_map
JPN_map = Coordinate_map(lines("""
Hokkaido,Sapporo,43.06417,141.34694
Aomori Prefecture,Aomori City,40.82444,140.74
Iwate Prefecture,Morioka City,39.70361,141.1525
Miyagi Prefecture,Sendai city,38.26889,140.87194
Akita,Akita City,39.71861,140.1025
Yamagata Prefecture,Yamagata City,38.24056,140.36333
Fukushima Prefecture,Fukushima City,37.75,140.46778
Ibaraki Prefecture,Mito City,36.34139,140.44667
Tochigi Prefecture,Utsunomiya City,36.56583,139.88361
Gunma Prefecture,Maebashi,36.39111,139.06083
Saitama,Saitama City,35.85694,139.64889
Chiba,Chiba,35.60472,140.12333
Tokyo,Shinjuku ward,35.68944,139.69167
Kanagawa Prefecture,Yokohama City,35.44778,139.6425
Niigata Prefecture,Niigata City,37.90222,139.02361
Toyama Prefecture,Toyama City,36.69528,137.21139
Ishikawa Prefecture,Kanazawa,36.59444,136.62556
Fukui prefecture,Fukui City,36.06528,136.22194
Yamanashi Prefecture,Kofu City,35.66389,138.56833
Nagano Prefecture,Nagano city,36.65139,138.18111
Gifu Prefecture,Gifu City,35.39111,136.72222
Shizuoka Prefecture,Shizuoka City,34.97694,138.38306
Aichi prefecture,Nagoya city,35.18028,136.90667
Mie Prefecture,Tsu city,34.73028,136.50861
Shiga Prefecture,Otsu City,35.00444,135.86833
Kyoto,Kyoto City,35.02139,135.75556
Osaka,Osaka City,34.68639,135.52
Hyogo prefecture,Kobe City,34.69139,135.18306
Nara Prefecture,Nara city,34.68528,135.83278
Wakayama Prefecture,Wakayama City,34.22611,135.1675
Tottori prefecture,Tottori City,35.50361,134.23833
Shimane Prefecture,Matsue,35.47222,133.05056
Okayama Prefecture,Okayama City,34.66167,133.935
Hiroshima Prefecture,Hiroshima city,34.39639,132.45944
Yamaguchi Prefecture,Yamaguchi City,34.18583,131.47139
Tokushima Prefecture,Tokushima City,34.06583,134.55944
Kagawa Prefecture,Takamatsu City,34.34028,134.04333
Ehime Prefecture,Matsuyama City,33.84167,132.76611
Kochi Prefecture,Kochi City,33.55972,133.53111
Fukuoka Prefecture,Fukuoka City,33.60639,130.41806
Saga Prefecture,Saga City,33.24944,130.29889
Nagasaki Prefecture,Nagasaki City,32.74472,129.87361
Kumamoto Prefecture,Kumamoto City,32.78972,130.74167
Oita Prefecture,Oita City,33.23806,131.6125
Miyazaki prefecture,Miyazaki City,31.91111,131.42389
Kagoshima prefecture,Kagoshima City,31.56028,130.55806
Okinawa Prefecture,Naha city,26.2125,127.68111
"""), delimiter=',', lat_col=2, long_col=3,lat_scale=91, long_scale=80)
plot_lines(JPN_map, 'bo')
it is a good feeling. When I solve it
plot_tsp(repeated_altered_nn_tsp, JPN_map)
47 city tour with length 4830.0 in 0.125 secs for repeated_altered_nn_tsp
It feels good. However, Japan is long and narrow, so I'm not surprised.
Fukuoka Prefecture Municipal Offices / Offices
I would like to find the shortest route from Fukuoka Prefecture Municipalities Offices / Offices to all Fukuoka Prefecture Municipalities Offices / Offices.
FO
FO = lines("""
Fukuoka Prefectural Government 130.25.05 33.36.23
Kitakyushu City Hall 130.52.31 33.53.00
Moji Ward Office 130.57.35 33.56.28
Wakamatsu Ward Office 130.48.40 33.54.20
Tobata Ward Office 130.49.47 33.53.36
Kokurakita Ward Office 130.52.25 33.52.51
Kokuraminami Ward Office 130.53.05 33.50.47
Yahatahigashi Ward Office 130.48.43 33.51.49
Yahatanishi Ward Office 130.45.51 33.51.59
Fukuoka City Hall 130.24.06 33.35.24
Higashi Ward Office 130.25.03 33.37.04
Hakata Ward Office 130.24.54 33.35.29
Chuo Ward Office 130.23.35 33.35.21
Minami Ward Office 130.25.36 33.33.42
Nishi Ward Office 130.19.23 33.34.58
Jonan Ward Office 130.22.12 33.34.33
Sawara Ward Office 130.20.54 33.34.55
Omuta City Hall 130.26.46 33.01.49
Kurume City Hall 130.30.30 33.19.10
Nogata City Hall 130.43.47 33.44.38
Iizuka City Hall 130.41.28 33.38.47
Tagawa City Hall 130.48.22 33.38.20
Yanagawa City Hall 130.24.22 33.09.47
Yame City Hall 130.33.28 33.12.43
Chikugo City Hall 130.30.08 33.12.44
Okawa City Hall 130.23.02 33.12.24
Yukuhashi City Hall 130.58.59 33.43.43
Buzen City Hall 131.07.49 33.36.42
Nakama City Hall 130.42.33 33.49.00
Ogori City Hall 130.33.20 33.23.47
Chikushino City Hall 130.31.34 33.29.15
Kasuga City Hall 130.28.13 33.31.58
Onojo City Hall 130.28.44 33.32.11
Munakata City Hall 130.32.26 33.48.20
Dazaifu City Hall 130.31.26 33.30.46
Koga City Hall 130.28.12 33.43.44
Fukutsu City Hall 130.29.28 33.46.01
Ukiha City Hall 130.45.18 33.20.50
Miyawaka City Hall 130.40.00 33.43.25
Kama City Hall 130.42.42 33.33.48
Asakura City Hall 130.39.56 33.25.24
Miyama City Hall 130.28.29 33.09.09
Itoshima City Hall 130.11.44 33.33.26
Nakagawa City Hall 130.25.20 33.29.58
Umi Town Hall 130.30.40 33.34.04
Sasaguri Town Hall 130.31.35 33.37.26
Shime Town Hall 130.28.47 33.35.29
Sue Town Hall 130.30.26 33.35.14
Shingu Town Hall 130.26.48 33.42.55
Hisayama Town Hall 130.30.00 33.38.48
Kasuya Town Hall 130.28.50 33.36.39
Ashiya Town Hall 130.39.50 33.53.38
Mizumaki Town Hall 130.41.41 33.51.17
Okagaki Town Hall 130.36.41 33.51.13
Onga Town Hall 130.40.06 33.50.53
Kotake Town Hall 130.42.46 33.41.33
Kurate Town Hall 130.40.27 33.47.31
Keisen Town Hall 130.40.41 33.34.44
Chikuzen Town Hall 130.35.43 33.27.25
Toho Village Office 130.52.12 33.23.50
Tachiarai Town Hall 130.37.21 33.22.21
Oki Town Hall 130.26.23 33.12.38
Hirokawa Town Hall 130.33.05 33.14.29
Kawara Town Hall 130.50.50 33.40.05
Soeda Town Hall 130.51.15 33.34.18
Itoda Town Hall 130.46.45 33.39.10
Kawasaki Town Hall 130.48.55 33.36.00
Oto Town Hall 130.51.13 33.36.44
Akamura Office 130.52.15 33.37.00
Fukuchi Town Hall 130.46.48 33.41.00
Kanda Town Hall 130.58.50 33.46.34
Miyako Town Hall 130.55.14 33.41.57
Yoshitomi Town Hall 131.10.34 33.36.10
Koge Town Office 131.09.52 33.34.42
Chikujo Town Hall 131.03.22 33.39.22
""")
Coordinate_map2 First, prepare a function that converts a 60-ary number to a decimal number.
def sixty2ten(x):
x_list = x.split('.')
t = float(x_list[0]) + float(x_list[1]) / 60 + float(x_list[2]) / 60 / 60
return t
Define Coordinate_map2.
def Coordinate_map2(lines, delimiter=' ', lat_col=2, long_col=1, lat_scale=91000, long_scale=81000):
return frozenset(City(long_scale * sixty2ten(row[long_col]),
lat_scale * sixty2ten(row[lat_col]))
for row in csv.reader(lines, delimiter=delimiter, skipinitialspace=True))
FO_map = Coordinate_map2(FO)
plot_tsp(repeated_altered_nn_tsp,FO_map)
75 city tour with length 425110.1 in 0.262 secs for repeated_altered_nn_tsp
Yeah, it feels good
Which city to visit
However, I don't know what order to actually go around. Until now, the coordinates were sorted, but by assigning numbers to the points of the coordinates and deciding which number to visit, the city names to be visited can be called.
For that purpose, it is necessary to redefine the functions set so far. It is assumed that the city name and the latitude mildness of the city are continuously input to the original data. Extract the information on the latitude of the city to mat_lat_long, distance2
def distance2(A, B):
global map_lat_long
"Distance between two points"
return abs(map_lat_long[A] - map_lat_long[B])
tour_length2
def tour_length2(tour):
"Add up the distances between two points along the path."
return sum(distance2(tour[i], tour[i-1])
for i in range(len(tour)))
This time, define up to the point where altered_nn_tsp can be used.
nn_tsp2
def nn_tsp2(cities):
"""Start the route from one city and proceed to the nearest city from that city,
Follow the route from the next city to the next, unvisited city."""
start = 0
tour = [start]
unvisited = set(range(1,len(cities)))
while unvisited:
C = nearest_neighbor2(tour[-1], unvisited)
tour.append(C)
unvisited.remove(C)
return tour
def nearest_neighbor2(A, cities):
"Find the city closest to A."
return min(cities, key=lambda c: distance2(c, A))
altered_nn_tsp2
def reverse_segment_if_better2(tour, i, j):
"If the segment is reversed[i:j]If the path is shortened by, reverse it."
#Original route[...A-B...C-D...]Against B...Reversed C[...A-C...B-D...]think of.
A, B, C, D = tour[i-1], tour[i], tour[j-1], tour[j % len(tour)]
if distance2(A, B) + distance2(C, D) > distance2(A, C) + distance2(B, D):
tour[i:j] = reversed(tour[i:j])
def alter_tour2(tour):
"Try to make the path shorter by reversing the segments."
original_length = tour_length2(tour)
for (start, end) in all_segments2(len(tour)):
reverse_segment_if_better2(tour, start, end)
# If we made an improvement, then try again; else stop and return tour.
#If there is an improvement, repeat it again, otherwise it ends and outputs a tour.
if tour_length2(tour) < original_length:
return alter_tour2(tour)
return tour
def all_segments2(N):
"Represents all segments for a path of length N(Start point, end point)Output a set of"
return [(start, start + length)
for length in range(N, 2-1, -1)
for start in range(N - length + 1)]
def altered_nn_tsp2(cities):
"Run nearest neighbor TSP algorithm, and alter the results by reversing segments."
return alter_tour2(nn_tsp2(cities))
drawing
#drawing
def plot_lines2(points, style='bo-'):
"Plot lines to connect a series of points."
global map_lat_long
plt.plot([map_lat_long[i].x for i in points], [map_lat_long[i].y for i in points], style)
plt.axis('scaled'); plt.axis('off')
def plot_tour2(tour):
"Plot the cities as circles and the tour as lines between them."
plot_lines2(list(tour) + [tour[0]])
Run
JPN_map2
JPN_map2 = lines("""
Hokkaido,Sapporo,43.06417,141.34694
Aomori Prefecture,Aomori City,40.82444,140.74
Iwate Prefecture,Morioka City,39.70361,141.1525
Miyagi Prefecture,Sendai city,38.26889,140.87194
Akita,Akita City,39.71861,140.1025
Yamagata Prefecture,Yamagata City,38.24056,140.36333
Fukushima Prefecture,Fukushima City,37.75,140.46778
Ibaraki Prefecture,Mito City,36.34139,140.44667
Tochigi Prefecture,Utsunomiya City,36.56583,139.88361
Gunma Prefecture,Maebashi,36.39111,139.06083
Saitama,Saitama City,35.85694,139.64889
Chiba,Chiba,35.60472,140.12333
Tokyo,Shinjuku ward,35.68944,139.69167
Kanagawa Prefecture,Yokohama City,35.44778,139.6425
Niigata Prefecture,Niigata City,37.90222,139.02361
Toyama Prefecture,Toyama City,36.69528,137.21139
Ishikawa Prefecture,Kanazawa,36.59444,136.62556
Fukui prefecture,Fukui City,36.06528,136.22194
Yamanashi Prefecture,Kofu City,35.66389,138.56833
Nagano Prefecture,Nagano city,36.65139,138.18111
Gifu Prefecture,Gifu City,35.39111,136.72222
Shizuoka Prefecture,Shizuoka City,34.97694,138.38306
Aichi prefecture,Nagoya city,35.18028,136.90667
Mie Prefecture,Tsu city,34.73028,136.50861
Shiga Prefecture,Otsu City,35.00444,135.86833
Kyoto,Kyoto City,35.02139,135.75556
Osaka,Osaka City,34.68639,135.52
Hyogo prefecture,Kobe City,34.69139,135.18306
Nara Prefecture,Nara city,34.68528,135.83278
Wakayama Prefecture,Wakayama City,34.22611,135.1675
Tottori prefecture,Tottori City,35.50361,134.23833
Shimane Prefecture,Matsue,35.47222,133.05056
Okayama Prefecture,Okayama City,34.66167,133.935
Hiroshima Prefecture,Hiroshima city,34.39639,132.45944
Yamaguchi Prefecture,Yamaguchi City,34.18583,131.47139
Tokushima Prefecture,Tokushima City,34.06583,134.55944
Kagawa Prefecture,Takamatsu City,34.34028,134.04333
Ehime Prefecture,Matsuyama City,33.84167,132.76611
Kochi Prefecture,Kochi City,33.55972,133.53111
Fukuoka Prefecture,Fukuoka City,33.60639,130.41806
Saga Prefecture,Saga City,33.24944,130.29889
Nagasaki Prefecture,Nagasaki City,32.74472,129.87361
Kumamoto Prefecture,Kumamoto City,32.78972,130.74167
Oita Prefecture,Oita City,33.23806,131.6125
Miyazaki prefecture,Miyazaki City,31.91111,131.42389
Kagoshima prefecture,Kagoshima City,31.56028,130.55806
Okinawa Prefecture,Naha city,26.2125,127.68111
""")
map_lat_long = Coordinate_map2(JPN_map2, delimiter=',', lat_col=2, long_col=3,lat_scale=91, long_scale=80)
map = list((row[1])
for row in csv.reader(JPN_map2, delimiter=','))
ant = altered_nn_tsp2(map_lat_long)
for i in range(len(map_lat_long)):
print(map[ant[i]])
plot_tour2(ant)
result
You can get the following list of prefectural office locations.
Prefectural office location patrol order list
Kanazawa Toyama City Nagano city Niigata City Akita City Aomori City Sapporo Morioka City Sendai city Yamagata City Fukushima City Utsunomiya City Mito City Chiba Yokohama City Shinjuku ward Saitama City Maebashi Kofu City Shizuoka City Nagoya city Gifu City Tsu city Nara city Otsu City Kyoto City Osaka City Kobe City Wakayama City Tokushima City Kochi City Miyazaki City Kagoshima City Naha city Nagasaki City Saga City Fukuoka City Kumamoto City Oita City Yamaguchi City Hiroshima city Matsuyama City Takamatsu City Okayama City Matsue Tottori City Fukui CitySummary
Solved the traveling salesman problem on non-random maps. There is room for improvement in the method of outputting the result after associating the city coordinates with the city name. Also, in reality, the path is a simple coordinate distance and does not represent the actual distance. The issue is how to reflect the expression of the distance between two points (time distance, distance as the magnitude of cost, etc.).
Recommended Posts