ShipPy

Inspiration

Our inspiration is the multiple travelling salesman problem, in which multiple salesmen are required to visit a given number of destinations once and return while minimizing travel cost. This problem occurs in many subjects but is prominent in logistics. It is essential that goods and services are delivered to customers at the the right time, at the right place and at a low cost, with the use of multiple assets. Solving this problem would result in improved quality of service to customers and cost reductions to service providers.

What it does

Our project generates delivery routes for a given number of mail trucks. We receive a list of all recipients along with their physical locations. These recipients are assigned to trucks based on their locations. The sequence of delivery for each truck is then optimized to minimize each of their travel times, factoring in road conditions such as traffic and weather.

How we built it

Our project generates delivery routes by simplifying the multiple travelling salesman problem into multiple instances of the single travelling salesman problem.

1 - Data Preperation. The list of addresses is converted into latitude and longitude GPS coordinates. The travel times between locations is acquired for and to each other location using the google maps API.

2 - Assignment of recipients based on physical location. We use KMeans clustering to group recipients based on their proximity to each other. Each truck has their own set of recipients. This step simplifies the problem from multiple travelling sales to multiple instances of single travelling salesman, for each truck.

3 - Individual route sequencing. We use the metropolis algorithm to optimize the sequence of recipients for each truck. For each truck, an initial random route is generated, followed by subsequent trial routes. The difference in route lengths are computed and the trial route is either accepted or rejected based on optimization parameters.

4 - Visualization. We use folium to visualize the locations of recipients, grouping and assignment of recipients and finally the route calculated for each truck.

Challenges we ran into

Our two main challenges were:

1 - Our algorithm has inherent limitations that can make it unwieldy. It does converge onto optimal routes but it can be time consuming and computationally intensive

2 - Our algorithm relies on the assumption that going from point A to point B has the same travel time as from point B to point A. This is true if the path was a straight line and both ways have the same speed. However, in reality, going from point A to point B may take longer than the other way, such as different roads and speed limits. To overcome this limitation, we used the greater time requirement for our algorithm.

Accomplishments that we're proud of

We put together a working solution for the multiple travelling salesman problem that can be applied on real world logistics problems. This problem is considered NP hard; as it is a generalization of the single travelling salesman which is also NP hard because the number of viable routes grows exponentially as more destinations are added. Overall, implementing a solution for this problem, to the level of a minimum viable product under tight time constraints was a non-trivial task.

What we learned

We improved our knowledge on optimization for complex problems, as well as integrating mathematical solutions with APIs and visualization tools.

What's next for ShipPy

ShipPy may be in a usable state but it can use more work. The individual route sequencing can be computationally intensive so that represents an area of improvement. For real time data, we used google maps API for travel time estimate, but this is all done prior to departure of the mail trucks. It may be possible to implement a solution that can adjust mail trucks' routes in real time should unforeseeable changes in road conditions occur.

Built With

• folium
• google-maps
• numpy
• python