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 :)
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)
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
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
.dataframe tbody tr th {
vertical-align: top;
}
.dataframe thead th {
text-align: right;
}
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
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)
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
.dataframe tbody tr th {
vertical-align: top;
}
.dataframe thead th {
text-align: right;
}
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
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]))
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]
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)
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
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)
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]
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)
%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
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)
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
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)
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
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)
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)
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)
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
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)
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
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)
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)
.dataframe tbody tr th {
vertical-align: top;
}
.dataframe thead th {
text-align: right;
}
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
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)
%time compute_distances()
data
CPU times: user 365 ms, sys: 5.95 ms, total: 371 ms
Wall time: 374 ms
.dataframe tbody tr th {
vertical-align: top;
}
.dataframe thead th {
text-align: right;
}
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
%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]
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)
%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
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)
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]
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)
%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
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)
%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
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)
%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
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)
%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
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)
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
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)
%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
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)
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.
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)
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)
%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
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)
%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
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)
But some routes are way longer than others. Some vans maybe will have to do an extra hour or two.