.png){kind=icon}
返回
Designing granular solution methods for routing problems with time windows
.png){kind=icon}
OA
AI
DOI：10.1016/j.ejor.2017.04.059.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
The use of granular neighborhoods is one way to improve the run-time of local-search-based metaheuristics for combinatorial optimization problems without compromising solution quality. So-called sparsification methods are applied to restrict the neighborhoods to include only elements which are likely to be part of high-quality solutions. The goal of this work is to provide insights about the design of effective and efficient granular solution methods for routing problems with time windows. In extensive numerical experiments with a granular tabu search (GTS) for the vehicle-routing problem with time windows (VRPTW), we find that sparsification methods using reduced-cost values based on the solution of a linear relaxation of the original problem outperform standard sparsification methods. Furthermore, including additional depot arcs into the restricted arc set (beyond those selected by the sparsification method) improves solution quality. The same is true for dynamically inserting into the restricted arc set (i) the arcs involved in the best move selected in each iteration, and (ii) the arcs of the current best-known solution. Moreover, for small restricted arc sets, guaranteeing a minimum number of incoming and outgoing arcs per vertex is beneficial. Finally, dynamically altering the size of the restricted arc set can be used to successfully diversify and intensify the search, which has a significant positive effect on solution quality. The usefulness of the gained insights about the design of granular solution methods is demonstrated by the performance of the final configuration of our GTS for VRPTW, which obtains state-of-the-art results and reaches an outstanding computational efficiency. (C) 2017 Elsevier B.V. All rights reserved.
Keyword:
Metaheuristics
Granular neighborhoods
Vehicle routing
Time windows
Local search
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
6
论文数:
2.2W
被引数:
6.4W
机构
引用论文
Mid-term and long-term prediction of carbon emissions in Jiangsu Province based on PCA-STIRPAT improved GA-BP.png)
2021 2nd International Conference on Intelligent Computing and Human-Computer Interaction (ICHCI)
2021 2nd International Conference on Intelligent Computing and Human-Computer Interaction (ICHCI)IF0
PREAI
分享收藏Arc-Guided Evolutionary Algorithm for the Vehicle Routing Problem with Time Windows带时间窗车辆路径问题的弧形引导进化算法
PREAI
分享收藏A Randomized Granular Tabu Search heuristic for the split delivery vehicle routing problem用于拆分交付车辆路径问题的随机粒度禁忌搜索启发式方法
PREAI
分享收藏
查看更多内容