.png){kind=icon}
返回
A branch-and-price algorithm for the Minimum Latency Problem
.png){kind=icon}
OA
AI
DOI：10.1016/j.cor.2018.01.016.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
This paper deals with the Minimum Latency Problem (MLP), a variant of the well-known Traveling Salesman Problem in which the objective is to minimize the sum of waiting times of customers. This problem arises in many applications where customer satisfaction is more important than the total time spent by the server. This paper presents a novel branch-and-price algorithm for MLP that strongly relies on new features for the ng-path relaxation, namely: (1) a new labeling algorithm with an enhanced dominance rule named multiple partial label dominance; (2) a generalized definition of ng-sets in terms of arcs, instead of nodes; and (3) a strategy for decreasing ng-set sizes when those sets are being dynamically chosen. Also, other elements of efficient exact algorithms for vehicle routing problems are incorporated into our method, such as reduced cost fixing, dual stabilization, route enumeration and strong branching. Computational experiments over TSPLIB instances are reported, showing that several instances not solved by the current state-of-the-art method can now be solved. (C) 2018 Elsevier Ltd. All rights reserved.
Keyword:
Minimum latency
ng-paths
Branch-and-price
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
C
IF:
4.3
论文数:
6.5K
被引数:
1.8W
机构
引用论文
An NMR crystallography DFT-D approach to analyse the role of intermolecular hydrogen bonding and π–π interactions in driving cocrystallisation of indomethacin and nicotinamide.png)
CrystEngComm
CrystEngCommIF0
PREAI
分享收藏
查看更多内容