An Exact Algorithm for the Green Vehicle Routing Problem

Research output: Contribution to journalArticleScientificpeer-review


Research units

  • RWTH Aachen University


We propose an exact algorithm for solving the green vehicle routing problem (G-VRP). The G-VRP models the optimal routing of an alternative fuel vehicle fleet to serve a set of geographically scattered customers. Vehicles’ fuel autonomy and possible refueling stops en route are explicitly modeled and maximum duration constraints are imposed on each vehicle route. We model the G-VRP as a set partitioning problem in which columns represent feasible routes corresponding to simple circuits in a multigraph. Each node in the multigraph represents one customer and each arc between two customers represents a nondominated path through a set of refueling stations visited by a vehicle when traveling directly between the two customers. We strengthen the set partitioning formulation by adding valid inequalities including k-path cuts and describe a method for separating them. We provide computational results on benchmark instances showing that the algorithm can optimally solve instances with up to ∼110 customers.


Original languageEnglish
Pages (from-to)1288-1303
Issue number4
Publication statusPublished - 6 Jul 2017
MoE publication typeA1 Journal article-refereed

    Research areas

  • Vehicle Routing, column generation, k-path cuts, green logistics

ID: 10521906