摘要
针对n次连续的交通需求依次到达出发点选择路径到目的地去的问题,本文从占线与竞争策略的角度出发,研究流量是任意可分的情形下交通流量分配,采用系统最优策略分配交通需求,即每次分配流量后都能使得当前网络上所有用户花费费用总和最小。借助于变分不等式对系统最优策略进行了竞争分析,特别地,当路阻函数是系数非负的线性函数时,证明该策略是4-竞争的;当路阻函数是系数非负、度数至多是d的多项式函数时,该策略是(d+)d+1-竞争的,同时给出系统最优策略竞争比的下界是5/3。
This paper explores the issue of arriving at the starting point in file to choose the route to the destination under n sequential traffic demands. From the point of view of online and competitive strategy, we define flow as the distribution of traffic volume in arbitrarily divisible situations. A system optimal strategy is put forward to assign traffic demand under the assumption that every assignment of flow will be able to minimize the total sum of all on-line users＇ expenses. The System optimal strategy is analyzed bY resorting to variational inequality; the strategy is 4-competitive if the road impedance function is linear function with nonnegative coefficient, and is （d＋ 1）d＋1-competitive if the road impedance function is the polynomial function with nonnegative coefficient and the most degree d, meanwhile, a lower bound on the competitive ratio of system optimization strategy 5/3 is given.
出处
《系统工程》
CSCD
北大核心
2009年第3期16-20,共5页
Systems Engineering
基金
国家杰出青年基金资助项目(70525004)
国家自然科学基金重点资助项目(60736027)
关键词
占线问题
竞争比
系统最优
流量分配
Online Problem
Competitive Ratio
System Optimal
Traffic Distribution
