基于随机机会约束规划模型的旅行商问题及其求解算法
本文关键词：基于随机机会约束规划模型的旅行商问题及其求解算法
【摘要】：为了提高旅行商的效率,将旅行时间引入旅行商问题(TSP),以最短时间和最短路径为目标对旅行商问题进行求解。假设旅行商在不同城市间的旅行时间服从正态分布,以最短路径为优化目标,将旅行时间以一定的置信水平成立作为机会约束条件,构建了旅行商问题的随机机会约束规划模型。提出已构建模型的确定性等价类,设计出遗传算法并编写算法代码,以一定规模的城市为例进行仿真验证。结果表明:给定期望的总旅行时间和置信水平时,可经过计算得出最短距离,并绘制出最优路径图,同时验证了所提出模型的可行性和算法的有效性。
【作者单位】： 北京交通大学轨道交通控制与安全国家重点实验室;北京交通大学交通运输学院;北京市商业学校物流交通系;
【关键词】： 旅行商问题 随机机会约束规划 遗传算法
【基金】：轨道交通控制与安全国家重点实验室(北京交通大学)自主研究课题(RCS2013ZZ001)
【分类号】：U116
【正文快照】： 0引言旅行商问题(traveling salesman problem,TSP)是一个典型的组合优化难题,属于NP难题。TSP可叙述为:在N个城市中,寻求一条旅行商可到达每个城市且只到一次的最短路径,这种TSP仅寻求一个性能指标,即最短路径。TSP在许多领域都有着广泛的应用,已经解决了交通运输、管道敷设
【参考文献】
中国期刊全文数据库 前9条
1 唐立新;旅行商问题(TSP)的改进遗传算法[J];东北大学学报;1999年01期
2 卢厚清,王辉东,黄杰,李波;任务均分的多旅行商问题[J];系统工程;2005年02期
3 刘荷花;崔超;陈晶;;一种改进的遗传算法求解旅行商问题[J];北京理工大学学报;2013年04期
4 陈斌,徐华中;一种改进遗传算法及其在TSP问题中的应用[J];计算机工程;2002年09期
5 朱献文;李福荣;;求解旅行商问题的几种智能算法[J];计算机与数字工程;2010年01期
6 周辉仁;唐万生;魏颖辉;;基于GA的最小旅行时间的多旅行商问题研究[J];计算机应用研究;2009年07期
7 陈德良;陈治亚;;随机的库存—路径问题的机会约束规划模型与算法[J];模糊系统与数学;2010年03期
8 吕善国;曹义亲;陈红丽;;求解旅行商问题的一种新方法[J];华东交通大学学报;2012年05期
9 刘星材;何世伟;孙杨;黎浩东;;基于时间满意度的铁路枢纽空车调配随机机会约束模型及算法研究[J];铁道学报;2013年09期
【共引文献】
中国期刊全文数据库 前10条
1 阮怀忠,张建中;基于改进遗传算法的TSP问题求解[J];安徽建筑工业学院学报(自然科学版);2003年04期
2 苏发慧;;模糊支持向量机在粮食安全预警中的应用[J];安徽建筑工业学院学报(自然科学版);2009年02期
3 韦忠良;崔斌;;基于管径的管道输水灌溉管网优化设计[J];安徽农业科学;2009年25期
4 张琳;李海燕;王莉;;模糊需求下批量生产优化模型[J];辽宁科技大学学报;2008年01期
5 刘卫果,胡思继;旅客交通方式选择行为的模糊机会约束规划模型[J];北方交通大学学报;2002年02期
6 吕擰,贾燕兵;应用遗传算法进行给水管网优化设计[J];北京工业大学学报;2001年01期
7 毕春长,张有忱;基于实码遗传算法的汽车变速箱可靠性优化设计[J];北京化工大学学报(自然科学版);2004年05期
8 芦永明;徐安军;贺东风;田乃媛;;一种有利于提高DHCR比例的热轧批量计划编制方法[J];北京科技大学学报;2011年10期
9 杨业建;姜泽毅;张欣欣;;板坯热轧批量计划数学模型及求解算法[J];北京科技大学学报;2012年04期
10 左秀峰,韩伯棠,何世伟;供应链库存控制策略的进化仿真[J];北京理工大学学报;2004年08期
中国重要会议论文全文数据库 前10条
1 杨吉会;;模糊关系规划概述[A];中国运筹学会第九届学术交流会论文集[C];2008年
2 麻倩倩;马新顺;石彤菊;;求解机会约束规划的回溯算法[A];第四届中国不确定系统年会论文集[C];2006年
3 李平;戴政国;;灰色线性规划问题的随机模拟解法[A];第一届中国智能计算大会论文集[C];2007年
4 刘金亮;;求解模糊需求条件下车辆路径问题的混合蚂蚁算法[A];第三届中国智能计算大会论文集[C];2009年
5 戎丽霞;;模糊需求条件下的多车场车辆路径问题[A];第三届中国智能计算大会论文集[C];2009年
6 蔡洪文;张殿业;;随机需求条件下的生产—定位—路径集成问题研究[A];第七届中国不确定系统年会论文集[C];2009年
7 熊翠;吴慧萍;李波;;多旅行商问题遗传算法求解及其改进[A];第四届中国智能计算大会论文集[C];2010年
8 张雷;杨大地;刘冬兵;刘凌晨;;DNA遗传算法在M-TSP问题中的应用[A];'2006系统仿真技术及其应用学术交流会论文集[C];2006年
9 宣吉;廖祖维;荣冈;阳永荣;;基于随机规划的炼厂氢网络改造设计[A];2009中国过程系统工程年会暨中国mes年会论文集[C];2009年
10 包莉丽;胡正华;;基于机会约束规划的制造／再制造混合系统生产决策[A];第八届中国管理科学学术年会论文集[C];2006年
中国博士学位论文全文数据库 前10条
1 彭北青;第三方物流配送车辆路径问题模型及算法研究[D];华中科技大学;2009年
2 孔令启;基于内外圈协同优化策略的间歇化工过程不确定性调度研究[D];华南理工大学;2010年
3 李艳红;综合运输通道客运结构优化理论与方法研究[D];北京交通大学;2010年
4 王宏亮;钢铁企业多粒度分型生产计划管理方法研究[D];大连理工大学;2011年
5 王书齐;可变模糊集多属性决策理论在大型编队防空决策中的应用研究[D];大连理工大学;2011年
6 陈德良;物流网络可靠性的关键问题与应用研究[D];中南大学;2010年
7 李峰;桩锚土钉复合支护基坑施工时变力学研究[D];郑州大学;2010年
8 李彦来;物流网络结构复杂性及优化设计问题研究[D];北京交通大学;2011年
9 左大杰;铁路快速客运网络旅客列车开行方案优化研究[D];西南交通大学;2010年
10 孙力勇;电力市场环境下发电公司的短期经济运行研究[D];上海交通大学;2007年
中国硕士学位论文全文数据库 前10条
1 石丽丽;智能优化算法对比研究及其在船体双底结构优化中的应用[D];哈尔滨工程大学;2010年
2 赵海坤;模糊线性规划理论的模糊结构元解法研究[D];辽宁工程技术大学;2009年
3 周聪;高维多目标减少算法的比较与研究[D];湘潭大学;2010年
4 陈小燕;高校人力资源模糊管理研究[D];福建师范大学;2010年
5 刘娟容;实时PCR仪荧光信号监测系统的研究[D];浙江大学;2011年
6 高伟;基于全年负荷的冷热电联供系统优化分析[D];东华大学;2010年
7 张宇;农产品销售物流中风险控制模型及求解方法研究[D];沈阳工业大学;2011年
8 李国华;不确定条件下电厂燃料供应优化研究[D];华北电力大学（北京）;2011年
9 孙翠英;基于可信性理论含规模化风电的机组组合问题研究[D];华北电力大学（北京）;2011年
10 何晓璇;基于收益管理理论的两级装配系统最优控制策略研究[D];吉林大学;2011年
【二级参考文献】
中国期刊全文数据库 前10条
1 张春霞;王蕊;;基于遗传算法求解TSP问题的算法设计[J];安阳工学院学报;2007年04期
2 穆艳玲;李学武;高润泉;;遗传算法解TSP问题的并行实现[J];北京联合大学学报(自然科学版);2006年02期
3 杨华芬;魏延;;一种求解TSP问题的改进遗传算法[J];重庆工学院学报(自然科学版);2007年05期
4 封全喜,刘诚;物流配送车辆路径问题的并行遗传算法研究[J];铁道科学与工程学报;2005年04期
5 唐立新;热轧调度并行处理策略的多旅行商模型[J];东北大学学报;1999年02期
6 高雷阜;刘旭旺;;基于模拟退火的Hopfield网全局优化方法[J];辽宁工程技术大学学报(自然科学版);2009年01期
7 卢厚清,王辉东,黄杰,李波;任务均分的多旅行商问题[J];系统工程;2005年02期
8 陈冬华;;旅行商问题推广及其混合智能算法[J];华东交通大学学报;2011年02期
9 万颖瑜,周智,陈国良,顾钧;SizeScale:求解旅行商问题(TSP)的新算法[J];计算机研究与发展;2002年10期
10 叶玉玲;伞冶;;一种混合优化算法及其性能[J];吉林大学学报(工学版);2009年01期
【相似文献】
中国期刊全文数据库 前6条
1 胡大伟;刘贵英;;基于空间填充曲线和or-opt搜索求解旅行商问题[J];长安大学学报(自然科学版);2007年02期
2 柳祖鹏;李克平;朱晓宏;;基于蚁群算法的公共自行车站间调度优化[J];交通信息与安全;2012年04期
3 黄X;;向蜜蜂学习或许可解决堵车问题[J];中国蜂业;2011年Z5期
4 张瑞友;汪定伟;尹原永;;集装箱卡车运输问题的基于图的建模方法[J];系统工程理论与实践;2011年08期
5 王金妹;张勤;朱东红;;基于图论的物流配送线路问题研究[J];交通标准化;2011年Z1期
6 ;[J];;年期
，本文编号：708693
本文链接：https://www.wllwen.com/kejilunwen/daoluqiaoliang/708693.html
