基于遗传算法的内河船舶路径优化问题研究

基于遗传算法的内河船舶路径优化问题研究沈航（武汉理工大学交通学院，湖北武汉430063）摘要：内河船舶的路径优化问题是内河运输研究的一个重点和难点，其路径选择是否科学合理直接影响着内河运输的运行效率。本文将遗传算法应用到内河船舶的路径优化研究中，建立了以运送成本最低为目标的无时间窗约束的内河船舶路径优化模型，并对模型的遗传算法进行了设计。通过实例的计算验证了该模型在内河船舶路径优化中的有效性。关键词：内河船舶；路径优化；遗传算法0引言随着综合运输的迅速发展，人们开始将注意力转移到构建合理的水运物流网络，水路运输在综合运输网络的构建中也发挥着重要的作用[12]。目前水运物流服务对水运资源缺乏有效的利用和整合，造成了资源的浪费，本文主要研究内河船舶路径优化，以便更好地进行水运物流组织，充分的利用航道等资源，降低水运物流成本。目前关于内河船舶的路径优化问题的研究较少，而在车辆的优化调度方面的研究颇多，本文将广泛应用于生产调度的遗传算法[35]加以改进应用于内河船舶路径优化的问题之中，与车辆路径优化问题不同，船舶路径优化问题在考虑的船舶的自身载重量的限制的基础之上，还应该区域航道的通过能力的限制。内河船舶的路径优化问题和车辆路径优化问题类似，同属于NP-hard问题，而遗传算法（GeneticAlgorithm，GA）在解决此类问题上显示出了良好的特性，对于复杂的工业过程的建模、控制和优化领域的研究有重要的意义[6]。本文在考虑了航道通行能力限制的基础之上，以某水路货运站在开展门到门的运输服务为例，将遗传算法应用于的内河船舶路径优化。1内河船舶路径优化问题的描述从水路货运站将一定的货物用m艘载重限制分别为mq船舶运送给n个需求点，每个需求点的位置和需求量ig(1,2,...,)in已知，水路货运站和各个需求点各自之间的距离ijC(,0,1,2,...,)ijn已知，并且他们俩俩相互之间的航道通行能力Tij已知，且imgq，通过合理的进行船舶的安排使得运送路径最短（即目标函数运价最低）。优化网络如图1所示。图1.水上货运站货物配送路径图2内河船舶路径优化问题的数学模型2.1模型假设在无时间窗的船舶路径优化的过程中，最终目标就是使得运送成本最低。在解决无时间窗约束内河船舶的路径优化问题之前，我们首先做出如下的模型假设：假设1：水路货运站和各个需求点的位置及需求量是确定的。假设2：运输成本是已知的，与运输距离有关，不考虑管理费用。假设3：每个需求点仅有一艘船舶经过。假设4：每艘船舶都有相关的载重限制。假设5:船舶在送货的过程中要受到实际区段航道的通过能力限制的约束。2.2模型建立由于每艘船舶最终都会回到水路货运站，所以将货运站记为0号货主，但它对货物的需求量为0，其他的需求点顺序编号为1，2,...,n。并且只有当回程的空船经过水路货运站时，货运站才被认为被服务一次，当满载船舶从货运站出发时，水路货运站不被认为被该船舶服务。设ijsx为船舶调度的01决策变量，当第s(1,2,...,)sm艘船舶由第i(0,1,2,...,)in号货主开往第j(0,1,2,...,)jn号货主时取值为1，否则为0。isy为01决策变量，当第s(1,2,...,)sm艘船舶经过了第i(0,1,2,...,)in号顾客时，取值为1，否则为0。ig表示第i个货主对与货物的需求量，且00g表示货运站对货物的需求为0吨，ijT表示第i号货主与第j号货主之间航道的通行能力的最大限制，sw表示第s艘船舶的自重，ST表示第s艘船舶一共服务了的货主数，spZ表示第s艘船舶第p(1,...,)SpT个服务的货主的编号，这里，水路货运站仅在被回程的空船访问时才被记为被服务1次，并且每水上货运站需求需求需求需求需求需求需求需求艘船舶最终都会回到货运站，所以每艘船舶最后访问的货主必为水上货运站。具体模型如下：001minnnmijijsijsVCx（1）0,niissigyqs（2）11,(1,2,...,)missyiin（3）1missym0i（4）0nijsjsixy1,2,...,;jns（5）0nijsisjxy1,2,...,;ins（6）0ssTZs（7）0spZ0ps（8）1mssTmns（9）(1)sspslslTZsZZplgwT{1,2,...,}slTs(10)目标函数（1）的目的是使得总行程最短，约束（2）表明每艘船舶所承运的货物不超过船舶最大的载重限制，约束（3）表明实际的n个货主被且仅被一艘船舶访问一次，约束（4）表示由于船舶最终都会回到水路货运站，当将货运站当作第0号货主，且在空船返回是才记为是一次服务的前提下，货运站会被访问s次，约束（5）、（6）表明对于n个实际的需求点有且仅会有一艘船舶到达并离开它。约束（7）表示由于第s船服务的最后一个对象是水路货运站，即船舶返回出发地，所以他服务的客户号ssTZ是0，约束（8）表示的含义是任意第s艘船舶在服务了它的第一个顾客1sZ之前，船舶的位置是水路货运站，约束（8）主要的作用是为约束（10）服务，因为约束（10）中会涉及到00sZ，表示的含义是船舶从水运货运站出发的。本模型中假设船舶仅在空船返回水路货运站时，货运站才被认为是被服务了一次，所以当第s()s艘船舶满载船舶从货运站出发时，货运站不被认为被第s艘船舶服务过。约束（9）表明每艘船舶回货运站的那m次服务，以及对于n个实际顾客的服务，m艘船舶一进行了mn次服务，约束（10）表示当第s艘船舶到达他服务的第l个客户之前的这段水路运输过程中船舶的自重加上它所载运的货物的总重量必须小于该区段的航道的最大通过能力限制，否则船舶无法正常运输。3遗传算法的设计3.1基于遗传算法的内河船舶路径优化方法本文根据所建立的模型设计了相关的遗传算法，其流程图如下图2，采用了交叉算子-最大保留交叉的方法和随机选取两基因交换的变异方法。图2算法流程图3.2染色结构编码采用自然数编码内河船舶的路径优化的可行路线可以编码成一个长度为1sn的染色体，每艘船舶用0隔开，每两个0之间表示的是一个基因，每个基因对应一艘船舶依次服务的实际货主，染色体的形式表示为12111212122212(0,,,...,(0),,,...,(0),...,,,...,(0))sTTsssTZZZZZZZZZ。如染色体012054306780表示的是一共3艘船进行货运服务，第1艘船舶先后服务了1，2号或主并回到货运站，第2艘船舶先后服务了5，4，3号货主再回到了货运站，第3艘船舶先后服务了6，7，8号货主，然后返回货运站。3.3初始种群的产生通过matlab编程，将目标函数的约束（2）和（10）这两个船舶和航道的通行能力的约束转化成罚函数[7]添加到目标中去，目标函数相应地变化为满足终止条件初始化编码算法结束轮盘赌选择子代计算染色体适应度变异交叉NY(1)0011011minmax(,0)max()ssspslslTTnnmmnmijijsiissZsZZijssislplVCxMgyqMgwT其中M为一个很大的正数，编写相关遗传算法的程序产生N个初始可行解，即使得这些解都满足即船舶的载重限制，又满足航道通过能力的限制，将它们作为初始种群。3.4适应度计算和选择操作一般而言，适应度函数值要求是非负的，首先分别计算的N条染色体对应的函数值kV(1,2,...,)kN，然后对这些值取倒数变换得到的kf为每一条染色体的适应度，即1kkfV。这里采用了最佳保留的轮盘赌的复制方法进行染色体复制，第k条染色体被选中的概率1kkNkifpf。3.5交叉和变异操作在船舶路径优化问题中，交叉操作之后难以保留双亲优良组的特性，甚至得到大量的不可行解。例如染色体012504970中的04970已经是最优路径的一部分而01250还没有形成最优路径，对染色体进行交叉，就会出现04970这个最优路径被破坏的结果。失去了这一优良基因，所以这里采用交叉算子—保留交叉[8]。操作过程如下：（1）如果交叉点处的两个基因都为0，直接进行循序交叉。（2）否则，将交叉点左移（右移），直到左右两个交叉点出的基因都为0.再进行顺序交叉，实例如下：双亲1：0120|345|06780双亲2：01370|26|50480||内为匹配段双亲的交叉点处的基因不全为0，首先移动交叉点使双亲1、2分别变化为012|03450|6780和0137|02650|480再进行顺序交叉，得到的后代为：后代1：013402650780后代2：017034502680选取适当的交叉率cp进行交叉操作，选取适当的变异率mp对交叉所得的结果进行交叉操作，完成交叉和变异过程。3.6算法的终止当算法达到了预先设定的条件是算法可以终止，否则将会跳回到3.4过程，重复循环，直至满足算法的终止条件为止，这里采用的终止条件是或算法收敛或达到了设定的迭代次数record，才终止。4实例计算以某内河水网中的货运为例，某次具体的货运中，水路货运站与10个货主的相关信息记录在如下的几张表格里面，用0表示水路货运站，货运站指定3艘船舶进行运送服务，现要求保证每个货主的送货量，满足船舶载重限制和船舶航行中航道通过能力的限制的前提下试求路程最短的安排方案。表1水路货运站与各个需求点之间的距离（km）Dij012345678910005.2528.57.5637.51811.2537.525.517.2515.25027.754.54.540.519.513.53625.527.75228.527.75028.52721.752416.518.7524.7510.537.54.528.502.2542.7525.516.534.53334.5464.5272.25039.752416.953331.527.75537.540.521.7542.7539.75022.525.518153.7561819.52425.52422.5021.75217.59.75711.2513.516.516.516.9525.521.75025.51512.75837.53618.7534.533182125.5023.2513.5925.525.524.753331.5157.51523.25061017.2527.7510.534.527.753.759.7512.7513.560表2水路货运站与各个节点之间的航线的通过能力限制（吨）Tij0123456789100500070010801100113074089082011009101150170050007707601130980970770112010108702108077050008107607908109007201150117031100760810500088075010908908209007404113011307608805000810870111070072078057409807907508105000107079010407908806890970810109087010705000920850950950782077090089011107909205000113097010108110011207208207001040850113050008109109910101011509007207909509708105000990101150870117074078088095010109109905000表3船舶的编号及信息船舶号码123船舶自重（吨）250300400船舶载重限制（吨）600700800表4各个货主的货物的需求量客户号码12345678910需求量（吨）18095290701606521011585220设定交叉率cp=0.9，变异率mp=0.1，迭代次数record=2000，种群的大小为N=100，罚函数系数M=600，使