A genetic algorithm with exact dynamic programming for the green vehicle routing scheduling problem
Abstract Traffic congestion significantly increases CO 2 (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 2 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 2 emissions optimization (TD VRSP CO 2 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 2 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 2 emissions and fuel consumption.