R4年度 ⼤⼿町・丸の内・有楽町地区駐⾞環境対策協議会研究助成

乗合タクシーのライドシェア問題における空席ごとの受⼊柔軟性の差に着⽬した⽬的関数の提案
1. 研究の背景・⽬的

2. シミュレーションの諸条件⎜ 対象地域•⎜ Ride-sharing problemとは（dial-a-ride problemとも）ØØ

オンデマンドの乗合サービス（乗合タクシー、デマンドバス）の運⽤にあたって、個々の⾞両がどの乗客群をいかなる経路で運送するのか⎜ 需要データ

巡回経路を求める（Vehicle Routing Problem）にあたってNP困難であり、乗⾞定員、リクエスト数の規模が⼤きくなると厳密解を求める計算時間が⻑く⎜ 道路ネットワークデータ••

内容

Schuller etal. (2021)

リクエストの拒否率の空間的な不平等さをジニ係数で定義し、ジニ係数を下げることを⽬的に、拒否率の⾼いエリアを出発地とするリクエストによる乗客の所要時間のコストを下げた⽬的関数を提案
需要と供給の空間的な偏りによる運送効率の低下を抑制するために、需要の多い地区に向かう割り当ての乗客の所要時間のコストを低減する⽬的関数を提案⎜ 研究の⽬的
悪天候時など需要が過多となり供給が逼迫する特定の状況において、多くのリクエストを運送する⽬的関数の提案

⎜ 新規性
Ø

1.
2.

390台、480台、570台、660台、750台、840台

•

研究

Ø

道路ネットワークデータをOpenStreetMapから⽣成
各リンクの旅⾏速度は道路交通センサスを基に補正⎜ ⾞両台数：6シナリオ

実際に乗合タクシーを運⽤する際に何を持って優れた解とするのか⽬的関数について考慮することが必要、⽬的関数について分析・⼯夫した既往研究は数少なく分析・改善の余地

Fielbaum etal. (2022)

東京のタクシー 20212) に基づくタクシー輸送実績とPT調査データから⽣成（1⽇あたり51,141トリップ）•⎜ 課題意識Ø

東京都の⼤丸有地区を中⼼とした16の⼩ゾーン（第6回東京都市圏パーソントリップ調査）

空席ごとの価値の差（受け⼊れ柔軟性の差）に着⽬した⽬的関数を提案

Schuller, P., Fielbaum, A. and Alonso-Mora, J. (2021) “Towards a geographically even level of service in ondemand ridepooling”, In 2021 IEEE International Intelligent Transportation Systems Conference (ITSC)，pp. 24292434.
Fielbaum, A., Kronmueller, M. and Alonso-Mora, J. (2022) “Anticipatory routing methods for an on-demandridepooling mobility system”, Transportation，49(6)，pp.1921-1962.

Ø

初期位置については、神⽥駅前交差点、⼋重洲中央⼝前交差点、新橋駅銀座⼝前交差点のリンクに運⽤台数の3分の1ずつ配置

Ø

東京のタクシー2021から推定される対象地域の1⽇の実働⾞両2,338⾞と⽐較して少数対象地域の道路ネットワークデータ

3.1 AMアルゴリズムの概要!" !# !!

⎜ 解法の分類

リクエスト群に該当しない

n Exact：整数計画問題として定式化し、厳密解を得る
n Dynamic：未来の需要が既知でなく柔軟に需要に対応
n バッチベース：⼀定時間リクエストの蓄積をまたてから⼀括して割り当て•

本研究は30秒ごとにバッチ処理を⾏う⎜ AMアルゴリズムの概要… 乗り合うことが不可能な組み合わせは!" !#全てのリクエス
ト群の集合&"!" !!
!# !!

!"# $"ℎ &!
!"Ø リクエスト群の定義
n 30秒間に新たに⽣じたリクエストの集合を!! 、前回以前のバッチ処理で既に⾞両が割り当てられているが乗⾞前のリクエストの集合を!"n !! と!" の和集合!# に含まれるリクエストのうち、乗り合うことが可能な組合せをリクエスト群と定義
Ø 全てのリクエスト群の集合と全⾞両の集合は2部グラフを成し、バッチ処理では後述するコストとペナルティを最⼩化する式を解くマッチングを採⽤!#$" = $"ℎ &!
&!

!! = !#$ %"﻿リクエスト群と⾞両の2部グラフとトリップ（3リクエスト・2⾞両の場合）

全⾞
両の集合

R3年度 ⼤⼿町・丸の内・有楽町地区駐⾞環境対策協議会研究助成

3.2
整数線形問題オンデマンド型乗合交通におけるトリップ・⾞両の割り当てアルゴリズムの分析

数学表記min $ %' & ' + $ )) *+ + + $ )) *, +!,#∈ %,&トリップのコスト項

s. t.

'∈()∈*!

)) +$1)∈*"%' = 1∀+ ∈ 4.

拒否ペナルティ項2':)∈)./ '$%' ≤ 1

∀7 ∈ 83':010.2 '1.

式(1)はトリップのコストと拒否ペナルティからなる、最⼩化する⽬的関数
n 拒否リクエストには⼤きな定数ペナルティを設定しているため、既に拒否リクエスト数は可能な限り最⼩化
n トリップのコスト項を⼯夫することで次回以降のバッチ処理の拒否リクエスト数を削減することを⽬的とも解釈

SymbolMeaning!!

30秒間に新たに⽣じたリクエストの集合!"

前回以前のバッチ処理で既に⾞両が割り当てられているが乗⾞前のリクエストの集合!#!! と!" の和集合"

1つのリクエスト#

運⽤されている全⾞両の集合

$

1つの⾞両

%

2部グラフにおけるリクエスト群と⾞両の辺がトリップであり、条件を満たしながら運送することのできる全てのトリップの集合&

1つのトリップ"'( &&に割り当てられたリクエスト群$'ℎ &&に割り当てられた⾞両"'( $⾞両$に既に乗⾞済みのリクエストの集合*$

トリップ&が採⽤された際にのみ1の値をとる⼆値変数2.

式(2)は!! に含まれる全てのリクエストはいずれかのトリップによって運送される、もしくは拒否されることを条件付け+%

リクエスト"が拒否された時にのみ1の値をとる⼆値変数3.

式(3)は個々の⾞両に2つ以上のリクエスト群は割り当てられないことを条件付け-! "30秒間に⽣じたリクエスト"(∈ !! )が拒否される際の定数ペナルティ（24時間）-" "既に⾞両が割り当てられているが乗⾞前のリクエスト"(∈ !" )が拒否される際の定数ペナルティ （24,000時間）. &トリップ&のコスト/& ", &トリップ&に従って運送される際のリクエスト"の到着遅延時間

Ø 上記の整数計画問題を解くマッチングをリクエストと⾞両の割り当てとして採⽤
Ø 式(1)〜(3)の整数計画問題を解くにあたって最適化ソルバーとしてオープンソースソフトウェアのGLPKを⽤いた

3.3

4.1 ⽬的関数

リクエストに⾞両を割り当てる条件と2部グラフ

ベースシナリオ!) " =乗客の到着遅延時間

1.

待ち時間の許容最⼤値を6分

2.

到着遅延時間の許容最⼤値を11分

3.

乗⾞定員を4名$#∈#%& '!! " =Ø 初回のバッチ処理で⾞両が割り当てられなかったリクエスト（そのリクエストが含まれるどのリクエスト群にも⾞両が割り当てられなかった場合）は運送拒否となり、次回以降のバッチ処理で扱われない
n 拒否リクエストによるペナルティ項を介して整数線形問題に影響を及ぼす（なるべく拒否リクエストが発⽣しないマッチングに）⎜ 2部グラフの作成$1 − '! ( )" *, " +!! " = $ "%&' (, " *"∈$ %max&∈&'( ",%$

1 − '! ( )" *, " + '! )! "⾞両の予定所要時間

5Symbol

Meaning#! ", !

トリップ!に従って運送される際のリクエスト"の到着遅延時間#" !

トリップ!による⾞両%の所要時間 （バッチ処理時点から未利⽤⾞両になるまでの予定所要時間）&"区間[0,1]の値をとる⾞両の所要時間の重みを⽰す⽐率
⾞両の所要時間の重みシナリオ
&"

シナリオ

4.3 ⽬的関数.* /, "
* 2'3" (, "10004﻿数学表記(c)空席制約度シナリオ
制約の強さ)" *, "#∈#%& !%( 'Ø リクエスト群と⾞両の2部グラフを作成し、待ち時間・到着遅延時間の最⼤許容値と乗⾞定員4名の条件を満たしながら運送することのできる全てのトリップ（リクエスト群と⾞両の辺）の集合"を探索

制約時間$#∈#%& !%( '#∈#%& 'Ø 加えて、!! に含まれるリクエストについては、既定の割り当てよりも待ち時間が増加しないという条件を付す

4.2 ⽬的関数)" *, " +(a) LOS最⼤化&" = 0(b) VKT最⼩化&" = 1(d)空席柔軟度シナリオ

影響を与える空席数

6!! " = $ "%&' (, " *"∈$ %﻿数学表記
SymbolMeaning" !

トリップ!に含まれる全降⾞地点の集合#

1つの降⾞地点!$%& #, !

トリップ!における、降⾞地点dの降⾞時刻と直前の降⾞地点の降⾞時刻（なければバッチ処理時刻）の差(&) #, !

トリップ!における、降⾞地点dとそれ以降の降⾞地点で降⾞するリクエストの集合*&+! #, !

トリップ!における、降⾞地点dにおける降⾞前の利⽤予定のない空席数（正確には、降⾞直前の移動を含む以降の最⼩空席数）+& − ++ 4, "+&* .'/"& − $ "%&' (, " * max* .'/" (, "'∈'() ",%
1000
1000

7"∈$ %

仮にずっと空⾞であった時の柔軟度

期間の⻑さ﻿数学表記

SymbolMeaning!!

到着遅延時間の許容最⼤値（11分）"#$%!

乗⾞定員（4名）

期間中の柔軟性

期間中の空席数

5. シミュレーション結果
表 各シナリオのLOSとVKT指標
シナリオ
運用台数 390台(a) LOS最大化

拒否リクエスト数

平均待ち時間（秒）

1台当たり平均 計算時間
走行距離（km） （mm:ss）

234.3
202.0
232.9
223.9-1.5 ) ( 10.8% , 21.9 ) ( -2.6% ,225.0
217.7-9.4 ) ( 7.8% , 15.7 ) ( -2.7% ,230.0
211.2-4.4 ) ( 4.6% , 9.2 ) ( -1.1% ,233.3
227.3-6.0 )227.1-6.3 )
230.8-2.5 )

7:48
8:04

4,788
219.4
158.5
4,500
218.4
191.9
( -6.0% , -287 ) ( -0.5% , -1.1 ) ( 21.0% , 33.3 ) ( -4.2% ,3,930
204.4
176.9
( -17.9% , -857 ) ( -6.8% , -15.0 ) ( 11.6% , 18.4 ) ( -4.2% ,4,293
212.3
168.8
( -10.3% , -494 ) ( -3.2% , -7.1 ) ( 6.5% , 10.3 ) ( -1.6% ,223.1
213.8-9.3 )213.8-9.3 )
219.5-3.6 )

9:09
9:35

1,967
200.0
104.7
211.0
1,797
201.7
150.0
198.5
( -8.7% , -170 ) ( 0.9% , 1.7 ) ( 43.4% , 45.4 ) ( -5.9% , -12.5 )
1,444
182.7
126.4
199.3
( -26.6% , -523 ) ( -8.6% , -17.3 ) ( 20.8% , 21.8 ) ( -5.5% , -11.7 )
1,640
192.1
117.2
206.4
( -16.6% , -327 ) ( -3.9% , -7.8 ) ( 12.0% , 12.6 ) ( -2.2% , -4.6 )

9:02
10:28

844
180.9
59.9
196.9
797
187.8
111.7
182.3
( -5.5% , -47 ) ( 3.8% , 6.9 ) ( 86.5% , 51.8 ) ( -7.4% , -14.6 )
572
166.0
87.6
184.1
( -32.2% , -272 ) ( -8.3% , -15.0 ) ( 46.3% , 27.7 ) ( -6.5% , -12.8 )
706
174.1
73.4
191.5
( -16.3% , -138 ) ( -3.8% , -6.8 ) ( 22.7% , 13.6 ) ( -2.7% , -5.4 )

9:08
10:15

230
166.1
38.4
180.7
192
177.5
88.7
166.2
( -16.5% , -38 ) ( 6.9% , 11.4 ) ( 131.2% , 50.3 ) ( -8.0% , -14.5 )18153.3
62.7
168.4( -92.1% , -212 ) ( -7.7% , -12.8 ) ( 63.4% , 24.3 ) ( -6.8% , -12.3 )69160.4
50.3
175.2( -70.0% , -161 ) ( -3.4% , -5.7 ) ( 31.1% , 11.9 ) ( -3.0% , -5.5 )

8:38
11:36

14
153.3
20.4
164.6
23168.6
70.6
151.4(b) VKT最小化( 63.4% ,9 ) ( 10.0% , 15.3 ) ( 246.6% , 50.2 ) ( -8.0% , -13.2 )17144.4
44.3
153.9(c) 空席制約度( 20.4% ,3 ) ( -5.8% , -8.9 ) ( 117.6% , 23.9 ) ( -6.5% , -10.7 )15149.4
30.6159.9(d) 空席柔軟度( 7.7% ,1 ) ( -2.5% , -3.9 ) ( 50.4% , 10.3 ) ( -2.9% , -4.7 )*(a) LOS最大化を基準とした増減率と差分をカッコ内に示した

6:37
8:52

(b) VKT最小化(c) 空席制約度(d) 空席柔軟度
運用台数 480台(a) LOS最大化(b) VKT最小化(c) 空席制約度(d) 空席柔軟度
運用台数 570台(a) LOS最大化(b) VKT最小化(c) 空席制約度(d) 空席柔軟度

10,0689,698( -3.7% , -370 ) ( -0.6% ,9,167( -8.9% , -901 ) ( -4.0% ,9,498( -5.7% , -570 ) ( -1.9% ,平均車内遅延時間（秒）図 ⾞両の状態別台数の推移（400台運⽤）

8:06
8:05

9:58
9:55

10:44
10:10

運用台数 660台(a) LOS最大化(b) VKT最小化(c) 空席制約度(d) 空席柔軟度
運用台数 750台(a) LOS最大化(b) VKT最小化(c) 空席制約度(d) 空席柔軟度
運用台数 840台(a) LOS最大化

8:49
8:44

6. シミュレーション結果の分析

8:56
8:26

⎜ 表 LOSとVKT指標•(c)：最も拒否リクエスト数を削減 、(d)：(c)に劣るが拒否リクエストを削減••(c),(d)：平均待ち時間が減少、⾞内遅延時間が増加、VKTが減少(c),(d)：運⽤台数に余裕が出ると拒否リクエスト削減の優位性が失われる⎜ 図 ⾞両の状態別台数推移•(c)空席制約度シナリオは8時~19時の時間帯の4名乗⾞の⾞両台数と停⾞台数が多く7:30
7:14

空席ごとの受⼊柔軟性に着⽬した⽬的関数は拒否リクエスト数を削減
将来的なオンデマンドの乗合の配⾞・運送ロジックへの活⽤に期待