摘要
用户打算从出发地s去目的地d,针对路段上的权重无法准确预知就必须做出决策,选择出行路径去目的地的问题。从占线与竞争策略的角度出发进行考虑,设计了最大权最小策略及贪婪策略选择路径,假设路段上的实际权重ωe和最大权重Te满足关系式ωe≥αTe的情形下,证明了这两个策略的竞争比都是1/α,并证明了这两个策略都是最优策略,其中α∈[0,1]。
To solve the problem that users choose their path under the uncertain edge weight from s to d in a traffic network, the method of online and competitive analysis is put forward and design the minmax weight strategy and greed strategy are designed to solve the problem, the competitive ratio of the two strategies are all 1/a under the assumption that the formula ωc≥aTc is held, where ωc, Tc are the real weight and max weight on edge e respectively, the constant a ∈ [0,1].
出处
《系统工程》
CSCD
北大核心
2009年第5期117-120,共4页
Systems Engineering
基金
国家自然科学基金资助项目(70525004
60736027
70702030)
关键词
占线问题
路段权重
竞争分析
竞争比
Online Problem
Road Section Weight
Competitive Analysis
Competitive Ratio
