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

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

单位：西安交通大学管理学院 西安710049 西安工业大学经济管理学院 西安710032 机械制造系统工程国家重点实验室 西安710049