The Traveling Salesperson Who Needs to Restock Problem

February 27, 2009 1:41 PM

I'm having trouble conceptualizing a Traveling Salesperson Problem that I'm interested in solving.

The story:
This is for a bicycle powered weekly curbside recycling pickup service. Each customer/household has one container of recyclables that they put by the curb on a designated day. There will be somewhere between 20 and 300 customers somewhat scattered around the city. The bicycle trailer can hold up to 12 containers of recycling at a time and off-loads the containers at any of 28 transfer stations also scattered around the city.

I'd like to create a series of fairly efficient routes so each household is visited at least once and no more than 12 households are visited in a row without stopping by a transfer station. More complex requirements would be to start and end at a particular location (easy) and divide the route into multiple days so no more than X miles are traveled or Y households are visited in a particular trip (probably increases the number of calculations another few powers).

My level of knowledge about TSP problems is limited to reading Wikipedia and the TSP Solver for Google Maps but I would like to learn more.

So two questions:

One, anyone got a quick answer?
Two, any pointers for learning more about this type of problem, including the language that would be used to describe it?
Third, when some company has a Traveling Salesperson Problem how do they solve it? Hire a mathematician? Specialized software like Concorde?

posted by Chrishartley to science & nature (10 comments total)

First, it's called the "Traveling Salesman Problem". Presumably you know that there is no general solution beyond brute force.

The best approach available to solving this kind of optimization problem in a practical amount of time is genetic algorithms. And a good implementation can come up with really amazingly well optimized solutions, which will be within a few percent of God's Solution.

Genetic algorithms are really quite easy to program. The only tricky part is the evaluation heuristic, and that's usually not too tough.
posted by Chocolate Pickle at 1:58 PM on February 27

This isn't a classic travelling salesman problem because your solution will contain multiple routes rather than a single route.

Your problem is: For a given set of transfer station and a given set of customers, what set of cycles of less-than-or-equal to 12 customers and 1 tranfer station optimally cover all customers. The additional constraints you pose are easy to satisfy. If I were to try to solve this problem, I would start with simulated annealing rather than TSP. Any third-year computer science student should be able to solve this problem for you once; writing an application to solve it for you every month or whenever you get a new customer is a job for a software engineer.

If you were interested in learning about this problem in excruciating depth, I can recommend the following books:

* http://www.amazon.com/Combinatorial-Optimization-Algorithms-Christos-Papadimitriou/dp/0486402584/ref=sr_1_1?ie=UTF8&s=books&qid=1235771848&sr=1-1
* http://www.amazon.com/Algorithm-Design-Manual-Steve-Skiena/dp/0387948600

On preview: I really wouldn't recommend genetic algorithms for this problem. Their performance and results are generally sub-optimal in my experience for combinatorial problems, since you generally have to layer some pseudobiology on top of your problem domain to model it. This is a classic graph traversal problem and there are deterministic methods to solve it which would be specializations of clique-finding or hamiltonian cycle algorithms, but you don't need a deterministic method; a probabilistic method like simulated annealing will work fine.
posted by doteatop at 2:07 PM on February 27 [1 favorite has favorites]

Simulated annealing is also used for travelling salesman problems. Using a voroni diagram will give you an easy way to know which depot is closest at any given point in the city. Beyond that, uh, I dunno.
posted by GuyZero at 2:10 PM on February 27

Thirding Simulated Annealing.

you just need a way to express a proposed solution (just a list of destinations, for example), a way to mutate a route (by randomly swapping elements in that list, for example), and a way to evaluate a route (this is the finnicky bit.)

The hardest part, since it can't be derived a priori, might be coming up with a function that gives you the travel time or distance between two addresses in your system. Perhaps you could approximate using Manhattan distance, but YMM(literally)V.
posted by blenderfish at 2:15 PM on February 27

Addressing the above, just want to point out you can use a voronoi diagram as GuyZero suggests, but the optimal route set may include customers being serviced by the second-closest depot, for example.

Blenderfish is right that mapping is hard. I recommend using PyRoute and Open Street Map data. The map-distance problem is completely solved for you by these open source saints.
posted by doteatop at 2:20 PM on February 27 [1 favorite has favorites]

Third, when some company has a Traveling Salesperson Problem how do they solve it? Hire a mathematician? Specialized software like Concorde?

It depends a lot on the exact nature of the TSP. If you're a microchip manufacturer and the cities in your TSP represent hundreds of thousands of locations on a chip that some doodad is going to visit, then you've probably already employed a specialist or two to solve this problem. On the other hand, if you're lone courier plotting your route over a dozen or so pick-up/drop-off points, then you're probably just going to eyeball it. Just because a class of problems is difficult doesn't mean that every instance of that problem is difficult.

In any case, the two most common solution methods (aside from just eyeballing it) in industry that I've encountered are: 1) formulate the problem as a integer (linear) program and use a linear solver to solve it, or 2) use something like Microsoft MapPoint to try to plot routes. People with bigger problems tend to use 1), people with smaller problems or who lack the required math/operations research expertise tend to use 2). I'm sure there are also people who use things like genetic programming and simulated annealing and other computer science/AI stuff like that; I just haven't encountered them myself.
posted by mhum at 2:20 PM on February 27

First, it's called the "Traveling Salesman Problem". Presumably you know that there is no general solution beyond brute force.

There is a difference between finding "the solution", i.e. the absolute shortest path and finding a "good" solution, i.e. just a solution that's pretty good. To say that there is no "general solution" isn't appropriate here because he's only talking about finding a "good" solution.

There are a lot of different optimization algorithms out there, I suggest looking at the books doteatop recommended. Most are not too hard to implement, but I'm not an expert on which would be best for your particular application.
posted by delmoi at 2:21 PM on February 27

I have a little experience in both combinatorial and convex optimization, so I will give this a crack.

The first thing I noticed is that your number of destinations is actually very small (20-300) and you are tackling something slightly different than TSP. Instead of treating this as a TSP problem, I might treat it as a graph partitioning problem, another class of NP-complete problems.

Your very first step in encoding this problem is to take a bunch of points (vertices) in space that represent each destination and turn them into a vertex-edge matrix. To get the distance cost d of each edge A-B, you need to evaluate the amount of time/distance it will require to get between Vertex A and Vertex B. You can make this matrix relatively sparse if you like by filtering the results (it doesn't make sense to consider two stops on opposite ends of town, so you should only consider two vertices that are relatively 'local' to each other).

The next step I would take is to treat this is as a graph partitioning problem. Partition the town into 'route sets', and make the sets as local as possible. Look into a tool like METIS which is very high-quality and can be freely downloaded online. Feed METIS your Vertex-Edge Matrix from the previous step and ask it to cut your town into n routes by calling the k-way graph partitioning code, requesting a cut into n subpartitions. Also, please note that if you're going to use graph partitioning, you need to invert your distance costs (METIS will try to minimize the edge cut between partitions, so you need to let your edge cost c=1/d. Setting the cost between transfer stations to zero increase the likelihood that they will be distributed well among your route sets.

You have such a small number of destinations that METIS will be able to solve this problem in under a minute, most likely in less than 10 seconds. You should be able to experiment with how many route sets you'd like to make, and then solve TSP on the individual routes once each has been generated to determine the total cost.

Your problem is sufficiently interesting that you would probably have some luck taking it to your local University's Industrial Engineering, Applied Mathematics, or Computer Science (which will depend on your school) Department, and asking for somebody with experience in solving combinatorial optimization problems. Also, your problem can be formulated and solved quickly as a Mixed-Integer Linear Program in the full multiple TSP sense. I don't know how to solve this problem using simulated annealing.
posted by onalark at 6:22 PM on February 27 [1 favorite has favorites]

Thank you everyone for the great answers. I have a lot to of reading to do before I really understand what it all means. I'll also try emailing a few professors at the local universities.
posted by Chrishartley at 7:21 PM on February 27

I think I goofed. You might want to just negate your distance costs instead of inverting them.
posted by onalark at 7:32 PM on February 27