(57)【要約】【課題】固定路線バスとデマンドバスとのメリット／デメリットを解析し、都市規模や運行台数とバス運行方式との関係を客観的に評価することのできる、新しいバス運行形態評価方法、ならびにバス運行形態評価プログラムおよび該プログラムを記録したコンピュータ読み取り可能な記録媒体を提供する。【解決手段】中央処理手段（１）が、固定路線バスにおける、出発地から目的地まで乗り換えなしで到達する場合の要求発生時間から要求達成時間までの平均時間が最小となる最適路線配置を、近似解探索手法により求め、且つ、デマンドバスにおける、出発地から目的地まで乗り換えなしで到達する場合の要求発生時間から要求達成時間までの平均時間が最小となる最適デマンド配分を、上記と同一の採算性条件の下に、近似解探索手法により求める。【選択図】  図１
2004287484.tif 000002
【特許請求の範囲】
【請求項１】
処理手段が、固定路線バスにおける、出発地から目的地まで乗り換えなしで到達する場合の要求発生時間から要求達成時間までの平均時間が最小となる最適路線配置を、近似解探索手法により求めるステップ、および
処理手段が、デマンドバスにおける、出発地から目的地まで乗り換えなしで到達する場合の要求発生時間から要求達成時間までの平均時間が最小となる最適デマンド配分を、上記ステップと同一の採算性条件の下に、近似解探索手法により求めるステップ、
を含むことを特徴とするバス運行形態評価方法。
【請求項２】
処理手段が固定路線バスの最適路線配置を近似解探索手法により求める前記ステップにおいて、
処理手段が、記憶手段に記憶されている平均時間式：
【数１】
2004287484.tif 000005
を用いて前記平均時間を算出する、
ことを特徴とする請求項１記載のバス運行形態評価方法。
【請求項３】
処理手段が固定路線バスの最適路線配置を近似解探索手法により求める前記ステップにおいて、該近似解探索手法が遺伝的アルゴリズムであり、
処理手段がデマンドバスの最適デマンド配分を近似解探索手法により求める前記ステップにおいて、該近似解探索手法が逐次最適挿入法である、
ことを特徴とする請求項１または２記載のバス運行形態評価方法。
【請求項４】
処理手段が固定路線バスの最適路線配置を遺伝的アルゴリズムにより求める前記ステップに、
処理手段が、任意の２つの交差点をランダムに選択し、選択された２つの交差点を結ぶＬの字型路線およびロの字型路線のいずれかを確率的に選択することで、遺伝的アルゴリズムの世代交代処理を行うステップ、
を含むことを特徴とする請求項３記載のバス運行形態評価方法。
【請求項５】
処理手段が固定路線バスの最適路線配置を遺伝的アルゴリズムにより求める前記ステップに、
処理手段が、記憶手段に記憶されている、隣り合う交差点を経路が直接結んでいる場合に該経路をコの字状に迂回する経路に変換する突然変異パターンと、ある街区の対角線位置にある交差点をＬの字状に経路が結んでいる場合に該経路を逆Ｌの字の経路に変換する突然変異パターンと、ターミナル駅を１ブロック移動して経路を伸縮させる突然変異パターンとを用いて、遺伝的アルゴリズムの突然変異処理を行うステップ、
を含むことを特徴とする請求項３記載のバス運行形態評価方法。
【請求項６】
処理手段が固定路線バスの最適路線配置を遺伝的アルゴリズムにより求める前記ステップに、
処理手段が、記憶手段に記憶されている、隣り合う交差点を経路が直接往復している場合に該経路を縮退させる突然変異パターンをさらに用いて、遺伝的アルゴリズムの突然変異処理を行うステップ、
を含むことを特徴とする請求項５記載のバス運行形態評価方法。
【請求項７】
処理手段が固定路線バスの最適路線配置を遺伝的アルゴリズムにより求める前記ステップに、
処理手段が、記憶手段に記憶されている交差確率で各路線を他の固体の路線と置き換えることで、遺伝的アルゴリズムの交差処理を行うステップ、
を含むことを特徴とする請求項３記載のバス運行形態評価方法。
【請求項８】
処理手段がデマンドバスの最適デマンド配分を逐次最適挿入法により求める前記ステップに、
処理手段が、各バスをデマンドの出発地点と目的地点に分割し、且つこれらの経由地点のリストとして配分されたデマンドを保持するものとし、各バスが各経由地点に到達した場合に該経由地点をリストから取り除くステップ、
処理手段が、各バスの各時点におけるデマンドの達成予定時刻を算出するステップ、
処理手段が、新たにデマンドが発生した際に各バスについてデマンドの出発地点および目的地点を現在の経由地点リストの任意の場所に挿入し、全経由地点における該挿入により生じる遅延の総和を、前記算出された達成予定時刻と比較して求めるステップ、
処理手段が、新しいデマンドの達成予定時間を求め、該達成予定時間と前記求められた遅延の総和を挿入のコストとするステップ、
処理手段が、出発地点と目的地点の挿入場所のペアのすべての組合せについて、前記コストが最小となるペアを、デマンドの受け入れ候補とするステップ、および
処理手段が、すべてのバスについて前記受け入れ候補を求め、前記コストが最も小さくなるバスにそのデマンドを配分するステップ、
を含むことを特徴とする請求項３記載のバス運行形態評価方法。
【請求項９】
固定路線バスおよびデマンドバスの運行形態を評価するためにコンピュータを、
固定路線バスにおける、出発地から目的地まで乗り換えなしで到達する場合の要求発生時間から要求達成時間までの平均時間が最小となる最適路線配置を、近似解探索手法により求める処理手段、および
デマンドバスにおける、出発地から目的地まで乗り換えなしで到達する場合の要求発生時間から要求達成時間までの平均時間が最小となる最適デマンド配分を、上記処理と同一の採算性条件の下に、近似解探索手法により求める処理手段、として機能させることを特徴とするバス運行形態評価プログラム。
【請求項１０】
固定路線バスの最適路線配置を近似解探索手法により求める前記処理手段において、
記憶手段に記憶されている平均時間式：
【数２】
2004287484.tif 000006
を用いて前記平均時間を算出する、
ことを特徴とする請求項９記載のバス運行形態評価プログラム。
【請求項１１】
固定路線バスの最適路線配置を近似解探索手法により求める前記処理手段において、該近似解探索手法が遺伝的アルゴリズムであり、
デマンドバスの最適デマンド配分を近似解探索手法により求める前記処理手段において、該近似解探索手法が逐次最適挿入法である、
ことを特徴とする請求項９または１０記載のバス運行形態評価プログラム。
【請求項１２】
固定路線バスの最適路線配置を遺伝的アルゴリズムにより求める前記処理手段に、
任意の２つの交差点をランダムに選択し、選択された２つの交差点を結ぶＬの字型路線およびロの字型路線のいずれかを確率的に選択することで、遺伝的アルゴリズムの世代交代処理を行う処理手段、
を含むことを特徴とする請求項１１記載のバス運行形態評価プログラム。
【請求項１３】
固定路線バスの最適路線配置を遺伝的アルゴリズムにより求める前記処理手段に、
記憶手段に記憶されている、隣り合う交差点を経路が直接結んでいる場合に該経路をコの字状に迂回する経路に変換する突然変異パターンと、ある街区の対角線位置にある交差点をＬの字状に経路が結んでいる場合に該経路を逆Ｌの字の経路に変換する突然変異パターンと、ターミナル駅を１ブロック移動して経路を伸縮させる突然変異パターンとを用いて、遺伝的アルゴリズムの突然変異処理を行う処理手段、
を含むことを特徴とする請求項１１記載のバス運行形態評価プログラム。
【請求項１４】
固定路線バスの最適路線配置を遺伝的アルゴリズムにより求める前記処理手段に、
記憶手段に記憶されている、隣り合う交差点を経路が直接往復している場合に該経路を縮退させる突然変異パターンをさらに用いて、遺伝的アルゴリズムの突然変異処理を行う処理手段、
を含むことを特徴とする請求項１３記載のバス運行形態評価プログラム。
【請求項１５】
固定路線バスの最適路線配置を遺伝的アルゴリズムにより求める前記処理手段に、
記憶手段に記憶されている交差確率で各路線を他の固体の路線と置き換えることで、遺伝的アルゴリズムの交差処理を行う処理手段、
を含むことを特徴とする請求項１１記載のバス運行形態評価プログラム。
【請求項１６】
デマンドバスの最適デマンド配分を逐次最適挿入法により求める前記処理手段に、
各バスをデマンドの出発地点と目的地点に分割し、且つこれらの経由地点のリストとして配分されたデマンドを保持するものとし、各バスが各経由地点に到達した場合に該経由地点をリストから取り除く処理手段、
各バスの各時点におけるデマンドの達成予定時刻を算出する処理手段、
新たにデマンドが発生した際に各バスについてデマンドの出発地点および目的地点を現在の経由地点リストの任意の場所に挿入し、全経由地点における該挿入により生じる遅延の総和を、前記算出された達成予定時刻と比較して求める処理手段、
新しいデマンドの達成予定時間を求め、該達成予定時間と前記求められた遅延の総和を挿入のコストとする処理手段、
出発地点と目的地点の挿入場所のペアのすべての組合せについて、前記コストが最小となるペアを、デマンドの受け入れ候補とする処理手段、および
すべてのバスについて前記受け入れ候補を求め、前記コストが最も小さくなるバスにそのデマンドを配分する処理手段、
を含むことを特徴とする請求項１１記載のバス運行形態評価プログラム。
【請求項１７】
固定路線バスおよびデマンドバスの運行形態を評価するためにコンピュータを、
固定路線バスにおける、出発地から目的地まで乗り換えなしで到達する場合の要求発生時間から要求達成時間までの平均時間が最小となる最適路線配置を、近似解探索手法により求める処理手段、および
デマンドバスにおける、出発地から目的地まで乗り換えなしで到達する場合の要求発生時間から要求達成時間までの平均時間が最小となる最適デマンド配分を、上記処理と同一の採算性条件の下に、近似解探索手法により求める処理手段、として機能させることを特徴とするバス運行形態評価プログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項１８】
固定路線バスの最適路線配置を近似解探索手法により求める前記処理手段において、
記憶手段に記憶されている平均時間式：
【数３】
2004287484.tif 000007
を用いて前記平均時間を算出する、
ことを特徴とする請求項１７記載のバス運行形態評価プログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項１９】
固定路線バスの最適路線配置を近似解探索手法により求める前記処理手段において、該近似解探索手法が遺伝的アルゴリズムであり、
デマンドバスの最適デマンド配分を近似解探索手法により求める前記処理手段において、該近似解探索手法が逐次最適挿入法である、
ことを特徴とする請求項１７または１８記載のバス運行形態評価プログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項２０】
固定路線バスの最適路線配置を遺伝的アルゴリズムにより求める前記処理手段に、
任意の２つの交差点をランダムに選択し、選択された２つの交差点を結ぶＬの字型路線およびロの字型路線のいずれかを確率的に選択することで、遺伝的アルゴリズムの世代交代処理を行う処理手段、
を含むことを特徴とする請求項１９記載のバス運行形態評価プログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項２１】
固定路線バスの最適路線配置を遺伝的アルゴリズムにより求める前記処理手段に、
記憶手段に記憶されている、隣り合う交差点を経路が直接結んでいる場合に該経路をコの字状に迂回する経路に変換する突然変異パターンと、ある街区の対角線位置にある交差点をＬの字状に経路が結んでいる場合に該経路を逆Ｌの字の経路に変換する突然変異パターンと、ターミナル駅を１ブロック移動して経路を伸縮させる突然変異パターンとを用いて、遺伝的アルゴリズムの突然変異処理を行う処理手段、
を含むことを特徴とする請求項１９記載のバス運行形態評価プログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項２２】
固定路線バスの最適路線配置を遺伝的アルゴリズムにより求める前記処理手段に、
記憶手段に記憶されている、隣り合う交差点を経路が直接往復している場合に該経路を縮退させる突然変異パターンをさらに用いて、遺伝的アルゴリズムの突然変異処理を行う処理手段、
を含むことを特徴とする請求項２１記載のバス運行形態評価プログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項２３】
固定路線バスの最適路線配置を遺伝的アルゴリズムにより求める前記処理手段に、
記憶手段に記憶されている交差確率で各路線を他の固体の路線と置き換えることで、遺伝的アルゴリズムの交差処理を行う処理手段、
を含むことを特徴とする請求項１９記載のバス運行形態評価プログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項２４】
デマンドバスの最適デマンド配分を逐次最適挿入法により求める前記処理手段に、
各バスをデマンドの出発地点と目的地点に分割し、且つこれらの経由地点のリストとして配分されたデマンドを保持するものとし、各バスが各経由地点に到達した場合に該経由地点をリストから取り除く処理手段、
各バスの各時点におけるデマンドの達成予定時刻を算出する処理手段、
新たにデマンドが発生した際に各バスについてデマンドの出発地点および目的地点を現在の経由地点リストの任意の場所に挿入し、全経由地点における該挿入により生じる遅延の総和を、前記算出された達成予定時刻と比較して求める処理手段、
新しいデマンドの達成予定時間を求め、該達成予定時間と前記求められた遅延の総和を挿入のコストとする処理手段、
出発地点と目的地点の挿入場所のペアのすべての組合せについて、前記コストが最小となるペアを、デマンドの受け入れ候補とする処理手段、および
すべてのバスについて前記受け入れ候補を求め、前記コストが最も小さくなるバスにそのデマンドを配分する処理手段、
を含むことを特徴とする請求項１９記載のバス運行形態評価プログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この出願の発明は、バス運行形態評価方法、ならびにバス運行形態評価プログラムおよび該プログラムを記録したコンピュータ読み取り可能な記録媒体に関するものである。さらに詳しくは、この出願の発明は、固定路線バスおよびデマンドバスの運行形態の客観的評価に有用な、新しいバス運行形態評価方法、ならびにバス運行形態評価プログラムおよび該プログラムを記録したコンピュータ読み取り可能な記録媒体に関するものである。
【０００２】
【従来の技術】
一定の路線の決められた停留所で乗客を乗降させる通常の固定路線バスに対し、乗客の要望に応じて乗降場所を自由に変更できるバスの運営形態はデマンドバスと呼ばれている。固定路線バスの場合、人口が比較的少なく、市域が平面的に広がる地域では、採算性の面から路線数や運用台数を十分に増やすことができず、利便性の確保が難しく、それにより利用者が減って採算性が悪化するという悪循環が生じやすい。このような状況に歯止めをかけるため、少ない運用台数で利便性を確保できるデマンドバスの運用を検討する自治体が増えてきている。
【０００３】
デマンドバスの形態には、
・あらかじめ決められた路線に幅を持たせ、デマンドに応じてその幅内で寄り道をしてくれる「寄り道タイプ」
・観光地やショッピングセンター、市役所など利用の可能性の高い場所に停留候補地を設け、その候補地におけるデマンドを処理するよう経路を決める「セミデマンドタイプ」
・町中のあらゆる場所を出発地／目的地としてデマンドを出すことができる「フルデマンドタイプ」
などいくつかのタイプがある。現状ではデマンドを受けるシステム構築の難しさから、寄り道タイプあるいはセミデマンドタイプが主流であるが、携帯電話など情報インフラの普及によりデマンドの情報をきめ細かく収集することが容易になってきており、フルデマンドバスの導入も比較的現実的な解となってきている。
【０００４】
このデマンドバスについては、巡回セールスマン問題（非特許文献２、１４参照）や車輛配送問題（非特許文献３、１９、２３，２４，２７参照）から派生した問題であるＤｉａｌ−ａ−Ｒｉｄｅ  Ｐｒｏｂｌｅｍ（非特許文献４，３３参照）におけるスケジューリングの最適化アルゴリズムに関する技術が種々提案されており、主に以下のような分類に分けることができる。
【０００５】
・運行車両に関する制約条件による違い：単数あるいは複数の運行台数による変化（非特許文献６、２０〜２２、２７、３０参照）、乗車定員に制限がある場合の配車（非特許文献４、１５参照）、および乗り換えの有無による比較（非特許文献３１参照）
・オンライン、オフラインアルゴリズム（非特許文献１、６、７、９参照）
・荷物などの収集、配送に一定の時間制約を加えた問題（非特許文献１、１３、１９、２１参照）
・環境に対する条件  ：基幹交通網との結合（非特許文献１２、３２、３３）、対象領域（地域）の規模（非特許文献８、２８、２９参照）、交通状況の考慮（非特許文献９、１８参照）
これら従来のデマンドバスＤｉａｌ−ａ−Ｒｉｄｅ  Ｐｒｏｂｌｅｍにおける最適化アルゴリズムの多くは、ｌｏｃａｌ  ｓｅａｒｃｈ（非特許文献１１参照）やｔａｂ  ｓｅａｒｃｈ（非特許文献５参照）、ｓｉｍｕｌａｔｅｄ  ａｎｎｅａｌｉｎｇ（非特許文献２５，２６参照）、Ｇｅｎｅｔｉｃ  Ａｌｇｏｒｉｔｈｍ等の従来からある最適化アルゴリズムの応用が主になっている。また、Ｄｉａｌ−ａ−Ｒｉｄｅ  の計算可能性に関しては他の車輛配送問題と同様に  ＮＰ−ｈｅａｄであるとされている（非特許文献１０参照）。さらにデマンドバスではないが、工場などでの配送問題としての  Ｄｉａｌ−ａ−Ｒｉｄｅ  Ｐｒｏｂｌｅｍ  における効率や利益に関するものも提案されている（非特許文献１６参照）。
【０００６】
【非特許文献１】
Ｎｏｒｂｅｒｔ  Ａｓｃｈｅｕｅｒ，  Ｓｖｅｎ  Ｏ．  Ｋｒｕｍｋｅ，  ａｎｄ  Ｊｏｒｇ  Ｒａｍｂａｕ，  ”Ｏｎｌｉｎｅ  ｄｉａｌ−        ａ−ｒｉｄｅ  ｐｒｏｂｌｅｍｓ：  Ｍｉｎｉｍｉｚｉｎｇ  ｔｈｅ  ｃｏｍｐｌｅｔｉｏｎ  ｔｉｍｅ，”  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ          ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，  １７７０：６３９−６５０，  ２０００．
【非特許文献２】
Ｌ．  Ｂｉａｎｃｏ，  Ａ．  Ｍｉｎｇｏｚｚｉ，  Ｓ．  Ｒｉｃｃａｉａｒｄｅｌｌｉ，  ａｎｄ  Ｍ．  Ｓｐａｄｏｎｉ，  ”Ｅｘａｃｔ          ａｎｄ  ｈｅｕｒｉｓｔｉｃ  ｐｒｏｃｅｄｕｒｅｓ  ｆｏｒ  ｔｈｅ  ｔｒａｖｅｌｉｎｇ  ｓａｌｅｓｍａｎ  ｐｒｏｂｌｅｍ  ｗｉｔ        ｈ  ｐｒｏｃｅｄｅｎｃｅ  ｃｏｎｓｔｒａｉｎｔｓ，  ｂａｓｅｄ  ｏｎ  ｄｙｎａｍｉｃ  ｐｒｏｇｒａｍｍｉｎｇ，”ＩＮＦＯＲ，  ｖ        ｏｌ．３２，  ｐｐ．１９−３１，  １９９４．
【非特許文献３】
Ｌ．  Ｄ．  Ｂｏｄｉｎ，  Ｂ．  Ｌ．  Ｇｏｌｄｅｎ，  Ａ．  Ａｓｓａｄ，  ａｎｄ  Ｍ．  Ｏ．  Ｂａｌｌ，  ”Ｒｏｕｔｉｎｇ  ａｎ        ｄ  ｓｃｈｅｄｕｌｉｎｇ  ｏｆ  ｖｅｈｉｃｌｅｓ  ａｎｄ  ｃｒｅｗｓ：  ｔｈｅ  ｓｔａｔｅ  ｏｆ  ｔｈｅ  ａｒｔ，”Ｃｏｍｐｕｔ        ｅｒｓ  ａｎｄ  Ｏｐｅｒａｔｉｏｎ  Ｒｅｓｅａｒｃｈ，  １０：６３−２１１，  １９８３．
【非特許文献４】
Ｍｏｓｅｓ  Ｃｈａｒｉｋａｒ  ａｎｄ  Ｂａｌａｊｉ  Ｒａｇｈａｖａｃｈａｒｉ，  ”Ｔｈｅ  ｆｉｎｉｔｅ  ｃａｐａｃｉｔｙ  ｄｉａ        ｌ−ａ−ｒｉｄｅ  ｐｒｏｂｌｅｍ，”  ＩＥＥＥ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｆｏｕｎｄａｔｉｏｎｓ  ｏｆ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉ        ｅｎｃｅ，  ｐｐ．４５８−４６７，  １９９８．
【非特許文献５】
Ｊｅａｎ−Ｆｒａｎｃｏｉｓ  Ｃｏｒｄｅａｕ  ａｎｄ  Ｇｉｌｂｅｒｔ  Ｌａｐｏｒｔｅ，  ”Ａ  Ｔａｂｕ  Ｓｅａｒｃｈ  Ｈｅｕｒｉｓ        ｔｉｃ  ｆｏｒ  ｔｈｅ  Ｓｔａｔｉｃ  Ｍｕｌｔｉ−Ｖｅｈｉｃｌｅ  Ｄｉａｌ−ａ−ＲｉｄｅＰｒｏｂｌｅｍ，”  Ｔｒａｎｓｐｏｒｔａ        ｔｉｏｎ  Ｒｅｓｅａｒｃｈ  Ｐａｒｔ  Ｂ：  Ｍｅｔｈｏｄｏｌｏｇｉｃａｌ，  ２００３．
【非特許文献６】
Ｅｓｔｅｂａｎ  Ｆｅｕｅｒｓｔｅｉｎ  ａｎｄ  Ｌｅｅｎ  Ｓｔｏｕｇｉｅ，  ”Ｏｎ−ｌｉｎｅ  ｓｉｎｇｌｅ−ｓｅｒｖｅｒ  ｄｉａｌ        −ａ−ｒｉｄｅ  ｐｒｏｂｌｅｍｓ，”  Ｔｈｅｏｒｅｔｉｃａｌ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，  ２６８（１）：９１−１０５，          ２００１．
【非特許文献７】
Ｍ．  Ｇｒｏｔｓｃｈｅｌ，  Ｄ．  Ｈａｕｐｔｍｅｉｅｒ，  Ｓ．  Ｋｒｕｍｋｅ，  ａｎｄ  Ｊ．  Ｒａｍｂａｕ，  ”Ｓｉｍｕｌａｔｉ        ｏｎ  ｓｔｕｄｉｅｓ  ｆｏｒ  ｔｈｅ  ｏｎｌｉｎｅ  ｄｉａｌ−ａ−ｒｉｄｅ−ｐｒｏｂｌｅｍ，”  Ｋｏｎｒａｄ−Ｚｕｓｅ−Ｚｅｎｔ        ｒｕｍ  ｆｕｒ  Ｉｎｆｏｒｍａｔｉｏｎｓｔｅｃｈｎｉｋ  Ｂｅｒｌｉｎ，  １９９９．
【非特許文献８】
Ａｌｉ  Ｈａｇｈａｎｉ  ａｎｄ  Ｍｏｈａｍａｄｒｅｚａ  Ｂａｎｉｈａｓｈｅｍｉ，  ”Ｈｅｕｒｉｓｔｉｃ  ａｐｒｏａｃｈｅｓ  ｆｏ        ｒ  ｓｏｌｖｉｎｇ  ｌａｒｇｅ−ｓｃａｌｅ  ｂｕｓ  ｔｒａｎｓｉｔ  ｖｅｈｉｃｌｅｓｃｈｅｄｕｌｉｎｇ  ｐｒｏｂｌｅｍ  ｗｉｔｈ          ｒｏｕｔｅ  ｔｉｍｅ  ｃｏｎｓｔｒａｉｎｔｓ，”Ｔｒａｎｓｐｏｒｔａｔｉｏｎ  Ｒｅｓｅａｒｃｈ  Ｐａｒｔ  Ａ：  Ｐｏｌｉｃｙ          ａｎｄ  Ｐｒａｃｔｉｃｅ，３６（４）：３０９−３３３，  ２００２．
【非特許文献９】
Ｄｉｅｔｒｉｃｈ  Ｈａｕｐｔｍｅｉｅｒ，  Ｓｖｅｎ  Ｏ．  Ｋｒｕｍｋｅ，  ａｎｄ  Ｊｏｒｇ  Ｒａｍｂａｕ，  ”Ｔｈｅ  ｏｎｌｉｎ        ｅ  ｄｉａｌ−ａ−ｒｉｄｅ  ｐｒｏｂｌｅｍ  ｕｎｄｅｒ  ｒｅａｓｏｎａｂｌｅ  ｌｏａｄ，”  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃ        ｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，  １７６７：１２５−１３３，  ２０００．
【非特許文献１０】
Ｄｉｅｔｒｉｃｈ  Ｈａｕｐｔｍｅｉｅｒ，  Ｓｖｅｎ  Ｏｌｉｖｅｒ  Ｋｒｕｍｋｅ，  Ｊｏｒｇ  Ｒａｍｂａｕ，  ａｎｄ  Ｈａｎｓ−Ｃ        ｈｒｉｓｔｏｐｈ  Ｗｉｒｔｈ，  ”Ｅｕｌｅｒ  ｉｓ  ｓｔａｎｄｉｎｇ  ｉｎ  ｌｉｎｅ  ｄｉａｌ−ａ−ｒｉｄｅ  ｐｒｏｂｌｅｍｓ          ｗｉｔｈｐｒｅｃｅｄｅｎｃｅ−ｃｏｎｓｔｒａｉｎｔｓ，”  Ｄｉｓｃｒｅｔｅ  Ａｐｐｌｉｅｄ  Ｍａｔｈｅｍａｔｉｃｓ，  １１３（１        ）：８７−１０７，  ２００１．
【非特許文献１１】
Ｐ．  Ｈｅａｌｙ  ａｎｄ  Ｒ．  Ｍｏｌｌ，  ”Ａ  ｎｅｗ  ｅｘｔｅｎｓｉｏｎ  ｏｆ  ｌｏｃａｌ  ｓｅａｒｃｈ  ａｐｐｌｉｅｄ  ｔ        ｏ  ｔｈｅ  ｄｉａｌ−ａ−ｒｉｄｅ  ｐｒｏｂｌｅｍ，”  Ｅｕｒｏｐｅａｎ  Ｊｏｕｒｎａｌ  ｏｆ  Ｏｐｅｒａｔｉｏｎｓ  Ｒｅｓｅａ        ｒｃｈ，  ８３：８３−１０４，  １９９５．
【非特許文献１２】
Ｍ．  Ｅ．  Ｔ．  Ｈｏｒｎ，  ”Ｍｕｌｔｉ−ｍｏｄａｌ  ａｎｄ  ｄｅｍａｎｄ−ｒｅｓｐｏｎｓｉｖｅ  ｐａｓｓｅｎｇｅｒ  ｔｒａｎ        ｓｐｏｒｔ  ｓｙｓｔｅｍｓ：  ａ  ｍｏｄｅｌｉｎｇ  ｆｒａｍｅｗｏｒｋ  ｗｉｔｈ  ｅｍｂｅｄｄｅｄ  ｃｏｎｔｒｏｌ  ｓｙｓｔｅｍ        ｓ，”Ｔｒａｎｓｐｏｒｔａｔｉｏｎ  Ｒｅｓｅａｒｃｈ  Ｐａｒｔ  Ａ：  Ｐｏｌｉｃｙ  ａｎｄ  Ｐｒａｃｔｉｃｅ，  ３６（２）：１６        ７−１８８，  ２００２．
【非特許文献１３】
Ｊ．  Ｊａｗ，  Ａ．  Ｒ．  Ｏｄｏｎｉ，  Ｈ．  Ｎ．  Ｐｓａｒａｆｔｉｓ，  ａｎｄ  Ｎ．  Ｈ．  Ｍ．  Ｗｉｌｓｏｎ，  ”Ａ  ｈｅ        ｕｒｉｓｔｉｃ  ａｌｇｏｒｉｔｈｍ  ｆｏｒ  ｔｈｅ  ｍｕｌｔｉ−ｖｅｈｉｃｌｅ  ａｄｖａｎｃｅ  ｒｅｑｕｅｓｔ  ｄｉａｌ−ａ−ｒ        ｉｄｅ  ｐｒｏｂｌｅｍ  ｗｉｔｈ  ｔｉｍｅ  ｗｉｎｄｏｗｓ，”  Ｔｒａｎｓｐｏｒｔａｔｉｏｎ  Ｒｅｓｅａｒｃｈ，  ｖｏｌ．２０Ｂ        ，  ｐｐ．２４３−２５７，  １９８６．
【非特許文献１４】
Ｓｖｅｎ  Ｏ．  Ｋｒｕｍｋｅ，  Ｗｉｌｌｅｍ  Ｅ．  ｄｅ  Ｐａｅｐｅ，  Ｄｉａｎａ  Ｐｏｅｎｓｇｅｎ，  ａｎｄ  Ｌｅｅｎ  Ｓｔｏ        ｕｇｉｅ，  ”Ｎｅｗｓ  ｆｒｏｍ  ｔｈｅ  Ｏｎｌｉｎｅ  Ｔｒａｖｅｌｉｎｇ  Ｒｅｐａｉｒｍａｎ，”  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ          ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，  Ｖｏｌ．２１３６，  ｐｐ．４８７−２９６，  ２００１．
【非特許文献１５】
Ｓｖｅｎ  Ｏ．  Ｋｒｕｍｋｅ，  Ｊｏｒｇ  Ｒａｍｂａｕ，  ａｎｄ  Ｓｔｅｆｆｅｎ  Ｗｅｉｄｅｒ，  ”Ａｎ  Ａｐｐｒｏｘｉｍａｔｉ        ｏｎ  Ａｌｇｏｒｉｔｈｍ  ｆｏｒ  ｔｈｅ  Ｎｏｎ−Ｐｒｅｅｍｐｔｉｖｅ  Ｃａｐａｃｉｔａｔｅｄ  Ｄｉａｌ−ａ−Ｒｉｄｅ  Ｐｒｏｂ        ｌｅｍ，”  Ｋｏｎｒａｄ−Ｚｕｓｅ−Ｚｅｎｔｒｕｍ  ｆｕｒ  Ｉｎｆｏｒｍａｔｉｏｎｓｔｅｃｈｎｉｋ  Ｂｅｒｌｉｎ，  ２０００．
【非特許文献１６】
Ｓａｍｕｅｌ  Ｗ．  Ｌａｕ，  ”Ａｕｔｏｎｏｍｏｕｓ  Ｄｉａｌ−ａ−Ｒｉｄｅ  Ｔｒａｎｓｉｔ−Ｂｅｎｅｆｉｔ−Ｃｏｓｔ  Ｅｖａｌ        ｕａｔｉｏｎ，”  Ｔｈｅ  Ｔｒａｎｓｉｔ  Ｓｔａｎｄａｒｄｓ  Ｃｏｎｓｏｒｔｉｕｍ  （ｔｅｃｈｎｉｃａｌ  ｒｅｐｏｒｔ），  ｕｒ        ｌ＝”ｃｉｔｅｓｅｅｒ．ｎｊ．ｎｅｃ．ｃｏｍ／ｌａｕ９８ａｕｔｏｎｏｍｏｕｓ．ｈｔｍｌ”，  １９９８．
【非特許文献１７】
Ｈａｉｂｉｎｇ  Ｌｉ  ａｎｄ  Ａｎｄｒｅｗ  Ｌｉｍ，  ”Ａ  ｍｅｔａｈｅｕｒｉｓｔｉｃ  ｆｏｒ  ｔｈｅ  ｐｉｃｋｕｐ  ａｎｄ  ｄ        ｅｌｉｖｅｒｙ  ｐｒｏｂｌｅｍ  ｗｉｔｈ  ｔｉｍｅ  ｗｉｎｄｏｗｓ，”  ＩＥＥＥ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃ        ｅ  ｏｎ  Ｔｏｏｌｓ  ｗｉｔｈ  Ａｒｔｉｆｉｃｉａｌ  Ｉｎｔｅｌｌｉｇｅｎｃｅ，  ｖｏｌ．１３，  ｐｐ．  １６０−１６７，  ２０        ０１．
【非特許文献１８】
Ｍａａｒｔｅｎ  Ｌｉｐｍａｎｎ，  Ｘ．  Ｌｕ，  Ｗｉｌｌｅｍ  Ｅ．  ｄｅ  Ｐａｅｐｅ，  Ｒｅｎｅ  Ａ．  Ｓｉｔｔｅｒｓ，  ａｎｄ          Ｌｅｅｎ  Ｓｔｏｕｇｉｅ，  ”Ｏｎ−ｌｉｎｅ  ｄｉａｌ−ａ−ｒｉｄｅ  ｐｒｏｂｌｅｍｓ  ｕｎｄｅｒ  ａ  ｒｅｓｔｒｉｃｔｅｄ          ｉｎｆｏｒｍａｔｉｏｎ  ｍｏｄｅｌ，”  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，  ２４６１：６７４−        ６８５，  ２００２．
【非特許文献１９】
Ｏ．  Ｂ．  Ｇ．  Ｍａｄｓｅｄ，  Ｈ．  Ｆ．  Ｒａｖｎ，  ａｎｄ  Ｊ．  Ｍ．  Ｒｙｇａａｒｄ，  ”Ａ  ｈｅｕｒｉｓｔｉｃ  ａｌｇ        ｏｒｉｔｈｍ  ｆｏｒ  ａ  ｄｉａｌ−ａ−ｒｉｄｅ  ｐｒｏｂｌｅｍ  ｗｉｔｈ  ｔｉｍｅ  ｗｉｎｄｏｗ，”  Ａｎｎａｌｓ  ｏｆ  Ｏｐ        ｅｒａｔｉｏｎｓ  Ｒｅｓｅａｒｃｈ，  ｖｏｌ．６０，  ｐｐ．１９３−２０８，  １９９５．
【非特許文献２０】
Ｈ．  Ｎ．  Ｐｓａｒｆａｉｔｓ，  ”Ａ  ｄｙｎａｍｉｃ  ｐｒｏｇｒａｍｍｉｎｇ  ｓｏｌｕｔｉｏｎ  ｔｏ  ｔｈｅ  ｓｉｎｇｌｅ  ｖ        ｅｈｉｃｌｅ  ｍａｎｙ−ｔｏ−ｍａｎｙ  ｉｍｍｅｄｉａｔｅ  ｒｅｑｕｅｓｔ  ｄｉａｌ−ａ−ｒｉｄｅ  ｐｒｏｂｌｅｍ，”  Ｔｒａｎ        ｓｐｏｒｔａｔｉｏｎ  Ｓｃｉｅｎｃｅ，  ｖｏｌ．１４，  ｐｐ．１３５−１５４，  １９８０．
【非特許文献２１】
Ｈ．  Ｎ．  Ｐｓａｒｆａｉｔｓ，  ”Ａ  ｅｘａｃｔ  ａｌｇｏｒｉｔｈｍ  ｆｏｒ  ｔｈｅ  ｓｉｎｇｌｅ  ｖｅｈｉｃｌｅ  ｍａｎｙ−        ｔｏ−ｍａｎｙ  ｄｉａｌ−ａ−ｒｉｄｅ  ｐｒｏｂｌｅｍ  ｗｉｔｈ  ｔｉｍｅ  ｗｉｎｄｏｗｓ，”  Ｔｒａｎｓｐｏｒｔａｔｉｏｎ  Ｓ        ｃｉｅｎｃｅ，  ｖｏｌ．１７，  ｐｐ．３１５−３５７，  １９８３．
【非特許文献２２】
Ｈ．  Ｎ．  Ｐｓａｒｆａｔｉｓ，  ”Ａｎａｌｙｓｉｓ  ｏｆ  ａｎ  ｏ（ｎ２）  ｈｅｕｒｉｓｔｉｃ  ｆｏｒ  ｔｈｅ  ｓｉｎｇｌｅ          ｖｅｈｉｃｌｅ  ｍａｎｙ−ｔｏ−ｍａｎｙ  ｅｕｃｌｉｄｅａｎ  ｄｉａｌ−ａ−ｒｉｄｅ  ｐｒｏｂｌｅｍ，”  Ｔｒａｎｓｐｏｒｔａ        ｔｉｏｎ  Ｒｅｓｅａｒｃｈ，  １７Ｂ：１３３−−１４５，  １９８３．
【非特許文献２３】
Ｋ．  Ｓ．  Ｒｕｌａｎｄ  ａｎｄ  Ｅ．  Ｙ．  Ｒｏｄｉｎ，  ”Ｔｈｅ  ｐｉｃｋｕｐ  ａｎｄ  ｄｅｌｉｖｅｒｙ  ｐｒｏｂｌｅｍ：          ｆａｃｅｓ  ａｎｄ  ｂｒａｎｃｈ−ａｎｄ−ｃｕｔ  ａｌｇｏｒｉｔｈｍ，”Ｃｏｍｐｕｔｅｒｓ  Ｍａｔｈ．  Ａｐｌｉｃ．，  ３３（１        ２）：１−１３，  １９９７．
【非特許文献２４】
Ｍ．  Ｗ．  Ｐ．  Ｓａｖｅｌｓｂｅｒｇｈ  ａｎｄ  Ｍ．  Ｓｏｌ，  ”Ｔｈｅ  ｇｅｎｅｒａｌ  ｐｉｃｋｕｐ  ａｎｄ  ｄｅｌｉｖｅｒ        ｙ  ｐｒｏｇｒａｍ，”  Ｔｒａｎｓｐｏｒｔａｔｉｏｎ  Ｓｃｉｅｎｃｅ，  ２９（１）：１７−２９，  １９９５．
【非特許文献２５】
Ｚｂｉｇｎｉｅｗ  Ｃｚｅｃｈ  Ｓｉｌｅｓｉａ，  ”Ｐａｒａｌｌｅｌ  ｓｉｍｕｌａｔｅｄ  ａｎｎｅａｌｉｎｇ  ｆｏｒ  ｔｈｅ  ｓｅ        ｔ−ｐａｒｔｉｔｉｏｎｉｎｇ  ｐｒｏｂｌｅｍ，”  Ｔｈｅ  ８ｔｈ  Ｅｕｒｏｍｉｃｒｏ  Ｗｏｒｋｓｈｏｐ  ｏｎ  Ｐａｒａｌｌｅｌ          ａｎｄ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｐｒｏｃｅｓｓｉｎｇ，  ｐｐ．３４３−３５０，  ２０００．
【非特許文献２６】
Ｚｂｉｇｎｉｅｗ  Ｃｚｅｃｈ  Ｓｉｌｅｓｉａ，  ”Ｐａｒａｌｌｅｌ  ｓｉｍｕｌａｔｅｄ  ａｎｎｅａｌｉｎｇ  ｆｏｒ  ｔｈｅ  ｄｅ        ｌｉｖｅｒｙ  ｐｒｏｂｌｅｍ，”  Ｔｈｅ  ９ｔｈ  Ｅｕｒｏｍｉｃｒｏ  Ｗｏｒｋｓｈｏｐ  ｏｎ  Ｐａｒａｌｌｅｌ  ａｎｄ  Ｄｉｓｔ        ｒｉｂｕｔｅｄ  Ｐｒｏｃｅｓｓｉｎｇ，  ｐｐ．２１９−２２６，  ２００１．
【非特許文献２７】
Ｊｒ．  Ｗｉｌｌｉａｍ  Ａ．  Ｂａｉｌｅｙ  ａｎｄ  Ｊｒ．  Ｔｈｏｍａｓ  Ｄ．  Ｃｌａｒｋ，  ”Ａ  ｓｉｍｕｌａｔｉｏｎ  ａｎａ        ｌｙｓｉｓ  ｏｆ  ｄｅｍａｎｄ  ａｎｄ  ｆｌｅｅｔ  ｓｉｚｅ  ｅｆｆｅｃｔｓ  ｏｎ  ｔａｘｉｃａｂ  ｓｅｒｖｉｃｅ  ｒａｔｅｓ，        ”  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  １９ｔｈ  ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｗｉｎｔｅｒ  ｓｉｍｕｌａｔｉｏｎ，ｐｐ．８３８        −８４４，  ＡＣＭ  Ｐｒｅｓｓ，  １９８７．
【非特許文献２８】
岡谷正博、  平田富夫、誉田安秀，  「中山間地におけるデマンドバスシステムの開発−デマンドバスの実際的経路探索法−」，高度交通システ
ム研究会，Ｎｏ．４，ｐｐ．７−１２，情報処理学会，２００１．
【非特許文献２９】
境周平、若林竜太、内村圭一，「デマンドバスの運用面積に関する考察」，高度交通システム研究会，  Ｎｏ．２，  ｐｐ．１９−２４，情報処理学会，２０００．
【非特許文献３０】
斎藤隆司、内村圭一、Ｈｉｒｏ  Ｔａｋａｈａｓｈｉ，「複数の車両を用いた  ｄｉａｌ−ａ−        ｒｉｄｅ  問題に対する遺伝的アルゴリズムの適応」，電気学会  道路交通  研究会資料，  ｖｏｌ．３１，ｐｐ．１７−２２，  １９９７．
【非特許文献３１】
鳥居健太郎、愛須英之、田中俊明，「乗り換え需要を想定した需要に」，電気学会  道路交通研究会資料，  ｖｏｌ．  ３１，ｐｐ．１７−２２，  １９９７．
【非特許文献３２】
内村圭一，「位置情報対応ｐｈｓを利用した公共交通管理システムの開発」，電気通信普及財団平成１２年度調査研究報告書，  ｐｐ．８００−８０９，２０００        ．
【非特許文献３３】
内村圭一、斎藤隆司、Ｈｉｒｏ  Ｔａｋａｈａｓｈｉ，「公共サービスにおけるｄｉａｌ−ａ        −ｒｉｄｅ問題」，電子情報通信学会誌Ａ，  Ｊ８１−Ａ（４）：５９９−６０，  １９９８．
【０００７】
【発明が解決しようとする課題】
しかしながら、上記いずれの最適化アルゴリズムも、デマンドバスが固定路線バスと比べてどの程度利便性を改善できているのか、上記いくつかあるタイプのどれが利便性・採算性の面から優位なのか、についての客観的な評価を行えるものではなく、特に、運行台数や都市の規模とどのような関係にあり、都市規模に応じてどのように運営すればよいかについては、判断することができないのである。
【０００８】
そこで、この出願の発明は、以上のとおりの事情に鑑み、固定路線バスとデマンドバスとのメリット／デメリットを解析し、都市規模や運行台数とバス運行方式との関係を客観的に評価することのできる、新しいバス運行形態評価方法、ならびにバス運行形態評価プログラムおよび該プログラムを記録したコンピュータ読み取り可能な記録媒体を提供することを課題としている。
【０００９】
【課題を解決するための手段】
この出願の発明は、上記の課題を解決するものとして、第１には、処理手段が、固定路線バスにおける、出発地から目的地まで乗り換えなしで到達する場合の要求発生時間から要求達成時間までの平均時間が最小となる最適路線配置を、近似解探索手法により求めるステップ、および処理手段が、デマンドバスにおける、出発地から目的地まで乗り換えなしで到達する場合の要求発生時間から要求達成時間までの平均時間が最小となる最適デマンド配分を、上記ステップと同一の採算性条件の下に、近似解探索手法により求めるステップ、を含むことを特徴とするバス運行形態評価方法を提供する。
【００１０】
また、第２には、処理手段が固定路線バスの最適路線配置を近似解探索手法により求める前記ステップおよび処理手段がデマンドバスの最適デマンド配分を近似解探索手法により求める前記ステップにおいて、処理手段が、記憶手段に記憶されている平均時間式：
【００１１】
【数４】
2004287484.tif 000003
を用いて前記平均時間を算出する、ことを特徴とするバス運行形態評価方法、
第３には、処理手段が固定路線バスの最適路線配置を近似解探索手法により求める前記ステップにおいて、該近似解探索手法が遺伝的アルゴリズムであり、処理手段がデマンドバスの最適デマンド配分を近似解探索手法により求める前記ステップにおいて、該近似解探索手法が逐次最適挿入法である、ことを特徴とするバス運行形態評価方法、
第４には、処理手段が固定路線バスの最適路線配置を遺伝的アルゴリズムにより求める前記ステップに、処理手段が、任意の２つの交差点をランダムに選択し、選択された２つの交差点を結ぶＬの字型路線およびロの字型路線のいずれかを確率的に選択することで、遺伝的アルゴリズムの世代交代処理を行うステップ、を含むことを特徴とするバス運行形態評価方法、
第５には、処理手段が固定路線バスの最適路線配置を遺伝的アルゴリズムにより求める前記ステップに、処理手段が、記憶手段に記憶されている、隣り合う交差点を経路が直接結んでいる場合に該経路をコの字状に迂回する経路に変換する突然変異パターンと、ある街区の対角線位置にある交差点をＬの字状に経路が結んでいる場合に該経路を逆Ｌの字の経路に変換する突然変異パターンと、ターミナル駅を１ブロック移動して経路を伸縮させる突然変異パターンとを用いて、遺伝的アルゴリズムの突然変異処理を行うステップ、を含むことを特徴とするバス運行形態評価方法、
第６には、処理手段が固定路線バスの最適路線配置を遺伝的アルゴリズムにより求める前記ステップに、処理手段が、記憶手段に記憶されている、隣り合う交差点を経路が直接往復している場合に該経路を縮退させる突然変異パターンをさらに用いて、遺伝的アルゴリズムの前記突然変異処理を行うステップ、を含むことを特徴とするバス運行形態評価方法、
第７には、処理手段が固定路線バスの最適路線配置を遺伝的アルゴリズムにより求める前記ステップに、処理手段が、記憶手段に記憶されている交差確率で各路線を他の固体の路線と置き換えることで、遺伝的アルゴリズムの交差処理を行うステップ、を含むことを特徴とするバス運行形態評価方法、
第８には、処理手段がデマンドバスの最適デマンド配分を逐次最適挿入法により求める前記ステップに、処理手段が、各バスをデマンドの出発地点と目的地点に分割し、且つこれらの経由地点のリストとして配分されたデマンドを保持するものとし、各バスが各経由地点に到達した場合に該経由地点をリストから取り除くステップ、処理手段が、各バスの各時点におけるデマンドの達成予定時刻を算出するステップ、処理手段が、新たにデマンドが発生した際に各バスについてデマンドの出発地点および目的地点を現在の経由地点リストの任意の場所に挿入し、全経由地点における該挿入により生じる遅延の総和を、前記算出された達成予定時刻と比較して求めるステップ、処理手段が、新しいデマンドの達成予定時間を求め、該達成予定時間と前記求められた遅延の総和を挿入のコストとするステップ、処理手段が、出発地点と目的地点の挿入場所のペアのすべての組合せについて、前記コストが最小となるペアを、デマンドの受け入れ候補とするステップ、および処理手段が、すべてのバスについて前記受け入れ候補を求め、前記コストが最も小さくなるバスにそのデマンドを配分するステップ、を含むことを特徴とするバス運行形態評価方法、を提供する。
【００１２】
そして、この出願の発明はさらに、固定路線バスおよびデマンドバスの運行形態を評価するためにコンピュータを、上記各ステップを実行する各処理手段として機能させることを特徴とするバス運行形態評価プログラムおよび該評価プログラムを記録したコンピュータ読み取り可能な記録媒体をも提供する。
【００１３】
【発明の実施の形態】
図１は、上記のとおりの特徴を有するこの出願の発明を実行する評価装置の構成図である。
【００１４】
評価装置は、ＣＰＵ等の中央処理手段（１）、キーボードやマウス等の入力手段（２）、ディスプレイやプリンタ等の出力手段（３）、メインメモリやデータベース等の記憶手段（４）を備えており、記憶手段（４）には評価プログラム、算出式、各種初期設定値、各種初期条件値、各種パラメータ値、算出評価値等のデータが記憶され、中央処理手段（１）は上記のとおりの各処理手段として機能して各ステップを実行する。各種初期設定値は予め入力手段（２）により入力されて記憶手段（４）に記憶されていても、必要時に随時入力手段（２）により入力されてもよい。
【００１５】
以下、添付した図面に沿って実施例を示し、さらに詳しくこの出願の発明の実施の形態について説明する。
【００１６】
【実施例】
［１．利便性と採算性］
デマンドバス、固定路線バスというバスの運行形態に因る利便性と採算性の差異を客観的に解明し評価するには、これら利便性・採算性の指標を主観的要素や経済的要因を含まないものとする必要がある。そこで、この出願の発明では、これらの指標を以下に述べるように単純化して定量的に扱うことのできるものとして定義する。
【００１７】
まず利便性に関して、バスの利便性には、待ち時間の多さや乗り心地、乗り継ぎの良さなどいくつかの要素がある。しかしそれらをすべて数値化して取り上げることは極めて難しいので、ここではバス本来の目的、つまり目的地までいかにスムースに到着するかに着目し、以下のように利便性を定義する。
・「利便性」＝「出発地から目的地まで乗り換えなしで到達する場合の、要求発生時間から要求達成時間までの平均時間」
ここで出発時間ではなく要求発生時間を用いている理由は、固定路線バスとデマンドバスの条件を揃えるために、前日などに予め乗降場所と時間を予約しておくタイプの予約型デマンドバスを除外するためである。よって、固定路線バスでは、バスが来る時刻に合わせて行動するつまり要求が発生するのではなく、移動を開始したい時点を要求が発生した時点と考え、その要求発生時点で最寄りのバス停まで歩き、来たバスに乗るものとする。また、デマンドバスの場合には、要求が発生した時点でバス会社に配車を依頼するものとする。
【００１８】
続いて採算性については、次のように考える。バス運行の採算性は、車体の維持費、燃料費、人件費と運賃収入などが絡む。さらに運賃収入に絡む運賃設定に関しては、それにより利用者が増減するなどの２次要因が生じるため扱うことが極めて難しい。そこで問題を収入と支出の割合に単純化し、収入は単位時間における総乗客数（＝総デマンド数）、支出はバス台数に比例するものと考える。よって、採算性は以下のように数値化する。
・「採算性」＝「単位時間におけるバス１台当たりのデマンド処理数」
そして、この出願の発明では、以上のとおりに定義した「利便性」が最大となる、つまり上記平均時間が最小となる固定路線バスの最適路線配置およびデマンドバスの最適デマンド配分を、同じく以上のとおりに定義した「採算性」の条件を同一として、つまり上記デマンド処理数を同一値として近似解探索手法を実行することにより求める。
【００１９】
なお、ここでは、説明の便宜上、上記「平均時間」を「平均達成時間」と呼び、上記「デマンド処理数」を「要求処理数」と呼ぶ場合がある。
【００２０】
［２．シミュレーション条件］
この出願の発明では、さらに、客観的評価の初期舞台設定として、以下のような仮想都市を考える。
・街路は碁盤目状であり、すべての街区は同じ大きさとする。
・都市全体は正方形とする。
・すべての交差点にバス停があるものとする。
・交通渋滞は存在せず、バスは一定速度で運行できるものとする。
・交差点での右左折、直進、Ｕターン等はすべて同じ時間で行えるものとする。
【００２１】
・バスの乗降には時間がかからないものとする。
・バスには何人でも乗れるものとする。
【００２２】
またデマンドに関しては、以下のような初期条件を仮定する。
・デマンドは一定時間ごとに一定数発生するものとする。
・デマンドの発生点（＝出発点）および目的点は、一様にランダムに決定される  。
・目的地までバスを利用するよりも歩いていった方が早い場合、バスは利用しない。この場合、デマンドは拒否されたと見なされ、利便性の評価の際には、徒歩による時間がデマンド達成時間として用いられる。
・バスの乗り換えは行わないものとする。
【００２３】
［３．シミュレーション］
［３．１  固定路線バス］
以上のような定義・設定のもと、まず、固定路線バスの最適な路線配置を、近似解探索手法の一例である遺伝的アルゴリズム手法を用いて求める。
【００２４】
ここでは解析の簡易化のために、路線の数および一路線当たりのバスの台数は固定であるとする。また路線の形状として、始発終着駅を往復運行する往復路線と、円環状の路線を右回り左回り両方向に運行する循環路線の２種類が存在するものとする。
【００２５】
［３．１．１  利便性評価］
利便性は、上記定義のとおりデマンドの平均達成時間により計測する。固定路線バスの場合のデマンドの平均達成時間Ｔｄｅｍａｎｄは、次のように表すことができる。
【００２６】
【数５】
2004287484.tif 000004
ただし、Ｌｓｒｃ、Ｌｄｓｔ、Ｌｒｏｕｔｅ、Ｌｂｕｓは出発点から乗車バス停までの距離、降車バス停から目的地までの距離、路線長、乗車バス停から降車バス停までの路線距離を、Ｖｗａｌｋ、Ｖｂｕｓは歩行速度、バス速度を、Ｍｂｕｓは路線当たりのバス台数を表している。
【００２７】
この式において、乗車バス停、降車バス停の選び方の組み合わせが複数生じる。また、複数路線を運行している場合、どの路線に乗るか自由度がある。そのため、各々の路線の全乗降車バス停の組み合わせについて上記の平均達成時間を求め、その最小となる路線を利用するものとする。
【００２８】
この式は予め上記解析装置の記憶手段（４）に記憶させておく。
【００２９】
［３．１．２  世代交代］
本実施例では、各世代は１００個体からなるとし、各個体について５０個のデマンドをランダムに生成し、上記の方法により平均達成時間を計算し、評価値とする。この評価によるベスト１０の固体が生き残り、各々８個体ずつコピーを作成し、残り２０個体は新たにランダム生成して次の世代を構成する。これらの初期設定値も予め上記解析装置の入力手段（２）により入力して記憶手段（４）に記憶させておく。
【００３０】
コピーを生成する場合は、以下に述べる突然変異と交差を適用して個体差を生じさせる。ただし、１体は完全なコピーを残すものとする。
【００３１】
ランダム生成は次のような手順で行う。任意の２つの交差点をランダムに選択し、その２点を結ぶＬの字型（＝往復路線を表した型）あるいはロの字型（＝循環路線を表した型）の確率的な選択を行う。Ｌの字、ロの字の選択確率は本実施例では１／２ずつとする。
【００３２】
［３．１．３  突然変異］
路線の経路の突然変異には、図２に例示したような下記４つの変換パターンを設定しておき、記憶手段（４）に記憶させておく。
【００３３】
パターンＡ：隣り合う交差点を経路が直接結んでいる場合、それをコの字状に迂回する経路に変換する（およびその逆変換）（図２（ａ））。
【００３４】
パターンＢ：ある街区の対角線位置にある交差点を  Ｌ  の字状に経路が結んでいる場合、それを逆  Ｌ  の字の経路に変換する（図２（ｂ））。
【００３５】
パターンＣ：隣り合う交差点を直接往復しているような経路がある場合、それを縮退させる（図２（ｃ））。
【００３６】
パターンＤ：一般路線の場合、ターミナル駅を１ブロック移動し、路線を伸ばす／縮める（図２（ｄ））。
【００３７】
なお、パターンＣはパターンＡとパターンＢとの組み合わせによって表現できるが、その変異の途中段階は多くの場合改悪となってしまうため、このような盲腸往復路線の縮退に結び付かないことが多いと考えられるので、このパターンＣを新たに導入する。これにより、探索の高速化を図ることができる。
【００３８】
また本実施例では、突然変異は、１路線につき最大１個所のみとする。多くの突然変異は改悪になるため、複数個所の突然変異を起こすと、数少ない改善につながる突然変異が起きても、他の突然変異による改悪によりほとんど改善できない。これを避けるため、突然変異はどんなに長い路線でも１個所のみとする。
【００３９】
［３．１．４  交差］
交差は、図３に例示したように、複製を作る際に各路線をある確率で他の個体の路線と置き換えるようにして行う。すなわち、交差は路線単位で起こるものとし、路線のなかは突然変異のみで変化する。
【００４０】
［３．１．５  固定路線バスの最適路線の一例］
以上の設定のもとで遺伝的アルゴリズムを上記評価装置の中央処理手段（１）で実行した。図４は得られた路線配置の一例を示したものである。
【００４１】
この図４に示した路線は、路線数を３に固定した場合の、１００００世代目において最も評価値の高かった個体の路線であり、バスと徒歩の速度の比Ｖｂｕｓを８倍（図４（ａ））、１６倍（図４（ｂ））、３２倍（図４（ｃ））、２５６倍（図４（ｄ））に変化させた場合の結果を示している。この例からわかるように、バスの速度が遅い場合には、３路線で町を取り囲むような配置が得られ、バスの速度が上がるに従い、町の全交差点を経由する複雑な路線になることがわかる。ここに示した例はあくまで各々１試行の結果であるが、複数試行行った場合でもほぼ同等の路線が得られており、遺伝的アルゴリズムにより固定路線バスの妥当な最適路線配置を得られることがわかる。
【００４２】
［３．２  デマンドバス］
次に、デマンドバスについては以下のとおりにシミュレーションを行う。
【００４３】
デマンドバスでは、各バスが各々いくつかのデマンド（＝乗降車希望地点のペア）を持っており、そのデマンドを達成する最適な経路を計画して運行し、各デマンドを処理していく。
【００４４】
デマンドの配分方式は、
・「バッチ処理方式」：デマンドは予約の形であらかじめためておき、それらをバッチ的に処理して最適な配分を計算する。よって、デマンドの発生時刻は乗車要求時刻より一定時間以上先立っている必要がある。
・「リアルタイム配分方式」：デマンドが発生した時点で、運行しているバスのうちそのデマンドを処理するのに最も敵したバスに配分する。よってデマンド発生時刻は乗車要求時刻と同じでよい。
【００４５】
本実施例ではこれらのうち、より利便性が高く路線バスと同じ条件で比較できるものとして、リアルタイム配分方式を仮定する。
【００４６】
一般に、このような方式で最適なデマンド配分および経路探索をする問題は、動的な巡回セールスマン問題と等価であり、完全な最適解を求めることは計算量の点で難しい。特にリアルタイム方式では新たなデマンドを受け入れるにあたって、既存のデマンドの締め切り時刻を越えないように配分する必要があるため、問題としてはより複雑になっている。なお、締め切り時刻とは、目的地到達時刻がその時刻を越えてしまう場合、バス以外の代替手段を選択する判断条件をさす。
【００４７】
そこで本実施例では、そのデマンドをすべて徒歩で行ったと仮定した場合の到達時刻とし、近似解探索手法としての以下に述べる逐次最適挿入法を用いて、デマンド配分の妥当な最適解を求める。
（１）各バスは、デマンドの出発地点（＝乗車地点）と目的地点（＝降車地点）    に分割し、これらの経由地点のリストとして配分されたデマンドを保持    している。バスが各経由地点に到着した場合には、その地点はリストか    ら取り除かれる。また、一旦保持された経由地点の列の順序は、変更さ    れないものとする。
（２）各バスは各時点において、自分が抱えているデマンドの達成予定時刻を計算する。この達成予定時刻は、そのバスが新たにデマンドを抱えずにリストにある各経由地点を順番通り回ると仮定して計算する。
（３）新たにデマンドが発生した際、各バスはデマンドの出発地点および目的地点を各々、現在の経由地点リストの任意の場所に挿入し、全経由地点における挿入により生じる遅延の総和を、上で求めた達成予定時刻と比較して求める。さらに、新しいデマンドの達成予定時間も求め、この達成予定時間と遅延の総和を挿入のコストとする。出発地点と目的地点の挿入場所のペアのすべての組み合わせ（ただし、目的地点は出発地点よりリストの後ろに挿入される）について、コストが最小となるペアを、デマンドの受け入れ候補とする。ただし、挿入により既存あるいは新しいデマンドの締め切り時刻を過ぎてしまう場合は、その挿入は候補から除外される。
（４）すべてのバスについて上記の受け入れ候補を求め、最もコストが小さくなるバスにそのデマンドを配分する。
【００４８】
そして、各バスは、以上の逐次最適挿入法により構成された経由地点のリストを順にたどって行き、デマンドを処理する。シミュレーションにおいては、一定時間に一定数のデマンドをランダムに発生させ、上記の方法で処理して行った場合の、各デマンドの処理に係った時間を計測する。この経過時間の平均をもってデマンドバスの利便性（つまり前記平均達成時間）とする。
【００４９】
［４．両シミュレーションの比較］
［４．１  パラメータ設定］
上述した両シミュレーションを、街のサイズを１１×１１、バスと徒歩の速度比を１：８とし、固定路線の路線あたりのバス台数を１として実行した。
【００５０】
［４．２  バス台数を固定した場合］
図６は、バス台数を３台に固定し、単位時間当たりのデマンドの発生件数を変化させた場合の、各デマンドの平均達成時間を示したものである。また、図７は、バスによる達成時刻が締め切り時刻を過ぎるためにバスを利用しなかった比率（「デマンド拒否率」と呼ぶこととする）の変化を示したものである。
【００５１】
固定路線バスの場合、バスが満員でない限り平均達成時間およびデマンド拒否率はデマンドの発生件数には関係ないので、各々横一直線となる。
【００５２】
一方、フルデマンドバスの場合は、デマンドの発生件数が多くなるに従い、利便性（＝デマンド達成時間の逆数）が急速に悪化し、５を越えたあたりで飽和する。これは、新規に発生したデマンドが他の利用者の達成時間を遅らせるため、締め切り時間をオーバしてデマンド拒否になってしまうことが原因となっている。
【００５３】
すなわち、デマンドバスの利便性は、バスが空いている場合に限られることがわかる。
【００５４】
［４．３  採算性を固定した場合］
図８は、採算性を一定に保つ場合（＝単位時間あたりのデマンド発生件数とバス台数の比率を固定した場合）の、デマンド発生件数に対するデマンド平均達成時間の変化を示したものである。
【００５５】
デマンドバスに関しては異なる採算性（＝デマンド頻度バス台数比率）別に、その利便性がプロットされている。固定路線バスの場合は、採算性の違いによって利便性に差は生じないため、１つのプロットとなっている。ただし、固定路線バスにおいてバス台数を増やす場合、路線あたりのバス台数を増やすのではなく、路線の数を増やす形で総バス台数を増やしている。すなわち、路線数を増やすごとに前節で述べている遺伝的アルゴリズムに従い準最適解を求めている。
【００５６】
図８から、固定路線バスおよびフルデマンドバスともに、デマンド発生件数（およびバス台数）が増加するに従い、利便性が改善されることがわかる。これは、固定路線バスの場合は路線数の増加によりデマンドに対する路線の選択肢が増えることが改善の原因になっており、デマンドバスの場合はバス台数の増加によりデマンドの競合によるデマンド拒否が減少することが改善の原因になっている。
【００５７】
しかし、改善の速度には違いがあり、フルデマンドの方が早く改善され、十分多くのデマンドがあれば、フルデマンドの方が固定路線よりも利便性がよくなることがわかる。
【００５８】
［４．４  結果］
以上のシミュレーション結果をまとめると、以下のようなことがわかる。
・バス台数を固定した場合、デマンド頻度が増えるに従い、フルデマンド方式では利便性（＝平均デマンド達成時間）およびデマンド拒否率ともに急速に悪  化する（図６、図７参照）。一方、固定路線ではバスが満員でない限り、デ  マンド頻度は利便性に影響を与えない。このため、同じ台数で運行する限り  、デマンド頻度が低い場合にはフルデマンド方式が、頻度が高い場合には固  定路線方式の方が利便性が高い。採算性を考えた場合、できるだけ多くのデ  マンドをさばく必要があるが、バス台数を固定する場合にはデマンドの増減  や運行規模の拡大によって、利便性が悪化することは避けられない。すなわ  ち、「規模を大きくして客が増えれば採算がとれる」単純な図式は成り立た  ないことがわかる。
・一方、デマンド頻度とバス台数を一定比率で比例させた場合、固定路線方式に比べフルデマンド方式の方が急速に利便性を改善できる（図８参照）。ただ、デマンド頻度とバス台数の比率（＝１台、単位時間あたりのデマンド数）を大きくとるほど、固定路線方式と利便性が逆転する点は大きくなる、つまりデマンド頻度が高くなる。よって、運行規模が大きくなるに従いフルデマンド方式の方が固定路線方式よりも高い利便性を確保できるが、採算を重視    （バスあたりのデマンド頻度を大きく）すると、より大きな規模を必要とす  ることがわかる。
【００５９】
これらのうち後者の結果は、今後バスの需要のより多い地域におけるフルデマンドバスシステムの適用に重要な要素となると考えられる。
【００６０】
以上によれば、この出願の発明によって、固定路線バスとデマンドバスの利便性および採算性の関係をシミュレーションすることができ、その結果、デマンドバスは十分に大きな需要があれば、採算性を維持しながら固定路線より高い利便性を維持することができることを客観的に評価することができた。
【００６１】
なお、評価精度をより高めるべく、以下のような要素を取り入れたシミュレーションを行うことも好ましい態様である。
・シミュレーションの単位と現実との擦り合わせ：町のサイズ、バス速度などの数値を現実の具体的数値に合わせる。
・デマンドの出発点、目標点の分布が片寄っている場合：実際の町ではデマンドがまんべんなく発生することはなく、  鉄道駅などどちらかのデマンドが集中する場所が存在することが多い。その場合には運営方式による利便性が変化すると考えられる。
・デマンドの距離による変化：今回はデマンドは出発地点・目的地点共にランダムに発生させた。しかし通常はある一定以上の距離を移動する場合に徒歩以外の交通手段を選択すると考えられる。また、十分に長距離の場合、いくら徒歩による達成時間よりも長くかかったとしてもバスを選択する場合があると考えられる。
・デマンド発生の時間的偏り：デマンドの発生頻度はラッシュ時や閑散期など時間的変化がある。そのような要素を取り入れた採算性と利便性の比較が実際には必要となる。
・乗降車時間および混雑率：多くのデマンドをさばく場合、乗客の乗降時間は無視できない。また、混雑率は利便性やデマンド拒否率に影響を与えることになる。
【００６２】
もちろん、この出願の発明は以上の実施例に限定されるものではなく、様々な態様が可能である。
【００６３】
たとえば、固定路線バスの最適路線配置およびデマンドバスの最適デマンド配分を求めるための近似解探索手法としては、上述の遺伝的アルゴリズムや逐次最適挿入法だけでなく、ニューラルネットワークやモンテカルロ法など各種探索手法を用いることができる。
【００６４】
【発明の効果】
以上詳しく説明したとおり、この出願の発明によって、固定路線バスとデマンドバスのメリット／デメリットを解析して、都市規模や運行台数とバス運行方式との関係を客観的に評価することのできる、新しいバス運行形態評価方法、ならびにバス運行形態評価プログラムおよび該プログラムを記録したコンピュータ読み取り可能な記録媒体が提供される。
【図面の簡単な説明】
【図１】この出願の発明による評価装置の構成図である。
【図２】（ａ）〜（ｄ）は、遺伝的アルゴリズムの突然変位処理で用いられる突然変位パターンＡ〜Ｄを説明するための図である。
【図３】遺伝的アルゴリズムの交差処理を説明するための図である。
【図４】（ａ）〜（ｄ）は、各々、遺伝的アルゴリズムにより得られた固定路線バスの最適解の一例を示した図である。
【図５】逐次最適挿入法を説明するための図である。
【図６】バス３台の場合のデマンド当たりの平均達成時間の変化を例示した図である。
【図７】バス３台の場合のデマンド拒否率を例示した図である。
【図８】デマンド頻度／バス台数の比率を一定に保った場合のデマンド当たりの平均達成時間の変化を例示した図である。
【符号の説明】
１  中央処理手段
２  入力手段
３  出力手段
４  記憶手段
【図１】
2004287484.tif 000008
【図２】
2004287484.tif 000009
【図３】
2004287484.tif 000010
【図４】
2004287484.tif 000011
【図５】
2004287484.tif 000012
【図６】
2004287484.tif 000013
【図７】
2004287484.tif 000014
【図８】
2004287484.tif 000015