Online TSP and Online Dial-a-Ride with Predictions
研究带预测的在线旅行商问题和在线叫车问题，设计算法在预测准确时提升性能，否则保持理论保证，改进了不同设置下的最佳已知结果。
We study online routing problems with predictions, inspired by recent exciting results emerged from the area of learning-augmented algorithms. A learning-augmented online algorithm, which incorporates predictions into a black-box manner to outperform existing algorithms if the predictions are accurate while otherwise maintaining theoretical guarantees, is a popular framework for overcoming pessimistic worst-case competitive analysis. In this paper, we particularly investigate the classical online traveling salesman problem (OLTSP) and online dial-a-ride problem (OLDARP), where future requests are augmented with predictions. Unlike the prediction models in other previous studies, each actual request in the OLTSP and OLDARP is associated with its arrival time and position, which, as imagined, leads to a more complicated situation. Our main result is to study different prediction models and design algorithms to improve the best-known results in the different settings. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Funding: This work was supported by National Science Council [Grants NSTC110-2221-E-007-106-MY3, NSTC111-2221-E-007-052-MY3].