LKH-3
Version 3.0.9 (June 2023)
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
BWTSP: Black and white traveling salesman problem
CCVRP: Cumulative capacitated vehicle routing problem
CTSP: Colored traveling salesman problem
CVRP: Capacitated vehicle routing problem
CVRPTW: Capacitated vehicle routing problem with time windows
DCVRP: Distance constrained capacitated vehicle routing 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
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
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
RCTVRP: Risk-constrained cash-in-transit vehicle routing problem
RCTVRPTW: Risk-constrained cash-in-transit vehicle routing with time windows
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.
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.9.tgz (gzipped tar file, approximately 2 MB).
On a Unix/Linux machine execute the following commands:
tar xvfz LKH-3.0.9.tgz
cd LKH-3.0.9
make
An executable file called LKH will now be available in the directory LKH-3.0.9.
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.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