Electric vehicle scheduling based on stochastic trip time and energy consumption

• Establish a probabilistic model based on the probability density function . • Define the time-compatibility and energy-compatibility of trips. • Derive the lower bound of the fleet size based on the time compatibility. • Develop an adaptive large neighborhood search heuristic algorithm. • Analyse the sensitivity of penalty coefficient, battery capacity, and recharge time. 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.