Real-time Approximate Routing for Smart Transit Systems

摘要: The advent of ride-hailing platforms such as Lyft and Uber has revolutionized urban mobility in the past decade. Given their increasingly important role today's society, recent years have seen growing interest integrating these services with mass transit options, order to leverage on-demand flexible nature former, sustainability cost-effectiveness latter. Our work explores a set operational questions that are critical success any integrated marketplace: trip requests, ability utilize services, which mass-transit routes should agency operate? How frequently it operate each route? And how can trips be used both help connect passengers routes, also cover not efficiently served by transit? We study under model Mobility-on-Demand provider (the platform ) control vehicle fleet comprising single-occupancy high-capacity vehicles (e.g., cars buses, respectively). is faced number requests fill during short time window, service via different options : dispatch car transport passenger from source destination; use for first last legs trip, travel bus between; or more complicated multiple legs. rewards matching costs operating line (i.e., route associated frequency), goal determine optimal lines (given fixed budget opening lines), well assignment utilizing lines, maximize total reward. refer this Real-Time Line Planning Problem (RLpp). demonstrate computational limits RLpp showing no constant-factor approximation possible if we relax either one two assumptions: (i) access pre-specified feasible (ii) bus-to-bus transfers. These assumptions practically motivated common literature, but our formally necessity.