StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>This problem is known in literature as Multiple Traveling Salesman Problem (MTSP). </p> <p><strong><a href="http://en.wikipedia.org/wiki/Travelling_salesman_problem" rel="nofollow">TSP</a></strong> is a hard problem to solve, in fact a brute force solution can be found only for a small number of cities (<~20). Many heuristic methods have been developed in order to find a suboptimal solution: you can find an intresting survay in <a href="http://cdn.intechopen.com/pdfs/12736/InTech-Traveling_salesman_problem_an_overview_of_applications_formulations_and_solution_approaches.pdf" rel="nofollow">this paper</a>. In general I find a good solution the application of a <strong><em>Closest neighbor heuristic</em></strong> followed by a <strong><em>k-opt</em></strong> optimization in a <strong><em>Hill climbing</em></strong> with <strong><em>random restarts</em></strong>.</p> <p>I strongly reccomend you to implement TSP as a starting point for your algorithm (k=1), it's just a brick that you will use later in the solution of the MTSP and will give you the opportunity to test your skills in an heuristic approach. Furthermore, once you understand the theory, the implementation will require just an evening (maybe with some cup of coffee by your side).</p> <p><strong>Multiple Traveling Salesman Problem</strong> is a really challenging problem but you can apply the same heuristic methods. Basically you need to find an initial solution in which you assign a number of cities to each salesman (see later for a possibly <em>Closest neighbor</em> metric), than for each salesman you can compute an heuristic solution of the TSP.</p> <p><strong>Hill climbing</strong> methods here can swap cities between salesman and recompute TSP. This method will lead you to many <a href="http://en.wikipedia.org/wiki/Maxima_and_minima" rel="nofollow">local minima</a>, for this reason i suggest you to use a <a href="http://en.wikipedia.org/wiki/Simulated_annealing" rel="nofollow"><strong>simulated annealing algorithm</strong></a>. Basically you swap the cities with a decreasing probability during the evolution of the algorithm.</p> <p><strong>An initial solution for MTSP</strong> Look at this one dimension example (S for salesman an C fo city)</p> <ul> <li>S0 = 3</li> <li>S1 = 5</li> <li>C0 = 2.5</li> <li>C1 = 1.5</li> <li>C2 = 3.6</li> <li>C3 = 8</li> </ul> <p>Just implement a greedy algorithm (use a timeline with a queue)</p> <ol> <li>Time 0.5: S0 -> C0</li> <li>Time 1.4: S1 -> C2</li> <li>Time 1.5: S0 -> C1</li> <li>Time 5.8: S1 -> C3</li> </ol> <p>Initial partion: S0:{C0,C1} - S0:{C2,C3}</p> <p>You can also read this article and follow the bibliography backwards</p> <p><a href="http://www.worldacademicunion.com/journal/1749-3889-3897IJNS/IJNSVol09No2Paper06.pdf" rel="nofollow">http://www.worldacademicunion.com/journal/1749-3889-3897IJNS/IJNSVol09No2Paper06.pdf</a></p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload