Using an enhanced artificial bee colony algorithm to solve the Electric Vehicle Routing Problem

Abstract

With the deterioration of the environment, people start replacing fuel vehicles by electric vehicles in logistic activities. Electric vehicle routing problem is gaining more and more attention from the researchers. This paper introduces the heterogeneous electric vehicle routing problem with time windows, partial charging, and piecewise linear charging functions. The available heterogeneous vehicle types differ in their load capacities, battery sizes, and charging functions. The charging amount is considered to be a decision variable and the charging process is approximated as a piecewise linear function. Unlike the literature, this variant simultaneously considers the following: (1) time windows for the customers, (2) time windows at both recharging stations and the depot, (3) heterogeneous vehicle fleet, (4) partial charging, (5) current-battery-level-dependent recharging time/cost, and (6) a nonconstant charging rate. An enhanced artificial bee colony algorithm is adopted to solve the problem. Several operators for partial charging, time-window infeasibility repairs, for inserting a recharging station, and partial charging amount adjustment are proposed. Numerical studies showed that with the proposed operators, the enhanced artificial bee colony algorithm can outperform CPLEX in terms of both CPU time and solution quality in all the tested instances, and the introduction of the novel operators can improve solution quality.