Electric vehicle scheduling based on stochastic trip time and energy consumption

The vehicle scheduling problem (VSP) is profound in public transit planning. Especially electric VSP (EVSP) occupies a hot topic, as electric vehicles have enjoyed a fast-expanding market share in the bus market in recent years. It used to be solved regardless of the dreadful variability of traffic by setting the fixed trip times and further deterministic energy consumption, then the robustness of resulting schedules is compromised. Therefore, EVSP based on stochastic trip time and energy consumption is studied. We propose a probabilistic model for EVSP based on the probability density function (PDF) of trip time to minimize the fleet size and operating cost and maximize on-time performance. For modeling, we define the time compatibility and energy compatibility of trips by PDF. Based on the time compatibility, the lower bound of the fleet size is derived. As energy compatibility is a non-inherent attribute of trips, we next develop an adaptive large neighborhood search (ALNS) heuristic for EVSP. Experiments demonstrate that ALNS may considerably surpass the large neighborhood search algorithm for solving EVSP, and the probabilistic model may lead to more robust schedules without increasing fleet size.