142 — Multi-Objective Vehicle Routing Problem Applied to Large Scale Post Office Deliveries

I’ve discussed multivehicle-routing problems before, #133, #96: This paper specifically addresses the challenegs of routing versus resource allocation. That is, given a finite resource pool of mail carriers in the city of Artur Nogueira, find a series of routes that cover all destinations which are known prior to deployment. This can be done offline, in contrast with resource-sharing applications that must take place in realtime.

This algorithm has several optimization metrics: The authors aim to minimize route length, maximize fairness (all carriers have similarly challenging or long routes), and minimize the number of mail carriers required, without making any individual carrier hold too much weight.

The PostVRP implementation represents each street as a chain of geometries embedded in the 2D coordinate plane. (One could imagine using osmnx to generate these maps!) A probability density $D(St)$ is then assigned to each street, where more central streets have higher densities than distant ones.

Then, a graph is constructed that defines each point weight as a function of its neighboring densities, as well as an additional cost associated with crossing the street. By segmenting this graph into $n$ parts on points of high centrality (high $D$ values) and traversing with $n$ agents, it is possible to come up with local optima for the PostVRP problem.

The authors also open-source the benchmarking library they use to optimize this vehicle-routing problem (VRP) so that others can compare their own implementations against these known benchmarks. The code is available on the project website.