Transport Analytics Training Series - Last Revision: October 2022
Transport Analytics Training Series - Last Revision: October 2022
import numpy as np
import pandas as pd
import matplotlib
import matplotlib.pyplot as plt
import seaborn as sns; sns.set()
from sklearn.datasets import make_blobs
from scipy.spatial import distance
%matplotlib inline
plot_size = 20
plot_width = 10
plot_height = 10
params = {'legend.fontsize': 'large',
'figure.figsize': (plot_width,plot_height),
'axes.labelsize': plot_size,
'axes.titlesize': plot_size,
'xtick.labelsize': plot_size*0.75,
'ytick.labelsize': plot_size*0.75}
plt.rcParams.update(params)
num_customer = 15
rnd_state = 5
seed_index = 1
cust_demand_low = 100
cust_demand_high = 200
vehicle_capacity = 1000
np.random.seed(seed=rnd_state)
center_box = (100, 150)
cust_coord, _ = make_blobs(n_samples=num_customer, centers=2, cluster_std=20,
center_box=center_box, random_state = rnd_state)
cust_coord = np.round(cust_coord,0)
facil_coord = (125, 150)
depot = facil_coord
cust_name = [('C'+str(i+1)) for i in range(num_customer)]
cust_demand = np.random.randint(low=cust_demand_low, high=cust_demand_high, size = num_customer)
plt.scatter(cust_coord[:, 0], cust_coord[:, 1], s=plot_size*2, cmap='viridis');
plt.scatter(facil_coord[0], facil_coord[1], s=plot_size*5, cmap='viridis');
for i in range(num_customer): plt.annotate(i+1, (cust_coord[i, 0]+0.3, cust_coord[i, 1]+0.3))
cust = list(zip(cust_name, cust_coord[:, 0], cust_coord[:, 1], cust_demand))
df = pd.DataFrame(cust, columns = ['cust', 'x', 'y', 'demand'])
df
| cust | x | y | demand | |
|---|---|---|---|---|
| 0 | C1 | 87.0 | 139.0 | 199 |
| 1 | C2 | 115.0 | 137.0 | 178 |
| 2 | C3 | 80.0 | 159.0 | 161 |
| 3 | C4 | 113.0 | 175.0 | 116 |
| 4 | C5 | 93.0 | 132.0 | 173 |
| 5 | C6 | 110.0 | 144.0 | 108 |
| 6 | C7 | 130.0 | 160.0 | 162 |
| 7 | C8 | 112.0 | 139.0 | 127 |
| 8 | C9 | 78.0 | 130.0 | 130 |
| 9 | C10 | 126.0 | 133.0 | 180 |
| 10 | C11 | 93.0 | 137.0 | 107 |
| 11 | C12 | 160.0 | 138.0 | 176 |
| 12 | C13 | 134.0 | 181.0 | 115 |
| 13 | C14 | 104.0 | 156.0 | 153 |
| 14 | C15 | 91.0 | 129.0 | 180 |
from scipy.spatial import distance
all_coord = list([facil_coord]) + list(cust_coord)
dist_matrix = distance.cdist(all_coord, all_coord, 'euclidean')
dist_matrix = np.round(dist_matrix,1)
savings_table = np.zeros((len(dist_matrix),len(dist_matrix)))
savings_dict = dict()
for i in range(len(dist_matrix)):
for j in range(len(dist_matrix)):
if j > i:
savings_table[i,j] = dist_matrix[i][j]
elif j>0 and j < i:
saving = round((dist_matrix[0][i] + dist_matrix[0][j] - dist_matrix[i][j]),1)
savings_table[i,j] = saving
savings_dict[(i,j)] = saving
savings_dict = dict(sorted(savings_dict.items(), key=lambda x:x[1],reverse=True))
dfm = pd.DataFrame(savings_table)
for t in range(len(dist_matrix)):
dfm.loc[t, t] = "-"
dfm.loc[t, 0] = "-"
dfm
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | - | 39.6 | 16.4 | 45.9 | 27.7 | 36.7 | 16.2 | 11.2 | 17 | 51.1 | 17 | 34.5 | 37 | 32.3 | 21.8 | 40 |
| 1 | - | - | 28.1 | 21.2 | 44.4 | 9.2 | 23.5 | 47.9 | 25 | 12.7 | 39.5 | 6.3 | 73 | 63 | 24 | 10.8 |
| 2 | - | 27.9 | - | 41.3 | 38.1 | 22.6 | 8.6 | 27.5 | 3.6 | 37.7 | 11.7 | 22 | 45 | 47.9 | 22 | 25.3 |
| 3 | - | 64.3 | 21 | - | 36.7 | 30 | 33.5 | 50 | 37.7 | 29.1 | 52.8 | 25.6 | 82.7 | 58.3 | 24.2 | 32 |
| 4 | - | 22.9 | 6 | 36.9 | - | 47.4 | 31.1 | 22.7 | 36 | 57 | 44 | 42.9 | 59.8 | 21.8 | 21 | 51 |
| 5 | - | 67.1 | 30.5 | 52.6 | 17 | - | 20.8 | 46.4 | 20.2 | 15.1 | 33 | 5 | 67.3 | 63.9 | 26.4 | 3.6 |
| 6 | - | 32.3 | 24 | 28.6 | 12.8 | 32.1 | - | 25.6 | 5.4 | 34.9 | 19.4 | 18.4 | 50.4 | 44.1 | 13.4 | 24.2 |
| 7 | - | 2.9 | 0.1 | 7.1 | 16.2 | 1.5 | 1.8 | - | 27.7 | 60 | 27.3 | 43.6 | 37.2 | 21.4 | 26.3 | 49.8 |
| 8 | - | 31.6 | 29.8 | 25.2 | 8.7 | 33.5 | 27.8 | 0.5 | - | 35.2 | 15.2 | 19.1 | 48 | 47.4 | 18.8 | 23.3 |
| 9 | - | 78 | 29.8 | 67.9 | 21.8 | 72.7 | 32.4 | 2.3 | 32.9 | - | 48.1 | 16.6 | 82.4 | 75.7 | 36.8 | 13 |
| 10 | - | 17.1 | 21.7 | 10.1 | 0.7 | 20.7 | 13.8 | 0.9 | 18.8 | 20 | - | 33.2 | 34.4 | 48.7 | 31.8 | 35.2 |
| 11 | - | 67.8 | 28.9 | 54.8 | 19.3 | 66.2 | 32.3 | 2.1 | 32.4 | 69 | 18.3 | - | 67 | 60.1 | 22 | 8.2 |
| 12 | - | 3.6 | 8.4 | 0.2 | 4.9 | 6.4 | 2.8 | 11 | 6 | 5.7 | 19.6 | 4.5 | - | 50.2 | 58.8 | 69.6 |
| 13 | - | 8.9 | 0.8 | 19.9 | 38.2 | 5.1 | 4.4 | 22.1 | 1.9 | 7.7 | 0.6 | 6.7 | 19.1 | - | 39.1 | 67.5 |
| 14 | - | 37.4 | 16.2 | 43.5 | 28.5 | 32.1 | 24.6 | 6.7 | 20 | 36.1 | 7 | 34.3 | 0 | 15 | - | 30 |
| 15 | - | 68.8 | 31.1 | 53.9 | 16.7 | 73.1 | 32 | 1.4 | 33.7 | 78.1 | 21.8 | 66.3 | 7.4 | 4.8 | 31.8 | - |
dfl = pd.DataFrame.from_dict(savings_dict, orient='index', columns=['Saving'])
dfl
| Saving | |
|---|---|
| (15, 9) | 78.1 |
| (9, 1) | 78.0 |
| (15, 5) | 73.1 |
| (9, 5) | 72.7 |
| (11, 9) | 69.0 |
| ... | ... |
| (13, 10) | 0.6 |
| (8, 7) | 0.5 |
| (12, 3) | 0.2 |
| (7, 2) | 0.1 |
| (14, 12) | 0.0 |
105 rows × 1 columns
def tour_distance(tour):
dist = dist_matrix[0][tour[0]]
for i in range(len(tour)):
if i>0:
dist += dist_matrix[tour[i-1]][tour[i]]
dist += dist_matrix[tour[i]][0]
return dist
def tour_cap_left(tour):
cap = vehicle_capacity
for i in range(len(tour)):
cap -= cust_demand[tour[i]-1]
return cap
print(f'Dst: {tour_distance([1, 2,3])}')
print(f'Cap: {tour_cap_left([2, 1,3])}')
Dst: 154.9 Cap: 462
savings_cur = savings_dict.copy()
tours = dict()
added = []
cnt_sav = 0
for i in range(len(dist_matrix)):
if i>0:
tours[i] = [i]
tours_modified = True
for pair, saving in savings_cur.items():
if (tours_modified):
tours_modified = False
print('\n-----------------\n')
print('Current tours:')
for r, tour in tours.items():
route_cap = tour_cap_left(tour)
tour_str = '-'.join(map(str,tour))
tour_str = f'0-{tour_str}-0'
print(f'{r:02}. (left {route_cap}): {tour_str}')
v1 = pair[0]
v2 = pair[1]
cnt_sav += 1
print(f'\nConsidering saving {cnt_sav}/{len(savings_cur)}: {v1}<->{v2} ({saving})')
for r, tour in tours.items():
if (v1 != tour[-1]) and (v2 != tour[0]) and (v2 != tour[-1]) and (v1 != tour[0]):
continue
route_cap = tour_cap_left(tour)
tour_str0 = '-'.join(map(str,tour))
tour_str = f'0-{tour_str0}-0'
print(f' Checking route {r:02} ({tour_str} - left: {route_cap})')
if v2 == tour[0] and v1 not in added:
if (cust_demand[v1-1]>route_cap):
print(f' SKIPPING: Not enough capacity ({route_cap}<{cust_demand[v1-1]})')
break
del tours[v1]
added.append(v1)
tours[r] = [v1] + tour
tours_modified = True
if (r not in added):
added.append(r)
print(f' SUCCESS: Adding saving {v1}->{v2} to tour {r}: 0-{v1}-{tour_str0}-0')
break
if v1 == tour[0] and v2 not in added:
if (cust_demand[v2-1]>route_cap):
print(f' SKIPPING: Not enough capacity ({route_cap}<{cust_demand[v2-1]})')
break
del tours[v2]
added.append(v2)
tours[r] = [v2] + tour
tours_modified = True
if (r not in added):
added.append(r)
print(f' SUCCESS: Adding saving {v2}->{v1} to tour {r}: 0-{v2}-{tour_str0}-0')
break
if v1 == tour[-1] and v2 not in added:
if (cust_demand[v2-1]>route_cap):
print(f' SKIPPING: Not enough capacity ({route_cap}<{cust_demand[v2-1]})')
break
del tours[v2]
added.append(v2)
tours[r] = tour + [v2]
tours_modified = True
if (r not in added):
added.append(r)
print(f' SUCCESS: Adding saving {v1}->{v2} to tour {r}: 0-{tour_str0}-{v2}-0')
break
if v2 == tour[-1] and v1 not in added:
if (cust_demand[v1-1]>route_cap):
print(f' SKIPPING: Not enough capacity ({route_cap}<{cust_demand[v1-1]})')
break
del tours[v1]
added.append(v1)
tours[r] = tour + [v1]
tours_modified = True
if (r not in added):
added.append(r)
print(f' SUCCESS: Adding saving {v2}->{v1} to tour {r}: 0-{tour_str0}-{v1}-0')
break
print(f' SKIPPING: Could not append')
print('\n-----------------\n')
print('FINAL TOURS')
cnt_tour=0
for r, tour in tours.items():
cnt_tour+=1
route_cap = tour_cap_left(tour)
tour_str = '-'.join(map(str,tour))
tour_str = f'0-{tour_str}-0'
print(f'Tour {cnt_tour:02}. (left {route_cap}): {tour_str}')
-----------------
Current tours:
01. (left 801): 0-1-0
02. (left 822): 0-2-0
03. (left 839): 0-3-0
04. (left 884): 0-4-0
05. (left 827): 0-5-0
06. (left 892): 0-6-0
07. (left 838): 0-7-0
08. (left 873): 0-8-0
09. (left 870): 0-9-0
10. (left 820): 0-10-0
11. (left 893): 0-11-0
12. (left 824): 0-12-0
13. (left 885): 0-13-0
14. (left 847): 0-14-0
15. (left 820): 0-15-0
Considering saving 1/105: 15<->9 (78.1)
Checking route 09 (0-9-0 - left: 870)
SUCCESS: Adding saving 15->9 to tour 9: 0-15-9-0
-----------------
Current tours:
01. (left 801): 0-1-0
02. (left 822): 0-2-0
03. (left 839): 0-3-0
04. (left 884): 0-4-0
05. (left 827): 0-5-0
06. (left 892): 0-6-0
07. (left 838): 0-7-0
08. (left 873): 0-8-0
09. (left 690): 0-15-9-0
10. (left 820): 0-10-0
11. (left 893): 0-11-0
12. (left 824): 0-12-0
13. (left 885): 0-13-0
14. (left 847): 0-14-0
Considering saving 2/105: 9<->1 (78.0)
Checking route 01 (0-1-0 - left: 801)
SKIPPING: Could not append
Checking route 09 (0-15-9-0 - left: 690)
SUCCESS: Adding saving 9->1 to tour 9: 0-15-9-1-0
-----------------
Current tours:
02. (left 822): 0-2-0
03. (left 839): 0-3-0
04. (left 884): 0-4-0
05. (left 827): 0-5-0
06. (left 892): 0-6-0
07. (left 838): 0-7-0
08. (left 873): 0-8-0
09. (left 491): 0-15-9-1-0
10. (left 820): 0-10-0
11. (left 893): 0-11-0
12. (left 824): 0-12-0
13. (left 885): 0-13-0
14. (left 847): 0-14-0
Considering saving 3/105: 15<->5 (73.1)
Checking route 05 (0-5-0 - left: 827)
SKIPPING: Could not append
Checking route 09 (0-15-9-1-0 - left: 491)
SUCCESS: Adding saving 5->15 to tour 9: 0-5-15-9-1-0
-----------------
Current tours:
02. (left 822): 0-2-0
03. (left 839): 0-3-0
04. (left 884): 0-4-0
06. (left 892): 0-6-0
07. (left 838): 0-7-0
08. (left 873): 0-8-0
09. (left 318): 0-5-15-9-1-0
10. (left 820): 0-10-0
11. (left 893): 0-11-0
12. (left 824): 0-12-0
13. (left 885): 0-13-0
14. (left 847): 0-14-0
Considering saving 4/105: 9<->5 (72.7)
Checking route 09 (0-5-15-9-1-0 - left: 318)
SKIPPING: Could not append
Considering saving 5/105: 11<->9 (69.0)
Checking route 11 (0-11-0 - left: 893)
SKIPPING: Could not append
Considering saving 6/105: 15<->1 (68.8)
Checking route 09 (0-5-15-9-1-0 - left: 318)
SKIPPING: Could not append
Considering saving 7/105: 9<->3 (67.9)
Checking route 03 (0-3-0 - left: 839)
SKIPPING: Could not append
Considering saving 8/105: 11<->1 (67.8)
Checking route 09 (0-5-15-9-1-0 - left: 318)
SUCCESS: Adding saving 1->11 to tour 9: 0-5-15-9-1-11-0
-----------------
Current tours:
02. (left 822): 0-2-0
03. (left 839): 0-3-0
04. (left 884): 0-4-0
06. (left 892): 0-6-0
07. (left 838): 0-7-0
08. (left 873): 0-8-0
09. (left 211): 0-5-15-9-1-11-0
10. (left 820): 0-10-0
12. (left 824): 0-12-0
13. (left 885): 0-13-0
14. (left 847): 0-14-0
Considering saving 9/105: 5<->1 (67.1)
Checking route 09 (0-5-15-9-1-11-0 - left: 211)
SKIPPING: Could not append
Considering saving 10/105: 15<->11 (66.3)
Checking route 09 (0-5-15-9-1-11-0 - left: 211)
SKIPPING: Could not append
Considering saving 11/105: 11<->5 (66.2)
Checking route 09 (0-5-15-9-1-11-0 - left: 211)
SKIPPING: Could not append
Considering saving 12/105: 3<->1 (64.3)
Checking route 03 (0-3-0 - left: 839)
SKIPPING: Could not append
Considering saving 13/105: 11<->3 (54.8)
Checking route 03 (0-3-0 - left: 839)
SKIPPING: Could not append
Checking route 09 (0-5-15-9-1-11-0 - left: 211)
SUCCESS: Adding saving 11->3 to tour 9: 0-5-15-9-1-11-3-0
-----------------
Current tours:
02. (left 822): 0-2-0
04. (left 884): 0-4-0
06. (left 892): 0-6-0
07. (left 838): 0-7-0
08. (left 873): 0-8-0
09. (left 50): 0-5-15-9-1-11-3-0
10. (left 820): 0-10-0
12. (left 824): 0-12-0
13. (left 885): 0-13-0
14. (left 847): 0-14-0
Considering saving 14/105: 15<->3 (53.9)
Checking route 09 (0-5-15-9-1-11-3-0 - left: 50)
SKIPPING: Could not append
Considering saving 15/105: 5<->3 (52.6)
Checking route 09 (0-5-15-9-1-11-3-0 - left: 50)
SKIPPING: Could not append
Considering saving 16/105: 14<->3 (43.5)
Checking route 09 (0-5-15-9-1-11-3-0 - left: 50)
SKIPPING: Not enough capacity (50<153)
Considering saving 17/105: 13<->4 (38.2)
Checking route 04 (0-4-0 - left: 884)
SUCCESS: Adding saving 13->4 to tour 4: 0-13-4-0
-----------------
Current tours:
02. (left 822): 0-2-0
04. (left 769): 0-13-4-0
06. (left 892): 0-6-0
07. (left 838): 0-7-0
08. (left 873): 0-8-0
09. (left 50): 0-5-15-9-1-11-3-0
10. (left 820): 0-10-0
12. (left 824): 0-12-0
14. (left 847): 0-14-0
Considering saving 18/105: 14<->1 (37.4)
Checking route 14 (0-14-0 - left: 847)
SKIPPING: Could not append
Considering saving 19/105: 4<->3 (36.9)
Checking route 04 (0-13-4-0 - left: 769)
SKIPPING: Could not append
Checking route 09 (0-5-15-9-1-11-3-0 - left: 50)
SKIPPING: Could not append
Considering saving 20/105: 14<->9 (36.1)
Checking route 14 (0-14-0 - left: 847)
SKIPPING: Could not append
Considering saving 21/105: 14<->11 (34.3)
Checking route 14 (0-14-0 - left: 847)
SKIPPING: Could not append
Considering saving 22/105: 15<->8 (33.7)
Checking route 08 (0-8-0 - left: 873)
SKIPPING: Could not append
Considering saving 23/105: 8<->5 (33.5)
Checking route 08 (0-8-0 - left: 873)
SKIPPING: Could not append
Checking route 09 (0-5-15-9-1-11-3-0 - left: 50)
SKIPPING: Not enough capacity (50<127)
Considering saving 24/105: 9<->8 (32.9)
Checking route 08 (0-8-0 - left: 873)
SKIPPING: Could not append
Considering saving 25/105: 9<->6 (32.4)
Checking route 06 (0-6-0 - left: 892)
SKIPPING: Could not append
Considering saving 26/105: 11<->8 (32.4)
Checking route 08 (0-8-0 - left: 873)
SKIPPING: Could not append
Considering saving 27/105: 6<->1 (32.3)
Checking route 06 (0-6-0 - left: 892)
SKIPPING: Could not append
Considering saving 28/105: 11<->6 (32.3)
Checking route 06 (0-6-0 - left: 892)
SKIPPING: Could not append
Considering saving 29/105: 6<->5 (32.1)
Checking route 06 (0-6-0 - left: 892)
SKIPPING: Could not append
Checking route 09 (0-5-15-9-1-11-3-0 - left: 50)
SKIPPING: Not enough capacity (50<108)
Considering saving 30/105: 14<->5 (32.1)
Checking route 09 (0-5-15-9-1-11-3-0 - left: 50)
SKIPPING: Not enough capacity (50<153)
Considering saving 31/105: 15<->6 (32.0)
Checking route 06 (0-6-0 - left: 892)
SKIPPING: Could not append
Considering saving 32/105: 15<->14 (31.8)
Checking route 14 (0-14-0 - left: 847)
SKIPPING: Could not append
Considering saving 33/105: 8<->1 (31.6)
Checking route 08 (0-8-0 - left: 873)
SKIPPING: Could not append
Considering saving 34/105: 15<->2 (31.1)
Checking route 02 (0-2-0 - left: 822)
SKIPPING: Could not append
Considering saving 35/105: 5<->2 (30.5)
Checking route 02 (0-2-0 - left: 822)
SKIPPING: Could not append
Checking route 09 (0-5-15-9-1-11-3-0 - left: 50)
SKIPPING: Not enough capacity (50<178)
Considering saving 36/105: 8<->2 (29.8)
Checking route 02 (0-2-0 - left: 822)
SUCCESS: Adding saving 8->2 to tour 2: 0-8-2-0
-----------------
Current tours:
02. (left 695): 0-8-2-0
04. (left 769): 0-13-4-0
06. (left 892): 0-6-0
07. (left 838): 0-7-0
09. (left 50): 0-5-15-9-1-11-3-0
10. (left 820): 0-10-0
12. (left 824): 0-12-0
14. (left 847): 0-14-0
Considering saving 37/105: 9<->2 (29.8)
Checking route 02 (0-8-2-0 - left: 695)
SKIPPING: Could not append
Considering saving 38/105: 11<->2 (28.9)
Checking route 02 (0-8-2-0 - left: 695)
SKIPPING: Could not append
Considering saving 39/105: 6<->3 (28.6)
Checking route 06 (0-6-0 - left: 892)
SKIPPING: Could not append
Checking route 09 (0-5-15-9-1-11-3-0 - left: 50)
SKIPPING: Not enough capacity (50<108)
Considering saving 40/105: 14<->4 (28.5)
Checking route 04 (0-13-4-0 - left: 769)
SUCCESS: Adding saving 4->14 to tour 4: 0-13-4-14-0
-----------------
Current tours:
02. (left 695): 0-8-2-0
04. (left 616): 0-13-4-14-0
06. (left 892): 0-6-0
07. (left 838): 0-7-0
09. (left 50): 0-5-15-9-1-11-3-0
10. (left 820): 0-10-0
12. (left 824): 0-12-0
Considering saving 41/105: 2<->1 (27.9)
Checking route 02 (0-8-2-0 - left: 695)
SKIPPING: Could not append
Considering saving 42/105: 8<->6 (27.8)
Checking route 02 (0-8-2-0 - left: 695)
SUCCESS: Adding saving 6->8 to tour 2: 0-6-8-2-0
-----------------
Current tours:
02. (left 587): 0-6-8-2-0
04. (left 616): 0-13-4-14-0
07. (left 838): 0-7-0
09. (left 50): 0-5-15-9-1-11-3-0
10. (left 820): 0-10-0
12. (left 824): 0-12-0
Considering saving 43/105: 8<->3 (25.2)
Checking route 09 (0-5-15-9-1-11-3-0 - left: 50)
SKIPPING: Could not append
Considering saving 44/105: 14<->6 (24.6)
Checking route 02 (0-6-8-2-0 - left: 587)
SKIPPING: Could not append
Checking route 04 (0-13-4-14-0 - left: 616)
SKIPPING: Could not append
Considering saving 45/105: 6<->2 (24.0)
Checking route 02 (0-6-8-2-0 - left: 587)
SKIPPING: Could not append
Considering saving 46/105: 4<->1 (22.9)
Considering saving 47/105: 13<->7 (22.1)
Checking route 04 (0-13-4-14-0 - left: 616)
SUCCESS: Adding saving 7->13 to tour 4: 0-7-13-4-14-0
-----------------
Current tours:
02. (left 587): 0-6-8-2-0
04. (left 454): 0-7-13-4-14-0
09. (left 50): 0-5-15-9-1-11-3-0
10. (left 820): 0-10-0
12. (left 824): 0-12-0
Considering saving 48/105: 9<->4 (21.8)
Considering saving 49/105: 15<->10 (21.8)
Checking route 10 (0-10-0 - left: 820)
SKIPPING: Could not append
Considering saving 50/105: 10<->2 (21.7)
Checking route 02 (0-6-8-2-0 - left: 587)
SUCCESS: Adding saving 2->10 to tour 2: 0-6-8-2-10-0
-----------------
Current tours:
02. (left 407): 0-6-8-2-10-0
04. (left 454): 0-7-13-4-14-0
09. (left 50): 0-5-15-9-1-11-3-0
12. (left 824): 0-12-0
Considering saving 51/105: 3<->2 (21.0)
Checking route 09 (0-5-15-9-1-11-3-0 - left: 50)
SKIPPING: Could not append
Considering saving 52/105: 10<->5 (20.7)
Checking route 02 (0-6-8-2-10-0 - left: 407)
SKIPPING: Could not append
Checking route 09 (0-5-15-9-1-11-3-0 - left: 50)
SKIPPING: Could not append
Considering saving 53/105: 10<->9 (20.0)
Checking route 02 (0-6-8-2-10-0 - left: 407)
SKIPPING: Could not append
Considering saving 54/105: 14<->8 (20.0)
Checking route 04 (0-7-13-4-14-0 - left: 454)
SKIPPING: Could not append
Considering saving 55/105: 13<->3 (19.9)
Checking route 09 (0-5-15-9-1-11-3-0 - left: 50)
SKIPPING: Could not append
Considering saving 56/105: 12<->10 (19.6)
Checking route 02 (0-6-8-2-10-0 - left: 407)
SUCCESS: Adding saving 10->12 to tour 2: 0-6-8-2-10-12-0
-----------------
Current tours:
02. (left 231): 0-6-8-2-10-12-0
04. (left 454): 0-7-13-4-14-0
09. (left 50): 0-5-15-9-1-11-3-0
Considering saving 57/105: 11<->4 (19.3)
Considering saving 58/105: 13<->12 (19.1)
Checking route 02 (0-6-8-2-10-12-0 - left: 231)
SKIPPING: Could not append
Considering saving 59/105: 10<->8 (18.8)
Considering saving 60/105: 11<->10 (18.3)
Considering saving 61/105: 10<->1 (17.1)
Considering saving 62/105: 5<->4 (17.0)
Checking route 09 (0-5-15-9-1-11-3-0 - left: 50)
SKIPPING: Could not append
Considering saving 63/105: 15<->4 (16.7)
Considering saving 64/105: 7<->4 (16.2)
Checking route 04 (0-7-13-4-14-0 - left: 454)
SKIPPING: Could not append
Considering saving 65/105: 14<->2 (16.2)
Checking route 04 (0-7-13-4-14-0 - left: 454)
SKIPPING: Could not append
Considering saving 66/105: 14<->13 (15.0)
Checking route 04 (0-7-13-4-14-0 - left: 454)
SKIPPING: Could not append
Considering saving 67/105: 10<->6 (13.8)
Checking route 02 (0-6-8-2-10-12-0 - left: 231)
SKIPPING: Could not append
Considering saving 68/105: 6<->4 (12.8)
Checking route 02 (0-6-8-2-10-12-0 - left: 231)
SKIPPING: Could not append
Considering saving 69/105: 12<->7 (11.0)
Checking route 02 (0-6-8-2-10-12-0 - left: 231)
SKIPPING: Could not append
Checking route 04 (0-7-13-4-14-0 - left: 454)
SKIPPING: Could not append
Considering saving 70/105: 10<->3 (10.1)
Checking route 09 (0-5-15-9-1-11-3-0 - left: 50)
SKIPPING: Could not append
Considering saving 71/105: 13<->1 (8.9)
Considering saving 72/105: 8<->4 (8.7)
Considering saving 73/105: 12<->2 (8.4)
Checking route 02 (0-6-8-2-10-12-0 - left: 231)
SKIPPING: Could not append
Considering saving 74/105: 13<->9 (7.7)
Considering saving 75/105: 15<->12 (7.4)
Checking route 02 (0-6-8-2-10-12-0 - left: 231)
SKIPPING: Could not append
Considering saving 76/105: 7<->3 (7.1)
Checking route 04 (0-7-13-4-14-0 - left: 454)
SKIPPING: Could not append
Checking route 09 (0-5-15-9-1-11-3-0 - left: 50)
SKIPPING: Could not append
Considering saving 77/105: 14<->10 (7.0)
Checking route 04 (0-7-13-4-14-0 - left: 454)
SKIPPING: Could not append
Considering saving 78/105: 13<->11 (6.7)
Considering saving 79/105: 14<->7 (6.7)
Checking route 04 (0-7-13-4-14-0 - left: 454)
SKIPPING: Could not append
Considering saving 80/105: 12<->5 (6.4)
Checking route 02 (0-6-8-2-10-12-0 - left: 231)
SKIPPING: Could not append
Checking route 09 (0-5-15-9-1-11-3-0 - left: 50)
SKIPPING: Could not append
Considering saving 81/105: 4<->2 (6.0)
Considering saving 82/105: 12<->8 (6.0)
Checking route 02 (0-6-8-2-10-12-0 - left: 231)
SKIPPING: Could not append
Considering saving 83/105: 12<->9 (5.7)
Checking route 02 (0-6-8-2-10-12-0 - left: 231)
SKIPPING: Could not append
Considering saving 84/105: 13<->5 (5.1)
Checking route 09 (0-5-15-9-1-11-3-0 - left: 50)
SKIPPING: Could not append
Considering saving 85/105: 12<->4 (4.9)
Checking route 02 (0-6-8-2-10-12-0 - left: 231)
SKIPPING: Could not append
Considering saving 86/105: 15<->13 (4.8)
Considering saving 87/105: 12<->11 (4.5)
Checking route 02 (0-6-8-2-10-12-0 - left: 231)
SKIPPING: Could not append
Considering saving 88/105: 13<->6 (4.4)
Checking route 02 (0-6-8-2-10-12-0 - left: 231)
SKIPPING: Could not append
Considering saving 89/105: 12<->1 (3.6)
Checking route 02 (0-6-8-2-10-12-0 - left: 231)
SKIPPING: Could not append
Considering saving 90/105: 7<->1 (2.9)
Checking route 04 (0-7-13-4-14-0 - left: 454)
SKIPPING: Could not append
Considering saving 91/105: 12<->6 (2.8)
Checking route 02 (0-6-8-2-10-12-0 - left: 231)
SKIPPING: Could not append
Considering saving 92/105: 9<->7 (2.3)
Checking route 04 (0-7-13-4-14-0 - left: 454)
SKIPPING: Could not append
Considering saving 93/105: 11<->7 (2.1)
Checking route 04 (0-7-13-4-14-0 - left: 454)
SKIPPING: Could not append
Considering saving 94/105: 13<->8 (1.9)
Considering saving 95/105: 7<->6 (1.8)
Checking route 02 (0-6-8-2-10-12-0 - left: 231)
SKIPPING: Could not append
Checking route 04 (0-7-13-4-14-0 - left: 454)
SKIPPING: Could not append
Considering saving 96/105: 7<->5 (1.5)
Checking route 04 (0-7-13-4-14-0 - left: 454)
SKIPPING: Could not append
Checking route 09 (0-5-15-9-1-11-3-0 - left: 50)
SKIPPING: Could not append
Considering saving 97/105: 15<->7 (1.4)
Checking route 04 (0-7-13-4-14-0 - left: 454)
SKIPPING: Could not append
Considering saving 98/105: 10<->7 (0.9)
Checking route 04 (0-7-13-4-14-0 - left: 454)
SKIPPING: Could not append
Considering saving 99/105: 13<->2 (0.8)
Considering saving 100/105: 10<->4 (0.7)
Considering saving 101/105: 13<->10 (0.6)
Considering saving 102/105: 8<->7 (0.5)
Checking route 04 (0-7-13-4-14-0 - left: 454)
SKIPPING: Could not append
Considering saving 103/105: 12<->3 (0.2)
Checking route 02 (0-6-8-2-10-12-0 - left: 231)
SKIPPING: Could not append
Checking route 09 (0-5-15-9-1-11-3-0 - left: 50)
SKIPPING: Could not append
Considering saving 104/105: 7<->2 (0.1)
Checking route 04 (0-7-13-4-14-0 - left: 454)
SKIPPING: Could not append
Considering saving 105/105: 14<->12 (0.0)
Checking route 02 (0-6-8-2-10-12-0 - left: 231)
SKIPPING: Could not append
Checking route 04 (0-7-13-4-14-0 - left: 454)
SKIPPING: Could not append
-----------------
FINAL TOURS
Tour 01. (left 231): 0-6-8-2-10-12-0
Tour 02. (left 454): 0-7-13-4-14-0
Tour 03. (left 50): 0-5-15-9-1-11-3-0
not_visited = df.index.tolist() # initialize list of unvisited nodes
cur_tour = 1
cur_visit = 1
cap_left = vehicle_capacity # keeping track of remaining vehicle capacity
while not_visited: # while unvisited customer exist
cust = not_visited[0] # go to the next unvisited customer
cust_demand = df.loc[cust, "demand"] # obtain their demand
if cust_demand > cap_left: # if we do not have enough capacity left
cur_tour += 1 # start a new tour (increment counter)
cur_visit = 1 # reset our vist counter to 1
cap_left = vehicle_capacity # and reset our vehicle capacity
df.loc[cust, "tour"] = cur_tour # assign customer to the current vehicle
df.loc[cust, "visit"]= cur_visit # keep track of the visit number
cur_visit += 1 # increment our visit counter
cap_left -= cust_demand # reduce remaining capacity
df.loc[cust, "cap left"]= cap_left # keep track of remaining capacity
not_visited.remove(cust) # remove customer from unvisited nodes
total_tours = cur_tour
df
| cust | x | y | demand | tour | visit | cap left | |
|---|---|---|---|---|---|---|---|
| 0 | C1 | 87.0 | 139.0 | 199 | 1.0 | 1.0 | 801.0 |
| 1 | C2 | 115.0 | 137.0 | 178 | 1.0 | 2.0 | 623.0 |
| 2 | C3 | 80.0 | 159.0 | 161 | 1.0 | 3.0 | 462.0 |
| 3 | C4 | 113.0 | 175.0 | 116 | 1.0 | 4.0 | 346.0 |
| 4 | C5 | 93.0 | 132.0 | 173 | 1.0 | 5.0 | 173.0 |
| 5 | C6 | 110.0 | 144.0 | 108 | 1.0 | 6.0 | 65.0 |
| 6 | C7 | 130.0 | 160.0 | 162 | 2.0 | 1.0 | 838.0 |
| 7 | C8 | 112.0 | 139.0 | 127 | 2.0 | 2.0 | 711.0 |
| 8 | C9 | 78.0 | 130.0 | 130 | 2.0 | 3.0 | 581.0 |
| 9 | C10 | 126.0 | 133.0 | 180 | 2.0 | 4.0 | 401.0 |
| 10 | C11 | 93.0 | 137.0 | 107 | 2.0 | 5.0 | 294.0 |
| 11 | C12 | 160.0 | 138.0 | 176 | 2.0 | 6.0 | 118.0 |
| 12 | C13 | 134.0 | 181.0 | 115 | 2.0 | 7.0 | 3.0 |
| 13 | C14 | 104.0 | 156.0 | 153 | 3.0 | 1.0 | 847.0 |
| 14 | C15 | 91.0 | 129.0 | 180 | 3.0 | 2.0 | 667.0 |
cur_tour = 0
for r, tour in tours.items():
cur_tour+=1
cur_vis=0
cap_left = vehicle_capacity
for v in tour:
cur_vis+=1
cust_demand = df.loc[v-1, "demand"]
cap_left -= cust_demand # reduce remaining capacity
df.loc[v-1, "cap left"]= cap_left # keep track of remaining capacity
df.loc[v-1, "tour"] = cur_tour
df.loc[v-1, "visit"]= cur_vis
print(tours)
df = df.sort_values(by=["visit"])
df = df.sort_values(by=["tour"])
df
{2: [6, 8, 2, 10, 12], 4: [7, 13, 4, 14], 9: [5, 15, 9, 1, 11, 3]}
| cust | x | y | demand | tour | visit | cap left | |
|---|---|---|---|---|---|---|---|
| 5 | C6 | 110.0 | 144.0 | 108 | 1.0 | 1.0 | 892.0 |
| 7 | C8 | 112.0 | 139.0 | 127 | 1.0 | 2.0 | 765.0 |
| 1 | C2 | 115.0 | 137.0 | 178 | 1.0 | 3.0 | 587.0 |
| 9 | C10 | 126.0 | 133.0 | 180 | 1.0 | 4.0 | 407.0 |
| 11 | C12 | 160.0 | 138.0 | 176 | 1.0 | 5.0 | 231.0 |
| 6 | C7 | 130.0 | 160.0 | 162 | 2.0 | 1.0 | 838.0 |
| 12 | C13 | 134.0 | 181.0 | 115 | 2.0 | 2.0 | 723.0 |
| 3 | C4 | 113.0 | 175.0 | 116 | 2.0 | 3.0 | 607.0 |
| 13 | C14 | 104.0 | 156.0 | 153 | 2.0 | 4.0 | 454.0 |
| 4 | C5 | 93.0 | 132.0 | 173 | 3.0 | 1.0 | 827.0 |
| 14 | C15 | 91.0 | 129.0 | 180 | 3.0 | 2.0 | 647.0 |
| 8 | C9 | 78.0 | 130.0 | 130 | 3.0 | 3.0 | 517.0 |
| 0 | C1 | 87.0 | 139.0 | 199 | 3.0 | 4.0 | 318.0 |
| 10 | C11 | 93.0 | 137.0 | 107 | 3.0 | 5.0 | 211.0 |
| 2 | C3 | 80.0 | 159.0 | 161 | 3.0 | 6.0 | 50.0 |
vect_orig = []
vect_dest = []
arrw_width = []
dist_tot = 0
for t in range(total_tours):
d_tour = df[df['tour']==t+1]
arrw_width.append(vehicle_capacity)
v_from = depot
for index, row in d_tour.iterrows():
v_to = (row['x'],row['y'])
arrw_width.append(row['cap left'])
vect_orig.append(v_from)
vect_dest.append(v_to)
dist_tot += distance.euclidean(v_from, v_to)
v_from = v_to
vect_orig.append(v_from)
vect_dest.append(depot)
dist_tot += distance.euclidean(v_from, depot)
vect_orig = np.array(vect_orig)
vect_dest = np.array(vect_dest)
plt.scatter(cust_coord[:, 0], cust_coord[:, 1], s=plot_size*5, color='red', zorder = 10000);
plt.scatter(facil_coord[0], facil_coord[1], s=plot_size*20, color='yellow', zorder = 10000);
for i in range(len(vect_orig)):
plt.arrow(vect_orig[i][0],vect_orig[i][1],vect_dest[i][0]-vect_orig[i][0],vect_dest[i][1]-vect_orig[i][1],
width=0.2,#arrw_width[i] / 2000,
head_width=0,color='green',zorder = 1)
frame1 = plt.gca(); frame1.axes.xaxis.set_ticklabels([]); frame1.axes.yaxis.set_ticklabels([]);
dist_tot
349.3355378304753
