| 失效链接处理 |
|
关于TSP问题的第三代LKH算法 PDF 下载
本站整理下载：
相关截图：
主要内容：
1. Introduction
The Lin-Kernighan-Helsgaun TSP solver, LKH [1, 2], is a state-of-the-art heuristic solver for the
traveling salesman problem. LKH implements a powerful local search heuristic for the TSP based on
the variable depth local search of Lin and Kernighan [3]. LKH has produced optimal solutions for all
solved problems we have been able to obtain; including an 85,900-city instance (at the time of writ-
ing, the largest nontrivial instance solved to optimality). Furthermore, the algorithm has improved
the best known solutions for a series of large-scale instances with unknown optima, among these a
1,904,711-city instance (World TSP).
However, in many practical situations, the TSP has additional constraints such as limited resources,
time windows and precedence constraints. Since the current version of LKH, LKH-2, is highly
customized for the standard TSP and cannot accommodate constraints, its usage is extremely limited
in these situations. Furthermore, solving problems that involve multiple traveling salesmen is not
straightforward.
This is the motivation for extending LKH-2 with facilities handling constraints and multiple traveling
salesmen. The extension, named LKH-3, is currently able to solve the following problem types:
2
ACVRP: Asymmetric capacitated vehicle routing problem
BWTSP: Black and white traveling salesman problem
CCVRP: Cumulative capacitated vehicle routing problem
CVRP: Capacitated vehicle routing problem
CVRPTW: Capacitated vehicle routing problem with time windows
DCVRP: Distance constrained capacitated vehicle routing 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
MTRP: Multiple traveling repairman problem
MTRPD: Multiple traveling repairman problem with distance constraints
mTSP: Multiple traveling salesmen 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
TRP: Traveling repairman problem
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.
The next sections describe the implementation of LKH-3.
|
| Java1234官方群25： | 
|
| Java1234官方群25： | 838462530 |
苏公网安备 32061202001004号
