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

Abstract: The 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 is also part of the objective of the EVRP. Accordingly, the EVRP has received considerable attention over the past years. Nevertheless, this type of problem 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 a partial charging policy. Hence this research extends the existing work on the EVRP to the on-demand bus routing problem (ODBRP) which transports passengers with the bus station assignment (BSA). The resultant problem is the electric ODBRP (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 the EODBRP, frequent intermediate visits to CSs are considered. Moreover, a nonlinear charging function is used and the partial charging strategy is applied. To solve the EODBRP, a greedy insertion method with a '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 are 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