(57)【特許請求の範囲】
【請求項１】
複数の路線を利用して移動する移動者の移動要求に応じて、運行計画を生成する運行計画装置において、
前記移動者が移動する移動経路の特性である経路特性と、前記移動者が前記経路特性を重視する度合いとを嗜好情報として受け付ける嗜好受付部と、
前記移動要求を満たす移動経路の候補を複数の経路候補として、前記複数の路線から抽出する抽出部と、
前記嗜好情報と前記複数の経路候補とに基づいて、前記複数の経路候補の各経路候補を移動する際の前記移動者の不快度を目的関数とする最適化問題を生成する問題生成部であって、前記不快度は、前記複数の経路候補の各々を前記移動者が利用するか否かを示す第１決定変数と、前記複数の経路候補の各々を走行する車両の運行計画と前記移動者が乗車する車両とを表す第２決定変数とを用いて表された問題生成部と、
前記最適化問題を計算することにより、前記第１決定変数と前記第２決定変数とを決定する問題計算部と
を備えた運行計画装置。
【請求項２】
前記運行計画装置は、
前記第１決定変数により、利用されることが示された経路候補を移動経路として前記移動者が利用する移動者端末に送信し、前記第２決定変数により表された前記車両の運行計画を出力機器に出力する出力部を備えた請求項１に記載の運行計画装置。
【請求項３】
前記第１決定変数は、前記複数の経路候補の各経路候補ｒについて、移動者ｕが経路候補ｒを利用する場合に１が設定され、移動者ｕが経路候補ｒを利用しない場合に０が設定される変数ｘｕ，ｒである請求項１または２に記載の運行計画装置。
【請求項４】
前記第１決定変数は、前記複数の経路候補の各経路候補ｒについて、時刻ｔに出発地ｏから目的地ｄへ移動する人数のうち、嗜好情報ｐを持ち、かつ、経路候補ｒを利用する人数を表す変数ｘｔ，ｏ，ｄ，ｒ，ｐである請求項１または２に記載の運行計画装置。
【請求項５】
前記経路特性は、複数の経路特性を含み、
前記受付部は、
前記複数の経路特性の各経路特性に対し、前記移動者が各経路特性を重視する度合いを数値で示した情報を前記嗜好情報として受け付ける請求項１から４のいずれか１項に記載の運行計画装置。
【請求項６】
前記経路特性は、複数の経路特性を含み、
前記受付部は、
前記複数の経路特性から、前記移動者が最も重視する経路特性を前記移動者に選択させた情報を前記嗜好情報として受け付け、予め定められた規則を用いて前記複数の経路特性の各経路特性を重視する度合いを設定する請求項１から４のいずれか１項に記載の運行計画装置。
【請求項７】
前記受付部は、
前記移動経路における移動時間、運賃、路線間の乗り継ぎ回数、および車両混雑度の少なくとも一部を前記経路特性として、前記嗜好情報を受け付ける請求項５または６に記載の運行計画装置。
【請求項８】
前記抽出部は、
前記受付部により受け付けた前記嗜好情報に基づいて、前記複数の路線から抽出する前記複数の経路候補を制限する請求項１から７のいずれか１項に記載の運行計画装置。
【請求項９】
複数の路線を利用して移動する移動者の移動要求に応じて、運行計画を生成する運行計画装置の運行計画方法において、
嗜好受付部が、前記移動者が移動する移動経路の特性である経路特性と、前記移動者が前記経路特性を重視する度合いとを嗜好情報として受け付け、
抽出部が、前記移動要求を満たす移動経路の候補を複数の経路候補として、前記複数の路線から抽出し、
問題生成部が、前記嗜好情報と前記複数の経路候補とに基づいて、前記複数の経路候補の各経路候補を移動する際の前記移動者の不快度であって、前記複数の経路候補の各々を前記移動者が利用するか否かを示す第１決定変数と、前記複数の経路候補の各々を走行する車両の運行計画と前記移動者が乗車する車両とを表す第２決定変数とを用いて表された不快度を目的関数とする最適化問題を生成し、
問題計算部が、前記最適化問題を計算することにより、前記第１決定変数と前記第２決定変数とを決定する運行計画方法。
【請求項１０】
複数の路線を利用して移動する移動者の移動要求に応じて、運行計画を生成する運行計画装置の運行計画プログラムにおいて、
前記移動者が移動する移動経路の特性である経路特性と、前記移動者が前記経路特性を重視する度合いとを嗜好情報として受け付ける受付処理と、
前記移動要求を満たす移動経路の候補を複数の経路候補として、前記複数の路線から抽出する抽出処理と、
前記嗜好情報と前記複数の経路候補とに基づいて、前記複数の経路候補の各経路候補を移動する際の前記移動者の不快度であって、前記複数の経路候補の各々を前記移動者が利用するか否かを示す第１決定変数と、前記複数の経路候補の各々を走行する車両の運行計画と前記移動者が乗車する車両とを表す第２決定変数とを用いて表された不快度を目的関数とする最適化問題を生成する問題生成処理と、
前記最適化問題を計算することにより、前記第１決定変数と前記第２決定変数とを決定する問題計算処理と
をコンピュータである前記運行計画装置に実行させる運行計画プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、運行計画装置、運行計画方法および運行計画プログラムに関する。特に、本発明は、デマンド型交通における運行計画を生成する運行計画装置、運行計画方法および運行計画プログラムに関する。
【背景技術】
【０００２】
近年、移動者の要求を車両の運行計画にリアルタイムに反映することができる交通が実用化されている。このような交通の具体例として、オンデマンドバスがある。オンデマンドバスは、移動者から、出発地、目的地、出発希望時刻、および到着希望時刻といった情報を含む移動要求を受け付ける。そして、オンデマンドバスは、移動要求を可能な限り満たす運行計画をリアルタイムに立案する。たとえば、オンデマンドバスは、停留所の巡回順番を変更することにより移動者の要求をリアルタイムに反映する。このような交通は、デマンド型交通あるいはオンデマンド交通と呼ばれる。【０００３】
デマンド型交通において、最適な運行計画を立案するための問題は、ｄｉａｌ−ａ−ｒｉｄｅ問題と呼ばれる。ｄｉａｌ−ａ−ｒｉｄｅ問題は、最適化問題の分野で、広く研究されている。非特許文献１では、人あるいは荷物の配送計画問題を最適化問題として扱う手法が開示されている。この配送計画問題には、ｄｉａｌ−ａ−ｒｉｄｅ問題が含まれる。【０００４】
デマンド型交通の運行計画を立案する際、最適化問題に用いられる目的関数が選択される。最も単純な選択方法は、移動者の移動時間の総和を目的関数として選択する方法である。この場合、「バスが一定台数という条件下で、移動要求を全て満たす運行計画の中から、移動時間の総和が最小となる運行計画を求める」という問題を解くことになる。【０００５】
特許文献１に開示されている装置は、移動者の介護度を目的関数に取り入れ、運行計画を生成する。
また、特許文献２に開示されている装置は、複数の運行計画の候補から、移動者に運行計画を選択させることで、最適化の指標を学習する。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００６−２５２０６６号公報
【特許文献２】国際出願２０１３／１４７０５６号
【非特許文献】
【０００７】
【非特許文献１】Ｍ．Ｗ．Ｐ．  Ｓａｖｅｌｓｂｅｒｇｈ  ａｎｄ  Ｍ．  Ｓｏｌ，  “Ｔｈｅ  Ｇｅｎｅｒａｌ  Ｐｉｃｋｕｐ  ａｎｄ  Ｄｅｌｉｖｅｒｙ  Ｐｒｏｂｌｅｍ，”  Ｔｒａｎｓｐｏｒｔａｔｉｏｎ  Ｓｃｉｅｎｃｅ，  ２９−１，  １７／２９  （１９９５）
【発明の概要】
【発明が解決しようとする課題】
【０００８】
移動に対する満足度は、移動者の嗜好によって異なる。具体例としては、移動時間を重視する移動者の満足度は、たとえ乗り換え回数が多くても、移動時間が短ければ高くなる。しかしながら、従来の装置では、移動者の嗜好を考慮した運行計画を生成することはできないという課題があった。また、通常、移動者は、移動経路の提示を所望する。従来の装置は、生成した運行計画から移動経路を生成し、生成した移動経路を移動者に提示していた。よって、従来の装置では、運行計画を生成した後に移動経路を計算する時間が必要であるという課題があった。【０００９】
本発明は、移動者の満足度が高い運行計画および移動経路を効率的に生成することができる運行計画装置を提供する。
【課題を解決するための手段】
【００１０】
本発明に係る運行計画装置は、
複数の路線を利用して移動する移動者の移動要求に応じて、運行計画を生成する運行計画装置において、
前記移動者が移動する移動経路の特性である経路特性と、前記移動者が前記経路特性を重視する度合いとを嗜好情報として受け付ける嗜好受付部と、
前記移動要求を満たす移動経路の候補を複数の経路候補として、前記複数の路線から抽出する抽出部と、
前記嗜好情報と前記複数の経路候補とに基づいて、前記複数の経路候補の各経路候補を移動する際の前記移動者の不快度を目的関数とする最適化問題を生成する問題生成部であって、前記不快度は、前記複数の経路候補の各々を前記移動者が利用するか否かを示す第１決定変数と、前記複数の経路候補の各々を走行する車両の運行状況を表す第２決定変数とを用いて表された問題生成部と、
前記最適化問題を計算することにより、前記第１決定変数と前記第２決定変数とを決定する問題計算部とを備えた。
【発明の効果】
【００１１】
本発明に係る運行計画装置は、問題生成部が、複数の経路候補の各経路候補を移動する際の移動者の不快度を目的関数とする最適化問題を生成する。不快度は、複数の経路候補の各々を移動者が利用するか否かを示す第１決定変数と、複数の経路候補の各々を走行する車両の運行状況を表す第２決定変数とを用いて表される。また、問題計算部は、最適化問題を計算することにより、第１決定変数と第２決定変数とを決定する。よって、本発明に係る運行計画装置によれば、第１決定変数と第２決定変数とを一度に決定することができるので、移動者の満足度が高い運行計画および移動経路を効率的に生成することができる。
【図面の簡単な説明】
【００１２】
【図１】実施の形態１に係る運行計画システム５００の構成図。
【図２】実施の形態１に係る運行計画装置１００の構成図。
【図３】実施の形態１に係る運行計画処理Ｓ１００における受付処理Ｓ１００のフロー図。
【図４】実施の形態１に係る嗜好情報１２を示す図。
【図５】実施の形態１に係る運行計画処理Ｓ１００における運行計画生成処理Ｓ１２０のフロー図。
【図６】実施の形態１の変形例に係る運行計画装置１００の構成図。
【発明を実施するための形態】
【００１３】
以下、本発明の実施の形態について、図を用いて説明する。なお、各図中、同一または相当する部分には、同一符号を付している。実施の形態の説明において、同一または相当する部分については、説明を適宜省略または簡略化する。
【００１４】
実施の形態１．
一般的に、移動者は、複数の交通手段を乗り継いで目的地に移動する。このとき、移動者は、複数の交通手段として、鉄道とバスといった異なる交通機関を利用する。あるいは、移動者は、複数の交通手段として、同じ鉄道という交通機関のうち複数の鉄道路線を利用する。移動者は、複数の交通手段を乗り継いで目的地に移動する。以下では、交通手段を路線と表現する。
【００１５】
また、移動者は、デマンド型交通を利用して目的地に移動する。あるいは、移動者は、従来型交通とデマンド型交通を組み合わせて利用し、目的地に移動する。ここで、従来型交通とは、固定スケジュールのもとで運行する交通である。
デマンド型交通は、車両の移動範囲が制限されている。このため、単一のデマンド型交通のみで任意の移動を達成することは難しい。よって、デマンド型交通の運行計画を生成する際、複数の路線の乗り継ぎを考慮することは重要である。
【００１６】
複数の路線を乗り継ぐ移動において、移動者が目的地に到達するための路線の組み合わせは、複数存在する場合がある。同じ目的地に向かう場合であっても、路線Ａ１と路線Ａ２との２つの路線を乗り継ぐ移動経路と、路線Ｂ１と路線Ｂ２と路線Ｂ３という３つの路線を乗り継ぐ移動経路がある。以下では、移動者が目的地に到達するために選択する路線の組み合わせのことを、移動経路という。
【００１７】
複数の移動経路は、それぞれ異なる特性を有する。移動経路の特性を経路特性と呼ぶ。経路特性とは、移動時間、運賃、路線の乗り継ぎ回数、および車両の混雑度のように、その移動経路を利用した際の満足度に関わる要素である。さらに、移動経路に対する満足度は、移動者の嗜好によって異なる。具体的には、移動時間重視の移動者は、運賃が高い移動経路あるいは乗換え回数が多い移動経路であっても、移動時間が短ければ満足度が高くなる。一方、乗換え回数重視の移動者にとっては、移動時間が長くても乗り換え回数が少ない方が好ましい。このように、複数の路線を乗り継ぐ移動では、移動者の嗜好と、各移動経路の経路特性を考慮して、デマンド型交通の運行計画を最適化することで、移動者の満足度が向上する。
【００１８】
デマンド型交通には、２つのタイプがある。１つ目のタイプは、車両の運行スケジュールと車両の運行経路をオンデマンドに計画するデマンド型交通である。１つ目のタイプの具体例は、オンデマンドバスである。２つ目のタイプは、運行経路は固定であり、運行スケジュールのみをオンデマンドに計画するデマンド型交通である。２つ目のタイプの具体例は、デマンド型の鉄道である。鉄道では、車両が線路上を走行するため、運行経路は固定である。よって、デマンド型の鉄道は、運行スケジュールのみを動的に変更する。
本実施の形態は、１つ目と２つ目の両方のタイプのデマンド型交通に適用できる。また、乗降地点は、車両が停車し、移動者が乗降する地点である。すなわち、バスの停留所および鉄道駅の各々は乗降地点である。
【００１９】
＊＊＊構成の説明＊＊＊
図１を用いて、本実施の形態に係る運行計画システム５００の構成を説明する。
運行計画システム５００は、運行計画装置１００と、移動者端末２００とを備える。
移動者端末２００は、路線を利用する移動者により保有される端末装置である。移動者端末２００は、具体的には、スマートフォン、携帯電話、ＰＣ（パーソナルコンピュータ）、あるいはタブレット端末といった端末装置である。移動者は、移動者端末２００を介して、移動要求１１および嗜好情報１２を運行計画装置１００に送信する。また、移動者は、移動者端末２００を介して、運行計画装置１００から移動経路２２を受信する。
【００２０】
運行計画装置１００は、複数の路線を利用して移動する移動者の移動要求１１に応じて、運行計画２１を生成する。運行計画装置１００は、移動者端末２００から移動要求１１および嗜好情報１２を受信する。運行計画装置１００は、運行計画２１を出力機器に出力する。運行計画装置１００は、移動経路２２を移動者端末２００に送信する。
【００２１】
なお、図１では、運行計画装置１００と通信する移動者端末２００は１台である。しかし、複数の移動者端末が運行計画装置１００と通信してもよい。また、移動者端末２００は、移動者端末２００にインストールされたネイティブアプリケーションを用いて運行計画装置１００と接続される。あるいは、移動者端末２００は、ＷＥＢアプリケーションといった任意の既存技術を用いて運行計画装置１００と接続されてもよい。
【００２２】
図２を用いて、本実施の形態に係る運行計画装置１００の構成を説明する。
運行計画装置１００は、コンピュータである。運行計画装置１００は、プロセッサ９１０を備えるとともに、メモリ９２１、補助記憶装置９２２、入力インタフェース９３０、出力インタフェース９４０、および通信装置９５０といった他のハードウェアを備える。プロセッサ９１０は、信号線を介して他のハードウェアと接続され、これら他のハードウェアを制御する。
【００２３】
運行計画装置１００は、機能要素として、受付部１１０と、抽出部１２０と、決定部１３０と、出力部１４０と、記憶部１５０とを備える。受付部１１０は、要求受付部１１１と嗜好受付部１１２を備える。決定部１３０は、問題生成部１３１と問題計算部１３２を備える。出力部１４０は、運行計画出力部１４１と移動経路出力部１４２を備える。記憶部１５０は、路線情報１５１と運賃情報１５２と地点間移動時間１５３と受付情報１５４を記憶する。
受付部１１０と、抽出部１２０と、決定部１３０と、出力部１４０の機能は、ソフトウェアにより実現される。記憶部１５０は、メモリ９２１に備えられる。
【００２４】
プロセッサ９１０は、運行計画プログラムを実行する装置である。運行計画プログラムは、受付部１１０と、抽出部１２０と、決定部１３０と、出力部１４０の機能を実現するプログラムである。
プロセッサ９１０は、演算処理を行うＩＣ（Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）である。プロセッサ９１０の具体例は、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）、ＤＳＰ（Ｄｉｇｉｔａｌ  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｏｒ）、ＧＰＵ（Ｇｒａｐｈｉｃｓ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）である。
【００２５】
メモリ９２１は、データを一時的に記憶する記憶装置である。メモリ９２１の具体例は、ＳＲＡＭ（Ｓｔａｔｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、あるいはＤＲＡＭ（Ｄｙｎａｍｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）である。
【００２６】
補助記憶装置９２２は、データを保管する記憶装置である。補助記憶装置９２２の具体例は、ＨＤＤである。また、補助記憶装置９２２は、ＳＤ（登録商標）メモリカード、ＣＦ、ＮＡＮＤフラッシュ、フレキシブルディスク、光ディスク、コンパクトディスク、ブルーレイ（登録商標）ディスク、ＤＶＤといった可搬記憶媒体であってもよい。なお、ＨＤＤは、Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅの略語である。ＳＤ（登録商標）は、Ｓｅｃｕｒｅ  Ｄｉｇｉｔａｌの略語である。ＣＦは、ＣｏｍｐａｃｔＦｌａｓｈの略語である。ＤＶＤは、Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋの略語である。
【００２７】
入力インタフェース９３０は、マウス、キーボード、あるいはタッチパネルといった入力装置と接続されるポートである。入力インタフェース９３０は、具体的には、ＵＳＢ（Ｕｎｉｖｅｒｓａｌ  Ｓｅｒｉａｌ  Ｂｕｓ）端子である。なお、入力インタフェース９３０は、ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）と接続されるポートであってもよい。
【００２８】
出力インタフェース９４０は、ディスプレイといった出力機器のケーブルが接続されるポートである。出力インタフェース９４０は、具体的には、ＵＳＢ端子またはＨＤＭＩ（登録商標）（Ｈｉｇｈ  Ｄｅｆｉｎｉｔｉｏｎ  Ｍｕｌｔｉｍｅｄｉａ  Ｉｎｔｅｒｆａｃｅ）端子である。ディスプレイは、具体的には、ＬＣＤ（Ｌｉｑｕｉｄ  Ｃｒｙｓｔａｌ  Ｄｉｓｐｌａｙ）である。
【００２９】
通信装置９５０は、ネットワークを介して他の装置と通信する装置である。通信装置９５０は、レシーバとトランスミッタを有する。通信装置９５０は、有線または無線で、ＬＡＮ、インターネット、あるいは電話回線といった通信網に接続している。通信装置９５０は、具体的には、通信チップまたはＮＩＣ（Ｎｅｔｗｏｒｋ  Ｉｎｔｅｒｆａｃｅ  Ｃａｒｄ）である。
【００３０】
運行計画プログラムは、プロセッサ９１０に読み込まれ、プロセッサ９１０によって実行される。メモリ９２１には、運行計画プログラムだけでなく、ＯＳ（Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ）も記憶されている。プロセッサ９１０は、ＯＳを実行しながら、運行計画プログラムを実行する。運行計画プログラムおよびＯＳは、補助記憶装置９２２に記憶されていてもよい。補助記憶装置９２２に記憶されている運行計画プログラムおよびＯＳは、メモリ９２１にロードされ、プロセッサ９１０によって実行される。なお、運行計画プログラムの一部または全部がＯＳに組み込まれていてもよい。
【００３１】
運行計画装置１００は、プロセッサ９１０を代替する複数のプロセッサを備えていてもよい。これら複数のプロセッサは、運行計画プログラムの実行を分担する。それぞれのプロセッサは、プロセッサ９１０と同じように、運行計画プログラムを実行する装置である。
【００３２】
運行計画プログラムにより利用、処理または出力されるデータ、情報、信号値および変数値は、メモリ９２１、補助記憶装置９２２、または、プロセッサ９１０内のレジスタあるいはキャッシュメモリに記憶される。
【００３３】
運行計画プログラムは、受付部１１０と抽出部１２０と決定部１３０と出力部１４０の各部の「部」を「処理」、「手順」あるいは「工程」に読み替えた各処理、各手順あるいは各工程を、コンピュータに実行させる。また、運行計画方法は、運行計画装置１００が運行計画プログラムを実行することにより行われる方法である。
運行計画プログラムは、コンピュータ読取可能な記憶媒体に記録されて提供されてもよいし、プログラムプロダクトとして提供されてもよい。
【００３４】
＊＊＊機能の説明＊＊＊
次に、運行計画装置１００の各部の機能について説明する。
受付部１１０は、移動者端末２００から、移動要求１１と嗜好情報１２を受け付ける。要求受付部１１１は、移動要求１１を受け付ける。移動要求１１には、出発地、目的地、出発希望時刻、および到着希望時刻が含まれる。移動要求１１には、出発地、目的地、出発希望時刻、および到着希望時刻のうちの一部のみが含まれていてもよい。嗜好受付部１１２は、嗜好情報１２を受け付ける。嗜好情報１２には、経路特性と、移動者が経路特性を重視する度合いとが含まれる。経路特性は、移動者が移動する移動経路の特性である。経路特性の具体例は、移動時間、運賃、路線の乗り継ぎ回数、あるいは車両の混雑度である。嗜好情報１２は嗜好パターンともいう。
【００３５】
記憶部１５０は、運行計画装置１００の動作に必要な情報を記憶する。路線情報１５１は、運行計画装置１００が運行計画を生成する対象となる複数の路線の各路線に関する情報である。路線情報１５１は、複数の路線の各路線に属する乗降地点の情報を含む。運賃情報１５２は、複数の路線の各路線に関する運賃の情報である。地点間移動時間１５３は、複数の路線の各路線における乗降地点間の移動時間である。受付情報１５４には、受付部１１０で受け付けた情報が一時的に記憶される。
【００３６】
抽出部１２０は、移動要求１１を満たす移動経路の候補を、複数の路線から抽出する。以下、移動経路の候補の各々を経路候補という。抽出部１２０は、記憶部１５０に記憶された路線情報１５１と受付情報１５４とに基づいて、移動要求１１を満たす経路候補を、複数の路線から抽出する。
【００３７】
決定部１３０は、記憶部１５０に記憶された各種情報と、抽出部１２０により抽出された経路候補とに基づいて、車両の運行計画２１と移動者の移動経路２２を決定する。
問題生成部１３１は、決定部１３０に入力された各種情報に基づき、車両の運行計画２１と移動者の移動経路２２を決定するための最適化問題を生成する。最適化問題の生成方法については後述する。
問題計算部１３２は、問題生成部１３１で生成した最適化問題を計算する。問題計算部１３２は、最適化問題の解として、車両の運行計画２１と移動者の移動経路２２を算出する。最適化問題を解く方法には、任意の既存技術が利用される。具体例としては、数理計画ソルバと呼ばれるソフトウェアを利用する方法がある。数理計画ソルバには、多くのソフトウェアが知られている。数理計画ソルバには、商用ソフトウェアもあれば、フリーソフトウェアもある。商用の数理計画ソルバとして、Ｇｕｒｏｂｉ  Ｏｐｔｉｍｉｚｅｒがある。数理計画ソルバでは、解くことができる最適化問題のクラスが決まっている。よって、問題生成部１３１は、問題計算部１３２が用いる数理計画ソルバにより解くことができる最適化問題を生成する必要がある。
【００３８】
出力部１４０は、決定部１３０により決定された運行計画２１および移動経路２２を出力する。運行計画出力部１４１は、出力インタフェース９４０を介して、運行計画２１を出力機器に出力する。移動経路出力部１４２は、通信装置９５０を介して、移動経路２２を移動者端末２００に送信する。
【００３９】
＊＊＊動作の説明＊＊＊
次に、本実施の形態に係る運行計画装置１００の各部の動作について説明する。
図３および図５は、本実施の形態に係る運行計画装置１００の運行計画処理Ｓ１００を示す図である。運行計画処理Ｓ１００は、受付処理Ｓ１１０と、運行計画生成処理Ｓ１２０とを有する。受付処理Ｓ１１０は、イベント駆動で実行される処理である。運行計画生成処理Ｓ１２０は、周期的に実行される処理である。
【００４０】
＜受付処理Ｓ１１０＞
図３を用いて、本実施の形態に係る受付処理Ｓ１００について説明する。
ステップＳ１０１において、受付部１１０は、通信装置９５０を介して、移動要求１１および嗜好情報１２を受け付ける。また、受付部１１０は、通信装置９５０を介して、移動要求１１および嗜好情報１２を受け付けた旨のメッセージを移動者端末２００に送信する。移動要求１１および嗜好情報１２は、移動者から不定期で送信される。よって、ステップＳ１０１はイベント駆動である。
ステップＳ１０２において、受付部１１０は、移動要求１１および嗜好情報１２を、受付情報１５４として記憶部１５０に記憶する。
【００４１】
図４を用いて、本実施の形態に係る嗜好情報１２の具体的な内容について説明する。
嗜好情報１２には、経路特性と、移動者がその経路特性を重視する度合いを表す数値とが設定される。以下、重視する度合いを重要度という。具体的には、嗜好情報１２には、移動時間、運賃、路線の乗り継ぎ回数、および車両混雑度の各々が経路特性として設定される。また、嗜好情報１２には、各経路特性に対して重要度が設定される。図４では、移動時間の重要度は０．６、運賃の重要度は０．２、路線の乗り継ぎ回数の重要度は０．１、および車両混雑度の重要度は０．１である。ここで、重要度は、総和が１になるように設定される。図４の嗜好情報１２は、移動時間が短くなることを移動者が最も重視することを示している。
【００４２】
移動者に嗜好情報１２を入力させる方法は、以下の通りである。
１つ目の方法は、移動者に重要度を直接入力させる方法である。
２つ目の方法は、移動者に、移動者が最優先する経路特性のみを選択させる方法である。このとき、受付部１１０は、移動者が最優先する経路特性のみを受け付ける。そして、受付部１１０は、予め定められた規則に基づいて嗜好情報１２を生成する。規則には、移動者が最優先する経路特性の重要度の数値と、その他の経路特性の重要度の数値とが予め定められている。具体例としては、移動者が最優先する経路特性の重要度の数値を０．７とし、その他の３つの経路特性の重要度をそれぞれ０．１とする。この方法により、移動者の入力負荷を下げることができる。
【００４３】
＜運行計画生成処理Ｓ１２０＞
図５を用いて、本実施の形態に係る運行計画生成処理Ｓ１２０について説明する。
運行計画生成処理Ｓ１２０は、周期的に実行される周期実行処理である。運行計画生成処理Ｓ１２０の周期は、運行計画を立案する間隔である。具体的には、運行計画生成処理Ｓ１２０の周期は、１日周期である。周期と運行計画生成処理Ｓ１２０の開始時刻とは予め決められている。
【００４４】
＜＜抽出処理：ステップＳ２０１＞＞
ステップＳ２０１において、抽出部１２０は、移動者ごとに経路候補を抽出する。抽出部１２０は、記憶部１５０に記憶されている路線情報１５１および移動要求１１を用いて、経路候補を抽出する。運行計画生成処理Ｓ１２０では、運行計画を生成する対象の時間区間が予め定められている。この時間区間は、具体的には、当該運行計画生成処理Ｓ１２０の周期の翌日である。抽出部１２０は、この時間区間内に出発希望時刻が含まれる移動要求１１について、移動者ごとに経路候補を抽出する。
【００４５】
ステップＳ２０１の抽出処理について具体的に説明する。
抽出部１２０は、移動要求１１に含まれる出発地と目的地に対し、最短路問題、あるいは最短路問題の応用である第ｋ最短路問題を解くといった処理を実行する。抽出部１２０は、このような処理を実行することにより、移動者ごとに複数の経路候補を求める。このとき、抽出部１２０は、最短路問題で用いられる路の長さを、経路特性を用いて定める。すなわち、抽出部１２０は、路の長さを経路特性に応じて定める。具体的には、抽出部１２０は、経路特性として移動時間を用いる場合、路の長さを移動時間に応じて定める。あるいは、抽出部１２０は、経路特性として運賃を用いる場合、路の長さを運賃に応じて定める。これにより、抽出部１２０は、異なる経路候補を抽出することができる。ここで路の長さは、経路候補における経路特性のスコアとして扱われる。
【００４６】
また、抽出部１２０は、嗜好情報１２を用いて、移動者ごとに経路候補を制限してもよい。具体的には、抽出部１２０は、移動者が移動時間重視である場合、明らかに移動時間のスコアが高い移動経路を経路候補から除外する。このように経路候補を制限することにより、抽出処理Ｓ１２０の計算量が低減される。なお、移動者が必要としない移動経路を経路候補から除外するので、運行計画の品質は維持される。
【００４７】
また、経路候補の抽出数について、予め上限を設けておく。抽出部１２０は、上限の範囲内で経路候補を抽出する。第二の経路候補を抽出することが現実的でない場合は、経路候補の抽出数が上限に満たなくても経路候補の抽出を打ち切ることができる。第二の経路候補を抽出することが現実的でないとは、第一の経路候補に対して、第二の経路候補のスコアが非常に高いといった場合である。打ち切り条件として、次に抽出した経路候補のスコアが他の経路候補に対して２倍以上となった場合に、経路候補の抽出を打ち切るといった条件を採用することができる。
【００４８】
＜＜問題生成処理：ステップＳ２０２＞＞
ステップＳ２０２において、問題生成部１３１は、車両の運行計画と移動者の移動経路を決定するために用いられる最適化問題を生成する。問題生成部１３１は、記憶部１５０に記憶されている各種情報と、抽出部１２０により抽出された経路候補とに基づいて、最適化問題を生成する。
問題生成部１３１は、嗜好情報１２と複数の経路候補とに基づいて、最適化問題を生成する。最適化問題は、複数の経路候補の各経路候補を移動する際の移動者の不快度を目的関数とする。この不快度は、第１決定変数と第２決定変数とを用いて表される。第１決定変数は、複数の経路候補の各々を移動者が利用するか否かを示す。第２決定変数は、複数の経路候補の各々を走行する車両の運行状況を表す。なお、第１決定変数は、複数の経路候補の各経路候補について、各経路候補が利用される場合に１が設定される。また、第１決定変数は、複数の経路候補の各経路候補について、各経路候補が利用されない場合に０が設定される。
【００４９】
最適化問題の生成方法について説明する。以下に、記号の定義を示す。
・Ｕは、運行計画を生成する対象である移動者の集合である。
・Ｒｕは、移動者ｕ∈Ｕについて抽出された経路候補の集合である。
・ｘｕ，ｒは、移動者ｕ∈Ｕが経路候補ｒ∈Ｒｕを利用するか否かを表す第１決定変数である。ｘｕ，ｒは、０または１で表される。ｘｕ，ｒ＝１は経路候補が利用されることを表す。ｘｕ，ｒ＝０は経路候補が利用されないことを表す。ｘｕ，ｒは、移動者がどの経路候補を利用するかを示す第１決定変数の例である。
・ｙは、複数の経路候補の各々を走行する車両の運行状況を表す第２決定変数である。具体的には、ｙは、車両の運行計画を表す決定変数と、移動者が乗車する車両を表す決定変数とから成る決定変数群である。
・ｃｕｔｉｍｅは、移動者ｕ∈Ｕにおける移動時間の重要度を表す定数である。ｃｕｃｏｓｔは、移動者ｕ∈Ｕにおける運賃の重要度を表す定数である。ｃｕｔｒａｎｓは、移動者ｕ∈Ｕにおける路線の乗り継ぎ回数の重要度を表す定数である。ｃｕｃｏｎｇは、移動者ｕ∈Ｕにおける車両の混雑度の重要度を表す定数である。
・ｇｔｉｍｅ（ｕ，ｒ，ｙ）は、第２決定変数ｙで表される車両の運行状況下で、移動者ｕ∈Ｕが経路候補ｒ∈Ｒｕを利用した場合の移動時間の実績を示す数値である。ｇｃｏｓｔ（ｒ）は、移動者ｕ∈Ｕが経路候補ｒ∈Ｒｕを利用した場合の運賃の実績を示す数値である。ｇｔｒａｎｓ（ｒ）は、移動者ｕ∈Ｕが経路候補ｒ∈Ｒｕを利用した場合の路線の乗り継ぎ回数の実績を示す数値である。ｇｃｏｎｇ（ｕ，ｒ，ｙ）は、第２決定変数ｙで表される車両の運行状況下で、移動者ｕ∈Ｕが経路候補ｒ∈Ｒｕを利用した場合の車両の混雑度の実績を示す数値である。これらの関数は、ｕ，ｒ，ｙが与えられれば値を返す関数である。
【００５０】
なお、運賃と路線の乗り継ぎ回数の各々は、移動者ｕ、および第２決定変数ｙで表される車両の運行状況に依存せずに決定できる。このため、運賃と路線の乗り継ぎ回数との各々の実績を示す関数において、ｕとｙは引数になっていない。
移動時間の実績を示す関数ｇｔｉｍｅ（ｕ，ｒ，ｙ）は、乗降地点間の移動時間のみから計算できる。この場合は、路線間の乗り継ぎ時の待ち時間は考慮されない。よって、移動時間の実績を示す関数は、ｇｔｉｍｅ（ｒ）のように引数からｕ，ｙを省略できる。ｇｔｉｍｅ（ｒ）は、ほぼ自明な関数である。移動時間の実績を示す関数に対して乗り継ぎ時の待ち時間を考慮する場合は、引数ｕ，ｙが必要となり、より複雑な関数が必要となる。
車両の混雑度実績を示す関数ｇｃｏｎｇ（ｕ，ｒ，ｙ）は、過去の実績値から類推することにより、ｇｃｏｎｇ（ｒ）のように引数からｕ，ｙを省略できる。ｇｃｏｎｇ（ｒ）は、ほぼ自明な関数である。車両の混雑度実績を示す関数について、実際の乗車人数から詳細に値を決定する場合は、引数ｕ，ｙが必要となり、より複雑な関数が必要となる。
【００５１】
数１の式は、移動者ｕ∈Ｕが経路候補ｒ∈Ｒｕを利用した際の不快度を計算する式である。
【数１】
0006272596.tif 000002
【００５２】
したがって、全移動者の不快度の総和は、数２の式により算出される。
【数２】
0006272596.tif 000003
【００５３】
この数２の式が、最適化問題の目的関数である。移動者ｕ∈Ｕが経路候補ｒ∈Ｒｕを利用しない場合は、第１決定変数ｘｕ，ｒが０となる。このため、移動者ｕ∈Ｕが経路候補ｒ∈Ｒｕを利用しない場合は、不快度は無視される。
決定部１３０は、この目的関数を最小化するような第１決定変数ｘｕ，ｒおよび第２決定変数ｙを求める。そして、決定部１３０は、第１決定変数ｘｕ，ｒおよび第２決定変数ｙから、移動者にとって満足度が高い運行計画および移動経路を求めることができる。なお、第１決定変数ｘｕ，ｒには、数３に表す制約条件が付される。
【数３】
0006272596.tif 000004
【００５４】
＜＜問題計算処理：ステップＳ２０３＞＞
ステップＳ２０３において、問題計算部１３２は、最適化問題を計算することにより、第１決定変数と第２決定変数とを決定する。問題計算部１３２は、不快度、すなわち目的関数を最小とする第１決定変数と第２決定変数とを算出する。問題計算部１３２は、第１決定変数により、移動者に利用されることが示された経路候補を、移動経路として出力部１４０に出力する。また、問題計算部１３２は、第２決定変数により表された車両の運行状況を、運行計画として出力部１４０に出力する。
【００５５】
＜＜出力処理：ステップＳ２０４およびステップＳ２０５＞＞
ステップＳ２０４において、運行計画出力部１４１は、問題計算部１３２から出力された運行計画２１を、出力インタフェース９４０を介して出力機器に出力する。
ステップＳ２０５において、移動経路出力部１４２は、問題計算部１３２から出力された移動経路２２を、通信装置９５０を介して移動者端末２００に送信する。
【００５６】
＊＊＊他の構成＊＊＊
＜変形例１＞
経路特性は、移動時間、運賃、路線の乗り継ぎ回数、および車両混雑度の４項目に限定されない。具体的には、経路特性に、車両から見える景観といった項目が設定されてもよい。また、経路特性に、上記４項目の一部が設定されてもよい。具体的には、経路特性に、車両混雑度以外の、移動時間、運賃、および路線の乗り継ぎ回数の３項目が設定されてもよい。
【００５７】
本実施の形態では、運行計画装置１００の機能がソフトウェアで実現されるが、変形例として、運行計画装置１００の機能がハードウェアで実現されてもよい。
【００５８】
図６は、本実施の形態の変形例に係る運行計画装置１００の構成を示す図である。
運行計画装置１００は、電子回路９０９、補助記憶装置９２２、入力インタフェース９３０、出力インタフェース９４０および通信装置９５０を備える。
【００５９】
電子回路９０９は、受付部１１０と、抽出部１２０と、決定部１３０と、出力部１４０の機能を実現する専用の電子回路である。
電子回路９０９は、具体的には、単一回路、複合回路、プログラム化したプロセッサ、並列プログラム化したプロセッサ、ロジックＩＣ、ＧＡ、ＡＳＩＣ、または、ＦＰＧＡである。ＧＡは、Ｇａｔｅ  Ａｒｒａｙの略語である。ＡＳＩＣは、Ａｐｐｌｉｃａｔｉｏｎ  Ｓｐｅｃｉｆｉｃ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔの略語である。ＦＰＧＡは、Ｆｉｅｌｄ−Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙの略語である。
運行計画装置１００の構成要素の機能は、１つの電子回路で実現されてもよいし、複数の電子回路に分散して実現されてもよい。
別の変形例として、運行計画装置１００の構成要素の一部の機能が電子回路で実現され、残りの機能がソフトウェアで実現されてもよい。
【００６０】
プロセッサと電子回路の各々は、プロセッシングサーキットリとも呼ばれる。つまり、運行計画装置１００において、受付部１１０と、抽出部１２０と、決定部１３０と、出力部１４０の機能は、プロセッシングサーキットリにより実現される。
【００６１】
運行計画装置１００において、受付部１１０と、抽出部１２０と、決定部１３０と、出力部１４０の「部」を「工程」に読み替えてもよい。また、受付処理、抽出処理、決定処理、および出力処理の「処理」を「プログラム」、「プログラムプロダクト」または「プログラムを記録したコンピュータ読取可能な記憶媒体」に読み替えてもよい。
【００６２】
＊＊＊本実施の形態の効果の説明＊＊＊
本実施の形態に係る運行計画装置１００では、抽出部１２０が予め経路候補を抽出する。また、運行計画装置１００は、経路候補の利用有無を示す第１決定変数と、車両の運行状況を表す第２決定変数とを用いて、移動者の不快度を目的関数とする最適化問題を生成する。よって、運行計画装置１００は、最適化問題の解を算出することにより、移動者の嗜好を考慮した運行計画および移動経路を一度に算出することができる。
【００６３】
また、本実施の形態に係る運行計画装置１００では、予め抽出部１２０で経路候補を抽出しておき、各経路候補を利用するか否かを０または１の値を取る決定変数とする。よって、本実施の形態に係る運行計画装置１００によれば、本来、相互に依存関係のある車両の運行計画と移動者の移動経路とを同時に決定することが可能な最適化問題を定式化することができる。
【００６４】
このように、本実施の形態に係る運行計画装置１００によれば、移動者の嗜好パターンと各経路特性とを考慮し、最適な車両の運行計画と移動者の移動経路を求めることができる。よって、本実施の形態に係る運行計画装置１００によれば、移動者の満足度を高めることができる。
【００６５】
実施の形態２．
本実施の形態では、実施の形態１とは異なる点について説明する。なお、実施の形態１と同様の構成には同一の符号を付し、その説明を省略する場合がある。
本実施の形態では、問題生成部１３１により生成される最適化問題が実施の形態１と異なる。その他の構成および動作は実施の形態１と同様である。
【００６６】
実施の形態１では、問題生成部１３１は、移動者ごとに決定変数を割り当て、最適化問題を生成した。本実施の形態では、問題生成部１３１は、まとめられた複数の移動者に対して決定変数を割り当て、最適化問題を生成する。
【００６７】
相違点である最適化問題の生成方法について説明する。以下に、記号の定義を示す。
・Ｔは、時刻の集合である。具体的には、Ｔは、１分単位に離散化された時刻の集合である。
・Ｎは、乗降地点全体の集合である。
・Ｐは、嗜好情報１２が取り得る組み合わせの集合である。
・Ｒｏ，ｄ，ｐは、出発地ｏ∈Ｎから目的地ｄ∈Ｎへ移動し、かつ、嗜好情報ｐ∈Ｐを持つ移動者に対して抽出された経路候補の集合である。
・ｄｔ，ｏ，ｄ，ｐは、時刻ｔ∈Ｔに出発地ｏ∈Ｎから目的地ｄ∈Ｎへ移動する人数のうち、嗜好情報ｐ∈Ｐを持つ人数を表す変数である。
・ｘｔ，ｏ，ｄ，ｒ，ｐは、時刻ｔ∈Ｔに出発地ｏ∈Ｎから目的地ｄ∈Ｎへ移動する人数のうち、嗜好情報ｐ∈Ｐを持ち、かつ、経路候補ｒ∈Ｒｏ，ｄ，ｐを利用する人数を表す第１決定変数である。ｘｔ，ｏ，ｄ，ｒ，ｐは、移動者がどの経路候補を利用するかを示す第１決定変数の例である。
・ｙは、複数の経路候補の各々を走行する車両の運行状況を表す第２決定変数である。具体的には、ｙは、車両の運行計画を表す決定変数と、移動者が乗車する車両を表す決定変数とから成る決定変数群である。
・ｃｐｔｉｍｅは、嗜好情報ｐ∈Ｐを持つ移動者における移動時間の重要度を表す定数である。ｃｐｃｏｓｔは、嗜好情報ｐ∈Ｐを持つ移動者における運賃の重要度を表す定数である。ｃｐｔｒａｎｓは、嗜好情報ｐ∈Ｐを持つ移動者における路線の乗り継ぎ回数の重要度を表す定数である。ｃｐｃｏｎｇは、嗜好情報ｐ∈Ｐを持つ移動者における車両の混雑度の重要度を表す定数である。
・ｇｔｉｍｅ（ｔ，ｏ，ｄ，ｒ，ｙ）は、第２決定変数ｙで表される車両の運行状況下で、時刻ｔ∈Ｔに出発地ｏ∈Ｎから目的地ｄ∈Ｎへ移動する移動者が経路候補ｒ∈Ｒｕを利用した場合の移動時間の実績を示す数値である。ｇｃｏｓｔ（ｏ，ｄ，ｒ）は、出発地ｏ∈Ｎから目的地ｄ∈Ｎへ移動する移動者が経路候補ｒ∈Ｒｕを利用した場合の運賃の実績を示す数値である。ｇｔｒａｎｓ（ｏ，ｄ，ｒ）は、出発地ｏ∈Ｎから目的地ｄ∈Ｎへ移動する移動者が経路候補ｒ∈Ｒｕを利用した場合の路線の乗り継ぎ回数の実績を示す数値である。ｇｃｏｎｇ（ｔ，ｏ，ｄ，ｒ，ｙ）は、第２決定変数ｙで表される車両の運行状況下で、時刻ｔ∈Ｔに出発地ｏ∈Ｎから目的地ｄ∈Ｎへ移動する移動者が経路候補ｒ∈Ｒｕを利用した場合の路線の車両の混雑度の実績を示す数値である。これらの関数は、ｔ，ｏ，ｄ，ｒ，ｙが与えられれば値を返す関数である。なお、運賃と路線の乗り継ぎ回数の各々は、ｔ，ｙに依存せずに決定できる。このため、運賃と路線の乗り継ぎ回数との各々の実績を示す関数において、ｔ，ｙは引数になっていない。
【００６８】
移動時間の実績を示す関数ｇｔｉｍｅ（ｔ，ｏ，ｄ，ｒ，ｙ）は、乗降地点間の移動時間のみから計算できる。この場合、路線間の乗り継ぎ時の待ち時間は考慮されない。移動時間の実績を示す関数は、ｇｔｉｍｅ（ｏ，ｄ，ｒ）のように引数からｔ，ｙを省略できる。ｇｔｉｍｅ（ｏ，ｄ，ｒ）は、ほぼ自明な関数である。移動時間の実績を示す関数について乗り継ぎ時の待ち時間を考慮する場合は、引数ｔ，ｙが必要となり、より複雑な関数が必要となる。
車両の混雑度実績を示す関数ｇｃｏｎｇ（ｔ，ｏ，ｄ，ｒ，ｙ）は、過去の実績値から類推することにより、ｇｃｏｎｇ（ｏ，ｄ，ｒ）のように引数からｔ，ｙを省略できる。ｇｃｏｎｇ（ｏ，ｄ，ｒ）は、ほぼ自明な関数である。車両の混雑度実績を示す関数について実際の乗車人数から詳細に値を決定する場合は、引数ｔ，ｙが必要となり、より複雑な関数が必要となる。
【００６９】
このとき、全移動者の不快度の総和は、数４の式により算出される。
【数４】
0006272596.tif 000005
【００７０】
この数４の式が、最適化問題の目的関数である。
決定部１３０は、この目的関数を最小化するような第１決定変数ｘｔ，ｏ，ｄ，ｒ，ｐおよび第２決定変数ｙを求める。そして、決定部１３０は、第１決定変数ｘｔ，ｏ，ｄ，ｒ，ｐおよび第２決定変数ｙから、移動者にとって満足度が高い運行計画および移動経路を求めることができる。なお、第１決定変数ｘｔ，ｏ，ｄ，ｒ，ｐには、数５の式により表される制約条件が付される。
【数５】
0006272596.tif 000006
【００７１】
以上のように、本実施の形態に係る運行計画装置は、まとめられた複数の移動者に対して決定変数を割り当て、最適化問題を生成する。よって、本実施の形態に係る運行計画装置によれば、変数量が削減される。また、必要な計算時間が低減される。
【００７２】
実施の形態１および２では、運行計画装置の各部を独立した機能ブロックとして説明した。しかし、運行計画装置の構成は、上述した実施の形態のような構成でなくてもよい。運行計画装置の機能ブロックは、上述した実施の形態で説明した機能を実現することができれば、どのような構成でもよい。
【００７３】
実施の形態１および２のうち、複数の部分を組み合わせて実施しても構わない。あるいは、これらの実施の形態のうち、１つの部分を実施しても構わない。その他、これらの実施の形態を、全体としてあるいは部分的に、どのように組み合わせて実施しても構わない。
なお、上述した実施の形態は、本質的に好ましい例示であって、本発明の範囲、本発明の適用物の範囲、および本発明の用途の範囲を制限することを意図するものではない。上述した実施の形態は、必要に応じて種々の変更が可能である。
【符号の説明】
【００７４】
１１  移動要求、１２  嗜好情報、２１  運行計画、２２  移動経路、１００  運行計画装置、１１０  受付部、１１１  要求受付部、１１２  嗜好受付部、１２０  抽出部、１３０  決定部、１３１  問題生成部、１３２  問題計算部、１４０  出力部、１４１  運行計画出力部、１４２  移動経路出力部、１５０  記憶部、１５１  路線情報、１５２  運賃情報、１５３  地点間移動時間、１５４  受付情報、２００  移動者端末、５００  運行計画システム、９０９  電子回路、９１０  プロセッサ、９２１  メモリ、９２２  補助記憶装置、９３０  入力インタフェース、９４０  出力インタフェース、９５０  通信装置。
【要約】
嗜好受付部（１１２）が、経路特性と、移動者が経路特性を重視する度合いとを嗜好情報（１２）として受け付ける。抽出部（１２０）が、移動者の移動要求（１１）を満たす移動経路の候補を複数の経路候補として、複数の路線から抽出する。問題生成部（１３１）は、嗜好情報（１２）と複数の経路候補とに基づいて、複数の経路候補の各経路候補を移動する際の移動者の不快度を目的関数とする最適化問題を生成する。不快度は、複数の経路候補の各々を移動者が利用するか否かを示す第１決定変数と、複数の経路候補の各々を走行する車両の運行状況を表す第２決定変数とを用いて表される。問題計算部（１３２）は、最適化問題を計算することにより、第１決定変数と第２決定変数とを決定する。【図１】
0006272596.tif 000007
【図２】
0006272596.tif 000008
【図３】
0006272596.tif 000009
【図４】
0006272596.tif 000010
【図５】
0006272596.tif 000011
【図６】
0006272596.tif 000012