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

    701 Downloads (Pure)

    Abstract

    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
    Volume45
    Issue number3
    Pages (from-to)299-316
    ISSN0041-1655
    DOIs
    Publication statusPublished - 2011

    Keywords

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

    Cite this