タイムテーブル最適化におけるハイブリッド・アルゴリズムの構築

时刻表优化中混合算法的构建

• 批准号: 18710127
• 负责人: 宮代 隆平
• 金额: $ 1.79万
• 依托单位: Tokyo University of Agriculture and Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2006
• 资助国家: 日本
• 起止时间: 2006 至 2007
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-18710127/
• 关键词: 組合せ最適化; タイムテーブリング; スケジューリング; アルゴリズム; 数理計画; 応用数学; オペレーションズ・リサーチ; 数理工学; タイムテーブル; 時間割; 情報基礎

本研究課題「タイムテーブル最適化におけるハイブリッド・アルゴリズムの構築」は,タイムテーブル最適化を効率的に解くアルゴリズムの構築を目指すものである.本年度の研究成果は,主に以下の三点である.1.半正定値計画法を利用したタイムテーブル最適化これまで,タイムテーブル最適化に用いられてきたのは主に整数計画法であるが,本研究では線形計画法の拡張である半正定値計画法を利用し,整数計画法では計算時間が多大になってしまう問題に対して高速なアルゴリズムを開発した.2.移動距離最小化がからんだタイムテーブル最適化における高速アルゴリズムタイムテーブル最適化に移動距離最小化の概念がからんだような問題は,通常よりさらに難しくなることが知られている.本研究では,それらのうちある特定のクラスの問題に対して,高速アルゴリズムを開発した.3.ある種のタイムテーブル最適化に適用可能なメタ・ヒューリスティックアルゴリズムある種のタイムテーブル最適化問題は,これまで主に数学の組合せ論の範疇で扱われており,組合せ最適化の観点からは扱われてこなかった.本研究では,この問題に対してメタ・ヒューリスティックの技術を利用したアルゴリズムを開発した.上記の問題はいずれも,従来研究では高速なアルゴリズムが得られていなかった問題であり,本研究で開発したアルゴリズムは非常に有用である.開発したアルゴリズムはいずれも高速に動作し,なおかつ実装が容易であるのも特徴である.

该研究主题是“为时间表优化构建混合算法”，旨在构建有效求解时间表优化的算法。今年的结果主要是以下三个点：1。使用半阳性点式编程的时间表优化，该编程已用于时间表优化，直到现在，当前的研究研究主要用于整数编程，但是在这项研究中，我们已经开发了高速算法的高速算法，这些算法是在Integer编程中引起大量计算时间的高速算法。 2。时间表优化中的快速算法，涉及最小化行进距离。涉及时间表优化和最小化旅行距离的概念的问题比平常更加困难。众所周知，在这项研究中，针对某些类别的问题开发了一种高速算法。3。可以应用于某些类型的时间表优化的元效法算法。到目前为止，某些类型的时间表优化问题主要是在组合数学类别中处理的，并且从组合优化的角度尚未解决。在这项研究中，为此问题开发了一种利用元海疗法技术的算法。以上所有问题是在先前的研究中未获得高速算法的问题，并且本研究中开发的算法非常有用。所有开发的算法都以高速运行，并且易于实现。

项目成果

スポーヅスケジューリング-近年の発展-

体育赛事安排 - 最新动态 -

• 发表时间: 2007
• 作者: Ryuhei Miyashiro;Tomomi Matsui;宮代 隆平
• 通讯作者: 宮代 隆平

巡回トーナメント問題に対するタブーサーチ・アルゴリズム

循环锦标赛问题的禁忌搜索算法

• 发表时间: 2007
• 作者: 住川 裕岳;宮代 隆平;中森 眞理雄
• 通讯作者: 中森 眞理雄

タイムテープリングにおける判定問題について

关于计时录音的判断问题

• 发表时间: 2007
• 作者: H. Sumikawa. R. Miyashiro;M. Nakamori;R. Miyashiro;宮代 隆平
• 通讯作者: 宮代 隆平

Dependent Randomized Rounding to the Home-Away Assignment Problem in Sports Scheduling

体育赛事安排中主客场分配问题的相关随机舍入

• 发表时间: 2006
• 期刊: IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences vol. E89-A(5)
• 作者: Ayami Suzuki;Ryuhei Miyashiro;Akiko Yoshise;Tomomi Matsui
• 通讯作者: Tomomi Matsui

A tabu search algorithm for the traveling tournament problem

旅行锦标赛问题的禁忌搜索算法

• 发表时间: 2007
• 期刊: IPSJ SIG Technical Report 2007-MPS-65
• 作者: H. Sumikawa;R. Miyashiro;M. Nakamori
• 通讯作者: M. Nakamori