Vehicle Routing Heuristics

Because vehicles typically come in standard sizes, logistics companies need to assign an equal number of deliveries to each vehicle to maximize utilization.

In this project, we developed heuristic algorithms that enable Redmart to balance delivery load among multiple vehicles while taking into account time windows, vehicle capacities, and pickup and delivery constraints. We do this by first posing the task of assigning multiple vehicles to deliveries as a set partitioning problem (with each set corresponding to feasible route) and then creating an optimal schedule for each vehicle once each route is assigned.

This method creates delivery regions for each driver that are both balanced and compact - thereby minimizing fleet driving time and fuel costs.

Joint work in collaboration with the Redmart engineering and product teams. Special thanks to Jon Sugihara and Roger Egan.

---

A Anwar, R Movassagh: Redmart Automated Routing Service. Unpublished (paper)