API Documentation¶
Parser¶

lkh_solver.parser.
get_keyword_index
(lines, keyword)[source]¶ Helper function used for parsing TSPLIB files. It searchs for the given keyword across the list of lines.
Parameters: Returns: index – If the keyword is found, returns the line index. None will be returned otherwise.
Return type:

lkh_solver.parser.
read_tsplib_tour
(filename)[source]¶ Read a tour from a TSPLIB file
Parameters: filename (list) – Path to the tour file. The expected extension is .tour Returns:  tour (list) – The tour as a list of integers
 info (dict) – Extra information contained in the .tour file

lkh_solver.parser.
write_parameters_file
(problem_file, params, working_path)[source]¶ Write the parameters file used by the lkh_solver node to solve a TSP instance.
Parameters:  problem_file (str) – Path to the problem file (.tsp file)
 params (SolverParameters) – Parameters to be pased to the LKH solver. See
SolverParameters
for details.  working_path (str) – Path where the files generated by the LKH solver will be placed.
Returns: basename – The basename is the problem_file without the file extension
Return type:
Solver¶

class
lkh_solver.solver.
SolverParameters
[source]¶ Bases:
object

ascent_candidates
= 50¶ The number of candidate edges to be associated with each node during the ascent. The candidate set is complemented such that every candidate edge is associated with both its two end nodes.

backbone_trials
= 0¶ The number of backbone trials in each run.

backtracking
= False¶ Specifies whether a backtracking Kopt move is to be used as the first move in a sequence of moves (where K = move_type)

extra_candidates
= 0¶ Number of extra candidate edges to be added to the candidate set of each node.

kicks
= 1¶ Specifies the number of times to “kick” a tour found by LinKernighan. Each kick is a random Kswap kick. However, if KICKS is zero, then LKH’s special kicking strategy, WALK, is used in stead

kick_type
= 0¶ Specifies the value of K for a random Kswap kick (an extension of the doublebridge move). If KICK_TYPE is zero, then the LKH’s special kicking strategy, WALK, is used.

max_candidates
= 30¶ The maximum number of candidate edges to be associated with each node. Default: 30

max_trials
= 1000¶ The maximum number of trials in each run.

move_type
= 5¶ Specifies the sequential move type to be used in local search. A value K >= 2 signifies that a sequential Kopt move is to be used.

population_size
= 1¶ Specifies the maximum size of the population in LKH’s genetic algorithm. Tours found by the first POPULATION_SIZE runs constitute an initial population of tours. In each of the remaining runs two tours (parents) from the current population is recombined into a new tour (child) using a variant of the Edge Recombination Crossover (ERX). The parents are chosen with random linear bias towards the best members of the population. The child is used as initial tour for the next run. If this run produces a tour better than the worst tour of the population, then the resulting tour replaces the worst tour. Premature convergence is avoided by requiring that all tours in the population have different costs.

precision
= 10¶ The internal precision in the representation of transformed distances (10 corresponds to 2 decimal places)

runs
= 1¶ The total number of runs.

seed
= 1¶ Specifies the initial seed for random number generation.

trace_level
= 1¶ Specifies the level of detail of the output given during the solution process. The value 0 signifies a minimum amount of output. The higher the value is the more information is given


lkh_solver.solver.
lkh_solver
(problem_file, params, pkg='lkh_solver', rosnode='lkh_solver', working_path='/tmp/lkh')[source]¶ Run the lkh_solver on the given problem_file. The lkh_solver node will generate several files (.par, .pi, .tour, etc) that can be used for debugging.
Parameters:  problem_file (str) – The problem file using the TSPLIB format. The expected extension of the file is .tsp.
 params (SolverParameters) – Parameters to be pased to the LKH solver. See
SolverParameters
for details.  pkg (str) – ROS package where the solver is available
 rosnode (str) – ROS node of the solver
 working_path (str) – Path to be used by the LKH solver to store the required intermediate files
Returns:  tour (list) – The nearoptimal tour found using the LKH heuristics.
 info (dict) – Extra information about the solver call. It includes the CPU time, stdout and stderr