Adaptive robust electric vehicle routing under energy consumption uncertainty

Abstract

Electric vehicles (EVs) have been highly favoured as a mode of transportation in recent years. EVs offer numerous benefits over traditional fuel-based vehicles, particularly in terms of the environmental impact. Although electric vehicles offer several advantages, there are certain restrictions that limit their usage. One of the significant issues is the uncertainty in their driving range. The driving range of EVs is closely related to their energy consumption, which is highly affected by exogenous and endogenous factors. Since those factors are unpredictable, uncertainty in EVs’ energy consumption should be considered for efficient operation. This paper proposes a two-stage adaptive robust optimization framework for the electric vehicle routing problem. The objective is to minimize the worst-case energy consumption while guaranteeing that services are delivered at the appointed time windows without battery level deficiency. We postulate that EVs can be recharged on route, and the charging amount can be adjusted depending on the circumstances. A column-and-constraint generation based heuristic algorithm, which is coupled with variable neighbourhood search and alternating direction algorithm, is proposed to solve the resulting model. The computational results show the economic efficiency and robustness of the proposed model, and that there is a tradeoff between the total required energy and the risk of failing to satisfy all customers’ demand.