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 .


    Access

    Access via TIB

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    An Exact Algorithm for the Green Vehicle Routing Problem


    Published in:

    Publication date :

    2017




    Type of media :

    Article (Journal)


    Type of material :

    Print


    Language :

    English



    Classification :

    Local classification 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


    A Green Vehicle Routing Problem

    Erdoğan, Sevgi / Miller-Hooks, Elise | Elsevier | 2011