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:
  • lines (list) – List of lines. Each element of this list is a string.
  • keyword (str) – The input keyword
Returns:

index – If the keyword is found, returns the line index. None will be returned otherwise.
Return type:

int
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:

str

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 K-opt 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 Lin-Kernighan. Each kick is a random K-swap 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 K-swap kick (an extension of the double-bridge 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 K-opt 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

initialized()[source]

Return True if the parameters have been initialized. False otherwise.

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 near-optimal tour found using the LKH heuristics.
  • info (dict) – Extra information about the solver call. It includes the CPU time, stdout and stderr