A multi-space sampling heuristic for the green vehicle routing problem
Autor: | Alejandro Montoya, Christelle Gueret, Jorge E. Mendoza, Juan G. Villegas |
---|---|
Rok vydání: | 2016 |
Předmět: |
050210 logistics & transportation
Engineering Low emission vehicle Mathematical optimization 021103 operations research business.industry Heuristic 05 social sciences 0211 other engineering and technologies Sampling (statistics) Transportation 02 engineering and technology Management Science and Operations Research Alternative fuel vehicle Set (abstract data type) 0502 economics and business Automotive Engineering Vehicle routing problem Routing (electronic design automation) business Heuristics Civil and Structural Engineering |
Zdroj: | Transportation Research Part C: Emerging Technologies. 70:113-128 |
ISSN: | 0968-090X |
Popis: | 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. |
Databáze: | OpenAIRE |
Externí odkaz: |