| 转向限制网络中基于预知时间的快递车辆在线揽件路径选择研究 |
| |
| 引用本文： | 马军平,徐寅峰,吴腾宇.转向限制网络中基于预知时间的快递车辆在线揽件路径选择研究[J].系统工程理论与实践,2017,37(9):2394-2402. |
| |
| 作者姓名： | 马军平 徐寅峰 吴腾宇 |
| |
| 作者单位： | 1. 西安工业大学 经济管理学院, 西安 710021;2. 西安交通大学 管理学院, 西安 710049;3. 重庆邮电大学 经济管理学院, 重庆 400065 |
| |
| 基金项目： | 国家自然科学基金（71601152）；中国博士后科学基金（2016M592811）；陕西省自然科学基础研究计划（2015JM7372）；重庆市社会科学规划博士项目（2016BS085） |
| |
| 摘 要： | 针对现实快递服务网络结构上的转向限制及待服务需求出现后不能立即接受服务的特征,将预知时间引入到在线旅行商问题中,提出以服务总时间最小为目标的转向限制网络中基于预知时间的快递车辆在线揽件路径选择问题.在半路径上提出了WBR-dd策略,在路径上提出了REPdd略,在一般网络上提出了PAH-dd策略,证明了上述在线策略的竞争比,分析了该问题竞争比的下界.结果表明预知信息越多,在线算法将获得更优的竞争性能.
|
| 关 键 词： | 在线旅行商问题 预知信息 转向限制网络 在线算法 竞争比 |
| 收稿时间： | 2016-09-23 |
Online routing of express pick-up vehicles with advanced information on the turn restriction network |
| |
| MA Junping,XU Yinfeng,WU Tengyu.Online routing of express pick-up vehicles with advanced information on the turn restriction network[J].Systems Engineering —Theory & Practice,2017,37(9):2394-2402. |
| |
| Authors: | MA Junping XU Yinfeng WU Tengyu |
| |
| Institution: | 1. School of Economics and Management, Xi'an Technological University, Xi'an 710021, China;2. School of Management, Xi'an Jiaotong University, Xi'an 710049, China;3. School of Economics and Management, Chongqing University of Posts and Telecommunications, Chongqing 400065, China |
| |
| Abstract: | Based on the turn restriction of network and the situation in which requests could not be serviced until its release time, this paper introduces the advanced information into online traveler salesman problem, proposes the online routing of express pick-up vehicles with advanced information on the turn restriction network. WBR-dd algorithm, REP-dd algorithm and PAH-dd algorithm are presented on half-path, path and general metric space. Competitive analysis is given respectively. The lower bounds are given. The results indicate that the more advanced information, the better online algorithms perform. |
| |
| Keywords: | online travelling salesman problem advanced information turn restriction network online algorithm competitive ratio |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《系统工程理论与实践》浏览原始摘要信息 |
| 点击此处可从《系统工程理论与实践》下载免费的PDF全文 |
