OASIcs.ATMOS.2010.130.pdf
- Filesize: 1.31 MB
- 12 pages
Document
Column Generation Heuristic for a Rich Arc Routing Problem
Authors
-
Part of:
Volume:
10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10) (ATMOS 2010)
Series: Open Access Series in Informatics (OASIcs)
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
Cite As Get BibTex
Sébastien Lannez, Christian Artigues, Jean Damay, and Michel Gendreau. Column Generation Heuristic for a Rich Arc Routing Problem. In 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10). Open Access Series in Informatics (OASIcs), Volume 14, pp. 130-141, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
https://doi.org/10.4230/OASIcs.ATMOS.2010.130
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.
Subject Classification
Keywords
- arc routing
- column generation
- heuristic
- railtrack maintenance
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads