/Delivery-Route-Planner-TSPSolver

Developing a driving route planner of multiple delivery addresses for a small food business in Toronto by using Python/OR-Tools to find the optimal (or near-optimal) solution and visualize on Google Maps.

Delivery Route Planner (TSP solver)

Given a list of addresses in Toronto, this planner can generate the most efficient (shortest) route with visting the same location twice, outputting as excel file.

What is TSP?

"The travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?" It is an NP-hardproblem in combinatorial optimization." -- by Wikipedia

Input

  • A list is imported by external file sources.
  • A random list of addresses in Toronto with the home address as the starting and ending points:
places = [
    "375 Bamburgh Cir, Scarborough, ON",
    "10231 Yonge St, Richmond Hill, ON",
    "1383 16th Ave, Richmond Hill, ON",
    "11 Disera Dr, Thornhill, ON",
    "280 West Beaver Creek Rd, Richmond Hill, ON",
    "3760 Hwy 7, Unionville, ON",
    "300 John St, Thornhill, ON",
    "5418 Yonge St #12, North York, ON",
    "8 William Kitchen Rd A, Scarborough, ON",
    "7575 Keele St, Concord, ON",
    "5284 Hwy 7, Markham, ON",
    "4205 Keele St, North York, ON",
    "3203 Dufferin St, North York, ON",
    "3400 Yonge St, Toronto, ON",
    "51 Gerry Fitzgerald Dr, Toronto, ON"
]

TSP Solver

  • By using ORtools from Google, the TSP question was solved to get the sub-optimal result by using distance matrix as the input.
Total distance: 98568 meters
Index:
 0 -> 5 -> 10 -> 4 -> 6 -> 2 -> 1 -> 3 -> 14 -> 9 -> 11 -> 12 -> 13 -> 7 -> 8 -> 0

Optimal Route Output

  • A dataframe was generated in the order of delivery spots, including address, lat, lng and maps url which can be clicked on a cellphone to navigate directly:
loc_id address latitude longitude maps_url
0 0 375 Bamburgh Cir, Scarborough, ON 43.815527 -79.322101 https://www.google.com/maps/dir/?api=1
1 5 3760 Hwy 7, Unionville, ON 43.856633 -79.332561 https://www.google.com/maps/dir/?api=1&destination=3760+Hwy+7,+Unionville,+ON&travelmode=driving
2 10 5284 Hwy 7, Markham, ON 43.868385 -79.283161 https://www.google.com/maps/dir/?api=1&destination=5284+Hwy+7,+Markham,+ON&travelmode=driving
3 4 280 West Beaver Creek Rd, Richmond Hill, ON 43.844163 -79.387734 https://www.google.com/maps/dir/?api=1&destination=280+West+Beaver+Creek+Rd,+Richmond+Hill,+ON&travelmode=driving
4 6 300 John St, Thornhill, ON 43.820492 -79.398466 https://www.google.com/maps/dir/?api=1&destination=300+John+St,+Thornhill,+ON&travelmode=driving
5 2 1383 16th Ave, Richmond Hill, ON 43.861279 -79.389934 https://www.google.com/maps/dir/?api=1&destination=1383+16th+Ave,+Richmond+Hill,+ON&travelmode=driving
6 1 10231 Yonge St, Richmond Hill, ON 43.876931 -79.438363 https://www.google.com/maps/dir/?api=1&destination=10231+Yonge+St,+Richmond+Hill,+ON&travelmode=driving
7 3 11 Disera Dr, Thornhill, ON 43.810779 -79.453600 https://www.google.com/maps/dir/?api=1&destination=11+Disera+Dr,+Thornhill,+ON&travelmode=driving
8 14 51 Gerry Fitzgerald Dr, Toronto, ON 43.784834 -79.471775 https://www.google.com/maps/dir/?api=1&destination=51+Gerry+Fitzgerald+Dr,+Toronto,+ON&travelmode=driving
9 9 7575 Keele St, Concord, ON 43.796424 -79.497674 https://www.google.com/maps/dir/?api=1&destination=7575+Keele+St,+Concord,+ON&travelmode=driving
10 11 4205 Keele St, North York, ON 43.773829 -79.492095 https://www.google.com/maps/dir/?api=1&destination=4205+Keele+St,+North+York,+ON&travelmode=driving
11 12 3203 Dufferin St, North York, ON 43.718606 -79.455361 https://www.google.com/maps/dir/?api=1&destination=3203+Dufferin+St,+North+York,+ON&travelmode=driving
12 13 3400 Yonge St, Toronto, ON 43.732653 -79.404582 https://www.google.com/maps/dir/?api=1&destination=3400+Yonge+St,+Toronto,+ON&travelmode=driving
13 7 5418 Yonge St #12, North York, ON 43.775507 -79.414727 https://www.google.com/maps/dir/?api=1&destination=5418+Yonge+St+#12,+North+York,+ON&travelmode=driving
14 8 8 William Kitchen Rd A, Scarborough, ON 43.771816 -79.280174 https://www.google.com/maps/dir/?api=1&destination=8+William+Kitchen+Rd+A,+Scarborough,+ON&travelmode=driving
15 0 375 Bamburgh Cir, Scarborough, ON 43.815527 -79.322101 https://www.google.com/maps/dir/?api=1

Google Maps API

  • A map of all places are drawn on Google Maps:

  • With Google Directions API, we can plot the actual routes on the map. However, due to a large number of direction requests. The screenshot is not the final result.

Lengend for the map:
1  =  375 Bamburgh Cir, Scarborough, ON
2  =  10231 Yonge St, Richmond Hill, ON
3  =  1383 16th Ave, Richmond Hill, ON
4  =  11 Disera Dr, Thornhill, ON
5  =  280 West Beaver Creek Rd, Richmond Hill, ON
6  =  3760 Hwy 7, Unionville, ON
7  =  300 John St, Thornhill, ON
8  =  5418 Yonge St #12, North York, ON
9  =  8 William Kitchen Rd A, Scarborough, ON
10  =  7575 Keele St, Concord, ON
11  =  5284 Hwy 7, Markham, ON
12  =  4205 Keele St, North York, ON
13  =  3203 Dufferin St, North York, ON
14  =  3400 Yonge St, Toronto, ON
15  =  51 Gerry Fitzgerald Dr, Toronto, ON