JPH08310399A

JPH08310399A - 運行ダイヤ作成方法

Info

Publication number: JPH08310399A
Application number: JP11953995A
Authority: JP
Inventors: Yasuhiro Sasage; 保浩捧; Hiroaki Sengoku; 浩明仙石; Hiroshi Kawashima; 宏川島; Kenichiro Okada; 健一郎岡田
Original assignee: Hitachi Ltd
Current assignee: Hitachi Ltd
Priority date: 1995-05-18
Filing date: 1995-05-18
Publication date: 1996-11-26

Abstract

(57)【要約】【目的】山ダイヤからの仕業ダイヤ作成において、少な
い労力で最適な仕業ダイヤの生成を可能とする運行ダイ
ヤ作成方法を提供する。【構成】山ダイヤを構成する各斜線に優先度を付与す
る。優先度の列を染色体とし、その染色体の集合である
第１の集団を生成する。第１の集団の各染色体に対して
交叉および突然変異を所定の基準に基づき行なわせ、新
たな染色体からなる第２の集団を生成する。第１の集団
および第２の集団の各染色体に基づき、各斜線に対応す
る各横線を所定の列数に分けて配列し、仕業ダイヤを生
成する。生成された仕業ダイヤを所定の基準に基づき評
価し、評価基準を満たす各仕業ダイヤに対応する染色体
からなる第３の集団を生成する。第３の集団を第１の集
団として上記の処理を繰り返して仕業ダイヤを生成す
る。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、バスや列車等の仕業ダ
イヤを自動生成する方法に関し、特に、バスや列車全体
の運行状況を表す山ダイヤを基に、各乗務員毎あるいは
各車両毎の仕業内容を表す仕業ダイヤを自動生成する運
行ダイヤ作成方法に関する。

【０００２】

【従来の技術】路線バスや列車などを運行する交通輸送
業務においては、所定の営業線区内の全運行状況を一目
で把握するために、通常、山ダイヤと呼ばれる図を用い
る。一方、各乗務員あるいは各車両に対してどの仕業が
どのような順序で割り当てられたかを一目で把握するた
めに、仕業ダイヤと呼ばれる図が用いられる。

【０００３】山ダイヤとは、図４に示すように、縦軸方
向に営業線区内の各停留所を距離（実際的距離または時
間的距離）に基づいて順に配置し、横軸方向に時間軸を
配置してなる座標平面上に、斜線４０１、４０２、…、
４０６で表される各車両（この例ではバス）の運行状況
を記載したものである。また、斜線４０１、４０２、
…、４０６の各斜線は、同一の乗務員および同一の車両
による始点から終点までの１回の運行（１仕業）の様子
を示している。１つの斜線は、始点および終点それぞれ
の位置（停留所名）と出発（または到着）時刻とにより
一意に定まる。各停留所の位置を表す横軸方向の直線と
上記の斜線４０１、４０２、…、４０６との交点は、車
両がその停留所に到着（またはそこを出発）する時刻を
表している。例えば、斜線４０２で表されるバスが「Ｂ
市役所」に到着（またはそこを出発）する時刻は交点４
０７が示す「７時」となる。

【０００４】仕業ダイヤとは、図６に示すように、縦方
向に乗務員を同定する番号または名称（図中の００１お
よび００２）を乗務員の数（ここでは２人）だけ配置
し、横軸方向に時間軸を配置し、斜線４０１、４０２、
…、４０６の各線の始点を左端に、終点を右端に対応さ
せた横線６０１、６０２、…、６０６のような各線分を
斜線の数だけ互いに重ならないように配置したものであ
る。仕業ダイヤは、山ダイヤが表す一日の全運行を各乗
務員に勤務条件等を加味して割り当てたものとみること
ができる。各横線の長さは車両が運行している時間を表
し、左端に始点の停留所名（図では頭文字のみを示す）
およびそこを出発する時刻（図では分表示のみ）が、右
端に終点の停留所名およびそこに到着する時刻が添えら
れる。図６の横線６０１、６０２、…、６０６はそれぞ
れ図４の斜線４０１、４０２、…、４０６に対応してい
る。図６を見ると、乗務員００１は横線６０１、６０
４、６０５、および６０６が表す各仕業をこの順序で担
当し、乗務員００２は横線６０２および６０３が表す各
仕業をこの順序で担当することが分かる。乗務員００１
は横線６０１を見ることにより、自分が担当するこの仕
業が６時３０分Ｂ市役所発、６時５０分Ａ駅着のＢ市役
所発Ａ駅行であることを確認できる。

【０００５】事業者は１つの山ダイヤを作成した後、こ
の山ダイヤ通りに、かつ勤務条件等の諸条件を満足して
バスを運行させることができる最適な仕業ダイヤを１つ
得ようとする。従来はこの一連の作業を人手によって行
っていた。しかし、一般に仕業ダイヤは山ダイヤから一
意に定まらず、複数通りの対応が考えられるので、人手
による方法では効率が悪い。そこで従来、専門家の知識
を蓄積させた知識ベースを利用してこの作業を行なうと
いうＡＩ的手法が提案されている。例えば、特開平３−
１１２７６９などがある。

【０００６】

【発明が解決しようとする課題】１つの山ダイヤから生
成可能な仕業ダイヤは、その山ダイヤを構成するすべて
の斜線の順列・組合せの数と同程度存在する。このた
め、山ダイヤの作成は比較的容易だが、作成された山ダ
イヤに基づき仕業ダイヤを作成する作業は通常困難なも
のとなる。

【０００７】この作業を人手により行なう場合、専門家
の長年の経験に基づく知識と勘に頼る手作業を基本とす
るため、作業者である専門家の経験、技能レベル、癖な
どの個人差により、作業者によって得られる結果が異な
るという問題があった。また、１つの山ダイヤから作成
可能な仕業ダイヤの種類は組合せにより一般に膨大とな
り、さらに勤務条件などが加味されるとダイヤ編成作業
はより複雑となる。このため、条件に適した仕業ダイヤ
を人手によって得るには相当な時間と労力とを要し、そ
の上、必ずしも最適解が得られるとは限らないという問
題があった。

【０００８】また、知識ベースに基づくＡＩ的手法で
は、仕業ダイヤ作成の専門的知識を専門家から引き出
し、これを整理して知識ベース上に蓄積していかなけれ
ばならない。この知識ベース構築の際の知識獲得に膨大
な時間と労力とがかかるという問題があった。

【０００９】本発明は上記問題点に鑑みてなされたもの
であり、仕業ダイヤの作成において、どの作業者が作成
しても一様な結果が得られるようにし、少ない時間と労
力で最適解が得られるようにし、かつ専門家の知識を蓄
積する作業を不要にして、最適な仕業ダイヤの生成を可
能とする運行ダイヤ作成方法を提供することを目的とす
る。

【００１０】

【課題を解決するための手段】本発明は、山ダイヤを構
成する各斜線に優先度を付与し、優先度の並びである１
つの記号列を１つの染色体とみたててこれを１つの仕業
ダイヤに対応させ、山ダイヤから仕業ダイヤを生成する
処理に遺伝的アルゴリズムを適用するというものであ
る。

【００１１】山ダイヤが入力されたシステムは、その山
ダイヤを構成する各斜線のそれぞれに、斜線の個数と同
数の要素からなる順序記号列の各要素を優先度として１
つずつ無作為に対応させて付与する。このように、優先
度を無作為に付与することにより構成される１つの記号
列が１つの染色体となる。優先度を無作為に付与する動
作を所定の回数繰り返すことにより、複数の染色体が生
成される。これらの染色体からなる集合を第１の集団
（初期集団）とする。次に、第１の集団を構成する各染
色体に対して優先度の並べ替えを所定の基準に基づき行
なわせることにより、新たな染色体からなる第２の集団
を生成する。優先度の並べ替えの方法としては、染色体
をある１つまたは複数の境界線で分割してできる部分列
を複数染色体にまたがって互いに入れ替える交叉や、染
色体を構成する優先度のいくつかを無作為に別のものに
変更する突然変異などがあり、これらを所定の割合（突
然変異率）ずつ行わせてもよい。ここまででいわゆる
「世代交代」が行われたことになり、第１の集団を
「親」とすると第２の集団は「子」に相当する。

【００１２】次に、第１の集団および第２の集団を構成
する各染色体に対して、１つの染色体を構成する各優先
度に対応する各斜線をその優先度に基づいて配列するこ
とにより、仕業ダイヤを生成する。この仕業ダイヤの生
成は具体的には、まず各斜線を横線に変換し、その横線
を優先度に基づき所定の列数に分けて配列する割当て処
理によって行なうことができる。この割当て処理は、例
えば、割り当てようとする横線を、既に割り当てられて
いる横線であって各列において最後に割り当てられたも
ののうち、付与されている優先度が最も高い横線に後続
させて行なう。

【００１３】次に、生成された仕業ダイヤのそれぞれを
所定の基準に基づき評価することにより、評価基準を満
たす各仕業ダイヤについては対応する染色体からなる第
３の集団を生成し、評価基準を満たさない各仕業ダイヤ
については対応する染色体を消去する。これを淘汰とい
う。評価の仕方としては、例えば、各乗務員の休憩時間
および車両の回送時間が所定の時間数以上である仕業ダ
イヤのうち、未割り当てとなった各横線の総時間数が小
さいものほど高い評価値を与えて行うことができる。こ
のように評価すれば、評価値の高いものから順に所定の
数だけ染色体を残し、残された染色体で第３の集団を構
成することによって淘汰を実現できる。第３の集団は、
淘汰により「洗練された生き残り」であり、次の選択交
配における「親」となる資格を有する。

【００１４】こうして、第３の集団を構成する各染色体
に対して上記の交叉あるいは突然変異を第１の集団につ
いて行なう場合と同様に行わせ、以上の交叉・突然変
異、割当て、および淘汰を繰り返す遺伝的アルゴリズム
により最適な仕業ダイヤを生成する。

【００１５】

【作用】本発明は、遺伝的アルゴリズムがルールを記述
することなくシステム構築に適用でき、かつ局所的な解
からの脱出が可能であることに着眼し、バスや列車等の
運行状況を表す山ダイヤから乗務員毎の仕業内容を表す
仕業ダイヤを作成する処理にこのアルゴリズムを適用し
たものである。本発明の運行ダイヤ作成方法を用いるこ
とにより、仕業ダイヤの作成が、ダイヤ作成者の築いた
ルールに捕らわれることなく行え、また、評価条件によ
りバスや列車等を運行する事業者それぞれに適した仕業
ダイヤを作成することができる。さらに、ルールの記述
が不要であるためシステム構築が短時間で可能となる。

【００１６】

【実施例】以下、本発明の運行ダイヤ作成方法の一実施
例を示し、本発明を図を用いて実施例によって説明す
る。なお、本実施例は、路線バスの仕業ダイヤを作成す
る場合の例である。

【００１７】図３は、本実施例のハードウェア構成を示
すものである。入力手段３０１は、操作者からの情報を
入力するためのもので、キーボードやポインティングデ
バイス等、公知の入力手段を用いることができる。制御
手段３０２は、本発明の運行ダイヤ作成方法に適用する
遺伝的アルゴリズムを実行する部分であり、ＣＰＵおよ
び一時記憶手段を有し、入力された情報に従って仕業ダ
イヤを作成、または修正する。制御手段３０２には、公
知のワークステーションやパーソナルコンピュータなど
を用いることができる。作業領域３０３は、制御装置３
０２に含まれる一時記憶手段上に割り当てられ、本実施
例における山ダイヤ作成および仕業ダイヤ作成の際の作
業領域として用いられるものである。基礎データファイ
ル３０４は、仕業ダイヤを作成するために入力された情
報を記憶する手段である。基礎データファイル３０４に
は、例えば、勤務条件として入力された勤務時間帯、拘
束時間、食事時間帯、ハンドルタイム等、あるいはバス
の発着場所情報として入力された発着場所名、車庫の有
無、食事の可否等が記憶される。山ダイヤデータファイ
ル３０５は、基礎データファイル３０４の情報を基に制
御手段３０２で作成または修正された山ダイヤのデータ
を記憶する手段である。仕業ダイヤデータファイル３０
６は基礎データファイル３０４および山ダイヤデータフ
ァイル３０５の情報を基に制御装置３０２で作成または
修正された仕業ダイヤのデータを記憶する手段である。
パラメタデータファイル３０７は遺伝的アルゴリズムの
実行に必要なパラメタ情報を記憶・保持する手段であ
る。パラメタデータファイル３０７には、例えば、生成
する世代数、生成する個体数、突然変異発生率等のパラ
メタ情報が記憶・保持される。各ファイル３０４〜３０
７には、例えば磁気ディスク装置や任意の記憶装置を使
うことができる。表示手段３０８は、制御手段３０２に
よって作成された仕業ダイヤを可視的に表示するもの
で、ＣＲＴディスプレイ装置等を用いることができる。
なお、図３には図示しないが、このほかプリンタなどの
出力装置や、その他のコンピュータ周辺機器を設けるこ
とができることは言うまでもない。

【００１８】次に、図１および図２に示す処理の流れに
沿って、本実施例における仕業ダイヤの作成方法を詳細
に説明する。

【００１９】システムの操作者はまず、バスの運行時刻
に関する情報のほか、勤務条件として勤務時間帯、拘束
時間、食事時間帯、ハンドルタイム等を、また、バスの
発着場所情報として発着場所名、車庫の有無、食事の可
否等を入力手段３０１により入力し、これらの情報を基
礎データファイル３０４に記憶させる。制御手段３０２
は操作者の指示および基礎データファイル３０４に記憶
されている入力情報に基づいて山ダイヤを作成し、山ダ
イヤデータファイル３０５に記憶させる（ステップ１０
１）。山ダイヤの作成には公知の手法を利用することが
できる。

【００２０】制御手段３０２は、山ダイヤデータファイ
ル３０５に記憶された山ダイヤのデータに基づき、山ダ
イヤリストを作成する（ステップ１０２）。図５は図４
の山ダイヤから作成された山ダイヤリストである。この
例では、各斜線４０１、４０２、…、４０６が表す各仕
業の内容を、優先度５０２、始点の停留所名および出発
時刻５０３、ならびに終点の停留所名および到着時刻５
０４からなる情報の組として表現し、これを始点の出発
時刻順に並べたものを山ダイヤリストとしている。図４
の斜線４０１、４０２、…、４０６は、それぞれ図５の
リスト上の順番５０１の１、２、…、６に対応する。本
実施例では山ダイヤリストを作成する際、各斜線を始点
の出発時刻順に並べることとしたが、並べ方はこれに限
るものではなく、並べ方に一定の規則があり山ダイヤか
ら山ダイヤリストが一意に定まるものであれば任意でよ
い。

【００２１】作成された山ダイヤリストを基に、遺伝的
アルゴリズム（以下「ＧＡ」と記す）を実行する。ＧＡ
の基本的な考え方については、北野宏明編「遺伝的アル
ゴリズム」（産業図書）第３頁〜第１６頁に記載されて
いる。ＧＡの適用に必要となる概念には、染色体、個体
数、世代数、突然変異発生率、淘汰、評価基準等があ
り、これらの意味や役割については上記公知文献に詳述
されている。

【００２２】本発明では、図４の各斜線４０１、４０
２、…、４０６に無作為に付与された優先度５０２のそ
れぞれを要素遺伝子とし、これらの要素遺伝子を並べた
列を染色体とする。例えば、図７に示す要素遺伝子７０
１、７０２、…、７０６を任意の順に並べてできる７１
１、７１２、…のような列を染色体とする。番号７２１
は山ダイヤリスト上の順番５０１を表す。

【００２３】本実施例では要素遺伝子を１からｎまでの
整数とする。ｎは横線の本数であり、ここでは６とな
る。これらを任意の順で並べた長さｎの数列が染色体と
なる。

【００２４】優先度とは、これから割り当てようとする
横線を、既に割り当てられた横線のうちのどれに後続さ
せて割り当てるかを決定するための情報である。これか
ら割り当てようとする横線は、既に割り当て済みでかつ
それに後続割り当て可能な横線のうち、その優先度が最
高（優先度の値が最小）のものの後に続けて割り当てら
れる。

【００２５】例えば、図７の染色体７１１に基づき図５
の山ダイヤリストを仕業ダイヤに割り当てることを考え
る。なお、ここで用いる番号はリスト上の順番５０１の
番号とする。まず、番号１のデータは先頭の斜線４０１
であり、先行する割当済み横線が存在しないので、横線
６０１に変換して無条件に乗務員００１に割り当てる。
番号２に対応する斜線４０２は先行する横線として横線
６０１が存在するが、乗務員００２が空なので、横線６
０２に変換して無条件に乗務員００２に割り当てる。次
に、番号３に対応する斜線４０３は、先行する２つの横
線６０１および６０２の優先度２と１とを比較し、小さ
い方の１を優先度として持つ横線６０２に後続させて横
線６０３として割り当てられる。さらに、番号４に対応
する斜線４０４は、先行する２つの横線６０１および６
０３の優先度２と５とを比較し、小さい方の２を優先度
として持つ横線６０１に後続させて横線６０４として割
り当てられる。以下、同様の処理を最後の番号６まで繰
り返す。割り当ててできあがった仕業ダイヤは図６のよ
うになる。

【００２６】このように割り当てると、優先度の列であ
る染色体から割当てのパターンが一意に定まる。すなわ
ち、１つの染色体は１つの仕業ダイヤに対応する（ただ
し、異なる複数の染色体が同一の仕業ダイヤに対応する
ことはある）。上述のように、図７の染色体７１１は図
６の仕業ダイヤに対応し、これ以外の仕業ダイヤに対応
することはない。

【００２７】以下、本実施例におけるＧＡの実行を詳細
に説明する。

【００２８】初期集団を発生させる（ステップ１０
３）。ここで、集団とは複数の染色体の集合を意味す
る。初期集団の発生は、要素遺伝子である整数の並び順
をランダムに決定し、それを繰り返すことにより複数の
染色体を発生させて行なう。

【００２９】発生した初期集団に対し選択交配を行なう
（ステップ１０４）。交配の仕方は、本実施例では、数
列をある一点で切断して互いに組み替える単純交叉を適
用するものとする。

【００３０】選択交配により得られた各染色体を山ダイ
ヤリストとみなし、各山ダイヤリストについて割当て処
理を行なう（ステップ１０７）。なお、ステップ１０７
の詳細を図２に示す。

【００３１】取り出された１つの山ダイヤリストから先
頭の横線の優先度を表す要素遺伝子を１つ取り出す（ス
テップ２０２）。例えば、既に横線５０１および線５０
２に対する処理が終わっている場合、山ダイヤリストの
先頭は横線５０３を表す遺伝子となっているので、これ
取り出す。取り出された遺伝子に対応する横線を乗務員
（運転手）に割り当てる（ステップ２０４）。既に割り
当て済みの横線があれば、これから割り当てようとする
横線がそれと重ならないかチェックする（ステップ２０
５）。例えば、横線５０３を割り当てようとすると、仕
業ダイヤ中に既に横線６０１および横線６０２の各横線
が存在し、それらと時間的に重ならないかチェックす
る。この場合は重ならない。これから割り当てようとす
る横線が、割り当てられる運転手の勤務形態に合うかチ
ェックする（ステップ２０６）。これから割り当てよう
とする横線に隣合う横線の優先度を調べ、優先度が最小
の横線にこれを割り当てる（ステップ２０７，２０８，
２０９）。例えば、横線５０１と横線５０２の優先度を
比較すると横線５０２の方が小さいので横線５０２の後
に線４０３を割り当てる。なお、ステップ２０５、２０
６、および２０８のチェックにより割り当てられなかっ
た横線については、未割当領域に格納する（ステップ２
１３）。

【００３２】すべての横線について割当て処理が終了し
たかをチェックし（ステップ２１５）、終了していなけ
れば、山ダイヤリスト中の次の横線を取り出し、以上の
動作を繰り返す。これを山ダイヤリスト中のすべての横
線に対して行ない、ひとつの仕業ダイヤを作成する（ス
テップ２１６）。

【００３３】以上の割当て処理（ステップ１０７）をす
べての山ダイヤリストに対して行なう。

【００３４】作成された仕業ダイヤを評価する（ステッ
プ１１０）。評価基準としては、未割り当てとなった各
横線の総時間数、各運転手の休憩時間、食事時間、回送
時間などが考えられる。これらに基づき評価値を決め
る。なお、評価基準は、システムの操作者が必要に応じ
て変更、追加できることは言うまでもない。それぞれの
仕業ダイヤに評価値が与えられたところで、評価の低い
仕業ダイヤを決められた個数、淘汰により取り除く（ス
テップ１１１）。淘汰とは、評価の低い仕業ダイヤを表
す染色体を次回の交配対象から取り除き、評価の高い仕
業ダイヤを表す染色体だけを次の選択交配における親と
して残すことである。

【００３５】図８は本実施例における選択交配から淘汰
までの様子を示す。初期集団または前回の淘汰で生き残
った集団の中の２つの染色体８０１および８０２を親と
し、境界線８１１を境に互いに交叉させることにより生
成される染色体８０３および８０４を子とする。次に、
各染色体８０１、８０２、８０３、８０４のそれぞれが
対応する仕業ダイヤを評価し、基準を満たす染色体８０
２および８０３を次の選択交配における親８０５および
８０６として残し、基準を満たさない染色体８０１およ
び８０４を取り除く。

【００３６】以上、ステップ１０４からステップ１１１
までの処理を世代数に達するまで繰り返す（ステップ１
１２）。繰返しが終了した段階で残っている染色体が対
応する仕業ダイヤを、求めるべき解とする（ステップ１
１３）。

【００３７】以上説明した実施例によって、最適な仕業
ダイヤを生成することができる。

【００３８】なお、本発明は実施例に限定されず、いろ
いろな応用・変形が可能である。例えば、本実施例はバ
スの運行ダイヤ作成に関するものであるが、これに限る
ものではなく、鉄道、航空、船舶等、あらゆる交通輸送
業務に適用可能である。また、本実施例では仕業ダイヤ
の縦方向に配置する属性を乗務員としたが、これに限る
ものではなく、車両でもよい。さらに、本実施例では選
択交配の際、単純交叉を適用するものとしたが、これに
限るものではなく、予め設定した突然変異率に基づき所
定の割合で突然変異（要素遺伝子のいくつかを無作為に
別のものに変更すること）を起こさせてもよい。

【００３９】

【発明の効果】以上説明したように、仕業ダイヤの生成
に遺伝的アルゴリズムを適用した本発明の運行ダイヤ作
成方法を用いることにより、局所的な解の探索では求め
られなかった最適解を求めることが可能となり、また評
価条件で解の候補を淘汰することにより、より優れた解
を得ることができ、最適な仕業ダイヤを作成できる。

【図面の簡単な説明】

【図１】本発明の一実施例の動作を示すフローチャート
である。

【図２】本発明の一実施例において山ダイヤを仕業ダイ
ヤに割り当てるフローチャートである。

【図３】本発明のハードウェア構成の一実施例を示す図
である。

【図４】本発明の一実施例における山ダイヤを示す図で
ある。

【図５】本発明の一実施例における山ダイヤリストを示
す図である。

【図６】本発明の一実施例における仕業ダイヤを示す図
である。

【図７】本発明の一実施例における染色体を示す図であ
る。

【図８】本発明の一実施例における選択交配および淘汰
を示す図である。

【符号の説明】

１０１開始１０２山ダイヤリストの作成１０３初期集団発生１０４選択交配１０７割当て処理１１０個体評価１１１淘汰１１２世代数による条件分岐１１３終了

フロントページの続き (51)Int.Cl.⁶ 識別記号庁内整理番号ＦＩ技術表示箇所 // Ｇ０６Ｆ 17/60 Ｇ０６Ｆ 15/21 Ｃ (72)発明者岡田健一郎神奈川県川崎市幸区鹿島田890番地の12 株式会社日立製作所情報システム事業部内

Claims

【特許請求の範囲】

【請求項１】山ダイヤに基づき仕業ダイヤを生成するシ
ステムにおいて、イ）前記山ダイヤを構成する各斜線のそれぞれと対応さ
せて優先度を付与し、ロ）付与された各優先度を並べることにより記号列を作
成し、ハ）前記優先度の付与の仕方を変えて前記イ）〜ロ）の
ステップを所定の回数繰り返すことにより、複数の前記
記号列からなる第１の集団を生成し、ニ）前記第１の集団を構成する各記号列に対して優先度
の並べ替えを行なわせることにより、新たな記号列から
なる第２の集団を生成し、ホ）前記第１の集団および第２の集団を構成する各記号
列に対して、前記優先度に基づいて、１つの記号列を構
成する各優先度に対応する各斜線から仕業ダイヤを生成
し、ヘ）生成された仕業ダイヤを評価することにより、評価
基準を満たす各仕業ダイヤについては対応する前記記号
列からなる第３の集団を生成し、評価基準を満たさない
各仕業ダイヤについては対応する前記記号列を消去し、ト）前記第３の集団を前記第１の集団として前記ニ）〜
ヘ）のステップを繰り返すことによって仕業ダイヤを生
成することを特徴とする運行ダイヤ作成方法。
【請求項２】請求項１の運行ダイヤ作成方法は、遺伝的
アルゴリズムによって行なうものであって、前記記号列
は染色体に相当し、前記並べ替えは交叉に相当し、前記
へ）のステップは淘汰に相当することを特徴とする運行
ダイヤ作成方法。
【請求項３】請求項１において、前記ニ）のステップにおける前記優先度の並べ替えは、
規則性のある並べ替えと規則性のない並べ替えとからな
ることを特徴とする運行ダイヤ作成方法。
【請求項４】請求項１において、前記ホ）のステップは、前記第１の集団および第２の集
団を構成する各記号列に対して、１つの記号列を構成す
る各優先度に対応する各斜線を、仕業ダイヤの構成要素
となる横線に変換し、該横線を前記優先度に基づき所定
の列数に分けて配列して仕業ダイヤを生成することを特
徴とする運行ダイヤ作成方法。
【請求項５】請求項４において、前記ホ）のステップは、配列すべき横線を、既に配列さ
れている横線であって各列において最後に割り当てられ
たもののうち、付与されている優先度が高い横線に後続
させて配列することを特徴とする運行ダイヤ作成方法。
【請求項６】請求項４において、前記ヘ）のステップにおける前記評価は、前記横線に対
応する各車両の回送時間、各乗務員の休憩時間、および
未配列となった各横線の総時間数に基づき行なうことを
特徴とする運行ダイヤ作成方法。