A Dynamic Discretization Discovery Algorithm for the Minimum Duration Time-Dependent Shortest Path Problem
A Dynamic Discretization Discovery Algorithm for the Minimum Duration Time-Dependent Shortest Path Problem
复制标题
DOI：
10.1007/978-3-319-93031-2_21
复制
发表时间：
2018-06
期刊：
影响因子：
--
通讯作者：
E. He;N. Boland;G. Nemhauser;M. Savelsbergh
中科院分区：
文献类型：
--
作者：
E. He;N. Boland;G. Nemhauser;M. Savelsbergh
本文给出了一个求解具有分段线性弧旅行时间函数的最小持续时间相关最短路问题的精确算法。该算法迭代地改进时间扩展的网络模型，该模型允许计算下限和上限，直到在有限次数的迭代中获得最优解。
We present an exact algorithm for the Minimum Duration Time-Dependent Shortest Path Problem with piecewise linear arc travel time functions. The algorithm iteratively refines a time-expanded network model, which allows for the computation of a lower and an upper bound, until - in a finite number of iterations - an optimal solution is obtained.