Skip to content

A fun study of some heuristics for the Travelling Salesman Problem.

License

Notifications You must be signed in to change notification settings

rsalmei/tsp-essay

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

14 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

TSP Essay

A fun study of some heuristics for the Travelling Salesman Problem.


I've always found the Travelling salesman problem particularly interesting. After studying a few papers on the subject (in this repository too), mainly the superb Clarke & Wright's Savings Algorithm from 1997, I felt like trying a few techniques.

To see the original ipynb format (probably better): https://github.com/rsalmei/tsp-essay/blob/master/tsp_essay.ipynb

To run this yourself, you need:

  • a recent python (I'm using 3.6.5)
  • a virtualenv
  • pip install -r requirements.txt
  • jupyter notebook tsp_essay.ipynb

Enjoy :)

Setup environment

import pandas as pd
import numpy as np

%matplotlib inline
%config InlineBackend.figure_format = 'retina'
import matplotlib.pyplot as plt
from pylab import rcParams
/Users/rogerio/.pyenv/versions/3.6.5/lib/python3.6/importlib/_bootstrap.py:219: RuntimeWarning: numpy.dtype size changed, may indicate binary incompatibility. Expected 96, got 88
  return f(*args, **kwds)
/Users/rogerio/.pyenv/versions/3.6.5/lib/python3.6/importlib/_bootstrap.py:219: RuntimeWarning: numpy.dtype size changed, may indicate binary incompatibility. Expected 96, got 88
  return f(*args, **kwds)

Customize graphics style

print(plt.style.available)
['seaborn-dark', 'seaborn-darkgrid', 'seaborn-ticks', 'fivethirtyeight', 'seaborn-whitegrid', 'classic', '_classic_test', 'fast', 'seaborn-talk', 'seaborn-dark-palette', 'seaborn-bright', 'seaborn-pastel', 'grayscale', 'seaborn-notebook', 'ggplot', 'seaborn-colorblind', 'seaborn-muted', 'seaborn', 'Solarize_Light2', 'seaborn-paper', 'bmh', 'tableau-colorblind10', 'seaborn-white', 'dark_background', 'seaborn-poster', 'seaborn-deep']
plt.style.use('classic')
rcParams['figure.figsize'] = 16, 10

Initialize data

np.random.seed(18)

size, cmin, cmax = 150, -100, 100
data = pd.DataFrame(dict(x=[0], y=[0])).append(
    pd.DataFrame((np.random.random_sample(2*size)*(cmax-cmin)+cmin).reshape(-1,2), columns=['x', 'y']), ignore_index=True)
data
<style scoped> .dataframe tbody tr th:only-of-type { vertical-align: middle; }
.dataframe tbody tr th {
    vertical-align: top;
}

.dataframe thead th {
    text-align: right;
}
</style>
x y
0 0.000000 0.000000
1 30.074848 1.090675
2 75.720294 -63.631955
3 70.446614 50.027257
4 33.220333 97.579090
5 -48.606315 -94.338815
6 27.143823 69.462477
7 47.234925 -95.838578
8 -77.679374 -40.455252
9 37.394038 72.325211
10 -60.273128 31.437806
11 39.931126 -29.521506
12 57.992110 62.809588
13 -60.515743 89.891059
14 -4.679923 33.320070
15 -57.737593 61.505265
16 -36.062776 -41.212805
17 -39.616364 65.577880
18 10.506738 -61.664519
19 42.851348 27.974071
20 6.640766 14.505583
21 -97.533493 39.047596
22 6.931842 -84.173057
23 -97.272500 -44.429392
24 99.477056 -54.879872
25 -78.996929 -96.739844
26 -31.674510 61.639612
27 -56.536075 86.920994
28 97.699575 -97.796661
29 56.980551 37.072724
... ... ...
121 89.841848 -55.198411
122 15.997366 -84.731802
123 57.065474 -1.286114
124 8.397404 45.994062
125 -95.971359 91.328450
126 33.324722 -82.136313
127 34.783261 52.531436
128 45.139227 -60.250218
129 35.987597 83.219655
130 67.314264 13.003851
131 -36.886862 -35.034144
132 42.068799 65.334579
133 -69.769883 -43.590844
134 33.143474 -27.783041
135 -41.797934 75.064175
136 5.324715 37.861594
137 68.512768 -50.739106
138 -64.144841 -50.464696
139 -26.845766 79.781956
140 0.068680 88.957681
141 18.895939 -56.449630
142 -26.104390 40.905810
143 -78.601095 8.400365
144 28.941010 83.297786
145 -61.078038 33.677658
146 44.080113 -41.024718
147 -61.088577 2.871590
148 15.453097 21.393731
149 26.546590 68.767646
150 -63.012893 11.913804

151 rows Ă— 2 columns

Plot problem

plt.scatter(data.x, data.y, c='r', marker='o', s=40)
plt.scatter(data.iloc[0].x, data.iloc[0].y, marker='*', c='r', s=400)
plt.axis([-100,100,-100,100])
plt.grid(True)

png

Compute distance matrix

distance_func = lambda a,b: np.sqrt((a.x-b.x)**2 + (a.y-b.y)**2)
def compute_distances(dfunc=distance_func):
    for i in range(size+1):
        current=data.iloc[i]
        data[i]=dfunc(current, data)
        #data[str(i)][i]=np.nan

%time compute_distances()
data
CPU times: user 346 ms, sys: 5.93 ms, total: 352 ms
Wall time: 357 ms
<style scoped> .dataframe tbody tr th:only-of-type { vertical-align: middle; }
.dataframe tbody tr th {
    vertical-align: top;
}

.dataframe thead th {
    text-align: right;
}
</style>
x y 0 1 2 3 4 5 6 7 ... 141 142 143 144 145 146 147 148 149 150
0 0.000000 0.000000 0.000000 30.094619 98.906970 86.402846 103.078947 106.124389 74.577630 106.846484 ... 59.528289 48.525504 79.048708 88.182216 69.747483 60.216973 61.156032 26.391096 73.713707 64.129271
1 30.074848 1.090675 30.094619 0.000000 79.199277 63.440275 96.539672 123.683115 68.434599 98.436519 ... 58.616164 68.857475 108.921496 82.214930 96.802687 44.383034 91.180819 25.020186 67.768880 93.714821
2 75.720294 -63.631955 98.906970 79.199277 0.000000 113.781493 166.719068 128.062552 141.682044 42.996311 ... 57.276463 145.932898 170.304863 154.196790 167.877766 38.886864 152.116365 104.218532 141.236354 157.968538
3 70.446614 50.027257 86.402846 63.440275 113.781493 0.000000 60.390171 187.123389 47.464297 147.701132 ... 118.299618 96.980912 154.751471 53.194391 132.536951 94.792692 139.732470 62.001337 47.732738 138.795084
4 33.220333 97.579090 103.078947 96.539672 166.719068 60.390171 0.000000 208.633848 28.765741 193.924735 ... 154.693357 82.044400 143.027539 14.908663 113.910385 139.028595 133.655082 78.229684 29.574281 128.838562
5 -48.606315 -94.338815 106.124389 123.683115 128.062552 187.123389 208.633848 0.000000 180.468687 95.852974 ... 77.408944 137.103775 107.028154 193.825565 128.622553 106.925989 98.008518 132.278609 179.587519 107.224850
6 27.143823 69.462477 74.577630 68.434599 141.682044 47.464297 28.765741 180.468687 0.000000 166.517540 ... 126.181957 60.422310 122.108842 13.951546 95.203204 111.777718 110.540955 49.469965 0.916230 106.958325
7 47.234925 -95.838578 106.846484 98.436519 42.996311 147.701132 193.924735 95.852974 166.517540 0.000000 ... 48.524090 155.169851 163.402757 180.068054 168.837654 54.904573 146.552646 121.463982 165.901224 154.159518
8 -77.679374 -40.455252 87.582604 115.486087 155.140639 173.575323 177.065594 61.226474 151.887491 136.641483 ... 97.890812 96.330687 48.864310 163.348464 75.969024 121.760819 46.394717 111.798720 150.972491 54.384039
9 37.394038 72.325211 81.420208 71.609564 141.255984 39.870685 25.596449 187.544551 10.642469 168.451485 ... 130.096654 70.846519 132.443410 13.851032 105.784607 113.546950 120.509879 55.456475 11.415928 117.179733
10 -60.273128 31.437806 67.979303 95.308474 165.929113 132.034914 114.523783 126.316558 95.328899 166.605100 ... 118.287542 35.456251 29.438717 103.192151 2.380087 127.044938 28.577853 76.389427 94.504923 19.715298
11 39.931126 -29.521506 49.658978 32.159786 49.440745 85.200944 127.277634 109.727672 99.806534 66.718059 ... 34.170205 96.543753 124.450615 113.353321 119.151104 12.228572 106.086252 56.493675 99.196287 110.970068
12 57.992110 62.809588 85.487596 67.739189 127.678315 17.846642 42.691441 189.891666 31.557530 159.012444 ... 125.504070 86.902225 147.030837 35.549018 122.582092 104.762143 133.314565 59.370370 32.004987 131.272965
13 -60.515743 89.891059 108.363082 126.854891 205.254899 136.895075 94.050826 184.614411 90.008480 214.722389 ... 166.498686 59.863977 83.473428 89.699398 56.216213 167.568594 87.021354 102.289533 89.588215 78.017229
14 -4.679923 33.320070 33.647120 47.398608 125.951935 76.961852 74.603291 135.004884 48.156250 139.201679 ... 92.813901 22.727764 78.008534 60.234037 56.399249 88.908315 64.101842 23.400342 47.240087 62.136653
15 -57.737593 61.505265 84.359512 106.587745 182.948985 128.697068 97.850218 156.111362 85.253574 189.146277 ... 140.662914 37.749133 57.056254 89.376138 28.027384 144.496514 58.729353 83.461441 84.596487 49.871252
16 -36.062776 -41.212805 54.763301 78.509679 114.009092 140.246209 155.123626 54.586750 127.452314 99.611656 ... 57.031756 82.720230 65.352699 140.457750 78.957867 80.143110 50.692451 81.076899 126.552884 59.571347
17 -39.616364 65.577880 76.615369 94.949802 173.198517 111.156111 79.556659 160.169188 66.873109 183.298716 ... 135.330717 28.129780 69.203161 70.810371 38.447726 135.533075 66.280727 70.603715 66.239800 58.542554
18 10.506738 -61.664519 62.553213 65.735267 65.243228 126.758990 160.855321 67.542303 132.178220 50.167978 ... 9.877943 108.908434 113.354726 146.129710 119.224623 39.410315 96.388788 83.205405 131.414712 104.013969
19 42.851348 27.974071 51.174082 29.765012 97.324363 35.324803 70.268165 152.725068 44.362306 123.890225 ... 87.756612 70.157849 123.019616 57.045691 104.085773 69.009729 106.928212 28.177386 43.931320 107.075533
20 6.640766 14.505583 15.953423 27.002147 104.295043 73.027225 87.222021 122.062865 58.656932 117.574315 ... 72.005774 42.062065 85.460217 72.316444 70.380430 66.972524 68.721275 11.184979 57.798040 69.701862
21 -97.533493 39.047596 105.059492 133.133829 201.395046 168.338555 143.256758 142.076751 128.333542 197.869084 ... 150.583972 71.453269 36.023443 133.992086 36.848832 162.683708 51.351098 114.357458 127.589765 43.908023
22 6.931842 -84.173057 84.458001 88.348756 71.789888 148.471716 183.643479 56.460868 154.959354 41.957394 ... 30.194834 129.368139 126.038572 168.910884 136.066655 56.936572 110.469669 105.910143 154.193375 118.848436
23 -97.272500 -44.429392 106.938815 135.238395 174.055293 192.488336 192.859504 69.709024 168.673588 153.379595 ... 116.788665 111.117040 56.032174 179.566372 86.085715 141.393610 59.553834 130.536369 167.763931 65.941462
24 99.477056 -54.879872 113.611114 89.159232 25.317636 108.849770 166.233837 153.250426 143.851022 66.384153 ... 80.596406 157.941751 188.987345 155.139934 183.358596 57.103298 170.635735 113.479903 143.553342 175.682608
25 -78.996929 -96.739844 124.896406 146.517791 158.219947 209.461105 224.393766 30.485314 197.203121 126.235072 ... 105.859884 147.458288 105.140954 209.914619 131.642742 135.100458 101.208433 151.249294 196.296113 109.823061
26 -31.674510 61.639612 69.301633 86.482119 165.004877 102.779232 74.182119 156.894728 59.336275 176.142212 ... 128.461820 21.468972 70.968457 64.368608 40.576327 127.588116 65.718093 61.973721 58.655820 58.777123
27 -56.536075 86.920994 103.689859 121.935621 200.394455 132.233699 90.386990 181.433181 85.481724 210.165367 ... 162.003470 55.167786 81.561966 85.553841 53.436712 162.768923 84.172605 97.346099 85.042773 75.286305
28 97.699575 -97.796661 138.236731 119.799035 40.624081 150.315118 205.740751 146.346747 181.531632 50.502624 ... 88.992079 185.918792 205.814807 193.708387 206.145160 78.090334 188.010037 144.813096 181.125415 194.589012
29 56.980551 37.072724 67.979188 44.929107 102.433443 18.685684 65.004371 168.575143 44.037785 133.268118 ... 100.979544 83.173313 138.580254 54.064519 118.107395 79.155743 122.922888 44.388740 43.940802 122.602601
... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
121 89.841848 -55.198411 105.443930 82.100886 16.448190 106.998208 162.932381 143.874477 139.539885 58.881007 ... 70.956942 150.597316 180.049519 151.294774 175.144991 47.906471 161.716165 106.770982 139.190062 166.938975
122 15.997366 -84.731802 86.228731 86.969380 63.340601 145.343471 183.122614 65.314090 154.596635 33.153364 ... 28.430318 132.504217 132.749649 168.527388 141.284883 51.951419 116.690174 106.126929 153.861518 124.831864
123 57.065474 -1.286114 57.079966 27.095074 65.076925 53.029397 101.700144 140.802458 76.815809 95.062127 ... 67.081494 93.259771 136.011933 89.137095 123.208583 41.806413 118.227181 47.391617 76.412903 120.801706
124 8.397404 45.994062 46.754360 49.862068 128.647717 62.180150 57.246772 151.468612 30.036557 147.053904 ... 102.980237 34.874979 94.773546 42.586471 70.558705 94.050645 81.779271 25.592168 29.120939 79.125814
125 -95.971359 91.328450 132.481650 155.017749 231.280675 171.466411 129.342815 191.613623 125.041868 235.668275 ... 187.170662 86.161684 84.727760 125.170250 67.388112 192.696071 95.086406 131.553313 124.577837 85.982245
126 33.324722 -82.136313 88.639219 83.290415 46.257927 137.277982 179.715433 82.834751 151.724741 19.525516 ... 29.461763 136.642539 143.959295 165.492170 149.414715 42.495197 127.044144 105.061245 151.056109 134.634173
127 34.783261 52.531436 63.003389 51.655794 123.165636 35.751163 45.074759 168.892546 18.574746 148.891587 ... 110.133009 61.987590 121.669896 31.316133 97.697766 94.016941 107.969947 36.649855 18.205969 105.895608
128 45.139227 -60.250218 75.283720 63.163602 30.767480 113.144091 158.278711 99.750986 130.955022 35.650012 ... 26.517063 123.726290 141.508196 144.459031 141.790525 19.254651 123.566617 86.873475 130.350663 130.017410
129 35.987597 83.219655 90.667624 82.341544 152.131793 47.845157 14.623649 196.680299 16.354579 179.411128 ... 140.711171 75.139046 136.852089 7.047020 108.977736 124.507642 126.014265 65.146838 17.262478 122.006644
130 67.314264 13.003851 68.558809 39.098566 77.095448 37.155675 91.188634 157.987432 69.290986 110.679059 ... 84.664752 97.496483 145.987959 80.085853 130.046105 58.812516 128.801988 52.535424 69.076799 130.331715
131 -36.886862 -35.034144 50.872702 76.084644 116.181782 136.952243 150.004295 60.451548 122.553957 103.796215 ... 59.752355 76.701618 60.221539 135.409580 72.845897 81.188287 44.972966 76.964773 121.649555 53.727826
132 42.068799 65.334579 77.707085 65.353914 133.284620 32.243053 33.436564 183.623444 15.485298 161.255931 ... 123.969250 72.417874 133.426864 22.248948 107.895462 106.378312 120.594648 51.373083 15.897325 117.881047
133 -69.769883 -43.590844 82.267845 109.386510 146.864011 168.597197 174.745343 54.984118 148.907085 128.140356 ... 89.593395 95.112353 52.735908 160.762448 77.755833 113.878913 47.266508 107.172530 147.990855 55.914424
134 33.143474 -27.783041 43.247974 29.036321 55.659054 86.290015 125.362154 105.416788 97.430420 69.499101 ... 32.011960 90.710902 117.456747 111.160293 112.494937 17.174169 99.092814 52.261883 96.775793 104.028296
135 -41.797934 75.064175 85.916806 103.139593 181.788752 115.002981 78.324082 169.539751 69.168959 192.703401 ... 144.843457 37.590972 76.148121 71.216505 45.657050 144.401073 74.725486 78.474180 68.633958 66.618645
136 5.324715 37.861594 38.234185 44.324593 123.517116 66.248509 65.911644 142.777814 38.401684 140.114958 ... 95.282659 31.576193 88.946645 51.207196 66.534434 87.892156 75.066808 19.333251 37.490693 73.097992
137 68.512768 -50.739106 85.255242 64.527513 14.770714 100.784918 152.459316 124.971254 127.121243 49.866912 ... 49.944368 131.723944 158.555876 139.756261 154.660813 26.293040 140.251971 89.545938 126.661060 145.685918
138 -64.144841 -50.464696 81.616458 107.402542 140.483568 167.968724 177.191816 46.544432 150.718768 120.267375 ... 83.256175 98.972952 60.614178 162.964343 84.198224 108.635878 53.423778 107.235560 149.804162 62.388769
139 -26.845766 79.781956 84.177525 97.119896 176.316042 101.740598 62.647221 175.475253 54.966966 190.605668 ... 143.705771 38.883215 88.169982 55.897455 57.423469 140.088304 84.188922 72.099782 54.516591 76.903493
140 0.068680 88.957681 88.957708 92.849238 170.313722 80.427803 34.254355 189.649310 33.363548 190.720508 ... 146.621116 54.717565 112.598467 29.421860 82.430589 137.231302 105.598414 69.293345 33.297406 99.574313
141 18.895939 -56.449630 59.528289 58.616164 57.276463 118.299618 154.693357 77.408944 126.181957 48.524090 ... 0.000000 107.252558 117.094805 140.107971 120.493838 29.532534 99.581774 77.919459 125.450782 106.689342
142 -26.104390 40.905810 48.525504 68.857475 145.932898 96.980912 82.044400 137.103775 60.422310 155.169851 ... 107.252558 0.000000 61.745510 69.477160 35.712774 107.881768 51.676834 45.910194 59.568512 46.933719
143 -78.601095 8.400365 79.048708 108.921496 170.304863 154.751471 143.027539 107.028154 122.108842 163.402757 ... 117.094805 61.745510 0.000000 131.053150 30.757098 132.263062 18.364522 94.947451 121.244564 15.979246
144 28.941010 83.297786 88.182216 82.214930 154.196790 53.194391 14.908663 193.825565 13.951546 180.068054 ... 140.107971 69.477160 131.053150 0.000000 102.789037 125.240877 120.721578 63.356419 14.726106 116.409592
145 -61.078038 33.677658 69.747483 96.802687 167.877766 132.536951 113.910385 128.622553 95.203204 168.837654 ... 120.493838 35.712774 30.757098 102.789037 0.000000 128.991014 30.806070 77.510705 94.389526 21.849691
146 44.080113 -41.024718 60.216973 44.383034 38.886864 94.792692 139.028595 106.925989 111.777718 54.904573 ... 29.532534 107.881768 132.263062 125.240877 128.991014 0.000000 113.962007 68.670000 111.183576 119.462961
147 -61.088577 2.871590 61.156032 91.180819 152.116365 139.732470 133.655082 98.008518 110.540955 146.552646 ... 99.581774 51.676834 18.364522 120.721578 30.806070 113.962007 0.000000 78.750857 109.645851 9.244708
148 15.453097 21.393731 26.391096 25.020186 104.218532 62.001337 78.229684 132.278609 49.469965 121.463982 ... 77.919459 45.910194 94.947451 63.356419 77.510705 68.670000 78.750857 0.000000 48.655456 79.036577
149 26.546590 68.767646 73.713707 67.768880 141.236354 47.732738 29.574281 179.587519 0.916230 165.901224 ... 125.450782 59.568512 121.244564 14.726106 94.389526 111.183576 109.645851 48.655456 0.000000 106.081385
150 -63.012893 11.913804 64.129271 93.714821 157.968538 138.795084 128.838562 107.224850 106.958325 154.159518 ... 106.689342 46.933719 15.979246 116.409592 21.849691 119.462961 9.244708 79.036577 106.081385 0.000000

151 rows Ă— 153 columns

Helper functions

estimate_cost = lambda route: sum(data.iloc[i][j] for i,j in zip(route, route[1:]))
get_coords = lambda route: list(zip(*[(data.iloc[i].x,data.iloc[i].y) for i in route]))

Scenario: center depot, one van, nearest neighbor heuristic

Apply a greedy NN algorithm

def nearest_neighbor(unserved, stop_condition=lambda route, target: False):
    current=0 #depot
    result_path=[]
    while True:
        result_path.append(current)
        unserved.remove(current)
        if not unserved:
            break

        current=data.iloc[unserved,current+2].idxmin()
        if stop_condition(result_path, int(current)):
            if len(result_path)>1:
                break

    result_path.append(0)
    return result_path

%time route = nearest_neighbor(list(range(size+1)))
print('cost={}\nroute={}'.format(estimate_cost(route),route))
CPU times: user 116 ms, sys: 8.29 ms, total: 125 ms
Wall time: 122 ms
cost=2623.828598616268
route=[0, 53, 60, 20, 66, 148, 55, 51, 1, 120, 104, 123, 74, 93, 130, 42, 29, 19, 91, 107, 81, 11, 134, 117, 57, 30, 34, 67, 75, 46, 39, 131, 16, 114, 72, 96, 38, 22, 122, 92, 36, 126, 113, 7, 58, 111, 28, 108, 63, 2, 137, 50, 128, 69, 141, 18, 146, 37, 54, 95, 24, 121, 35, 83, 3, 49, 12, 73, 105, 129, 90, 144, 9, 86, 132, 31, 70, 127, 149, 6, 71, 41, 140, 76, 102, 32, 100, 97, 139, 88, 78, 26, 17, 135, 27, 13, 110, 89, 59, 119, 40, 15, 56, 145, 10, 106, 82, 94, 115, 87, 98, 44, 64, 52, 14, 33, 136, 124, 65, 142, 150, 147, 143, 109, 112, 23, 47, 101, 45, 138, 99, 133, 8, 48, 62, 80, 103, 43, 68, 61, 125, 21, 25, 118, 5, 79, 116, 77, 85, 84, 4, 0]

Plot result path

coords=get_coords(route)
plt.plot(coords[0], coords[1], 'b-', linewidth=2)
plt.scatter(data.x, data.y, c='r', s=30)
plt.scatter(data.iloc[0].x, data.iloc[0].y, marker='*', c='r', s=400)
plt.axis([-100,100,-100,100])
plt.grid(True)

png

Let's improve it with a 2-opt heuristic

def twoOptSwap(route,i,j):
    t=route[i:j+1];
    t.reverse();
    route[i:j+1]=t

def twoOpt(route):
    cost=estimate_cost(route)

    def inner():
        nonlocal cost
        for i in range(1,len(route)-2):
            nodei=data.iloc[route[i]]
            for j in range(i+1,len(route)-1):
                nodej=data.iloc[route[j]]
                save=nodei.iloc[route[i-1]+2]+nodej.iloc[route[j+1]+2] - (nodej.iloc[route[i-1]+2]+nodei.iloc[route[j+1]+2])
                if save>0:
                    twoOptSwap(route,i,j)

                    cost-=save
                    print('exchanging {}-{},{}-{} with {}-{},{}-{} => save={} => cost: {}'.format(
                            route[i-1],route[i],route[j],route[j+1],route[i-1],route[j],route[i],route[j+1],save,cost))
                    return False
        return True

    while True:
        if inner():
            break

%time twoOpt(route)
exchanging 53-64,60-52 with 53-60,64-52 => save=2.8803537373675177 => cost: 2620.948244878901
...
exchanging 1-120,81-107 with 1-81,120-107 => save=26.496627104257605 => cost: 2100.7350743873462
CPU times: user 3min 11s, sys: 1.65 s, total: 3min 13s
Wall time: 3min 21s

Plot improved path

coords=get_coords(route)
plt.plot(coords[0], coords[1], 'b-', linewidth=2)
plt.scatter(data.x, data.y, c='r', s=30)
plt.scatter(data.iloc[0].x, data.iloc[0].y, marker='*', c='r', s=400)
plt.axis([-100,100,-100,100])
plt.grid(True)

png

Incredible! A clean path, without any crossing parts!

Scenario: center depot, one van, 2-opt heuristic

Just for fun, let's pass a random route to 2-opt heuristic

route = [x for x in range(size+1)]+[0]
print('cost={}\nroute={}'.format(estimate_cost(route),route))
cost=16332.039263088578
route=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 0]

Plot result path

coords=get_coords(route)
plt.plot(coords[0], coords[1], 'b-', linewidth=2)
plt.scatter(data.x, data.y, c='r', s=30)
plt.scatter(data.iloc[0].x, data.iloc[0].y, marker='*', c='r', s=400)
plt.axis([-100,100,-100,100])
plt.grid(True)

png

Let's see what 2-opt heuristic can do

%time twoOpt(route)
exchanging 0-4,1-5 with 0-1,4-5 => save=11.966404491447804 => cost: 16320.07285859713
...
exchanging 47-23,112-8 with 47-112,23-8 => save=11.556726776627453 => cost: 2181.5435075388827
CPU times: user 19min 11s, sys: 8.18 s, total: 19min 19s
Wall time: 19min 44s

Plot improved path

coords=get_coords(route)
plt.plot(coords[0], coords[1], 'b-', linewidth=2)
plt.scatter(data.x, data.y, c='r', s=30)
plt.scatter(data.iloc[0].x, data.iloc[0].y, marker='*', c='r', s=400)
plt.axis([-100,100,-100,100])
plt.grid(True)

png

WOW, very cool, a clean path too, almost as good as the previous one.

But extremely slower... It took ~19 minutes, while NN + 2-opt took only ~3 minutes.

Scenario: center depot, several vans, no clustering

Let's apply a sequential NN algorithm, but including a max cost constraint

def sequential_nn(max_cost):
    unserved=list(range(size+1))
    result=[]
    while True:
        result_path = nearest_neighbor(unserved, lambda route, target: estimate_cost(route+[target,0])>=max_cost)
        result.append(result_path)
        print('van {}: {}'.format(len(result), estimate_cost(result_path)))

        if not unserved:
            break
        unserved.append(0)
    return result

%time result_paths = sequential_nn(400)
van 1: 389.0742611200774
van 2: 398.3533734081084
van 3: 397.4195886051539
van 4: 390.9917686566429
van 5: 371.6762623788105
van 6: 320.29683749922486
van 7: 364.8394134778564
van 8: 320.99556479051967
van 9: 210.1189842618746
van 10: 276.59421133431306
CPU times: user 1.48 s, sys: 24.4 ms, total: 1.51 s
Wall time: 1.54 s

Plot result paths

for path in result_paths:
    coords=get_coords(path)
    plt.plot(coords[0], coords[1], linewidth=2)
plt.scatter(data.x, data.y, c='r', s=30)
plt.scatter(data.iloc[0].x, data.iloc[0].y, marker='*', c='r', s=400)
plt.axis([-100,100,-100,100])
plt.grid(True)

png

Let's improve them with a 2-opt heuristic

def improve_seq_nn():
    for i,path in enumerate(result_paths):
        print('Starting path {}/{}'.format(i+1, len(result_paths)))
        twoOpt(path)

%time improve_seq_nn()
Starting path 1/10
exchanging 55-19,51-91 with 55-51,19-91 => save=2.6873147586143844 => cost: 386.386946361463
...
exchanging 67-39,75-0 with 67-75,39-0 => save=4.275672113835263 => cost: 368.50842741951476
Starting path 2/10
exchanging 17-97,78-0 with 17-78,97-0 => save=0.09782392307953103 => cost: 398.25554948502884
...
exchanging 88-78,26-0 with 88-26,78-0 => save=1.6805548383893267 => cost: 394.249851279636
Starting path 3/10
Starting path 4/10
exchanging 124-127,65-0 with 124-65,127-0 => save=0.5258127779938491 => cost: 390.465955878649
exchanging 14-65,33-0 with 14-33,65-0 => save=3.343148155406432 => cost: 387.1228077232426
Starting path 5/10
exchanging 0-18,141-69 with 0-141,18-69 => save=6.7520080457503155 => cost: 364.9242543330602
exchanging 50-121,146-0 with 50-146,121-0 => save=41.908681513869396 => cost: 323.0155728191908
Starting path 6/10
exchanging 47-45,101-138 with 47-101,45-138 => save=1.4275147235708587 => cost: 318.869322775654
Starting path 7/10
exchanging 3-35,83-77 with 3-83,35-77 => save=3.633104522812438 => cost: 361.20630895504394
...
exchanging 90-129,144-0 with 90-144,129-0 => save=5.489882024385494 => cost: 347.690672350374
Starting path 8/10
Starting path 9/10
Starting path 10/10
CPU times: user 3.25 s, sys: 37.7 ms, total: 3.29 s
Wall time: 3.31 s

Plot improved paths

for path in result_paths:
    coords=get_coords(path)
    plt.plot(coords[0], coords[1], linewidth=2)
plt.scatter(data.x, data.y, c='r', s=30)
plt.scatter(data.iloc[0].x, data.iloc[0].y, marker='*', c='r', s=400)
plt.axis([-100,100,-100,100])
plt.grid(True)

png

Great! Several clean paths, but with many superpositions, let's improve them once more.

Scenario: center depot, several vans, KMeans clustering

Compute delivery clusters

from sklearn.cluster import KMeans

work_per_van=20 #how many deliveries each van will start, ie granularity; a better approach would be capacity.
model = KMeans(n_clusters=1+size//work_per_van, init='k-means++', random_state=0)
%time model.fit(data[['x', 'y']])
CPU times: user 75.7 ms, sys: 4.05 ms, total: 79.7 ms
Wall time: 92.8 ms





KMeans(algorithm='auto', copy_x=True, init='k-means++', max_iter=300,
    n_clusters=8, n_init=10, n_jobs=1, precompute_distances='auto',
    random_state=0, tol=0.0001, verbose=0)

Plot clusters

plt.scatter(data.x, data.y, marker='o', c=model.labels_, s=200)
plt.scatter(model.cluster_centers_[:,0], model.cluster_centers_[:,1], marker='+', c='r', s=500)
plt.scatter(data.iloc[0].x, data.iloc[0].y, marker='*', c='r', s=400)
plt.axis([-100,100,-100,100])
plt.grid(True)

png

Let's apply a greedy NN algorithm sequentially, on each of the clusters

def greedy_nn_clusters():
    result=[]
    for i in range(model.n_clusters):
        unserved=data[model.labels_ == i].index.tolist()
        if 0 not in unserved:
            unserved.append(0)
        result_path = nearest_neighbor(unserved)
        result.append(result_path)
        print('van {}: {}'.format(i+1, estimate_cost(result_path)))
    return result

%time result_paths = greedy_nn_clusters()
van 1: 409.3080162039939
van 2: 266.4745473994821
van 3: 413.3606064604762
van 4: 446.80922078430706
van 5: 457.66477785115126
van 6: 455.80304195030294
van 7: 459.76894476196577
van 8: 376.5008949566861
CPU times: user 164 ms, sys: 10.1 ms, total: 174 ms
Wall time: 174 ms

Plot result paths

plt.scatter(data.x, data.y, marker='o', c=model.labels_, s=200)
plt.scatter(model.cluster_centers_[:,0], model.cluster_centers_[:,1], marker='+', c='r', s=500)
for path in result_paths:
    coords=get_coords(path)
    plt.plot(coords[0], coords[1], 'k-', linewidth=2)
plt.scatter(data.iloc[0].x, data.iloc[0].y, marker='*', c='r', s=400)
plt.axis([-100,100,-100,100])
plt.grid(True)

png

Let's improve them with a 2-opt heuristic

def improve_result_paths():
    for i, path in enumerate(result_paths):
        print('Starting path {}/{}'.format(i+1, len(result_paths)))
        twoOpt(path)

%time improve_result_paths()
Starting path 1/8
exchanging 48-112,99-138 with 48-99,112-138 => save=11.5162692633929 => cost: 397.791746940601
exchanging 45-118,25-5 with 45-25,118-5 => save=13.984640981159586 => cost: 383.8071059594414
Starting path 2/8
exchanging 148-52,136-65 with 148-136,52-65 => save=1.6057804518926915 => cost: 264.8687669475894
exchanging 148-124,52-142 with 148-52,124-142 => save=6.904413311483367 => cost: 257.964353636106
Starting path 3/8
exchanging 63-24,108-111 with 63-108,24-111 => save=11.657922849361384 => cost: 401.7026836111148
...
exchanging 113-36,126-0 with 113-126,36-0 => save=7.772149456496223 => cost: 378.1902685773841
Starting path 4/8
exchanging 147-109,150-0 with 147-150,109-0 => save=5.601665728075147 => cost: 441.2075550562319
...
exchanging 62-109,143-150 with 62-143,109-150 => save=0.5147852919035643 => cost: 394.93412566866925
Starting path 5/8
exchanging 9-149,6-144 with 9-6,149-144 => save=0.0011015802705607314 => cost: 457.66367627088067
...
exchanging 105-129,144-90 with 105-144,129-90 => save=3.918490824545831 => cost: 407.2051777421843
Starting path 6/8
exchanging 30-69,34-116 with 30-34,69-116 => save=1.1688372549307786 => cost: 454.63420469537215
...
exchanging 22-116,79-38 with 22-79,116-38 => save=5.039989423215701 => cost: 380.39750649818404
Starting path 7/8
exchanging 0-55,1-107 with 0-1,55-107 => save=14.962441964752642 => cost: 444.8065027972131
...
exchanging 0-107,55-42 with 0-55,107-42 => save=6.044195398723886 => cost: 403.197665386089
Starting path 8/8
exchanging 0-71,26-59 with 0-26,71-59 => save=17.738760993960298 => cost: 358.76213396272584
...
exchanging 17-78,26-88 with 17-26,78-88 => save=0.17155006280330554 => cost: 319.53217682612376
CPU times: user 2.81 s, sys: 64.8 ms, total: 2.87 s
Wall time: 3.03 s

Plot improved paths

plt.scatter(data.x, data.y, marker='o', c=model.labels_, s=200)
plt.scatter(model.cluster_centers_[:,0], model.cluster_centers_[:,1], marker='+', c='r', s=500)
for path in result_paths:
    coords=get_coords(path)
    plt.plot(coords[0], coords[1], 'k-', linewidth=2)
plt.scatter(data.iloc[0].x, data.iloc[0].y, marker='*', c='r', s=400)
plt.axis([-100,100,-100,100])
plt.grid(True)

png

Cool clean paths, with clearly defined cluster subsections!

Let's change the depot to the farthest point

Find farthest point and set it as new depot

maxid=data[0].idxmax()
print('farthest point={}; distance={}; coords={}'.format(maxid, data.iloc[maxid,2], tuple(data.iloc[maxid][['x','y']].tolist())))
data.drop(data.columns.difference(['x', 'y']), axis=1, inplace=True)
data.iloc[0]=data.iloc[maxid]
data.drop(maxid, inplace=True)
data.reset_index(drop=True, inplace=True)
size-=1
data
farthest point=84; distance=138.29710566715653; coords=(99.07656719022526, 96.48794364952255)
<style scoped> .dataframe tbody tr th:only-of-type { vertical-align: middle; }
.dataframe tbody tr th {
    vertical-align: top;
}

.dataframe thead th {
    text-align: right;
}
</style>
x y
0 99.076567 96.487944
1 30.074848 1.090675
2 75.720294 -63.631955
3 70.446614 50.027257
4 33.220333 97.579090
5 -48.606315 -94.338815
6 27.143823 69.462477
7 47.234925 -95.838578
8 -77.679374 -40.455252
9 37.394038 72.325211
10 -60.273128 31.437806
11 39.931126 -29.521506
12 57.992110 62.809588
13 -60.515743 89.891059
14 -4.679923 33.320070
15 -57.737593 61.505265
16 -36.062776 -41.212805
17 -39.616364 65.577880
18 10.506738 -61.664519
19 42.851348 27.974071
20 6.640766 14.505583
21 -97.533493 39.047596
22 6.931842 -84.173057
23 -97.272500 -44.429392
24 99.477056 -54.879872
25 -78.996929 -96.739844
26 -31.674510 61.639612
27 -56.536075 86.920994
28 97.699575 -97.796661
29 56.980551 37.072724
... ... ...
120 89.841848 -55.198411
121 15.997366 -84.731802
122 57.065474 -1.286114
123 8.397404 45.994062
124 -95.971359 91.328450
125 33.324722 -82.136313
126 34.783261 52.531436
127 45.139227 -60.250218
128 35.987597 83.219655
129 67.314264 13.003851
130 -36.886862 -35.034144
131 42.068799 65.334579
132 -69.769883 -43.590844
133 33.143474 -27.783041
134 -41.797934 75.064175
135 5.324715 37.861594
136 68.512768 -50.739106
137 -64.144841 -50.464696
138 -26.845766 79.781956
139 0.068680 88.957681
140 18.895939 -56.449630
141 -26.104390 40.905810
142 -78.601095 8.400365
143 28.941010 83.297786
144 -61.078038 33.677658
145 44.080113 -41.024718
146 -61.088577 2.871590
147 15.453097 21.393731
148 26.546590 68.767646
149 -63.012893 11.913804

150 rows Ă— 2 columns

Plot relocated depot

plt.scatter(data.x, data.y, c='r', marker='o', s=40)
plt.scatter(data.iloc[0].x, data.iloc[0].y, marker='*', c='r', s=400)
plt.axis([-100,100,-100,100])
plt.grid(True)

png

Recompute distance matrix

%time compute_distances()
data
CPU times: user 365 ms, sys: 5.95 ms, total: 371 ms
Wall time: 374 ms
<style scoped> .dataframe tbody tr th:only-of-type { vertical-align: middle; }
.dataframe tbody tr th {
    vertical-align: top;
}

.dataframe thead th {
    text-align: right;
}
</style>
x y 0 1 2 3 4 5 6 7 ... 140 141 142 143 144 145 146 147 148 149
0 99.076567 96.487944 0.000000 117.736469 161.814392 54.573525 65.865272 241.298748 76.842016 199.190980 ... 172.681309 136.965856 198.314834 71.365094 172.030897 148.102471 185.517910 112.392284 77.646716 182.827181
1 30.074848 1.090675 117.736469 0.000000 79.199277 63.440275 96.539672 123.683115 68.434599 98.436519 ... 58.616164 68.857475 108.921496 82.214930 96.802687 44.383034 91.180819 25.020186 67.768880 93.714821
2 75.720294 -63.631955 161.814392 79.199277 0.000000 113.781493 166.719068 128.062552 141.682044 42.996311 ... 57.276463 145.932898 170.304863 154.196790 167.877766 38.886864 152.116365 104.218532 141.236354 157.968538
3 70.446614 50.027257 54.573525 63.440275 113.781493 0.000000 60.390171 187.123389 47.464297 147.701132 ... 118.299618 96.980912 154.751471 53.194391 132.536951 94.792692 139.732470 62.001337 47.732738 138.795084
4 33.220333 97.579090 65.865272 96.539672 166.719068 60.390171 0.000000 208.633848 28.765741 193.924735 ... 154.693357 82.044400 143.027539 14.908663 113.910385 139.028595 133.655082 78.229684 29.574281 128.838562
5 -48.606315 -94.338815 241.298748 123.683115 128.062552 187.123389 208.633848 0.000000 180.468687 95.852974 ... 77.408944 137.103775 107.028154 193.825565 128.622553 106.925989 98.008518 132.278609 179.587519 107.224850
6 27.143823 69.462477 76.842016 68.434599 141.682044 47.464297 28.765741 180.468687 0.000000 166.517540 ... 126.181957 60.422310 122.108842 13.951546 95.203204 111.777718 110.540955 49.469965 0.916230 106.958325
7 47.234925 -95.838578 199.190980 98.436519 42.996311 147.701132 193.924735 95.852974 166.517540 0.000000 ... 48.524090 155.169851 163.402757 180.068054 168.837654 54.904573 146.552646 121.463982 165.901224 154.159518
8 -77.679374 -40.455252 223.598080 115.486087 155.140639 173.575323 177.065594 61.226474 151.887491 136.641483 ... 97.890812 96.330687 48.864310 163.348464 75.969024 121.760819 46.394717 111.798720 150.972491 54.384039
9 37.394038 72.325211 66.246298 71.609564 141.255984 39.870685 25.596449 187.544551 10.642469 168.451485 ... 130.096654 70.846519 132.443410 13.851032 105.784607 113.546950 120.509879 55.456475 11.415928 117.179733
10 -60.273128 31.437806 172.115792 95.308474 165.929113 132.034914 114.523783 126.316558 95.328899 166.605100 ... 118.287542 35.456251 29.438717 103.192151 2.380087 127.044938 28.577853 76.389427 94.504923 19.715298
11 39.931126 -29.521506 139.199730 32.159786 49.440745 85.200944 127.277634 109.727672 99.806534 66.718059 ... 34.170205 96.543753 124.450615 113.353321 119.151104 12.228572 106.086252 56.493675 99.196287 110.970068
12 57.992110 62.809588 53.124047 67.739189 127.678315 17.846642 42.691441 189.891666 31.557530 159.012444 ... 125.504070 86.902225 147.030837 35.549018 122.582092 104.762143 133.314565 59.370370 32.004987 131.272965
13 -60.515743 89.891059 159.728596 126.854891 205.254899 136.895075 94.050826 184.614411 90.008480 214.722389 ... 166.498686 59.863977 83.473428 89.699398 56.216213 167.568594 87.021354 102.289533 89.588215 78.017229
14 -4.679923 33.320070 121.472588 47.398608 125.951935 76.961852 74.603291 135.004884 48.156250 139.201679 ... 92.813901 22.727764 78.008534 60.234037 56.399249 88.908315 64.101842 23.400342 47.240087 62.136653
15 -57.737593 61.505265 160.668816 106.587745 182.948985 128.697068 97.850218 156.111362 85.253574 189.146277 ... 140.662914 37.749133 57.056254 89.376138 28.027384 144.496514 58.729353 83.461441 84.596487 49.871252
16 -36.062776 -41.212805 192.935581 78.509679 114.009092 140.246209 155.123626 54.586750 127.452314 99.611656 ... 57.031756 82.720230 65.352699 140.457750 78.957867 80.143110 50.692451 81.076899 126.552884 59.571347
17 -39.616364 65.577880 142.095606 94.949802 173.198517 111.156111 79.556659 160.169188 66.873109 183.298716 ... 135.330717 28.129780 69.203161 70.810371 38.447726 135.533075 66.280727 70.603715 66.239800 58.542554
18 10.506738 -61.664519 181.264492 65.735267 65.243228 126.758990 160.855321 67.542303 132.178220 50.167978 ... 9.877943 108.908434 113.354726 146.129710 119.224623 39.410315 96.388788 83.205405 131.414712 104.013969
19 42.851348 27.974071 88.630841 29.765012 97.324363 35.324803 70.268165 152.725068 44.362306 123.890225 ... 87.756612 70.157849 123.019616 57.045691 104.085773 69.009729 106.928212 28.177386 43.931320 107.075533
20 6.640766 14.505583 123.553571 27.002147 104.295043 73.027225 87.222021 122.062865 58.656932 117.574315 ... 72.005774 42.062065 85.460217 72.316444 70.380430 66.972524 68.721275 11.184979 57.798040 69.701862
21 -97.533493 39.047596 204.828975 133.133829 201.395046 168.338555 143.256758 142.076751 128.333542 197.869084 ... 150.583972 71.453269 36.023443 133.992086 36.848832 162.683708 51.351098 114.357458 127.589765 43.908023
22 6.931842 -84.173057 202.802977 88.348756 71.789888 148.471716 183.643479 56.460868 154.959354 41.957394 ... 30.194834 129.368139 126.038572 168.910884 136.066655 56.936572 110.469669 105.910143 154.193375 118.848436
23 -97.272500 -44.429392 241.682957 135.238395 174.055293 192.488336 192.859504 69.709024 168.673588 153.379595 ... 116.788665 111.117040 56.032174 179.566372 86.085715 141.393610 59.553834 130.536369 167.763931 65.941462
24 99.477056 -54.879872 151.368346 89.159232 25.317636 108.849770 166.233837 153.250426 143.851022 66.384153 ... 80.596406 157.941751 188.987345 155.139934 183.358596 57.103298 170.635735 113.479903 143.553342 175.682608
25 -78.996929 -96.739844 262.768240 146.517791 158.219947 209.461105 224.393766 30.485314 197.203121 126.235072 ... 105.859884 147.458288 105.140954 209.914619 131.642742 135.100458 101.208433 151.249294 196.296113 109.823061
26 -31.674510 61.639612 135.315373 86.482119 165.004877 102.779232 74.182119 156.894728 59.336275 176.142212 ... 128.461820 21.468972 70.968457 64.368608 40.576327 127.588116 65.718093 61.973721 58.655820 58.777123
27 -56.536075 86.920994 155.906450 121.935621 200.394455 132.233699 90.386990 181.433181 85.481724 210.165367 ... 162.003470 55.167786 81.561966 85.553841 53.436712 162.768923 84.172605 97.346099 85.042773 75.286305
28 97.699575 -97.796661 194.289484 119.799035 40.624081 150.315118 205.740751 146.346747 181.531632 50.502624 ... 88.992079 185.918792 205.814807 193.708387 206.145160 78.090334 188.010037 144.813096 181.125415 194.589012
29 56.980551 37.072724 72.816502 44.929107 102.433443 18.685684 65.004371 168.575143 44.037785 133.268118 ... 100.979544 83.173313 138.580254 54.064519 118.107395 79.155743 122.922888 44.388740 43.940802 122.602601
... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
120 89.841848 -55.198411 151.967201 82.100886 16.448190 106.998208 162.932381 143.874477 139.539885 58.881007 ... 70.956942 150.597316 180.049519 151.294774 175.144991 47.906471 161.716165 106.770982 139.190062 166.938975
121 15.997366 -84.731802 199.355838 86.969380 63.340601 145.343471 183.122614 65.314090 154.596635 33.153364 ... 28.430318 132.504217 132.749649 168.527388 141.284883 51.951419 116.690174 106.126929 153.861518 124.831864
122 57.065474 -1.286114 106.417566 27.095074 65.076925 53.029397 101.700144 140.802458 76.815809 95.062127 ... 67.081494 93.259771 136.011933 89.137095 123.208583 41.806413 118.227181 47.391617 76.412903 120.801706
123 8.397404 45.994062 103.789897 49.862068 128.647717 62.180150 57.246772 151.468612 30.036557 147.053904 ... 102.980237 34.874979 94.773546 42.586471 70.558705 94.050645 81.779271 25.592168 29.120939 79.125814
124 -95.971359 91.328450 195.116154 155.017749 231.280675 171.466411 129.342815 191.613623 125.041868 235.668275 ... 187.170662 86.161684 84.727760 125.170250 67.388112 192.696071 95.086406 131.553313 124.577837 85.982245
125 33.324722 -82.136313 190.341615 83.290415 46.257927 137.277982 179.715433 82.834751 151.724741 19.525516 ... 29.461763 136.642539 143.959295 165.492170 149.414715 42.495197 127.044144 105.061245 151.056109 134.634173
126 34.783261 52.531436 77.883271 51.655794 123.165636 35.751163 45.074759 168.892546 18.574746 148.891587 ... 110.133009 61.987590 121.669896 31.316133 97.697766 94.016941 107.969947 36.649855 18.205969 105.895608
127 45.139227 -60.250218 165.759126 63.163602 30.767480 113.144091 158.278711 99.750986 130.955022 35.650012 ... 26.517063 123.726290 141.508196 144.459031 141.790525 19.254651 123.566617 86.873475 130.350663 130.017410
128 35.987597 83.219655 64.469107 82.341544 152.131793 47.845157 14.623649 196.680299 16.354579 179.411128 ... 140.711171 75.139046 136.852089 7.047020 108.977736 124.507642 126.014265 65.146838 17.262478 122.006644
129 67.314264 13.003851 89.322100 39.098566 77.095448 37.155675 91.188634 157.987432 69.290986 110.679059 ... 84.664752 97.496483 145.987959 80.085853 130.046105 58.812516 128.801988 52.535424 69.076799 130.331715
130 -36.886862 -35.034144 189.166893 76.084644 116.181782 136.952243 150.004295 60.451548 122.553957 103.796215 ... 59.752355 76.701618 60.221539 135.409580 72.845897 81.188287 44.972966 76.964773 121.649555 53.727826
131 42.068799 65.334579 64.964742 65.353914 133.284620 32.243053 33.436564 183.623444 15.485298 161.255931 ... 123.969250 72.417874 133.426864 22.248948 107.895462 106.378312 120.594648 51.373083 15.897325 117.881047
132 -69.769883 -43.590844 219.388219 109.386510 146.864011 168.597197 174.745343 54.984118 148.907085 128.140356 ... 89.593395 95.112353 52.735908 160.762448 77.755833 113.878913 47.266508 107.172530 147.990855 55.914424
133 33.143474 -27.783041 140.678536 29.036321 55.659054 86.290015 125.362154 105.416788 97.430420 69.499101 ... 32.011960 90.710902 117.456747 111.160293 112.494937 17.174169 99.092814 52.261883 96.775793 104.028296
134 -41.797934 75.064175 142.494221 103.139593 181.788752 115.002981 78.324082 169.539751 69.168959 192.703401 ... 144.843457 37.590972 76.148121 71.216505 45.657050 144.401073 74.725486 78.474180 68.633958 66.618645
135 5.324715 37.861594 110.573318 44.324593 123.517116 66.248509 65.911644 142.777814 38.401684 140.114958 ... 95.282659 31.576193 88.946645 51.207196 66.534434 87.892156 75.066808 19.333251 37.490693 73.097992
136 68.512768 -50.739106 150.366053 64.527513 14.770714 100.784918 152.459316 124.971254 127.121243 49.866912 ... 49.944368 131.723944 158.555876 139.756261 154.660813 26.293040 140.251971 89.545938 126.661060 145.685918
137 -64.144841 -50.464696 219.627654 107.402542 140.483568 167.968724 177.191816 46.544432 150.718768 120.267375 ... 83.256175 98.972952 60.614178 162.964343 84.198224 108.635878 53.423778 107.235560 149.804162 62.388769
138 -26.845766 79.781956 127.025683 97.119896 176.316042 101.740598 62.647221 175.475253 54.966966 190.605668 ... 143.705771 38.883215 88.169982 55.897455 57.423469 140.088304 84.188922 72.099782 54.516591 76.903493
139 0.068680 88.957681 99.293840 92.849238 170.313722 80.427803 34.254355 189.649310 33.363548 190.720508 ... 146.621116 54.717565 112.598467 29.421860 82.430589 137.231302 105.598414 69.293345 33.297406 99.574313
140 18.895939 -56.449630 172.681309 58.616164 57.276463 118.299618 154.693357 77.408944 126.181957 48.524090 ... 0.000000 107.252558 117.094805 140.107971 120.493838 29.532534 99.581774 77.919459 125.450782 106.689342
141 -26.104390 40.905810 136.965856 68.857475 145.932898 96.980912 82.044400 137.103775 60.422310 155.169851 ... 107.252558 0.000000 61.745510 69.477160 35.712774 107.881768 51.676834 45.910194 59.568512 46.933719
142 -78.601095 8.400365 198.314834 108.921496 170.304863 154.751471 143.027539 107.028154 122.108842 163.402757 ... 117.094805 61.745510 0.000000 131.053150 30.757098 132.263062 18.364522 94.947451 121.244564 15.979246
143 28.941010 83.297786 71.365094 82.214930 154.196790 53.194391 14.908663 193.825565 13.951546 180.068054 ... 140.107971 69.477160 131.053150 0.000000 102.789037 125.240877 120.721578 63.356419 14.726106 116.409592
144 -61.078038 33.677658 172.030897 96.802687 167.877766 132.536951 113.910385 128.622553 95.203204 168.837654 ... 120.493838 35.712774 30.757098 102.789037 0.000000 128.991014 30.806070 77.510705 94.389526 21.849691
145 44.080113 -41.024718 148.102471 44.383034 38.886864 94.792692 139.028595 106.925989 111.777718 54.904573 ... 29.532534 107.881768 132.263062 125.240877 128.991014 0.000000 113.962007 68.670000 111.183576 119.462961
146 -61.088577 2.871590 185.517910 91.180819 152.116365 139.732470 133.655082 98.008518 110.540955 146.552646 ... 99.581774 51.676834 18.364522 120.721578 30.806070 113.962007 0.000000 78.750857 109.645851 9.244708
147 15.453097 21.393731 112.392284 25.020186 104.218532 62.001337 78.229684 132.278609 49.469965 121.463982 ... 77.919459 45.910194 94.947451 63.356419 77.510705 68.670000 78.750857 0.000000 48.655456 79.036577
148 26.546590 68.767646 77.646716 67.768880 141.236354 47.732738 29.574281 179.587519 0.916230 165.901224 ... 125.450782 59.568512 121.244564 14.726106 94.389526 111.183576 109.645851 48.655456 0.000000 106.081385
149 -63.012893 11.913804 182.827181 93.714821 157.968538 138.795084 128.838562 107.224850 106.958325 154.159518 ... 106.689342 46.933719 15.979246 116.409592 21.849691 119.462961 9.244708 79.036577 106.081385 0.000000

150 rows Ă— 152 columns

Scenario: farthest depot, one van, nearest neighbor heuristic

Apply a greedy NN algorithm

%time route = nearest_neighbor(list(range(size+1)))
print('cost={}\nroute={}'.format(estimate_cost(route),route))
CPU times: user 111 ms, sys: 13.4 ms, total: 124 ms
Wall time: 118 ms
cost=2598.9001149206997
route=[0, 84, 77, 83, 3, 49, 12, 73, 104, 128, 89, 143, 9, 85, 131, 31, 70, 126, 148, 6, 71, 41, 139, 76, 101, 32, 99, 96, 138, 87, 78, 26, 17, 134, 27, 13, 109, 88, 59, 118, 40, 15, 56, 144, 10, 105, 82, 93, 114, 86, 97, 44, 64, 53, 60, 20, 66, 147, 55, 51, 1, 119, 103, 122, 74, 92, 129, 42, 29, 19, 90, 106, 81, 11, 133, 116, 57, 30, 34, 67, 75, 46, 39, 130, 16, 113, 72, 95, 38, 22, 121, 91, 36, 125, 112, 7, 58, 110, 28, 107, 63, 2, 136, 50, 127, 69, 140, 18, 145, 37, 54, 94, 24, 120, 35, 123, 135, 33, 14, 52, 65, 141, 149, 146, 142, 108, 111, 23, 47, 100, 45, 137, 98, 132, 8, 48, 62, 80, 102, 43, 68, 61, 124, 21, 25, 117, 5, 79, 115, 4, 0]

Plot result path

coords=get_coords(route)
plt.plot(coords[0], coords[1], 'b-', linewidth=2)
plt.scatter(data.x, data.y, c='r', s=30)
plt.scatter(data.iloc[0].x, data.iloc[0].y, marker='*', c='r', s=400)
plt.axis([-100,100,-100,100])
plt.grid(True)

png

Let's improve it with a 2-opt heuristic

%time twoOpt(route)
exchanging 84-4,77-0 with 84-77,4-0 => save=15.967192548480725 => cost: 2582.932922372219
...
exchanging 3-49,12-83 with 3-12,49-83 => save=1.0654890882007315 => cost: 2111.9918767877866
CPU times: user 3min 36s, sys: 1.67 s, total: 3min 38s
Wall time: 3min 44s

Plot improved path

coords=get_coords(route)
plt.plot(coords[0], coords[1], 'b-', linewidth=2)
plt.scatter(data.x, data.y, c='r', s=30)
plt.scatter(data.iloc[0].x, data.iloc[0].y, marker='*', c='r', s=400)
plt.axis([-100,100,-100,100])
plt.grid(True)

png

A great optimized route too.

Scenario: farthest depot, one van, 2-opt heuristic

Just for fun, let's pass a random route to 2-opt heuristic

route = [x for x in range(size+1)]+[0]
print('cost={}\nroute={}'.format(estimate_cost(route),route))
cost=16502.514122712284
route=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 0]

Plot result path

coords=get_coords(route)
plt.plot(coords[0], coords[1], 'b-', linewidth=2)
plt.scatter(data.x, data.y, c='r', s=30)
plt.scatter(data.iloc[0].x, data.iloc[0].y, marker='*', c='r', s=400)
plt.axis([-100,100,-100,100])
plt.grid(True)

png

Let's see what 2-opt heuristic can do

%time twoOpt(route)
exchanging 0-2,1-3 with 0-1,2-3 => save=6.263294946633721 => cost: 16496.25082776565
...
exchanging 31-70,126-131 with 31-126,70-131 => save=1.7915970025161734 => cost: 2147.6785119636334
CPU times: user 30min 1s, sys: 27.7 s, total: 30min 29s
Wall time: 33min 24s

Plot improved path

coords=get_coords(route)
plt.plot(coords[0], coords[1], 'b-', linewidth=2)
plt.scatter(data.x, data.y, c='r', s=30)
plt.scatter(data.iloc[0].x, data.iloc[0].y, marker='*', c='r', s=400)
plt.axis([-100,100,-100,100])
plt.grid(True)

png

Yes, it's beautiful what this heuristic can do.

Only again extremely slower. It's best suited to improve a path, not to build one.

Scenario: farthest depot, several vans, no clustering

Let's apply a sequential NN algorithm, but including a max cost constraint

%time result_paths = sequential_nn(400)
van 1: 385.64822798111754
van 2: 396.65132151762236
van 3: 356.93203827425646
van 4: 396.0161561312648
van 5: 387.061496278307
van 6: 395.6147269472501
van 7: 369.199156243418
van 8: 394.6734767469922
van 9: 397.84112119751114
van 10: 398.459895479128
van 11: 398.88707002367426
van 12: 393.1275886242274
van 13: 399.0252974546198
van 14: 369.5354695202354
van 15: 399.04095929693733
van 16: 398.1246462968952
van 17: 390.2323088432243
van 18: 391.6922432861831
van 19: 396.62966713208937
van 20: 397.37088575736055
van 21: 398.69882895151926
van 22: 398.71167524672734
van 23: 401.9265755043099
van 24: 405.5614801848182
van 25: 405.6059533951813
van 26: 406.6405588064364
van 27: 409.6579507334966
van 28: 416.22815658152126
van 29: 426.0013563494297
van 30: 427.5654816187484
van 31: 428.5781354316992
van 32: 438.7764370279704
van 33: 439.2553078706148
van 34: 445.7400163235422
van 35: 447.1961602342642
van 36: 461.09599384348525
van 37: 464.4374453992292
van 38: 471.7901899743616
van 39: 482.2725996546565
van 40: 482.59749534967307
van 41: 483.3659132930797
van 42: 494.26350457825447
van 43: 525.5364809069648
van 44: 551.3280289580272
CPU times: user 1.22 s, sys: 48.8 ms, total: 1.27 s
Wall time: 1.43 s

Plot result paths

for path in result_paths:
    coords=get_coords(path)
    plt.plot(coords[0], coords[1], linewidth=2)
plt.scatter(data.x, data.y, c='r', s=30)
plt.scatter(data.iloc[0].x, data.iloc[0].y, marker='*', c='r', s=400)
plt.axis([-100,100,-100,100])
plt.grid(True)

png

Max cost 400 doesn't quite work here, as the distances are much larger

%time result_paths = sequential_nn(500)
van 1: 493.1613509811791
van 2: 498.37402590912467
van 3: 499.57415652250484
van 4: 490.0564767221547
van 5: 497.67366460125766
van 6: 491.0474410501304
van 7: 476.1857519522164
van 8: 487.87440569372217
van 9: 462.17325815341474
van 10: 486.2976818275437
van 11: 498.3091236408933
van 12: 466.4397450832517
van 13: 464.4374453992292
van 14: 494.26350457825447
van 15: 525.5364809069648
van 16: 551.3280289580272
CPU times: user 573 ms, sys: 20.1 ms, total: 593 ms
Wall time: 588 ms

Plot result paths

for path in result_paths:
    coords=get_coords(path)
    plt.plot(coords[0], coords[1], linewidth=2)
plt.scatter(data.x, data.y, c='r', s=30)
plt.scatter(data.iloc[0].x, data.iloc[0].y, marker='*', c='r', s=400)
plt.axis([-100,100,-100,100])
plt.grid(True)

png

Let's improve them with a 2-opt heuristic

%time improve_result_paths()
Starting path 1/16
exchanging 84-134,77-0 with 84-77,134-0 => save=17.58671573136749 => cost: 475.57463524981165
...
exchanging 131-9,85-73 with 131-85,9-73 => save=0.22871091978264957 => cost: 415.7579280346732
Starting path 2/16
exchanging 114-10,93-0 with 114-93,10-0 => save=4.063910634805211 => cost: 494.31011527431946
exchanging 114-105,10-82 with 114-10,105-82 => save=2.900319415888454 => cost: 491.409795858431
Starting path 3/16
exchanging 4-13,123-0 with 4-123,13-0 => save=19.13464498164811 => cost: 480.43951154085676
exchanging 65-14,52-33 with 65-52,14-33 => save=1.587339787656024 => cost: 478.8521717532007
Starting path 4/16
exchanging 19-16,55-0 with 19-55,16-0 => save=0.7537655368855951 => cost: 489.3027111852691
...
exchanging 46-130,39-75 with 46-39,130-75 => save=1.7704562419552907 => cost: 455.4046302803684
Starting path 5/16
exchanging 37-112,94-0 with 37-94,112-0 => save=11.94699370814547 => cost: 485.7266708931122
exchanging 58-110,28-107 with 58-28,110-107 => save=9.304516959883209 => cost: 476.422153933229
Starting path 6/16
exchanging 62-142,144-0 with 62-144,142-0 => save=23.25445433373693 => cost: 467.79298671639344
Starting path 7/16
Starting path 8/16
exchanging 44-100,48-0 with 44-48,100-0 => save=1.0746379367560621 => cost: 486.7997677569661
...
exchanging 44-98,8-48 with 44-8,98-48 => save=6.17952602155286 => cost: 476.7280985588525
Starting path 9/16
Starting path 10/16
exchanging 113-5,72-0 with 113-72,5-0 => save=1.4836706701319144 => cost: 484.8140111574118
Starting path 11/16
Starting path 12/16
Starting path 13/16
Starting path 14/16
Starting path 15/16
Starting path 16/16
CPU times: user 2.16 s, sys: 40 ms, total: 2.2 s
Wall time: 2.24 s

Plot improved paths

for path in result_paths:
    coords=get_coords(path)
    plt.plot(coords[0], coords[1], linewidth=2)
plt.scatter(data.x, data.y, c='r', s=30)
plt.scatter(data.iloc[0].x, data.iloc[0].y, marker='*', c='r', s=400)
plt.axis([-100,100,-100,100])
plt.grid(True)

png

Nice! Several clean paths, but some vans had to do only one distant delivery.

As we see, it is better to increase the max cost again.

In a real system, there should be a way to estimate it based on a full day of work (generally 8 hours). Let's try again.

%time result_paths = sequential_nn(800)
van 1: 792.9220639985251
van 2: 793.9102149907774
van 3: 749.3577273914822
van 4: 769.1224381882283
CPU times: user 1.03 s, sys: 18.5 ms, total: 1.05 s
Wall time: 1.05 s

Plot result paths

for path in result_paths:
    coords=get_coords(path)
    plt.plot(coords[0], coords[1], linewidth=2)
plt.scatter(data.x, data.y, c='r', s=30)
plt.scatter(data.iloc[0].x, data.iloc[0].y, marker='*', c='r', s=400)
plt.axis([-100,100,-100,100])
plt.grid(True)

png

Let's improve them with a 2-opt heuristic

%time improve_result_paths()
Starting path 1/4
exchanging 84-51,77-0 with 84-77,51-0 => save=11.952005586800027 => cost: 780.9700584117251
...
exchanging 66-51,147-126 with 66-147,51-126 => save=6.004072981449653 => cost: 732.2204189744828
Starting path 2/4
exchanging 35-69,29-0 with 35-29,69-0 => save=15.964056951390774 => cost: 777.9461580393865
...
exchanging 35-129,90-42 with 35-90,129-42 => save=14.532045586175727 => cost: 750.7675349695343
Starting path 3/4
exchanging 4-124,123-0 with 4-123,124-0 => save=19.23021437016152 => cost: 730.1275130213206
...
exchanging 65-14,52-33 with 65-52,14-33 => save=1.587339787656024 => cost: 701.2274950765787
Starting path 4/4
exchanging 19-21,54-0 with 19-54,21-0 => save=12.646642051225456 => cost: 756.4757961370028
CPU times: user 3.71 s, sys: 44.8 ms, total: 3.75 s
Wall time: 3.81 s

Plot improved paths

for path in result_paths:
    coords=get_coords(path)
    plt.plot(coords[0], coords[1], linewidth=2)
plt.scatter(data.x, data.y, c='r', s=30)
plt.scatter(data.iloc[0].x, data.iloc[0].y, marker='*', c='r', s=400)
plt.axis([-100,100,-100,100])
plt.grid(True)

png

Nice, clean paths. But with several overlaps.

In a real system, it should be analysed not only the cost (distance), but also the number of points in the route. Each one introduces a delay, as the driver has to park, walk, wait the customer, etc.

Scenario: farthest depot, several vans, KMeans clustering

Compute delivery clusters

from sklearn.cluster import KMeans

work_per_van=20 #how many deliveries each van will start, ie granularity; a better approach would be capacity.
model = KMeans(n_clusters=1+size//work_per_van, init='k-means++', random_state=0)
%time model.fit(data[['x', 'y']])
CPU times: user 91.4 ms, sys: 10.6 ms, total: 102 ms
Wall time: 111 ms





KMeans(algorithm='auto', copy_x=True, init='k-means++', max_iter=300,
    n_clusters=8, n_init=10, n_jobs=1, precompute_distances='auto',
    random_state=0, tol=0.0001, verbose=0)

Plot clusters

plt.scatter(data.x, data.y, marker='o', c=model.labels_, s=200)
plt.scatter(model.cluster_centers_[:,0], model.cluster_centers_[:,1], marker='+', c='r', s=500)
plt.scatter(data.iloc[0].x, data.iloc[0].y, marker='*', c='r', s=400)
plt.axis([-100,100,-100,100])
plt.grid(True)

png

Let's apply a greedy NN algorithm sequentially, on each of the clusters

%time result_paths = greedy_nn_clusters()    
van 1: 390.25298877225174
van 2: 687.7516428319581
van 3: 382.7248611037869
van 4: 505.82568809746317
van 5: 478.6115152097322
van 6: 644.9250908928291
van 7: 595.3986361541317
van 8: 665.6387979350595
CPU times: user 154 ms, sys: 16.6 ms, total: 170 ms
Wall time: 165 ms

Plot result paths

plt.scatter(data.x, data.y, marker='o', c=model.labels_, s=200)
plt.scatter(model.cluster_centers_[:,0], model.cluster_centers_[:,1], marker='+', c='r', s=500)
for path in result_paths:
    coords=get_coords(path)
    plt.plot(coords[0], coords[1], 'k-', linewidth=2)
plt.scatter(data.iloc[0].x, data.iloc[0].y, marker='*', c='r', s=400)
plt.axis([-100,100,-100,100])
plt.grid(True)

png

Let's improve them with a 2-opt heuristic

%time improve_result_paths()
Starting path 1/8
exchanging 77-4,83-29 with 77-83,4-29 => save=0.8194748732687884 => cost: 389.43351389898294
...
exchanging 6-143,128-89 with 6-128,143-89 => save=5.407506824441722 => cost: 324.93008877322006
Starting path 2/8
exchanging 30-5,34-0 with 30-34,5-0 => save=4.481243727960788 => cost: 683.2703991039973
...
exchanging 115-95,121-18 with 115-121,95-18 => save=8.322195150021315 => cost: 594.5702251203929
Starting path 3/8
exchanging 32-59,99-41 with 32-99,59-41 => save=4.114432829335271 => cost: 378.61042827445164
exchanging 17-78,26-87 with 17-26,78-87 => save=0.17155006280330554 => cost: 378.43887821164833
Starting path 4/8
exchanging 42-19,129-106 with 42-129,19-106 => save=3.8728268587745447 => cost: 501.9528612386886
...
exchanging 37-94,54-0 with 37-54,94-0 => save=1.3747236340181104 => cost: 495.2855372216575
Starting path 5/8
exchanging 0-147,123-65 with 0-123,147-65 => save=11.990854640529989 => cost: 466.6206605692022
...
exchanging 135-65,123-0 with 135-123,65-0 => save=3.919229108305899 => cost: 435.93197839715947
Starting path 6/8
exchanging 56-21,15-0 with 56-15,21-0 => save=6.923848236857282 => cost: 638.0012426559717
...
exchanging 102-43,118-40 with 102-118,43-40 => save=15.652843812142969 => cost: 602.6373464143627
Starting path 7/8
exchanging 63-24,107-110 with 63-107,24-110 => save=11.657922849361384 => cost: 583.7407133047703
...
exchanging 112-36,91-125 with 112-91,36-125 => save=4.722248082275083 => cost: 559.3163570654888
Starting path 8/8
exchanging 48-111,98-137 with 48-98,111-137 => save=11.5162692633929 => cost: 654.1225286716666
...
exchanging 8-132,137-98 with 8-137,132-98 => save=7.784370993699362 => cost: 615.4951078634247
CPU times: user 2.17 s, sys: 49.8 ms, total: 2.22 s
Wall time: 2.39 s

Plot improved paths

plt.scatter(data.x, data.y, marker='o', c=model.labels_, s=200)
plt.scatter(model.cluster_centers_[:,0], model.cluster_centers_[:,1], marker='+', c='r', s=500)
for path in result_paths:
    coords=get_coords(path)
    plt.plot(coords[0], coords[1], 'k-', linewidth=2)
plt.scatter(data.iloc[0].x, data.iloc[0].y, marker='*', c='r', s=400)
plt.axis([-100,100,-100,100])
plt.grid(True)

png

Very cool subsections! Aproximately the same number of deliveries in each route!

But some routes are way longer than others. Some vans maybe will have to do an extra hour or two.


That's it!

Thank you for getting this far, hope you liked! :)