A fast randomized algorithm for the heterogeneous vehicle routing problem with simultaneous pickup and delivery
type: Item
instance of: scholarly article
title: A fast randomized algorithm for the heterogeneous vehicle routing problem with simultaneous pickup and delivery
zbMATH Open document ID: 1461.68256
author: Napoleão Nepomuceno
author: Ricardo Barboza Saboia
author: Placido Rogerio Pinheiro
published in: Algorithms
publication date: 2020-10-08T00:00:00Z
review text: Summary: In the vehicle routing problem with simultaneous pickup and delivery (VRPSPD), customers demanding both delivery and pickup operations have to be visited once by a single vehicle. In this work, we propose a fast randomized algorithm using a nearest neighbor strategy to tackle an extension of the VRPSPD in which the fleet of vehicles is heterogeneous. This variant is an NP-hard problem, which in practice makes it impossible to be solved to proven optimality for large instances. To evaluate the proposal, we use benchmark instances from the literature and compare our results to those obtained by a state-of-the-art algorithm. Our approach presents very competitive results, not only improving several of the known solutions, but also running in a shorter time.
Mathematics Subject Classification ID: 68W20
Mathematics Subject Classification ID: 90B06
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 7257778
zbMATH Keywords: vehicle routing problem
zbMATH Keywords: greedy algorithms
zbMATH Keywords: randomized algorithms
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.3390/a12080158
OpenAlex ID: W2965566565
cites work: A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service
cites work: A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery
cites work: An ant colony system (ACS) for vehicle routing problem with simultaneous delivery and pickup
cites work: A parallel heuristic for the vehicle routing problem with simultaneous pickup and delivery
cites work: Branch-and-cut with lazy separation for the vehicle routing problem with simultaneous pickup and delivery
cites work: Q5187226
cites work: Traveling salesman should not be greedy: Domination analysis of greedy-type heuristics for the TSP
cites work: When the greedy algorithm fails
DOI: 10.3390/A12080158
description: scientific article; zbMATH DE number 7257778