| 基于预知信息的占线Nomadic TSP问题 |
| |
| 引用本文： | 温新刚,徐寅峰,丁黎黎. 基于预知信息的占线Nomadic TSP问题[J]. 系统工程理论与实践, 2013, 33(11): 2845-2851. DOI: 10.12011/1000-6788(2013)11-2845 |
| |
| 作者姓名： | 温新刚 徐寅峰 丁黎黎 |
| |
| 作者单位： | 1. 西安交通大学 管理学院, 西安 710049;2. 西安交通大学 智能网络与网络安全教育部重点实验室, 西安 710049;3. 山东科技大学 经济管理学院, 青岛 266590 |
| |
| 基金项目： | 国家自然科学基金(71071123,60921003,71001057,71371111);长江学者和创新团队发展计划(IRT1173);山东省博士基金(2010BSE06034) |
| |
| 摘 要： | 自然灾害的频繁发生使得应急减灾倍受关注, 尤其有效的应急救援车辆调度对应急减灾非常重要. 针对受灾点被提前获知但是不能立即接受救援服务的情形, 通过将受灾点(需求)的揭露时间和释放时间引入Nomadic TSP模型中构建了预知信息的占线Nomadic TSP问题, 并分别给出了问题的下界, 直线网络结构下的ENO-dd算法, 和一般网络结构下的GTR-dd算法, 并对算法进行了竞争性能分析. 结果表明两个算法随着预知信息的增多会有明显改进. 更为一般的预知信息结构以及最优的算法设计是下一步研究的方向.
|
| 关 键 词： | 旅行商问题 预知信息 占线路径选择 竞争分析 |
| 收稿时间： | 2011-10-21 |
Online nomadic TSP based on advanced information |
| |
| WEN Xin-gang,XU Yin-feng,DING Li-li. Online nomadic TSP based on advanced information[J]. Systems Engineering —Theory & Practice, 2013, 33(11): 2845-2851. DOI: 10.12011/1000-6788(2013)11-2845 |
| |
| Authors: | WEN Xin-gang XU Yin-feng DING Li-li |
| |
| Affiliation: | 1. School of Management, Xi'an Jiaotong University, Xi'an 710049, China;2. Ministry of Education Key Lab for Intelligent Networks and Network Security, Xi'an Jiaotong University, Xi'an 710049, China;3. School of Economics and Management, Shandong University of Science and Technology, Qingdao 266590, China |
| |
| Abstract: | The frequent occurrence of natural disasters has drawn people's attention to the aftermath work, especially the effective routing of emergency vehicles carrying relief efforts. Based on the situation where some disaster hit areas can be informed in advance while could not accept emergency service, this paper introduces the disclosure date and release date to nomadic TSP model, studies an online nomadic TSP problem based on advanced information, and gives a lower bound. When the metric space is the real line, an ENO-dd algorithm is presented. For general metric spaces, a GTR-dd algorithm is presented. Competitive analysis is given for these two algorithms respectively. The results indicate that the more advanced information, the better these two algorithms perform. More general information structure and optimal algorithm design can be the future research. |
| |
| Keywords: | traveling salesman problem advanced information online vehicle routing problems competitive analysis |
|
| 点击此处可从《系统工程理论与实践》浏览原始摘要信息 |
|
点击此处可从《系统工程理论与实践》下载全文 |
|
