Title
Heuristics for a vehicle routing problem with information collection in wireless networks
Date Issued
01 April 2020
Access level
open access
Resource Type
journal article
Author(s)
Instituto de Matemática y Ciencias Afines
Instituto de Matemática y Ciencias Afines
Publisher(s)
Springer
Abstract
We consider a wireless network where a given set of stations is continuously generating information. A single vehicle, located at a base station, is available to collect the information via wireless transfer. The wireless transfer vehicle routing problem (WTVRP) is to decide which stations should be visited in the vehicle route, how long shall the vehicle stay in each station, and how much information shall be transferred from the nearby stations to the vehicle during each stay. The goal is to collect the maximum amount of information during a time period after which the vehicle returns to the base station. The WTVRP is NP-hard. Although it can be solved to optimality for small size instances, one needs to rely on good heuristic schemes to obtain good solutions for large size instances. In this work, we consider a mathematical formulation based on the vehicle visits. Several heuristics strategies are proposed, most of them based on the mathematical model. These strategies include constructive and improvement heuristics. Computational experiments show that a strategy that combines a combinatorial greedy heuristic to design a initial vehicle route, improved by a fix-and-optimize heuristic to provide a local optimum, followed by an exchange heuristic, affords good solutions within reasonable amount of running time.
Start page
187
End page
217
Volume
26
Issue
2
Language
English
OCDE Knowledge area
Matemáticas puras
Ingeniería del transporte
Ingeniería de sistemas y comunicaciones
Subjects
Scopus EID
2-s2.0-85074759646
Source
Journal of Heuristics
ISSN of the container
13811231
Sponsor(s)
This research was supported by the Fundação para a Ciência e a Tecnologia (FCT), through the research program PESSOA 2018 - Project FCT/5141/13/4/2018/S and through Project UID/MAT/04106/2019 (A. Agra). It was also supported by Campus France through the research program PESSOA 2018 - Project N 40821YH (R. Figueiredo) and by the Fondo Nacional de Desarrollo Científico, Tecnológico y de Innovación Tecnológica (FONDECYT), with a PhD Grant (L. Flores-Luyo).
Sources of information:
Directorio de Producción Científica
Scopus