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.130
URN: urn:nbn:de:0030-drops-27559
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2010/2755/
Go to the corresponding OASIcs Volume Portal

Lannez, Sébastien ; Artigues, Christian ; Damay, Jean ; Gendreau, Michel

Column Generation Heuristic for a Rich Arc Routing Problem

pdf-format:
11.pdf (1 MB)

Abstract

In this paper we address a real world optimisation
problem, the Rail Track Inspection Scheduling Problem (RTISP).
This problem consists of scheduling network inspection tasks.
The objective is to minimise total deadhead distance.
A mixed integer formulation of the problem
is presented. A column generation based algorithm is proposed
to solve this rich arc routing problem. Its performance
is analysed by benchmarking a real world dataset from the French national
railway company (SNCF). The efficiency of the algorithm is compared
to an enhanced greedy algorithm. Its ability to schedule one
year of inspection tasks on a sparse graph with thousand nodes, arcs
and edges is assessed.

BibTeX - Entry

@InProceedings{lannez_et_al:OASIcs:2010:2755,
  author =	{S{\'e}bastien Lannez and Christian Artigues and Jean Damay and Michel Gendreau},
  title =	{{Column Generation Heuristic for a Rich Arc Routing Problem}},
  booktitle =	{10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10)},
  pages =	{130--141},
  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/2755},
  URN =		{urn:nbn:de:0030-drops-27559},
  doi =		{10.4230/OASIcs.ATMOS.2010.130},
  annote =	{Keywords: arc routing, column generation, heuristic, railtrack maintenance}
}

Keywords: arc routing, column generation, heuristic, railtrack maintenance
Collection: 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10)
Issue Date: 2010
Date of publication: 01.09.2010

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI