| 带有预知信息的在线Homing ATSP问题 |
| |
| 引用本文： | 马军平,徐寅峰,温新刚,张惠丽.带有预知信息的在线Homing ATSP问题[J].系统工程理论与实践,2015,35(2):381-387. |
| |
| 作者姓名： | 马军平 徐寅峰 温新刚 张惠丽 |
| |
| 作者单位： | 1. 西安交通大学 管理学院, 西安 710049;
2. 西安工业大学 经济管理学院, 西安 710032;
3. 机械制造系统工程国家重点实验室, 西安 710049 |
| |
| 基金项目： | 国家自然科学基金(61221063,71071123);长江学者和创新团队发展计划(IRT1173) |
| |
| 摘 要： | 针对快递服务网络结构上的非对称性以及可提前获知待服务需求的位置和释放时间的特征,将预知信息引入可返回原点的非对称TSP问题中,提出以服务总成本最小为目标的带有预知信息的在线Homing ATSP问题.分析了该问题竞争比的下界,并且在一般网络图上设计了SSdd(α)算法和PAH-dd算法,分析了算法各自的竞争比.结果表明在线车采取适时等待策略比采取zealous策略更优;并且预知信息越多,在线算法的竞争性能越优.
|
| 关 键 词： | 旅行商问题 预知信息 非对称网络 在线算法 |
| 收稿时间： | 2014-01-24 |
Online homing asymmetric TSP with advanced information |
| |
| MA Jun-ping;XU Yin-feng;WEN Xin-gang;ZHANG Hui-li.Online homing asymmetric TSP with advanced information[J].Systems Engineering —Theory & Practice,2015,35(2):381-387. |
| |
| Authors: | MA Jun-ping;XU Yin-feng;WEN Xin-gang;ZHANG Hui-li |
| |
| Institution: | 1. School of Management, Xi'an Jiaotong University, Xi'an 710049, China;
2. School of Economics and Management, Xi'an Technological University, Xi'an 710032, China;
3. The State Key Lab for Manufacturing Systems Engineering, Xi'an 710049, China |
| |
| Abstract: | Based on the asymmetry of courier service network and the situation in which the location and release time of requests could be known in advance, this paper introduced the advanced information to homing asymmetric TSP, proposed the online homing ATSP with advanced information. A lower bound was given, SS-dd(α) algorithm and PAH-dd algorithm were presented for general metric space. Competitive analysis were given to the two algorithms respectively. The result indicated that the strategy of waiting when necessary has an advantage over zealous strategy, and, the more advanced information, the better the online algorithms perform. |
| |
| Keywords: | travelling salesman problem advanced information asymmetric network online algorithm |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《系统工程理论与实践》浏览原始摘要信息 |
| 点击此处可从《系统工程理论与实践》下载免费的PDF全文 |
|
