单回路运输问题的表上作业求解

《单回路运输问题的表上作业求解》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第49卷第5期厦门大学学报(自然科学版)Vol.49No.52010年9月JournalofXiamenUniversity(NaturalScience)Sep.2010单回路运输问题的表上作业求解***刘旺盛,黄敏霁,李茂青(厦门大学信息科学与技术学院,福建厦门361005)摘要:基于单回路运输问题的数学模型的特征与多点间运输问题有相似之处,提出了单回路运输问题的表上作业求解法;并探讨了该方法的求解适用原则,除了适用大部分多点间运输问题可行解的确定原则法外,还可以和其启发式算法)))最近邻点法结

2、合使用.但运用闭回路法优化时易产生子回路,优化方法有待继续探索.关键词:单回路运输问题;旅行商问题;多点间运输问题;表上作业法;闭回路法中图分类号:O221.4文献标识码:A文章编号:043820479(2010)0520608204处不一一列举.由于该问题的可行解是所有顶点的全1单回路运输问题及其模型排列,随着顶点数的增加,计算量会产生组合爆炸,属于/NP(Non2deterministricpoly2nomial)完全问题0,单回路运输问题主要见于单一车辆的路径安排,是NP问题中最难的一类.它一

3、开始是为解决交通运指在运输线路优化中,设存在节点集合A,选择一条闭输问题而提出的,后来逐步应用到飞机航线的安排、快合路径遍历所有的节点,使该车辆遍历所有用户的同递服务、电路板线路设计及物流配送等领域.旅行商问时,达到所行驶的距离最短.这类问题的两个显著特点题(Travelingsalesmanproblem,TSP)就是最为典型是单一性(只有一个回路)和遍历性(不可遗漏性).的一个单回路运输问题,国内外学者对其进行了大量该问题的数学描述为:设有n个节点A1,A2,,,的研究.目前存在的算法主要有割平

4、面法、动态规划算[1]An.已知从节点Ai到节点Aj的距离为dij,其n阶矩法及分支定界法等精确算法,但由于精确算法所能阵为D=(dij).若从某节点出发,遍历其它n-1个节求解的问题规模非常有限,实际中使用的往往是多项点各一次,最后返回出发点,求使总运输费用最少(或式阶数的近似算法或启发式算法.通常有下列一些近总距离最短)的路径.假设似解法:经典的插入算法(按插入规则的不同分为若干1,若从节点Ai到节点Aj类)、最近邻点法和树算法等;需要借助计算机实现的xij=0,若不从节点Ai到节点Aj禁忌搜索

5、法、模拟退火算法、遗传算法及其他智能算法则其数学模型为:[1211]和各种智能算法的混合算法等.nnnnminz=EEdijxij实际上,从模型中可以看出Exij=Exij=n,i=1j=1i=1j=1n这与产销平衡的多点间运输问题的约束特征相同,因Exij=1,j=1,2,,,ni=1此可以尝试用表上作业法求解.ns.t.Exij=1,i=1,2,,,nj=12表上作业法求解xij=0或1,i,j=1,2,,,n该问题在图论的意义上就是所谓的最小Hamil2由于寻找的回路是包含所有城市节点的一个循

6、[1]ton圈问题,模型还有其它一些等价的书写形式,此环,故可以把任意一个城市节点作为起点,也是终点.表上作业法在求解多点间运输问题时可以运用闭回路收稿日期:2009209210优化得到最优解,是一种精确算法.但在求解单回路运基金项目:国家/211工程0(三期)项目;福建省自然科学基金项目输问题时运用闭回路法优化易出现子回路,因此本文(2010J01359)提出的表上作业法是一种近似算法.求解步骤如下:*现工作单位:集美大学现代物流研究中心1)将单回路运输问题转化为产销平衡的多点间**通讯作者:mq

7、li@xmu.edu.cn运输问题,建立求解表格:视需遍历的城市A1,A2,,,第5期刘旺盛等:单回路运输问题的表上作业求解#609#An既为产地(起始地)又为销地(目的地),各城市节点表2求解表格的产量(供应量)和销量(需求量)均为1,当i=j时令Tab.2Solvingformcij=M(任意大正数),其余各格cij=dij,将cij值标注目的地在表格的右上角;起始点供应量A1A2A3A4A5A62)确定解:同样可以采用求解多点间运输问题的A1M10687151最小元素法,但不同的是每在Ai到A

8、j处填上数字1,A210M52015161除了要将第i行和第j列划掉,同时需要将易造成子A365M14781回路的对应格划掉,以避免出现子回路.若记第k步求A482014M4121解得到的链路为Lp=AkyAiyAj,则该对应格为Aj到Ak.但当k=n-1,此时所有顶点都加入链路中,对A571574M61应格不需划掉,而应在对应格中直接填上数字1,至此A615168126M1求解结束.需求量1111113算例有6个城市A1,A2,,,A6,它们之间的距离如表[11]1