Title: A Multi-Space Sampling Heuristic for the Green Vehicle Routing Problem

Speaker: VILLEGAS, Juan G. (Universidad de Antioquia, Colombia)

Abstract:

The global warming phenomenon and other environmental concerns have motivated the use of zero emission vehicles (ZEV) in different transportation operations ranging from postal delivery to grocery distribution. The use of ZEV leads to new optimization problems.  One of these problems is the green vehicle routing problem (Green-VRP): an extension of the well-known vehicle routing problem arising when a fleet of ZEV based at a central depot services the demand of a set of geographically-spread customers.  The particular feature of the Green VRP comes from the limited autonomy of ZEV. Indeed, to assure the feasible completion of trips, alternative fuel stations (AFS) have to be visited en-route in order to refill the tank (or recharge the battery). Additionally, a maximum duration constraint is imposed to the routes of a Green-VRP.

In this work 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 randomized route-first cluster-second heuristic. 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.

Computational experiments, on a set of instances from the literature, show that our heuristic obtains competitive results when compared to state-of-the-art methods including a modified Clarke and Wright savings heuristic, a density-based clustering algorithm, and a hybrid variable neighborhood search/tabu search.

*Coauthors: Jose A. Montoya, Christelle Guéret, Jorge E. Mendoza