The Hybrid Electric Vehicle - Traveling Salesman Problem

The reduction in carbon dioxide levels by using hybrid electric vehicles is a currently ongoing endeavor. Although this development is quite advanced for hybrid electric passenger cars, small transporters and trucks are far behind. We try to address this challenge by introducing a new optimization problem that describes the delivery of goods with a hybrid electric vehicle to a set of customer locations. The Hybrid Electric Vehicle - Traveling Salesman Problem extends the well-known Traveling Salesman Problem by adding different modes of operation for the vehicle, causing different costs and driving times for each arc within a delivery network. As the use of different modes of operation immensely increases the complexity of the problem, we present a heuristic solution approach, based mainly on a Tabu Search, to solve this optimization problem. Additionally, we provide a set of realistic benchmark instances based on real-world delivery tours to test and evaluate our solution approach. We also implemented a mathematical problem formulation and are able to solve small instances with the IBM ILOG CPLEX Optimization Studio, which allows us to prove the quality of the solutions, provided by our heuristic.