引入空间局部性信息，显著提升在线路由问题的求解效率
On the Power of Spatial Locality on Online Routing Problems
- 基于服务器当前位置预测未来请求的分布范围，提供前瞻性信息
- 在任意度量空间下，小范围局部性即可改善竞争比
- 适用于物流、机器人等实时调度场景，尤其适合有预判能力的应用
我们研究了两类基础在线路由问题——旅行商（TSP）和叫车接送（DARP）的在线版本，这两类问题在物流与机器人领域有广泛应用。在线版本要求服务器（销售人员/车辆/机器人）实时响应度量空间中逐个出现的请求。受现实应用（如Uber/Lyft）启发，我们提出「空间局部性」模型：预先告知新请求将在服务器当前位置的一定距离范围内释放。针对 $k\≥ 1$ 台服务器的情况，我们研究该先验信息对改进竞争比的作用，发现即便在任意度量空间下，微小的空间局部性也能有效提升算法性能，优于未考虑局部性的已有结果。
原文摘要 · Abstract (English)
We consider the online versions of two fundamental routing problems, traveling salesman (TSP) and dial-a-ride (DARP), which have a variety of relevant applications in logistics and robotics. The online versions of these problems concern with efficiently serving a sequence of requests presented in a real-time on-line fashion located at points of a metric space by servers (salesmen/vehicles/robots). In this paper, motivated from real-world applications, such as Uber/Lyft rides, where some limited knowledge is available on the future requests, we propose the {\em spatial locality} model that provides in advance the distance within which new request(s) will be released from the current position of server(s). We study the usefulness of this advanced information on achieving the improved competitive ratios for both the problems with $k\geq 1$ servers, compared to the competitive results established in the literature without such spatial locality consideration. We show that small locality is indeed useful in obtaining improved competitive ratios irrespective of the metric space.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。