A multi-mode hybrid electric vehicle routing problem with time windows

The increasing focus on energy consumption and carbon emissions has spurred interest in application of the hybrid electric vehicles (HEVs) for logistics and transportation. This paper proposes a multi-mode hybrid electric vehicle routing problem with time windows (MM-HEVRPTW), in which the HEVs are allowed to operate in combustion, electric, charging, and boost modes. The MM-HEVRPTW simultaneously optimizes the routing decision and operation mode on each road segment while considering constraints such as the battery level and customer time windows. We express the problem as a mixed-integer linear programming model, aiming to minimize the total travel cost on different operation modes. An improved adaptive large neighborhood search (ALNS) algorithm is proposed to address this challenging problem. The algorithm introduces a new customer removal number scheme, two new operators, and combines a local search process and an infeasibility penalization scheme to obtain improved solutions. Computational experiments have been performed on sets of new instances which are generated by modifying existing benchmark instances. Results of different scales of numerical experiments and evaluation of optimization components demonstrate the excellent performance of the proposed ALNS. Furthermore, we investigate the effect of using multi-mode for HEVs and the impact of battery charging and discharging rates on the total travel cost.