Optimizing nonlinear charging times of electric vehicle routing with genetic algorithm

With the rising share of electric vehicles used in the service industry, the optimization of their specific constraints is gaining importance. Lowering energy consumption, time of charging and the strain on the electric grid are just some of the issues that must be tackled, to ensure a cleaner and more efficient industry. This paper presents a Two-Layer Genetic Algorithm (TLGA) for solving the capacitated Multi-Depot Vehicle Routing Problem with Time Windows (MDVRPTW) and Electric Vehicles (EV) with partial nonlinear recharging times (NL) – E-MDVRPTW-NL. Here, the optimization goal is to minimize driving times, number of stops at electric charging stations and time of recharging while taking the nonlinear recharging times into account. This routing problem closes the gap between electric vehicle routing problem research on the one hand and its applications to several problems with numerous real-world constraints of electric vehicles on the other. Next to the definition and the formulation of the E-MDVRPTW-NL, this paper presents the evolutionary method for solving this problem using the Genetic Algorithm (GA), where a novel two-layer genotype with multiple crossover operators is considered. This allows the GA to not only solve the order of the routes but also the visits to electric charging stations and the electric battery recharging times. Various settings of the proposed method are presented, tested and compared to competing meta-heuristics using well-known benchmarks with the addition of charging stations.