本文主要是介绍遗传算法优化连续泊位调度问题概述，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一、问题描述
随着航运业务量的增长,港口泊位资源的有效配置与利用成为一个重要的问题。传统的泊位调度方法是将泊位分成固定的格子,船只只能停靠在格子位置,但这样会造成泊位利用率低下的问题。针对此问题,我们提出采用遗传算法来进行连续泊位调度,即考虑船只的实际长度和宽度,允许船只停靠在任意泊位位置,而不仅限定于固定格子,从而提高泊位利用率。
二、模型描述
泊位编码
我们将泊位空间划分成一个二维网格,每个网格单元代表一个最小泊位单元。对于每个船只i,用一个二维向量表示其停靠位置,向量元素代表网格单元的编号。
适应度函数
我们定义适应度函数为泊位占用率与船只重叠程度的综合考虑。泊位占用率用停靠船只占据的网格单元数除以总网格单元数得到。船只重叠程度用停靠船只之间相交网格单元数除以重叠船只总网格单元数得到。
遗传操作
采用选择、交叉和变异三种遗传操作。选择采用轮盘赌选择,交叉采用单点交叉,变异采用位置移动变异。
三、算法流程
初始化种群,随机生成一定数量的个体作为初代种群;
计算每一个个体的适应度;
重复执行以下操作直到满足停止条件:
(1) 根据适应度进行选择,选择适应度高的个体;
(2) 按一定概率对选择出的个体进行交叉和变异,形成新一代种群;
(3) 对新一代种群计算个体的适应度;
在所有代中选择适应度最高的个体作为优化结果。
四、结果与分析
代码
采用MATLAB模拟运行算法,设置种群规模为100,最大进化代数为200代。
数据:
| 船舶i | 预计到港时间/h | 装卸量/TEU | 船长（包括安全距离）/m |
| 船舶0 | 0 | 1400 | 250 |
| 船舶1 | 2.5 | 800 | 150 |
| 船舶2 | 6.5 | 1900 | 360 |
| 船舶3 | 8 | 700 | 140 |
| 船舶4 | 9.2 | 2000 | 310 |
| 船舶5 | 13.6 | 600 | 150 |
| 船舶6 | 17.5 | 1300 | 250 |
| 船舶7 | 20 | 1500 | 280 |
| 船舶8 | 22.5 | 800 | 150 |
| 船舶9 | 25.3 | 1100 | 240 |
| 船舶10 | 26.2 | 1800 | 360 |
| 船舶11 | 30 | 1300 | 260 |
| 船舶12 | 32.6 | 900 | 170 |
| 船舶13 | 35.5 | 1400 | 280 |
| 船舶14 | 37.2 | 2100 | 300 |
| 船舶15 | 38 | 1200 | 250 |
| 船舶16 | 40.1 | 700 | 160 |
| 船舶17 | 45.3 | 900 | 150 |
| 船舶18 | 49.6 | 800 | 150 |
| 船舶19 | 53.5 | 1500 | 290 |
| 船舶20 | 56.9 | 800 | 150 |
程序结果:
最优目标函数
bestValue =
61
最优染色体
bestChrom =
1 至 28 列
3 5 4 7 11 1 6 8 14 9 12 13 15 17 2 10 18 16 19 21 20 15 366 271 347 645 290 463
29 至 42 列
165 380 103 588 675 770 59 344 685 154 403 50 659 59
优先顺序
S =
3 5 4 7 11 1 6 8 14 9 12 13 15 17 2 10 18 16 19 21 20
泊位
M1 =
15 366 271 347 645 290 463 165 380 103 588 675 770 59 344 685 154 403 50 659 59
outcell =
'船编号' '泊位'
[ 1] [ 15]
[ 2] [ 366]
[ 3] [ 271]
[ 4] [ 347]
[ 5] [ 645]
[ 6] [ 290]
[ 7] [ 463]
[ 8] [ 165]
[ 9] [ 380]
[ 10] [ 103]
[ 11] [ 588]
[ 12] [ 675]
[ 13] [ 770]
[ 14] [ 59]
[ 15] [ 344]
[ 16] [ 685]
[ 17] [ 154]
[ 18] [ 403]
[ 19] [ 50]
[ 20] [ 659]
[ 21] [ 59]
outcell =
'船id' '泊位' '到港时间' '开始时间' '结束时间'
[ 3] [ 271] [ 6.5] [ 6.5] [ 16]
[ 5] [ 645] [ 9.2] [ 9.2] [ 19.2]
[ 4] [ 347] [ 8] [ 16] [ 19.5]
[ 7] [ 463] [ 17.5] [ 19.5] [ 26]
[ 11] [ 588] [ 26.2] [ 26.2] [ 35.2]
[ 1] [ 15] [ 0] [ 0] [ 7]
[ 6] [ 290] [ 13.6] [ 19.5] [ 22.5]
[ 8] [ 165] [ 20] [ 22.5] [ 30]
[ 14] [ 59] [ 35.5] [ 35.5] [ 42.5]
[ 9] [ 380] [ 22.5] [ 30] [ 34]
[ 12] [ 675] [ 30] [ 35.2] [ 41.7]
[ 13] [ 770] [ 32.6] [ 41.7] [ 46.2]
[ 15] [ 344] [ 37.2] [ 37.2] [ 47.7]
[ 17] [ 154] [ 40.1] [ 42.5] [ 46]
[ 2] [ 366] [ 2.5] [ 47.7] [ 51.7]
[ 10] [ 103] [ 25.3] [ 46] [ 51.5]
[ 18] [ 403] [ 45.3] [ 51.7] [ 56.2]
[ 16] [ 685] [ 38] [ 46.2] [ 52.2]
[ 19] [ 50] [ 49.6] [ 51.5] [ 55.5]
[ 21] [ 59] [ 56.9] [ 56.9] [ 60.9]
[ 20] [ 659] [ 53.5] [ 53.5] [ 61]
>>
五、结论
本文提出采用遗传算法来解决连续泊位调度问题,并给出完整的模型描述和算法流程。通过模拟实验可以效果可以验证该方法的有效性。未来工作可以考虑引入更多约束条件,如船只类型、吃水线高度等,进一步优化泊位利用率。
这篇关于遗传算法优化连续泊位调度问题概述的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
