優先度ベースを用いた配車アルゴリズムの性能評価
M2014SC015 中山遼祐
指導教員：河野浩之

1

はじめに以前より交通の IT 化が進み，タクシー業界にもエリア情報や位置情報を用いることで効率良く客を探索でき，空車状態での無駄な走行を減少するタクシー配車が提案されきている．しかし，どの提案もタクシーが客を獲得する各方法において提案されている．
そこで，本研究では客が電話によってタクシーを要請する際，先行研究 [1] で提案された配車システムに加え，先行研究 [2] で提案された優先度ベースを採用することでより効率いい配車システムを提案する．評価方法として，客の平均待ち時間と空車状態の走行距離を算出し，[1] のみの場合と比較し評価を行う．
本論文の構成は以下の通りである．2 章では配車システ
ムの先行研究，3 章では配車の流れ，優先度ベースルールについて述べる．4 章では地図データ，パラメータの設定，入力ファイル例と実験手順について述べる．5 章では空車走行距離と客の平均待ち時間の算出，評価について述べる．6 章ではまとめを述べる．

2

配車システムの先行研究

ます，タクシーの配車を行うにあたって以下のことを定義する．

• 対象時間区間を T (= [0, t]) とし，さらに，nT 個の期 に分割し，ある期を指すとき f 期 と呼ぶ．
• 対象地域を A とする．さらに，nA 個の エリア に分割し，あるエリアを指すとき エリア q と呼ぶ．
• エリアの集合を Q = 1, 2, ..., nA とする．
• 自社車両 Ci ：すべての状態が観測可能―車両位置，車両エリア：車両の位置は対象地域上のある 1 点の座標で代表される．車両位置はいずれかの 1 つのエリアに含まれ，これを車両エリアという．
―目標エリア：車両は空車時における移動目標とするエリアを１つ持つ．

• 客：自社の車両に乗車した客が観測可能―出現位置，目的位置：客は対象地域内のある１点に位置し，乗車中以外は移動しない．また，客は対象区域内の１点に移動目標を持つ．

3.1

配車までのフローチャート

本章では本研究に関する既存の研究を説明する．まず， 本研究におけるタクシー配車のフローチャートを図 1
タクシーが客を獲得する主な方法として，事前予約や電 に示す.
話による依頼を受けて客を迎えに行く「迎車」，駅前や公共施設のタクシー乗り場で客を待つ「付け待ち」，そして移動しながら客を探す「流し」が存在する．
迎車に関しては配送計画・デマンドバスなどに類似した，適応的に割り当てる手法が提案されている [1][3]．また，[１] では提案されたシステムを従来の「流し」の場合と比較し，コスト面において有用性が高いことが示された．流しに関しては客探索を行うエリア決定の際，あらゆる情報を考慮し，適応的に探索エリアを決定する優
先度ベースルール [2] が提案され，決定されたルールをランダム配車などと比較し有用性が高いことが示された．
[1] では客を目的地で降ろした後の待機場所に関してその地域内のあらゆる情報が考慮されておらず，時間帯によって客が多く発生する場所 (オフィス街，住宅街，繁華街など) に偏りができ [2]，配車を重ねるごとに効率が悪化すると考えられる．
そこで本研究では，迎車において [1] の配車システムを用いる際，各タクシーの待機場所を [2] の優先度ベースルールを採用することで配車を繰り返しても効率の落ちない新たな配車アルゴリズムを提案し，客の平均待ち時間，空車状態の走行距離を先行研究 [1] のパターンと比較し評価を行う．

3

優先度ベースを用いた配車アルゴリズム

本章では 3.1 節で配車の際のフローチャート，3.2 節で優先度ベースルールを述べる．

図 1 配車の際の流れ3.2

優先度ベースルール

4.1

地図データ

ある車両が行き先を要請したときに考える．この車両
本研究で用いる地図を図 2 に示す．地図データにあたっに対する各エリアの優先度を算出し，最も優先度の高い ては OpenStreetMap より取得し，MATES で使えるようエリアを目標エリアとして指示する．このとき，エリア 変換した．対象地域として中心部に商業地区 (勤務先) がごとに優先度を求め，これらの和をエリア優先度とする． あり，その周辺に住宅街があり，そのほかに駅の周辺にこのルールを優先度ベースルール [2] と呼ぶ．
ショッピングモールなどの施設がある．
各優先度に関して本研究では以下の 3 点について考える．

(i) 客が多く発生するエリアでは客を発見しやすい．
(ii) 車両数が少ないエリアでは客の奪い合いになりにくい．
(iii) エリアまでへの移動時間が短ければその分，空車走行によるコストを抑えれる．
次にある f 期における自社車両 Ci に対するエリア q の優先度の算出を示す．

• 優先度 ϕ1i,q ：客数が多いエリアほど高くなる．
ϕ1i,q [f ] =A
4uA
q [f ] + cq [f ]40(1)

ここで，uAq はエリア q で単位時間当たりに発生する客数の推定値で，cAq は単位時間当たりエリア q で過去に自社が獲得した客数である．

• 優先度 ϕ2i,q ：対象車両から近いエリアほど高くなる． 4.2

図 2 使用する地図データパラメータシミュレーション実験を行うにあたり，使用するパラーメータの項目を表 1 に示す．
タクシーは 20 台に設定する．対象地域の面積は 4km
C
ここで，δi,qは対象車両の位置と対象エリアの重心点間
×8km とし，エリアを 4 × 4 の矩形・等分割の 16 個とCの直線距離，θi,qは対象エリアの重心点までの推定移動時する．また，タクシーの待機場所は 1 つのエリアにつき間である．
１ヵ所設ける．客の乗車回数は 300 回とし，目的位置を• 優先度 ϕ3i,q ：自社車両が少ないエリアほど高くなる． 対象地域内で出現位置から距離 1〜5km の範囲でランダムに与えるとする．また，出勤時や帰宅時など時間帯に11C
ϕ3i,q [f ] = (7 C+ log(δ q [f ] + 1))(3) よって客の発生場所に偏りができる．今回は朝の出勤時
5 nq [f ] + 1の 7 時〜9 時を想定して 2 時間のシミュレーションを行Cう．この場合，客の発生場所は住宅街や駅に集中し，目ここで，nC
q は対象エリアにおける自社車両の台数，δqは対象車両を除いた各車両の位置と対象エリアの重心点 的地は商業地区や駅周辺に集中すると設定する．客に関しては流しと違い迎車はあらかじめ呼ぶタクシー会社を間の直線距離の平均値である．
決定するので 300 回全て本研究のタクシーを利用すると• エリア優先度 ϕi,q ：エリア優先度は各優先度を結合し，他社のタクシーは考慮しないものとする．また，タする．すなわち，クシーの初期位置に関しては全エリア均等に配置した状態とする．
3∑rϕi,q [f ] =φi,q [f ](4)

ϕ2i,q [f ] =1

C [f ] + θ C [f ] + 3)
log(2δi,qi,q(2)r=14MATES によるシミュレーション

本研究では知的マルチエージェント交通流シミュレー
タである MATES(Multi-Agent-based Traﬃc and Environment Simulator) を用いてシミュレーションを行う．
本章では，4.1 節で地図データ，4.2 節でパラメータの設定 4.3 節で入力ファイル例と実験手順を述べる．

表 1 パラメータ
シミュレーション時間
2 時間
タクシー台数20 台
対象地域
4km × 8km
エリア数
16 個
客の乗車回数
300 回
客の目的位置1〜5km
タクシーの待機場所
16 か所

4.3

入力ファイル例と実験手順

次にタクシーが配車され新たなエリアまで向かう手順を次に示す．

本研究で使用した MATES ではいくつかの入力ファイルを用いる．ここでは一部を示す．また，入力ファイル (1) 入力ファイル (generateTable.txt) で指定された発生地から客のいる目的地までタクシーが向かうの太線部分の出力結果も図 3，4 で示す．

mapPosition.txt(交差点の座標※一部抜粋)(2) 入力ファイルでは 1 つの目的地しか記述できないた

112,-93,-752,0113,-148,-815,0114,-223,-901,0
記述内容は左から交差点 ID，x 座標 [m]，y 座標 [m]，z座標 [m] である．

め，目的地までのトリップ情報が記述される出力ファ
イルの vehicleTrip.txt よりタクシーが客の位置に到着したらシミュレーション実行中に車両を発生できる Agent Generation ウィンドウを用いて目的地まで設定し自動車をその場に発生させる．

(3) 目的地に到着したら優先度ベースを用いて次に向かうエリアを決定する．エリア決定における各計算はExcel 上で計算した．その際の数値に関しては出力
ファイルの vehicleTrip.txt と各時間ステップにおける各車両の走行状態が出力される vehicle.txt から得た．
(4) その後，Agent Generation ウィンドウを用いてその場に車両を発生させ，そのエリアに向かうよう設定する．

空車走行距離，客の平均待ち時間の評価

5

本章では 5.1 節に空車走行距離と客の平均待ち時間の算出，5.2 節に空車走行距離と客の平均待ち時間の評価について述べる．

5.1

図 3 設定した交差点の様子
generateTable.txt(タクシーの生成※一部抜粋)
81000, 81500, 4180, 2277, 1, 13, 1, 3967
91000, 91500, 2277, 4180, 1, 14, 1, 117
101000, 101500, 3061, 2380, 1, 15, 1, 2379

記述内容は左から開始時刻 [msec]，終了時刻 [msec]，発生地 ID，目的地 ID，発生交通量 [台/時]，車種 ID，経由
交差点数，経由交差点 ID である．

空車走行距離と客の平均待ち時間の算出

ここでは，タクシーの空車状態による合計走行距離と客の平均待ち時間の算出を行う．シミュレーションより得た各車両のトリップデータ情報を出力する vehicleTrip.txtと各時刻ステップにおける各車両の走行状態を出力する

vehicle.txt の 2 つの出力ファイルより算出する．
また，算出にあたって空車走行距離と客の平均待ち時間を求める式を次に示す．

• 空車状態での合計走行距離：V

V =20
∑

Pr + T r(5)

r=1• 客の平均待ち時間：W∑k
W =図 4 タクシーが発生している様子

r=1 Mrk(6)vehicleTrip.txt(各車両のトリップ情報※一部抜粋)

000117,369.998,22200
000208,103.333,6200
000160,328.333,19700
000241,103.333,6200
000215,191.667,11500
000233,190.911,11500


記述内容は左から車両 ID，目的地までの走行距離 [m]，目的地までの走行時間 [msec] である．

timeline/vehicle.txt(※一部抜粋)

図 6 は客の乗車回数 50 回毎の客の平均待ち時間の平均を示している．各項目において左が優先度ベースを用い(各時刻ステップにおける各車両の走行状態)ない場合を表し，右が優先度ベースを用いる場合を表し000000,20,-1883.13,808.732,0,139.708,0,4.30722,ている．優先度ベースを用いない場合は 50 回から 300 回
1.47477,NULL,004007004074,に 2.11 分増加しているのに対し，優先度ベースを用いた
000001,20,1048.81,928.798,0,160.201,0,16.3626,場合は 1.61 分にとどまった．また，50 回の時点では優先
3.04091,NULL,000487000488,
度ベースを用いなかった場合に比べて優先度ベースを用
いた場合が 1.44 分短くなっており，最終的な 300 回の時
記述内容は左から車両 ID，車種 ID，x，y，z 座標，XY 点では優先度ベースを用いなかった場合に比べて 1.94 分
回転角，Z 回転角，速度 [m/s]，加速度 [m/s2 ]，交差点 短くなり，優先度ベースを用いた場合，配車を繰り返したときの客の平均待ち時間とその増加値が優先度ベース
ID，単路部 ID である．
を用いなかった場合に比べ下回ることができた．
5.2 空車走行距離と客の平均待ち時間の評価
これらの結果から優先度ベースを用いた方が優先度ベー
優先度ベースを用いない先行研究と優先度ベースを用 スを用いなかった場合と比べて効率の配車が行えたと言いる本研究での空車走行距離と客の平均待ち時間を算出 える．これは優先度ベースを用いた場合は客の降車後にした．その値をグラフ化したものを図 5，6 に示す．
あらゆる情報を考慮し，待機するエリアを選択することで配車を繰り返しても安定的な配車を行えたためである．

6

図 5 タクシーの空車走行距離
図 5 は客の乗車回数 50 回毎の合計の空車走行距離を示している．各項目において左が優先度ベースを用いない場合を表し，右が優先度ベースを用いる場合を表している．50 回の時点で優先度ベースを用いた場合が優先度ベースを用いなかった場合より 0.9km 短く，そこまで差がなかったが最終的な 300 回の時点では優先度ベースを用いた方が 157.2km 短くなった．

まとめ本研究では優先度ベースを用いた配車アルゴリズムをMATES 上で 4km × 8km の地域でタクシー 20 台によって空車走行距離と客の平均待ち時間で評価した．客の乗車回数を 300 回行ったときに優先度ベースを用いた場合が優先度ベースを用いない場合に比べ空車走行距離が 157.2km短くなった．また，客の平均待ち時間に関しては優先度ベースを用いない場合が乗車回数 50 回から 300 回にかけて 2.11 分増加したのに対し，優先度ベースを用いた場合は 1.61 分の増加にとどまった．また，最終的に優先度ベースを用いた場合は優先度ベースを用いなかった場合に比べ 1.94 分下回ることができ，空車走行距離と客の平均待ち時間の両方において湯鮮度ベースを用いた方が効率の良い配車を行えることが示せた．また，実際のタクシー会社のデータをもとにより大規模な環境で優先度ベースを用いればより正確な評価が得られるであろうと考えられる．

参考文献[1] Chi-Hsuan Wu，S.K.Jason Chang，Chih-Hsu Lin
Evaluation of cruising taxi operations in the Taipei
met ropolitan area ，Life Science Journal，Vol.11
No.3 pp.160-165，2014[2] 大原誠，玉置久， 客獲得数向上のためのタクシー車両
配車問題のモデル化と目標エリア決定ルールの構成 ，
電気学会論文誌 C，Vol.132，No.10，pp.1545-1655，
2010.
[3] B.Chen，H.H.Cheng， A review of the applicationsof agent technology in traﬃc and transportation systems ，IEEE Trans. Intelligent Transportation Systems，Vol.11，No.2，pp.485-497，2010．

図 6 客の平均待ち時間