Java知识分享网 - 轻松学习从此开始!    

Java知识分享网

Java1234官方群25:java1234官方群17
Java1234官方群25:838462530
        
SpringBoot+SpringSecurity+Vue+ElementPlus权限系统实战课程 震撼发布        

最新Java全栈就业实战课程(免费)

springcloud分布式电商秒杀实战课程

IDEA永久激活

66套java实战课程无套路领取

锋哥开始收Java学员啦!

Python学习路线图

锋哥开始收Java学员啦!
当前位置: 主页 > Java文档 > Java基础相关 >

关于TSP问题的第三代LKH算法 PDF 下载


分享到:
时间:2021-04-27 09:46来源:http://www.java1234.com 作者:转载  侵权举报
关于TSP问题的第三代LKH算法 PDF 下载
失效链接处理
关于TSP问题的第三代LKH算法 PDF 下载


本站整理下载:
提取码:rdol 
 
 
相关截图:
 
主要内容:

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.

 

------分隔线----------------------------

锋哥公众号


锋哥微信


关注公众号
【Java资料站】
回复 666
获取 
66套java
从菜鸡到大神
项目实战课程

锋哥推荐