-
Notifications
You must be signed in to change notification settings - Fork 0
/
travel_scheduling.py
231 lines (192 loc) · 7.87 KB
/
travel_scheduling.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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
import pandas as pd
import numpy as np
from tsp import GUI
GUI()
print("Running...")
df_city_site = pd.read_csv("site_city.csv", encoding="big5")
site_city_dict = {}
city_site_dict = {}
# 創建 dict 是縣市對應裡面的所有景點
for i in range(len(df_city_site)):
site_name = df_city_site.iloc[i][1]
city_name = df_city_site.iloc[i][0]
site_city_dict[site_name] = city_name
try:
city_site_dict[city_name[:2]].append(site_name)
except:
city_site_dict[city_name[:2]] = [site_name]
city_order = [ '基隆', '臺北', '新北', '桃園', '新竹', '苗栗', '臺中', '南投', '彰化',
'雲林', '嘉義', '臺南', '高雄', '屏東', '臺東', '花蓮', '宜蘭']
# read file
df_site_distance = pd.read_csv("travel_sites.csv", encoding="big5")
# 把第一行當作 index
df_site_distance.set_index("Unnamed: 0", inplace=True)
# 去掉 nan 值(有些列是空的的狀況)
df_site_distance = df_site_distance.dropna(axis=0, how="any")
df_site_distance = df_site_distance.dropna(axis=1, how="all")
'''
# 取值方法
print(df_site_distance.loc['101大樓', '木柵動物園'])
print(df_site_distance.iloc[0, 1])
'''
# 所有景點的 list
site_list = list(df_site_distance.keys())
# - - - - #
import random
from pulp import *
import random
import json
# 讀檔
satisfaction = []
with open("data.txt") as data_file:
json_data = json.load(data_file)
for place in site_list:
if(place in json_data):
satisfaction.append(int(json_data[place]))
else:
print("place " + place + " not in json file.")
buget = float(json_data["預算"]) / 2.6
# print(len(satisfaction))
# satisfaction = list(np.zeros(len(df_site_distance.keys())))
# # create 隨機滿意度變數 list
# for i in range(len(satisfaction)):
# satisfaction[i] = round(random.uniform(0, 10), 1) # 取小數兩位
# print(satisfaction)
# create 2-D variables list
length = len(df_site_distance.keys())
# create a new model
prob = pulp.LpProblem("travel routines scheduling", pulp.LpMaximize)
# decision variable
variable_list = []
for num_source in range(length):
tmp_list = [] # 因為是二維的,所以先建好一維再依序加入
for num_destination in range(length):
variable_name = site_list[num_source] + "-" + site_list[num_destination]
tmp = pulp.LpVariable(variable_name, lowBound=0, cat="Binary")
tmp_list.append(tmp)
# infinite distance (A -> A)
if(num_source == num_destination):
df_site_distance.iloc[num_source, num_destination] = float("inf")
variable_list.append(tmp_list)
'''
# 變數名稱查看
print(variable_list[0][:10])
print(len(satisfaction))
print("finish")
'''
# objective(滿意度最大化)
tmp_obj = 0
# print(length)
for i in range(length):
tmp_obj += lpSum([satisfaction[j] * variable_list[i][j] for j in range(length)])
prob += tmp_obj
# constraint
for num in range(length):
# 景點行列各別總和等於 0 或 1 variables_list
prob += lpSum([variable_list[num][j] for j in range(length)]) <= 1 # column
prob += lpSum([variable_list[j][num] for j in range(length)]) <= 1 # row
# 景點有進有出 (### 但是還沒處理完三個以上景點的 loop ###)
tmp1, tmp2 = 0, 0
for j in range(length):
tmp1 += variable_list[num][j]
tmp2 += variable_list[j][num]
prob += (variable_list[num][j] + variable_list[j][num] <= 1) # 避免兩個景點之間互相抵達
prob += (tmp1 == tmp2)
# 每個縣市都要逛到(有進有出):從外縣市、離開此縣市,縣市之間有順序性
for city in city_site_dict:
flag = True
for next_city in city_site_dict:
city_tmp_sum_in, city_tmp_sum_out = 0, 0
if(next_city == city):
continue
# 某個縣市的所有景點針對另一個縣市所有的景點進出計算(跨縣市)
for site in city_site_dict[city]:
index_site = site_list.index(site)
city_tmp_sum_out += lpSum(variable_list[index_site][site_list.index(next_site)]
for next_site in city_site_dict[next_city])
city_tmp_sum_in += lpSum(variable_list[site_list.index(next_site)][index_site]
for next_site in city_site_dict[next_city])
num_in, num_out = 0, 0
if(next_city == city_order[(city_order.index(city)+1)%len(city_order)]):
num_out = 1
if(city == city_order[(city_order.index(next_city)+1)%len(city_order)]):
num_in = 1
prob += (city_tmp_sum_in == num_in)
prob += (city_tmp_sum_out == num_out)
# 距離成本
distance = 0
for i in range(length):
for j in range(length):
if(i == j):
distance += 1000 * variable_list[i][j]
continue
distance += df_site_distance.iloc[i, j] * variable_list[i][j]
prob += (distance <= float(buget))
import itertools
# 縣市裡面內部景點自己繞圈圈(目前設定到 6 個)
for city in city_site_dict:
site_list_in_city = city_site_dict[city]
for numbers in range(2, 6):
if(len(site_list_in_city) < numbers):
continue
permutation_list = list(itertools.permutations(site_list_in_city, numbers))
for num in range(len(permutation_list)):
tmp_addition = 0
for index in range(numbers):
site_1 = site_list.index(permutation_list[num][index])
site_2 = site_list.index(permutation_list[num][(index+1)%numbers])
tmp_addition += variable_list[site_1][site_2]
prob += (tmp_addition <= numbers - 1) # 避免景點之間互相抵達
# print("finish")
prob.solve()
print("Status:", LpStatus[prob.status])
total = 0
distance_total = 0
bool_list = [0] * len(site_list) # 判斷走幾次
global final_dict
final_dict = {}
for site in site_list:
final_dict[site] = ["", ""]
# 計算總距離的 function + 存入景點進出狀況到 final_dict
def add(routine, distance_total, bool_list):
routine = routine.split("_")
bool_list[site_list.index(routine[0])] += 1
bool_list[site_list.index(routine[1])] += 1
#print(df_site_distance.loc[routine[0], routine[1]])
distance_total += df_site_distance.loc[routine[0], routine[1]]
final_dict[routine[0]][1] = routine[1] # 抵達
final_dict[routine[1]][0] = routine[0] # 出發
return distance_total
final_site_list = []
for v in prob.variables():
if(int(v.varValue) == 1):
#print(v.name, "=", int(v.varValue))
total += 1
distance_total = add(str(v.name), distance_total, bool_list)
final_site_list.append(str(v.name).split("_")[0])
# 把景點順序印出來
first = final_site_list[0] # 有在路線當中隨便一個景點丟進來
this_site = first
next_site = final_dict[first][1]
final_site_list.remove(first)
print(first + " -> " + next_site)
this_site = next_site
next_site = final_dict[this_site][1]
counting = 0
while(this_site != first):
print(this_site + " -> " + next_site)
final_site_list.remove(this_site)
this_site = next_site
next_site = final_dict[this_site][1]
counting += 1
# print("count:", counting)
# print(final_site_list) # 剩下有問題沒接起來的景點(自己有小 loop 的)
'''
比如範例裡面臺南的 '赤崁樓', '林百貨', '國華街' 三個自己在小圈圈
'''
print('obj=',round(value(prob.objective), 2)) # 滿意度
print("total sites:", total) # 經過總景點數
print("distance:", distance_total) # 總里程
# print(bool_list)
final_site_list = set(final_site_list)
# print(final_site_list, len(final_site_list))