Exact and Heuristic Algorithms for Rapid and Station Arrival-Time Guaranteed Bus Transportation via Lane Reservation

This paper addresses a new lane reservation problem called bus lane reservation problem (BLRP). The focus of the problem is on optimally selecting lanes to be reserved from an existing transport network and designing reserved lane-based bus paths, such that the rapid and station arrival-time guaranteed bus transit can be ensured, thereby achieving rapid and reliable bus transportation. However, once lanes are reserved, negative impact, such as an increase in travel time on adjacent non-reserved lanes may be caused. For this problem, an improved integer linear program is first formulated to minimize such negative impact. As the existing commercial solvers, e.g., CPLEX, can only solve small-size problems, we develop an exact enhanced cut-and-solve algorithm and an improved kernel search heuristic for solving medium- and large-size problems. Results of extensive numerical experiments confirm the effectiveness and efficiency of the proposed algorithms. In addition, a bi-objective robust BRLP is investigated to study the tradeoff between the negative impact of reserved lanes and the robustness of solution against the uncertainties in the link travel time and the bus dwell time.