Findings on route optimization in practice

https://www.graphhopper.com/blog/2022/01/19/findings-on-route-optimization-in-practice-part-1/

by detaro • 5 years ago

50 9 5 years ago

quibono2• 4 years ago

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.

leetrout• 4 years ago

At a previous startup I worked at I suggested letting users paint weights on a map to influence routing and clustering.

Nothing specific, not anchors like additional stops on google maps but like "this is a neighborhood to locals" that would influence clustering and "avoid this area" for routing so the algorithm would use interstates or not based on what appeared more optimal even with just using time or distance as a cost.

quibono2• 4 years ago

I think this is the way to go whenever optimization software meets real humans. I've had some experience with trying to optimize diets based on nutrition, and most of the work goes into making sure the suggested improvements aren't too radical and that the new 'improved' diet feels close to the original. Simply because the most optimal diet is something that no one would actually want to eat, while dramatic changes in suggested foods will simply be ignored by most.

tgflynn• 4 years ago

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.

newrotik• 4 years ago

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.

nocubicles• 4 years ago

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.

salmonellaeater• 4 years ago

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.

andreareina• 4 years ago

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.

baking• 4 years ago

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.

Findings on route optimization in practice

Related Stories