论文标题
在时间相关图中的路径排名上
On path ranking in time-dependent graphs
论文作者
论文摘要
在本文中，我们研究了时间依赖图的属性，称为路径排名不变性。从广义上讲，如果时间依赖图是路径排名不变的路径（W.R.T.旅行时间）独立于开始时间，则是路径排名。在本文中，我们表明，如果图是路径排名不变的，那么可以通过求解适当定义（和更简单）时间独立的路由问题来获得大量时间相关的车辆路由问题的解决方案。我们还展示了如何通过求解线性程序来检查该属性。如果检查失败，则可以使用线性程序的解决方案来确定紧密的下限。为了评估这些见解的价值，下限已嵌入列举方案中。 \ textit {旅行推销员问题}和\ textit {乡村邮政邮政问题}的计算结果表明，新发现允许超越最先进的算法。
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 \textit{Travelling Salesman Problem} and the \textit{Rural Postman Problem} show that the new findings allow to outperform state-of-the-art algorithms.
