Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-14257
For citation please use:
Main Title: A Fast Algorithm for Near Cost Optimal Line Plans
Author(s): Bussieck, Michael R.
Lindner, Thomas
Lübbecke, Marco E.
Type: Research Paper
URI: https://depositonce.tu-berlin.de/handle/11303/15484
http://dx.doi.org/10.14279/depositonce-14257
License: http://rightsstatements.org/vocab/InC/1.0/
Abstract: We consider the design of line plans in public transport at a minimal total cost. Both, linear and non-linear integer programming are adequate and intuitive modeling approaches for this problem. We present a heuristic variable fixing procedure which builds on problem knowledge from both techniques. We derive and compare lower bounds from different linearizations in order to assess the quality of our solutions. The involved integer linear programs are strengthened by means of problem specific valid inequalities. Computational results with practical data from the Dutch Railways indicate that our algorithm gives excellent solutions within minutes of computation time.
Subject(s): integer programming
non-linear integer programming
cutting planes
public transport
line planning
Issue Date: 2003
Date Available: 17-Dec-2021
Language Code: en
DDC Class: 510 Mathematik
MSC 2000: 90C10 Integer programming
90C30 Nonlinear programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90B06 Transportation, logistics
Series: Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Series Number: 2003, 43
ISSN: 2197-8085
TU Affiliation(s): Fak. 2 Mathematik und Naturwissenschaften » Inst. Mathematik
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Report-043-2003.pdf
Format: Adobe PDF | Size: 178.54 kB
DownloadShow Preview
Thumbnail
Report-043-2003.ps.gz
Format: Unknown | Size: 95.57 kB
Download

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.