A hybrid GRASP+VND heuristic for the two-echelon vehicle routing problem arising in city logistics
type: Item
instance of: scholarly article
title: A hybrid GRASP+VND heuristic for the two-echelon vehicle routing problem arising in city logistics
zbMATH Open document ID: 1407.90071
DOI: 10.1155/2014/517467
author: Zheng-yang Zeng
author: Wei-sheng Xu
author: Zhi-yu Xu
author: Wei-hui Shao
published in: Mathematical Problems in Engineering
publication date: 2019-02-08T00:00:00Z
review text: Summary: The two-echelon vehicle routing problem (2E-VRP) is a variant of the classical vehicle routing problem (VRP) arising in two-level transportation systems such as those encountered in the context of city logistics. In the 2E-VRP, freight from a depot is compulsorily delivered through intermediate depots, named satellites. The first echelons are routes that distribute freight from depot to satellites, and the second are those from satellites to customers. This problem is solved by a hybrid heuristic which is composed of a greedy randomized adaptive search procedure (GRASP) with a route-first cluster-second procedure embedded and a variable neighborhood descent (VND), called GRASP+VND hereafter. Firstly, an extended split algorithm in the GRASP continuously splits randomly generated permutations of all customers and assigns customers to satellites reasonably until a feasible assignment appears, and a complete 2E-VRP feasible solution is obtained by solving the first echelon problem subsequently and, secondly, a VND phase attempts to improve this solution until no more improvements can be found. The process above is iterated until the maximum number of iterations is reached. Computational tests conducted on three sets of benchmark instances from the literature show that our algorithm is both effective and efficient and outperforms the best existing heuristics for the 2E-VRP.
Mathematics Subject Classification ID: 90B06
Mathematics Subject Classification ID: 90C59
zbMATH DE Number: 7016641
Wikidata QID: Q59068131
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1155/2014/517467
OpenAlex ID: W1590882662
cites work: New families of valid inequalities for the two-echelon vehicle routing problem
cites work: An Exact Algorithm for the Two-Echelon Capacitated Vehicle Routing Problem
cites work: An adaptive large neighborhood search heuristic for two-echelon vehicle routing problems arising in city logistics
cites work: Greedy randomized adaptive search procedures
cites work: Handbook of metaheuristics
cites work: Variable neighborhood search
cites work: A hybrid GRASP/VND heuristic for the one-commodity pickup-and-delivery traveling salesman problem
cites work: Efficient GRASP+VND and GRASP+VNS metaheuristics for the traveling repairman problem
cites work: A hybrid GRASP/VND algorithm for two- and three-dimensional bin packing
cites work: Solving the two-echelon location routing problem by a GRASP reinforced by a learning process and path relinking
cites work: A simple and effective evolutionary algorithm for the vehicle routing problem
cites work: A parallel heuristic for the vehicle routing problem with simultaneous pickup and delivery
cites work: A hybrid algorithm for the heterogeneous fleet vehicle routing problem
cites work: An Exchange Heuristic for Routeing Problems with Time Windows
description: scientific article; zbMATH DE number 7016641