LKH-3

Version 3.0.10 (June 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

CBTSP: Colored balanced traveling salesman problem

CBnTSP: Colored bottleneck 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

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

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 windowsExtensive 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 executingtar xvfz

file_name.tgzRun scripts are provided for Unix/Linux.

InstallationLKH-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.10.tgz (gzipped tar file, approximately 2 MB).

On a Unix/Linux machine execute the following commands:tar xvfz LKH-3.0.10.tgz

cd LKH-3.0.10

makeAn executable file called LKH will now be available in the directory LKH-3.0.10.

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.10:Added code for solving the colored balanced traveling salesman problem (CBTSP), the colored bottleneck traveling salesman problem (CBnTSP), and the homogeneous probability traveling salesman problem (PTSP).

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_3DThe data part:

BACKHAUL_SECTION

PICKUP_AND_DELIVERY_SECTION

SERVICE_TIME_SECTION

TIME_WINDOW_SECTION

[home]