LKH-3
Version 3.0.9 (June 2023)


VRP image

 

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

POPMUSIC_SOLUTIONS = <int> 
Number of solutions to generate.
Default: 50

POPMUSIC_MAX_NEIGHBORS = <int>
Maximum number of nearest neighbors used as candidates in iterated 3-opt for
POPMUSIC.
Default: 5

POPMUSIC_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: 1

POPMUSIC_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> ]
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>

New initial tour algorithms:

CVRPR
MTSP
SOP

New move types:

3 SPECIAL
5 SPECIAL

New TSPLIB format keywords:

The specification part:

DISTANCE : <real>
GRID_SIZE : <real>
RISK_THRESHOLD : <integer>
SALESMEN : <integer>
SCALE : <integer>
SERVICE_TIME : <integer>
VEHICLES : <integer>

New edge weight types:

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

[home]