6
$\begingroup$

I'm building a Mixed Integer Linear Program for a variant of TSP I'm dealing with, where there are multiple salesmen. The way I have formulated the problem is that each agent has a time variable $T_i$ associated to them which is the time taken for them to complete their route.

My plan to minimize the time taken for everyone to return is then have an extra variable $T_{max}$ and do $\min T_{max} \, s.t. \,T_i\leq T_{max}$.

This is working and finding solutions but I'm getting the case where the faster agents are taking somewhat counter intuitive routes as the have no incentive since they are not holding up $T_{max}$ from being decreased.

Are there any common tricks to make the faster agents also behave somewhat efficiently as well?

$\endgroup$

2 Answers 2

4
$\begingroup$

You are dealing with a multi-objective problem.

A common approach is to first consider your main goal, in your case that is $T_{max}$. Once you have found an optimal $T_{max}$, you adjust your objective function by minimizing for example the distance traveled. Additionaly, you are adding a constraint to your problem that states that no tour length exceeds the previously found $T_{max}$ (now as a parameter, not a variable).

$\endgroup$
4
  • $\begingroup$ Thanks, I suppose this would make the run time linear in the number of agents as I would have to solve the problem then run another minimization for each agent being the objective function? $\endgroup$
    – John Smith
    Commented Jun 13 at 11:13
  • 1
    $\begingroup$ You do not have to run a problem for each agent, but one with all the agents. $\endgroup$
    – PeterD
    Commented Jun 13 at 11:15
  • $\begingroup$ Are you not suggesting something like solve the problem once to get $T_{max}^1$ and then run the problem again, with an extra constraint $T_1 \leq T_{max}^1$ and then solve the problem $\max T_{max} \, s.t. \, T_i \leq T_{max}\, i=2,3,4,..$ and then repeat this for each agent? Ah I see how they're different, your approach should take that all into account since the sum of all the paths should be minimised! Thanks $\endgroup$
    – John Smith
    Commented Jun 13 at 12:29
  • 1
    $\begingroup$ Some MIP solvers support multiple objectives with lexicographic ordering (which is what is proposed here). They would only require solving the model once. $\endgroup$
    – prubin
    Commented Jun 13 at 16:06
3
$\begingroup$

In addition to the multiobjective approach suggested by @PeterD, another possibility is to penalize the total time taken by each agent in the objective. The objective would now be to minimize $T_{max} + \lambda \sum_i T_i$ where $\lambda > 0$ needs to be small enough that it does not lead to a solution which extends the time of the slowest agent in order to save time with faster agents. (This assumes that agents can interfere with each other in some way.)

The upside to this approach is that it requires solving the model just once and does not require support for multiple objectives in the solver. The downside is that it requires guessing a value of $\lambda$ that is large enough to make the gain from reductions in route times bigger than rounding error while small enough not to result in inflation of $T_{max}.$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.