这样就近服务的运行里程与最优 值的比值为
(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。