1
$\begingroup$

Given:

Set of n>0 cities is to be traversed by m>0 salespeople

Where all the salespeople:

  • Are positioned at the same starting city;
  • Finish at a same destination (which different from starting city);

The problem is to determine m routes:

  • With optimal traversal cost/distance (load balancing if possible);
  • Each city must be visited exactly once by one salesmen.

Details:

I am a beginner in this kind of problem. Have been reading a lot of paper but mostly "must return to the same city".

What "kind" of problem is this?

How would you implement a solution for it?

Please help me with keywords or article (or a solution if possible).

Thank you in advance!

Improve this question
$\endgroup$
5
  • $\begingroup$ When you say beginner, could you be more specific about what your mathematical background is? $\endgroup$
    – David Roberts ♦
    Commented Jan 5, 2021 at 6:36
  • 1
    $\begingroup$ I'm currently in university studing software engineering.This is for my graduation thesis. As I said, I'm a beginner in this problem, I studied Discrete mathematics but dont have much confidence in it $\endgroup$
    – Nhân
    Commented Jan 5, 2021 at 6:47
  • $\begingroup$ Thanks for the response. Please note that MathOverflow is for research mathematics (and roughly at second-half of graduate mathematics, though it's not a hard line). I don't know enough about the subject matter of your question to know if this is original research, or more of a literature search style of "research" (looking up and summarizing known results). So I wish you the best of luck, but keep in mind that there is always math.stackexchance.com for questions at all levels of mathematics. $\endgroup$
    – David Roberts ♦
    Commented Jan 5, 2021 at 6:55
  • $\begingroup$ I really appreciate your help. $\endgroup$
    – Nhân
    Commented Jan 5, 2021 at 7:04
  • $\begingroup$ No problems, and I hope you learn some cool mathematics. $\endgroup$
    – David Roberts ♦
    Commented Jan 5, 2021 at 8:55

1 Answer 1

Reset to default
1
$\begingroup$

Assuming you mean that each city should be visited by exactly one salesman, this is called the multiple traveling salesman (mTSP) problem. See https://neos-guide.org/content/multiple-traveling-salesman-problem-mtsp.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thank you. But most of the cases, the problem is "All of the routes must start and end at the (same) depot.". What I'm looking for is that the start and end are not at the same spot $\endgroup$
    – Nhân
    Commented Jan 6, 2021 at 4:21
  • 1
    $\begingroup$ You can introduce a dummy depot adjacent to only the start and end to transform to the classical formulation. $\endgroup$
    – RobPratt
    Commented Jan 6, 2021 at 4:36
  • $\begingroup$ Can you please more specific $\endgroup$
    – Nhân
    Commented Jan 6, 2021 at 12:16
  • $\begingroup$ This is a standard transformation from Hamiltonian path to Hamiltonian cycle. There is a one-to-one correspondence between Hamiltonian cycles through the dummy node and Hamiltonian paths in the original graph. In the cycle, the two neighbors of the dummy correspond to the start and end of the path. $\endgroup$
    – RobPratt
    Commented Jan 6, 2021 at 16:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .