Constraint Programming & Metaheuristic Approach For Electric Vehicle Routing Problem With Time Windows: A Case Study From Company In Xuan Loc

Abstract

The surge in electric vehicle adoption necessitates advanced logistics solutions, particularly for optimizing vehicle routes and schedules. This study addresses the Electric Vehicle Routing Problem with Time Windows, focusing on a logistics company in Xuan Loc, Vietnam. The research problem involves developing efficient routing algorithms that consider the unique constraints of electric vehicles, such as limited battery capacity and recharging needs, alongside traditional logistics constraints like vehicle load and delivery time windows. We employed a hybrid optimization approach combining constraint programming and a Genetic Algorithm. Constraint programming was used to model and solve complex logical and temporal constraints, while the Genetic Algorithm was utilized to explore and refine potential solutions. Data from the logistics company, including customer locations, demand sizes, delivery time windows, and charging station locations, were used to evaluate our approach. This study addresses the electric vehicle routing problem with time windows by comparing two optimization techniques: Genetic Algorithms and Constraint Programming. The primary goal is to determine the most efficient routes for electric vehicles to deliver goods while considering constraints such as vehicle capacity, battery life, and customer time windows. The methodology involves creating an initial population of potential solutions, evaluating them based on their fitness, and iteratively improving these solutions through crossover and mutation processes in GA. Compared to CP, GA demonstrates significant improvements in computational efficiency by reducing the time required to reach near-optimal solutions, thereby facilitating quicker decision making in logistics operations. This computational advantage of GA over CP is crucial in dynamic environments where timely routing decisions are essential. The results highlight that GA not only optimizes route planning but also contributes to operational efficiency, economic benefits, and environmental impact, making it a viable approach for sustainable logistics practices.