-
Notifications
You must be signed in to change notification settings - Fork 0
/
floyd_path.py
96 lines (89 loc) · 3.57 KB
/
floyd_path.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import networkx as nx
from global_parameters import get_value
from collections import OrderedDict
def floyd_warshall(distance):
'''
:param distance: distance model with maxsize
:return: shortest_dis, predecessors
'''
G = nx.DiGraph(distance)
shortest_dis = nx.floyd_warshall(G)
predecessors, _ = nx.floyd_warshall_predecessor_and_distance(G)
return shortest_dis, predecessors
def get_route(source, target):
predecessors = get_value('predecessors')
route = nx.reconstruct_path(source, target, predecessors)
return route
def get_distance(source, target):
shortest_dis = get_value('shortest_dis')
return shortest_dis[source][target]
def plan_route(loc, re_to_pick, isEmpty, onboard):
# REQUESTS = get_value('REQUESTS')
DATA = get_value('DATA')
origin = []
destination = []
if len(re_to_pick) == 1:
re = re_to_pick[0]
origin = DATA.loc[re, 'PULocationID']
if isEmpty:
destination = DATA.loc[re, 'DOLocationID']
return_route = []
return_route += get_route(loc, origin)
return_route.pop(-1)
return_route += get_route(origin, destination)
return return_route.pop(0)
else:
destination.append(DATA.loc[onboard[0], 'DOLocationID'])
destination.append(DATA.loc[re, 'DOLocationID'])
route_all = [[origin, destination[0], destination[1]],
[origin, destination[1], destination[0]]]
s = loc
dis_all = {}
for i in range(len(route_all)):
route = route_all[i]
dis = 0
for grid in route:
dis += get_distance(s, grid)
s = grid
dis_all[i] = dis
dis_all_sorted = OrderedDict(sorted(dis_all.items(), key=lambda t: t[1]))
key = list(dis_all_sorted.keys())[0]
temp_route = route_all[key]
return_route = []
return_route += get_route(loc, temp_route[0])
return_route.pop(-1)
return_route += get_route(temp_route[0], temp_route[1])
return_route.pop(-1)
return_route += get_route(temp_route[1], temp_route[2])
return return_route.pop(0)
if len(re_to_pick) > 1:
for re in re_to_pick:
origin.append(DATA.loc[re, 'PULocationID'])
destination.append(DATA.loc[re, 'DOLocationID'])
route_all = [[origin[0], origin[1], destination[0], destination[1]],
[origin[1], origin[0], destination[1], destination[0]],
[origin[0], origin[1], destination[1], destination[0]],
[origin[1], origin[0], destination[0], destination[1]]]
s = loc
dis_all = {}
for i in range(len(route_all)):
route = route_all[i]
dis = 0
for grid in route:
dis += get_distance(s, grid)
s = grid
dis_all[i] = dis
dis_all_sorted = OrderedDict(sorted(dis_all.items(),key=lambda t:t[1]))
key = list(dis_all_sorted.keys())[0]
temp_route = route_all[key]
return_route = []
return_route += get_route(loc, temp_route[0])
return_route.pop(-1)
return_route += get_route(temp_route[0], temp_route[1])
return_route.pop(-1)
return_route += get_route(temp_route[1], temp_route[2])
return_route.pop(-1)
return_route += get_route(temp_route[2], temp_route[3])
return return_route.pop(0)