グラフの色分け手法の車両運用問題への適用

• Item type: SIG Technical Reports(1)
• 公開日: 1997-05-15
• タイトル: グラフの色分け手法の車両運用問題への適用
• タイトル / 言語: en
• タイトル: Train Schedule Revision by Graph Coloring Method
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 株式会社東芝研究開発センター
• 著者所属: 株式会社東芝研究開発センター
• 著者所属(英): en
• 著者所属(英): TOSHIBA Corporation, Research and Development Center
• 著者所属(英): en
• 著者所属(英): TOSHIBA Corporation, Research and Development Center
• 著者名: 外山, 春彦; 荒木, 大
• 著者名(英): Haruhiko, Toyama; Dai, Araki
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 予め作成された計画に事故などにより変更が生じる場合がある。このとき、与えられた制約条件を満足するように、かつ、出来るだけ少ない変更で、計画のほかの部分を修正する必要が生じる。我々はこの問題を「リソース再割り当て問題」として定式化し、グラフの色分け手法を適用する方法を考案した。計画修正範囲を出来るだけ少なくすることを、修正範囲を徐々に広げながら探索を行う機構と元の計画を初期解とする近傍探索機構を組み合わせる事で実現した。この方法を「鉄道車両運用計画の修正」に適用し、出来るだけ少ない修正で元の計画に戻すという観点で、人手よりも良い修正計画を短時間に作成できる事を確認した。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We propose a method for schedule revision on resource assignment problem. Some accidents causes some changes in the original schedule. Then, we have to revise the schedule with less changes to satisfy the given constraints. We formulate this problem into Resource Reassignment Problem. For this problem we propose a method using Graph Coloring Method. To revise the schedule with less changes, this system has two mechanisms. The one is a search mechanism widening the schedule revision range gradually, out of which the revised schedule is same as the original one. The other one is a local search mechanism with the original schedule initial data. We apply this method to Train Schedule Revision Problem, and we can get schedules revised with less changes, than that revised manually.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10505667
• 書誌情報: 情報処理学会研究報告数理モデル化と問題解決（MPS）; 巻 1997, 号 41(1997-MPS-013), p. 27-32, 発行日 1997-05-15
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会