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

Traffic congestion significantly increases CO2 (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 CO2 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 CO2 emissions optimization (TD-VRSP-CO2) 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-CO2. Computational experiments on 30 small-sized instances arid 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 CO2 emissions and fuel consumption. (C) 2016 Elsevier Ltd. All rights reserved.