How we quantify traffic in our Routing Platform
by Victor Sprengel, Lucas Brunialti, Tobin Fulton, Daniel Miranda
Cobli (link in Portuguese) is a company dedicated to making fleet management simple. We do this by providing an easy-to-use platform for managers to better control and optimize their vehicle fleets. One of the tools in our platform is multi-vehicle routing (link in Portuguese), which helps our clients get the most out of their available vehicles, such as minimizing gas and maintenance costs as well as maximizing the number of deliveries done per day.
In our system, we let the user input the number of available vehicles, addresses representing deliveries or services as well as other relevant information such as time windows and lunch breaks. We then suggest optimal routes and assign addresses to each vehicle that should be visited in a specific order.
Distance and time are the most important factors in generating these optimal routes. In this post we will take a further look into this service and the search for optimality.
The algorithm used to find the optimal solution needs cost matrices, which represent the relation of distance or time required to travel between each pair of addresses. Initially, we used GoogleMaps’ services and APIs to run these queries. However, we found that our larger clients needed support for more vehicles and addresses per route, and unfortunately, the API costs at this scale are prohibitive.
We thus needed a new source of cost matrices, and we discovered that we could reach enough accuracy for our needs using a different approach: building our own matrices from other datasets we also had access to.
The origin of the new dataset is the API to which we delegate running the algorithm mentioned before. Their service accepts the cost matrices as part of the request, which in our case comes from Google. However, this API has its own data and doesn’t need the matrices from outside. That being said, traffic is not taken into account in this API’s dataset, which reduces the quality of the routes that we generate in our system. Given this reality, we decided to create a solution in-house to quantify traffic into these matrices.
The solution we came up was to multiply the API’s cost matrices by a parameter, named speed-factor ⍺, which exists to simulate the existence of traffic. And so we reduced our initial problem to finding an optimal ⍺.
To find ⍺, we used our dataset of historic routing requests, which is composed of all routes ever generated in our routing system. For each routing request to our system, we acquired both a “raw” cost matrix and an adjusted matrix with traffic taken into account. With all these matrices in hand, we created two large matrices, G and H, following this procedure:
- Determine the maximum dimension of a matrix (all of them are square).
- Fill the cost matrix of each request with zeros in its rows and columns until it has the dimension found at step 1.
- Flatten each of these matrices into vectors.
- The matrices from Google are inserted as rows in G and the ones from the API in H. Of course the indexes must match (i.e., request i must be row i for both matrices).
Then we can find ⍺ by solving the following optimization problem:
The method used to compare the two matrices is the Frobenius norm, which is a natural norm that is also easy to compute. Using derivates we find that the answer is:
Notice how the amount of zeros added during the second step has absolutely no effect on ⍺, since we are only multiplying artificial zeros by other artificial zeros when using trace.
In fact, we are not calculating an optimal ⍺ in the strict sense that it will always be the best solution. But it is indeed the best solution considering all past usages of our routing system. That means it is biased by the locations used for routing in our system.
Importantly, tests using the calculated speed-factor have been successful with little to no practical difference. Hooray!
But that doesn’t mean we are finished. In fact, we will continue to use our clients’ data to improve our routing service such as using a different ⍺ for different times of the day or week.
By the way, if you’re interested in solving these kinds of real-world problems as well as building an awesome end-to-end product that’s helping to make Brazil more efficient, we’re hiring!
Also, follow us on Facebook, LinkedIn, Twitter, and Instagram as well as our Cobli Blog (links in Portuguese)!
