Route optimization in delivery systems
In delivery systems, aspects like route optimization are very important. It not only ensures a reduction of fuel cost, but also saves time, two aspects that are quite important in business. In this post, a route optimization algorithm is explored to find the optimal route between different stops. This is specifically done for UPS, however, extensions to other business domains can be made as well (e.g., travelling agencies to find the best road trip, flight agencies to optimize airplane flights, etc.).
Route optimization stems back from the travelling salesman problem (TSP), a classic algorithmic problem in the field of computer science, and can be categorized as a mathematical problem. It was first defined in the 1800s by the Irish mathematician W. R. Hamilton and by the British mathematician Thomas Kirkman, and can simple be explained as follows:
The travelling salesman problem is regarded as difficult to solve. If there is a way to break this problem into smaller component problems, the components will be at least as complex as the original one. This is what computer scientists call NP-hard problems.
In this blog post, an algorithm is used that combines advanced machine learning techniques such as K-means clustering and K-Nearest Neighbors algorithm with Google's API usage. It was originally based on Randal Olson's blog, where the optimal route strategy for finding Waldo was explored:
The Process
While classical strategies uses distances "as the crow flies", Google's API was used here to take into account traffic flows, which makes it possible to optimize routes on traffic maps. Particularly, the distance matrix of Google API is used, which outputs the optimal distances and corresponding times between 2 stops in a matrix.
UPS drivers make an average of 120 stops per day (facts 2014). Therefore, a total of 6,689,502,913,449,135 x 10^(183) routes can be made by the driver, which make it unreasonable to compute all routes seperataly (unless you have time enough), even for a computer. To circumvent this issue, the set of stops is split into smaller, more dual sets of stops where less computations are needed and much faster results are obtained. It then combines them according to the K-Nearest Neighbors algorithm. A similar approach was followed by the UPS team, to construct their own optimization algorithm 'ORION':
In order to test the algorithm, the following artificial example was considered: UPS driver John V. needs to delivery 20 packages, spread over 10 locations in Belgium, i.e., Woluwelaan 151, 1831 Machelen (UPS centre); Neerstraat 78-92, 3150 Haacht; Dreefweg 22-28, 1820 Steenokkerzeel; Bocqstraat 15, 1160 Oudergem; Zijpstraat 1-5, 1755 Gooik; Nijverheidslaan 1-17, 1853 Grimbergen (Keyrus BE); Baasbergstraat 2, 1750 Lennik; Lissabonstraat 27, 1060 Sint-Gillis; Directoirelaan 43-45, 1180 Ukkel; Verdunstraat 130-190, 1130 Brussel; Meusegemstraat 64, 1861 Meise.
As result, the following route was conducted by the algorithm, with a total distance of 140.402 km and a time of 3.492 hours:
