| 具有服务时长的在线TSP问题 |
| |
| 引用本文： | 马军平,徐寅峰,陈聪,吴腾宇.具有服务时长的在线TSP问题[J].系统工程理论与实践,2015,35(11):2832-2839. |
| |
| 作者姓名： | 马军平 徐寅峰 陈聪 吴腾宇 |
| |
| 作者单位： | 1. 西安交通大学 管理学院, 西安 710049;2. 西安工业大学 经济管理学院, 西安 710032;3. 机械制造系统工程国家重点实验室, 西安 710049 |
| |
| 基金项目： | 国家自然科学基金(61221063);长江学者和创新团队发展计划(IRT1173) |
| |
| 摘 要： | 针对城市快递揽件服务过程中,需求事先无法预知并且每个需求服务时长不确定的情形,提出具有服务时长的在线TSP问题.分别在一般网络图上和直线上证明了此问题的竞争比下界进而在一般网络上给出PAH-ST算法,在直线上给出PQR-ST算法,并对算法进行了竞争性能分析.本文提出模型是在线TSP问题的一般形式,结论可以为快递车辆的实时调度决策提供依据.
|
| 关 键 词： | 旅行商问题 服务时长 在线算法 竞争比 |
| 收稿时间： | 2014-06-19 |
Online traveling salesman problem with service time |
| |
| MA Jun-ping,XU Yin-feng,CHEN Cong,WU Teng-yu.Online traveling salesman problem with service time[J].Systems Engineering —Theory & Practice,2015,35(11):2832-2839. |
| |
| Authors: | MA Jun-ping XU Yin-feng CHEN Cong WU Teng-yu |
| |
| 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 situation in which the requests could not be predicted in advance and the service time of each request is uncertain, this paper proposes the online traveling salesman problem with service time. A lower bound and PAH-ST algorithm are presented for general metric space. Moreover, a lower bound and PQR-ST algorithm are presented for real line. Competitive analyses are given to the two algorithms respectively. The model proposed in this paper is the general form of the traveling salesman problem. The conclusion can provide the basis of real-time scheduling for delivery vehicles. |
| |
| Keywords: | traveling salesman problem service time online algorithm competitive ratio |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《系统工程理论与实践》浏览原始摘要信息 |
| 点击此处可从《系统工程理论与实践》下载免费的PDF全文 |
|
