Route optimization app

How does it work? 

  1. Point-to-point routing optimization engine. I set up a Valhalla server on a Google Cloud (GCP) instance that I can make HTTP requests to. You can get the data for the street networks from OpenStreetMaps, and preprocess it into Valhalla map tiles. Right now, my server has the limitation that it only has data for California, but with a little more hard drive space that is a non-issue. By submitting a sequence of latitude/longitude pairs as a JSON payload to this server, Valhalla will return two matrices containing the distance and duration of the journey from any one location to any other.
  2. Routing optimization using constraint satisfaction solver microservice. Google actively maintains a suite of open-source operations research (OR) tools and algorithms called OR-Tools. I used this to create a solver for my own version of the CVRPTW (Capacitated Vehicle Routing Problem with Time Windows). It uses the distance/time matrices from Valhalla to define the edges of the transit graph being optimized over, while keeping track of several cumulative variables (distance, time, vehicle capacity, etc.) in order to enforce the given constraints. I then used FastAPI to turn this solver into a web microservice, wrapped it in a docker container, and deployed it on GCP's Cloud Run service. You can access the raw backend API here. Please don't spam it!
  3. Front-end webserver. The webiste that you are viewing now is was written from scratch using HTML, CSS, and TypeScript (which is transpiled to JavaScript) on the front-end, and utilizes FastAPI on the backend to serve files and make further API calls to the route optimization microservice. The interactive map utilizes an open-source mapping utility called Leaflet, and the tables are represented by JavaScript objects which manage the state of all the stops and vehicles you have added to your optimization problem. When you click the "Optimize routes" button, the state of the stop/vehicle tables is serialized to JSON, then sent to the back-end through a POST request for optimization. The response is parsed and the optimized routes are displayed on the map. All libraries utilize publically-hosted CDN's, to minimize costs due to data ingress from serving large JavaScript files.

To use the application, simply toggle stop placement by clicking the checkbox, then click the map to place stops. The stop table will auto-populate with some sensible default information, but you can edit some details by clicking into the cells of the table. You can zoom the map to a specific stop by clicking on the magnifying glass icon, and you can get more detail on the stops by clicking on the markers. You can also mouse over the column headers for a short description of what they mean. To add vehicles to your fleet, click the "Add vehicle" button above the table. Vehicle details are mostly editable as well. Once you have everything set up as you would like, you can click the "Optimize routes" button, which will make an HTTP call out to the backend to solve your problem. Note that if you choose "Realistic" for the distance calculation, it will typically take a bit longer to solve due to having to make a secondary HTTP request to the Valhalla server (the solver might take a bit longer too due to the non-Euclidean edge weights in the network graph). Happy routing!

Cost per mile Cost per hour Distance calculation





© Eric Cotner, 2021

If you have questions, feedback, or feature requests, email me at `2.71828cotner AT`, and follow my work on GitHub.

Please note that this project is "just for fun" at the moment, but if you are interested in using it for serious business, let me know and we can try and flesh it out a bit more.