(57)【要約】【課題】  遺伝的アルゴリズムに替わる手法で、高速且つ適切なラベルの配置を実現することである。【解決手段】  現ラベル配置パターン７３０と、当該現ラベル配置パターンを局所的に変更したラベル配置パターン候補７４０とのそれぞれの総ペナルティを算出する。そして、現総ペナルティ７５０と候補総ペナルティ７６０とを比較して、候補総ペナルティ７６０が現総ペナルティ７５０よりも小さい場合は、現ラベル配置パターン７３０をラベル配置パターン候補７４０で更新する。また、候補総ペナルティ７６０が現総ペナルティ７５０以上である場合は、現ラベル配置パターン７３０をラベル配置パターン候補７４０で更新するか否かを確率的に決定する。そして、この一連の処理を所定の条件を満たすまで繰り返し行った後に得られる現ラベル配置パターン７３０を最適な列車ラベルの配置パターンであるとする。【選択図】図２
2006069278.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータに、複数の対象線が表された図表上に、各対象線に対して少なくとも１のラベルを配置させるためのプログラムであって、
前記各対象線に対して１以上のラベル配置可能位置を設定する設定手段、
前記各対象線に対するラベル配置位置を、当該対象線に対して前記設定手段が設定したラベル配置可能位置の何れかから選択することによりラベル配置パターンを仮決定するパターン仮決定手段、
前記ラベル配置パターンを記憶する記憶手段、
前記記憶手段に記憶されたラベル配置パターンを所定の評価基準に基づいて評価する第１の評価手段、
前記記憶手段に記憶されたラベル配置パターンのうち、１のラベル配置位置を、対応する対象線に対する他のラベル配置可能位置に変更する変更手段、
前記変更手段による変更後のラベル配置パターンを前記所定の評価基準に基づいて評価する第２の評価手段、
前記第１の評価手段による評価結果より前記第２の評価手段による評価結果の方が高評価であった場合に前記変更手段による変更後のラベル配置パターンで前記記憶されたラベル配置パターンを更新し、前記第１の評価手段による評価結果より前記第２の評価手段による評価結果の方が低評価であった場合に所定の確率に従って前記変更手段による変更後のラベル配置パターンで前記記憶されたラベル配置パターンを更新する更新手段、
前記第１の評価手段、前記変更手段、前記第２の評価手段及び前記更新手段による一連の処理を所定の条件を満たすまで繰り返し制御する繰り返し制御手段、
として前記コンピュータを機能させるためのプログラム。
【請求項２】
請求項１に記載のプログラムであって、
前記更新手段が、前記第１の評価手段による評価結果より前記第２の評価手段による評価結果の方が低評価であった場合に、その評価の差の程度に応じた確度で、前記変更手段による変更後のラベル配置パターンで前記記憶されたラベル配置パターンを更新するように前記コンピュータを機能させるためのプログラム。
【請求項３】
請求項１又は２に記載のプログラムであって、
前記図表を列車ダイヤ図とし、前記対象線を列車スジとし、前記ラベルを列車番号として前記コンピュータを機能させるためのプログラム。
【請求項４】
請求項１又は２に記載のプログラムであって、
前記図表を列車ダイヤ図とし、前記対象線を列車スジとし、前記ラベルを所定のダイヤ図付帯情報記号として前記コンピュータを機能させるためのプログラム。
【請求項５】
請求項１〜３の何れか一項に記載のプログラムであって、
前記繰り返し制御手段による制御の後、前記記憶手段に記憶されているラベル配置パターンのうち、所定の縮小化条件を満足するラベル配置位置を検出する検出手段、
前記検出手段により検出されたラベル配置位置に配置するラベルのサイズを他のラベルより縮小化する縮小化手段、
として前記コンピュータを更に機能させるためのプログラム。
【請求項６】
複数の対象線が表された図表上に、各対象線に対して少なくとも１のラベルを配置するためのラベル配置装置であって、
前記各対象線に対して１以上のラベル配置可能位置を設定する設定手段と、
前記各対象線に対するラベル配置位置を、当該対象線に対して前記設定手段が設定したラベル配置可能位置の何れかから選択することによりラベル配置パターンを仮決定するパターン仮決定手段と、
前記ラベル配置パターンを記憶する記憶手段と、
前記記憶手段に記憶されたラベル配置パターンを所定の評価基準に基づいて評価する第１の評価手段と、
前記記憶手段に記憶されたラベル配置パターンのうち、１のラベル配置位置を、対応する対象線に対する他のラベル配置可能位置に変更する変更手段と、
前記変更手段による変更後のラベル配置パターンを前記所定の評価基準に基づいて評価する第２の評価手段と、
前記第１の評価手段による評価結果より前記第２の評価手段による評価結果の方が高評価であった場合に前記変更手段による変更後のラベル配置パターンで前記記憶されたラベル配置パターンを更新し、前記第１の評価手段による評価結果より前記第２の評価手段による評価結果の方が低評価であった場合に所定の確率に従って前記変更手段による変更後のラベル配置パターンで前記記憶されたラベル配置パターンを更新する更新手段と、
前記第１の評価手段、前記変更手段、前記第２の評価手段及び前記更新手段による一連の処理を所定の条件を満たすまで繰り返し制御する繰り返し制御手段と、
を備えるラベル配置装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の対象線が表された図表上に、各対象線に対して少なくとも１のラベルを配置するラベル配置装置等に関する。
【背景技術】
【０００２】
近年、地図や路線図等の図表上の対象線に対して地名等のラベルを配置する問題が注目を集めるようになった。中でも、川や道路等の線分上の図形にその名前等のラベルを配置する問題は、ＥＬＰ（Edge Label Placement）問題と呼ばれる。ＥＬＰ問題は、ＮＰ困難であることが証明されており、ヒューリスティックな方法で近似最適解を求める試みが行われている。列車ダイヤ図を生成する際の問題も、列車スジに列車番号等のラベルを配置するという点でＥＬＰ問題に類似している。
【０００３】
列車ダイヤ図は、鉄道の運行スケジュールに関する膨大な情報が描画された図表であり、主に、列車の運行を表す列車スジ、当該列車スジが示す列車の列車番号、到着時刻や発車時刻を表す秒記号や番線名等の付帯情報記号等により構成される。１本の列車スジに対して、列車番号、秒記号及び付帯情報記号等のラベルが配置されるため、複数の列車スジが描画される列車ダイヤ図は複雑な図表となる。特に、都市近郊における朝夕のラッシュアワー時は列車の運行間隔が短いため、列車スジ同士の間隔が狭まってしまい列車ダイヤ図は極めて複雑である。
【０００４】
このため、経験を積んだベテランによって列車ダイヤ図は作成されてきたが、近年、これをコンピュータにより作成する試みが為されてきた。しかし、コンピュータで列車ダイヤ図を作成する際に、ベテランが経験上培ってきた列車ダイヤ図を作成する際の留意点が完全には考慮されないという問題があった。具体的には、列車番号同士や列車番号と秒記号又は付帯情報記号とが重ならないこと、同じ種類の列車に対する列車番号の水平位置がなるべく揃うこと、列車番号が密集しないこと等の条件が満たされないといった問題である。このような問題を解決するために、遺伝的アルゴリズムを用いて列車ダイヤ図を作成する手法が提案されている。これは、生成した複数の列車ダイヤ図の候補それぞれを所定の評価条件に基づいて評価して、高評価な列車ダイヤ図同士を交叉及び突然変異させるといった一連の処理を所定回数繰り返すことで、局所最適解に陥らず最適な位置に列車番号を配置した列車ダイヤ図を得る手法である（特許文献１参照）。
【特許文献１】特開２００２−２９３２４２号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかし、遺伝的アルゴリズムは、一般に計算回数が多いことで知られている。しかも、列車ダイヤ図は、上述したように様々な条件が複雑に絡み合った図である。そのため、列車スジに対する列車番号の配置は、それらの条件をなるべく満たすことが望まれる。ところが、上述したように列車ダイヤ図にラベルを配置することはＮＰ困難であるから、当該条件を満たす最適な列車ダイヤ図を得るために、膨大な計算量が必要となり、引いては多大な処理時間を要してしまった。
【０００６】
本発明は、上述した課題に鑑みて為されたものであり、その目的とするところは、遺伝的アルゴリズムに替わる手法で、高速且つ適切なラベルの配置を実現することである。
【課題を解決するための手段】
【０００７】
以上の課題を解決するために、第１の発明は、
コンピュータに、複数の対象線（例えば、図１の列車スジＧＦ１００）が表された図表（例えば、図１の列車ダイヤ図ＦＧ１００）上に、各対象線に対して少なくとも１のラベル（例えば、図１の列車ラベルＴＲ１００）を配置させるためのプログラムであって、
前記各対象線に対して１以上のラベル配置可能位置（例えば、図１２のラベルポジションＴＬＰ１）を設定する設定手段（例えば、図２のＣＰＵ１０；図９のステップＡ５）、
前記各対象線に対するラベル配置位置を、当該対象線に対して前記設定手段が設定したラベル配置可能位置の何れかから選択することによりラベル配置パターン（例えば、図６の現ラベル配置パターン７３０）を仮決定するパターン仮決定手段（例えば、図２のＣＰＵ１０；図９のステップＡ９）、
前記ラベル配置パターンを記憶する記憶手段（例えば、図２のＲＡＭ７０）、
前記記憶手段に記憶されたラベル配置パターンを所定の評価基準に基づいて評価する第１の評価手段（例えば、図２のＣＰＵ１０；図１０のステップＡ１０７）、
前記記憶手段に記憶されたラベル配置パターンのうち、１のラベル配置位置を、対応する対象線に対する他のラベル配置可能位置に変更する変更手段（例えば、図２のＣＰＵ１０；図１０のステップＡ１０３）、
前記変更手段による変更後のラベル配置パターンを前記所定の評価基準に基づいて評価する第２の評価手段（例えば、図２のＣＰＵ１０；図１０のステップＡ１０９）、
前記第１の評価手段による評価結果より前記第２の評価手段による評価結果の方が高評価であった場合に前記変更手段による変更後のラベル配置パターンで前記記憶されたラベル配置パターンを更新し、前記第１の評価手段による評価結果より前記第２の評価手段による評価結果の方が低評価であった場合に所定の確率に従って前記変更手段による変更後のラベル配置パターンで前記記憶されたラベル配置パターンを更新する更新手段（例えば、図２のＣＰＵ１０；図１０のステップＡ１１１→Ａ１１３、ステップＡ１１１→Ａ１１５→Ａ１１３）、
前記第１の評価手段、前記変更手段、前記第２の評価手段及び前記更新手段による一連の処理を所定の条件を満たすまで繰り返し制御する繰り返し制御手段（例えば、図２のＣＰＵ１０；図９のステップＡ１３→Ａ１１）、
として前記コンピュータを機能させるプログラムである。
【０００８】
第６の発明は、
複数の対象線（例えば、図１の列車スジＧＦ１００）が表された図表（例えば、図１の列車ダイヤ図ＦＧ１００）上に、各対象線に対して少なくとも１のラベル（例えば、図１の列車ラベルＴＲ１００）を配置するためのラベル配置装置（例えば、図２の列車ダイヤ図生成装置１）であって、
前記各対象線に対して１以上のラベル配置可能位置（例えば、図１２のラベルポジションＴＬＰ１）を設定する設定手段（例えば、図２のＣＰＵ１０；図９のステップＡ５）と、
前記各対象線に対するラベル配置位置を、当該対象線に対して前記設定手段が設定したラベル配置可能位置の何れかから選択することによりラベル配置パターン（例えば、図６の現ラベル配置パターン７３０）を仮決定するパターン仮決定手段（例えば、図２のＣＰＵ１０；図９のステップＡ９）と、
前記ラベル配置パターンを記憶する記憶手段（例えば、図２のＲＡＭ７０）と、
前記記憶手段に記憶されたラベル配置パターンを所定の評価基準に基づいて評価する第１の評価手段（例えば、図２のＣＰＵ１０；図１０のステップＡ１０７）と、
前記記憶手段に記憶されたラベル配置パターンのうち、１のラベル配置位置を、対応する対象線に対する他のラベル配置可能位置に変更する変更手段（例えば、図２のＣＰＵ１０；図１０のステップＡ１０３）と、
前記変更手段による変更後のラベル配置パターンを前記所定の評価基準に基づいて評価する第２の評価手段（例えば、図２のＣＰＵ１０；図１０のステップＡ１０９）と、
前記第１の評価手段による評価結果より前記第２の評価手段による評価結果の方が高評価であった場合に前記変更手段による変更後のラベル配置パターンで前記記憶されたラベル配置パターンを更新し、前記第１の評価手段による評価結果より前記第２の評価手段による評価結果の方が低評価であった場合に所定の確率に従って前記変更手段による変更後のラベル配置パターンで前記記憶されたラベル配置パターンを更新する更新手段（例えば、図２のＣＰＵ１０；図１０のステップＡ１１１→Ａ１１３、ステップＡ１１１→Ａ１１５→Ａ１１３）と、
前記第１の評価手段、前記変更手段、前記第２の評価手段及び前記更新手段による一連の処理を所定の条件を満たすまで繰り返し制御する繰り返し制御手段（例えば、図２のＣＰＵ１０；図９のステップＡ１３→Ａ１１）と、
を備えるラベル配置装置である。
【０００９】
第１又は第６の発明によれば、ラベル配置パターンの評価結果と、変更手段が変更したラベル配置パターンの評価結果とを比較し、変更後のラベル配置パターンの方が高評価であれば、記憶手段に記憶されるラベル配置パターンを変更後のラベル配置パターンで更新して、より良いラベル配置パターンを得る。しかし、変更後のラベル配置パターンの方が低評価であった場合、所定の確率に従って記憶手段に記憶されるラベル配置パターンを変更後のラベル配置パターンで更新する。このように変更後のラベル配置パターンが低評価である場合にも、そのラベル配置パターンで記憶手段に記憶されているラベル配置パターンを更新することで、記憶手段に記憶されたラベル配置パターンが局所最適解となることを防ぐことができる。従って、遺伝的アルゴリズムに替わる手法で、対象線に対する最適な位置にラベルを配置することが可能となる。また、遺伝的アルゴリズムに比べてその処理方法が比較的単純であるため、処理を高速化できる。
【００１０】
第２の発明は、第１の発明のプログラムであって、
前記更新手段が、前記第１の評価手段による評価結果より前記第２の評価手段による評価結果の方が低評価であった場合に、その評価の差の程度に応じた確度で、前記変更手段による変更後のラベル配置パターンで前記記憶されたラベル配置パターンを更新するように前記コンピュータを機能させるものである。
【００１１】
第２の発明によれば、第１の発明と同様の効果が得られるのは無論のこと、記憶手段により記憶されたラベル配置パターンを更新する確率を、第１の評価手段による評価結果と第２の評価手段による評価結果との差の程度に応じた確度とする。このため、第１の評価手段の評価結果より第２の評価手段の評価結果の方が低評価であった際に、それらの評価結果に応じた確率で、記憶手段により記憶されたラベル配置パターンの更新を行うことができる。
【００１２】
第３の発明は、第１又は第２の発明のプログラムであって、
前記図表を列車ダイヤ図とし、前記対象線を列車スジとし、前記ラベルを列車番号として前記コンピュータを機能させるプログラムである。
【００１３】
第３の発明によれば、第１又は第２の発明と同様の効果が得られるのは無論のこと、列車ダイヤ図を生成する際に、列車ダイヤ図上の列車スジに対して最適な位置に列車番号を配置することができる。
【００１４】
第４の発明は、第１又は第２の発明のプログラムであって、
前記図表を列車ダイヤ図とし、前記対象線を列車スジとし、前記ラベルを所定のダイヤ図付帯情報記号（例えば、図１の番線名ラベルＨＲ１００）として前記コンピュータを機能させるものである。
【００１５】
第４の発明によれば、第１又は第２の発明と同様の効果が得られるのは無論のこと、列車ダイヤ図を生成する際に、列車ダイヤ図上の列車スジに対して最適な位置にダイヤ図付帯情報記号を配置することができる。
【００１６】
第５の発明は、第１〜第３の発明の何れか一つのプログラムであって、
前記繰り返し制御手段による制御の後、前記記憶手段に記憶されているラベル配置パターンのうち、所定の縮小化条件を満足するラベル配置位置を検出する検出手段（例えば、図２のＣＰＵ１０；図１１のステップＡ２０１）、
前記検出手段により検出されたラベル配置位置に配置するラベルのサイズを他のラベルより縮小化する縮小化手段（例えば、図２のＣＰＵ１０；図１１のステップＡ２０９）、
として前記コンピュータを更に機能させるプログラムである。
【００１７】
第５の発明によれば、第１〜第３の何れか一つの発明と同様の効果が得られるのは無論のこと、繰り返し制御手段の制御後に、縮小化条件を満足するラベル配置位置のラベルのサイズを他のラベルより縮小化する。例えば、他のラベルのラベル配置位置と重なっているか否かを縮小化条件とした場合に、他のラベルのラベル配置位置と重なっている場合は、そのラベル配置位置のラベルを縮小化することにより、他のラベル配置位置との重なりの解消が期待される。
【発明の効果】
【００１８】
以上、本発明によれば、ラベル配置パターンが局所最適解となることを防ぐことができる。従って、遺伝的アルゴリズムに替わる手法で、対象線に対する最適な位置にラベルを配置することが可能となる。また、比較的単純な処理方法を用いるため、処理を高速化できる。
【発明を実施するための最良の形態】
【００１９】
ラベル配置の対象とする図表を列車ダイヤ図とした場合の実施形態について、図１〜１６を参照して詳細に説明する。尚、以下の説明において、本発明のラベル配置装置をパーソナルコンピュータ（以下、「パソコン」と略す。）に適用し、このパソコンで列車ダイヤ図生成装置を構成することとして説明するが、本発明が適用可能なものはこれに限られるものではない。
【００２０】
図１は、列車ダイヤ図の一例を示す図である。列車ダイヤ図ＦＧ１００は、横軸を時間、縦軸を駅としたグラフであり、駅の位置を表す駅線と時刻を示す時刻線とが引かれている。また、列車ダイヤ図ＦＧ１００は、列車の運行の時間的な遷移を表す列車スジと、各列車スジに対応した列車の列車番号と、各列車の停車駅における着発時刻を表す秒記号と、ダイヤ図付帯情報記号（以下、単に「付帯情報記号」という。）の１つである番線名等により構成される。尚、付帯情報記号には、番線名の他に、回送列車や指定日に運行される列車といった列車の性質を表すスジ記号や列車の速度種別を表す速度記号等があるが、本実施形態では番線名を付帯情報記号の一例として説明する。
【００２１】
同図によれば、列車ダイヤ図ＦＧ１００には、縦軸に駅Ａ、駅Ｂ及び駅Ｃといった駅名が示されている。そして、駅Ａに対応する駅線Ｌａ１００、駅Ｂに対応する駅線Ｌｂ１００、駅Ｃに対応する駅線Ｌｃ１００といったように各駅毎に駅線が引かれている。
【００２２】
また、列車ダイヤ図ＦＧ１００上には、右上がりの傾斜線又は右下がりの傾斜線で列車スジが描画されている。例えば、列車スジＧＦ１００は、駅線Ｌａ１００、Ｌｂ１００及びＬｃ１００と交差する右上がりの傾斜線で描画されている。これは、駅Ｃ、駅Ｂ、駅Ａといった順に着発する上り列車の運行を表している。また、列車スジＧＦ１１０は、駅線Ｌａ１００、Ｌｂ１００及びＬｃ１００と交差する右下がりの傾斜線である。これは、駅Ａ、駅Ｂ、駅Ｃといった順に着発する下り列車の運行を表している。
【００２３】
この列車スジには、当該列車スジで表される列車の列車番号が列車ラベルとして配置指定駅間で少なくとも１つ配置される。列車ラベルは、右上がりの列車スジに対してはその左側、右下がりの列車スジに対してはその右側、即ち、列車スジに対して上側に配置される。例えば、右上がりの列車スジＧＦ１００の上側には、列車番号「８２８０Ｆ」が列車ラベルＴＲ１００として配置され、右下がりの列車スジＧＦ１１０の上側には、列車番号「１０６３」が列車ラベルＴＲ１１０として配置されている。また、列車スジと駅線とが交差する箇所には、秒記号（例えば、秒記号ＳＲ１００）や番線名（例えば、番線名ラベルＨＲ１００）が配置される。ここで、秒記号は、例えば、駅線Ｌａ１００を中心とする上下方向の領域ＡＲ１００内といった予め定められた範囲内に配置される。
【００２４】
列車ダイヤ図は、図１に示すように複雑な図であるので、視認性の向上を図るために次のような仕様が要求される。先ず、列車ダイヤ図の生成の際に則る第１のルールとして、
（１）全ての列車スジに対して必ず１つ以上の列車番号を配置すること。
（２）右上がりの列車スジに対してはその左側に、右下がりの列車スジに対してはその右側に列車番号を配置すること。
（３）列車番号がどの列車スジに対応しているかが明確に分かる位置、即ち、列車スジから余り離れない位置に配置すること。
（４）指定された駅間に列車番号を配置すること。
（５）上り列車の秒記号は駅線の下側に、下り列車の秒記号は駅線の上側に配置すること。
等がある。この第１のルールを満たすように列車ダイヤ図生成装置１は、列車ダイヤ図を生成しなければならない。
【００２５】
また、第１のルールの他に、
（６）列車番号同士が重ならないこと。
（７）列車番号と他の列車の列車スジとがなるべく重ならないこと。
（８）列車番号と駅線とがなるべく重ならないこと。
（９）同一種別の列車の列車番号の水平位置がなるべく横に揃っていること。
（１０）同一種別の列車の列車番号が密集しすぎないこと。
（１１）列車番号と秒記号とが重ならないこと。
等の第２のルールを満たした列車ダイヤ図がより望ましい。これらのルールを満たした列車ダイヤ図を生成することで、列車ダイヤ図の視認性を向上させることができる。
【００２６】
図２は、列車ダイヤ図生成装置１の機能構成の一例を示すブロック図である。同図によれば、列車ダイヤ図生成装置１は、ＣＰＵ（Central Processing Unit）１０と、入力装置２０と、表示装置３０と、ＲＯＭ（Read Only Memory）４０と、記憶装置５０と、ＲＡＭ（Random Access Memory）７０とがバス８０に接続されて構成される。
【００２７】
ＣＰＵ１０は、入力される指示に応じて所定のプログラムに基づいた処理を実行し、各機能部への指示やデータの入出力を行う。具体的には、ＣＰＵ１０は、入力装置２０から入力される操作信号に応じてＲＯＭ４０や記憶媒体６０に格納されたプログラムを読み出し、当該プログラムに従って処理を実行する。そして、処理結果を表示装置３０に表示させる。
【００２８】
入力装置２０は、カーソルキー、テンキー及び各種ファンクションキー等を有するキーボードやマウス等のポインティングデバイスを備え、押下されたキーの押下信号や、マウスの位置信号等をＣＰＵ１０に出力する。
【００２９】
表示装置３０は、ＣＲＴ（Cathode-ray Tube）やＬＣＤ（Liquid Crystal Display）等により構成され、ＣＰＵ１０から入力される表示データに基づいて各種画面を表示出力する。
【００３０】
ＲＯＭ４０は、各種初期設定、ハードウェアの検査に必要なプログラムのロード等を行うための初期化（ＩＰＬ）プログラムや、当該プログラムに係る各種初期設定値を格納する。ＣＰＵ１０は、列車ダイヤ図生成装置１の電源投入時にこの初期化プログラムを実行することにより、当該装置の動作環境を設定する。
【００３１】
記憶装置５０は、例えば、ＣＤ−ＲＯＭやメモリカード、ハードディスク等の記憶媒体６０に対してデータの読み書きを行う機能部である。記憶媒体６０は、磁気的、光学的記憶媒体、若しくは半導体メモリ等で構成され、アプリケーションプログラムや各種処理プログラムで処理されたデータ等を格納する。尚、記憶媒体６０は、記憶装置５０に固定的に設けることとしてもよいし、着脱自在に装着するものとしてもよい。
【００３２】
図２によれば、記憶媒体６０は、列車ダイヤデータ６００と、列車ダイヤ図生成プログラム６１０とを格納している。
【００３３】
列車ダイヤデータ６００は、列車番号と、当該列車番号の列車が着発する着発駅毎のダイヤデータとを対応付けて格納するデータテーブルである。図３（ａ）は、列車ダイヤデータ６００のデータ構造を表す図である。同図（ａ）によれば、列車番号に対応付けられたダイヤデータには、列車が着発する駅の番線名、着時刻及び発時刻が含まれている。同図（ｂ）は、列車ダイヤデータ６００のデータ構成の一例を示す図であり、列車ダイヤ図に描画される全ての列車スジの列車番号及びダイヤデータが蓄積記憶されている。ＣＰＵ１０は、列車ダイヤデータ６００に格納されるダイヤデータを元に、列車スジと秒記号とにより構成される列車ダイヤ図を生成して、この列車ダイヤ図に番線名を配置した後、後述する確率的局所探索処理に従って列車ラベルの最適な配置位置を求める。
【００３４】
列車ダイヤ図生成プログラム６１０は、本実施形態に係る列車ダイヤ図生成処理を実現するためのプログラムであり、サブルーチンとして確率的局所探索プログラム６１２とフォントサイズ変更プログラム６１４とを有して構成される。確率的局所探索プログラム６１２は確率的局所探索処理（図１０参照）を、フォントサイズ変更プログラム６１４はフォント変更処理（図１１参照）をそれぞれ実現するためのプログラムである。ＣＰＵ１０は、適宜プログラムを記憶媒体６０から読み出すことで、当該プログラムに基づく処理を開始する。
【００３５】
ここで確率的局所探索処理について簡単に説明する。確率的局所探索処理とは、改善を行う際に、それまでの解よりも悪い解となっても確率的にその解を受け入れて解の探索を実行することにより、局所最適解に陥ることを防止し、更に良い解（列車ラベルの配置位置）を得ようとする手法である。より具体的には、現在の列車ラベルの配置（解）と、この列車ラベルの配置を局所的に変更した列車ラベルの配置候補（解候補）とのそれぞれを、上述したルールをどの程度満たしているかを評価し、高評価であるほうの列車ラベルの配置を選択して、より良い列車ラベルの配置（解）を得るが、列車ラベルの配置候補が現在の列車ラベルの配置よりも悪くなった（低評価となった）としても、確率的にその配置候補を選択し、これらの一連の処理を繰り返す。この現在の列車ラベルの配置よりも悪くなってしまった列車ラベルの配置を解として時には選択することで、局所最適解に陥ることを防ぐのである。
【００３６】
ＲＡＭ７０は、ＣＰＵ１０が実行する各種プログラムや、これらプログラムの実行に係るデータ等を一時的に保持する記憶領域である。図２によれば、ＲＡＭ７０は、配置指定駅間７００と、指定駅間内ラベルポジション数７１０と、ラベルポジション座標値テーブル７２０と、現ラベル配置パターン７３０と、ラベル配置パターン候補７４０と、現総ペナルティ７５０と、候補総ペナルティ７６０とを格納する。
【００３７】
配置指定駅間７００は、列車ラベルを配置する駅間であり、指定駅間内ラベルポジション数７１０は、配置指定駅間７００の駅間内に生成するラベルポジションの数である。この配置指定駅間７００及び指定駅間内ラベルポジション数７１０は、ユーザによって指定・入力されるデータである。
【００３８】
ＣＰＵ１０は、配置指定駅間７００と、指定駅間内ラベルポジション数７１０とに基づいて列車ダイヤ図上の列車スジに対してラベルポジションを生成する。ラベルポジションとは、配置指定駅間７００の駅間内の列車スジに対して、列車ラベルを配置可能な位置（ラベル配置可能位置）のことである。このラベルポジションは、列車番号に使用される英数字のフォントの大きさや字数等を考慮して生成される。ＣＰＵ１０は、指定駅間内ラベルポジション数７１０の数分のラベルポジションを配置指定駅間７００内の列車スジに対して生成する。そして、この生成したラベルポジションに対して列車スジの発駅側から着駅側に向けて昇順にラベルポジション番号を振る。
【００３９】
例えば、配置指定駅間７００が「駅Ａ〜Ｂ」、指定駅間内ラベルポジション数７１０が「５」と指定されたとする。図４（ａ）の駅Ａに対応する駅線Ｌａ２００と駅Ｂに対応する駅線Ｌｂ２００間の列車スジＧＦ２００には、５つのラベルポジションＴＬＰ２００が生成される。ラベルポジションのサイズは、列車番号の文字の大きさを元とする。ラベルポジションは、互いに重なりあってもよい。これは何れか１つが選択されるためである。そして、このラベルポジションＴＬＰ２００には、発駅である駅Ａ側から着駅である駅Ｂ側に向けて昇順にラベルポジション番号が“０”〜“４”と振られる。
【００４０】
また、図４（ｂ）の列車スジＧＦ３００には、当該列車スジの上側に５つのラベルポジションＴＬＰ３００が生成される。そして、このラベルポジションＴＬＰ３００には、この発駅である駅Ｂ側から着駅である駅Ａ側に向けて昇順にラベルポジション番号が“０”〜“４”と振られる。
【００４１】
ここで、指定駅間内ラベルポジション数７１０は奇数であることが望ましい。これは、配置指定駅間７００の駅間の中央に列車ラベルを配置するのが最適であり視認性が良いとされるからである。
【００４２】
ラベルポジション座標値テーブル７２０は、ＣＰＵ１０が生成したラベルポジションの座標値を列車スジ毎に格納するデータテーブルである。図５に指定駅間内ラベルポジション数７１０が「５」である場合のラベルポジション座標値テーブル７２０のデータ構成の一例を示す。同図によれば、ラベルポジション座標値テーブル７２０は、各列車スジに対して生成されたラベルポジションの４頂点の座標値（Ｘ座標、Ｙ座標）を格納している。また、１つの列車スジに対して５つのラベルポジションの座標値が対応付けられて格納されている。
【００４３】
現ラベル配置パターン７３０は、ラベルポジションに対して仮配置した各列車ラベルの配置位置のパターンであり、列車ラベルを配置したラベルポジションのラベルポジション番号を、列車スジ毎に配置ラベルポジション番号として格納するデータテーブルである。図６は、図１３（ｂ）の列車ダイヤ図に対する現ラベル配置パターン７３０のデータ構成の一例を示す図である。図６によれば、例えば、列車スジＧＦ１に対しては配置ラベルポジション番号“０”が格納されている。これは、列車スジＧＦ１に対して生成されたラベルポジションＴＬＰ１のうちラベルポジション番号が“０”のラベルポジションをラベル配置位置として列車ラベルを仮配置したということを表している。
【００４４】
確率的局所探索処理において、ＣＰＵ１０は、現ラベル配置パターン７３０を仮の解とし、この現ラベル配置パターン７３０から解候補となるラベル配置パターン候補７４０を生成する。より具体的には、ＣＰＵ１０は、現ラベル配置パターン７３０の中からランダムに列車スジを選択して、選択した列車スジに配置された列車ラベルの配置位置を当該列車スジに対するラベルポジションの中の移行候補位置へ変更する。この移行候補位置は、例えば、乱数を発生させることによって“０〜４”の何れかの整数を無作為に生成して、当該整数で示されるラベルポジション番号のラベルポジションとする。ＣＰＵ１０は、現ラベル配置パターン７３０中の選択した列車スジに対応する配置ラベルポジション番号を移行候補位置のラベルポジション番号に変更し、その変更後のラベル配置パターンをラベル配置パターン候補７４０としてＲＡＭ７０に格納する。尚、ラベル配置パターン候補７４０のデータ構成は、現ラベル配置パターン７３０と同様であるので、その図示は省略する。
【００４５】
現総ペナルティ７５０は、現ラベル配置パターン７３０を評価することにより得られる値であり、候補総ペナルティ７６０は、ラベル配置パターン候補７４０を評価することにより得られる値である。これらの総ペナルティは、列車ラベルと、列車スジ、駅線及び他の列車の列車ラベルとの位置関係を評価するにあたっての評価基準となり、各種ペナルティ値を元に求められる。
【００４６】
ここで、ペナルティ値について説明する。ペナルティ値は、ラベル配置パターンで表される列車ラベルの配置位置の適正を判断するための値であり、その名の通り、数値として小さい値を良しとする値である。また、ペナルティ値には、静的ペナルティと動的ペナルティとの２つがあり、静的ペナルティは、列車ラベル毎の配置位置のみによって定まる値、動的ペナルティは、２個以上の複数の列車ラベルの配置の相互関係によって定まる値である。
【００４７】
先ず、静的ペナルティについて説明する。静的ペナルティには、絶対位置ペナルティＳ１と、駅線交差ペナルティＳ２と、列車交差スジペナルティＳ３とがある。
【００４８】
絶対位置ペナルティＳ１は、ラベルポジションに対して絶対的に定めた優先順位に従って設定された値である。例えば、図４（ａ）に示す駅Ａと駅Ｂとの間に列車ラベルを１つ配置する場合、ラベルポジションＴＬＰ２００の５つのうち、中心に位置するラベルポジション番号“２”のラベルポジションを最適な配置位置として、そのペナルティ値を“０”とする。
【００４９】
例えば、下り列車の列車スジＧＦ２００に対する各ラベルポジションのペナルティ値は、発駅の駅Ａ側から優先順位が高くなるように、“１”、“３”、“０”、“６”、“９”といった順に各ラベルポジションに設定する。また、図４（ｂ）の上り列車の列車スジＧＦ３００に対する各ラベルポジションに対するペナルティ値は、発駅の駅Ｂ側から優先順位が高くなるように設定する。このように、何れの場合も着駅側のペナルティ値が最大となるように設定するのは、列車番号は、駅線と駅線との中央付近か、若しくは発駅側に配置されるのが、一般に視認性が良いとされているからである。但し、ラベルポジションの絶対的な優先順位は、上述の順に限るものではない。
【００５０】
駅線交差ペナルティＳ２は、列車ラベルが駅線と交差した際のペナルティ値である。ＣＰＵ１０は、先ず、ラベルポジション座標値テーブル７２０から、仮配置した列車ラベルの上端点と下端点との座標値を読み出す。そして、読み出した座標値を用いて、列車ラベルと駅線とが交差するか否かを判定する。交差すると判定した場合は、例えば、ペナルティ値として“α”を設定する。αの値は任意の固定値としてよいが、列車ラベルの中央で交差するのか、端部で交差するのか、といった交差の程度に応じて異なる値としてもよい。その場合、駅線交差ペナルティＳ２の値（α）が小さいほど、上述した第２のルールの（８）を満たすように設定する。
【００５１】
列車スジ交差ペナルティＳ３は、列車ラベルが他の列車を示す列車スジと交差した際のペナルティ値である。ＣＰＵ１０は、先ず、上述した駅線交差ペナルティＳ２と同様に、仮配置した列車ラベルの上端点と下端点との座標値を用いて交差の有無を判定する。そして、判定結果に基づいて、例えば、ペナルティ値として“β”を設定する。βの値は任意の固定値としてよいが、交差の程度に応じて異なる値としてもよい。その場合、列車スジ交差ペナルティＳ３の値（β）が小さいほど、上述した第２のルールの（７）を満たすように設定する。
【００５２】
また、本実施の形態においては、説明の簡明化のため、列車ラベルと秒記号との交差に関するペナルティを付与しないこととして説明するが、第２のルールの１つとなっているため、列車ラベルと秒記号との交差に応じてペナルティを付与することとしてよいことは勿論である。
【００５３】
次に、動的ペナルティについて説明する。動的ペナルティには、ラベル接触ペナルティＤ１と、水平位置ペナルティＤ２と、密集ペナルティＤ３とがある。
【００５４】
ラベル接触ペナルティＤ１は、異なる列車ラベル同士が重なった際のペナルティ値である。ＣＰＵ１０は、列車ダイヤ図に配置される列車ラベルに重なる列車ラベルが存在するか否かを、ラベルポジション座標値テーブル７２０を用いて判定する。例えば、列車ラベルの長辺や、対角線を用いて当該列車ラベルを認識し、この直線と他の列車ラベルとの交差を判定する。そして、交差すると判定した場合は、ペナルティ値として、例えば“θ”を設定する。θの値は任意の固定値としてよいが、列車ラベル同士の重なりの程度に応じて異なる値としてもよい。その場合、このラベル接触ペナルティＤ１の値が小さいほど、第２のルールの（６）を満たすように設定する。
【００５５】
水平位置ペナルティＤ２は、同一種別の列車スジに配置される列車ラベル同士が、水平方向に揃っているか否かによって定まるペナルティ値である。ここで、同一種別の列車とは、例えば、特急列車、普通列車、上り列車、下り列車等である。列車ラベルが、水平方向に揃っているか否かに係る度合いは、例えば、列車ダイヤ図を時間軸方向に見たときの、列車ラベルの高さの差で算出する。より具体的には、ある１つの列車スジに注目し、注目した列車スジの列車と同一種別の列車の列車スジを時間軸方向に順次検索する。そして、隣り合う同一種別の列車スジ対する列車ラベルの高さの差の二乗の合計を算出して、この処理を全列車の種別に対して行って、その合計を水平位置ペナルティＤ２とする。ここで、水平位置ペナルティＤ２の値が小さいほど、第２のルールの（９）を満たしているとする。
【００５６】
例えば、図７に示す列車ダイヤ図ＦＧ４００において、列車ラベルＴＲ４００、ＴＲ４０２、ＴＲ４０４及びＴＲ４０６が同一種別の列車の列車スジに対する列車ラベルであるとする。このとき、列車ラベルＴＲ４００に注目した場合、列車ラベルＴＲ４００と列車ラベルＴＲ４０２との高さの差分ｄｆ１、列車ラベルＴＲ４０２と列車ラベルＴＲ４０４との高さの差分ｄｆ２、列車ラベルＴＲ４０４と列車ラベルＴＲ４０６との高さの差分ｄｆ３それぞれの二乗の合計を水平位置ペナルティＤ２とする。従って、これらの列車ラベルが水平方向に揃っている場合は、列車ラベル間の高さの差分は“０”となるため、水平位置ペナルティＤ２も“０”となる。
【００５７】
密集ペナルティＤ３は、同一種別の列車スジに配置される列車ラベル同士が、密集しているか否かによって定まるペナルティ値である。例えば、配置指定駅間７００の駅間内を所定の区画に分割して、その区画内にある同一種別の列車の列車ラベルの数をカウントする。そして、各区画に配置された列車ラベルの個数の平均値と、区画内に配置された列車ラベルの個数の分散値を算出して、密集ペナルティＤ３として設定する。ここで、密集ペナルティＤ３の値が小さいほど、第２のルールの（１０）を満たしているとする。以下に、列車ダイヤ図を４つの区画に分割した場合の密集ペナルティＤ３を算出する式を示す。
【００５８】
平均値＝配置指定駅間内の列車ラベルの総数／区画数・・・（ａ）
【数１】
2006069278.tif 000003
【００５９】
例えば、図８の列車ダイヤ図ＦＧ５００において、区画ＡＲ５００には列車ラベルが４個、区画ＡＲ５０２には列車ラベルが３個、区画ＡＲ５０４には列車ラベルが３個、区画ＡＲ５０６には列車ラベルが４個配置されている。このとき、平均値は“３．５”となり密集ペナルティＤ３は“１”と算出される。
【００６０】
上述した各ペナルティ値（静的ペナルティ及び動的ペナルティの値）を算出後、以下に示す式により総ペナルティを算出する。
総ペナルティ＝Ｓ１W・Ｓ１＋Ｓ２W・Ｓ２＋Ｓ３W・Ｓ３
＋Ｄ１W・Ｄ１＋Ｄ２W・Ｄ２＋Ｄ３W・Ｄ３・・・（ｃ）
尚、Ｓ１W、Ｓ２W、Ｓ３W、Ｄ１W、Ｄ２W及びＤ３Wを各ペナルティに対する重みとする。
【００６１】
尚、静的ペナルティ及び動的ペナルティは、上述したペナルティ値のみに限られるものではなく、視認性の向上の妨げとなる要因の度合いを適宜ペナルティ値として算出・加算することとしてよく、例えば、列車ラベルが付帯情報記号や秒記号等と交差した際のペナルティ値を静的ペナルティとして算出・加算することとしてよい。
【００６２】
ＣＰＵ１０は、上述した方法によって、現ラベル配置パターン７３０で示される列車ラベルの配置の総ペナルティ値を算出して現総ペナルティ７５０としてＲＡＭ７０に格納し、また、ラベル配置パターン候補７４０で示される列車ラベルの配置の総ペナルティ値を算出して候補総ペナルティ７６０としてＲＡＭ７０に格納する。
【００６３】
ＣＰＵ１０は、現総ペナルティ７５０と候補総ペナルティ７６０とを比較して、その比較結果に基づいて、現ラベル配置パターン７３０をラベル配置パターン候補７４０で更新するか否かを決定する。より具体的には、候補総ペナルティ７６０が現総ペナルティ７５０よりも小さい場合、即ち、ラベル配置パターン候補７４０の方が高評価であった場合は、現ラベル配置パターン７３０をラベル配置パターン候補７４０で更新する。また、候補総ペナルティ７６０が現総ペナルティ７５０よりも大きい場合、即ち、ラベル配置パターン候補７４０のほうが低評価であった場合は、現ラベル配置パターン７３０を保持するが、所定の確率に従って現ラベル配置パターン７３０をラベル配置パターン候補７４０で更新する。
【００６４】
例えば、現総ペナルティ７５０と候補総ペナルティ７６０との差分を算出し、その差分が例えば“１０”であった場合には、１０分の１の確率で現ラベル配置パターン７３０をラベル配置パターン候補７４０で更新するといったように、現総ペナルティ７５０と候補総ペナルティ７６０との差分に従って確度を決定する。尚、この更新を決定する確率の決定方法は、適宜に設定して良く、現総ペナルティ７５０の候補総ペナルティ７６０に対する比に従って決定することとしてもよい。
【００６５】
このように、現ラベル配置パターン７３０よりもラベル配置パターン候補７４０の方が低評価であった場合にも、所定の確率に従って現ラベル配置パターン７３０をラベル配置パターン候補７４０で更新することで、現ラベル配置パターン７３０が局所最適解となることを防ぐ。そして、確率的局所探索処理において現ラベル配置パターン７３０を随時更新していくことにより、より最適なラベル配置パターンを探索することとなる。
【００６６】
次に、列車ダイヤ図生成装置１の具体的な処理を、図１２〜１４の列車ダイヤ図を参照しつつ、図９〜１１のフローチャートを用いて説明する。
【００６７】
先ず、ＣＰＵ１０は、列車ダイヤ図生成処理を開始すると、ユーザにより指定される配置指定駅間７００と指定駅間内ラベルポジション数７１０とをＲＡＭ７０に入力・記憶する（ステップＡ１）。そして、列車ダイヤデータ６００に基づいて、図１２（ａ）のように駅線Ｌａ、Ｌｂ及びＬｃが表された列車ダイヤ図ＦＧ上に列車スジＧＦ１、ＧＦ２、ＧＦ３及びＧＦ４を作成する（ステップＡ３）。
【００６８】
次いで、図１２（ａ）のように各列車スジに対してラベルポジションＴＬＰ１、ＴＬＰ２、ＴＬＰ３及びＴＬＰ４を生成した後（ステップＡ５）、ＣＰＵ１０は、列車ダイヤデータ６００に基づいて、ステップＡ３で作成した列車スジに対して番線名ラベル（例えば、図１２（ｂ）の番線名ラベルＨＲ１）を配置する（ステップＡ７、図１２（ｂ）参照）。このとき、列車ラベルの配置に先だって、付帯情報記号である番線名ラベルを配置するのは、列車ラベルの探索空間を狭め、処理全体の高速化を図るためである。
【００６９】
そして、ステップＡ５で生成した列車スジ毎のラベルポジションに対して、所定位置に列車ラベルを仮配置して、現ラベル配置パターン７３０を生成する（ステップＡ９）。ここで、列車ラベルを配置する位置は、一般に視認性が良いとされる列車ラベルの配置位置（配置推奨位置）とし、例えば、図１３（ａ）のように駅線Ｌａと駅線Ｌｂのラベルポジション番号が“２”となるラベルポジションとする。
【００７０】
現ラベル配置パターン７３０の生成後、ＣＰＵ１０は、確率的局所探索処理（ステップＡ１１）を所定回数（例えば、３０００回）繰り返し実行する。そして、所定回数繰り返したと判定した場合には、次の処理へ移行する。尚、この確率的局所探索処理から次の処理への移行を判定する判定条件は、これに限られるものではなく、例えば、現総ペナルティ７５０が所定の値（例えば、１５，０００）以下となったか否かを判定条件とするとしてもよい。
【００７１】
ＣＰＵ１０は、確率的局所探索処理を開始すると、列車ダイヤ図ＦＧ中の列車スジをランダムに選択する（ステップＡ１０１）。そして、選択した列車スジに配置された列車ラベルの配置位置を移行候補位置に変更して（ステップＡ１０３）、ラベル配置パターン候補７４０を生成する（ステップＡ１０５）。例えば、図１３（ａ）においては、列車スジＧＦ１を選択して、その列車スジＧＦ１に配置されている列車ラベルＴＲ１を図１３（ｂ）のように変更する。
【００７２】
そして、ＣＰＵ１０は、現ラベル配置パターン７３０に基づいて現総ペナルティ７５０を算出し、次いで、ラベル配置パターン候補７４０に基づいて候補総ペナルティ７６０を算出する（ステップＡ１０７〜Ａ１０９）。
【００７３】
例えば、現ラベル配置パターン７３０で配置される図１３（ａ）の列車ラベルにおいては、列車ラベルＴＲ１〜ＴＲ４全てのラベルポジション番号が“２”となり、絶対位置ペナルティＳ１は“０”となる。また、駅線交差ペナルティＳ２は、列車ラベルＴＲ１〜ＴＲ４の全てが駅線Ｌｂと交差しているので“４α”と設定される。列車スジ交差ペナルティＳ３は、列車ラベルＴＲ１及び列車ラベルＴＲ２それぞれが列車スジＧＦ３と、列車ラベルＴＲ３が列車スジＧＦ２と交差しているので、“３β”と設定される。動的ペナルティであるラベル接触ペナルティＤ１は、列車ラベルＴＲ１及びＴＲ４それぞれが他の列車ラベルと一箇所で交差・接触し（ペナルティ値“θ”）、列車ラベルＴＲ２及びＴＲ３それぞれが他の列車ラベルと二箇所で互いに交差・接触している（ペナルティ値“２θ”）ので、“６θ（＝θ＋２θ＋２θ＋θ）”と設定される。水平位置ペナルティＤ２は、下り列車の列車ラベルＴＲ１及びＴＲ２と、上り列車の列車ラベルＴＲ３及びＴＲ４とはそれぞれ時間軸方向に水平に揃っているので“０”と設定される。最後に、密集ペナルティＤ３は、区画ＡＲ１〜４内に配置された列車ラベルの個数をカウントした後、上述した算出方法に基づいて“４”と算出される。ＣＰＵ１０は、これらのペナルティ値を元に式（ｃ）を用いて現総ペナルティ７５０を算出する。
【００７４】
同様にして、ラベル配置パターン候補７４０で配置される図１３（ｂ）の列車ラベルにおいても、静的ペナルティと動的ペナルティとを算出した後、候補総ペナルティ７６０を算出する。
【００７５】
このように算出して現総ペナルティ７５０と候補総ペナルティ７６０とをＣＰＵ１０は比較する（ステップＡ１１１）。そして、現総ペナルティ７５０が候補総ペナルティ７６０よりも大きい場合は、ラベル配置パターン候補７４０で現ラベル配置パターン７３０を更新した後（ステップＡ１１３）、列車ダイヤ図生成処理へ戻る。
【００７６】
図１３においては、図１３（ｂ）の総ペナルティ（候補総ペナルティ７６０）が図１３（ａ）の総ペナルティ（現総ペナルティ７５０）よりも小さいと判定されて、現ラベル配置パターン７３０は、図１３（ｂ）の列車ラベルの配置パターンに更新される。
【００７７】
ＣＰＵ１０は、確率的局所探索処理において、現総ペナルティ７５０が候補総ペナルティ７６０以下であると判定した場合は、現ラベル配置パターン７３０の更新の是非を上述したように確率的に決定する（ステップＡ１１５）。そして、現ラベル配置パターン７３０を更新すると決定した場合は（ステップＡ１１５：更新する）、ステップＡ１１３の処理へ移行してラベル配置パターン候補７４０で現ラベル配置パターン７３０を更新した後（ステップＡ１１５→Ａ１１３）、列車ダイヤ図生成処理へ戻る。また、現ラベル配置パターン７３０を更新しないと決定した場合は（ステップＡ１１５：更新しない）、現ラベル配置パターン７３０は保持したまま列車ダイヤ図生成処理に戻る。
【００７８】
例えば、図１３（ｂ）の列車ダイヤ図ＦＧの列車スジの中から列車スジＧＦ４を選択して、列車スジＧＦ４に配置される列車ラベルＴＲ４を図１４（ａ）のように配置することで、ラベル配置パターン候補７４０を生成する。ＣＰＵ１０は、図１３（ｂ）における現総ペナルティ７５０と、図１４（ａ）における候補総ペナルティ７６０とを算出する。このとき、候補総ペナルティ７６０が現総ペナルティ７５０よりも大きくなり、図１４（ａ）のラベル配置パターンが、図１３（ｂ）のラベル配置パターンよりも悪くなったとする。この際、例えば、候補総ペナルティ７６０と現総ペナルティ７５０との差分が“１０”であった場合は、１０分の１の確率で現ラベル配置パターン７３０をラベル配置パターン候補７４０で更新する。これにより、列車ラベルの配置パターンが局所的な最適解となってしまうことを避け、図１４（ｂ）の列車ダイヤ図ＦＧのような最適な列車ダイヤ図を得ることができる。
【００７９】
ここで、図９の列車ダイヤ図生成処理に立ち返ると、ＣＰＵ１０は、確率的局所探索処理を所定回数繰り返したと判定した場合は（ステップＡ１３：Ｙｅｓ）、フォントサイズ変更処理を開始する（ステップＡ１５）。
【００８０】
ＣＰＵ１０は、フォントサイズ変更処理を開始すると、列車ラベル相互間で重なりあっている列車ラベルを検出する（ステップＡ２０１）。そして、検出した列車ラベル全てに対して以下の処理を行う。先ず、現ラベル配置パターン７３０を元に現総ペナルティ７５０を算出する（ステップＡ２０５）。そして、検出した列車ラベルのサイズを他の列車ラベルよりも小さいサイズ（例えば、４分の３程度小さいサイズ）に縮小して仮変更し、その仮変更した際の総ペナルティを算出する（ステップＡ２０７〜Ａ２０９）。尚、この変更するサイズは、ある程度の視認性が保たれるサイズとする。
【００８１】
続いて、ＣＰＵ１０は、現総ペナルティ７５０がステップＡ２０９で算出した総ペナルティ（算出総ペナルティ）よりも大きいか否かを判定する（ステップＡ２１１）。現総ペナルティ７５０が算出総ペナルティよりも大きいと判定した場合は、列車ラベルのサイズをステップＡ２０７で仮変更したサイズに決定した後、総ペナルティが最小となるラベルポジションに当該列車ラベルの配置位置を変更する（ステップＡ２１１→Ａ２１３〜Ａ２１５）。また、現総ペナルティ７５０が算出総ペナルティ以下であると判定した場合は、列車ラベルのサイズをステップＡ２０７での変更前のサイズに戻す（ステップＡ２１１→Ａ２１７）。これは、総ペナルティが小さくならない、即ち、他の列車ラベルとの重なりが解消されないのであれば、わざわざ列車ラベルのサイズを小さくする必要がないからである。
【００８２】
ステップＡ２１５又はＡ２１７の処理後、ステップＡ２０１で検出した列車ラベル全てに対してステップＡ２０５〜Ａ２１７の処理を実行したかを判定し、実行したと判定した場合は、列車ダイヤ図生成処理へ戻る。そして、ＣＰＵ１０は、フォントサイズ変更処理の終了後、列車ダイヤ図生成処理を終了する。
【００８３】
尚、ステップＡ２０１において列車ラベルを検出する縮小化条件は、他の列車ラベルと重なっているか否かだけでなく、例えば、列車スジや駅線と重なっているか否かといった上述した第２のルールを満たすか否かの条件としてもよい。
【００８４】
このフォントサイズ変更処理によって、例えば、ステップＡ１５の直前において生成された列車ダイヤ図が図１４（ａ）の状態の列車ダイヤ図であった場合に、列車ラベル同士が重なり合う列車ラベルＴＲ３と列車ラベルＴＲ２のうちの、例えば列車ラベルＴＲ２のサイズを一回り小さくする。このときに、列車ラベルＴＲ３との重なりが解消されたなら、列車ラベルＴＲ２のサイズを一回り小さいサイズに決定して、更に総ペナルティが最小となるラベルポジションに再配置する。そして、列車ラベルＴＲ２と重なっていた列車ラベルＴＲ３においても重なりは解消されたため、列車ラベルＴＲ３のサイズは変更する必要がない。このため、重なりのある列車ラベル全てのサイズを縮小変更して、更に視認性を低下させることがない。また、列車ラベルのサイズを小さくして、総ペナルティが最小となる位置に再配置できれば、列車ダイヤ図の視認性の更なる向上が期待される。
【００８５】
以上、本実施形態によれば、列車ダイヤ図生成装置１は、現ラベル配置パターン７３０とラベル配置パターン候補７４０との総ペナルティを比較して、ラベル配置パターン候補７４０の方が高評価であれば、現ラベル配置パターン７３０を更新するが、低評価であった場合も、確率的にラベル配置パターン候補７４０で現ラベル配置パターン７３０を更新する。この一連となる確率的局所探索処理を繰り返すことにより、遺伝的アルゴリズムに替わる手法で列車ラベルの最適な配置位置を求めることができる。
【００８６】
図１５は、大都市近郊のラッシュ時の時間帯を含む列車ダイヤ図を、一般的なパソコンを用いて上述した確率的局所探索処理により生成した際の実行結果と、同一の列車ダイヤ図を遺伝的アルゴリズムにより生成した際の実行結果とを示す図である。同図によれば、結果として得られた総ペナルティは、ほぼ同じであるが、計算に要する時間には大きな違いが生じており、明らかに確率的局所探索のほうが高速に列車ダイヤ図を生成できることが分かる。このため、確率的局所探索による手法が、遺伝的アルゴリズムによる手法よりもより実用的な手法であると言える。
【００８７】
〔変形例〕
尚、上述した実施形態は、列車ラベルの最適な配置位置を探索するために確率的局所探索処理を行うこととしたが、例えば、番線名等のダイヤ図付帯情報記号の最適な配置位置を探索するために確率的局所探索処理を行うこととしてもよい。以下、番線名ラベルの最適な配置位置を探索するために確率的局所探索処理を行う場合の変形例を説明する。
【００８８】
先ず、番線名ラベルの配置可能位置である番線名ラベルポジションについて説明する。番線名ラベルポジションは、番線名ラベルの仮配置に先立って、上述した実施形態と同様に当該番線名ラベルに対応する列車の列車スジに対して生成する。このとき、配置指定駅間７００の駅間の２分の１の範囲に番線名ラベルポジションを生成する。また、着駅の番線名ラベルの番線名ラベルポジションは着駅側、発駅の番線名ラベルの番線名ラベルポジションは発駅側に生成する。
【００８９】
例えば、図１６において、配置指定駅間７００が「駅Ａ〜Ｂ」である場合、駅線Ｌａ６００と駅線Ｌｂ６００との間を２分の１に分割する。そして、列車スジＧＦ６００は、上り列車の列車スジであり着駅は駅Ａであるので、このとき、分割した領域のうち駅線Ｌａ６００側の領域ＡＲ６００内に番線名ラベルポジションＨＬＰ６００を例えば３つ生成する。番線名ラベルポジションをこのように生成することで、駅Ａでの着番線名ラベルが駅Ｂの発番線名ラベルと誤認されることを防ぐ。
【００９０】
また、例えば、図１６の列車スジＧＦ６１０のように駅Ａが終着駅の場合は、上述した方法と同様に、駅線Ｌａ６００の下側に番線名ラベルポジションＨＬＰ６１２を生成するだけではなく、駅線Ｌａ６００の上側にも１つ番線名ラベルポジションＨＬＰ６１４を生成する。これは、終着駅の場合、駅線Ｌａ６００の上側に配置した着番線名ラベルが発番線名ラベルと誤認されることがなく、また、空間的にも余裕がある場合が多いからである。この終着駅における番線名ラベルポジションの生成は、始発駅における場合も同様の方法で適用可能であることは無論である。
【００９１】
上述したように番線名ラベルポジションを生成した後、ＣＰＵ１０は、その番線名ラベルポジションに番線名ラベルを仮配置して、番線名ラベルに係る現ラベル配置パターンを生成する。また、上述した実施形態と同様に、現ラベル配置パターンを元にラベル配置パターン候補を生成する。そして、ＣＰＵ１０は、番線名ラベルに係る現ラベル配置パターン及びラベル配置パターン候補それぞれの総ペナルティを算出・比較して、確率的局所探索処理を繰り返すことで、番線名ラベルの最適な配置位置を求める。
【００９２】
尚、この場合の静的ペナルティとしては、番線名ラベルに係る絶対位置ペナルティ（番線名ラベルポジションの絶対位置よるペナルティ値）、駅線交差ペナルティ（番線名ラベルが駅線と交差したか否かによるペナルティ値）及び列車スジ交差ペナルティ（番線名ラベルが列車スジと交差したか否かによるペナルティ値）とがあり、上述した列車ラベルの静的ペナルティと同様に求める。また、動的ペナルティとしては、番線名ラベルに係るラベル接触ペナルティ（番線名ラベル同士が重なっているか否かによるペナルティ値）があり、これも上述した列車ラベルのラベル接触ペナルティと同様に求める。
【００９３】
以上のように、確率的局所探索処理によるラベルの最適な配置位置を求める手法は、列車ラベルだけではなく、番線名ラベル等の付帯情報記号にも適用可能である。
【００９４】
尚、本実施形態において、列車ダイヤ生成装置に本発明を適用することとして説明したが、本発明の適用可能なものはこれに限られるものではない。対象線（本実施形態の列車スジ）があって、その対象線に対してラベル（本実施形態の列車ラベル）を配置するものであれば、何れのものに対しても適用可能である。例えば、道路や河川といった地図、航路といった航行図等に対して本発明を適用してもよい。より具体的には、道路等を本実施形態の列車スジとし、道路等の名称を本実施形態の列車ラベルとすることにより、実現することが可能である。
【図面の簡単な説明】
【００９５】
【図１】列車ダイヤ図の一例を示す図。
【図２】列車ダイヤ図生成装置の機能構成の一例を示すブロック図。
【図３】列車ダイヤデータのデータ構成の一例を示す図。
【図４】ラベルポジションの生成を説明するための図。
【図５】ラベルポジション座標値テーブルのデータ構成の一例を示す図。
【図６】現ラベル配置パターンのデータ構成の一例を示す図。
【図７】水平位置ペナルティを説明するための図。
【図８】密集ペナルティを説明するための図。
【図９】列車ダイヤ図生成処理を説明するためのフローチャート。
【図１０】確率的局所探索処理を説明するためのフローチャート。
【図１１】フォントサイズ変更処理を説明するためのフローチャート。
【図１２】列車ダイヤ図生成処理の具体的な処理を説明するための第１の図。
【図１３】列車ダイヤ図生成処理の具体的な処理を説明するための第２の図。
【図１４】列車ダイヤ図生成処理の具体的な処理を説明するための第３の図。
【図１５】列車ダイヤ図を遺伝的アルゴリズム及び確率的局所探索それぞれで生成した場合の実行結果を比較するための図。
【図１６】変形例における番線名ラベルポジションを説明するための図。
【符号の説明】
【００９６】
１     列車ダイヤ図生成装置
１０   ＣＰＵ
２０   入力装置
３０   表示装置
４０   ＲＯＭ
５０   記憶装置
６０   記憶媒体
６００ 列車ダイヤデータ
６１０ 列車ダイヤ図生成プログラム
６１２ 確率的局所探索プログラム
６１４ フォントサイズ変更プログラム
７０   ＲＡＭ
７００ 配置指定駅間
７１０ 指定駅間内ラベルポジション数
７２０ ラベルポジション座標値テーブル
７３０ 現ラベル配置パターン
７４０ ラベル配置パターン候補
７５０ 現総ペナルティ
７６０ 候補総ペナルティ
８０   バス
【図１】
2006069278.tif 000004
【図２】
2006069278.tif 000005
【図３】
2006069278.tif 000006
【図４】
2006069278.tif 000007
【図５】
2006069278.tif 000008
【図６】
2006069278.tif 000009
【図７】
2006069278.tif 000010
【図８】
2006069278.tif 000011
【図９】
2006069278.tif 000012
【図１０】
2006069278.tif 000013
【図１１】
2006069278.tif 000014
【図１２】
2006069278.tif 000015
【図１３】
2006069278.tif 000016
【図１４】
2006069278.tif 000017
【図１５】
2006069278.tif 000018
【図１６】
2006069278.tif 000019