論文
DBSJ Letters Vol.2, No.3――――――――――――――――――――――――――――――――――――

時間制約付き車両配送問題における 顧 客 満 足 度 に 基 づ い た
CVTPR-Tree 手法
CVTPR-Tree Approach for Customer
Satisfaction on Temporal Vehicle Routing
Problem with Time Windows向 直人♥
渡邉 豊英♠馮 鈞♦

Naoto MUKAI Jun FENG
Toyohide WATANABE
公共交通手段としてのデマンドバスが注目されている．将来の大規模な運営のためには，シミュレーションによる利便性と採算性の評価が必要である．我々が対象とする問題はTemporal Vehile Routing Problem with Time Windows と呼ばれ，ある地域内における顧客の乗降時間の制約を含む配送依頼に対し，車両（バス）を的確に配備し，顧客配送を効果的に解決することを目的としている．本論文で提案する
CVTPR‑Tree は，車両を木構造で索引付けすることにより，効率的に短時間で顧客の配車を可能にする．顧客の配送順序は車両の走行距離または顧客の時間制約に基づき決定する.
Demand-bus system is focused as a new transportation
system. The profitability and usability of the systemshould be analyzed for adopting a wide community. In
Temporal Vehicle Routing Problem with Time Windows(TVRPTW) we address, demands with time constraints ofcustomers arise enduringly. Share-ride vehicles transport
customers to their destinations. We propose CVTPR-Treethat indexes vehicles in consideration of time constraints.
The CVTPR-Tree assigns customers to a vehicleeffectively in a short time. Delivery orders for customers
depend on riding distance of vehicles or time constraintsof customers.

1. はじめに利便性の高い交通システムとしてデマンドバスが注目されている．デマンドバスとは乗客の要求に応じて乗降車場所を自由に変更できる乗合いバスのことである．通常の固定路線バスに対し，少ない台数で運営可能なデマンドバスを今後の公共交通手段として検討する自治体が増えてきている．我々の対象と す る Temporal Vehicle Routing Problem withTime Windows (TVRPTW)はデマンドバス問題をシミュレーション・レベルに単純化したものである．ある地域内におけ♥学生会員 名古屋大学大学院情報科学研究科博士後期課
程 naoto@watanabe.nuie.nagoya-u.ac.jp♦学生会員 名古屋大学大学院工学研究科博士後期課程
feng@watanabe.nuie.nagoya-u.ac.jp♠
正会員 名古屋大学大学院情報科学研究科
watanabe@is.nagoya-u.ac.jp

1

る顧客の乗降車時間の制約を含む配送依頼に対し，配備されている車両（バス）による相乗り方式のサービスを行う．この時間制約とは乗車時間制限を意味し，顧客によってその値は異なる．TVRPTW において，解決すべき問題は顧客の車両割当と，顧客の配送順序の決定である．提案する
CVTPR-Tree はリアルタイムに収集された移動オブジェクトに関する位置データを用いて移動オブジェクト（車両）のデータベースを構成する．時々刻々と変化する移動オブジェク
トの位置管理において,位置情報の更新負荷が問題となる.そこで,車両の位置・速度と顧客の乗降位置に基づき時間をパラメータとした包含矩形(Bounding Rectangle)によってオブジェクトの将来の位置を近似表現する.顧客は索引に従って効率的に短時間で車両に割り当られる．また，車両割当後の顧客の配送順序は車両の走行距離または顧客の時間制約に基づき決定される．
2 章では TVRPTW の形式化を述べる．3 章では CVTPRTree を定義し，4 章では CVTPR-Tree に基づく顧客の割当，5 章では配送順序のアルゴリズムを示す．6 章で実験・考察し，7 章でまとめる．

2. TVRPTW
複数台の車両で地域内の全ての要求発生地点を回るためにどのようなルートを走らせるかという問題はVehicle Routing Problem (VRP)と呼ばれる．また，要求に時間制約が付加された問題はVRP with Time Windows (VRPTW)[1][2]と呼ばれる．我々の対象とするTemporal VRPTW (TVRPTW)では，要求が初期段階で与えられるのではなく，時間経過と共に継続的に発生する．これらの問題はＮＰ困難な問題であり，最適解を求めることは非常に困難である．従って，精度のよい近似解を求めることが現実的な解法となる．TVRP
TWを以下のように形式化する．
N 人の顧客を C = {c1 , c2 LcN }とする．顧客 c j の乗降車要求を DEMAND j = ( rj , d j , T j ) と表す． r j と d j はそれぞれ乗降車位置であり，T j は顧客の乗車制限時間である．顧客満足度

CS j を式(1)のように定義する．tr j と td j はそれぞれ乗車時刻と降車時刻である．σ は顧客満足度の曲線の傾きを決定するパラメータであり，値が小さいほど，顧客は満足を得やすいことになる．顧客満足度は図 1 に示すように，制限時間以内に顧客の配送を完了できれば最大値１となり，乗車時間が増加するにつれ値は０に近づく．
CSTC(t)

11

0.8

0.8

0.6

0.6

0.4

0.4

0.2

0.2

0-1-0.5

00.5

1

1.5

22.53P

図 1 顧客満足度の値域
Fig.1 Range of Customer
Satisfaction

0-3-2.5-2-1.5-1-0.50Q(t)図 2 時間制約の値域
Fig.2 Range of TimeConstraint

Pj = ((td j − tr j ) − T j ) / T j
1Pj ≤ 0
CS j =   − Pj exp σ  Pj > 0



(1)

日本データベース学会 Letters Vol.2, No.3

論文
DBSJ Letters Vol.2, No.3――――――――――――――――――――――――――――――――――――
K 台の車両を B = {b1 , b2 , L , bK }とする．車両 bi の時刻 t の位 置 を bi (t ) = ( x i (t ), y i (t )) ， 速 度 ベ ク ト ル をrbi (t ) = (vx i (t ), vy i (t )) と表す．割り当られた顧客の配送順序は図 3 に示すような配列 q i (t ) で与えられる．配列には顧客の乗車・降車位置が格納され，配列の先頭から要求が処理される． 配列は時刻 t をパラメータに持ち時間経過と共にその内容が変化する．
[0]

[1]

[2]

[3]

[4]

[5]

r1

r2

d2

r3

d1d3

←
→←
DR j = (( DR →jx , DR jx ), ( DR jy , DR jy ))DR →jx = min( r jx , d jx )

(4)

DR ←
jx = max(r jx , d jx )車両 bi の要求矩形 DRi を割当られた全顧客 c j ( j = 0, L , k ) の要求矩形 DR j を包含するように定義する(式(5))．

DRi = (( DRix→ , DRix← ), ( DRiy→ , DRiy← ))kDRix→ = min ( DR →jx )図 3 顧客の配送順序配列
Fig.3 Array of Delivery Order
位置 p1 , p 2 間の経路距離を d ( p1 , p 2 ) とする．長さ L の配列を持つ車両 bi の時刻 t の走行コスト | q i (t ) | を式(2)で定義する．
L −1| qi (t ) |= ∑ d (qi (t )[l ], qi (t )[l + 1])

(2)

l =0

TVRPTW に対する研究視点は，車両の走行コスト（採算性）を抑えながら顧客満足度（採算性）を最大化することにある．目的関数は式(3)によって与えられる．

 N
 ∑ CS j 
 j =1max K ∑ | qi (t ) |  i =1


j =0

CVTPR-Tree は更新間隔 I で周期的に更新される．更新時刻
t upd の包含矩形は車両 bi の位置と車両の要求矩形によって決まる(式(6))．

R x→ (t upd ) = min( xi (t upd ), DRix→ )R x← (t upd ) = max( xi (t upd ), DRix← )Rvx→ = vxi (t upd )(3)

移動オブジェクトの位置・速度を管理するための手法として静的オブジェクトの索引手法である R*-Tree[3]を拡張した TPR-Tree[4,5]が提案されている．TPR-Tree は時間 t をパラメータとした包含矩形(Bounding Rectangle)を形成することにより移動オブジェクトを索引付ける．我々の提案するConstraint Vehicle TPR-Tree(CVTPR-Tree)は TPR-Tree の拡張版であり，顧客の乗降車位置と時間制約が考慮される．
以下に CVTPR-Tree の構造を述べる．

3.1 葉ノード
葉ノードは車両 bi へのポインタ，包含矩形 R (t ) ，時間制約TC (t ) から構成される．

(bi , R(t ), TC (t ))包含矩形 R (t ) を x 座標・ y 座標の間隔として定義する．
R (t ) = (( R x→ (t ), R x← (t )), ( R y→ (t ), R y← (t )))以下で包含矩形と時間制約を具体的に定義する．また， x 座標についてのみ考え， y 座標については省略する．

3.1.1 包含矩形
まず，顧客乗降車位置を頂点に持つ四角形を要求矩形(Demand Rectangle)と定義する．顧客 c j の要求矩形 DR j を

2kDRix← = max( DR ←jx )(6)

包含矩形の両端の速度を車両 bi の速度とする(式(7))．

3. CVTPR-Tree

式(4)で定義する．

(5)

j =0(7)

Rvx← = vxi (t upd )時刻 t > t upd の包含矩形を式(8)のように定義する．

R x→ (t ) = R x→ (t upd ) + Rvx→ × (t − t upd )R x← (t ) = R x← (t upd ) + Rvx← × (t − t upd )(8)

3.1.2 時間制約
顧客 c j の時刻 t の時間制約 TC j (t ) を式(9)によって定義する．

ς は制約値の最小値である．図 2 は時間制約値( ς = 0 )の時間経過に伴う変化を示している．車両が制限時間内に顧客の配送完了が充分に可能ならば値は小さいが，時間の経過と共に増加し，制限時間内に配送不可能になると，最大値１となる．

− Tj

r
Q j (t ) =(d (bi , r j ) + d (r j , d j )) / bi(t − tr j ) − T j
rQ j (t ) =(,)/dbdbiji  Q j (t ) + 1  + ςexp
TC j (t ) =   σ

1+ς


(乗車前)
(乗車後)
(9)

Q j (t ) ≤ −1
Q j (t ) > −1

車 両 bi の 時 間 制 約 TC (t ) を 割 り 当 ら れ た 全 顧 客

c j ( j = 0, L , k ) の時間制約値の最大値とする(式(10))．その理由は，現実問題において，時間制約の高い乗車客が一人でもいれば，車両はその顧客を優先して送り届けなくてはならないからである．

日本データベース学会 Letters Vol.2, No.3

論文
DBSJ Letters Vol.2, No.3――――――――――――――――――――――――――――――――――――A( R(t ) U DR j )kTC (t ) = max(TC j (t ))

(10)

j =0

3.2 中間ノード
中間ノードは最大 M の子ノードへのポインタを持つ．従って，木の高さは最も低くて log M ( K ) となる．

3.2.1 包含矩形
子ノード集合の包含矩形を Ri (t ), (i = 0, L , m < M ) とする．
中間ノードの時刻 t upd の包含矩形は全ての子ノードの時刻 t updの包含矩形をさらに包含する矩形として定められる(式(11))．
m→x→ixR (t upd ) = min ( R (t upd ))i =0(11)m←x←ix

R (t upd ) = max( R (t upd ))i =0

包含矩形の両端の速度を子ノード集合の最大・最小の速度と定める（式(12)）．
m→
Rvx→ = min ( Rivx)
i =0R

←vx

(12)

m

式(15)は，時間制約が小さくかつ配送領域の小さい車両を優先する．この手法を CVTPR と呼ぶ．CVTPR は時間制約の最小値 ς が小さければ時間制約を優先し，逆に大きければ配送領域を優先する．

TC (t ) × A( R(t ) U DR j )(15)

5. 顧客配送順序
顧客割当の決定後，顧客の配送順序を決定する．つまり，配送順序を表す配列 q(t)に顧客の乗車・降車位置を挿入する．
以下に２通りの挿入方法を提案する．

5.1 距離優先
走行コスト|q(t)|が最小になるように顧客配送の順序を決定する．図 6 のような顧客要求を考える．図中の(r1,1.0)は乗車位置 r1 と時間制約値 1.0 を意味する．配送順序配列 q(t)は図 7 のようになる．走行コストを優先することにより，顧客の乗車時間が増加してしまい，満足度の低下を引き起こす可能性がある．
(r1,1.0)←ivx= max( R )i =0(14)(d1,1.0)

Vehicle時刻 t の包含矩形は葉ノードと同じ式(8)で定義される．

(r2,0.1)

3.2.2 時間制約
子ノード集合の時間制約を TCi (t ), (i = 0, L , m < M ) とする．

(d2,0.1)(d3,0.5)

時間制約 TC (t ) を式(13)のように子ノード集合の時間制約の平均値として定義する．その理由は，次節で提案する車両割
当アルゴリズムにおいて，車両負荷の偏りを表現する必要があるからである．
mTC (t ) = avg (TC i (t ))(13)i= 03.3

例

要求 DR1 ・ DR 2 を担う車両 b1 と要求 DR3 ・ DR 4 を担う
車両 b2 の包含矩形を図 4 に示す．これらの車両は図 5 に示す
木構造で索引付けされる．

Fig.6

r1

R2

b2(R1,TC1)(R2,TC2)

b1b2

DR1 DR2DR3 DR4

r2

d1d2

r3d3

5.2 満足度優先
顧客の満足度が最大になるように顧客配送の順序を決定する．つまり，顧客の時間制約値が高い順に配送する．配送順
序配列 q(t)は図 8 のようになる．時間制約を優先することにより，顧客の満足度は高くなるが，車両の走行コストも高くなることが考えられる．

(R0,(TC1+TC2)/2)

DR2

図 6 顧客要求
Demands of Customers

図 7 距離優先の配送順序
Fig.7 Traveling Distance Measure

r1

R1DR1(r3,0.5)

d1

r3d3

r2d2

図 8 満足度優先の配送順序
Fig.8 Customer Satisfaction Measure

DR3b1
DR4R0Fig.4

図 4 包含矩形
Bounding Rectangles

Fig.5

図 5 木構造
Tree Structure

4. 車両割当CVTPR-Tree への問合せ処理により車両割当を行う.包含
矩形 R の面積を A( R ) と表す．顧客の要求 DR j が発生したとすると，木の根から式(14)または式(15)を評価しながら，評価値の小さいノードを降下していき，最終的に到達した葉ノードの車両に要求を割り当てる．最短で M ⋅ log M ( K ) のオーダで車両割当が可能である．式(14)は配送領域の小さな車両を優先する．この手法を VTPR と呼ぶ．

36. 実験・考察
提案手法(表 1)を評価実験した．評価項目は，平均顧客満足度(図 9)，平均顧客乗車時間(図 10)，平均走行コスト（図11），配送完了顧客数(図 12)，平均顧客待ち時間(図 13）の５つであり，図中の横軸は車両数を表している．道路ネットワークとして 21×21 のグリッド(キャンバスサイズは 1000×1000 ピクセル)を用いた．終了時刻は t=10000 とし，各時刻に 10％の確率で新たな顧客の要求を発生させる．顧客の乗降車位置と車両の初期位置は道路ネットワークからランダムに選択される．顧客の乗車時間制限 T j は最短到着時間の１〜５倍の間の値でランダムに決定される．また，車両速度r| b |= 5 ，更新間隔 I=10，最大ノード数 M=5，時間制約最小値 ς = 0.1 ，顧客満足度パラメータ σ = 0.5 を実験で用いた．
平均顧客満足度に関して，CS-CVTPR は車両数に依存す日本データベース学会 Letters Vol.2, No.3

論文
DBSJ Letters Vol.2, No.3――――――――――――――――――――――――――――――――――――
ることなく全体的に高い満足度を得ることができた．その理由は満足度優先の配送順序を用いており，一人ずつ着実に配送を完了していくからである．一方，CVTPR と VTPR においては車両数の影響が大きく，車両数に比例して満足度が増加した．また，CVTPR の方が VTPR よりも良い値を示した．
時間制約を車両割当の判断の一つに組み込んだことにより，車両への負荷が分散されたからであると考えられる．また，顧客満足度は平均顧客乗車時間に直結しており，同様の傾向を示した．配送完了顧客数，平均車両走行距離，平均顧客待ち時間に関しては，VTPR と CVTPR は同じような曲線を描き，共に良い値を示した．一方，CS-CVTPR はいずれの項目においても下回る結果となった．その理由は，配送順序において満足度を優先することにより，一人一人の乗車時間は減らせるものの，走行距離が長くなってしまい，配送完了顧客数や顧客待ち時間が増大してしまうからである．以上の結果から，顧客満足度（利便性）を高めることを重視するならば CS-CVTPR が良いが，さらに車両コスト（採算性）も考えるならば CVTPR が相応しい．
表 1 比較手法
Table 1 Comparative Patterns
表記
割当
順序
VTPR
VTPR
距離優先
CVTPR
CVTPR
距離優先
CS-CVTPR
CVTPR
満足度優先

[文献］
[1] M. Desrochers, J.K. Lenstra, M.W.P. Savelsbergh, andF. Soumis: “Vehicle routing with time windows:
Optimization and approximation”, Methods and Studies,
pp.65-84(1988).
[2] M.M. Solomon and J. Desrosiers: “Time window
constrained
routing
andschedulingproblems”,
Transportations Science, pp.1-13(1988).
[3] N. Bechmann, H. P. Kriegel, R. Schneider, andB.Seeger: “The R*-Tree : An efficient and robust accessmethod for points and rectangles”, Proceedings of ACM
SIGMOD 1990, pp.322-331(1990).
[4] Simonas Saltenis, Christian S. Jensen, Scott T.
Leutenegger, and Mario A. Lopez: “Indexing thepositions of continuously moving objects”, Proceedingsof ACM SIGMOD 2000, pp.331-342 (2000).
[5] Sionas Saltenis, and Christian S. Jensen: ”Indexingof moving objects for location-based services,
Proceedings of ICDE 2002, pp.463-473(2002).

向 直人

馮 鈞

7. まとめと今後の課題
本稿ではデマンドバス・システムをシミュレーションし，その利便性・採算性を評価した．提案した CVTPR-Tree は
動的に車両の索引を形成し，短時間かつ効率的な車両割当を可能とした．また，走行距離と顧客満足度を基準とした顧客配送順序を提案した．最後に評価実験を行い，提案手法が有効であることを示した． 最適化アルゴリズムを用いた顧客交換によるパフォーマンスの向上が今後の課題である．

[謝辞]
本研究の一部は，名古屋大学情報系 COE：「社会情報基盤のための音声・映像の知的統合」の支援による．ここに記して感謝の意を表す．また，日頃からご指導頂いた愛知工業大学・石井直宏教授に感謝します．

Naoto MUKAI名古屋大学大学院情報科学研究科博士後期課程在学中．2003
名古屋工業大学大学院工学研究科博士前期課程修了．地理情報システムと高度交通情報システムの研究・開発に従事．情報処理学会学生会員．日本データベース学会学生会員．

Jun FENG

名古屋大学大学院工学研究科博士後期課程在学中．1994 中
国河海大学コンピュータ学院修士課程修了．地理情報システ
ム，空間データベースシステムと空間検索の研究・開発に従事．情報処理学会学生会員．日本データベース学会学生会員．

渡邉 豊英

Toyohide WATANABE

名古屋大学大学大学院情報科学研究科教授. 1974 京都大学
大学院工学研究科修士課程修了．1975 同大学工学研究科博士課程中退．工学博士．統合化環境，分散協調環境，データベース環境，教育支援システム，文書理解に興味を持つ．情報処理学会，電子情報通信学会，日本ソフトウェア科学会，人工知能学会，システム制御情報学会，教育システム情報学会，日本データベース学会会員，ACM，IEEE-CS，AAAI，AACE 各会員．

380

0.9

50000
CS-CVTPR

360

CS-CVTPR
49000

CVTPR

0.85

VTPR

340

CVTPR
VTPR

48000
47000

320

0.8

46000
300
45000
280

0.75

44000
260
43000

0.7

240

CS-CVTPR

42000

22041000

CVTPR

0.65

VTPR

200

40000

1800.6202224262830

図 9 平均顧客満足度
Fig.9 Customer Satisfaction

39000
202224262830

図 10 平均顧客乗車時間
Fig.10 Average of Riding Time

202224262830

図 11 平均車両走行コストFig.11 Average of Traveling Cost

2000

1

CS-CVTPR
1800

0.95

CVTPR
VTPR

1600

0.9
14000.85

1200
1000

0.8

8000.75600

0.7
CS-CVTPR

400

CVTPR
0.65

200

VTPR

00.6
202224262830

図 12 配送完了顧客数
Fig.12 Transportable Customers

4202224262830

図 13 平均顧客待ち時間
Fig.13 Average of Waiting Time

日本データベース学会 Letters Vol.2, No.3