Support for Asymmetric Multiple Traveling Salesman Problem

[elimkyl]

I have tried to run the downloaded data from LKH3 website mTSP/INSTANCES/ATSP/br17.atsp with multiple salesman.

Code

with open(filepath, "r") as f:
    problem_str = f.read()
problem = lkh.LKHProblem.parse(problem_str)
problem.salesmen = 5
problem.depots = [1]

solution = lkh.solve(solver_path, problem=problem, max_trials=1000, runs=10, mtsp_objective="MINMAX", mtsp_min_size = 1)

Results:

LKH3 Tour: [[6, 16, 7, 15], [12, 1, 14, 3, 2, 13, 10, 11], [5, 4, 8, 9], []]

Some of the settings for the problem didn't seems to get translated to the LKH3 program.

• It didn't start and end at the depot specified.
• We specified 5 salesmen and each should have at least 1 node in its tour due to the mtsp_min_size variable (mtsp_min_size specifies the minimum number of cities each salesman must visit in an MTSP or CVRP instance.), but the resultant tour only shows 3 tour instead of 5.

Are these variables supported? And what are the best way of passing them: overriding the problem attribute or in the solve function.

DEPOT = <integer>
MTSP_MIN_SIZE = <integer>
MTSP_MAX_SIZE = <integer>
MTSP_OBJECTIVE = [ MINMAX | MINMAX_SIZE | MINSUM ]

Thanks in advance!

[ben-hudson]

Hey so you're right that the settings aren't getting passed to the solver properly. The issue is that LKHProblem doesn't have the DEPOT, MTSP_MIN_SIZE, MTSP_MAX_SIZE, MTSP_OBJECTIVE, etc. fields so it leaves them out.

I don't have time to work on this right now, but it's an easy fix. You just need to add the missing fields here with the appropriate type of field (IntegerField, StringField, etc.)

[ben-hudson]

Oh, and the appropriate place to pass the min/max size and objective is as part of the problem object