基于遗传算法的组合运输问题研究崔雪源，马英钧，赵东方**（华中师范大学数学与统计学学院,武汉430079）5101520253035摘要：随着运输工具和路段数的增加，利用传统的规划模型求解组合运输问题就会变得十分困难。本文在建立其数学模型的基础上，提出解决这类问题的遗传算法，为了提高算法的效率，在传统交叉变异的基础上提出一种新的进化突变算子。最后，通过MATLAB随机生成运输费用和中转费用矩阵并编程求解，结果表明，该算法的收敛速度较快，十分适合组合运输问题的求解。关键词：运筹学；运输优化；遗传算法；均匀交叉；进化突变中图分类号：O224AStudyofCombinedtransportationproblembasedongeneticalgorithmCUIXueyuan,MAYingjun,ZHAODongfang(SchoolofMathematicsandStatistics,HuazhongNormalUniversity,Wuhan430079,China)Abstract:Asthenumberofconveyanceandroadincrease,itbecomesverydifficulttosolvecombinedtransportationproblemusingthetraditionalplanningmodel.Onthebasisofsettingupmathematicalmodel,thispaperputsforwardgeneticalgorithm.Inordertoimprovetheefficiencyofthealgorithm,anewevolutionarymutationoperatorisproposedonthebasisofthetraditionalcrossoverandmutationoperator.Finally,thispaperrandomlygeneratetransportationandtransitcostsmatrixandprogrammethroughMATLAB.Theresultsshowthattheconvergencespeedofthealgorithmisfastanditisverysuitableforsolvingcombinedtransportationproblem.Keywords:Operationsresearch;Transportationoptimization;geneticalgorithm;uniformcross;evolutionarymutation0引言组合不同方式的运输优化决策问题[1]就是从物流系统的总目标出发,运用系统学的理论和系统工程的方法对货物运输中的运输工具、运输费用、中转费用等进行综合分析,制定出可能的货物运输方案,并从中选择最优,以达到降低运输成本的目的。选择运输方案时，要在城市间现有基础上选择合适的运输工具，使得运输费用和中转费用的总和达到最省。遗传算法[2]的出现为求解组合不同方式的运输问题提供了新的工具,它是一种借鉴生物界自然选择和进化机制发展起来的高度并行、随机、自适应搜索方法。由于其具有并行性、健壮性,特别适合于解决复杂的非线性问题。本文针对组合运输问题的特点,建立了求解这类问题的遗传算法模型,并通过实验分析,得到了较好的结果。1数学描述有若干吨货物需要沿着一条路径运输到M个城市，相邻城市间的连接称为路径的一段，在第i个路段上有Ni中运输方式，其中i1,2,,M1.相邻路段间可以更改运输方式，但作者简介：崔雪源（1990.05），女，研究生，运筹学与控制论通信联系人：赵东方，男，教授，运筹学与控制论.710030245@qq.com-1-Ccostchangemnluseml404550是在同一路段上只能选择一种运输方式，选择合适的运输方案使得运输费用和中转费用的总和达到最小。令WAY表示可选的运输工具的集合，则WAY{WAY1,WAY2,,WAYM1}，其中WAYi表示在第i个路段上的运输方式集，其中|WAYi|Ni；令ROUTE表示完整的运输路径，Tcostml表示在路径l上使用运输工具m的费用其中l1,2,,M1;mWAYl;Ccostmn表示将运输工具m转换到运输工具n的费用。下面定义两组{0,1}变量，第一组变量useml，其中m表示运输工具，l表示路径，其意义如下：1在路径l上使用m0在路径l上不使用m第二组变量changemnl，其中m,n表示运输工具，l表示路径，其意义如下：1在第l段到第l1段将运输工具从m换为n0在第l段到第l1段不将运输工具从m换为n由此，可得到数学模型如下：minfTcostmlusemlmWAYllROUTEM1mWAYlnWAYl1l1mnchangemnl（1）s.tusemlmWAYl1,l1,2,,M（2）changemnlmWAYl,nWAYl11,l1,2,,M（3）usemlusen,l12changemnl,mWAYl;nWAYl1;l1,2,,M1（4）55useml{0,1},mWAYl;l1,2,,Mchangemnl{0,1},mWAYl;nWAYl1;l1,2,,M1（5）（6）上述...