Interval Based Constrained Path Optimization in Time-Dependent Road Networks

In the realm of urban mobility, the increasing availability of large-scale transportation data has paved the way for advanced and sophisticated routing queries. Among these, the time-dependent constrained path optimization (TD-CPO) problem optimizes route selection based on user-defined preferences such as safety, navigability, road width, or scenic value, while adhering to specific constraints (travel time). This problem has broad applications in urban navigation, helping commuters and travelers find paths that align with their individual needs. However, solving the TD-CPO problem is challenging, as it can be reduced to the NP-hard arc-orienteering problem. Existing state-of-the-art research has predominantly focused on solving the TD-CPO problem for a single departure time. However, this approach is often too limiting for users who prefer to depart within a time range. Extending these methods to handle a range of departure times typically results in redundant computations and inefficiencies. This paper proposes an extension of the TD-CPO query, called interval TD-CPO, that accounts for a range of departure times. This extension aims to identify the most suitable path and a corresponding departure time that maximizes the user’s preference metric within the given constraints. Experimental results on real-world graphs show that our algorithm delivers comparable solution quality in just 5 s, a major improvement over the 120 s needed by state-of-the-art methods adapted for interval TD-CPO.