A STUDY ON THE DYNAMIC TRAVELING SALESMAN PROBLEM FOR ELECTRIC VEHICLES

Abstract

In recent years, electric vehicles have started to be used frequently in logistics operations, especially in cities, since they cause less damage to the environment compared to conventional vehicles. Instantaneous data from vehicles obtained with the help of the development in vehicle technologies and the progress in information technologies enable to have more efficient and less costly distribution routes. In this study, the Traveling Salesman Problem for electric vehicles has been investigated with the assumption that vehicle speeds can change dynamically during travel, and a Dynamic Programming model has been developed for the addressed problem. Explicit energy consumption calculation is integrated into the model with an energy consumption function consisting of elements such as curb weight, road condition, traction power and driver experience. A Restricted Dynamic Programming – Link Elimination Approach algorithm is proposed for solving large-sized problems. The proposed algorithm has been applied on 90 problems that are frequently studied in the literature, and it has been observed that the proposed algorithm provides better results than the Restricted Dynamic Programming algorithm in 51 of these problems.