Findings on route optimization in practice

Worked quite a bit in the field of mathematical optimization, more towards the SWE side of implementing and deploying systems for actual usage for the past ~decade rather than the theoretical end / designing new algorithms.

In many cases, it would have been better to think about solutions from solvers as "good first drafts" for actual usage, and instead of investing very significant amounts of time improving on models and algorithms, spend time developing a good UI/UX that would make it easy for human operators to do the necessary rectifications.

In the article's case, it was possible to fix the issue with a relatively simple modification to the model. I have seen, many times, practitioners of math optimization trying to "fix" their model by adding more and more features to it, leading to horribly complex, nonlinear messes that would never be of much use in practice.

The customers' dislike of the lowest-cost routes might have to do with surprises that can occur along the route. For example, if the vehicle breaks down, it's better to have made as many deliveries as possible already so you don't have to offload as much or any of the cargo to another vehicle. A route that greedily visits deliveries and then has a long return leg is better from this perspective. Another thing that might happen is additional stops might be added as new information becomes available. Leaving the return leg less constrained makes the average cost of adding a stop in a new area lower.

Interesting article. I've assumed that route optimization would be a fairly well-developed industry by now without a lot of room for new small entrants, especially with all the well-known companies offering online delivery services. Surely they must have at least the basics of route optimization pretty well worked out.

One thought that occurred to me is that drivers might unconsciously not want to delay deliveries for later in the day if they can be done sooner. Delivery locations further away will always be delivered later, but if I'm in the neighborhood early in the day I should make those deliveries first.

Imagine an optimal route that involves taking an expressway to a remote location and then making deliveries on a local road heading back to the depot and compare that with the reverse trip making deliveries on the local road before returning empty via the expressway. Both trips might seem to be equivalent from an optimization standpoint, but the deliveries would be made sooner on average for the second trip.

Very cool. I just impemented routing optimization software into a customers ERP system and it went live last week. Basically we will ask for route optimization of approx 15-25 destinations and then pick and pack the goods into the truck in that order from the warehouse. Then the driver will follow phone application and start delivering the goods. It took around 100h of development to get this integrated into the ERP but now its work very well.

I will look into this solution as well since I have a feeling that in the future there will be more similar requests.

This makes me think of the (apparently true?) story of the shuffle mode in iTunes being seemingly too random for people to the point that some believed it was broken. I have a feeling the differences between the theoretically optimal path (i.e. the one from the start of the article) and the improved ones they get by including additional heuristics are there mainly because they make the drivers feel like they're working more efficiently. Which is very fair considering that the way the drivers feel about the routing is also a cost.

We're doing a different kind of discrete optimization at $job and see much the same: there are other, often difficult to quantify preferences over and above what we naively thought we were optimizing for.