A DECOMPOSITION-BASED ALGORITHM FOR TRAIN TIMETABLING PROBLEM WITH DYNAMIC PASSENGERS' DEMANDS
-
- Matsunaga Ryuya
- Mitsubishi Electric Corporation
-
- Shibata Hideya
- Mitsubishi Electric Corporation
Bibliographic Information
- Other Title
-
- 移動需要に基づく鉄道運行計画決定問題に対する分解アルゴリズム
- イドウ ジュヨウ ニ モトズク テツドウ ウンコウ ケイカク ケッテイ モンダイ ニ タイスル ブンカイ アルゴリズム
Search this article
Abstract
<p>In many current railway systems, trains are operated under the fixed timetable. Dynamic planning of train timetable with demands can make passengers more comfortable. There are many researches for demand-driven train timetabling by solving optimization problem and efforts for practical use have begun for small railway networks. However, it is difficult to plan train timetable on-demand for large scale networks in urban area, because it takes too much time to solve train timetabling problem (TTP). In this paper, we propose an algorithm which aims to solve TTP in O(L) time where LM is number of lines. Our method decomposes the original problem into several single line problems by converting a multiple transfer demand to several ones with no transfer. This makes the problem size small and the computation time short. Also, our method updates the solution iteratively in order to prevent declining the solution quality. We evaluate our method by comparing with a local search method. The result shows that our method can compute the solution more quickly and accurately than local search for large scale networks. On the other hand, the result reveals the problem that the computation time of updating the solution is larger than O(L) and becomes a bottleneck for large scale networks. Future research is hence needed to resolve this task to solve TTP for large scale network in short time.</p>
Journal
-
- Transactions of the Operations Research Society of Japan
-
Transactions of the Operations Research Society of Japan 64 (0), 101-125, 2021
The Operations Research Society of Japan
- Tweet
Details 詳細情報について
-
- CRID
- 1390570574765885952
-
- NII Article ID
- 130008076755
-
- NII Book ID
- AA11998080
-
- ISSN
- 21888280
- 13498940
-
- NDL BIB ID
- 031964958
-
- Text Lang
- ja
-
- Data Source
-
- JaLC
- NDL
- Crossref
- CiNii Articles
-
- Abstract License Flag
- Disallowed