“What about if we bring you a sandwich?” the dispatcher asked.
“Make it doughnuts and you have a deal.”
Insight delivers to Springfield. Neat.
A wrong way road sign in Boston, Massachusetts What do heuristics, graph theory and doughnuts have in common? Each of them, in its own way, underpins one of the most challenging parts of the logistics process: planning delivery routes. Every day, millions of products find their way from manufacturers to distributors, …
Be glad they arrive at all. I've had to stop using suppliers who ship by UPS, they can never find my house, or don't bother to try. Tracking one recent, correctly-addressed, parcel showed that it left the depot at 7am, and was returned at 8am as undeliverable, despite the fact that it would take at least an hour to get from that depot to chez moi, never mind there and back.
This post has been deleted by its author
Be glad they arrive at all. I've had to stop using suppliers who ship by UPS
UPS is not my preferred. I had a package sent on a Monday, for next-day delivery on Tuesday. After a week's worth of a phone calls and comedy of UPS errors, my package finally arrived at my local dispatch on Friday - yes, Friday afternoon. When I asked if the package would be delivered on Saturday I was told "No sir, you did not pay for Saturday delivery". Nothing I said about the UPS foul-ups would cause them to budge.
Compare that to FedEx. After a missed delivery one day, a FedEx supervisor showed up at my house that evening in his own car to deliver my package.
Oh, and FedEx was also nice enough to throw Tom Hanks that great party after he got off the island...
FedEx gets my vote.
I think it depends on the local area. For example - UPS sending a package by ground from Houston to San Antonio - they deliver in 2 days, but you're only paying standard ground rates. Fedex sending a package by ground from Houston to San Antonio (west 200 miles)- takes 7 days. They don't like delivering "early" if you haven't paid for expedited shipping.
Fedex skillfully delayed a package of mine once for two days that was in transit from Dallas to San Antonio (travelling SSW 275 miles) by sending back 80 miles Northeast to Austin from San Antonio, before sending it back to San Antonio again.
It was about 20 years ago so the details are sketchy but it was related to optimising CNC machine tool paths (the goal being to visit all locations in the shortest time to drill X number of holes etc..).
I ended using a nice little gem I found in 'Numerical Recipes in C', it was an old book but it referred to a technique called simulated annealing. It's quite smart and attempts to mimic what nature does etc.. We ended up going into production with it and I wouldn't be surprised that it's still in use today.
It's probably the kind of problem a Quantum computer would be ideal for solving though these days.
quite! we use simulated annealing in molecular dynamics too. The problem always depends on the number of sub-optimal minima that are near to the true global minimum. In a protein structure (say), 2 energies that are very close may have completely different conformations (shapes).
In delivering parcels, I would imagine a solution might oscillate between a similar set of paths. Then perhaps you could use min-cut/max flow to divide the network up...
Need to get some coffee...
It's probably the kind of problem a Quantum computer would be ideal for solving though these days.
Not as far as I know.
A highly-parallel classical one with a shared memory would be better.
Or you can build an actual physical system modeling your problem, then let it anneal. An "analog computer"...
watch out for simulated annealing though - in economics that's called Marxism and not allowed
I don't get this joke at all. Marxism is related to Simulated Annealing how?
Me too, in the early eighties. I didn't even know then the name of the problem. Ended up optimising 3 variables, 1. The time on the CNC drilling tool used to drill a stack of PCBs, 2. The machine time on the much more expensive mainframe computer, and 3. the number of days programming effort.
I seem to remember I did it by dividing up the rectangular area into a number of smaller squares with suitable start and end nodes within each square to minimise movement of the drill head between squares, optimised the route within each square and moved between adjacent squares.
I remember seeing a nice "physical" demonstration of an answer to the problem. Non optimal, but close. They set up two glass panes parallel, 1 or 2 cm apart with the stops represented by "pins" between the two panes. then pass the whole package through some bubble mixture. The resulting bubble film draws out a spanning tree between the stops even with non node branches in places.
It was really a cute demonstration of solving the problem in a different way.
Yes, Simulated Annealing is widely used for various applications that deal with intractable problems. There's a good DDJ article from a bygone era1:
Includes source code, natcherly.
Girish Keshav Palshikar, the author of that piece, refers specifically to the TSP in the intro.
1Obviously, since this appeared back when DDJ was a print magazine.
A while ago there was a program on TV about a team of researchers being filmed building an ant colony in a lab armed with cameras in order to really observe their behaviour.
One relevant snippet was how ant behaviours have inspired Ant colony optimisation algorithms, which the program mentioned has really helped with routes for shipping. Just thought I'd throw that into the conversation, and the "go" icon for the improved movement inspired by ants :-)
Yes, ant algorithms are another class used to address graph problems. Graph traversal, inspection, etc is one of the most fecund areas of computer science - it's given us Dijkstra's algorithm, A*, graph sparsification, spanning-tree, and all sorts of other things that show up all over the place, mostly because so many problem domains are graph-processing problems (or can be transformed into or approximated by them).
Having a good friend who was until recently a delivery driver doing multi-drop for a couple of years I can confirm that optimisation (including when to have driver breaks) was left to the drivers. The motivation for optimisation was them getting home earlier and as an agency temp a standard day rate meant there was no overtime for going over the normal working hours. Must do some move investigation next time I see him to work out how optimised it all was (I suspect not a lot).
Tesco could have done with 'a little help' last week. They delivered to my neighbour at ten to nine, then drove off. Came back to me at quarter past nine. Apparently it was because my neighbour had booked the eight to nine slot and I'd booked nine to ten.
Then again if my neighbour and I could reliably sync deliveries we could reduce the cost even further :)
That's the next bit of software the supermarkets need. Some will already give you lower delivery costs, if you're willing to take unpopular time slots. I got free delivery from Ocado, for taking 9:30pm.
So they just need to have a system where you get cheaper/free delivery if you're willling to take a slot at the same time as one's already booked for anyone on the same street (or whatever arbitrary range they pick). Extra points if their system can make this distance greater in rural areas.
I'm sure that's already available somewhere. It's a while since I placed an online order, but the last time (Sainsburys, I think) offered me tiered delivery prices based on other deliveries they were already making, if I remember correctly I was offered a £3.50 delivery for one slot as they were already in the area in the same slot, £5 for one where it was "close" to another delivery and £7.50 for the slot where no other deliveries were happening nearby.
That's a typical comment from people who don't fully understand how all this stuff works. Tesco (and others) have multi-dimensional traveling salesman problems. It's not just about distance but also time slots, lateness, overtime, weight and sometimes volume of goods on the vans, length of time perishable goods can remain on a vehicle, chilled goods, frozen goods, drive time limits etc. The Tesco scheduling system is highly configurable. They can get almost any desired behaviour from it.
In order to get your delivery and everyone else's delivery on time, their system is compelled to do exactly what you described. Making a delivery too early is sometimes as bad as making it too late because the customer may not be at home 5 minutes before their stated time slot. Imagine if they had knocked on your door 15 minutes early and you weren't in. Your subsequent complaint would be as valid as if they had knocked on your door 15 minutes late.
Customer satisfaction is extremely important to Tesco hence they are willing to sacrifice a little efficiency so that you get your bread on time otherwise they would have continued to offer AM/PM type slots as they did a few years ago. The reason the vehicle drove off elsewhere after delivering your neighbours goods would have almost certainly have been to ensure that the other deliveries were done on time and that yours was not done too early. Also your house may well have been on the vehicle's route back to depot. i.e they probably had to go past your house anyway so they may not have had such an inefficient route as you seem to think. I've seen the Tesco operation in action and it is extremely impressive what they do and how they do it. (I don't work for Tesco by the way).
Also you are correct. If you could sync your deliveries with your neighbour then you (or perhaps just one of you) may even get cheaper delivery options.
Even that isn't simple. For instance back when I was driving my commute time could vary between 40 minutes and 100 minutes excluding days on which there was an actual collision in my travel path. There was a two month period when I was leaving the house at 4:30 am and had the 40 minute commute. Most of the time I left at 6:00 and it took 60 minutes. For 7:30 it was the 100. If it got past 7:30 I waited until 9:00 before leaving.
Ah yes the famous Murphy Problem - my commute is only 12k by road.
If I leave home at 7:30am I somehow do not end up with the pensioner doing 50 in a 70 zone. There is nobody on the turnoff onto the highway, and the lights are green to do a left hand turn. Again there is no numpety slowing down to 40 through the 70 speed camera. Total trip time @15minutes.
OTOH if I am running late and leave @ 7:50 I seem to encounter all or some of the problems above (+ others - accidents etc) - total trip time has seen me arrive at work dead on the 8:25 bell but normal arrival is 8:15.
It also depends on what the "efficiency" criteria is - time, fuel, or distance
Actually IIRC Mythbusters looked at testing one of the additional criteria UPS uses (only doing right hand turns - or for we more civilised countries left turns) - The myth was setup from the perspective of a delivery truck driver. Several locations within the San Francisco area were setup as delivery points, then two routes were derived. The first route was a more “logical” route trying not to favor right turns. This route had eight left turns, four right turns, and a total distance of 5.2 miles. The second route tried to exclude as many left turns as practical. The “right turn” route was 6.8 miles long, had one left turn and twenty-three right turns. Each route visited each stop in the same order.
The MythBusters concluded that right turns were indeed more efficient in their test. While the route favoring right turns was a longer distance and took a longer amount of time, it used only 4.0 gallons of fuel compared to 6.8 gallons of fuel on the “control” route.
Being a bit odd, having graduated as an engineer i got a job as a truck driver for a couple of years.
I was vaguely aware of NP-C, and wondered what a practical approach to it was.
Turns out it's a shitload of experience and insight on the part of the dispatcher :-)
May not be THE optimum route, but it's bloody close to it. and there are another 20 or so to plot out before everyone sets off, in an hour or so.
Likewise with loading the truck, broadly in reverse order of the drops, but also aware of the type of equipment available at the other end - is a fork truck available, or has the load got to come off the back on the tail lift.
A graphic demonstration of the difference between science and engineering. NP-C? fuck it! just drive where I tell you to, and I scheduled drop 5 & 6 like that so you avoid the roadworks. see you at 5:30.
> experience and insight on the part of the dispatcher
Sadly, such old-fashioned industrial 'craft' often isn't valued.
What never fails to blow my mind are those old-time analog gadgets that solve computationally hard problems. I've used a planimiter to 'automagically' find the area of irregular solids, and there's the classic example of the soap bubble Steiner tree.
That'll be lorry, truck, or if you really insist, "wagon".
And yes, it can make for an interesting night when the algorithms (and some humans in the loop) bugger things up a bit and the sorting warehouse ends up packed to the rafters with crap that's only going out via local deliveries in 6 hours, crap that should have gone out on a trunk 2 hours ago, all mixed in with crap that's supposed to be getting sorted and loaded right now.
Almost as much fun as being in the back of the wagon when the wrong driver is told to pull away and start with the deliveries, but I guess that's a different type of fuck-up.
EDIT: UPS adverts down both sides and all over the page. Har de har.
Yes, thank you. Every time I see someone using "exponential" to mean "I dunno, but pretty darn big" to describe some function that has non-exponential growth, I want to ban them from using adjectives for a year.
I was disappointed Birtstone didn't mock Bausch, after including his quote in the first place. But then I was also disappointed that Birtstone didn't note the common optimization for computing factorials (turns out you can skip the final multiplication by 1). I expect better from the Reg.
Last summer I travelled to Poland and back by coach using the Polish company, Sindbad. Each journey had only one change of coach between Leicester and Krakow. There were several places where coaches synchronised journeys to exchange passengers and a large hub just inside the Polish border where coaches from all over Europe met at 8am then dispersed to different parts of Poland. The reverse happened at 8pm.
The problem here, I guess, is how to fill all the coach seats and at the same time minimise passenger changes.
It was a brilliant operation and I'd love to know how they run it.
Biting the hand that feeds IT © 1998–2022