Skip to content

Instantly share code, notes, and snippets.

@Mizux

Mizux/vrp_with_weighted_travel_time.py

Created June 25, 2021 03:30
Show Gist options
  • Save Mizux/5a0f25f832db3b4c49cf3b99183f32aa to your computer and use it in GitHub Desktop.
Save Mizux/5a0f25f832db3b4c49cf3b99183f32aa to your computer and use it in GitHub Desktop.
Download ZIP
VRP with weighted travel time
Raw
vrp_with_weighted_travel_time.py
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
# Create Data Model
def create_data_model():
"""Stores the data for the problem."""
data = {}
data['time_matrix'] = [
[0,77,157,140,258,233,289,175,202,479,209,275,641,299,108,83,151,198,246,0,125,319,321,607,408,336,274,502,268,227,461,393,505,445,373,835,725,325,82,27,180,186,388,193,29,29,29,575,23,163,117,672,79],
[77,0,234,217,221,189,272,144,280,556,286,248,718,376,175,53,154,265,209,77,203,283,277,684,485,413,351,579,345,304,538,376,582,522,440,912,802,402,159,104,257,142,465,270,106,106,106,652,100,126,184,749,82],
[157,234,0,140,414,390,446,332,157,480,210,432,663,321,248,222,290,338,402,157,108,476,478,629,429,358,295,503,268,228,462,550,526,467,513,856,747,347,75,132,181,343,388,148,134,134,134,596,134,320,256,694,218],
[140,217,140,0,317,341,327,313,63,339,69,314,711,369,231,205,273,321,310,140,52,377,398,677,478,406,344,362,128,87,321,431,575,515,496,905,795,395,97,115,40,326,248,53,117,117,117,645,117,297,239,742,201],
[258,221,414,315,0,73,123,212,334,608,338,80,899,557,364,246,347,454,35,258,367,62,85,865,665,594,531,631,397,349,420,190,762,703,629,1092,983,583,339,284,309,114,494,324,286,286,286,832,281,104,373,930,274],
[233,189,390,339,73,0,168,199,358,632,362,130,874,532,340,221,322,430,38,233,358,132,108,840,640,569,507,655,421,374,489,259,738,678,605,1068,958,558,315,260,333,47,520,349,262,262,262,808,256,82,348,905,250],
[289,272,446,325,123,168,0,258,344,618,348,91,930,588,397,290,391,487,130,289,377,60,177,896,696,625,563,641,394,340,334,104,794,734,662,1124,1014,614,371,316,319,206,408,334,317,317,317,863,312,169,406,961,319],
[175,144,332,311,212,199,258,0,330,604,334,239,816,474,281,163,264,372,200,175,300,274,276,782,582,511,449,627,392,352,586,362,680,620,547,1010,900,500,257,202,305,189,513,320,203,203,203,749,198,131,290,847,192],
[201,278,157,61,344,368,354,340,0,327,68,340,763,421,292,266,335,382,336,201,91,403,424,729,530,458,396,350,127,86,321,458,627,567,557,957,847,447,158,176,47,360,247,9,178,178,178,697,178,324,300,794,262],
[479,557,480,340,616,641,626,612,327,0,271,613,1051,709,570,545,613,660,609,479,392,676,697,1017,817,746,684,23,279,329,499,729,915,855,835,1245,1135,735,437,455,313,633,426,337,457,457,457,984,456,596,579,1082,541],
[209,286,210,69,346,370,356,342,68,270,0,342,780,438,300,274,343,390,338,209,121,406,426,746,547,475,413,293,64,58,280,460,644,585,565,974,864,464,166,184,42,363,206,77,186,186,186,714,186,326,308,811,270],
[275,248,432,312,80,130,91,239,330,605,335,0,917,574,384,273,374,474,92,275,364,63,149,882,683,611,549,628,381,327,398,168,780,721,649,1110,1001,600,357,302,306,168,472,321,304,304,304,850,298,131,392,948,301],
[641,718,663,711,899,874,930,816,763,1050,780,917,0,374,732,707,775,822,887,641,680,960,962,68,280,353,391,1074,839,798,1033,1034,136,196,997,220,111,398,622,617,752,827,959,754,618,618,618,67,618,804,741,31,703],
[299,376,321,369,557,532,588,474,421,708,438,574,373,0,390,365,433,480,545,299,338,618,620,339,139,37,49,732,497,456,691,692,237,177,655,567,457,41,280,274,409,485,617,412,276,276,276,306,276,462,399,404,360],
[108,175,248,231,364,340,397,281,293,570,300,384,732,390,0,122,173,93,352,108,216,426,428,698,498,427,365,593,358,318,552,501,596,536,281,926,816,416,173,116,271,293,478,284,114,114,114,666,119,270,24,763,118],
[83,53,222,205,246,221,290,163,268,544,274,273,707,365,122,0,101,212,234,83,191,308,309,673,473,402,339,568,333,292,527,395,570,511,387,900,791,391,147,90,246,174,453,259,88,88,88,640,94,151,131,738,28],
[151,154,290,273,347,322,391,264,336,613,343,374,775,433,173,101,0,121,335,151,259,408,410,741,541,470,408,636,401,361,595,495,639,579,290,969,859,459,216,158,314,275,521,327,157,157,157,708,162,252,149,806,72],
[198,265,338,321,454,430,487,372,383,660,390,474,822,480,93,212,121,0,443,198,306,516,518,788,589,517,455,683,449,408,642,591,686,626,226,1016,906,506,263,206,361,383,569,374,204,204,204,756,209,360,82,853,191],
[246,209,402,308,35,38,130,200,326,601,331,92,887,545,352,234,335,443,0,246,360,97,88,853,653,582,520,624,389,342,454,224,751,691,618,1081,971,571,328,272,302,85,488,317,274,274,274,820,269,92,361,918,263],
[0,77,157,140,258,233,289,175,202,479,209,275,641,299,108,83,151,198,246,0,125,319,321,607,407,336,274,502,267,227,461,393,505,445,373,835,725,325,82,27,180,186,387,193,29,29,29,575,23,163,117,672,79],
[125,203,108,52,369,358,379,300,91,391,121,366,680,338,216,191,259,306,362,125,0,429,446,646,446,375,313,414,180,139,373,483,544,484,481,874,764,364,83,101,92,312,300,82,103,103,103,613,102,289,225,711,187],
[319,283,476,375,62,132,60,274,393,668,398,63,960,618,426,308,408,516,97,319,427,0,116,926,727,655,593,691,444,391,358,128,824,764,691,1154,1044,644,401,346,369,175,431,384,348,348,348,894,342,166,434,991,336],
[321,277,478,395,85,108,177,276,414,688,418,149,962,620,428,309,410,518,88,321,446,116,0,928,729,657,595,712,477,430,474,244,826,766,693,1156,1046,646,403,348,390,135,548,405,350,350,350,896,344,168,436,993,338],
[607,684,629,677,865,840,896,782,729,1016,746,882,68,340,698,673,741,788,853,607,646,926,928,0,246,319,357,1040,805,764,999,1000,102,162,963,228,118,364,588,582,717,793,925,720,584,584,584,32,584,770,707,78,668],
[408,485,429,478,665,640,696,582,530,817,547,683,280,140,498,473,541,589,653,407,446,727,729,246,0,119,157,840,605,565,799,800,143,100,763,473,364,164,388,383,518,594,725,520,385,385,385,213,384,571,507,311,469],
[336,413,358,406,594,569,625,511,458,745,475,611,352,37,427,402,470,517,582,336,375,655,657,318,119,0,75,769,534,493,728,729,216,156,692,546,436,47,317,311,446,522,654,449,313,313,313,286,313,499,436,383,397],
[274,351,295,344,531,507,563,449,396,683,413,549,391,49,365,339,408,455,520,274,313,593,595,357,157,75,0,706,472,431,666,667,255,195,630,585,475,54,254,249,384,460,592,387,251,251,251,324,251,437,373,422,335],
[503,580,503,363,640,664,650,635,351,23,294,636,1074,732,593,568,636,684,632,503,415,699,720,1040,840,769,707,0,303,352,523,753,938,878,859,1268,1158,758,460,478,336,656,449,360,480,480,480,1008,480,620,602,1105,564],
[268,345,268,128,403,427,394,400,127,279,64,381,839,497,358,333,401,449,396,267,180,444,484,805,605,534,472,302,0,69,220,450,703,643,623,1033,923,523,225,243,87,420,146,136,245,245,245,772,244,383,367,870,329],
[227,304,228,87,349,374,340,360,86,328,58,327,798,456,318,292,361,408,342,227,139,391,430,764,565,493,431,351,69,0,234,444,662,603,583,992,882,482,184,202,47,366,161,96,204,204,204,732,204,329,326,829,288],
[461,538,462,321,426,496,341,591,321,499,280,404,1033,691,552,527,595,642,460,461,373,364,480,999,799,728,666,522,220,234,0,230,896,837,817,1226,1117,717,419,437,281,539,74,330,438,438,438,966,438,510,561,1064,523],
[399,382,556,436,196,266,111,369,454,729,459,174,1041,698,508,401,502,598,231,399,488,134,250,1006,807,735,673,752,450,451,230,0,904,845,773,1234,1125,724,481,426,430,309,304,445,428,428,428,974,422,280,516,1072,429],
[505,582,526,575,762,738,794,680,627,914,644,780,136,237,596,570,639,686,751,505,544,824,826,102,143,217,255,937,703,662,896,898,0,60,861,330,220,262,485,480,615,691,823,618,482,482,482,70,482,668,604,167,566],
[445,522,467,515,703,678,734,620,567,855,585,721,196,178,536,511,579,626,691,445,484,764,766,162,100,157,195,878,643,603,837,838,60,0,801,390,280,202,426,421,556,631,763,558,422,422,422,129,422,608,545,227,507],
[373,440,513,496,629,605,662,547,558,835,565,649,997,655,281,387,290,226,618,373,481,691,693,963,763,692,630,858,623,583,817,766,861,801,0,1191,1081,681,438,381,536,558,744,549,379,379,379,931,384,535,257,1028,360],
[835,912,856,905,1092,1068,1124,1010,957,1244,974,1110,220,567,926,900,969,1016,1081,835,874,1154,1156,228,473,547,585,1267,1033,992,1226,1228,330,390,1191,0,110,592,815,810,945,1021,1153,948,812,812,812,260,812,998,934,189,896],
[725,802,747,795,983,958,1014,900,847,1134,864,1001,111,458,816,791,859,906,971,725,764,1044,1046,118,364,437,475,1158,923,882,1117,1118,220,280,1081,110,0,482,706,700,836,911,1043,838,702,702,702,151,702,888,825,80,787],
[325,402,347,395,583,558,614,500,447,734,464,600,397,41,416,391,459,506,571,325,364,644,646,363,164,47,54,758,523,482,717,718,261,201,681,591,481,0,306,300,435,511,643,438,302,302,302,331,302,488,425,428,386],
[82,159,75,97,339,315,371,257,160,436,166,357,622,280,173,147,216,263,328,82,83,401,403,588,388,317,254,459,225,184,419,475,485,426,438,815,706,306,0,57,137,268,345,150,59,59,59,555,59,245,181,653,143],
[27,104,132,115,284,260,316,202,178,454,184,302,617,274,116,90,158,206,272,27,101,346,348,582,383,311,249,477,243,202,437,420,480,421,381,810,700,300,57,0,155,213,363,168,2,2,2,550,4,190,124,648,86],
[180,257,181,40,317,341,327,313,47,312,42,314,752,409,271,246,314,361,310,180,92,377,397,717,518,446,384,335,87,47,281,431,615,556,536,945,836,435,137,155,0,334,208,50,157,157,157,685,157,297,279,783,241],
[186,142,343,326,114,47,206,189,350,625,355,168,827,485,293,174,275,383,85,186,312,175,135,793,594,522,460,648,413,366,533,303,691,631,558,1021,911,511,268,213,326,0,512,341,215,215,215,761,209,58,301,858,203],
[388,465,388,248,495,520,414,517,247,425,206,473,959,617,478,453,521,569,488,387,300,438,554,925,725,654,592,448,146,161,74,304,823,763,744,1153,1043,643,345,363,208,512,0,256,365,365,365,893,364,475,487,990,449],
[192,269,148,52,334,359,344,330,9,336,77,331,754,412,282,257,325,373,327,192,82,394,415,720,520,449,387,359,136,96,330,449,618,558,548,948,838,438,149,167,50,351,256,0,169,169,169,688,169,315,291,785,253],
[29,106,134,117,286,262,317,203,180,456,186,304,618,276,114,88,157,204,274,29,103,348,350,584,385,313,251,479,245,204,438,422,482,422,379,812,702,302,59,2,157,215,365,170,0,0,0,552,5,192,122,649,84],
[29,106,134,117,286,262,317,203,180,456,186,304,618,276,114,88,157,204,274,29,103,348,350,584,385,313,251,479,245,204,438,422,482,422,379,812,702,302,59,2,157,215,365,170,0,0,0,552,5,192,122,649,84],
[29,106,134,117,286,262,317,203,180,456,186,304,618,276,114,88,157,204,274,29,103,348,350,584,385,313,251,479,245,204,438,422,482,422,379,812,702,302,59,2,157,215,365,170,0,0,0,552,5,192,122,649,84],
[575,652,596,645,832,808,863,749,697,984,714,850,67,307,666,640,708,756,820,575,613,894,896,32,213,287,324,1007,772,732,966,968,70,129,931,260,151,331,555,550,685,761,893,688,552,552,552,0,552,738,674,98,636],
[23,100,134,117,281,256,312,198,179,456,186,298,618,276,119,94,162,209,269,23,102,342,344,584,384,313,251,479,244,204,438,416,482,422,384,812,702,302,59,4,157,209,364,170,5,5,5,552,0,186,128,649,90],
[163,126,320,295,104,82,169,131,314,588,318,131,804,462,270,151,252,360,92,163,289,166,168,770,571,499,437,611,377,329,503,274,668,608,535,998,888,488,245,190,289,58,475,305,192,192,192,738,186,0,278,835,180],
[117,184,256,239,373,348,406,290,302,578,308,392,741,399,24,131,149,82,361,117,225,434,436,707,507,436,373,602,367,326,561,510,604,545,257,934,825,425,181,124,279,301,487,293,122,122,122,674,128,278,0,772,126],
[672,749,694,742,930,905,961,847,794,1081,811,948,31,405,763,738,806,853,918,672,711,991,993,78,311,384,422,1105,870,829,1064,1065,167,227,1028,189,80,429,653,648,783,858,990,785,649,649,649,98,649,835,772,0,734],
[79,82,218,201,274,250,319,192,264,540,270,301,703,360,118,28,72,191,263,79,187,336,338,668,469,397,335,563,329,288,523,423,566,507,360,896,787,386,143,86,241,203,449,255,84,84,84,636,90,180,126,734,0]
]
data['distance_matrix'] = [
[0, 973,1786,1858, 2762, 2553, 3173, 1924, 2564, 6112, 2776, 3023, 8359, 39, 1221, 888, 1579, 2165, 2643, 1, 1607, 3386, 3446, 8067, 5316, 4275, 3603, 6348, 3234, 2825, 5202, 423, 6708, 5917, 4201, 10794, 9568, 397, 1027, 354, 235, 2078, 4454, 247, 375, 375, 375, 7636, 308, 181, 1328, 8673, 846],
[973, 0, 2759, 2832, 2238, 1913, 2754, 1464, 3538, 7086, 375, 2514, 9332, 4873, 1852, 538, 156, 2796, 212, 975, 2581, 2863, 2805, 9041, 6289, 5248, 4576, 7321, 4208, 3799, 6175, 3811, 7682, 6891, 4832, 11767, 10541, 4943, 2, 1328, 3323, 1437, 5428, 3444, 1348, 1348, 1348, 8609, 1281, 1277, 1958, 9647, 827],
[1786, 2759, 0, 1608, 4548, 4339, 4959, 371, 159, 5862, 2526, 4381, 8173, 3714, 2753, 2419, 311, 3696, 4429, 1785, 11, 5172, 5232, 7881, 513, 4089, 3417, 6097, 2984, 2575, 4951, 6016, 6522, 5731, 5732, 10608, 9382, 3784, 759, 1456, 21, 3864, 4204, 1496, 1476, 1476, 1476, 745, 1478, 3596, 2859, 8487, 2377],
[1858, 2832, 1608, 0, 3902, 4178, 4056, 3938, 706, 4254, 918, 3906, 9015, 4556, 2825, 2491, 3182, 3768, 3829, 1857, 631, 4547, 4681, 8724, 5972, 4931, 4259, 449, 1376, 967, 3343, 5113, 7365, 6573, 5805, 1145, 10224, 4626, 1228, 1528, 492, 3936, 2596, 612, 1548, 1548, 1548, 8292, 155, 373, 2931, 933, 2449],
[2762, 2238, 4548, 3928, 0, 737, 1243, 2151, 4051, 7573, 4237, 806, 1112, 6661, 3798, 2492, 3514, 4742, 354, 2763, 4559, 633, 866, 10829, 8078, 7036, 6364, 7808, 4695, 3318, 4258, 1927, 947, 8679, 6778, 13555, 12329, 6732, 3788, 3116, 3811, 115, 5005, 3957, 3136, 3136, 3136, 10398, 307, 1055, 3904, 11435, 278],
[2553, 1913, 4339, 4204, 737, 0, 1702, 2018, 4326, 7849, 4513, 1316, 10912, 6453, 359, 2283, 3305, 4533, 382, 2555, 4161, 1336, 1091, 10621, 7869, 6828, 6156, 8084, 4971, 3593, 4961, 263, 9262, 847, 657, 13347, 12121, 6523, 358, 2907, 4086, 475, 5074, 4232, 2928, 2928, 2928, 10189, 2861, 832, 3696, 11226, 2572],
[3173, 2754, 4959, 4082, 1243, 1702, 0, 2618, 4205, 7727, 4391, 919, 11532, 7073, 4395, 2944, 3966, 5338, 132, 3175, 4713, 61, 179, 11241, 8489, 7448, 6776, 7963, 3791, 3291, 3388, 1056, 9882, 909, 7375, 13967, 12741, 7143, 42, 3527, 3965, 2089, 4135, 4111, 3548, 3548, 3548, 10809, 3481, 1717, 4501, 11847, 3233],
[1924, 1464, 371, 3964, 2151, 2018, 2618, 0, 4087, 7609, 4273, 2427, 10283, 5824, 2961, 1654, 2676, 3904, 2033, 1926, 3532, 2776, 2798, 9991, 724, 6199, 5527, 7844, 4731, 4322, 6698, 3675, 8633, 7841, 594, 12718, 11492, 5894, 2951, 2278, 3847, 1919, 5951, 3993, 2299, 2299, 2299, 956, 2232, 1329, 3067, 10597, 1943],
[2544, 3518, 159, 686, 4131, 4406, 4285, 4167, 0, 3745, 715, 4135, 9192, 4733, 3511, 3177, 3868, 4455, 4057, 2543, 924, 4775, 491, 8901, 615, 5108, 4436, 398, 1283, 875, 3251, 5341, 7542, 6751, 6491, 11627, 10401, 4804, 1915, 2214, 479, 433, 2504, 94, 2235, 2235, 2235, 847, 2236, 3958, 3617, 9507, 3135],
[6127, 71, 5876, 4269, 7639, 7915, 7793, 7675, 3759, 0, 3351, 7643, 13283, 8825, 7093, 676, 7451, 8037, 7566, 6125, 49, 8284, 8418, 12992, 10241, 9199, 8528, 235, 3326, 396, 5545, 7876, 11633, 10842, 10073, 15718, 14492, 8895, 5497, 5796, 3869, 7839, 4798, 3853, 5817, 5817, 5817, 12561, 5819, 7467, 72, 13598, 6718],
[2776, 375, 2526, 918, 4288, 4564, 4443, 4324, 715, 3336, 0, 4293, 9933, 5474, 3743, 3409, 41, 4686, 4215, 2775, 1549, 4933, 5068, 9642, 689, 5849, 5177, 3572, 713, 61, 2858, 5499, 8283, 7491, 6723, 12368, 11142, 5544, 2146, 2446, 518, 4488, 2111, 809, 2467, 2467, 2467, 921, 2468, 4116, 3849, 10248, 3367],
[3023, 2514, 4381, 3932, 806, 1316, 919, 2427, 4055, 7577, 4241, 0, 11382, 6923, 4245, 2768, 379, 5188, 934, 3025, 4563, 641, 151, 11091, 8339, 7298, 6626, 7813, 3663, 3163, 4034, 1703, 9732, 894, 7224, 13817, 12591, 6993, 3622, 3377, 3815, 1703, 4782, 3961, 3398, 3398, 3398, 10659, 3331, 1331, 4351, 11697, 3057],
[8359, 9332, 8173, 9015, 1112, 10912, 11532, 10283, 9192, 13269, 9933, 11382, 0, 4544, 9325, 8992, 9683, 10269, 11002, 8357, 8347, 11745, 11804, 748, 3264, 4335, 4995, 13504, 10391, 9982, 12358, 12588, 165, 2441, 12305, 2468, 1242, 479, 7756, 8028, 9507, 10436, 11611, 9098, 8049, 8049, 8049, 723, 8051, 10169, 9431, 315, 8949],
[39, 4873, 3714, 4556, 6661, 6453, 7073, 5824, 4733, 881, 5474, 6923, 4562, 0, 4866, 4533, 5224, 581, 6543, 3898, 3888, 7286, 7345, 427, 1519, 375, 536, 9045, 5932, 5523, 7899, 8129, 2911, 212, 7846, 6997, 5771, 411, 3297, 3569, 5048, 5977, 7152, 4639, 359, 359, 359, 3839, 3592, 571, 4972, 4876, 449],
[1221, 1852, 2753, 2825, 3798, 359, 4395, 2961, 3531, 7079, 3743, 4245, 9325, 4866, 0, 1314, 1845, 942, 368, 122, 2574, 4423, 4483, 9034, 6283, 5241, 4569, 7314, 4201, 3792, 6168, 5451, 7675, 6884, 3135, 1176, 10534, 4937, 1993, 1297, 3317, 3115, 5421, 3437, 1276, 1276, 1276, 8603, 1343, 2847, 262, 964, 1272],
[888, 538, 2419, 2491, 2492, 2283, 2944, 1654, 3197, 6746, 3409, 2768, 8992, 4533, 1314, 0, 1022, 2258, 2373, 886, 2241, 3116, 3176, 87, 5949, 4908, 4236, 6981, 3867, 3458, 5835, 4, 7341, 655, 4294, 11427, 10201, 4603, 166, 963, 2983, 1808, 5088, 3104, 943, 943, 943, 8269, 101, 154, 142, 9306, 289],
[1579, 156, 311, 3182, 3514, 3305, 3966, 2676, 3888, 7436, 41, 379, 9683, 5224, 1845, 1022, 0, 1228, 3395, 1577, 2931, 4138, 4198, 9391, 664, 5599, 4927, 7672, 4558, 4149, 6526, 5022, 8032, 7241, 3148, 12118, 10892, 5294, 2351, 1654, 3674, 283, 5778, 3794, 1634, 1634, 1634, 896, 1701, 2563, 1583, 9997, 733],
[2165, 2796, 3696, 3768, 4742, 4533, 5338, 3904, 4475, 8023, 4686, 5188, 10269, 581, 942, 2258, 1228, 0, 4624, 2164, 3518, 5367, 5426, 9978, 7226, 6185, 5513, 8258, 5144, 4736, 7112, 6395, 8619, 7827, 2499, 12704, 11478, 588, 2937, 2241, 426, 4058, 6365, 4381, 222, 222, 222, 9546, 2287, 3791, 838, 10584, 1937],
[2643, 212, 4429, 3855, 354, 382, 132, 2033, 3977, 75, 4164, 934, 11002, 6543, 368, 2373, 3395, 4624, 0, 2645, 4486, 979, 896, 10711, 7959, 6918, 6246, 7735, 4622, 3244, 4604, 2272, 9352, 856, 666, 13437, 12211, 6613, 367, 2997, 3737, 858, 4725, 3883, 3018, 3018, 3018, 10279, 2951, 936, 3786, 11317, 2662],
[1, 975, 1785, 1857, 2763, 2555, 3175, 1926, 2563, 6111, 2775, 3025, 8357, 3898, 122, 886, 1577, 2164, 2645, 0, 1606, 3388, 3447, 8066, 5315, 4273, 3601, 6346, 3233, 2824, 52, 4231, 6707, 5916, 42, 10792, 9566, 3968, 1025, 353, 2349, 2079, 4453, 2469, 373, 373, 373, 7634, 306, 1812, 1326, 8672, 844],
[1607, 2581, 11, 631, 4533, 4161, 4687, 3532, 924, 4885, 1549, 4537, 8347, 3888, 2574, 2241, 2931, 3518, 446, 1606, 0, 5178, 5053, 8056, 5304, 4263, 3591, 5121, 2007, 1598, 3975, 5744, 6697, 5906, 5554, 10782, 9556, 3958, 978, 1277, 1123, 3685, 3227, 83, 1298, 1298, 1298, 7624, 13, 3418, 268, 8662, 2198],
[3386, 2863, 5172, 4573, 633, 1336, 61, 2776, 4695, 8218, 4882, 641, 11745, 7286, 4423, 3116, 4138, 5367, 979, 3388, 5204, 0, 118, 11454, 8702, 7661, 6989, 8453, 4303, 3804, 3625, 1294, 10095, 9303, 7403, 1418, 12954, 7356, 4413, 374, 4455, 1775, 4372, 4601, 3761, 3761, 3761, 11022, 3694, 1679, 4529, 1206, 3405],
[3446, 2805, 5232, 4707, 866, 1091, 179, 2798, 483, 8352, 5016, 151, 11804, 7345, 4483, 3176, 4198, 5426, 896, 3447, 5053, 118, 0, 11513, 8762, 772, 7049, 8588, 5474, 4097, 4805, 2474, 10154, 9363, 7462, 14239, 13013, 7416, 4472, 38, 459, 1368, 5552, 4736, 3821, 3821, 3821, 11082, 3754, 1702, 4589, 12119, 3465],
[8067, 9041, 7881, 8724, 10829, 10621, 11241, 9991, 8901, 12978, 9642, 11091, 748, 4253, 9034, 87, 9391, 9978, 10711, 8066, 8056, 11454, 11513, 0, 2973, 4044, 4704, 13213, 101, 9691, 12067, 12297, 1359, 215, 12014, 2726, 15, 4499, 7465, 7737, 9215, 10145, 1132, 8807, 7758, 7758, 7758, 431, 7759, 9878, 914, 971, 8658],
[5316, 6289, 513, 5972, 8078, 7869, 8489, 724, 615, 10227, 689, 8339, 3264, 1501, 6283, 5949, 664, 7226, 7959, 5315, 5304, 8702, 8762, 2973, 0, 1292, 1953, 10462, 7348, 6939, 9316, 9546, 1614, 104, 9262, 5699, 4473, 1748, 4713, 4986, 6464, 7394, 8569, 6056, 5006, 5006, 5006, 2541, 5008, 7126, 6389, 3579, 5907],
[4275, 5248, 4089, 4931, 7036, 6828, 7448, 6199, 5108, 9185, 5849, 7298, 4353, 375, 5241, 4908, 5599, 6185, 6918, 4273, 4263, 7661, 772, 4061, 131, 0, 763, 942, 6307, 5898, 8274, 8504, 2703, 1911, 8221, 6788, 5562, 472, 3672, 3944, 5423, 6352, 7527, 5014, 3965, 3965, 3965, 363, 3967, 6085, 5347, 4667, 4865],
[3603, 4576, 3417, 4259, 6364, 6156, 6776, 5527, 4436, 8513, 5177, 6626, 4995, 536, 4569, 4236, 4927, 5513, 6246, 3601, 3591, 6989, 7049, 4704, 1953, 763, 0, 8749, 5635, 5226, 7602, 7833, 3345, 2554, 7549, 743, 6204, 55, 3, 3272, 4751, 5681, 6855, 4343, 3293, 3293, 3293, 4273, 3295, 5413, 4676, 531, 4193],
[6362, 7335, 6112, 4504, 7874, 815, 8029, 791, 3995, 235, 3586, 7878, 13519, 906, 7329, 6995, 7686, 8272, 7801, 6361, 5135, 8519, 8654, 13228, 10476, 9435, 8763, 0, 3561, 4196, 578, 8111, 11869, 11077, 10308, 15954, 14728, 913, 5732, 6032, 4104, 8074, 5033, 4089, 6052, 6052, 6052, 12796, 6054, 7702, 7435, 13833, 6953],
[3234, 4208, 2984, 1376, 3817, 4093, 3791, 4782, 1283, 3312, 713, 3663, 10391, 5932, 4201, 3867, 4558, 5144, 3744, 3233, 2007, 4303, 4597, 101, 7348, 6307, 5635, 3547, 0, 649, 2219, 455, 8741, 7949, 7181, 12826, 116, 6002, 2604, 2904, 884, 4017, 1471, 1377, 2924, 2924, 2924, 9668, 2926, 3645, 4307, 10706, 3825],
[2825, 3799, 2575, 967, 3318, 3593, 3291, 4374, 875, 3946, 61, 3163, 9982, 5523, 3792, 3458, 4149, 4736, 3244, 2824, 1598, 3804, 4097, 9691, 6939, 5898, 5226, 4181, 649, 0, 2376, 4347, 8332, 7541, 6772, 12417, 11191, 5593, 2196, 2495, 475, 3518, 1629, 968, 2516, 2516, 2516, 9259, 2517, 3146, 3898, 10297, 3416],
[5202, 6175, 4951, 3343, 4323, 5026, 3452, 5845, 3251, 553, 2858, 4099, 12358, 7899, 6168, 5835, 6526, 7112, 4669, 52, 3975, 369, 487, 12067, 9316, 8274, 7602, 5766, 2219, 2376, 0, 2331, 10708, 9917, 9148, 14793, 13567, 797, 4572, 4871, 2852, 5465, 747, 3345, 4892, 4892, 4892, 11636, 4894, 517, 6274, 12673, 5792],
[4295, 3875, 6081, 5203, 1991, 2695, 1121, 374, 5326, 8849, 5512, 1768, 12653, 8194, 5516, 4065, 5087, 646, 2337, 4296, 5834, 1359, 2539, 12362, 9611, 8569, 7897, 9084, 455, 4412, 2331, 0, 11003, 10212, 8496, 15088, 13862, 8264, 5321, 4649, 5086, 3134, 3078, 5232, 4669, 4669, 4669, 1193, 4603, 2838, 5622, 12968, 4354],
[6708, 7682, 6522, 7365, 947, 9262, 9882, 8633, 7542, 11619, 8283, 9732, 165, 2894, 7675, 7341, 8032, 8619, 9352, 6707, 6697, 10095, 10154, 1359, 1614, 2685, 3345, 11854, 8741, 8332, 10708, 10938, 0, 791, 10655, 4085, 2859, 314, 6106, 6378, 7857, 8786, 9961, 7448, 6399, 6399, 6399, 928, 64, 8519, 7781, 1965, 7299],
[5917, 6891, 5731, 6573, 8679, 847, 909, 7841, 6751, 10828, 7491, 894, 2441, 2102, 6884, 655, 7241, 7827, 856, 5916, 5906, 9303, 9363, 215, 104, 1893, 2554, 11063, 7949, 7541, 9917, 10147, 791, 0, 9863, 4876, 365, 2349, 5315, 5587, 7065, 7995, 917, 6657, 5607, 5607, 5607, 1719, 5609, 7728, 699, 2756, 6508],
[4201, 4832, 5732, 5805, 6778, 657, 7375, 594, 6511, 10059, 6723, 7224, 12305, 7846, 3135, 4294, 3148, 2499, 666, 42, 5554, 7403, 7462, 12014, 9262, 8221, 7549, 10294, 7181, 6772, 9148, 8431, 10655, 9863, 0, 1474, 13514, 7916, 4973, 4277, 6296, 6094, 8401, 6417, 4256, 4256, 4256, 11582, 4323, 5827, 2874, 1262, 3857],
[10794, 11767, 10608, 1145, 13555, 13347, 13967, 12718, 11627, 15704, 12368, 13817, 2468, 6979, 1176, 11427, 12118, 12704, 13437, 10792, 10782, 1418, 14239, 2726, 5699, 677, 743, 15939, 12826, 12417, 14793, 15023, 4085, 4876, 1474, 0, 1226, 7225, 10191, 10463, 11942, 12871, 14046, 11533, 10484, 10484, 10484, 3158, 10486, 12604, 11866, 2154, 11384],
[9568, 10541, 9382, 10224, 12329, 12121, 12741, 11492, 10401, 14478, 11142, 12591, 1242, 5753, 10534, 10201, 10892, 11478, 12211, 9566, 9556, 12954, 13013, 15, 4473, 5544, 6204, 14713, 116, 11191, 13567, 13797, 2859, 365, 13514, 1226, 0, 5999, 8965, 9237, 10716, 11645, 1282, 10307, 9258, 9258, 9258, 1932, 926, 11378, 1064, 928, 10158],
[397, 4943, 3784, 4626, 6732, 6523, 7143, 5894, 4804, 8881, 5544, 6993, 4808, 411, 4937, 4603, 5294, 588, 6613, 3968, 3958, 7356, 7416, 4517, 1765, 472, 55, 9116, 6002, 5593, 797, 82, 3158, 2366, 7916, 7243, 6017, 0, 3367, 364, 5118, 6048, 7222, 471, 366, 366, 366, 4085, 3662, 578, 5043, 5123, 4561],
[1027, 2, 759, 1228, 3788, 358, 42, 2951, 1935, 5483, 2146, 3622, 7756, 3297, 1993, 166, 2351, 2937, 367, 1025, 978, 4413, 4472, 7465, 4713, 3672, 3, 5718, 2604, 2196, 4572, 5256, 6106, 5315, 4973, 10191, 8965, 3367, 0, 696, 172, 3104, 3825, 1841, 717, 717, 717, 7033, 719, 2837, 2099, 8071, 1617],
[354, 1328, 1456, 1528, 3116, 2907, 3527, 2278, 2234, 5782, 2446, 3377, 8028, 3569, 1297, 963, 1654, 2241, 2997, 353, 1277, 374, 38, 7737, 4986, 3944, 3272, 6017, 2904, 2495, 4871, 4584, 6378, 5587, 4277, 10463, 9237, 364, 696, 0, 202, 2432, 4124, 214, 21, 21, 21, 7306, 46, 2165, 1403, 8343, 921],
[235, 3323, 21, 492, 3862, 4138, 4017, 3898, 479, 3855, 518, 3866, 9507, 5048, 3317, 2983, 3674, 426, 3789, 2349, 1123, 4507, 4642, 9215, 6464, 5423, 4751, 409, 884, 475, 2852, 5073, 7857, 7065, 6296, 11942, 10716, 5118, 172, 202, 0, 4062, 2104, 521, 204, 204, 204, 8784, 2042, 369, 3423, 9821, 2941],
[2078, 1437, 3864, 3936, 115, 475, 2089, 1919, 425, 7773, 4437, 1703, 10436, 5977, 3115, 1808, 283, 4058, 858, 2079, 3685, 1775, 1368, 10145, 7394, 6352, 5681, 8008, 4895, 3518, 54, 3069, 8786, 7995, 6094, 12871, 11645, 6048, 3104, 2432, 4011, 0, 4998, 4157, 2453, 2453, 2453, 9714, 2386, 59, 3221, 10751, 2097],
[4454, 5428, 4204, 2596, 4798, 5074, 42, 5098, 2504, 4783, 2111, 4643, 11611, 7152, 5421, 5088, 5778, 6365, 4725, 4453, 3227, 4437, 5617, 1132, 8569, 7527, 6855, 5019, 1471, 1629, 747, 3078, 9961, 917, 8401, 14046, 1282, 7222, 3825, 4124, 2104, 4998, 0, 2598, 4145, 4145, 4145, 10888, 4147, 4626, 5527, 11926, 5045],
[245, 3424, 1496, 592, 4037, 4312, 4191, 4073, 94, 3839, 809, 4041, 9098, 4639, 3417, 3083, 3774, 4361, 3963, 2449, 83, 4681, 4816, 8807, 6056, 5014, 4343, 4074, 1377, 968, 3345, 5247, 7448, 6657, 6397, 11533, 10307, 471, 1821, 212, 521, 4237, 2598, 0, 2141, 2141, 2141, 8376, 2142, 3864, 3523, 9413, 3041],
[375, 1348, 1476, 1548, 3136, 2928, 3548, 2299, 2255, 5803, 2467, 3398, 8049, 359, 1276, 943, 1634, 222, 3018, 373, 1298, 3761, 3821, 7758, 5006, 3965, 3293, 6038, 2924, 2516, 4892, 4605, 6399, 5607, 4256, 10484, 9258, 366, 717, 21, 204, 2453, 4145, 2161, 0, 0, 0, 7326, 67, 2185, 1382, 8364, 9],
[375, 1348, 1476, 1548, 3136, 2928, 3548, 2299, 2255, 5803, 2467, 3398, 8049, 359, 1276, 943, 1634, 222, 3018, 373, 1298, 3761, 3821, 7758, 5006, 3965, 3293, 6038, 2924, 2516, 4892, 4605, 6399, 5607, 4256, 10484, 9258, 366, 717, 21, 204, 2453, 4145, 2161, 0, 0, 0, 7326, 67, 2185, 1382, 8364, 9],
[375, 1348, 1476, 1548, 3136, 2928, 3548, 2299, 2255, 5803, 2467, 3398, 8049, 359, 1276, 943, 1634, 222, 3018, 373, 1298, 3761, 3821, 7758, 5006, 3965, 3293, 6038, 2924, 2516, 4892, 4605, 6399, 5607, 4256, 10484, 9258, 366, 717, 21, 204, 2453, 4145, 2161, 0, 0, 0, 7326, 67, 2185, 1382, 8364, 9],
[7636, 8609, 745, 8292, 10398, 10189, 10809, 956, 847, 12547, 921, 10659, 723, 3821, 8603, 8269, 896, 9546, 10279, 7634, 7624, 11022, 11082, 431, 2541, 3612, 4273, 12782, 9668, 9259, 11636, 11866, 928, 1719, 11582, 3158, 1932, 4067, 7033, 7306, 8784, 9714, 10888, 8376, 7326, 7326, 7326, 0, 7328, 9446, 8709, 1037, 8227],
[308, 1281, 1478, 155, 307, 2861, 3481, 2232, 2256, 5805, 2468, 3331, 8051, 3592, 1343, 101, 1701, 2287, 2951, 306, 13, 3694, 3754, 7759, 5008, 3967, 3295, 604, 2926, 2517, 4894, 4538, 64, 5609, 4323, 10486, 926, 3662, 719, 46, 2042, 2386, 4147, 2163, 67, 67, 67, 7328, 0, 2118, 1449, 8365, 967],
[181, 1277, 3596, 3756, 1055, 832, 1717, 1329, 3878, 7401, 4065, 1331, 10169, 571, 2847, 154, 2563, 3791, 936, 1812, 3418, 1679, 1702, 9878, 7126, 6085, 5413, 7636, 4523, 3146, 5105, 2774, 8519, 7728, 5827, 12604, 11378, 578, 2837, 2165, 3638, 59, 4626, 3785, 2185, 2185, 2185, 9446, 2118, 0, 2953, 10484, 1829],
[1328, 1958, 2859, 2931, 3904, 3696, 4501, 3067, 3637, 7185, 3849, 4351, 9431, 4972, 262, 142, 1583, 838, 3786, 1326, 268, 4529, 4589, 914, 6389, 5347, 4676, 742, 4307, 3898, 6274, 5557, 7781, 699, 2874, 11866, 1064, 5043, 2099, 1403, 3423, 3221, 5527, 3543, 1382, 1382, 1382, 8709, 1449, 2953, 0, 9746, 1378],
[8673, 9647, 8487, 933, 11435, 11226, 11847, 10597, 9507, 13584, 10248, 11697, 315, 4859, 964, 9306, 9997, 10584, 11317, 8672, 8662, 1206, 12119, 971, 3579, 465, 531, 13819, 10706, 10297, 12673, 12903, 1965, 2756, 1262, 2154, 928, 5105, 8071, 8343, 9821, 10751, 11926, 9413, 8364, 8364, 8364, 1037, 8365, 10484, 9746, 0, 9264],
[846, 827, 2377, 2449, 278, 2572, 3233, 1943, 3155, 6703, 3367, 3057, 8949, 449, 1272, 289, 733, 1937, 2662, 844, 2198, 3405, 3465, 8658, 5907, 4865, 4193, 6938, 3825, 3416, 5792, 4289, 7299, 6508, 3857, 11384, 10158, 4561, 1617, 921, 2941, 2097, 5045, 3061, 9, 9, 9, 8227, 967, 1829, 1378, 9264, 0]
]
data['Pickups_Deliveries_Passengers'] = [
[21, 1, 2], # Passengers
[22, 2, 1],
[23, 3, 2],
[24, 4, 1],
[25, 5, 2],
[26, 6, 3],
[27, 7, 4],
[28, 8, 3],
[29, 9, 5],
[30, 10, 2],
[31, 11, 1],
[32, 12, 3],
[33, 13, 4],
[34, 14, 5],
[35, 15, 6],
[36, 16, 7],
[37, 17, 8],
[38, 18, 2],
[39, 19, 3],
[40, 20, 2],
[47, 41, 1], # Goods
[48, 42, 1],
[49, 43, 1],
[50, 44, 1],
[51, 45, 1],
[52, 46, 1],
]
data['vehicle_capacities_Passengers'] = [6, 6, 6, 6, 6]
data['vehicle_capacities_Goods'] = [4, 4, 4, 4, 4]
data['num_vehicles'] = 5
data['depot'] = 0
data['demands_Passengers'] = [
0, # 0 depot
-1, # 1 Delivery Passengers
-1,
-1,
-1,
-1, # 5
-1,
-1,
-1,
-1,
-1, # 10
-1,
-1,
-1,
-1,
-1, # 15
-1,
-1,
-1,
-1,
-1, # 20
1, # 21 Pickup Passengers
1,
1,
1,
1, # 25
1,
1,
1,
1,
1, # 30
1,
1,
1,
1,
1, # 35
1,
1,
1,
1,
1, # 40
0, #41 Delivery Goods
0,
0,
0,
0, # 45
0,
0, # 47 Pickup Goods
0,
0,
0, # 50
0,
0, # 52
]
data['demands_Goods'] = [
0, # 0 depot
0, # 1 Delivery Passengers
0,
0,
0,
0, # 5
0,
0,
0,
0,
0, # 10
0,
0,
0,
0,
0, # 15
0,
0,
0,
0,
0, # 20
0, # 21 Pickup Passengers
0,
0,
0,
0, # 25
0,
0,
0,
0,
0, # 30
0,
0,
0,
0,
0, # 35
0,
0,
0,
0,
0, # 40
-1, # 41 Delivery Goods
-1,
-1,
-1,
-1,
-1,
1, # 47 Pickup Goods
1,
1,
1,
1,
1, # 52
]
data['time_windows'] = [
(0, 3600), # 0 depot
(0, 3600), # 1 Delivery Passengers
(0, 3600),
(0, 3600),
(0, 3600),
(0, 3600), # 5
(0, 3600),
(0, 3600),
(0, 3600),
(0, 3600),
(0, 3600), # 10
(0, 3600),
(0, 3600),
(0, 3600),
(0, 3600),
(0, 3600), # 15
(0, 3600),
(0, 3600),
(0, 3600),
(0, 3600),
(0, 3600), # 20
(0, 3600), # 21 Pickup Passengers
(0, 3600),
(0, 3600),
(0, 3600),
(0, 3600), #25
(0, 3600),
(0, 3600),
(0, 3600),
(0, 3600),
(0, 3600), #30
(0, 3600),
(0, 3600),
(0, 3600),
(0, 3600),
(0, 3600), #35
(0, 3600),
(0, 3600),
(0, 3600),
(0, 3600),
(0, 2000), #40
(0, 3600), # 41 Delivery Goods
(800, 3000),
(0, 3600),
(0, 3600),
(0, 3600), # 45
(0, 3600),
(0, 3600), # 47 Pickup Goods
(0, 3600),
(0, 3600),
(0, 3600), # 50
(0, 3600),
(0, 3600), #52
]
assert len(data['time_matrix']) == len(data['distance_matrix'])
assert len(data['vehicle_capacities_Passengers']) == data['num_vehicles']
assert len(data['vehicle_capacities_Goods']) == data['num_vehicles']
assert len(data['demands_Passengers']) == len(data['demands_Goods'])
assert len(data['demands_Passengers']) == len(data['time_matrix'])
assert len(data['time_windows']) == len(data['time_matrix'])
return data
### Start the printing section
def print_solution(manager, routing, solution):
"""Prints solution on console."""
print(f'Objective: {solution.ObjectiveValue()}')
# Display dropped nodes.
passenger_pickup = range(1, 21)
passenger_delivery = range(21, 41)
good_pickup = range(41, 47)
good_delivery = range(47, 53)
dropped_nodes = 'Dropped nodes:'
for node in range(routing.Size()):
if routing.IsStart(node) or routing.IsEnd(node):
continue
if solution.Value(routing.NextVar(node)) == node:
dropped_nodes += ' {}'.format(manager.IndexToNode(node))
print(dropped_nodes)
# Print routes
time_dimension = routing.GetDimensionOrDie('Time')
distance_dimension = routing.GetDimensionOrDie('Distance')
capacity_dimension_p = routing.GetDimensionOrDie('Capacity_Passengers')
capacity_dimension_g = routing.GetDimensionOrDie('Capacity_Goods')
total_time = 0
total_distance = 0
total_passengers = 0
total_goods = 0
for vehicle_id in range(manager.GetNumberOfVehicles()):
index = routing.Start(vehicle_id)
plan_output = f'Route for vehicle {vehicle_id}:\n'
passengers = 0
goods = 0
while not routing.IsEnd(index):
node_index = manager.IndexToNode(index)
time_var = time_dimension.CumulVar(index)
distance_var = distance_dimension.CumulVar(index)
capacity_var_p = capacity_dimension_p.CumulVar(index)
capacity_var_g = capacity_dimension_g.CumulVar(index)
plan_output += '{0} Time({1},{2}) Distance:{3} Passenger_Load:{4}, Goods_Load:{5} -> '.format(
node_index,
solution.Min(time_var), solution.Max(time_var),
solution.Value(distance_var),
solution.Value(capacity_var_p), solution.Value(capacity_var_g))
if node_index in passenger_pickup:
passengers += 1
if node_index in good_pickup:
goods += 1
index = solution.Value(routing.NextVar(index))
node_index = manager.IndexToNode(index)
time_var = time_dimension.CumulVar(index)
distance_var = distance_dimension.CumulVar(index)
capacity_var_p = capacity_dimension_p.CumulVar(index)
capacity_var_g = capacity_dimension_g.CumulVar(index)
plan_output += '{0} Time({1},{2}) Distance:{3} Passenger_Load:{4}, Goods_Load:{5})\n'.format(
manager.IndexToNode(index),
solution.Min(time_var), solution.Max(time_var),
solution.Value(distance_var),
solution.Value(capacity_var_p), solution.Value(capacity_var_g))
start_var = time_dimension.CumulVar(routing.Start(vehicle_id))
plan_output += f'Time of the route: {solution.Min(time_var) - solution.Min(start_var)}sec\n'
plan_output += f'Distance of the route: {solution.Value(distance_var)}m\n'
plan_output += f'Passengers: {passengers}\n'
plan_output += f'Goods: {goods}\n'
print(plan_output)
total_time += solution.Min(time_var)
total_distance += solution.Value(distance_var)
total_passengers += passengers
total_goods += goods
print(f'Total time of all routes: {total_time}sec')
print(f'Total distance of all routes: {total_distance}m')
print(f'Total number of Passengers: {total_passengers}')
print(f'Total number of Goods: {total_goods}')
def print_cost(data, manager, routing, solution):
"""Prints solution on console."""
print(f'Objective: {solution.ObjectiveValue()}')
total_cost = 0
# compute arc cost
arc_cost = 0
for vehicle_id in range(manager.GetNumberOfVehicles()):
index = routing.Start(vehicle_id)
while not routing.IsEnd(index):
previous_index = index
index = solution.Value(routing.NextVar(index))
arc_cost += routing.GetArcCostForVehicle(previous_index, index, vehicle_id)
print(f'Total arc cost: {arc_cost}')
total_cost += arc_cost
# compute lower/upper cost
travel_time_cost = 0
travel_time_fixed_cost = 0
time_dimension = routing.GetDimensionOrDie('Time')
for pickup, delivery, weight in data['Pickups_Deliveries_Passengers']:
pickup_index = manager.NodeToIndex(pickup)
pickup_var = time_dimension.CumulVar(pickup_index)
#travel_time_cost += (3600 - solution.Value(pickup_var)) * weight
delivery_index = manager.NodeToIndex(delivery)
delivery_var = time_dimension.CumulVar(delivery_index)
#travel_time_cost += (solution.Value(delivery_var) - 0) * weight
# second method of computation
# Fixed added cost
travel_time_fixed_cost += (3600 - 0) * weight
# Travel time weighted cost (the one we care)
cost = (solution.Value(delivery_var) - solution.Value(pickup_var)) * weight
print(f'Passenger/Goods {pickup}->{delivery} weight:{weight} TravelTime:{int(cost/weight)}s cost:{cost}')
travel_time_cost += cost
print(f'Total Travel Time cost: {travel_time_cost}')
print(f'Total Travel Time Fixed cost: {travel_time_fixed_cost}')
total_cost += travel_time_fixed_cost
total_cost += travel_time_cost
print(f'Total cost: {total_cost}')
### Start the main funciton
def main():
"""Solve the CVRP problem."""
# Instantiate the data problem.
data = create_data_model()
# Create the routing index manager.
manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']),
data['num_vehicles'], data['depot'])
# Create Routing Model.
routing = pywrapcp.RoutingModel(manager)
# Create and register a transit callback for distance.
def distance_callback(from_index, to_index):
"""Returns the distance between the two nodes."""
# Convert from routing variable Index to distance matrix NodeIndex.
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
return data['distance_matrix'][from_node][to_node]
transit_callback_index = routing.RegisterTransitCallback(distance_callback)
# Add Distance constraint.
dimension_name = 'Distance'
routing.AddDimension(
transit_callback_index,
0, # no slack
50_000,
True, # start cumul to zero
dimension_name)
distance_dimension = routing.GetDimensionOrDie(dimension_name)
#distance_dimension.SetGlobalSpanCostCoefficient(100)
# Add Passenger Seats Capacity constraint.
def demand_callback_p(from_index):
"""Returns the demand of the node."""
# Convert from routing variable Index to demands NodeIndex.
from_node = manager.IndexToNode(from_index)
return data['demands_Passengers'][from_node]
demand_callback_index_p = routing.RegisterUnaryTransitCallback(demand_callback_p)
routing.AddDimensionWithVehicleCapacity(
demand_callback_index_p,
0, # null capacity slack
data['vehicle_capacities_Passengers'], # vehicle maximum capacities
True, # start cumul to zero
'Capacity_Passengers')
# Add Goods Capacity constraint.
def demand_callback_g(from_index):
"""Returns the demand of the node."""
# Convert from routing variable Index to demands NodeIndex.
from_node = manager.IndexToNode(from_index)
return data['demands_Goods'][from_node]
demand_callback_index_g = routing.RegisterUnaryTransitCallback(demand_callback_g)
routing.AddDimensionWithVehicleCapacity(
demand_callback_index_g,
0, # null capacity slack
data['vehicle_capacities_Goods'], # vehicle maximum capacities
True, # start cumul to zero
'Capacity_Goods')
## Add Time window constraint
# Create and register a transit callback for time.
def transit_time_callback(from_index, to_index):
"""Returns the travel time between the two nodes."""
# Convert from routing variable Index to time matrix NodeIndex.
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
return data['time_matrix'][from_node][to_node]
transit_time_callback_index = routing.RegisterTransitCallback(transit_time_callback)
# Define cost of each arc.
routing.SetArcCostEvaluatorOfAllVehicles(transit_time_callback_index)
# Add Time Windows constraint.
def time_callback(from_index, to_index):
"""Retruns the travel time between the two nodes"""
# convert from routing variable Index to the time matrix NodeIndex
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
return data['time_matrix'][from_node][to_node]
time_callback_index = routing.RegisterTransitCallback(time_callback)
time = 'Time'
routing.AddDimension(
transit_time_callback_index,
0, # allow waiting time
3600, # maximum time per vehicle
False, # Don't force start cumul to zero.
time)
time_dimension = routing.GetDimensionOrDie(time)
# Add time window constraints for each location except depot.
for location_idx, time_window in enumerate(data['time_windows']):
if location_idx == data['depot']:
continue
index = manager.NodeToIndex(location_idx)
time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])
# Add time window constraints for each vehicle start node.
depot_idx = data['depot']
for vehicle_id in range(manager.GetNumberOfVehicles()):
index = routing.Start(vehicle_id)
time_dimension.CumulVar(index).SetRange(
data['time_windows'][depot_idx][0],
data['time_windows'][depot_idx][1])
# Instantiate route start and end times to produce feasible times.
for i in range(manager.GetNumberOfVehicles()):
routing.AddVariableMinimizedByFinalizer(
time_dimension.CumulVar(routing.Start(i)))
routing.AddVariableMinimizedByFinalizer(
time_dimension.CumulVar(routing.End(i)))
#### Weighting part !!!!!
for pickup, delivery, weight in data['Pickups_Deliveries_Passengers']:
pickup_index = manager.NodeToIndex(pickup)
delivery_index = manager.NodeToIndex(delivery)
# these costs will be added to the objective
time_dimension.SetCumulVarSoftLowerBound(pickup_index, 3600 , weight)
time_dimension.SetCumulVarSoftUpperBound(delivery_index, 0, weight)
# Define Transportation Requests for Passengers.
for pickup, delivery, _ in data['Pickups_Deliveries_Passengers']:
passenger_pickup_index = manager.NodeToIndex(pickup)
passenger_delivery_index = manager.NodeToIndex(delivery)
routing.AddPickupAndDelivery(passenger_pickup_index, passenger_delivery_index)
routing.solver().Add(
routing.VehicleVar(passenger_pickup_index) ==
routing.VehicleVar(passenger_delivery_index))
routing.solver().Add(
distance_dimension.CumulVar(passenger_pickup_index) <=
distance_dimension.CumulVar(passenger_delivery_index))
# Setting first solution heuristic.
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.PARALLEL_CHEAPEST_INSERTION)
search_parameters.local_search_metaheuristic = (
routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
search_parameters.log_search = True
search_parameters.time_limit.FromSeconds(10)
# Solve the problem.
solution = routing.SolveWithParameters(search_parameters)
# Print solution on console.
if solution:
print_solution(manager, routing, solution)
print_cost(data, manager, routing, solution)
else:
print('No Solution was found !')
if __name__ == '__main__':
main()
Raw
zz.readme.md

Possible output:

Objective: 304093
Dropped nodes:
Route for vehicle 0:
0 Time(977,977) Distance:0 Passenger_Load:0, Goods_Load:0 -> 26 Time(1251,1251) Distance:3603 Passenger_Load:0, Goods_Load:0 -> 6 Time(1814,1814) Distance:10379 Passenger_Load:1, Goods_Load:0 -> 31 Time(1918,1918) Distance:11435 Passenger_Load:0, Goods_Load:0 -> 11 Time(2092,2092) Distance:13203 Passenger_Load:1, Goods_Load:0 -> 21 Time(2155,2155) Distance:13844 Passenger_Load:0, Goods_Load:0 -> 49 Time(2321,2321) Distance:15523 Passenger_Load:1, Goods_Load:0 -> 1 Time(2447,2447) Distance:16800 Passenger_Load:1, Goods_Load:1 -> 48 Time(2547,2547) Distance:18081 Passenger_Load:0, Goods_Load:1 -> 43 Time(2717,2717) Distance:20244 Passenger_Load:0, Goods_Load:2 -> 42 Time(2973,2973) Distance:22842 Passenger_Load:0, Goods_Load:1 -> 30 Time(3047,3047) Distance:23589 Passenger_Load:0, Goods_Load:0 -> 28 Time(3267,3267) Distance:25808 Passenger_Load:1, Goods_Load:0 -> 10 Time(3331,3331) Distance:26521 Passenger_Load:2, Goods_Load:0 -> 8 Time(3399,3399) Distance:27236 Passenger_Load:1, Goods_Load:0 -> 0 Time(3600,3600) Distance:29780 Passenger_Load:0, Goods_Load:0)
Time of the route: 2623sec
Distance of the route: 29780m
Passengers: 5
Goods: 2

Route for vehicle 1:
0 Time(0,0) Distance:0 Passenger_Load:0, Goods_Load:0 -> 35 Time(835,835) Distance:10794 Passenger_Load:0, Goods_Load:0 -> 36 Time(945,945) Distance:12020 Passenger_Load:1, Goods_Load:0 -> 15 Time(1736,1736) Distance:22221 Passenger_Load:2, Goods_Load:0 -> 16 Time(1837,1837) Distance:23243 Passenger_Load:1, Goods_Load:0 -> 34 Time(2127,2127) Distance:26391 Passenger_Load:0, Goods_Load:0 -> 50 Time(2384,2384) Distance:29265 Passenger_Load:1, Goods_Load:0 -> 14 Time(2408,2408) Distance:29527 Passenger_Load:1, Goods_Load:1 -> 44 Time(2522,2522) Distance:30803 Passenger_Load:0, Goods_Load:1 -> 0 Time(2551,2551) Distance:31178 Passenger_Load:0, Goods_Load:0)
Time of the route: 2551sec
Distance of the route: 31178m
Passengers: 3
Goods: 1

Route for vehicle 2:
0 Time(477,477) Distance:0 Passenger_Load:0, Goods_Load:0 -> 32 Time(982,982) Distance:6708 Passenger_Load:0, Goods_Load:0 -> 12 Time(1118,1118) Distance:6873 Passenger_Load:1, Goods_Load:0 -> 51 Time(1149,1149) Distance:7188 Passenger_Load:0, Goods_Load:0 -> 23 Time(1227,1227) Distance:8159 Passenger_Load:0, Goods_Load:1 -> 33 Time(1389,1389) Distance:8374 Passenger_Load:1, Goods_Load:1 -> 13 Time(1567,1567) Distance:10476 Passenger_Load:2, Goods_Load:1 -> 45 Time(1843,1843) Distance:10835 Passenger_Load:1, Goods_Load:1 -> 3 Time(1960,1960) Distance:12383 Passenger_Load:1, Goods_Load:0 -> 40 Time(2000,2000) Distance:12875 Passenger_Load:0, Goods_Load:0 -> 20 Time(2092,2092) Distance:13998 Passenger_Load:1, Goods_Load:0 -> 29 Time(2231,2231) Distance:15596 Passenger_Load:0, Goods_Load:0 -> 9 Time(2559,2559) Distance:19542 Passenger_Load:1, Goods_Load:0 -> 27 Time(2582,2582) Distance:19777 Passenger_Load:0, Goods_Load:0 -> 7 Time(3217,3217) Distance:20568 Passenger_Load:1, Goods_Load:0 -> 0 Time(3392,3392) Distance:22492 Passenger_Load:0, Goods_Load:0)
Time of the route: 2915sec
Distance of the route: 22492m
Passengers: 6
Goods: 1

Route for vehicle 3:
0 Time(0,0) Distance:0 Passenger_Load:0, Goods_Load:0 -> 47 Time(575,575) Distance:7636 Passenger_Load:0, Goods_Load:0 -> 24 Time(788,788) Distance:10177 Passenger_Load:0, Goods_Load:1 -> 25 Time(907,907) Distance:11469 Passenger_Load:1, Goods_Load:1 -> 38 Time(1224,1224) Distance:15141 Passenger_Load:2, Goods_Load:1 -> 41 Time(1492,1492) Distance:18245 Passenger_Load:3, Goods_Load:1 -> 5 Time(1539,1539) Distance:18720 Passenger_Load:3, Goods_Load:0 -> 18 Time(1577,1577) Distance:19102 Passenger_Load:2, Goods_Load:0 -> 4 Time(1612,1612) Distance:19456 Passenger_Load:1, Goods_Load:0 -> 22 Time(1697,1697) Distance:20322 Passenger_Load:0, Goods_Load:0 -> 2 Time(2175,2175) Distance:25554 Passenger_Load:1, Goods_Load:0 -> 37 Time(2522,2522) Distance:29338 Passenger_Load:0, Goods_Load:0 -> 17 Time(3028,3028) Distance:29926 Passenger_Load:1, Goods_Load:0 -> 52 Time(3219,3219) Distance:31863 Passenger_Load:0, Goods_Load:0 -> 46 Time(3303,3303) Distance:31872 Passenger_Load:0, Goods_Load:1 -> 39 Time(3305,3305) Distance:31893 Passenger_Load:0, Goods_Load:0 -> 19 Time(3332,3332) Distance:32246 Passenger_Load:1, Goods_Load:0 -> 0 Time(3332,3332) Distance:32247 Passenger_Load:0, Goods_Load:0)
Time of the route: 3332sec
Distance of the route: 32247m
Passengers: 6
Goods: 2

Route for vehicle 4:
0 Time(0,0) Distance:0 Passenger_Load:0, Goods_Load:0 -> 0 Time(0,0) Distance:0 Passenger_Load:0, Goods_Load:0)
Time of the route: 0sec
Distance of the route: 0m
Passengers: 0
Goods: 0

Total time of all routes: 12875sec
Total distance of all routes: 115697m
Total number of Passengers: 20
Total number of Goods: 6
Objective: 304093
Total arc cost: 11421
Passenger/Goods 21->1 weight:2 TravelTime:292s cost:584
Passenger/Goods 22->2 weight:1 TravelTime:478s cost:478
Passenger/Goods 23->3 weight:2 TravelTime:733s cost:1466
Passenger/Goods 24->4 weight:1 TravelTime:824s cost:824
Passenger/Goods 25->5 weight:2 TravelTime:632s cost:1264
Passenger/Goods 26->6 weight:3 TravelTime:563s cost:1689
Passenger/Goods 27->7 weight:4 TravelTime:635s cost:2540
Passenger/Goods 28->8 weight:3 TravelTime:132s cost:396
Passenger/Goods 29->9 weight:5 TravelTime:328s cost:1640
Passenger/Goods 30->10 weight:2 TravelTime:284s cost:568
Passenger/Goods 31->11 weight:1 TravelTime:174s cost:174
Passenger/Goods 32->12 weight:3 TravelTime:136s cost:408
Passenger/Goods 33->13 weight:4 TravelTime:178s cost:712
Passenger/Goods 34->14 weight:5 TravelTime:281s cost:1405
Passenger/Goods 35->15 weight:6 TravelTime:901s cost:5406
Passenger/Goods 36->16 weight:7 TravelTime:892s cost:6244
Passenger/Goods 37->17 weight:8 TravelTime:506s cost:4048
Passenger/Goods 38->18 weight:2 TravelTime:353s cost:706
Passenger/Goods 39->19 weight:3 TravelTime:27s cost:81
Passenger/Goods 40->20 weight:2 TravelTime:92s cost:184
Passenger/Goods 47->41 weight:1 TravelTime:917s cost:917
Passenger/Goods 48->42 weight:1 TravelTime:426s cost:426
Passenger/Goods 49->43 weight:1 TravelTime:396s cost:396
Passenger/Goods 50->44 weight:1 TravelTime:138s cost:138
Passenger/Goods 51->45 weight:1 TravelTime:694s cost:694
Passenger/Goods 52->46 weight:1 TravelTime:84s cost:84
Total Travel Time cost: 33472
Total Travel Time Fixed cost: 259200
Total cost: 304093
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment