Itinerary planning with deadline in headway-based bus networks minimizing lateness level

For an urban traveler using headway-based bus services, this paper concerns the itinerary planning problem with deadline under vehicular travel time and transfer waiting time uncertainties. An earliness ratio is proposed to practically specify the travel time budget, which is given by a traveler determined by his / her conservatism level. Both the risk and ambiguity of each uncertain arc travel times are considered (i.e., each arc travel time is depicted by its mean and support). Under this kind of uncertainty, this paper minimizes the lateness level, which is adjusted from the concept “lateness index” proposed by Jaillet et al. [1]. Two modified Dijkstra sub-procedures are integrated in a binary search procedure, leading to an acceptable computation time. By an illustrated example, this paper shows that the optimal itineraries might vary with different time budgets. Thus the optimal travel arrangement is not simply “travel along the optimal itinerary derived from solving the deterministic itinerary planning problem but budget more time”. Moreover, we reach the management insights in this example that an itinerary with less transfer times and with less vehicular travel time perturbations (although with longer travel distance) is more suitable for a conservative traveler.