A MIP‐based local search method for the railway rescheduling problem
Identifieur interne : 000849 ( Main/Exploration ); précédent : 000848; suivant : 000850A MIP‐based local search method for the railway rescheduling problem
Auteurs : Rodrigo Acuna-Agost [France] ; Philippe Michelon [France] ; Dominique Feillet [France] ; Serigne Gueye [France]Source :
- Networks [ 0028-3045 ] ; 2011-01.
English descriptors
Abstract
For operational and unpredictable reasons, many small incidents occur day after day in rail transportation systems. Most of them have a local impact, but, in some cases, mainly in dense networks, minimal disruptions can spread out through the whole network and affect significantly the train schedules. In this article, we present the railway rescheduling problem as the problem of finding a new schedule of trains after one or several incidents by minimizing some measure of the effect. We investigate the solution of this problem through a mixed‐integer programming (MIP) formulation. Because of the impossibility for solving it exactly just using a standard MIP solver, we propose to limit the search space around the original nondisrupted schedule by hard and soft fixing of integer variables with local‐branching‐type cuts. Different variations of the method are compared to a right‐shift rescheduling policy in two different networks located in France and Chile. The experimental results are also used to study the impact of different objectives on the total delay. © 2010 Wiley Periodicals, Inc. NETWORKS, 2011
Url:
DOI: 10.1002/net.20384
Affiliations:
- France
- Haute-Normandie, Provence-Alpes-Côte d'Azur, Région Normandie
- Avignon, Gardanne, Le Havre
- Université d'Avignon, Université du Havre
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 001411
- to stream Istex, to step Curation: 001411
- to stream Istex, to step Checkpoint: 000136
- to stream Main, to step Merge: 000850
- to stream Main, to step Curation: 000849
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">A MIP‐based local search method for the railway rescheduling problem</title><author><name sortKey="Acuna Gost, Rodrigo" sort="Acuna Gost, Rodrigo" uniqKey="Acuna Gost R" first="Rodrigo" last="Acuna-Agost">Rodrigo Acuna-Agost</name></author><author><name sortKey="Michelon, Philippe" sort="Michelon, Philippe" uniqKey="Michelon P" first="Philippe" last="Michelon">Philippe Michelon</name></author><author><name sortKey="Feillet, Dominique" sort="Feillet, Dominique" uniqKey="Feillet D" first="Dominique" last="Feillet">Dominique Feillet</name></author><author><name sortKey="Gueye, Serigne" sort="Gueye, Serigne" uniqKey="Gueye S" first="Serigne" last="Gueye">Serigne Gueye</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:BA6A03976F1AEFB04BCE1A11E0A707885A586800</idno><date when="2011" year="2011">2011</date><idno type="doi">10.1002/net.20384</idno><idno type="url">https://api.istex.fr/document/BA6A03976F1AEFB04BCE1A11E0A707885A586800/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">001411</idno><idno type="wicri:Area/Istex/Curation">001411</idno><idno type="wicri:Area/Istex/Checkpoint">000136</idno><idno type="wicri:doubleKey">0028-3045:2011:Acuna Gost R:a:mip:based</idno><idno type="wicri:Area/Main/Merge">000850</idno><idno type="wicri:Area/Main/Curation">000849</idno><idno type="wicri:Area/Main/Exploration">000849</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">A MIP‐based local search method for the railway rescheduling problem</title><author><name sortKey="Acuna Gost, Rodrigo" sort="Acuna Gost, Rodrigo" uniqKey="Acuna Gost R" first="Rodrigo" last="Acuna-Agost">Rodrigo Acuna-Agost</name><affiliation wicri:level="4"><country xml:lang="fr">France</country><wicri:regionArea>Université d'Avignon et des Pays de Vaucluse, Laboratoire Informatique d'Avignon, F‐84911 Avignon</wicri:regionArea><placeName><region type="region" nuts="2">Provence-Alpes-Côte d'Azur</region><settlement type="city">Avignon</settlement></placeName><orgName type="university">Université d'Avignon</orgName></affiliation></author><author><name sortKey="Michelon, Philippe" sort="Michelon, Philippe" uniqKey="Michelon P" first="Philippe" last="Michelon">Philippe Michelon</name><affiliation wicri:level="4"><country xml:lang="fr">France</country><wicri:regionArea>Université d'Avignon et des Pays de Vaucluse, Laboratoire Informatique d'Avignon, F‐84911 Avignon</wicri:regionArea><placeName><region type="region" nuts="2">Provence-Alpes-Côte d'Azur</region><settlement type="city">Avignon</settlement></placeName><orgName type="university">Université d'Avignon</orgName></affiliation></author><author><name sortKey="Feillet, Dominique" sort="Feillet, Dominique" uniqKey="Feillet D" first="Dominique" last="Feillet">Dominique Feillet</name><affiliation wicri:level="3"><country xml:lang="fr">France</country><wicri:regionArea>École des Mines de Saint‐Étienne, CMP Georges Charpak, F‐13541 Gardanne</wicri:regionArea><placeName><region type="region" nuts="2">Provence-Alpes-Côte d'Azur</region><settlement type="city">Gardanne</settlement></placeName></affiliation></author><author><name sortKey="Gueye, Serigne" sort="Gueye, Serigne" uniqKey="Gueye S" first="Serigne" last="Gueye">Serigne Gueye</name><affiliation wicri:level="4"><country xml:lang="fr">France</country><wicri:regionArea>Université du Havre, Laboratoire de Mathématiques Appliquées du Havre, F‐76058 Le Havre</wicri:regionArea><placeName><region type="region" nuts="2">Région Normandie</region><region type="old region" nuts="2">Haute-Normandie</region><settlement type="city">Le Havre</settlement></placeName><orgName type="university">Université du Havre</orgName></affiliation></author></analytic><monogr></monogr><series><title level="j">Networks</title><title level="j" type="abbrev">Networks</title><idno type="ISSN">0028-3045</idno><idno type="eISSN">1097-0037</idno><imprint><publisher>Wiley Subscription Services, Inc., A Wiley Company</publisher><pubPlace>Hoboken</pubPlace><date type="published" when="2011-01">2011-01</date><biblScope unit="volume">57</biblScope><biblScope unit="issue">1</biblScope><biblScope unit="page" from="69">69</biblScope><biblScope unit="page" to="86">86</biblScope></imprint><idno type="ISSN">0028-3045</idno></series><idno type="istex">BA6A03976F1AEFB04BCE1A11E0A707885A586800</idno><idno type="DOI">10.1002/net.20384</idno><idno type="ArticleID">NET20384</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0028-3045</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>disruption management</term><term>local branching</term><term>rescheduling</term><term>train timetabling</term></keywords></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">For operational and unpredictable reasons, many small incidents occur day after day in rail transportation systems. Most of them have a local impact, but, in some cases, mainly in dense networks, minimal disruptions can spread out through the whole network and affect significantly the train schedules. In this article, we present the railway rescheduling problem as the problem of finding a new schedule of trains after one or several incidents by minimizing some measure of the effect. We investigate the solution of this problem through a mixed‐integer programming (MIP) formulation. Because of the impossibility for solving it exactly just using a standard MIP solver, we propose to limit the search space around the original nondisrupted schedule by hard and soft fixing of integer variables with local‐branching‐type cuts. Different variations of the method are compared to a right‐shift rescheduling policy in two different networks located in France and Chile. The experimental results are also used to study the impact of different objectives on the total delay. © 2010 Wiley Periodicals, Inc. NETWORKS, 2011</div></front></TEI><affiliations><list><country><li>France</li></country><region><li>Haute-Normandie</li><li>Provence-Alpes-Côte d'Azur</li><li>Région Normandie</li></region><settlement><li>Avignon</li><li>Gardanne</li><li>Le Havre</li></settlement><orgName><li>Université d'Avignon</li><li>Université du Havre</li></orgName></list><tree><country name="France"><region name="Provence-Alpes-Côte d'Azur"><name sortKey="Acuna Gost, Rodrigo" sort="Acuna Gost, Rodrigo" uniqKey="Acuna Gost R" first="Rodrigo" last="Acuna-Agost">Rodrigo Acuna-Agost</name></region><name sortKey="Feillet, Dominique" sort="Feillet, Dominique" uniqKey="Feillet D" first="Dominique" last="Feillet">Dominique Feillet</name><name sortKey="Gueye, Serigne" sort="Gueye, Serigne" uniqKey="Gueye S" first="Serigne" last="Gueye">Serigne Gueye</name><name sortKey="Michelon, Philippe" sort="Michelon, Philippe" uniqKey="Michelon P" first="Philippe" last="Michelon">Philippe Michelon</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/France/explor/LeHavreV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000849 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 000849 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/France
|area= LeHavreV1
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:BA6A03976F1AEFB04BCE1A11E0A707885A586800
|texte= A MIP‐based local search method for the railway rescheduling problem
}}
| This area was generated with Dilib version V0.6.25. |  |