The Shortest Path Problem with Time Windows and Linear Waiting Costs
研究了带等待成本的最短路径问题，提出两种新模型将原非线性整数规划转化为已有算法可解的形式，并通过计算比较了它们的效率。
This paper considers the shortest path problem with waiting costs (SPWC) as an extension to the shortest path problem with time windows. The problem consists of finding the minimum cost path in a network, where cost and time are two independent quantities associated with a path. Path feasibility is constrained by time windows at each node and a linear cost penalty is imposed for each unit of time spent waiting along the path. Starting from a known, nonlinear, integer programming formulation, we propose two alternative formulations for which algorithms already exist. First, we indicate how to transform the SPWC into a shortest path problem with time windows and linear node costs. Second, we prove that the SPWC can also be formulated as a two-resource generalized shortest path problem with resource constraints. Computational results used to compare these alternative formulations are presented.