Construction
Cheapest insertion builds the first solution. If the tank does not hold enough for the next stop, the solver inserts the cheapest refill station before it.
Open source project
Streamlet
Route planning for vehicles whose tank does not hold enough for the whole tour.
Tank
Streamlet fixes the order of the stops and plans the refills along the way in the same pass. It runs as a standalone service behind an HTTP API.
Streamlet was built for Green Ecolution because none of the solvers we evaluated could express this problem. It now lives in a repository of its own and has no dependency on Green Ecolution. Anyone with the same planning problem can adopt it as it is.
The problem
Stop order and refills depend on each other
As soon as a vehicle has to refill along the way, the best order of the stops depends on when and where it refills. Deciding both at once is the heart of the problem.
Without a solver that takes this as input, there are two options, and both cost solution quality: plan the tour without the refills and end up with an infeasible result, or cut the tour into pieces by hand and give up optimising across the whole of it.
Streamlet plans the refill stations in the same optimisation run instead of fitting them in afterwards. At Green Ecolution route optimisation previously ran on Vroom, which could not express several refill stations in the middle of a tour.
Where it fits
Does Streamlet fit your problem?
Streamlet is not tailored to one industry, what matters is the structure of the tour. The more of these traits your tours have, the better the fit.
- Vehicles with limited tank capacity
- Stops with time windows
- Refilling or reloading in the middle of the tour
- Several possible refill stations
- Return to the depot at the end of the shift
Independent of what you carry
Streamlet knows about tank capacity and demand, not about irrigation. What you transport is up to you. Water is the first use case, and nothing in the API assumes it.
Interface
One call, one solution
Streamlet works synchronously. You send the problem, you get the routes back, with no job handling and no polling in between.
- 01
Send the problem
A JSON body sent to POST /v1/solve describes the vehicles with their tank capacity and shift time window, the depots, the stops with their demand and time windows, and the refill stations.
- 02
Fetch costs and solve
Streamlet requests the travel time and distance matrix from the routing engine and solves the problem in the solver.
- 03
Receive the routes
For every route the response holds the order of the stops, distance, driving and waiting time, and the geometry. It also lists the stops that stay unserved.
- POST/v1/solveSolve a problem and return the routes
- GET/healthLiveness check
- GET/api-docs/openapi.jsonOpenAPI schema of the API
Streamlet validates the problem while reading it. An initial load above the tank capacity, a time window that ends before it starts, or a problem without a vehicle is rejected with a 422 instead of failing later in the solver. Error responses give away no internal detail, neither engine URLs nor third-party response bodies.
Solver
Traceable instead of random
The solver works in two phases and without randomness. As long as the time budget does not cut in, the same input yields the same output, which makes results reproducible and regressions testable.
Local search
A VND-style search improves the solution. The cheap moves within a single route run first, the more expensive ones between routes afterwards. Once neither finds anything, it places all refill visits anew and drops the ones that no longer pay off.
Load and duration segments. The solver checks capacity and time windows through load and duration segments following Vidal et al. (2014). They can be merged in constant time, and every move is evaluated on the route it affects.
Measured against the Solomon instances
The regression tests solve well-known VRPTW instances, that is vehicle routing with time windows. They check whether the solution respects capacity and time windows and whether it lands close enough to the optimum. These instances contain no refill stations, so what is measured is the solver's baseline quality.
- c101
- 3.1%
- r101
- 1.9%
- rc101
- 1.5%
Gap to the best known solution, threshold 5%
Map data
Fitting the road network to your fleet
A good route is worth nothing if the road network does not match the fleet. A municipal vehicle may use service and access roads that are closed to general traffic. A standard map does not know that and makes destinations look unreachable when they are not.
The routing engine works on tiles built from an OSM extract. The Streamlet repository ships a CLI that modifies that extract beforehand through OSC changesets, that is change files in the OSM format. This is how you model what your vehicles are actually allowed to drive on.
construction
AvailableMarks roads closed for construction work as access=no. Routes then no longer lead through the closure.
allowed-paths
In developmentOpens paths to motor vehicles when a destination cannot be reached from any drivable road. The patcher is meant to read those destinations from the Green Ecolution API.
The patcher only changes your extract for your routing instance. It affects what the engine considers drivable for your vehicles. It does not grant permission to drive there. Anyone adopting it needs a tile pipeline of their own.
Operations
Deploying and running it
Streamlet is a single service alongside your application. Every state of main is published as a container image, and it is configured through environment variables. Beyond that you need a reachable routing engine.
Stateless
No database, no job queue. On shutdown, open requests are allowed to finish instead of being cut off.
Swappable engine
The routing engine sits behind the Router port trait. Valhalla is the implementation that ships. Another engine can take its place without touching the solver.
Solver as a separate crate
The solver lives in the streamlet-core crate, without tokio, axum or HTTP code. All it adds is serialisation and error types.
AGPL-3.0
The source code is licensed under the GNU Affero General Public License, version 3. Anyone who modifies Streamlet and runs it as a network service has to offer the modified source to its users.
Current state
What works today and what does not
Streamlet is early and runs in operational planning at Green Ecolution. These points are listed here so that nobody discovers them only while integrating.
- Geometry comes back as an encoded polyline. The geojson option currently behaves like polyline.
- The API accepts several depots, but every route returns to the first one.
- There is no GPX endpoint and no embedded routing engine.
Contribute or adopt it yourself
Questions, bug reports and experience from other use cases are welcome in the repository. How Streamlet is wired into Green Ecolution is described in release 0.4.0.