带有预知信息的在线Homing ATSP问题

发布时间：2018-03-06 12:25

  本文选题：旅行商问题　切入点：预知信息　出处：《系统工程理论与实践》2015年02期 　论文类型：期刊论文

【摘要】：针对快递服务网络结构上的非对称性以及可提前获知待服务需求的位置和释放时间的特征,将预知信息引入可返回原点的非对称TSP问题中,提出以服务总成本最小为目标的带有预知信息的在线Homing ATSP问题.分析了该问题竞争比的下界,并且在一般网络图上设计了SSdd(α)算法和PAH-dd算法,分析了算法各自的竞争比.结果表明在线车采取适时等待策略比采取zealous策略更优;并且预知信息越多,在线算法的竞争性能越优.
[Abstract]:In view of the asymmetry in the network structure of express delivery service and the characteristics of knowing the location and release time of the need for service in advance, the predictive information is introduced into the asymmetric TSP problem which can return to the origin. This paper presents an online Homing ATSP problem with predictive information aiming at the minimum total service cost, analyzes the lower bound of the competition ratio of the problem, and designs the SSdd- (伪) algorithm and the PAH-dd algorithm on the general network diagram. The results show that the in-time waiting strategy is better than the zealous strategy, and the more information is predicted, the better the competitive performance of the online algorithm is.
【作者单位】： 西安交通大学管理学院;西安工业大学经济管理学院;西安交通大学机械制造系统工程国家重点实验室;
【基金】：国家自然科学基金(61221063,71071123) 长江学者和创新团队发展计划(IRT1173)
【分类号】：TP393.01

【参考文献】

相关期刊论文 前1条

1 温新刚;徐寅峰;丁黎黎;;基于预知信息的占线Nomadic TSP问题[J];系统工程理论与实践;2013年11期

【共引文献】

相关期刊论文 前2条

1 马卫民;董丹丹;王珂;;基于特殊路径的局内车辆路径问题混合策略研究[J];运筹与管理;2011年05期

2 温新刚;徐寅峰;丁黎黎;;基于预知信息的占线Nomadic TSP问题[J];系统工程理论与实践;2013年11期

相关会议论文 前1条

1 ;Dial-a-Ride Problem with Time-Windows and On-Line Algorithms[A];中国运筹学会第七届学术交流会论文集（上卷）[C];2004年

相关博士学位论文 前4条

1 余炜;若干网络排序问题的算法和复杂性研究[D];华东理工大学;2010年

2 包晓光;一些路线问题的算法设计与分析[D];华东理工大学;2012年

3 周洁;车辆调度问题的算法及复杂性[D];华东师范大学;2013年

4 于波;快运网络构建及快运车辆配载配送优化研究[D];大连海事大学;2013年

相关硕士学位论文 前2条

1 贺朝新;动态TSP遗传算法研究[D];中南民族大学;2010年

2 杨鸣;动态多目标TSP演化算法研究[D];中国地质大学;2008年

【相似文献】

相关期刊论文 前10条

1 龚元浩;杨晨晖;;基于感知评价的三维信号识别的一种在线算法[J];计算机工程与科学;2009年05期

2 王明岳;;目标可移动的直线搜索问题的在线算法研究[J];计算机工程与科学;2008年12期

3 仵博;吴敏;;基于Monte Carlo粒子滤波的POMDPs在线算法[J];控制与决策;2013年06期

4 王洪涛;邹鹤良;李达强;何国渊;;基于左右手运动想象的在线算法设计与应用[J];数据采集与处理;2013年06期

5 吕淑平;方兴杰;;基于独立分量分析的自适应在线算法[J];计算机应用研究;2010年11期

6 帅典勋;在可编程序的逻辑阵列(PLA)中交叉点故障定位的一种在线算法[J];计算机工程;1984年06期

7 贺文武;;在线核学习的一般形式探讨[J];福建工程学院学报;2010年04期

8 仵博;吴敏;佘锦华;;基于点的POMDPs在线值迭代算法[J];软件学报;2013年01期

9 肖鸣宇;沈正翔;;带有多折扣选项的滑雪租赁问题的在线和离线算法[J];软件学报;2014年05期

10 余建军;吴春明;;支持接入控制的虚拟网映射近似算法[J];电子与信息学报;2014年05期

相关会议论文 前4条

1 柏庆国;张玉忠;;有尺寸的单机在线分批排序[A];中国运筹学会第七届学术交流会论文集（中卷）[C];2004年

2 何宇新;韩志刚;;多层递阶方法时变参数估值最佳初值和最佳跟踪的在线算法[A];1992年中国控制与决策学术年会论文集[C];1992年

3 石永强;张国川;;工件尺寸不同的单台批处理机加工在线问题[A];中国运筹学会第七届学术交流会论文集（上卷）[C];2004年

4 尹焕平;孙宗海;;基于自然梯度的支持向量回归在线算法[A];2009中国控制与决策会议论文集（3）[C];2009年

相关博士学位论文 前3条

1 李文杰;具有交货期或友好释放时间的在线排序研究[D];郑州大学;2014年

2 农庆琴;在线排序与路由安排[D];郑州大学;2006年

3 黄禹潇;面向复杂诊断贝叶斯网实时推理问题的离线、在线算法的研究[D];吉林大学;2012年

相关硕士学位论文 前7条

1 张韬;带前瞻的在线最大化问题[D];复旦大学;2008年

2 吴用;平行机覆盖问题的半在线算法研究[D];浙江大学;2006年

3 高洁;批容量有界的单机分批列表在线排序[D];郑州大学;2011年

4 刘幼珠;基于在线算法的进口设备投资决策研究[D];华南理工大学;2014年

5 马平娟;两类单机批容量有界的分批在线排序[D];郑州大学;2012年

6 王明岳;m射线路径上移动目标搜索的在线算法研究[D];复旦大学;2009年

7 高文君;序列标注的在线算法研究[D];复旦大学;2011年

，

本文编号：1574828