Travelling Salesman with multiple salesmen?

by

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

More Related Contents:

  1. Design patterns for converting recursive algorithms to iterative ones
  2. What is the problem name for Traveling salesman problem(TSP) without considering going back to starting point?
  3. Efficient way to add element to sorted datastructure [closed]
  4. What is tail recursion?
  5. Algorithm for finding the fewest rectangles to cover a set of rectangles without overlapping
  6. Getting the closest string match
  7. How do you detect Credit card type based on number?
  8. How does finding a cycle start node in a cycle linked list work?
  9. Efficient list intersection algorithm
  10. Millions of 3D points: How to find the 10 of them closest to a given point?
  11. Algorithm to randomly generate an aesthetically-pleasing color palette [closed]
  12. How to efficiently build a tree from a flat structure?
  13. What would cause an algorithm to have O(log log n) complexity?
  14. 3D Least Squares Plane
  15. Is there ever a good reason to use Insertion Sort?
  16. Shortest distance between points algorithm
  17. The Sieve of Atkin
  18. Quicksort vs heapsort
  19. Algorithm to mix sound
  20. finding a^b^c^… mod m
  21. Algorithm to find the most common substrings in a string
  22. Sorting a sequence by swapping adjacent elements using minimum swaps
  23. Simplest way to get the top n elements of a Scala Iterable
  24. Optimizing Conway’s ‘Game of Life’
  25. Retrieving the top 100 numbers from one hundred million of numbers [duplicate]
  26. What is password hashing? [closed]
  27. Can an array be grouped more efficiently than sorted?
  28. Why use binary search if there’s ternary search?
  29. Algorithm for reflecting a point across a line
  30. What is the most efficient way to encode an arbitrary GUID into readable ASCII (33-127)?

Leave a Comment