带有线性惩罚的在线旅行商问题

发布时间：2018-06-12 22:51

  本文选题：旅行商问题 + 线性惩罚　； 参考：《计算机集成制造系统》2017年04期

【摘要】：为了在自然灾害之后通过应急车辆尽快地将应急物资送到受灾点,针对每个受灾点在发出需求信号后,不能尽快被应急车辆服务,从而导致受灾点的情形进一步恶化的情形,提出了带有线性惩罚的在线旅行商问题。通过设计最坏序列证明了该问题在一般网络上不存在确定性和随机性的在线算法。针对需求点仅在线段上的情形,分析了问题的下界、设计了推测后再移动策略,并证明了当单个需求点的最大惩罚值大于等于8时,该算法为最优算法。
[Abstract]:In order to deliver emergency supplies to the disaster site as soon as possible through emergency vehicles after a natural disaster, the emergency vehicle service cannot be served as soon as possible after each disaster site has issued a demand signal, thus leading to a further deterioration of the situation at the disaster site. An online traveling salesman problem with linear penalty is proposed. By designing worst-case sequences, it is proved that there are no deterministic and stochastic online algorithms for this problem in general networks. For the case that the demand point is only on the line segment, this paper analyzes the lower bound of the problem, designs a speculative removing strategy, and proves that the algorithm is an optimal algorithm when the maximum penalty value of a single demand point is greater than or equal to 8.
【作者单位】： 重庆邮电大学经济管理学院;西安交通大学管理学院;西安交通大学机械制造系统工程国家重点实验室;重庆交通大学管理学院;
【基金】：重庆市社会科学规划博士基金资助项目(2014BS108,2016BS085) 重庆市教委科技基金资助项目(KJ1600525) 陕西省自然科学基础研究计划资助项目(2015JM7372) 重庆邮电大学文峰创新创业基金资助项目(WF201406)~~
【分类号】：TP301.6

【相似文献】

相关期刊论文 前10条

1 王大志;汪定伟;闫杨;;一类多旅行商问题的计算及仿真分析[J];系统仿真学报;2009年20期

2 莫愿斌;刘贺同;王勤;;旅行商问题的综述教学研究[J];中国科教创新导刊;2008年08期

3 顾大权;徐四林;袁媛;汪晋;;求解旅行商问题的一个有效算法[J];解放军理工大学学报(自然科学版);2006年02期

4 陈文兰;戴树贵;;旅行商问题算法研究综述[J];滁州学院学报;2006年03期

5 江贺;张宪超;陈国良;;有向黑白旅行商问题[J];计算机学报;2007年03期

6 管琳;白艳萍;;用分支定界算法求解旅行商问题[J];中北大学学报(自然科学版);2007年02期

7 黄可为;汪定伟;;热轧计划中的多旅行商问题及其计算方法[J];计算机应用研究;2007年07期

8 张敏;金琴玲;;旅行商问题的一种新解法[J];重庆职业技术学院学报;2008年01期

9 高春涛;;求解旅行商问题的几种解法[J];边疆经济与文化;2010年05期

10 刘冠佳;刘水强;;一类多出发点多旅行商问题规划算法[J];山东理工大学学报(自然科学版);2011年02期

相关会议论文 前7条

1 冯纯伯;;旅行商问题的一种解法[A];1991年控制理论及其应用年会论文集（下）[C];1991年

2 胡巧华;吴怀宇;陈乔礼;陈媛;;一种求解旅行商问题的启发交叉算子的研究[A];第25届中国控制会议论文集（中册）[C];2006年

3 张辉;王锡淮;肖健梅;;基于改进蚁群算法的旅行商问题[A];2007中国控制与决策学术年会论文集[C];2007年

4 刘春波;潘丰;杨丹;;基于改进的蚁群算法在中国旅行商问题中的求解[A];2007中国控制与决策学术年会论文集[C];2007年

5 韩爱丽;朱大铭;;旅行商问题的一种新DNA编码方案[A];2006年全国理论计算机科学学术年会论文集[C];2006年

6 贾亚军;丛爽;;粒子群与模拟退火的混合算法求解旅行商问题[A];'2010系统仿真技术及其应用学术会议论文集[C];2010年

7 董亚非;谭刚军;张社民;;基于粘贴系统求解TSP问题[A];提高全民科学素质、建设创新型国家——2006中国科协年会论文集（下册）[C];2006年

相关博士学位论文 前1条

1 王刚;两类圈问题的算法研究[D];国防科学技术大学;2013年

相关硕士学位论文 前10条

1 徐东镇;蚁群算法及其在广义旅行商问题求解中的应用[D];合肥工业大学;2007年

2 王玲丽;随机存储下的有容量限制的广义旅行商问题[D];上海交通大学;2012年

3 高峰;求解多目标旅行商问题的进化算法研究[D];华东师范大学;2013年

4 覃锦华;求解旅行商问题的进化算法[D];西安电子科技大学;2008年

5 李天龙;基于自组织优化算法的多旅行商问题的求解与应用[D];浙江大学;2010年

6 南小康;树算法求解旅行商问题[D];兰州大学;2008年

7 刘仁洪;一种改进的蚁群算法求解旅行商问题[D];山东大学;2008年

8 胡平;群集智能算法在不确定旅行商问题中的应用研究[D];吉林大学;2007年

9 李国宁;基于捕食搜索的蚁群算法及其在旅行商问题中的应用研究[D];华南理工大学;2010年

10 吴晓维;求解旅行商问题和非线性方程组的蚁群算法[D];陕西师范大学;2008年

，

本文编号：2011364