Heterogeneous fleet management for one-way electric carsharing system with optional orders, vehicle relocation and on-demand recharging

As a part of the trend of shared transport, carsharing has received increasing attention over the recent years. We address the operation management problem of a heterogeneous electric vehicle fleet in a one-way carsharing system with relocation and on-demand recharging activities, to fulfill the optional rental orders that are known in advance. We present a mixed-integer linear programming formulation for the problem with the objective to maximize the overall profit, which can be solved to the optimum for instances with up to 50 rental orders by CPLEX within an hour. To deal with large-scale problems, we apply the Dantzig-Wolfe decomposition technique and propose an approach which hybridizes the ant colony optimization (ACO) metaheuristics into the column generation framework to quickly solve the pricing subproblems. The evaluation experiments using randomly generated instances of different scales have shown that, the proposed hybrid approach is both efficient and efficacious: (1) the gap between the solutions by the hybrid approach and the optimal solutions is below 5% in average for small instances; (2) for large instances with over 100 rental orders, the overall performance of the hybrid approach is significantly better than those of CPLEX and ACO metaheuristics, with rather short time consumption. Furthermore, a case study is conducted based on practical transportation data of Beijing, using the net profit and order fulfillment rate as performance criteria. Insightful findings have been revealed by sensitivity analysis.