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