There is an unweighted and directed graph that may contain bidirectional edges. There is a fixed number of salesmen. Each salesman can start from any node. Each node should be visited at least once. I need to minimize each salesman's path. Which algorithm can I use to solve this problem?
1 Answers
This problem is a variation of the Travelling Salesman Problem (TSP) called Multiple Travelling Salesman Problem, or mTSP. More precisely, it is the MDVRP, for Multiple Depot Vehicle Routing Problem,.
This problem, being a generalization of the TSP problem, is also NP-hard.
There exist several methods to solve this problem, each with its own pros and cons. It's up to you to choose one.
First, you have to answer a simple question: do you need an optimal solution, or is an approximation acceptable ? If your input is relatively large (say, dozens of vehicules visiting hundreds of nodes), an optimal algorithm is out of question (there may not be enough energy in the world to compute an optimal solution within a century).
Approximation algorithms can be very efficient, and propose very good approximations.
When it comes to the algorithms, here is a list of algorithms/methods you could consider:
- Brute force: with a couple of vehicles and a handful of nodes, it will be perfect. Otherwise, you can just forget it.
- Branch and Bound: it can be en efficient method to solve some optimization problems, but in your case, I would not recommend it as a premium solution.
- Metaheuristics: this term encompasses a range of very efficient methods, such as local search, genetic algorithms, simulated annealing, ant colony .... They are approximation algorithms, but they have the advantage to be able to tackle very large inputs, and deliver quickly a decent approximation. They're generally not too hard to implement, especially on graph problems.
- Mixed-integer linear programming (MILP): since the mTSP problem can be written as a MILP, you can use a MILP solver such as CPLEX, Gurobi or LocalSolver to find a solution. This approach has several advantages: given that you have a little experience regarding mathematical programming, they're very easy to write, and they generally have very good performances. I would recommend this approach over the others for several reasons. First, I believe that you will get the best tradeoff "hours of work vs solution quality". Second, you can add some other constraints (like saying that a vehicle should not drive 15 hours in a row because the human driver is a human). Third, you can run the solver for a minute or for an hour, it's your choice. You will get better and better solutions as it's running, along with a bound (for instance, you will know that your solution is at most 8.7% worse than the optimal solution, which is always nice to report to management). If you have questions regarding this method, you can ask it on the OR stackexchange.
- If you have enough expertise to read scientific papers, and enough time and skills to go for it, you can dig in the literature and write your own algorithm. This would be a good solution if we're talking about a very big company, where each percent gained on the solution represents a lot of money (say, a company with hundreds/thousands of vehicles operating at a country level). If you decide to go for it, you'll probably get better solutions, but it may take (at least) a couple of months to a small and experienced team. You can start with this survey to get an overview (beware though, the survey is 14 y.o, better methods can be described in more recent papers). To look for very similar problems, the term "MDVRP" is your friend.
TL;DR: Write your problem as a MILP, and feed it to a solver. It's the best trade-off you'll ever get for a TSP variant, especially since plenty solvers have TSP-oriented optimizations.
Related