Wir befassen uns erneut mit dem bekannten Online-Reiseverkäuferproblem (OLTSP) und seiner Erweiterung, dem Online-Dial-a-Ride-Problem (OLDARP). Ein Server, der an einem bestimmten Ursprung in einem metrischen Raum startet, muss Online-Anfragen bedienen und zum Ursprung zurückkehren, sodass die Abschlusszeit minimiert wird. Der SmartStart-Algorithmus, eingeführt von Ascheuer et al., integriert einen Wartenansatz in einen online planbasierten Algorithmus und erreicht die optimale obere Grenze von 2 für das OLTSP und das OLDARP, wenn jeder Zeitplan optimal ist. Die Verwendung der Christofides-Heuristik zur Annäherung an jeden Zeitplan führt zu der derzeit besten oberen Grenze von (7 + sqrt(13)) / 4, ungefähr 2.6514, in polynomieller Zeit. In dieser Studie untersuchen wir, wie ein Online-Algorithmus mit Vorhersagen, ein kürzlich populäres Framework (d.h. die sogenannten lernergänzten Algorithmen), verwendet werden kann, um das beste Wettbewerbsverhältnis in polynomieller Zeit zu verbessern. Insbesondere entwickeln wir eine Warte-Strategie mit Online-Vorhersagen, wobei jede von ihnen nur eine binäre Entscheidungsfindung für jeden Zeitplan in einer gesamten Route darstellt, anstatt zu Beginn ein ganzes Set von Anfragen vorherzusagen (d.h. Offline-Vorhersagen). Das heißt, es ist nicht notwendig, die Anzahl der Anforderungen im Voraus zu kennen. Der vorgeschlagene online planbasierte Algorithmus kann eine 1.1514 * lambda + 1.5-Konsistenz und 1.5 + 1.5 / (2.3028 * lambda - 1)-Robustheit in polynomieller Zeit erreichen, wobei lambda im Intervall (1/theta, 1] liegt und theta auf (1 + sqrt(13)) / 2, ungefähr 2.3028, gesetzt ist. Die beste Konsistenz neigt dazu, sich 2 zu nähern, wenn lambda nahe bei 1/theta liegt. Inzwischen zeigen wir, dass keine online planbasierten Algorithmen ein Wettbewerbsverhältnis von weniger als 2 erreichen können, selbst mit perfekten Online-Vorhersagen.
Liang et al. (Thu,) haben diese Frage untersucht.