On the practical viability of competitive algorithms for the homing online traveling salesperson problem: empirical evaluation and practical recommendations

Abstract

The Homing Online Traveling Salesperson Problem (H-OLTSP) models a dynamic routing scenario in which a server must respond to requests revealed over time while always returning to a fixed origin. Here, the server represents a moving agent, such as a robot or vehicle, that travels through the metric space to serve requests. Although competitive algorithms such as Plan At Home (PAH) and Greedily Traveling between Requests (GTR) have been proposed under competitive analysis, their behavior under practical conditions remains largely untested. Competitive analysis reflects worst-case performance but may not capture how these algorithms perform in realistic environments where response speed and solution efficiency are critical.

This thesis bridges that gap by empirically evaluating PAH and GTR through simulation. Each algorithm is implemented with multiple scheduling strategies and tested under controlled experimental settings that vary the number of requests and the distribution of their release times. The evaluation focuses on two core aspects: responsiveness, which reflects how quickly the server reacts to incoming requests, and efficiency, which reflects how effectively the algorithm solves each H-OLTSP instance.

The study compares GTR and PAH directly and evaluates how each performs when combined with different scheduling algorithms under varying conditions. The results provide practical insight into the trade-offs between response speed and instance-solving efficiency, revealing performance differences that are not visible through theoretical analysis alone. This work offers a grounded perspective on the real-world suitability of competitive online algorithms. It guides their application in dynamic routing applications that require timely decisions and low completion time.