论文标题
定向启动问题与时间浪费和更新延迟
Orienteering problem with time-windows and updating delay
论文作者
论文摘要
定向式问题与时间窗口和延迟（\ optiwind）是在线定向问题的变体。一系列请求出现在各个位置，而车辆在领土内移动以服务。每个请求都有一个时间窗口，可以在此窗口中供应其重要性。连续的请求之间也有最小延迟$ t $。目的是找到一条最大化所提供请求权重总和的车辆的路径。我们进一步假设每个时间窗口的长度等于区域的直径。我们研究了$ n $请求的一组实例的最佳性能和竞争比率。我们为$ t $至少获得直径的一半，$ t $的小值或$ n $的小值的一半分辨率，以及在其余情况下的部分结果。
The Orienteering Problem with Time Window and Delay (\OPTiWinD) is a variant of the online orienteering problem. A series of requests appear in various locations while a vehicle moves within the territory to serve them. Each request has a time window during which it can be served and a weight which describes its importance. There is also a minimum delay $T$ between successive requests. The objective is to find a path for the vehicles that maximises the sum of the weights of the requests served. We further assume that the length of each time window is equal to the diameter of the territory. We study the optimal performance and competitive ratio for the set of instances with $n$ requests. We obtain complete resolution for $T$ at least half of the diameter, small values of $T$ or small values of $n$, as well as partial results in the remaining cases.
