License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2010.34
URN: urn:nbn:de:0030-drops-27489
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2010/2748/
Dewilde, Thijs ;
Cattrysse, Dirk ;
Coene, Sofie ;
Spieksma, Frits C. R. ;
Vansteenwegen, Pieter
Heuristics for the Traveling Repairman Problem with Profits
Abstract
In the traveling repairman problem with profits, a repairman (also known as the server) visits a subset of nodes in order to collect time-dependent profits. The objective consists of maximizing the total collected revenue. We restrict our study to the case of a single server with nodes located in the Euclidean plane. We investigate properties of this problem, and we derive a mathematical model assuming that the number of visited nodes is known in advance. We describe a tabu search algorithm with multiple neighborhoods, and we test its performance by running it on instances based on TSPLIB. We conclude that the tabu search algorithm finds good-quality solutions fast, even for large instances.
BibTeX - Entry
@InProceedings{dewilde_et_al:OASIcs:2010:2748,
author = {Thijs Dewilde and Dirk Cattrysse and Sofie Coene and Frits C. R. Spieksma and Pieter Vansteenwegen},
title = {{Heuristics for the Traveling Repairman Problem with Profits}},
booktitle = {10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10)},
pages = {34--44},
series = {OpenAccess Series in Informatics (OASIcs)},
ISBN = {978-3-939897-20-0},
ISSN = {2190-6807},
year = {2010},
volume = {14},
editor = {Thomas Erlebach and Marco L{\"u}bbecke},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2010/2748},
URN = {urn:nbn:de:0030-drops-27489},
doi = {10.4230/OASIcs.ATMOS.2010.34},
annote = {Keywords: Traveling Repairman, Profits, Latency, Tabu Search, Relief Efforts}
}
Keywords: |
|
Traveling Repairman, Profits, Latency, Tabu Search, Relief Efforts |
Collection: |
|
10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10) |
Issue Date: |
|
2010 |
Date of publication: |
|
01.09.2010 |