This webpage was designed to help aid the efficient planning of a route for deliveries for a business. It’s main objective was to figure out the route with least time to visit all the shops listed. In order to facilitate this, google maps distance matrix Api was used in order to get the distances and travelling times between each of the destinations.
How does it work?
- The webpage can connect directly to a wordpress database, then retrieve a list of customers from which the user can select in each input box. However, it has also been designed so that postcodes can be directly entered into each input box.
- If existing customers in the wordpress database have been selected, then their postcodes are retrieved.
- Once the user presses the ‘Calculate’ button, a distance matrix is formed using a 2D array containing times to travel between each pair of locations. In order to get this information, Google Maps Distance Matrix Api is used.
- As Google charges per each query, to reduce the number of queries, I would just reflect the distance matrix along its diagonal. Eg: time between PA66 6BL and IV32 7DN is the same as the time between IV32 7DN and PA66 6BL.
- After this, the nearest neighbour algorithm is applied to determine the shortest route between each stop. The algorithm is designed to start and stop at the first location.
- Then, a custom google maps link is generated with the order to visit each stop. This link is then opened in a new tab displaying the map.
- The order in which the stops need to be visited is then also displayed on the webpage.
Limitations:
- This problem is similar to the travelling salesman problem to which there is no solution. There are simply best guesses to the most efficient solution to visit all the stops and return back to the starting point. One of these is the nearest neighbour algorithm which is used here. As a result, the route displayed might not always be optimal.