带有预知信息的在线Homing ATSP问题

摘要：

针对快递服务网络结构上的非对称性以及可提前获知待服务需求的位置和释放时间的特征,将预知信息引入可返回原点的非对称TSP问题中,提出以服务总成本最小为目标的带有预知信息的在线Homing ATSP问题.分析了该问题竞争比的下界,并且在一般网络图上设计了SS-dd(α)算法和PAH-dd算法,分析了算法各自的竞争比.结果表明在线车采取适时等待策略比采取zealous策略更优;并且预知信息越多,在线算法的竞争性能越优.

关键词：旅行商问题、预知信息、非对称网络、在线算法

所属期刊栏目：35

分类号：C935(管理学)

资助基金：国家自然科学基金61221063,71071123;长江学者和创新团队发展计划IRT1173

在线出版日期：2015-04-08（万方平台首次上网日期，不代表论文的发表时间）

页码：381-387