An Exact Algorithm for the Green Vehicle Routing Problem

Juho Andelmin, Enrico Bartolini

Research output: Contribution to journalArticleScientificpeer-review

79 Citations (Scopus)


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


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


Dive into the research topics of 'An Exact Algorithm for the Green Vehicle Routing Problem'. Together they form a unique fingerprint.

Cite this