Formulations and Branch-and-Cut Algorithms for the Generalized Vehicle Routing Problem

Tolga Bektas, Günes Erdogan, Stefan Røpke

    Research output: Contribution to journalJournal articleResearchpeer-review

    953 Downloads (Pure)


    The Generalized Vehicle Routing Problem (GVRP) consists of nding a set of routes for a number of vehicles with limited capacities on a graph with the vertices partitioned into clusters with given demands such that the total cost of travel is minimized and all demands are met. This paper offers four new integer linear programming formulations for the GVRP, two based on multicommodity flow and the other two based on exponential sets of inequalities. Branch-and-cut algorithms are proposed for the latter two. Computational results on a large set of instances are presented.
    Original languageEnglish
    JournalTransportation Science
    Issue number3
    Pages (from-to)299-316
    Publication statusPublished - 2011


    • Branch-and-Cut
    • Integer Programming
    • Generalized Vehicle Routing

    Cite this