26K meals per day delivered?
The delivery logistics for this volume are tough. We are assuming that our volunteer drivers can deal with 15 rations, i.e. 30 meals per delivery trip, and we are giving them each an optimized driving route. It still takes them about 1.5 to 2 hours to complete their run, a duration that we feel is sustainable 2-3 days per week for our volunteers.
For us, 26K meals would translate into 13K rations. We would expect that this would mean about 7K stops (about 2 rations per stop) for us. Assuming volunteer drivers and regular cars for delivery, that would mean, for us, 700 drivers driving every day, so, for us, in reality about 2,000 drivers (because ours won’t volunteer to drive every day).
If you have control over the source of the meals (we don’t make the food so it is much harder for us), then you just need to partition the address list between drivers, then optimize each route. Our volume is a lot lower than yours (we are thinking 2-3K meals per day, 1/10 of yours), so we don’t auto-partition the address list. Each delivery address is assigned to a neighborhood, and our dispatchers hand partition the delivery list by neighborhood (it is a simple spreadsheet sort). Then we optimize each driver route through a web server running on AWS, and give each driver an optimized driving route (simple traveling salesman algo).
We have considered auto-partitioning the full address list. But we dont need it yet, and we don’t have much money so we want to keep our AWS and Google Maps API tabs low
For the generalized multiple vehicle routing problem, there are simple algorithmic solutions that we could use, for instance here:
However, with that many deliveries, I imagine you must cover a very large geographic area, so possibly you also have to look at your drivers’ home addresses, which takes you out of the regular VRP. Possibly simple heuristics can partition the drivers’ groups and the delivery addresses into subproblems where both the deliveries and the drivers are in the same geo area, in which case you can just use a canned VRP solution again.
Btw we use the GMap travel duration as the point to point distance.