Transport Analytics Training Series - Last Revision: October 2022

The Savings Method¶

   

In [1]:
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)
In [2]:
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)
In [3]:
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
In [4]:
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)
In [5]:
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))
In [6]:
cust = list(zip(cust_name, cust_coord[:, 0], cust_coord[:, 1], cust_demand))
df = pd.DataFrame(cust, columns = ['cust', 'x', 'y', 'demand']) 
df
Out[6]:
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
In [7]:
from scipy.spatial import distance
all_coord = list([facil_coord]) + list(cust_coord)
In [8]:
dist_matrix = distance.cdist(all_coord, all_coord, 'euclidean')
dist_matrix = np.round(dist_matrix,1)
In [9]:
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))
In [10]:
dfm = pd.DataFrame(savings_table)
for t in range(len(dist_matrix)):
    dfm.loc[t, t] = "-"
    dfm.loc[t, 0] = "-"
dfm
Out[10]:
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 -
In [11]:
dfl = pd.DataFrame.from_dict(savings_dict, orient='index', columns=['Saving'])
dfl
Out[11]:
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

In [12]:
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
In [13]:
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
In [14]:
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
Out[14]:
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
In [15]:
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]}
Out[15]:
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
In [16]:
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)
In [17]:
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
Out[17]:
349.3355378304753