Algorithms for time-dependent bicriteria shortest path problems
Algorithms for time-dependent bicriteria shortest path problems
复制标题
DOI：
10.1016/j.disopt.2006.05.006
复制
发表时间：
2006-09
期刊：
影响因子：
--
通讯作者：
H. Hamacher;Stefan Ruzika;S. Tjandra
中科院分区：
文献类型：
--
作者：
H. Hamacher;Stefan Ruzika;S. Tjandra
在本文中，我们以两种方式概括了经典的最短路径问题。我们考虑两个目标函数和时间相关数据。由此产生的问题称为时间相关双标准最短路径问题 (TdBiSP)，它有几个有趣的实际应用，但在文献中并未引起太多关注。在回顾相关文献后，我们开发了一种用于非负数据 TdBiSP 的新算法。数值测试表明，与文献中现有算法相比，我们的算法具有优越性。此外，我们还讨论了具有负传播时间和成本的 TdBiSP 算法。
In this paper we generalize the classical shortest path problem in two ways. We consider two objective functions and time-dependent data. The resulting problem, called the time-dependent bicriteria shortest path problem (TdBiSP), has several interesting practical applications, but has not gained much attention in the literature. After reviewing relevant literature we develop a new algorithm for the TdBiSP with non-negative data. Numerical tests show the superiority of our algorithm compared with an existing algorithm in the literature. Furthermore, we discuss algorithms for the TdBiSP with negative travel times and costs.