Nearest neighbor algorithm solution for package delivery using python
In this project I was asked to assist the Western Governors University Parcel Service (WGUPS) with their need to determine an efficient route and delivery distribution for their Daily Local Deliveries (DLD). The constraints of this project were to deliver 40 packages using efficient mileage throughout the Salt Lake City area in Utah with a total of two drivers and three trucks. Each package has notes, deadlines and an address. Each truck can hold 16 packages at a time. Each delivery needs to be updated in the WGUPS system to ensure that a supervisor can address any problems that may arise, and track data to adjust for future growth and demand.
For this task I chose the “Nearest Neighbor Algorithm” as my initial approach to find the best route, which is heuristic, and is greedy in nature. “A greedy algorithm is an algorithm that, when presented with a list of options, chooses the option that is optimal at that point in time. The choice of option does not consider additional subsequent options and may or may not lead to an optimal solution.” ( Lysecky, R., & Vahid, F.) “A heuristic algorithm is an algorithm that quickly determines a near optimal or approximate solution.” ( Lysecky, R., & Vahid, F.) What makes this solution a Nearest Neighbor algorithm is that it makes the most optimal choice at each stage. At each location, the methods I created will sort through all of the packages on a truck and find the nearest remaining destination location using a lower bound check of the miles for each package on board the truck. With the consistent and reliable number of steps, I found this to be the best method to help with WGUPS’s delivery needs. The greedy nature of this algorithm ensures that each step will be taken, and each package will be delivered. The basic travel decisions of each truck are listed below and can be broken into three steps:
- We sort the packages by mileage to their destination, and return the mileage to the nearest destination.
- We match that mileage to the package inside the truck storage and deliver that package.
- That package location becomes the new current location. Repeat until there are no longer any packages in the truck storage. By definition this is a heuristic greedy algorithm since we are sorting at each location to find the nearest location without any planning or forethought. We are not considering the best route overall, only the best route at each stop.
• Step 1: We sort the packages and find the mileage of the nearest package and return it.
• Step 2 We match that mileage to the package inside the truck storage and deliver that package.
• Step 3 That package’s location becomes the new current location.
For this step we need to refer back to the second half of the “Match the lowest miles to package
method”
Processor: Intel(R) Core(TM) i7-10750H CPU @ 2.60GHz 2.59 GHz Installed RAM: 16.0 GB (15.8 GB usable) System type: 64-bit operating system, x64-based processor Integrated Development Environment (IDE): PyCharm 2021.3 Python Version: 3.9
The hash table class was built using linked lists which grow dynamically. With a list foundation we are allowed access to Python’s built-in methods such as append, which allows an element to be appended to the end of a list, and remove, which will remove any item from the list. List items are changeable, ordered, and allow for duplicate values, making them the perfect flexible structure that can adapt and scale with business demand.
A Nearest Neighbor algorithm ensures that each step will be taken and each package will be delivered with a max time complexity of O(N^2) and O(N) space. With the consistent and reliable number of steps, and no backtracking thanks to using a breadth-first search traversal, I found this to be the best method to help with WGUPS’s delivery needs at this time. This efficient algorithm combined with the self-adjusting chaining hash table built using scalable and adaptable linked lists provides not only a consistent algorithm, but a maintainable one, since the hash table can make adjustments for growth, and the algorithm guarantees delivery. Though the Nearest Neighbor was considered suboptimal in similar situations and can sometimes miss shorter routes when given larger maps to work with, this algorithm is easy and intuitive to implement. It also executes quickly, and our drivers completed their day by 12:53 p.m., with a total mileage of 104.4 miles. As time goes on, this document and code comments will help new hires be able to implement the same software as more hubs are opened throughout the state and even the country.
The hash table class is built with a linked list of lists that adjusts with growth. Since the hash uses a chaining technique, collisions are avoided, and since linked lists are the foundation, adjustable growth is guaranteed. However, as the linked lists grow, the value of N will grow, but this can be worked with by increasing the size of the hash table.
I used a chaining hash table with linear probing as the self-adjusting data structure.
The chaining hash table class was built using linked lists which grow dynamically. With a list foundation we are allowed access to Python’s built-in methods such as append, which allows an element to be appended to the end of a list, and remove, which will remove any item from the list. List items are changeable, ordered, and allow for duplicate values, making them the perfect flexible structure that can adapt and scale.
- Dijkstra Shortest Path
- Christofides Algorithm
Though this algorithm finds the shortest distance, it finds the shortest from the starting point to all other points. It does not find the minimum distance as we go, like Nearest Neighbor does. It will not target each stop, and the truck would have had to keep returning home, wasting time and miles.
Though this algorithm holds the record for the best approximation ratio for metric space, for this algorithm to work, the distances between each location would have to be symmetric. Though the Nearest Neighbor Algorithm is considered more of a naïve approach in comparison, I felt that the Christofides Algorithm would be better served as an assistant to a travel plan and not the main plan.
If I were to do this project again, I would like to try the Farthest Insertion Algorithm. The Nearest Neighbor Algorithm works fine if the trucks have another destination hub by its last package; however, having to circle back to the main hub makes the algorithm less simple and causes an unnecessary circle. With the Farthest Insertion Algorithm we would deliver our farthest package first and move inward. The packages would still have to be sorted, but instead of using a linked list, I would use a stack to push and pop packages on and off of the truck which I believe might be a cleaner approach to delivery. Even though the Nearest Neighbor Algorithm and the Farthest Insertion Algorithm both have a time complexity of O(N^2) and a space complexity of O(N), the Farthest Insertion Algorithm would ensure that the packages that might have been late in a Nearest Neighbor Algorithm are now on time, and would ensure that we end where we started from.
The chaining hash table implementation is very efficient for key-value pair data. It is a dictionary of sorts with a key value lookup. Below is a small demo example of a pet store, showing how easy it makes inventory look up for the store.
I implemented a hash table similarly in the project to access and manipulate the data for the packages:
The implemented hash table uses linear probing for the functions. Each time a package is accessed for usage the worst-case scenario space-time complexity for linear probing is O(N), with N being the number of packages inside the package storage hash table. Each time we increase the number of packages the time needed to perform look-up functions grows linearly with it.
- Stack
- Graph
There are multiple ways a stack could have been implemented in this project, one of which is shown below. The linked lists are great for inserting and removing at random locations; however, since we already had our distances sorted, and are only adding and removing items from the truck, a stack with its push and pop methods is much clearer to implement, and allow us much more control with how memory is allocated and deallocated. Stack Demo:
A graph opens doors to graph traversal, where we visit every vertex in the graph. The vertices in the graph could be the package locations and would be very intuitive to understand since graphs are used in many real world applications to represent networks. A graph with depth-first search would allow us to properly utilize the trucks leaving the hub and coming back to the hub using backtracking instead of just limiting ourselves to traversing linearly. Graph Demo:
