LKH-3
Version 3.0.13 (November 2024)
LKH-3 is an extension of LKH-2 for solving constrained traveling salesman and vehicle routing problems. The extension has been desribed in the report
K. Helsgaun,
An Extension of the Lin-Kernighan-Helsgaun TSP Solver for Constrained Traveling Salesman and Vehicle Routing Problems.
Technical Report, Roskilde University, 2017.
Currently, LKH-3 is able to solve the following problem types:
From LKH-2:
TSP: Symmetric traveling salesman problem
ATSP: Asymmetric traveling salesman problem
HCP: Hamiltonian cycle problem
HPP: Hamiltonian path problem
New in LKH-3:
ACVRP: Asymmetric capacitated vehicle routing problem
ADCVRP: Asymmetric distance constrained vehicle routing problem
BMTSP: Bounded multiple traveling salesman problem
BWTSP: Black and white traveling salesman problem
CATSPP: Constrained asymmetric traveling salesman path problem
CBTSP: Colored balanced traveling salesman problem
CBnTSP: Colored bottleneck traveling salesman problem
CluVRP: Clustered vehicle routing problem
CCCTSP: Cumulative capacitated colored traveling salesman problem
CCVRP: Cumulative capacitated vehicle routing problem
CTSP: Colored traveling salesman problem
CTSP-d: Clustered traveling salesman problem with d-relaxed priority rule
CVRP: Capacitated vehicle routing problem
CVRPTW: Capacitated vehicle routing problem with time windows
DCVRP: Distance constrained capacitated vehicle routing problem
GCTSP: General colored traveling salesmen problem
k-TSP: K-traveling salesman problem
1-PDTSP: One-commodity pickup-and-delivery traveling salesman problem
m-PDTSP: Multi-commodity pickup-and-delivery traveling salesman problem
m1-PDTSP: Multi-commodity one-to-one pickup-and-delivery traveling salesman problem
MLP: Minimum latency problem
MSCTSP: Maximum scattered colored traveling salesman problem
MTRP: Multiple traveling repairman problem
MTRPD: Multiple traveling repairman problem with distance constraints
mTSP: Multiple traveling salesmen problem
OCMTSP: Open close multiple traveling salesman problem
OVRP: Open vehicle routing problem
PCTSP: Precedence-constrained colored traveling salesman problem
PDPTW: Pickup-and-delivery problem with time windows
PDTSP: Pickup-and-delivery traveling salesman problem
PDTSPF: Pickup-and-delivery traveling salesman problem with FIFO loading
PDTSPL: Pickup-and-delivery traveling salesman problem with LIFO loading
PTSP: Homogeneous probability traveling salesman problem
RCTVRP: Risk-constrained cash-in-transit vehicle routing problem
RCTVRPTW: Risk-constrained cash-in-transit vehicle routing with time windows
SoftCluVRP: Soft-clustered vehicle routing problem
SOP: Sequential ordering problem
STTSP: Steiner traveling salesman problem
TRP: Traveling repairman problem
TSPDL: Traveling salesman problem with draft limits
TSPPD: Traveling salesman problem with pickups and deliveries
TSPTW: Traveling salesman problem with time windows
VRPB: Vehicle routing problem with backhauls
VRPBTW: Vehicle routing problem with backhauls and time windows
VRPMPD: Vehicle routing problem with mixed pickup and delivery
VRPMPDTW: Vehicle routing problem with mixed pickup and delivery and time windows
VRPSPD: Vehicle routing problem with simultaneous pickup and delivery
VRPSPDTW: Vehicle routing problem with simultaneous pickup-delivery and time windows
Extensive testing on benchmark instances from the literature has shown that LKH-3 is effective. Best known solutions are often obtained, and in some cases, new best solutions are found. Instances and best solutions obtained by LKH-3 may be downloaded by clicking on the problem types above. Unpack a downloaded file, file_name.tgz, by executing
tar xvfz file_name.tgz
Run scripts are provided for Unix/Linux.
A list of scientific applications of LKH may be seen here.
Installation
LKH-3 has been implemented in the programming language C. The software is entirely written in ANSI C and portable across a number of computer platforms and C compilers.
The code can be downloaded here: LKH-3.0.13.tgz (gzipped tar file, approximately 2 MB).
On a Unix/Linux machine execute the following commands:
tar xvfz LKH-3.0.13.tgz
cd LKH-3.0.13
make
An executable file called LKH will now be available in the directory LKH-3.0.13.
A stand-alone executable for Windows machines may be downloaded here. A Visual Studio 2022 project is available here.
The code is distributed for academic and non-commercial use. The author reserves all rights to the code.
CHANGES IN VERSION LKH-3.0.13:
Added code for solving
the maximum scattered colored traveling salesman problem (MSCTSP),
the precedence-constrained colored traveling salesman problem (PCTSP), and
the constrained asymmetric traveling salesman path problem (CATSPP).
CHANGES IN VERSION LKH-3.0.12:
Added code for solving
the general colored traveling salesman problem (GCTSP) and
the capacitated colored traveling salesman problem (CCCTSP).
CHANGES IN VERSION LKH-3.0.11:
Added code for solving
the clustered vehicle routing problem (CluVRP) and
the
soft-clustered vehicle routing problem (SoftCluVRP).
CHANGES IN VERSION LKH-3.0.10:
Added code for solving
the bounded multiple traveling salesman problem (BMTSP),
the colored balanced traveling salesman problem (CBTSP),
the colored bottleneck traveling salesman problem (CBnTSP),
the homogeneous probability traveling salesman problem (PTSP), and
the tlustered traveling salesman problem with d-relaxed priority rule (CTSP-d).
New keyword:
PROBABILITY
CHANGES IN VERSION LKH-3.0.9:
Added code for solving the k-traveling salesman problem (kTSP).
New keyword:
K
CHANGES IN VERSION LKH-3.0.8:
Tours may now be recombined by Xavier Clarist's recombination (CLARIST).
CLARIST recombination is used by giving the following specification in the parameter file
RECOMBINATION = CLARIST
CHANGES IN LKH-3.0.7:
Added code for solving the asymmetric distance constrained vehicle routing problem (ADCVRP).
CHANGES IN LKH-3.0.6:
Added code for solving the Steiner traveling saleman problem (STTSP).
New keyword:
REQUIRED_NODES_SECTION
CHANGES IN LKH-3.0.5:
Added code for solving the open close multiple traveling saleman problem (OCMTSP).
New keyword:
EXTERNAL_SALESMEN
CHANGES IN LKH-3.0.4:
Added code for solving the colored traveling saleman problem (CTSP). The node coloring is described in a
CTSP_SET_SECTION
New initial tour algorithm: CTSP
Added code for solving the minimum latency problem (MLP).
CHANGES IN LKH-3.0.3:
Candidate sets may now be created by means of POPMUSIC by giving the following specification in the parameter file for LKH:
CANDIDATE_SET_TYPE = POPMUSIC
The value of the parameter MAX_CANDIDATES is used to trim the candidate set. There are, however, some other POPMUSIC related parameters. If not specified, they will take their default values. These parameters are:
POPMUSIC_SAMPLE_SIZE = <int>
Sample size.
Default: 10POPMUSIC_SOLUTIONS = <int>
Number of solutions to generate.
Default: 50POPMUSIC_MAX_NEIGHBORS = <int>
Maximum number of nearest neighbors used as candidates in iterated 3-opt for
POPMUSIC.
Default: 5POPMUSIC_TRIALS = <int>
Number of trials used in iterated 3-opt for POPMUSIC. If the value is zero, the number of trials is the size of the subpath to be optimized.
Default: 1POPMUSIC_INITIAL_TOUR = { YES | NO }
Specifies whether the first generated POPMUSIC tour is used as initial tour for Lin-Kernighan.
Default: NO
CHANGES IN LKH-3.0.2:
Tours may now be recombined by GPX2 (Generalized Partition Crossover 2) instead of IPT (Iterative Partial Transcription).
GPX2 is used by giving the following specification in the parameter file:
RECOMBINATION = GPX2
The possible settings are:
RECOMBINATION = { IPT | GPX2 }
IPT is default.
CHANGES IN LKH-3.0.1:
Added code for solving the traveling saleman problem with draft limits (TSPDL).
NEW IN LKH-3:
New parameter keywords:
BWTSP = <integer> <integer> [ <integer> ]
New initial tour algorithms:
DEPOT = <integer>
MAKESPAN = { YES | NO }
MTSP_MIN_SIZE = <integer>
MTSP_MAX_SIZE = <integer>
MTSP_OBJECTIVE = [ MINMAX | MINMAX_SIZE | MINSUM ]
MTSP_SOLUTION_FILE = <string>
SINTEF_SOLUTION_FILE = <string>
SALESMEN = <integer>
SCALE = <integer>
SPECIAL
VEHICLES = <integer>
CVRPR
New move types:
MTSP
SOP
3 SPECIAL
5 SPECIAL
New TSPLIB format keywords:
The specification part:
DISTANCE : <real>
New edge weight types:
GRID_SIZE : <real>
RISK_THRESHOLD : <integer>
SALESMEN : <integer>
SCALE : <integer>
SERVICE_TIME : <integer>
VEHICLES : <integer>
EXACT_2D
EXACT_3D
FLOOR_2D
FLOOR_3D
TOR_2D
TOR_3D
The data part:
BACKHAUL_SECTION
PICKUP_AND_DELIVERY_SECTION
SERVICE_TIME_SECTION
TIME_WINDOW_SECTION