r"""
LKH (Lin-Kernighan-Helsgaun)
"""
# Copyright (c) 2024 Thinklab@SJTU
# ML4CO-Kit is licensed under Mulan PSL v2.
# You can use this software according to the terms and conditions of the Mulan PSL v2.
# You may obtain a copy of Mulan PSL v2 at:
# http://license.coscl.org.cn/MulanPSL2
# THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OF ANY KIND,
# EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO NON-INFRINGEMENT,
# MERCHANTABILITY OR FIT FOR A PARTICULAR PURPOSE.
# See the Mulan PSL v2 for more details.
import os
import sys
import shutil
from ml4co_kit.optimizer.base import OptimizerBase
from ml4co_kit.task.base import TaskBase, TASK_TYPE
from ml4co_kit.solver.base import SolverBase, SOLVER_TYPE
from ml4co_kit.utils.file_utils import download, pull_file_from_huggingface
from .lib.lkh.tsp_lkh import tsp_lkh
from .lib.lkh.atsp_lkh import atsp_lkh
from .lib.lkh.cvrp_lkh import cvrp_lkh
[docs]class LKHSolver(SolverBase):
"""
LKH: http://akira.ruc.dk/~keld/research/LKH-3/LKH-3.0.14.tgz
PyLKH: https://github.com/ben-hudson/pylkh
Current Version: LKH-3.0.14
Last Update: 2026-05-26
@article{
helsgaun2017extension,
title={An extension of the Lin-Kernighan-Helsgaun TSP solver for constrained traveling salesman and vehicle routing problems},
author={Helsgaun, Keld},
journal={Roskilde: Roskilde University},
volume={12},
pages={966--980},
year={2017}
}
"""
def __init__(
self,
lkh_scale: int = 1e6,
lkh_max_trials: int = 500,
lkh_runs: int = 1,
lkh_seed: int = 1234,
lkh_special: bool = False,
optimizer: OptimizerBase = None,
):
# Super Initialization
super(LKHSolver, self).__init__(
solver_type=SOLVER_TYPE.LKH, optimizer=optimizer
)
# Initialize Attributes
self.lkh_scale = lkh_scale
self.lkh_max_trials = lkh_max_trials
self.lkh_runs = lkh_runs
self.lkh_seed = lkh_seed
self.lkh_special = lkh_special
# LKH Path Check
self.lkh_store_path = os.path.join(sys.prefix, "bin")
self.lkh_bin_path = os.path.join(self.lkh_store_path, "LKH")
if os.path.exists(self.lkh_bin_path) is False:
self.install()
def _solve(self, task_data: TaskBase):
"""Solve the task data using LKH solver."""
if task_data.task_type == TASK_TYPE.TSP:
return tsp_lkh(
task_data=task_data,
lkh_scale=self.lkh_scale,
lkh_max_trials=self.lkh_max_trials,
lkh_path=self.lkh_bin_path,
lkh_runs=self.lkh_runs,
lkh_seed=self.lkh_seed,
lkh_special=self.lkh_special
)
elif task_data.task_type == TASK_TYPE.ATSP:
return atsp_lkh(
task_data=task_data,
lkh_scale=self.lkh_scale,
lkh_max_trials=self.lkh_max_trials,
lkh_path=self.lkh_bin_path,
lkh_runs=self.lkh_runs,
lkh_seed=self.lkh_seed,
lkh_special=self.lkh_special
)
elif task_data.task_type == TASK_TYPE.CVRP:
return cvrp_lkh(
task_data=task_data,
lkh_scale=self.lkh_scale,
lkh_max_trials=self.lkh_max_trials,
lkh_path=self.lkh_bin_path,
lkh_runs=self.lkh_runs,
lkh_seed=self.lkh_seed,
lkh_special=self.lkh_special
)
else:
raise ValueError(
f"Solver {self.solver_type} is not supported for {task_data.task_type}."
)
[docs] def install(self):
"""Install LKH solver."""
# Step1: Download LKH
try:
# from huggingface
pull_file_from_huggingface(
repo_id="ML4CO/ML4CO-Kit",
repo_type="dataset",
filename="routing/lkh/LKH-3.0.14.tgz",
save_path="LKH-3.0.14.tgz"
)
except:
# from original website
lkh_url = "http://akira.ruc.dk/~keld/research/LKH-3/LKH-3.0.14.tgz"
download(file_path="LKH-3.0.14.tgz", url=lkh_url)
# Step2: tar .tgz file
os.system("tar xvfz LKH-3.0.14.tgz")
# Step3: build LKH
ori_dir = os.getcwd()
os.chdir("LKH-3.0.14")
os.system("make")
# Step4: move LKH to the bin dir
os.system(f"cp LKH {self.lkh_store_path}")
os.chdir(ori_dir)
# Step5: clean up
os.remove("LKH-3.0.14.tgz")
shutil.rmtree("LKH-3.0.14")
print(f"LKH Solver installed successfully at {self.lkh_bin_path}.")