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. The online appendix is available at https://doi.org/10.1287/trsc.2016.0734 .


    Zugriff

    Zugriff über TIB

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    An Exact Algorithm for the Green Vehicle Routing Problem


    Erschienen in:

    Transportation science ; 51 , 4 ; 1288-1303


    Erscheinungsdatum :

    2017




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Print


    Sprache :

    Englisch



    Klassifikation :

    Lokalklassifikation TIB:    770/1935/7000
    BKL:    55.80 / 55.80 Verkehrswesen, Transportwesen: Allgemeines



    An Exact Algorithm for the Green Vehicle Routing Problem

    Andelmin, Juho / Bartolini, Enrico | British Library Online Contents | 2017


    An Exact Algorithm for the Vehicle Routing Problem with Backhauls

    Toth, P. / Vigo, D. | British Library Online Contents | 1997



    A Green Vehicle Routing Problem

    Erdoğan, Sevgi | Online Contents | 2012


    Exact Solution of the Vehicle Routing Problem

    Toth, Paolo / Vigo, Daniele | Springer Verlag | 1998