不确定旅行商问题的鲁棒模型与算法

doi:10.11772/j.issn.1001-9081.2014.07.2090

计算机应用 ›› 2014, Vol. 34 ›› Issue (7): 2090-2092.DOI: 10.11772/j.issn.1001-9081.2014.07.2090

不确定旅行商问题的鲁棒模型与算法

麻存瑞,马昌喜

兰州交通大学交通运输学院，兰州 730070

收稿日期:2014-01-20 修回日期:2014-03-12 出版日期:2014-07-01 发布日期:2014-08-01
通讯作者: 马昌喜
作者简介:麻存瑞(1986-)，男，甘肃兰州人，硕士研究生，主要研究方向：物流系统优化与仿真；马昌喜(1979-)，男，湖北汉川人，副教授，博士，主要研究方向：交通运输系统优化。
基金资助:
国家自然科学基金资助项目;甘肃省科技计划资助项目

Robust model and algorithms for uncertain traveling salesman problem

MA Cunrui,MA Changxi

School of Traffic and Transportation, Lanzhou Jiaotong University, Lanzhou Gansu 730070, China

Received:2014-01-20 Revised:2014-03-12 Online:2014-07-01 Published:2014-08-01
Contact: MA Changxi

摘要/Abstract

摘要：

考虑到不确定参数在旅行商问题(TSP)中广泛存在，在Bertsimas鲁棒离散优化理论的框架下，建立了不确定旅行商问题的鲁棒优化模型，并按转换规则将鲁棒模型转换为鲁棒对等模型。给出了一种求解旅行商问题的基于Prufer数编码的单亲遗传算法，与求解该类问题的传统遗传算法相比，该算法缩减了染色体长度，避免了传统交叉和变异操作破坏染色体可行解的缺陷。通过算例验证，表明该算法有较高的求解效率，所建立的鲁棒模型在不确定环境下能得到较好的鲁棒解。

Abstract:

Considering the fact that uncertain parameters were widespread in the Traveling Salesman Problem (TSP), this paper built a robust optimization model for traveling salesman problem under the frame of Bertsimas robust discrete optimization theory, and then transformed it into robust counterpart model according to transformational rule. In addition, a single parent genetic algorithm based on Prufer coding was designed to solve the traveling salesman problem. Compared with the traditional genetic algorithm, the method has shortened the length of the chromosome and prevented feasible solutions being destructed by the traditional crossover and mutation operators. According to the validation by numerical examples, the results show that the algorithm has a higher solving efficiency, and the robust model developed in the uncertain environment can get some better robust solutions.

中图分类号:

TP301.6

麻存瑞马昌喜. 不确定旅行商问题的鲁棒模型与算法[J]. 计算机应用, 2014, 34(7): 2090-2092.

MA Cunrui MA Changxi. Robust model and algorithms for uncertain traveling salesman problem[J]. Journal of Computer Applications, 2014, 34(7): 2090-2092.

参考文献

[1]ZHANG J, TIAN B, LI X. Solving TSP with improved multi-Agent genetic algorithm［J］. Journal of Computer Applications, 2008, 28(4): 954-956.(张继军,田宝国,李萧.用改进的多智能体遗传算法求解旅行商问题［J］.计算机应用,2008,28(4):954-956.)
[2]BERTSIMAS D，SIM M．The price of robustness［J］．Operations Research，2004，52(1)：35-53.
[3]SOYSTER A L. Convex programming with set-inclusive constraints and applications to inexact linear programming ［J］. Operations Research, 1973, 21(5):1154-1157.
[4]BEN-TAL A, NEMIROVSKI A. Robust convex optimization［J］．Mathematics of Operations Research, 1998, 23(4): 769-805.
[5]BEN-TAL A, NEMIROVSKI A. Robust solutions to uncertain linear programs［J］. Operations Research Letters, 1999, 25(1): 1-13.
[6]BEN-TAL A, GORYASHKO A, GUSLITZER E, et al．Adjustable robust solutions of uncertain linear programs［J］．Mathematical Programming，2004，99(2)：351-376.
[7]MULVEY J M, VANDERBEI R J, ZENIOS S A. Robust optimization of large-scale systems［J］. Operational Research, 1995, 43(2): 264-281.
[8]MULVEY J M, RUSZCZYNSKI A. A new scenario decomposition method for large-scale stochastic optimization［J］. Operational Research, 1995, 43(3): 477-490.
[9]MA C. Optimization of emergency transportation and logistics system［M］. Chengdu: Southwest Jiaotong University Publishing House, 2014.(马昌喜. 应急交通与物流系统优化［M］.成都: 西南交通大学出版社, 2014.)
[10]SONG H. A partheno-genetic algorithm for solving the degree-constrained minimum spanning tree problem［J］. Systems Engineering-Theory and Practice, 2005,29(4):61-66.(宋海洲.求解度约束最小生成树的单亲遗传算法［J］.系统工程理论与实践,2005,29(4):61-66.)
[11]WANG X, WU Y. Optimal algorithm for coding and decoding Prufer codes［J］. Journal of Chinese Computer Systems, 2008, 29(4): 687-690．(王晓东,吴英杰.Prufer编解码的最优算法［J］.小型微型计算机系统,2008,29(4):687-690.)
[12]TSPLIB［EB /OL］. ［2014-03-11］.http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/tsp/.

[1]	肖智豪胡志华朱琳. 求解冷链物流时间依赖型车辆路径问题的混合自适应大邻域搜索算法[J]. 计算机应用, 0, (): 0-0.
[2]	沙林秀，聂凡，高倩，孟号. 基于布朗运动与梯度信息的交替优化算法[J]. 计算机应用, 0, (): 0-0.
[3]	董永峰孙跃华高立超韩鹏季海鹏. 基于改进一维卷积和双向长短期记忆神经网络的故障诊断方法[J]. 计算机应用, 0, (): 0-0.
[4]	李大海刘庆腾艾志刚王振东. 基于动态D向分割和混沌扰动的阴阳对算法[J]. 计算机应用, 0, (): 0-0.
[5]	雷鹰郑万波魏嵬夏云霓李晓波刘诚武谢洪. 基于概率性能感知演化博弈策略的混合“云+边”环境中任务卸载方法 [J]. 计算机应用, 0, (): 0-0.
[6]	乔钢柱王瑞孙超利. 基于分解的高维多目标改进进化算法[J]. 计算机应用, 0, (): 0-0.
[7]	朱诚潘旭华张勇. 基于趋化校正的哈里斯鹰优化算法[J]. 计算机应用, 0, (): 0-0.
[8]	平凡汤小春潘彦宇李战怀. 不规则任务在图形处理器集群上的调度策略[J]. 计算机应用, 0, (): 0-0.
[9]	杨杰张名扬芮晓彬王志晓. 融合节点覆盖范围和结构洞的影响力最大化算法[J]. 计算机应用, 0, (): 0-0.
[10]	汤安迪, 韩统, 徐登武, 谢磊. 混沌精英哈里斯鹰优化算法[J]. 计算机应用, 2021, 41(8): 2265-2272.
[11]	李蒙蒙, 秦伟, 刘艺, 刁兴春. 结合头脑风暴优化的混合蚁群优化算法[J]. 计算机应用, 2021, 41(8): 2412-2417.
[12]	张闻强, 邢征, 杨卫东. 基于多区域采样策略的混合粒子群优化求解多目标柔性作业车间调度问题[J]. 计算机应用, 2021, 41(8): 2249-2257.
[13]	张祥飞, 鲁宇明, 张平生. 基于协同进化的约束多目标优化算法[J]. 计算机应用, 2021, 41(7): 2012-2018.
[14]	张萌, 李维华. 用户互动表示下的影响力最大化算法[J]. 计算机应用, 2021, 41(7): 1964-1969.
[15]	王宇, 刘燕丽, 陈劭武. 基于顶点冲突学习的最大公共子图算法[J]. 计算机应用, 2021, 41(6): 1756-1760.

不确定旅行商问题的鲁棒模型与算法

Robust model and algorithms for uncertain traveling salesman problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics