I referred to the code from the link and modified it a little bit so as to fit my problem.
Here's the description of my problem:
- There's only one vehicle, and it starts from point 0 (row 0/col 0) and ends at the last point (last row/last col).
- The cost matrix is asymmetric. (Note: The cost matrix is the travel time matrix by calling the OSRM API and then adjusting it by conducting the XGBoost regression)
- Find the shortest path to this known o-d pair.
And here's my code:
def vrpRouting(timeMatx):
data = {}
data['costMatx'] = timeMatx
data["num_vehicles"] = 1
data["starts"] = [0]
data["ends"] = [timeMatx.shape[0]-1]
# Create the routing index manager.
manager = pywrapcp.RoutingIndexManager(
len(data["costMatx"]), data["num_vehicles"], data["starts"], data["ends"]
)
# Create Routing Model.
routing = pywrapcp.RoutingModel(manager)
# Create and register a transit callback.
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["costMatx"][from_node][to_node]
def distance_callback(from_index, to_index):
"""Returns the distance between the two nodes."""
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
return timeMatx[from_node][to_node]
transit_callback_index = routing.RegisterTransitCallback(distance_callback)
# Define cost of each arc.
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
# Add Distance constraint.
dimension_name = "Distance"
routing.AddDimension(
transit_callback_index,
0, # no slack
86400, # vehicle maximum travel distance
True, # start cumul to zero
dimension_name,
)
distance_dimension = routing.GetDimensionOrDie(dimension_name)
distance_dimension.SetGlobalSpanCostCoefficient(100)
# Setting first solution heuristic.
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
)
# Solve the problem.
solution = routing.SolveWithParameters(search_parameters)
index = routing.Start(0)
orderList = [index]
while not routing.IsEnd(index):
index = solution.Value(routing.NextVar(index))
orderList.append(index)
return orderList
Input:
timeMatx = array([[ 0. , 605.24976 , 269.00424 , 606.7239 , 295.72632 ,
701.6189 , 269.7843 , 514.0885 , 507.23184 , 544.19366 ,
226.32301 , 441.45337 , 613.2007 , 606.7652 , 593.4828 ,
414.8909 , 155.63597 , 565.78534 , 298.49384 , 491.65146 ,
52.440372, 484.62408 , 374.28607 , 685.8375 , 2165.6511 ,
825.4935 ],
[ 561.3975 , 0. , 231.96214 , 417.78793 , 256.68472 ,
603.73035 , 235.05937 , 271.1455 , 264.71735 , 195.92427 ,
327.4776 , 281.9526 , 252.85829 , 274.38208 , 506.42474 ,
294.85602 , 501.11224 , 573.43286 , 298.6754 , 287.14642 ,
544.6249 , 290.71954 , 169.4396 , 601.56433 , 1970.7639 ,
715.9111 ],
[ 262.27753 , 323.74512 , 0. , 503.0027 , 48.66478 ,
556.1962 , 49.444817, 292.84494 , 306.4768 , 365.8359 ,
51.76648 , 290.83154 , 485.11664 , 462.46436 , 432.70767 ,
236.12527 , 197.15515 , 540.28687 , 301.12393 , 329.84088 ,
276.75488 , 329.84088 , 215.01988 , 553.1245 , 2215.9258 ,
668.996 ],
[ 676.66907 , 440.7867 , 538.61066 , 0. , 523.7939 ,
328.48447 , 571.5865 , 392.6493 , 390.994 , 324.9568 ,
552.6026 , 417.04404 , 380.0602 , 245.07535 , 259.8233 ,
433.95746 , 585.4867 , 520.9353 , 466.26447 , 339.55667 ,
678.39624 , 341.70975 , 375.12747 , 330.96844 , 2014.8074 ,
307.0386 ],
[ 279.03555 , 312.55005 , 48.66478 , 491.4429 , 0. ,
545.7762 , 49.444817, 267.90707 , 298.87366 , 361.43207 ,
62.489613, 284.3184 , 456.6484 , 462.51218 , 418.38113 ,
224.31155 , 186.10187 , 532.77765 , 280.48578 , 329.84088 ,
286.0367 , 321.64236 , 199.83817 , 546.7755 , 2025.4688 ,
632.142 ],
[ 727.03754 , 595.5355 , 610.61475 , 297.4268 , 605.13983 ,
0. , 615.9515 , 438.4176 , 471.41455 , 483.88916 ,
699.1968 , 489.25296 , 553.45984 , 409.81995 , 314.77545 ,
467.4864 , 659.3457 , 383.023 , 513.4552 , 449.91113 ,
708.2596 , 445.44595 , 547.36676 , 80.06507 , 2080.5547 ,
262.19095 ],
[ 257.08786 , 326.2468 , 51.166454, 488.04865 , 51.166454,
586.5719 , 0. , 291.75586 , 309.40366 , 360.60843 ,
52.762993, 289.2958 , 465.60294 , 463.53494 , 413.9559 ,
241.64075 , 198.96646 , 512.3829 , 291.21436 , 326.0583 ,
270.51175 , 319.29498 , 223.7703 , 566.83795 , 2215.1855 ,
662.5635 ],
[ 459.82492 , 286.65698 , 306.26852 , 388.16956 , 324.50848 ,
472.96484 , 331.41495 , 0. , 105.842026, 179.01134 ,
380.34143 , 152.53131 , 305.39743 , 291.39746 , 317.27963 ,
189.02483 , 332.37558 , 460.87854 , 216.90073 , 73.08488 ,
448.9391 , 69.51257 , 261.15314 , 472.89905 , 2168.003 ,
588.8121 ],
[ 448.00867 , 317.68057 , 249.61453 , 448.0973 , 256.79227 ,
484.4628 , 257.06888 , 150.32164 , 0. , 224.1563 ,
305.67023 , 57.057663, 347.53983 , 321.38745 , 304.5325 ,
93.02085 , 312.1978 , 438.9198 , 191.96974 , 201.89294 ,
426.3994 , 201.87694 , 254.11345 , 483.98294 , 2298.2432 ,
592.0609 ],
[ 555.53796 , 220.56247 , 410.68362 , 430.04636 , 391.3362 ,
581.43414 , 420.44113 , 285.7975 , 285.53186 , 0. ,
483.14706 , 305.77493 , 166.89928 , 265.15802 , 505.59888 ,
327.89725 , 545.64014 , 549.73016 , 365.22986 , 317.2754 ,
541.4608 , 304.20532 , 276.38202 , 576.97864 , 2080.0095 ,
580.7666 ],
[ 226.56038 , 378.07886 , 56.35862 , 519.5915 , 71.37685 ,
632.35425 , 55.63349 , 330.9645 , 327.59625 , 416.49722 ,
0. , 316.1576 , 485.64777 , 526.60693 , 506.71664 ,
280.86526 , 230.70573 , 550.1051 , 331.00058 , 360.97076 ,
237.093 , 354.3738 , 258.68503 , 583.74426 , 1903.4921 ,
751.7908 ],
[ 458.76953 , 301.67664 , 263.1459 , 450.9532 , 250.61711 ,
493.19943 , 261.45465 , 157.58664 , 57.495247, 214.8607 ,
313.91885 , 0. , 346.0988 , 340.1446 , 334.08752 ,
63.607277, 342.14474 , 457.31595 , 231.61456 , 209.15794 ,
462.25943 , 203.73096 , 223.95009 , 506.00223 , 2350.5847 ,
577.3593 ],
[ 642.9194 , 291.66708 , 511.38297 , 355.97083 , 459.01636 ,
561.35596 , 498.29596 , 356.08563 , 353.01437 , 186.48058 ,
519.45703 , 374.19904 , 0. , 152.57288 , 519.08777 ,
371.75195 , 538.47186 , 663.63617 , 445.79474 , 400.12662 ,
632.9558 , 384.0962 , 316.19202 , 563.8031 , 1911.8192 ,
492.3857 ],
[ 623.09015 , 297.91776 , 451.68054 , 281.79025 , 447.24365 ,
444.21805 , 444.50677 , 321.42468 , 320.20535 , 206.25587 ,
527.1237 , 343.518 , 148.0402 , 0. , 363.97754 ,
352.02362 , 537.3169 , 577.52057 , 412.57935 , 299.2037 ,
627.4473 , 277.2091 , 291.3151 , 452.99948 , 2149.2 ,
442.72867 ],
[ 579.5865 , 490.6468 , 520.3644 , 279.6822 , 503.1384 ,
309.12106 , 507.2774 , 303.86588 , 333.23834 , 438.0203 ,
581.85345 , 339.57266 , 457.12305 , 320.24927 , 0. ,
354.19998 , 515.85205 , 421.9343 , 352.8753 , 294.42746 ,
612.50476 , 287.2488 , 514.80835 , 317.7338 , 2197.196 ,
412.9734 ],
[ 456.45532 , 299.7252 , 233.60907 , 534.6004 , 226.06946 ,
545.06934 , 233.96426 , 214.50896 , 94.12929 , 267.78806 ,
281.4427 , 65.66601 , 401.13135 , 413.39264 , 412.9242 ,
0. , 414.6986 , 525.05096 , 288.66278 , 246.21217 ,
453.87292 , 246.21217 , 198.48744 , 577.5303 , 2243.206 ,
640.5496 ],
[ 155.05891 , 568.0132 , 202.34547 , 523.2096 , 209.78374 ,
599.26495 , 198.99548 , 324.08633 , 360.44186 , 440.45587 ,
204.37946 , 347.49423 , 550.2359 , 487.60785 , 499.01086 ,
348.1288 , 0. , 540.9888 , 135.66075 , 382.7744 ,
152.5354 , 388.61807 , 340.47018 , 605.20166 , 2219.416 ,
750.00006 ],
[ 485.56516 , 599.9722 , 555.8168 , 433.31882 , 546.8365 ,
387.8317 , 568.41846 , 355.81543 , 380.595 , 493.46066 ,
546.05084 , 387.7209 , 618.6706 , 558.7649 , 324.0919 ,
458.19125 , 480.57907 , 0. , 357.47806 , 398.37247 ,
483.3039 , 414.2812 , 564.6456 , 396.15234 , 2270.4104 ,
506.2483 ],
[ 258.69937 , 363.43213 , 254.57268 , 486.9452 , 260.889 ,
494.29837 , 253.17126 , 210.97049 , 234.34555 , 292.24005 ,
293.57297 , 252.55754 , 421.17807 , 378.61005 , 303.36768 ,
257.93448 , 122.264015, 454.98428 , 0. , 236.93938 ,
253.4676 , 250.04745 , 319.4175 , 510.46442 , 2382.3901 ,
589.0268 ],
[ 505.6519 , 319.01617 , 369.75504 , 347.82373 , 354.70322 ,
460.26096 , 369.75504 , 69.547066, 127.82035 , 210.15347 ,
426.0753 , 159.16548 , 322.0247 , 289.36023 , 302.46762 ,
212.24222 , 382.88596 , 438.27753 , 247.4827 , 0. ,
485.8731 , 57.478493, 295.67023 , 473.18552 , 2146.8052 ,
597.9801 ],
[ 52.440372, 623.14404 , 302.80176 , 624.6241 , 293.33078 ,
709.0436 , 276.45862 , 508.44223 , 503.47537 , 551.4158 ,
235.32637 , 443.49643 , 625.1005 , 617.32056 , 600.292 ,
424.56824 , 151.66562 , 588.89496 , 282.82944 , 527.02325 ,
0. , 527.02325 , 402.1343 , 694.4563 , 2189.2695 ,
894.13544 ],
[ 505.6519 , 314.47266 , 369.75504 , 347.82556 , 354.70322 ,
455.94913 , 360.55518 , 70.66477 , 133.36484 , 210.88097 ,
421.11978 , 172.64131 , 309.93774 , 274.33762 , 301.96918 ,
211.38991 , 380.6542 , 438.65326 , 247.4827 , 57.478493,
518.7389 , 0. , 298.9216 , 473.18552 , 2146.8052 ,
575.477 ],
[ 414.08194 , 201.07932 , 199.54063 , 494.52237 , 199.88744 ,
575.1419 , 216.00842 , 267.15692 , 267.73367 , 211.15106 ,
246.80675 , 238.4922 , 328.6415 , 317.64835 , 520.3694 ,
200.55713 , 398.5762 , 555.1304 , 321.4037 , 332.76724 ,
418.20874 , 324.56873 , 0. , 612.2203 , 2017.541 ,
717.155 ],
[ 671.4406 , 516.2827 , 539.4914 , 222.72615 , 590.8812 ,
160.31212 , 556.17993 , 382.5772 , 400.06876 , 412.24472 ,
644.9995 , 416.24802 , 467.7319 , 327.4732 , 239.71906 ,
418.28366 , 621.23175 , 450.61893 , 454.04272 , 412.1341 ,
658.5174 , 405.12924 , 459.46152 , 0. , 2095.0942 ,
272.13074 ],
[1573.2515 , 1987.4009 , 1665.257 , 1870.9703 , 1826.2843 ,
1671.1206 , 1665.257 , 1911.0514 , 1910.6981 , 1910.8704 ,
1594.4753 , 1851.5399 , 1861.7765 , 1802.8763 , 1727.6866 ,
1944.2445 , 1632.5803 , 1619.3777 , 1871.582 , 1743.7849 ,
1609.6631 , 1795.7052 , 1948.1182 , 1791.7504 , 0. ,
2547.5269 ],
[ 829.8453 , 676.68646 , 670.7141 , 273.16794 , 708.10034 ,
239.30353 , 655.7406 , 561.3706 , 605.7688 , 578.7432 ,
804.855 , 595.2515 , 508.47095 , 415.9521 , 402.31876 ,
580.0205 , 773.40485 , 571.7874 , 623.5673 , 551.49817 ,
821.65045 , 555.5913 , 675.1111 , 362.9447 , 2355.539 ,
0. ]], dtype=float32)
Then I draw the results on the map, and it looks strange. The pink icon is the start and the green icon is the end.
Did I do something wrong during the process?