4 ms·

Given the scale of the problems they are tackling, I'm quite surprised how little they are saving. $5m over $120m is only 4%. I would imagine municipalities' ma

by mck- 9y ago

Given the scale of the problems they are tackling, I'm quite surprised how little they are saving. $5m over $120m is only 4%. I would imagine municipalities' manual route planners wouldn't be that great. We have found with many real-world scenarios, that at a much smaller scale we could save easily up to 40% in driving time and fuel costs. When we studied cases of 20+ vehicles and ~1000 stops, sometimes the savings were up to 60%. In one scenario we took 8 cars off the road form a fleet of 30. [1] That's 26% compared to the article's 11.5%. Not to discount its results, dropping 75 bus routes is incredible! Imagine dropping another 75 :) Note that since this is an NP-complete problem, the larger the size of the problem, the more constraints you add, the harder it is for any human route planner to plan routes efficiently -- so the larger the potential efficiency gains for an algorithm. Disclaimer/plug: founder of Routific here. [1] https://routific.com/stories/spring-hope-food-drive/ https://routific.com/stories/spring-hope-food-drive/

com2kid 9y ago
> I would imagine municipalities' manual route planners wouldn't be that great. Depends. If the same routes have been in use for a long time, odds are they are already really optimized. Bus drivers will take the same route year after year, and make suggestions to optimize it (often times by "going off route" now and then, which is very much against the rules, but at times very much needed), and those suggestions will get rolled in next year. 5 or 10 years of incremental improvements add up.
cropsieboss 9y ago
These are all just savings numbers for simplified problems, like vehicle routing problem or simple pickup & delivery problem. Points below properly define problem above: * capacitated pickup and delivery with time windows (NP-hard) * capacity of around 20-60 * every child has to stay maximum T minutes in the bus from the moment it is picked up * each bus can work simultaneously on delivering to multiple schools (covered by standard p&d algorithms) * additional routing/map constraints for roads/vehicle constraints - like minibus drivers being constrained to ares with different housing etc. I'm pretty sure the third point is a tricky one, implementation and speed wise, last one too. I'm skeptical that your API could solve the problem for 600 vehicles off-the-shelf. Not to mention that pickup&delivery slows things down extremely compared to capacitated VRP. Each optimising step is a venture into heavy graph theory. Or one can use easy heuristics and fail miserably by exploring too little of constrained space. I'm skeptical of these large savings. I've personally worked with some top logistics people that did amazing things with pencils and rulers. Trumping these methods gained savings of about 10-15%. Not to mention the optimizing time. It is impossible (if algorithm is not heavily optimized) to search through enough space for these heavily constrained problems in short amount of time (couple of minutes) to get 60% savings. I might be too critical, but I doubt that Common Lisp algorithm can achieve those kinds of speeds. What if a child was forgotten, how much will the replanning time impact the real world workflow. All sorts of invisible issues.

by mck- 9y ago

com2kid 9y ago

> I would imagine municipalities' manual route planners wouldn't be that great. Depends. If the same routes have been in use for a long time, odds are they are already really optimized. Bus drivers will take the same route year after year, and make suggestions to optimize it (often times by "going off route" now and then, which is very much against the rules, but at times very much needed), and those suggestions will get rolled in next year. 5 or 10 years of incremental improvements add up.

cropsieboss 9y ago

These are all just savings numbers for simplified problems, like vehicle routing problem or simple pickup & delivery problem. Points below properly define problem above: * capacitated pickup and delivery with time windows (NP-hard) * capacity of around 20-60 * every child has to stay maximum T minutes in the bus from the moment it is picked up * each bus can work simultaneously on delivering to multiple schools (covered by standard p&d algorithms) * additional routing/map constraints for roads/vehicle constraints - like minibus drivers being constrained to ares with different housing etc. I'm pretty sure the third point is a tricky one, implementation and speed wise, last one too. I'm skeptical that your API could solve the problem for 600 vehicles off-the-shelf. Not to mention that pickup&delivery slows things down extremely compared to capacitated VRP. Each optimising step is a venture into heavy graph theory. Or one can use easy heuristics and fail miserably by exploring too little of constrained space. I'm skeptical of these large savings. I've personally worked with some top logistics people that did amazing things with pencils and rulers. Trumping these methods gained savings of about 10-15%. Not to mention the optimizing time. It is impossible (if algorithm is not heavily optimized) to search through enough space for these heavily constrained problems in short amount of time (couple of minutes) to get 60% savings. I might be too critical, but I doubt that Common Lisp algorithm can achieve those kinds of speeds. What if a child was forgotten, how much will the replanning time impact the real world workflow. All sorts of invisible issues.