A Smart Solution to Identify an Efficient Delivery Route Involving Several Destinations and Drivers

In delivery services, a handful of drivers deliver items in multiple locations. Currently, in most companies, one employee decides on the delivery assignments, based on intuition. When there are many locations, some drivers will invariably drive much longer than others. If 10 drivers deliver to 50 locations, the total possible assignments/solutions are 10
⁵⁰
. So, all possible exploration is not practical. In this project, the goal is to create a fast, efficient solution to distribute delivery destinations among all the available drivers. To formulate the problem, Google Maps is used to find distances between any two location pairs. In the core algorithm, a distance-based initial seed assignment was used, followed by a proximity-based allocation. Finally, there is a critical-driver optimization phase, to improve the quality of the assignment. After all the computation is completed, the solution visually displays the complete paths for all the drivers. The primary goal is to reduce the time needed to complete the delivery to all the destinations. The solution will try to minimize the time taken by the most-critical driver (the person who is driving for the longest duration). To compute the solution for a large number of drivers and destinations, the software takes a maximum of 2 minutes. For verification, experimentation was performed with various delivery configurations, ranging from 2 to 100 locations, and 2 to 10 drivers. For configurations up to 7 locations and 3 drivers, this proposed solution was compared with the best solution from all possible explorations. On average, this software took only < 10 seconds and produced only a 3 % slower driving solution (driving-time wise) than the best solution produced by the all-possible-exploration. For any larger configuration (location or driver), exploring all possible solutions was not feasible, and this approach produced a good result and consumed only up to 2 minutes of runtime. The solution was verified both visually and analytically by checking the most-critical driver's time.