The Microsoft Excel workbook “VRP Spreadsheet Solver” is an open source tool for representing, solving, and visualising the results of Vehicle Routing Problems (VRPs). It unifies Excel, public GIS and metaheuristics. It can solve Vehicle Routing Problems with up to 200 customers.
Without a unified platform, every VRP should be tackled on its own, with the results getting lost in the ocean of information that is the Internet.
Why, then, has nobody ever built one?
On one hand, the standard software for small to medium scale quantitative analysis for businesses has been established as, arguably, Microsoft Excel. On the other hand, most academics develop solution algorithms in C++ and the resulting codes are not for the faint of heart. Distance and driving time data have to be retrieved from a Geographical Information Systems (GIS) database, which requires investment. The results of the algorithms are usually represented as a single value, the total cost, and it can only mean so much. It is not straightforward to manually find a solution of a VRP, much less so to compute its cost or to visualize it. Hence, constructing a unified platform for the data sources, solution algorithms, and visual representation of the results is a problem on its own.
The capabilities of public GIS have significantly increased in the past few years. As of the time of this writing, Bing Maps as well as Google Maps have the autocomplete feature, and you can find the address you are looking for within 10-15 keyboard clicks. Although there are many more, we will be using three functions of the public GIS systems. Geocoding is the function that converts and address into the corresponding Latitude / Longitude values. Directions is the function that returns the distance and driving time between two points in addition to the directions. Finally, Static maps is the function that returns image files, which are defined by their centre point, zoom level, and their size. The leading public GIS systems at this point are Bing Maps and Google Maps. Both offer a limited free service, and extended services for subscribers. Within this study, we will be using free services of Bing Maps. Please consult their Terms of Service (http://www.microsoft.com/maps/product/terms.html) before using the VRP Spreadsheet Solver.
What’s new in Version 3.4:
- The solver can handle vehicle-location incompatibility.
What’s new in Version 3.3:
- The solver can handle multi-trip VRP variants, in which the vehicles can visit their depot to deliver their load and leave again for service.
- Driving durations of Bing Maps distances can now be computed using average vehicle speed.
What’s new in Version 3.2:
- There is a “duration multiplier” for each vehicle type, which will allow each different vehicle type to have a different driving duration based on its speed.
What’s new in Version 3.1:
- Populating the coordinates creates a small map in the Locations worksheet. This enables the user to spot coordinate errors before populating the distances.
- If some distances could not be populated due to a connection error, the next attempt only populates the missing distances.
What’s new in Version 3.0:
- Works on both Windows and Mac.
- Changing problem data is reflected on the solution worksheet with a warning.
- Dynamically determined line and marker sizes in the visualization worksheet – smaller markers and thinner lines for larger instances.
- Minor bug fixes.