资源描述：
《遗传算法求解多式联运最小费用问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、遗传算法求解多式联运最小费用问题//・paper・edu-1-遗传算法求解多式联运最小费用问题王欣欣北京邮电大学自动化学院北京（1〈#004699'〉0〈#004699'>0876）摘要：多式联运是现代物流网络运作的主体和纽带。在多品种、小批量的市场环境下，多式联运的物流系统规划工作变得更加重要也更加复杂。本文以运筹学为基础，研究多式联运最小费用问题，将该问题划分为两个步骤求解。第一步根据运输路段信息枚举可行的路线；第二步运用遗传算法，将第一步生成的路线作为基因，所有订单的路线构成染色体，考虑运输的重量、数量、体积等能力限制约束，建立数学模型。提出一个基
2、于对应位杂交、自适应相关变异的混合遗传算法，改善求解速度。最后对一个小规模算例（7点*15订单*12路段）进行求解，并对得到的结果进行了验证。关键词：物流，多式联运，遗传算法1引言多式联运是现代物流网络运作的主体和纽带，是贯穿整个现代物流活动的主线［1］。在越来越个性化的市场环境下，多式联运系统规划工作变得更加重要也更加复杂。建立准确、合理的多式联运模型，可提高企业的运送速度和服务质量，实现高效、低耗的物流运输口标，从而获得巨大的经济效益。针对多式联运的模型和算法，很多学者从不同的角度分别对最短路、最短时间以及基于时间因素的最短路问题进行了研究［2^6］
3、oAngelicaLozano等在每条有向边对应一种运输方式的情况下，研究了多式联运的最短路问题［2］o张运河等将多式联运广义最短路问题纳入到多重图最佳路线的求解上，通过在图中增加虚拟的发、到站，使得该问题完全转化为一个最短路问题，应用静态最短路算法对其求解［3］。魏众、中金升等提出了一个适用于多节点、长距离的多式联运运输网络问题，并运用系统的理论和方法，建立多式联运下的路径最短时间模型，并求得与之对应的路径的运输费用［4］。魏航等针对时变条件下多式联运的最短路问题，考虑了各个节点的不同运输方式之间有出发时间限制的约束条件［5,6］。这些研究对提高企业物
4、流运输效率有一定的意义。然而决定企业运输成本的因素有很多，不是简单的最短路径或者最短时间。在运达时间允许的情况下，换另外一种运输方式多走一些路程也可能节约运输成本。遗传算法［7］是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。它的思想源于生物遗传学和适者生存的自然规律，是具有“生存+检测”的迭代过程的搜索算法。遗传算法具有大范围全局搜索的能力和刻扩展性，对优化对象既不要求连续，乂不要求可微，并具有极强的鲁棒性和内在的并行计算机制，特别适合于非凸空间中复杂的多级值优化和组合优化问题。作为一种新的全局优化搜索算法，遗传算法在各个领域得到了广泛应用，
5、取得了良好效果，并逐渐成为重要的智能算法Z-o因此，本文采用遗传算法对多式联运最小费用问题进行了研究。2建立多式联运问题模型2.1问题提出与假设某第四方物流企业与多个承运商合作，将业务发展到了多个城市。为满足客户对运输的要求并降低运输成本，获得最大的利润，该公司需要结合订单和各承运商能够提供的运输路//・paper・edu-2-段，规划确定各订单的运送路线。运用遗传算法求解该问题，需要进行如下的假设：需求假设1：每个订单都有固定的重量、体积和数量，而且订单不能被拆分。需求假设2：不存在单张订单超过路段运送能力的现象。假设数据中已将运货量过大的订单拆分为若
6、干个运货量适中的小型订单。成本假设1：运输成本就等于配送的单位成本同所配送的重量的乘积，不考虑数量和体积的因素。成本假设2：数据中采用平均的运输成本，不考虑因由淡季、旺季的影响而造成的运输报价不同的因素。成本假设3：货物屮途的转运成本和因转运产生的存储成本为零。2.2定义符号和变量{}12,，…，…kdSssss二d个城市的集合。{}12,,•••,...imOoooo二集合。其中订单i的起始城市(1,2,...)kd二为公司业务覆盖的(1,2,...)im二为m个运货订单的和到达城市分别为lisiteSe,2isiteSe。{}12,,・..，・・・j
7、nRrrrr=,(1,2,..・)jn二为各承运商可提供的n条路段的集合。其中路段j的起点终点分别为ljsitcSW,2jsiteSE。jcarricr为承运商名称，cosjtUnit为单位重量的运输费用。路段j上每班次的运输能力为jquantity,jvolume和jweighto定义m*n的二维矩阵变量:()■JiJX99=9999••••••当订单i经过路段j(当订单i不经过路段)〈#004699'>0,。已知赋权有向图D二(S,R),对每个弧Rj=(1jsite,2jsite),有相应的权cosjtUnito定义变量Path为得到的路线集合，其中
8、共有h个元素，其序号用p表示,(p=l,2,・・・h)。则pjlj2jxPath
