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

《基于遗传算法的内河船舶路径优化问题研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、基于遗传算法的内河船舶路径优化问题研究沈航（武汉理工大学交通学院，湖北武汉430063）摘要：内河船舶的路径优化问题是内河运输研究的一个重点和难点，其路径选择是否科学合理直接影响着内河运输的运行效率。本文将遗传算法应用到内河船舶的路径优化研究中，建立了以运送成本最低为目标的无时间窗约束的内河船舶路径优化模型，并对模型的遗传算法进行了设计。通过实例的计算验证了该模型在内河船舶路径优化中的有效性。关键词：内河船舶；路径优化；遗传算法0引言随着综合运输的迅速发展，人们开始将注意力转移到构建合理的水运物流网络，水路运输在综合运输网络

2、的构建中也发挥着重要的作用。目前水运物流服务对水运资源缺乏有效的利用和整合，造成了资源的浪费，本文主要研究内河船舶路径优化，以便更好地进行水运物流组织，充分的利用航道等资源，降低水运物流成本。目前关于内河船舶的路径优化问题的研究较少，而在车辆的优化调度方面的研究颇多，本文将广泛应用于生产调度的遗传算法加以改进应用于内河船舶路径优化的问题之中，与车辆路径优化问题不同，船舶路径优化问题在考虑的船舶的自身载重量的限制的基础之上，还应该区域航道的通过能力的限制。内河船舶的路径优化问题和车辆路径优化问题类似，同属于NP-hard问题，

3、而遗传算法（GeneticAlgorithm，GA）在解决此类问题上显示出了良好的特性，对于复杂的工业过程的建模、控制和优化领域的研究有重要的意义。本文在考虑了航道通行能力限制的基础之上，以某水路货运站在开展门到门的运输服务为例，将遗传算法应用于的内河船舶路径优化。1内河船舶路径优化问题的描述从水路货运站将一定的货物用艘载重限制分别为船舶运送给个需求点，每个需求点的位置和需求量已知，水路货运站和各个需求点各自之间的距离已知，并且他们俩俩相互之间的航道通行能力Tij已知，且，通过合理的进行船舶的安排使得运送路径最短（即目标函数

4、运价最低）。优化网络如图1所示。需求水上货运站需求需求需求需求需求需求需求图1.水上货运站货物配送路径图1内河船舶路径优化问题的数学模型2.1模型假设在无时间窗的船舶路径优化的过程中，最终目标就是使得运送成本最低。在解决无时间窗约束内河船舶的路径优化问题之前，我们首先做出如下的模型假设：假设1：水路货运站和各个需求点的位置及需求量是确定的。假设2：运输成本是已知的，与运输距离有关，不考虑管理费用。假设3：每个需求点仅有一艘船舶经过。假设4：每艘船舶都有相关的载重限制。假设5:船舶在送货的过程中要受到实际区段航道的通过能力限制

5、的约束。2.2模型建立由于每艘船舶最终都会回到水路货运站，所以将货运站记为号货主，但它对货物的需求量为0，其他的需求点顺序编号为，。并且只有当回程的空船经过水路货运站时，货运站才被认为被服务一次，当满载船舶从货运站出发时，水路货运站不被认为被该船舶服务。设为船舶调度的决策变量，当第艘船舶由第号货主开往第号货主时取值为，否则为。为决策变量，当第艘船舶经过了第号顾客时，取值为，否则为。表示第个货主对与货物的需求量，且表示货运站对货物的需求为0吨，表示第号货主与第号货主之间航道的通行能力的最大限制，表示第艘船舶的自重，表示第艘船舶

6、一共服务了的货主数，表示第艘船舶第个服务的货主的编号，这里，水路货运站仅在被回程的空船访问时才被记为被服务次，并且每艘船舶最终都会回到货运站，所以每艘船舶最后访问的货主必为水上货运站。具体模型如下：（1）（2）（3）（4）（5）（6）（7）（8）（9）(10)目标函数（1）的目的是使得总行程最短，约束（2）表明每艘船舶所承运的货物不超过船舶最大的载重限制，约束（3）表明实际的个货主被且仅被一艘船舶访问一次，约束（4）表示由于船舶最终都会回到水路货运站，当将货运站当作第号货主，且在空船返回是才记为是一次服务的前提下，货运站会被

7、访问次，约束（5）、（6）表明对于个实际的需求点有且仅会有一艘船舶到达并离开它。约束（7）表示由于第船服务的最后一个对象是水路货运站，即船舶返回出发地，所以他服务的客户号是，约束（8）表示的含义是任意第艘船舶在服务了它的第一个顾客之前，船舶的位置是水路货运站，约束（8）主要的作用是为约束（10）服务，因为约束（10）中会涉及到，表示的含义是船舶从水运货运站出发的。本模型中假设船舶仅在空船返回水路货运站时，货运站才被认为是被服务了一次，所以当第艘船舶满载船舶从货运站出发时，货运站不被认为被第艘船舶服务过。约束（9）表明每艘船舶

8、回货运站的那次服务，以及对于个实际顾客的服务，艘船舶一进行了次服务，约束（10）表示当第艘船舶到达他服务的第个客户之前的这段水路运输过程中船舶的自重加上它所载运的货物的总重量必须小于该区段的航道的最大通过能力限制，否则船舶无法正常运输。1遗传算法的设计3.1基于遗传算法的内河船舶路径优化方