31

I have a problem that has been effectively reduced to a Travelling Salesman Problem with multiple salesmen. I have a list of cities to visit from an initial location, and have to visit all cities with a limited number of salesmen.

I am trying to come up with a heuristic and was wondering if anyone could give a hand. For example, if I have 20 cities with 2 salesmen, the approach that I thought of taking is a 2 step approach. First, divide the 20 cities up randomly into 10 cities for 2 salesman each, and I'd find the tour for each as if it were independent for a few iterations. Afterwards, I'd like to either swap or assign a city to another salesman and find the tour. Effectively, it'd be a TSP and then minimum makespan problem. The problem with this is that it'd be too slow and good neighborhood generation of swapping or assigning a city is hard.

Can anyone give an advise on how I could improve the above?

EDIT:

The geo-location for each city are known, and the salesmen start and end at the same places. The goal is to minimize the max travelling time, making this sort of a minimum makespan problem. So for example, if salesman1 takes 10 hours and salesman2 takes 20 hours, the maximum travelling time would be 20 hours.

Nicolas Kaiser
  • 1,628
  • 2
  • 14
  • 26
dustin ledezma
  • 615
  • 2
  • 6
  • 10
  • I can think about situations which your algorithm doesn't find the best answer, if you only want to find the best answer and not case if a city is visited by 2 salesmen. think of a country with 20 cities, all having distance 20 from each other. but there is only a loop in which all the cities have distance 1. meaning `d(c[i],c[j])=20,i!=(j+1)%20` and `d(c[i],c[(i+1)%20]) = 1` in this the all your sales man have to visit all cities for minimum cost. – Ali1S232 Jun 04 '11 at 20:24
  • Do all the salesmen start from the same city? – Case Jun 04 '11 at 20:24
  • 1
    Some more information that could improve this question: Do you have geo-location information for the cities, or all the distances between them? What are your constraints per salesman? Time, distance? Just the tip of the iceberg for problems like this. – Bork Blatt Jun 04 '11 at 20:27
  • Heuristics for the TS is a difficult problem (see this book, http://www.amazon.com/Traveling-Salesman-Problem-Combinatorial-Optimization/dp/0471904139) – ysdx Jun 04 '11 at 20:32
  • I'm with Bork. We need more information. For example, if you have two loops, but they aren't the same distance, is that an acceptable solution? Or are you optimizing for average path length? – Case Jun 04 '11 at 20:33
  • @Sharon: Yes, the salesmen start from the same city. @Bork Blatt, I edited the original question to address some of your questions =). @Mehrdad we still need to deliver the parcels to the customers – dustin ledezma Jun 04 '11 at 20:34
  • @Gajet: Can you explain further? What do you mean by only a loop in which all the cities have distance 1 when you previously mentioned all have distance 20 from each other? – dustin ledezma Jun 04 '11 at 20:37
  • @dustin ledezma: just look at the sample distance function I mentioned after, it came to my head after finishing my first sentence so I wrote it afterwards but it's completing my example : when that is the distance function (although it may not happen in real world) if all your salesmen go from city 1 to city 2 and then city 3 and so on and after city 20 return to city 1 you'll just have your lowest price. also you can just send one salesman. there can also be a city that can benefit 2 salesman for traveling if they both pass throw it. I can think of a example but it's hard to explain it here. – Ali1S232 Jun 04 '11 at 20:45
  • @dustin Please don't repost your questions using multiple accounts. Which account do you want to keep? I'll merge the other one into it. – Lasse V. Karlsen Jun 04 '11 at 20:46
  • @Lasse: Sorry about that, I don't actually have an account and I believe the cache stored in the browser have disappeared so I don't have the rights to edit the previous post. – dustin ledezma Jun 04 '11 at 20:47
  • @dustin Ok, do you want me to just close that question and merge your other account into this here then (ie. merge dustin - http://stackoverflow.com/users/783534/dustin - into this one here - dustin ledezma) ? – Lasse V. Karlsen Jun 04 '11 at 20:50
  • @Lasse: Yes that'd be great, thanks! – dustin ledezma Jun 04 '11 at 20:55
  • 1
    @dustin Ok, I merged the old account into this one, and also merged the TSP question, there was one answer there that I didn't see here, so it was moved, you should now have access to your old question and any reputation you had on the old account here. Also, if you haven't already you might want to ensure you don't lose your account again in the future by providing some login data :) Best of luck with your TSP problem :) Cheers. – Lasse V. Karlsen Jun 04 '11 at 21:00
  • Besides looking into metaheuristics (tabu search, simulated annealing, ...), make sure you implement [delta based score caculcation](http://docs.jboss.org/drools/release/5.2.0.CR1/drools-planner-docs/html_single/index.html#d0e1619). – Geoffrey De Smet Jun 05 '11 at 07:01

8 Answers8

12

TSP is a difficult problem. Multi-TSP is probably much worse. I'm not sure you can find good solutions with ad-hoc methods like this. Have you tried meta-heuristic methods ? I'd try using the Cross Entropy method first : it shouldn't be too hard to use it for your problem. Otherwise look for Generic Algorithms, Ant Colony Optimization, Simulated Annealing ...

See "A Tutorial on the Cross-Entropy Method" from Boer et al. They explain how to use the CE method on the TSP. A simple adaptation for your problem might be to define a different matrix for each salesman.

You might want to assume that you only want to find the optimal partition of cities between the salesmen (and delegate the shortest tour for each salesman to a classic TSP implementation). In this case, in the Cross Entropy setting, you consider a probability for each city Xi to be in the tour of salesman A : P(Xi in A) = pi. And you work, on the space of p = (p1, ... pn). (I'm not sure it will work very well, because you will have to solve many TSP problems.)

ysdx
  • 8,889
  • 1
  • 38
  • 51
  • Meta-heuristic method is actually exactly what I am looking at. I was looking to try to use Simulated Annealing after the "iterations" I mentioned in the hopes of closing down the search space. But again, coming up with good neighborhood generator that will guide the search, I am finding difficult. – dustin ledezma Jun 04 '11 at 20:43
3

When you start talking about multiple salesmen I start thinking about particle swarm optimization. I've found a lot of success with this using a gravitational search algorithm. Here's a (lengthy) paper I found covering the topic. http://eprints.utm.my/11060/1/AmirAtapourAbarghoueiMFSKSM2010.pdf

Dustin Pfannenstiel
  • 552
  • 3
  • 15
  • Yep I forgot to say "and Particle Swarm Optimization" – ysdx Jun 04 '11 at 20:42
  • 1
    The link no longer works. After searching a bit it seems the paper has been retracted (I found a notice of retraction of a paper from the same author with a similar topic from 2010 here: https://ieeexplore.ieee.org/abstract/document/5486167/ ) – Deruijter Jun 12 '18 at 09:07
2

I wouldn't start writing an algorythm for such complicated issue (unless that's my day job - to write optimization algorythms). Why don't you turn to a generic solution like http://www.optaplanner.org/ ? You have to define your problem and the program uses algorithms that top developers took years to create and optimize.

akostadinov
  • 17,364
  • 6
  • 77
  • 85
2

Why don't you convert your multiple TSP into the traditional TSP?
This is a well-known problem (transforming multiple salesman TSP into TSP) and you can find several articles on it.

For most transformations, you basically copy your depot (where the salesmen start and finish) into several depots (in your case 2), make the edge weights in a way to force a TSP to come back to the depot twice, and then remove the two depots and turn them into one.

Voila! got two min cost tours that cover the vertices exactly once.

CosmicGiant
  • 6,275
  • 5
  • 43
  • 58
Maryam
  • 21
  • 1
1

My first thought on reading the problem description would be to use a standard approach for the salesman problem (googling for an appropriate one as I've never actually had to write code for it); Then take the result and split it in half. Your algorithm then could be to decide where "half" is -- maybe it is half of the cities, or maybe it is based on distance, or maybe some combination. Or search the result for the largest distance between two cities and choose that as the separation between salesman #1's last city and salesman #2's first city. Of course it does not limit to two salesman, you would break into x pieces; But overall the idea is that your standard 1 salesman TSP solution should have already gotten the "nearby" cities next to each other in the travel graph, so you don't have to come up with a separate grouping algorithm...

Anyway, I'm sure there are better solutions, but this seems like a good first approach to me.

Chris Shaffer
  • 32,199
  • 5
  • 49
  • 61
1

Have a look at this question (562904) - while not identical to yours there should be some good food for thought and references for further study.

Community
  • 1
  • 1
Bork Blatt
  • 3,308
  • 2
  • 19
  • 17
  • I agree...The hierarchical clustering algorithm mentioned is the perfect heuristic for this kind of problem. – Case Jun 04 '11 at 20:36
0

As mentioned in the answer above the hierarchical clustering solution will work very well for your problem. Instead of continuing to dissolve clusters until you have a single path, however, stop when you have n, where n is the number of salesmen you have. You can probably improve it some by adding in some "fake" stops to improve the likelihood that your clusters end up evenly spaced from the initial destination if the initial clusters are too disparate. It's not optimal - but you're not going to get an optimal solution for a problem like this. I'd create an app that visualizes the problem and then test many variants of the solution to get a feel for whether your heuristic is optimal enough.

In any case I would not randomize the clusters, that would cause the majority of the clusters to be sub-optimal.

Case
  • 1,848
  • 21
  • 32
0

just by starting to read your question using genetic algorithm came to my head. just use two genetic algorithm in the same time one can solve how to assign cities to salesmen and the other can solve the TSP for each salesman you have.

Ali1S232
  • 3,373
  • 2
  • 27
  • 46