没有合适的资源?快使用搜索试试~ 我知道了~
EURO Journal on Computational Optimization 9(2021)100018Ailsa H.研究旅行商问题吉尔伯特·拉波特加拿大蒙特利尔HEC公司英国巴斯大学管理学院ABsTRA cT艾尔莎湖兰德获得了2021年欧洲金奖,他对旅行推销员问题的研究做出了一些重要贡献,这些贡献发表在1955年的一篇期刊文章和1979年的一篇工作论文中本介绍性说明的目的是介绍这些贡献。1. 介绍艾尔莎湖兰德女士因其在运筹学领域的杰出成就而获得2021年欧洲金奖。颁奖典礼于2021年7月在欧洲会议上举行在她去世后不到两个月,在这个场合 我被邀请做一个视频演示,在视频中我讲述了我在她的博士学位期间。她是伦敦经济学院(LSE)的一名学生,然后我提到了她关于旅行推销员问题(TSP)的工作论文(兰德,1979)。这引起了Immanuel Bomze教授的注意,他联系我在这份期刊上发表这篇文章,并邀请我介绍它,在准备这篇文章时,我意识到另一篇相对不为人知的论文(Morton和Land,1955),它对TSP的研究做出了一些早期的贡献。在介绍这两篇论文之前,我将提供一些背景信息。2. 背景信息:1972-1975年在LSE1972年夏天,当我还是兰卡斯特大学的一名硕士生时,我申请攻读博士学位。该计划在LSE,约四个月后,官方的最后期限。不久之后,我收到了一封署名为“A”的信。兰德”邀请我去伦敦面试。刚到LSE,我惊喜地发现A。土地是一个女人。 我不知道很多关于数学规划在那个时候,我当然不知道存在的土地和多伊格(1960年)文件。经过一番讨论,我们就我将做的论文类型达成了一致。然后我被录取为她的博士。学生,在她的指导下写了一篇论文,并于1975年进行了答辩。我将永远感谢Ailsa Land作为我的论文指导,以及她对我学术生涯的影响在我读博士的时候。一直以来,艾尔萨都有大约五个博士学位。凹痕,我们大多数人都从事数学编程主题。的博士该计划没有课程或考试要求,所以所有的学习都是自学和非正式的。 经常有一对一的会议原文DOI:10.1016/j.ejco.2021.100017https://doi.org/10.1016/j.ejco.2021.100018和我们的导师交流,他是一个知识丰富的人她向我们传递了几个从未在公开文献中发表过的研究思想,但却进入了我们的论文。我记得在我读博士的时候有一次这样的会面,当她建议将Gomory切割(Gomory,1963)和其他类型的切割与分支定界相结合,以解决整数线性规划。这实际上是分支和切割的本质,但这个术语是很晚才创造的。PanagiotisMiliotis也是Land的学生,他很快就尝试了这个想法,事实上他是第一个开发出一种结合Gomory cuts和subtour elimination约束的全自动算法的研究人员(Dantzig et al.,1954)的TSP(Miliotis,1975,1978)。作为她的学生,我们有机会接触到当时被称为兰德-鲍威尔密码的东西,在我们得到它之后,1973年发表了详尽而仔细的描述(兰德和鲍威尔,1973)。这种代码提供了一种非常聪明的机制,以减少单纯形计算和节省计算机内存。它的基础上,其大小动态变化的解决方案的过程中,只包含有效的约束和活动(原始的,但不是松弛)变量的系数。它被认为是一种算法开发工具,而不是作为一个black-boX求解器,它是完全文档化的,以方便定制和实验。它作为一个基础,所有数学规划论文完成下艾尔莎但在开始之前,我将评论莫顿和兰德(1955)的论文。3. Morton and Land(1955)在20世纪50年代初,乔治·莫顿是博士。Ailsa H.土地他们一起发表了一篇题为“对'旅行推销员'问题的贡献”(莫顿和土地,1955年),出现在皇家统计学会杂志。在我看来,这篇论文实际上包含了对TSP的两个重要贡献。接收日期:2021年7月30日;接收日期:2021年9月29日;接受日期:2021年10月18日2192-4406/Crown版权所有© 2021由Elsevier Ltd代表欧洲运筹学学会协会(EURO)发布。这是一篇基于CC BY-NC-ND许可证的开放获取文章(http://creativecommons.org/licenses/by-nc-nd/4.0/)可在ScienceDirect上获得目录列表欧洲计算优化期刊主页:www.elsevier.com/locate/ejcoG.拉波特EURO Journal on Computational Optimization 9(2021)1000182本文的第一个贡献是介绍了一些3-opt移动。作者写道(第190页):“In dealing with a complete circuit it can be shown that any proposedalteration will involve substituting at least three new links formingpart of the circuit, where reversal of direction is also considered sucha 如果要参观的地方用数字1,2,…,除了单位置换和循环置换(实际上不改变电路)之外,置换必须至少涉及将整数之一(例如j)从其自然顺序中的位置移到其他位置(例如在k和k之间)。k+1),其还包括简单的转置。 这意味着重新-将链路j其他排列是可能的,不能用“三进三出”的变化来表达。然而,可以通过一系列这样的变化来获得任何排列,因为任何排列都可以被写为转置然后,作者描述了一种计算所有三进三出交换机的成本变化的方法,这些交换机不会破坏电路。因此,这种方法显然是3-opt启发式的先驱,3-opt启发式由Lin(1965)推广和形式化,并由Lin和Kernighan(1973)扩展。在他们对Lin和Kernighan算法的描述中,Applegate et al. ( 2006年)写道(第104页):“The Lin-Kernighan algorithm is a 基 本 步 骤 可 以 追 溯 到 Flood(1956),他观察到,通常可以通过在可能的情况下用更便宜的替代对重复替换旅游边对来获得好的旅游。[...]这种洪水的交换被称为2- opt移动,并由其他早期研究人员进行了研究,包括Morton和Land(1955),Bock(1958),Croes(1958)和Lin(1965)。事实上,Morton和Land引入的不是2-opt,而是一个顶点重定位启发式算法,它是3-opt的一个子情况莫顿和兰德(Morton and Land,1955)的第二个重要贡献在于,他提出了一种替代的方法来消除subtours,这种方法与丹齐格等人(Dantzig et al.,1954)的方法不同。在第188页,作者建议沿着路线积累时间变量将防止subtour。他们给出了一个销售员的路线作为例子(在多销售员的情况下),从一个仓库开始和结束,访问四个顶点,并沿着路线积累时间(我的修改,以避免引入符号,在括号中显示):“要求是,任何中间点的推销员都不得累积或减少[.],必须有一名推销员离开[仓库],必须有一名推销员到达[仓库]。在这种形式下,没有一个子周期可以在不违反某些边界条件的情况下发生,因为没有无成本和无时间的复合活动。假设有一个子周期[虽然Morton和Land没有提供数学模型,但他们通过沿着推销员的路线积累正数量来消除子路线的想法是Miller等人(1960)和其他几个TSP公式的子路线消除约束的核心,例如Gavish和Graves(1978)和许多其他人(参见Öncan等人,2009年)。4. 03 The Dog(1979)Land(1979)的论文提出了一种求解对称TSP的精确算法。像一些早期的作品基于切割平面方法(Dantzig等人,1954; Martin,1966;Miliotis,1975,1978),它最初放松问题的大多数约束,并在发现它们被违反时动态地生成它们。 下面的观察有助于正确理解这篇论文。 Dantzig等人(1954)使用了现在已经成为对称TSP的经典公式,其中包含了度约束、子环消除约束和完整性约束。他们最初放松了子图消除约束和完整性约束,通常会产生一个不可行的解决方案。Subtour elimination constraints and onecomb inequality ( Subtour elimination constraints and one combinequality)(参见Applegate等人,2006,第86页),并迅速达到收敛。这种方法只适用于一个单一的42个顶点的情况下,但它构成了对称TSP的最佳可用算法的基础。Martin(1966)也放宽了子巡回赛淘汰的限制,但除此之外,他产生了Gomory削减 达到完整性。放松的约束在每次通过后手动添加,并且在三次通过后达到42顶点实例上的收敛。在他的博士学位。03 The Dog(1975) Miliotis(1976)提出了一个分支和切割算法,其中完整性是通过分支和定界达到的,并且只在整数解处施加subtour消除约束;Miliotis(1978)描述了一个纯切割平面算法,其中完整性是通过施加Gomory切割来达到的。作者提出了一种在整数解上加子环消去约束的所谓直算法和一种在非整数解上分离子环消去约束的逆算法。所有的运算都是用整数运算来完成的。Miliotis得出结论,切割平面算法优于分支切割算法,反向算法优于直接算法。由逆切割平面al-出租m解决的最大实例在欧几里得情况下涉及64个顶点,并且当成本随机生成时涉及80个顶点。Miliotis(1978)算法的两个局限性Land(1979)的论文试图减轻这些限制。在Miliotis的工作中,该算法基于Land-Powell代码,所有操作都以整数运算执行。该模型和算法的工作与通常的程度约束和subtour消除约束,并通过实施Gomory割达到完整性。此外,该方法利用2-匹配约束(埃德蒙兹,1965年),这有助于达到完整性。这项工作的一个重要的新颖性相对于以前的算法在于放宽了很大一部分的变量,一个想法提出了- ward在最后一节的Miliotis最初,程序中包含的变量是与边相关的变量一个很好的解决方案,其中3-选择适用,并以四个最小的与每个顶点关联的边偶尔通过变量的完整集合,并且违反最优性条件的变量被激活。该算法在10个欧几里得100顶点实例上进行了测试,其中9个被解决为最优。对于未解决的实例,该算法确定上限为769,下限为768。三个100个顶点的随机费用也很容易解决这篇论文将在接下来发表。它构成了一个巧妙的计算优化,因此是一个完美的适合这本杂志。这里省略了几个巧妙的实现细节,因为它们非常技术性,并且在论文中有充分的描述。本文还证明了潜在的土地鲍威尔代码处理不仅是约束松弛,因为大多数情况下以前,但也变量松弛。同时做到这两点在当时是相当了不起的。请注意,该算法从不诉诸分支,很可能是第一个纯粹的切割和价格实现的例子几代研究人员对TSP的研究导致了许多精确和启发式求解技术的发展,我们现在经常在组合优化中使用。在Dantzig等人的开创性论文中介绍了一些关键概念。(1954年),不-G.拉波特EURO Journal on Computational Optimization 9(2021)1000183特别是使用切割平面。这一系列的研究在20世纪的最后一部分得到了发展,并在协和式飞机的生产中达到了顶峰(Applegate等人, 2006年)。Ailsa Land和她的学生Panagiotis Miliotis都在这一发展中发挥了重要作用申报利益作者声明,他们没有已知的竞争性经济利益或个人关系,可能会影响本文报告的工作。确认我感谢伊曼纽尔·博姆泽教授邀请我写这封信。同时也感谢两位推荐人的宝贵意见。引用Applegate,D.L.,比克斯,R. E.,Chvátal,V.库克,W.J.,2006.旅行推销员的问题。一项计算研究。普林斯顿应用数学系列。普林斯顿大学出版社,普林斯顿.Bock,F.,1958.一种求解“旅行商”及相关网络优化问题的算法。1958年,阿莫尔研究基金会研究报告。克罗伊斯,GA,1958.求解旅行商问题的一种方法。操作员Res. 6,791-812.Dantzig,G.B.,Fulkerson,D.R.,Johnson,S.M.,1954.一个大规模旅行商问题的解。操作员Res. 2,393-410.Edmonds,J.,一九六五年最大匹配和0,1顶点的多面体 J. Res. Natl.局标准,第B69节,125洪水,M.M.,1956年。旅行推销员问题操作员Res. 4,61-75。Gavish,B.,南卡罗来纳州格雷夫斯1978.旅行商问题及相关问题。麻省理工学院运筹学中心工作文件GR-078-78。Gomory,R. E.,1963.线性规划整数解的一种算法。在:格雷夫斯,RL,Wolfe,P.(Eds.),数学规划的最新进展McGraw-Hill,New York,pp. 269-302兰德,A.H.,1979. 100个城市旅行商问题的求解。Working Paper.伦敦经济学院。兰德,A.H.,多伊格,A.,1960.离散规划问题的一种自动求解方法。Econometrica 28,497-520.兰德,A.H.,鲍威尔,S.,1973.数学规划的Fortran代码:线性,二次和离散。威利,纽约。林,S.,1965.旅行商问题的计算机解法。贝尔系统技术公司 J.44,2245林,S.,Kernighan,B.W.,1973.旅行商问题的一种有效启发式算法。操作员Res. 21,498-516.马丁,G.T.,1966.用整数线性规划求解旅行商问题。CEIR,纽约技术报告。Miliotis,P.,1975.结合切割平面和分枝定界方法解决整数规划问题:应用于旅行商问题和1-匹配问题论文伦敦经济学院Miliotis,P.,一九七六年旅行推销员问题的可编程方法数学程序. 10,376Miliotis,P.,1978.用割平面法求解对称旅行商问题。数学课程。15,177-188。米勒,C.E.,塔克,A.W.,Zemlin,R.A.,1960年旅行推销员问题的可编程公式化J.Assoc. Comput.马赫7,326Morton,G.,兰德,A.H.,一九五五年对“旅行推销员问题”的贡献 J. 罗伊国家主义者。Soc. 序列A 17(2),185Oncan,T.,Altinel,I.K.,Laporte,G.,2009.几种不对称旅行商问题公式的比较分析。Comput.操作员Res. 36,637
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功