(331d) Heuristic Algorithm Utilizing Mixed-Integer Linear Programming to Schedule Electric Vehicles for Reduced Cost and Energy Use

A heuristic algorithm based on Mixed-Integer Linear Programming (MILP) is proposed to obtain economical schedules for routing electric vehicles with multiple depots. Electric vehicles are an opportunity to handle delivery or geographically distributed activities in a sustainable way. However, besides the original problem of routing vehicles, special attention must be given to attributes of these technologies, especially recharging. Assignment and scheduling are not solely to be taken into account, but significant travelling times and costs may arise. The goal is the minimization of total cost and use of energy while performing the most activities possible, which involves keeping travelled distances, and hence environmental impacts low. A novel MILP model is proposed, which is capable of handling several factors that may arise in electric vehicle management problems, including time windows. A heuristic greedy algorithm is developed, which assigns activities one by one to the available electric vehicles’ daily schedules based on the MILP. This two-level approach is tested over medium scale problem instances, proving that computational requirements are acceptable.