| 带有配额的在线Nomadic旅行商问题 |
| |
| 引用本文： | 吴腾宇,徐寅峰. 带有配额的在线Nomadic旅行商问题[J]. 运筹与管理, 2016, 25(2): 1-6. DOI: 10.12005/orms.2016.0037 |
| |
| 作者姓名： | 吴腾宇 徐寅峰 |
| |
| 作者单位： | 1.西安交通大学 管理学院,陕西 西安 710049;2.机械制造系统工程国家重点实验室,陕西 西安 710049 |
| |
| 基金项目： | 国家自科基金(61221063),长江学者和创新团队发展计划(No.IRT1173) |
| |
| 摘 要： | 由于自然灾害的频繁发生,灾后的应急物资车辆调度受到了社会的广泛重视,而应急车辆尽快地将应急物资送到受灾点显得尤为重要。针对应急车辆装载物资能力有限和应急车辆不必返回出发点的情形,提出了带有配额的在线Nomadic旅行商问题。分析了该问题在正半轴和一般网络上的下界,针对受灾点仅在正半轴上的情形设计了WTAIB算法,针对受灾点在一般网络上设计了WSB算法,并进一步分析了两个算法的竞争性能。
|
| 关 键 词： | 配额旅行商问题 在线算法 竞争性分析 |
| 收稿时间： | 2014-03-06 |
Online Quota Nomadic Traveling Salesman Problem |
| |
| WU Teng-yu,XU Yin-feng. Online Quota Nomadic Traveling Salesman Problem[J]. Operations Research and Management Science, 2016, 25(2): 1-6. DOI: 10.12005/orms.2016.0037 |
| |
| Authors: | WU Teng-yu XU Yin-feng |
| |
| Affiliation: | 1.School of Management, Xi’an Jiaotong University, Xi’an 710049, China;2.The State Key Lab for Manufacturing Systems Engineering, Xi’an 710049, China |
| |
| Abstract: | Due to the frequent occurrence of natural disasters, routing of the emergency vehicles after disaster is gaining extensive attention, and emergency vehicles transporting emergency materials to affected points as soon as possible seem very important. This paper considers the situation that the emergency vehicle has finite capacity and the emergency vehicle is nomadic. We analyze online quota nomadic TSP. We give the lower bounds of the problem, when metric space is positive half-line, and WTAIB algorithm is presented. For general metric space, WSB algorithm is presented, and competitive analysis is given for these two algorithms respectively. |
| |
| Keywords: | quota traveling salesman problem online algorithm competitive analysis |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《运筹与管理》浏览原始摘要信息 |
|
点击此处可从《运筹与管理》下载全文 |
|
