LKH is an implementation of the Lin-Kernighan traveling salesman heuristic.

The code is distributed for research use. The author reserves all rights to 
the code.


INSTRUCTIONS FOR INSTALLATION: (Version 3.0.13 - November 2024)
-----------------------------

The software is available in gzipped tar format:

	LKH-3.0.13.tgz	(approximately 2.3 MB)

Download the software and execute the following UNIX 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.

To test the installation, run the program by typing ./LKH pr2392.par and 
then press return. The program should now solve a TSP instance with 2392 nodes.

To test the installation on an mTSP problem, type ./LKH whizzkids96.par and
then press return.

The default tour representation uses a two-level tree. 
To use a three-level tree representation instead, compile the source code 
with the compiler option

	-DTHREE_LEVEL_TREE

Just edit the first line in SRC/Makefile and execute the commands

	make clean
	make

CHANGES IN VERSION 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 3.0.12:
-------------------------

Added code for solving 
the general colored traveling salesman problem (GCTSP) andi
the capacitated colored traveling salesman problem (CCCTSP).

CHANGES IN VERSION 3.0.11:
-------------------------

Added code for solving the clustered vehicle routing problem (CluVRP).

CHANGES IN VERSION 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 traveling salesman problem with d-relaxed priority rule (TSP-d).

New keyword: PROBABILITY.

CHANGES IN VERSION 3.0.9:
-------------------------

Added code for solving the k-traveling salesman problem (kTSP).
New keyword: K.


CHANGES IN VERSION 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 salesman problem (STTSP). 
New keyword

    REQUIRED_NODES_SECTION


CHANGES IN LKH-3.0.5:
---------------------

Added code for solving the open close multiple traveling salesman 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 solving the minimum latency problem (MLP).


CHANGES IN VERSION 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 VERSION 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 VERSION 3.0.1:
-------------------------

    New problem type: TSPDL (traveling salesman with draft limits)


NEW IN VERSION 3.0:
-------------------
	
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_RESULT_FILE = <string>
	SINTEF_RESULT_FILE = <string>
	SALESMEN = <integer>
	SCALE = <integer>
	VEHICLES : <integer>

	New initial tour algorithms:
	CVRPR
	MTSP
	SOP 

New TSPLIB format keywords:

The specification part: 

	CAPACITY : <integer>
	DEMAND_DIMENSION : <integer>
	DISTANCE : <real>
	GRID_SIZE : <real>
	RISK_THRESHOLD : <integer>
	SALESMEN : <integer>
	SCALE : <integer> 
	SERVICE_TIME_SECTION 
	VEHICLES : <integer>

	New edge weight types:	
	EXACT_2D
	EXACT_3D 
	FLOOR_2D
	FLOOR_3D
	TOR_2D
	TOR_3D 

The data part: 

	BACKHAUL_SECTION
	DEMAND_SECTION
	DEPOT_SECTION
	PICKUP_AND_DELIVERY_SECTION
	TIME_WINDOW_SECTION