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

Yiyong Xiao, Abdullah Konak

Research output: Contribution to journalArticlepeer-review

127 Scopus citations


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 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 CO2 emissions and fuel consumption.

Original languageEnglish (US)
Pages (from-to)1450-1463
Number of pages14
JournalJournal of Cleaner Production
StatePublished - Nov 20 2017

All Science Journal Classification (ASJC) codes

  • Renewable Energy, Sustainability and the Environment
  • General Environmental Science
  • Strategy and Management
  • Industrial and Manufacturing Engineering


Dive into the research topics of 'A genetic algorithm with exact dynamic programming for the green vehicle routing & scheduling problem'. Together they form a unique fingerprint.

Cite this