Highlights We tackle the green vehicle routing problem – Green VRP. The Green VRP has duration and renewable fuel consumption constraints. We propose a simple yet effective route-first, split-second hybrid heuristic. We introduce a novel mechanism to split giant tours into Green VRP solutions. We report state-of-the-art results on standard instances from the literature.

    Abstract The green vehicle routing problem (Green VRP) is an extension of the VRP in which routes are performed using alternative fuel vehicles (AFVs). AFVs have limited tank capacity, so routes may visit alternative fuel stations (AFSs) en-route. We propose a simple yet effective two-phase heuristic to tackle the Green VRP. In the first phase our heuristic builds a pool of routes via a set of randomized route-first cluster-second heuristics with an optimal AFSs insertion procedure. In the second phase our approach assembles a Green VRP solution by solving a set partitioning formulation over the columns (routes) stored in the pool. To test our approach, we performed experiments on a set of 52 instances from the literature. The results show that our heuristic is competitive with state-of-the-art methods. Our heuristic unveiled 8 new best-known solutions, matched another 40, and delivered solutions with an average gap of 0.14% for the 4 remaining instances.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    A multi-space sampling heuristic for the green vehicle routing problem


    Contributors:


    Publication date :

    2015-09-17


    Size :

    16 pages




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English





    A Simulated Annealing Heuristic for the Green Vehicle Routing Problem

    Yasin, Moch / Yu, Vincent F. | Springer Verlag | 2013


    A tabu search heuristic for the multi-depot vehicle routing problem

    Renaud, Jacques / Laporte, Gilbert / Boctor, Fayez F. | TIBKAT | 1994


    Reoptimization Heuristic for the Capacitated Vehicle Routing Problem

    Rodrigo Linfati / John Willmer Escobar | DOAJ | 2018

    Free access

    A Green Vehicle Routing Problem

    Erdoğan, Sevgi | Online Contents | 2012