这样就近服务的运行里程与最优 值的比值为
（m-1）/3,随着m 增大，比值 10
需求无法预知的车辆调度问题
公平策略（BAL）
设n=k+1，对于每一个车辆 si以及该车辆运行 的路程Di，服务需求r，移动 si 使得 Di d (si , r) 最 小。
在服务需求为n=k+1的任意度量空间内，BAL 策略是k竞争的。
19
道路突发性堵塞路径选择问题
模型构造：
CA (r1, r2 ,L , rk )：遭遇k个堵塞边时用策略A将货物从O点
运到D点的总费用
COPT (r1, r2,L , rk ) ： 相应的离线最优费用
基本假设：
1）去掉堵塞边后图G仍是连通的；
2）只有当运输车走到堵塞边的起点后，才能发现该边 发生堵塞而不能通过；
CA (r1, r2 ,..., rk ) kCOPT (r1, r2,..., rk )
24
道路突发性堵塞路径选择问题
日常生活中的贪婪策略
O3 O2
O
O1
D
25
道路突发性堵塞路径选择问题
城市交通网络结构—— 方格网络
西安市新城区局部地图
巴塞罗那城区局部地图 26
道路突发性堵塞路径选择问题
但是，在n>k+1的度量空间中，BAL是非竞争 策略。
11
需求无法预知的车辆调度问题
例， n=4， k＝2，初始位置c、d。
服务需求 Di d (si , r)
a
M
d
m
a,b,c, d, a,b,c, d,..., a,b,c, d b
c
最优的策略为：先将c处的车辆调到b处， 移动 距离为M，然ቤተ መጻሕፍቲ ባይዱ两个车辆在每次响应服务需求时， 都只需移动m。
