Web app solving modified vehicle routing problem (or a set of independent traveling salesman problems). This application uses OSRM API to get all the data. Algorithms are implemented with the use of OR-TOOLS.
We have a set of vehicles, a set of products and a set of locations that we want to deliver some goods to. All of these variables are customizable by the user. Difference between this and the original vehicle routing problem is that the vehicles do not need to have the same starting locations.
We can create a package by assigning multiple products with the location they should be delivered to. The user can then select which vehicles should deliver which packages and choose an algorithm to solve the problem.
Command line application can solve traveling salesman problem. It requires an input file with the following content and creates an output file with the results (list of ordered locations to visit) according to the algorithm that was chosen.
Syntax:
python main.py INPUT_FILE [ALGORITHM_ID]
Current supported algorithms:
- ID=0 - OSRM+OR-TOOLS
- ID=1 - MANHATTAN+OR-TOOLS
- ID=2 - Brute force
- OSRM+OR-TOOLS - Suboptimal
Creates a complete graph using OSRM server and then executes OR-TOOLS algorithm.
- MANHATTAN+OR-TOOLS - Suboptimal (quicker than the one above)
Creates a complete graph using manhattan metric and then executes OR-TOOLS algorithm.
- Brute force - O(n!) complexity
Calculates every permutation of points and gets the shortest.
For more information contact kamil.lepek94@gmail.com
- Required python packages: requests, ortools, itertools
- Host your own OSRM server or change webserver in this file to default. The default server handles only 5000 requests overall per minute so it might block your requests.