back to article Finding the formula for the travelling salesman problem

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, …

COMMENTS

This topic is closed for new posts.
  1. TRT Silver badge

    Wow.

    “What about if we bring you a sandwich?” the dispatcher asked.

    “Make it doughnuts and you have a deal.”

    Insight delivers to Springfield. Neat.

  2. Anonymous Coward
    Anonymous Coward

    Instead of investing in new software UPS should invest in some bubble wrap so that my packages arrive without looking like they've been partially digested by a mentally disturbed hippo.

    1. Phil O'Sophical Silver badge

      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.

      1. TRT Silver badge

        At least they're not Yodel.

        1. This post has been deleted by its author

      2. BillG
        WTF?

        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.

        1. Tom 13
          Facepalm

          @ BillG: It always depends on your local group.

          At my office the rolls are reversed. Government building, packages keep going awry and the error code reported by Fed Ex is:

          unable to find residence.

          1. Anonymous Coward
            Anonymous Coward

            Re: @ BillG: It always depends on your local group.

            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.

      3. Intractable Potsherd

        I've always tended to avoid UPS - a company that has "Oops!" as their name doesn't inspire confidence.* Nor does the shitty brown livery.

        * This may not work in certain accents.

  3. iGoto

    Worked on something similar to this.

    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.

    1. Tom 7

      Re: Worked on something similar to this.

      And ditto 30 years ago for microchip auto layout and routing - 10's of thousands of components and interconnects,

      Watch out for simulated annealing though - in economics that's called Marxism and not allowed.

      1. phil dude
        Boffin

        Re: Worked on something similar to this.

        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...

        P.

    2. Destroy All Monsters Silver badge

      Re: Worked on something similar to this.

      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?

    3. PyLETS

      Re: Worked on something similar to this.

      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.

    4. awol

      Re: Worked on something similar to this.

      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.

    5. Michael Wojcik Silver badge

      Re: Worked on something similar to this.

      Yes, Simulated Annealing is widely used for various applications that deal with intractable problems. There's a good DDJ article from a bygone era1:

      http://www.drdobbs.com/architecture-and-design/simulated-annealing-a-heuristic-optimiza/184404780

      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.

  4. Tezla P
    Go

    Ant colony optimisation algorithms, anyone?

    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 :-)

    1. Michael Wojcik Silver badge

      Re: Ant colony optimisation algorithms, anyone?

      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).

  5. Grikath

    or maybe....

    They could simply request knowledge input from the actual delivery men who tend to be locals, and know their area... oh wait.. They all got fired because they became Dangerously Knowledgeable, and upset or ignored the System.

  6. Anonymous Coward
    Anonymous Coward

    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).

  7. AndrueC Silver badge
    Facepalm

    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.

    Hmmm..

    Then again if my neighbour and I could reliably sync deliveries we could reduce the cost even further :)

    1. I ain't Spartacus Gold badge

      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.

      1. chr0m4t1c

        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.

        1. JetSetJim
          Flame

          Boilerjuice do it for domestic oil deliveries...

          Title says it all...

      2. AndrueC Silver badge
        Thumb Up

        Some will already give you lower delivery costs

        Yeah, Tesco do but only based on time rather than being 'opportunistic'. Still, at £1 delivery it's cheaper than going to my nearest decent Tesco since that's over ten miles away. The one in town is very poor and not adequate for a weekly shop.

        1. Paul2724

          You have a decent Tesco near you ??? I guess there has to be one somewhere !

          1. Intractable Potsherd

            Decent Tesco

            Riverside Tesco in Dundee - nice building, good selection, friendly staff, and a view onto the Tay Rail Bridge. I actually enjoy going there.

    2. iRadiate

      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.

  8. Frumious Bandersnatch
    Coffee/keyboard

    "So, where do the doughnuts come in?"

    Damn. I was guessing (and hoping) they'd found some way to break free from the confines of Cartesian geometry for that customer and instead routed over a topology with one hole ...

    Now where did I leave my coffee cup ... ?

    1. Hero Protagonist

      Re: "So, where do the doughnuts come in?"

      +1 for the topology joke

    2. John Gamble

      Re: "So, where do the doughnuts come in?"

      They found a nearby doughnut shop by making use of the Ham Sandwich Theorem

  9. Chris Miller

    "Which are the good, fast roads to use and how well do they connect the stops on the route?"

    That's simply dealt with by choosing the correct metric - you could use minutes of travel instead of miles, for instance (or some more complex combination).

    1. Tom 13

      Re: you could use minutes of travel

      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.

      1. Diogenes

        Re: you could use minutes of travel

        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.

  10. Terry 6 Silver badge

    Which only leaves me wondering..

    ...why the small white multdrop van that apparently left a depot in Borehamwood, a few miles up the road, at 7:00am, took almost 12 hours to get to Finchley and was unable to let me know an approximate delivery time so that soemone had to wait in all day.

    1. TRT Silver badge

      Re: Which only leaves me wondering..

      Wasn't Yodel by any chance was it? Departed Borehamwood at 11.30 Saturday, parcel dropped off three miles away at 19:05. Contents: mashed.

      1. Terry 6 Silver badge

        Re: Which only leaves me wondering..

        !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

        Bloody mind readers in this place now is it.

        1. TRT Silver badge

          Re: Which only leaves me wondering..

          I had plenty of meditation time available whilst waiting in all day Saturday!

          Nah, joking. Merely another cog in the gestalt entity that is the Yodel customer. Shared experience.

  11. Naughtyhorse

    The key..

    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.

    mindblowing.

    1. Fink-Nottle

      Re: The key..

      > 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.

      http://highscalability.com/blog/2012/6/13/why-my-soap-film-is-better-than-your-hadoop-cluster.html

  12. M Gale

    40ft? A van?

    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.

    1. Tom 13

      Re: 40ft? A van?

      Maybe he's from Texas. I here everything is bigger in Texas.

  13. another_vulture

    Factorial, not exponential

    I don't think there is a exponential bound on a factorial problem. Factorial is worse than exponential.

    1. John H Woods Silver badge

      Re: Factorial, not exponential

      Correct. If f(n) is n! / a^n, then think about what f(n+1) is -- It gets bigger by a factor of (n+1)/a and therefore the growth of the factorial increasingly exceeds that of the exponential as n increases.

    2. Michael Wojcik Silver badge

      Re: Factorial, not exponential

      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.

  14. Bucky 2

    I'm pretty sure something is being left out here.

    In most travelling salesman problems I've ever read about, a farmer's daughter figures in somehow.

  15. Siskris

    Similar problem

    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.

    1. Naughtyhorse

      Re: Similar problem

      I'll bet you a pound to a pinch of shit it's an old codger in one of them brown storesman coats with an impressively large back of a fag packet, and a bloody sharp pencil

This topic is closed for new posts.