论文标题
受约束的后时间旅行计划在P中
Constrained Backward Time Travel Planning is in P
论文作者
论文摘要
我们考虑通过动态图建模的运输网络，并介绍了旅行代理在任何节点上使用向后的时间旅行（BTT）设备的可能性，以便在恢复旅行之前及时返回（在某种程度上，并以某种适当的费用）。我们专注于动态线图。更详细地，我们提出了确切的算法来计算对BTT成本的限制或可以及时的限制的旅行计划，同时最大程度地减少了旅行延迟（即，在多项式时间内到达瞬间和开始时的时间差）。我们研究了BTT设备定价政策对考虑旅行延迟和成本的计划的计算过程的影响，并提供了必要的属性，这些定价策略应满足以使这些计划的影响。最后，当成本函数是身份时，我们为无约束的问题提供了最佳的在线算法。
We consider transportation networks that are modeled by dynamic graphs, and introduce the possibility for traveling agents to use Backward Time-Travel (BTT) devices at any node to go back in time (to some extent, and with some appropriate fee) before resuming their trip. We focus on dynamic line graphs. In more detail, we propose exact algorithms to compute travel plans with constraints on the BTT cost or on how far back in time you can go, while minimizing travel delay (that is, the time difference between the arrival instant and the starting instant), in polynomial time. We study the impact of the BTT devices pricing policies on the computation process of those plans considering travel delay and cost, and provide necessary properties that pricing policies should satisfy to enable to compute such plans. Finally, we provide an optimal online algorithm for the unconstrained problem when the cost function is the identity.
