Multi-Depot Electric Vehicle Routing Problem With Half-Open Routes and Rotations: a Mathematical Formulation

Abstract

The electrification spreads all around the world with the goal of global net zero emission, especially in transportation sector. As a natural consequence of this phenomenon, many countries and organizations announce their targets relating to the Electric Vehicles (EVs). Although shifting from fossil-fuel towards EVs is a major step forward, there are other precious actions to be taken, one of which is to integrate EVs into scientific studies along with the routing improvements. To this end, we introduce the Multi-Depot Electric Vehicle Routing Problem with Half-Open Routes and Rotations (MDEVRP-HORR) as an extension of the MDEVRP where the rotation refers to set of all routes assigned to anEV. EVs can be recharged at the depots or at the recharging stations along the route with full recharging strategy. The problem is formulated as a 0-1 mixed integer linear program (MILP) and existing procedures are applied to improve the model. The proposed model relaxes the restriction that the departure depot of the first route and arrival depot of the last route of an EV must be the same. It also avoids from creating dummy nodes for recharging stations and replenishment depots. We conducted experimental studies by using small-sized instances from the recent literature due to problem intractability. Out of 36 instances, results reveal that inclusion of half-open routes leads to a cost reduction for 20 instances. Besides, inclusion of both half-open rotations and half-open routes results in cost reduction for 28 instances.