Helper function used for parsing TSPLIB files. It searchs for the given keyword across the list of lines.
index – If the keyword is found, returns the line index. None will be returned otherwise.
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
write_parameters_file(problem_file, params, working_path)¶
Write the parameters file used by the lkh_solver node to solve a TSP instance.
basename – The basename is the problem_file without the file extension
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.
The number of backbone trials in each run.
Specifies whether a backtracking K-opt move is to be used as the first move in a sequence of moves (where K = move_type)
Number of extra candidate edges to be added to the candidate set of each node.
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
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.
The maximum number of candidate edges to be associated with each node. Default: 30
The maximum number of trials in each run.
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.
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.
The internal precision in the representation of transformed distances (10 corresponds to 2 decimal places)
The total number of runs.
Specifies the initial seed for random number generation.
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
Return True if the parameters have been initialized. False otherwise.
lkh_solver(problem_file, params, pkg='lkh_solver', rosnode='lkh_solver', working_path='/tmp/lkh')¶
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.
- 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
- 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
- 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