Jordi van Selm
Reputation: 75
Improving mTSP based on Greedy approach using Simulated Annealing
I am trying to improve an mTSP where we have 'unlimited' salesman, representing the vehicles that need to pick up goods.
There are 2 main constraints:
The addresses close at a certain time. So a route cannot continue driving to an address after it has been closed.
The capacity of the vehicles cannot be exceeded.
I decided to apply a 'greedy' approach I came up with.
I am using a time matrix as input. I convert the matrix to a table with every pair of points and the time between them. Then I sort in ascending order and start at the top, the smallest time between two given addresses.
Then I apply these scenarios:
- Scenario 1: Both of the points (from the pair) are new and so the pair can be added as a whole.
- Scenario 2: One of the points has already been added. The other point is not. We need to check if the other point can be added to the route where the other point is already in.
- Scenario 3: Both points are already added but are separated. We need to check if the routes can joined.
During the iterative process, it constantly checks if the constraints are not violated. This is the 'core' of my algorithm.
This yields the following output, where you will see nested lists representing the order in which the addresses (referenced with indices) need to be visited. Always starting and ending at the hub (which is not included in the output).
[[7, 15],
[11, 26, 4, 12, 27, 24],
[22, 21, 14],
[18, 20, 13, 25],
[9, 5],
[28, 10, 19],
[8, 23, 17],
[16],
[6]]
Then I apply my objective function once again to see how well this solution is. My objective function is given by the distance driven (I also have a distance matrix), the fuel consumption, and the drivers' wage. (hours x hourly wage) Now, I will come to my question. I want to explore algorithms/(meta)heuristics that can improve this solution. I opted for Simulated Annealing but the results I got (using ChatGPT) were very bad. It even worsened the score and sometimes oscillated between scores.
Now, my question is; What should I do to improve the score knowing that I need to check if a route is feasible using the constraints?
I will provide my code below. Please note that this also requires the data from every address, but I would like to focus on the algorithms that I should apply.
def start_solution(chosen_day,index_hub):
extract = set(chosen_day['index_locatie'].to_list())
extract = list(extract)
time_matrix_extract = time_matrix_pd.iloc[extract,extract]
# This part is only for converting the time matrix to a table with pairs (location X to Y with time).
# I found that there's a much faster solution, but I will keep this for now.
pairs = []
non_zero_min = 0
pairs_copy = []
while non_zero_min<10**10:
non_zero_min = time_matrix_extract[time_matrix_extract > 0].min().min() # Find the minimum non-zero value
min_position = time_matrix_extract[time_matrix_extract == non_zero_min].stack().index[0]
time_matrix_extract.loc[min_position[0],min_position[1]] = 10**10
min_position = numpy.array(list(min_position)).tolist()
postion_in_matrix = [int(i) for i in min_position]
time_between_x_y = int(non_zero_min)
if time_between_x_y !=10**10:
pairs_copy.append([postion_in_matrix,time_matrix_extract])
done_ind = []
done_merged = []
all_points = set(extract)
i = 1
done_merged_total = []
while len(all_points - set(done_ind))>0 and i<len(pairs_copy):
total = 0
total_n = []
for t in pairs_copy[i][0]:
if t in done_ind:
total+=1
total_n.append(t)
# Scenario 1: Both of the points (from the pair) are new and so the pair can be added as a whole.
if total == 0:
test = pairs_copy[i][0]
route_temp = {}
if check(chosen_day,test,cap_auto):
objf = objective_function(diesel_price,consumption,test,hourly_wage,index_hub)
route_temp[objf] = test
if check(chosen_day,test[::-1],cap_auto):
objf = objective_function(diesel_price,consumption,test[::-1],hourly_wage,index_hub)
route_temp[objf] = test[::-1]
if len(route_temp)>0:
test = route_temp[min(route_temp)]
done_merged.append(test)
done_ind.extend(test)
# Scenario 2: One of the points is already added. The other point not. We need to check if the other point can be added to the route where the other point is already in.
elif total == 1:
total_n = total_n[0]
for y in range(len(done_merged)):
if total_n in done_merged[y]:
indexx = done_merged[y].index(total_n)
insert_point = list(set(pairs_copy[i][0])-set([total_n]))
insert_point = insert_point[0]
if indexx == 0:
test = done_merged[y].copy()
test.insert(indexx,insert_point)
route_temp = {}
if check(chosen_day,test,cap_auto):
objf = objective_function(diesel_price,consumption,test,hourly_wage,index_hub)
route_temp[objf] = test
if check(chosen_day,test[::-1],cap_auto):
objf = objective_function(diesel_price,consumption,test[::-1],hourly_wage,index_hub)
route_temp[objf] = test[::-1]
if len(route_temp)>0:
test = route_temp[min(route_temp)]
done_merged.remove(done_merged[y])
done_merged.append(test)
done_ind.extend(test)
elif indexx == len(done_merged[y])-1:
test = done_merged[y].copy()
test.insert(indexx+1,insert_point)
route_temp = {}
if check(chosen_day,test,cap_auto):
objf = objective_function(diesel_price,consumption,test,hourly_wage,index_hub)
route_temp[objf] = test
if check(chosen_day,test[::-1],cap_auto):
objf = objective_function(diesel_price,consumption,test[::-1],hourly_wage,index_hub)
route_temp[objf] = test[::-1]
if len(route_temp)>0:
test = route_temp[min(route_temp)]
done_merged.remove(done_merged[y])
done_merged.append(test)
done_ind.extend(test)
# Scenario 3: Both points are already added but are seperated. We need to check if the routes can joined.
elif total == 2:
pos1=-2
pos2=-2
stop = 0
for y in range(len(done_merged)):
if total_n[0] in done_merged[y] and total_n[1] in done_merged[y]:
stop=1
if stop == 0:
if total_n[0] in done_merged[y]:
ind_y = done_merged[y].index(total_n[0])
if ind_y==0:
pos1 = 0
elif ind_y == len(done_merged)-1:
pos1 = -1
first = done_merged[y].copy()
if total_n[1] in done_merged[y]:
ind_y = done_merged[y].index(total_n[1])
if ind_y==0:
pos2 = 0
elif ind_y == len(done_merged)-1:
pos2 = -1
second = done_merged[y].copy()
break
# Check the position of the indices. If they are at the end or beginning, they can be joined.
if pos1 == 0 and pos2 == -1:
temp = [i for i in second]
temp.extend(first)
test = temp
route_temp = {}
if check(chosen_day,test,cap_auto):
objf = objective_function(diesel_price,consumption,test,hourly_wage,index_hub)
route_temp[objf] = test
if check(chosen_day,test[::-1],cap_auto):
objf = objective_function(diesel_price,consumption,test[::-1],hourly_wage,index_hub)
route_temp[objf] = test[::-1]
if len(route_temp)>0:
test = route_temp[min(route_temp)]
done_merged.remove(first)
done_merged.remove(second)
done_merged.append(test)
done_ind.extend(test)
elif pos1 == -1 and pos2 == -1:
temp = [i for i in first]
temp.extend(second[::-1])
test = temp
route_temp = {}
if check(chosen_day,test,cap_auto):
objf = objective_function(diesel_price,consumption,test,hourly_wage,index_hub)
route_temp[objf] = test
if check(chosen_day,test[::-1],cap_auto):
objf = objective_function(diesel_price,consumption,test[::-1],hourly_wage,index_hub)
route_temp[objf] = test[::-1]
if len(route_temp)>0:
test = route_temp[min(route_temp)]
done_merged.remove(first)
done_merged.remove(second)
done_merged.append(test)
done_ind.extend(test)
elif pos1 == -1 and pos2 == 0:
temp = [i for i in first]
temp.extend(second)
test = temp
route_temp = {}
if check(chosen_day,test,cap_auto):
objf = objective_function(diesel_price,consumption,test,hourly_wage,index_hub)
route_temp[objf] = test
if check(chosen_day,test[::-1],cap_auto):
objf = objective_function(diesel_price,consumption,test[::-1],hourly_wage,index_hub)
route_temp[objf] = test[::-1]
if len(route_temp)>0:
test = route_temp[min(route_temp)]
done_merged.remove(first)
done_merged.remove(second)
done_merged.append(test)
done_ind.extend(test)
elif pos1 == 0 and pos2 == 0:
temp1 = [i for i in first[::-1]]
temp = temp1
temp.extend(second)
test = temp
route_temp = {}
if check(chosen_day,test,cap_auto):
objf = objective_function(diesel_price,consumption,test,hourly_wage,index_hub)
route_temp[objf] = test
if check(chosen_day,test[::-1],cap_auto):
objf = objective_function(diesel_price,consumption,test[::-1],hourly_wage,index_hub)
route_temp[objf] = test[::-1]
if len(route_temp)>0:
test = route_temp[min(route_temp)]
done_merged.remove(first)
done_merged.remove(second)
done_merged.append(test)
done_ind.extend(test)
done_merged_total.append(done_merged[:])
i+=1
list_not_done = list(all_points - set(done_ind))
if len(list_not_done)>0:
done_merged.extend([[i] for i in list_not_done])
return done_merged,pairs,done_merged_total
Objective/fitness function: Please ignore the use of variables outside of the function.
def objective_function(diesel_price,route,hourly_wage,index_hub):
route_total= [index_hub]
route_total.extend(route)
route_total.append(index_hub)
distance = 0
time = 0
for w in range(len(route_total)-1):
distance += distance_matrix_pd.iloc[route_total[w],route_total[w+1]]
time += time_matrix_pd.iloc[route_total[w],route_total[w+1]]
score = diesel_price*consumption*(distance/1000)+hourly_wage*(time/3600)
return score
This is the function to check for the time frames and the capacity:
def check(chosen_day,route,capacity_of_vehicle):
# Checking if a route is feasible
ok_nok = True
# Check if capacity is not exceeded.
if sum(chosen_day[chosen_day['index_location'].isin(route)]['capaciteit_needed'])>capacity_of_vehicle:
ok_nok = False
else:
# ev is just a variable which is used instead of a for-loop.
ev = 0
while ev != len(route):
# Going to the first address is always possible.
if ev == 0:
arrival = chosen_day[chosen_day['index_location']==route[ev]]['opening_time'].tolist()[0]
# Determining the travel time to the next address
else:
# getting the traveling time
travel_time = time_matrix_pd.iloc[route[ev-1],route[ev]].tolist()
# arrival = departure + traveling_time.
arrival = depature + timedelta(seconds=travel_time)
# Compare to the closing time.
arrival_before_closing = chosen_day[chosen_day['index_location']==route[ev]]['closing_time'].tolist()[0]
if arrival > arrival_before_closing:
ok_nok = False
# Depart 10 minutes after arrival
depature = arrival + timedelta(minutes=10)
ev+=1
return ok_nok
And finally, getting the score for all routes:
def score_total(routes,index_hub):
total_score = 0
for i in routes:
total_score+=objective_function(diesel_price,route,hourly_wage,index_hub)
return totaal_score
Upvotes: 0
Views: 20