The electric on-demand bus routing problem with partial charging and nonlinear functions

Electric vehicle routing problems (EVRPs) with recharging policy consider the limited range of electric vehicles and thus include intermediate visits to charging stations (CSs). In general, minimizing the resultant charging costs such as charging duration or charging amount are also part of the objective of EVRP. Accordingly, EVRPs have received considerable attention over the past years. Nevertheless, this type of problems in the domain of passenger transportation, a VRP variant, has been rarely studied in the literature, especially with time windows, a realistic nonlinear charging function or partial charging policy. Hence this research extends the existing work on EVRP to an On-Demand Bus Routing Problem (ODBRP) which transports passengers with bus station assignment (BSA). The resultant problem is the EODBRP. Specifically, each passenger can have more than one stations to board or alight, and they are assigned to the ones with the smallest increase in the total user ride time (URT). In EODBRP, frequent intermediate visits to CSs are considered. Moreover, nonlinear charging functions are in use and partial charging strategy is applied. To solve the EODBRP, a greedy insertion method with ‘charging first, routing second’ strategy is developed, followed by a large neighborhood search (LNS) which consists of local search (LS) operators to further improve the solution quality. Experimental data were generated by a realistic instance generator based on a real city map, and the corresponding results show that the proposed heuristic algorithm performs well in solving the EODBRP. Finally, sensitivity analyses with divergent parameters such as the temporal distributions of passengers and bus ranges may provide practical guidance