Heuristics for the Traveling Repairman Problem with Profits

Dewilde, Thijs; Cattrysse, Dirk; Coene, Sofie; Spieksma, Frits C. R.; Vansteenwegen, Pieter

doi:10.4230/OASIcs.ATMOS.2010.34

Document

Heuristics for the Traveling Repairman Problem with Profits

Authors Thijs Dewilde, Dirk Cattrysse, Sofie Coene, Frits C. R. Spieksma, Pieter Vansteenwegen

Part of: Volume: 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10) (ATMOS 2010)
Part of: Series: Open Access Series in Informatics (OASIcs)
Part of: Conference: Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS)
License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
Publication Date: 2010-09-01

PDF

File

PDF

OASIcs.ATMOS.2010.34.pdf

Filesize: 403 kB
11 pages

Document Identifiers

DOI: 10.4230/OASIcs.ATMOS.2010.34
URN: urn:nbn:de:0030-drops-27489

Subject Classification

Keywords

Traveling Repairman
Profits
Latency
Tabu Search
Relief Efforts

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

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.

Cite As Get BibTex

Thijs Dewilde, Dirk Cattrysse, Sofie Coene, Frits C. R. Spieksma, and Pieter Vansteenwegen. Heuristics for the Traveling Repairman Problem with Profits. In 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10). Open Access Series in Informatics (OASIcs), Volume 14, pp. 34-44, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010) https://doi.org/10.4230/OASIcs.ATMOS.2010.34

Author Details

Thijs Dewilde

Dirk Cattrysse

Sofie Coene

Frits C. R. Spieksma

Pieter Vansteenwegen

Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail