A genetic algorithm with exact dynamic programming for the green vehicle routing & scheduling problem

Traffic congestion significantly increases CO₂ (a well-known greenhouse gas) emissions of vehicles in road transportation and causes other environmental costs as well. A road-based delivery company can reduce its CO₂ emissions through operational decisions such as efficient vehicle routes and delivery schedules by considering time-varying traffic congestion in its service area. In this paper, we study the time-dependent vehicle routing & scheduling problem with CO₂ emissions optimization (TD-VRSP-CO₂) and develop an exact dynamic programming algorithm to determine the optimal vehicle schedules for given vehicle routes. A hybrid solution approach that combines a genetic algorithm with the exact dynamic programming procedure (GA-DP) is proposed as an efficient solution approach for the TD-VRSP-CO₂. Computational experiments on 30 small-sized instances and 14 large-sized instances are used to study the efficiency and effectiveness of the proposed hybrid optimization approach with promising results. Contributions of this study can help road-based delivery companies be ready for a low-carbon economy and also help individual vehicle drivers make better vehicle scheduling plans with lower CO₂ emissions and fuel consumption.