.png){kind=icon}
返回
On path ranking in time-dependent graphs
.png){kind=icon}
OA
AI
DOI：10.1016/j.cor.2021.105446.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
In this paper we study a property of time-dependent graphs, dubbed path ranking invariance. Broadly speaking, a time-dependent graph is path ranking invariant if the ordering of its paths (w.r.t. travel time) is independent of the start time. In this paper we show that, if a graph is path ranking invariant, the solution of a large class of time-dependent vehicle routing problems can be obtained by solving suitably defined (and simpler) time-independent routing problems. We also show how this property can be checked by solving a linear program. If the check fails, the solution of the linear program can be used to determine a tight lower bound. In order to assess the value of these insights, the lower bounds have been embedded into an enumerative scheme. Computational results on the time-dependent versions of the Travelling Salesman Problem and the Rural Postman Problem show that the new findings enable to outperform state-of-the-art algorithms.
Keyword:
Time-dependent routing
Path ranking invariance
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
C
IF:
4.3
论文数:
6.5K
被引数:
1.8W
机构
引用论文
.png){kind=icon}
分享收藏An integer programming approach for the time-dependent traveling salesman problem with time windowsOAAI
OAAI分享收藏分享收藏Analysis and Branch-and-Cut Algorithm for the Time-Dependent Travelling Salesman Problem时间相关旅行商问题的分析和分支割算法
PREAI
分享收藏
查看更多内容