MAU算法流程理解

参考文献：湘江船闸的过闸调度算法研究(李 楠，李桂华，尹剑平)
（湖南湘江航运建设开发有限公司，湖南 长沙 410011）

MAU算法流程

图4展示的是一种船舶排档算法（MAU算法），它采用"行式布局"策略，将船闸空间划分为多行进行排布。算法核心思想是：优先安排等待时间最长的船舶，并在每行中尽可能多地并排安排船舶。

核心概念解析

1. 剩余长度：

   • 指船闸在长度方向(X轴) 上剩余可用空间
   • 初始值 = 船闸总长度(180m)
   • 每安排完一行，减去该行中最长船舶的长度
   • 更新公式：新剩余长度 = 原剩余长度 - 当前行最大船长度

2. 剩余宽度：

   • 指当前行在宽度方向(Y轴) 上剩余可用空间
   • 初始值 = 船闸总宽度(23m)
   • 每安排一艘船，减去该船宽度
   • 更新公式：新剩余宽度 = 原剩余宽度 - 新安排船的宽度
   • 每行开始时重置为船闸总宽度

算法流程详解（结合具体数据）

初始状态

• 船闸尺寸：180m × 23m
• 船舶队列（按等待时间降序排列）：

  1:65.0×11.7 (等待10.0h)
  2:31.0×5.8  (等待9.9h)
  3:29.0×6.3  (等待9.8h)
  4:54.0×9.8  (等待9.7h)
  5:51.0×9.8  (等待9.6h)
  6:40.0×7.8  (等待9.5h)
  7:36.0×7.2  (等待9.4h)
  8:57.0×10.5 (等待9.3h)
  9:60.0×11.5 (等待9.2h)
  10:70.0×12.0(等待9.1h)
  

第1行排档过程

1. 选择队首船舶（等待时间最长）：

   • 船舶1 (65m×11.7m)
   • 放置位置：(0, 0)
   • 剩余宽度：23 - 11.7 = 11.3m

2. 判断能否放入多艘：

   • 剩余宽度11.3m > 0 → 可以尝试放入更多船舶
   • 选择宽度最小的两艘：船舶2(5.8m) + 船舶3(6.3m) = 12.1m > 11.3m → 不能同时放入

3. 尝试放入单艘：

   • 选择长度最接近首船(65m)且宽度≤11.3m的船舶
   • 候选：船舶8(57m×10.5m) - 长度差8m
   • 船舶4(54m×9.8m) - 长度差11m → 选择船舶8
   • 放置位置：与船舶1并排，Y坐标相邻
   • 剩余宽度：11.3 - 10.5 = 0.8m（小于最小船宽5.8m，结束本行）

4. 更新全局状态：

   • 本行最大长度 = max(65,57) = 65m
   • 新剩余长度 = 180 - 65 = 115m
   • 剩余宽度重置为23m（新行开始）

第2行排档过程

1. 选择当前队首：

   • 船舶2 (31m×5.8m) - 现在等待时间最长
   • 放置位置：(65, 0)（X坐标接上一行末尾）
   • 剩余宽度：23 - 5.8 = 17.2m

2. 判断能否放入多艘：

   • 选择宽度最小两艘：船舶3(6.3m) + 船舶7(7.2m) = 13.5m ≤ 17.2m → 可以放入
   • 同时安排船舶3和船舶7

3. 更新行状态：

   • 放置位置：与船舶2并排
   • 剩余宽度：17.2 - 6.3 - 7.2 = 3.7m（小于最小船宽5.8m，结束本行）
   • 本行最大长度 = max(31,29,36) = 36m（船舶7长度）

4. 更新全局状态：

   • 新剩余长度 = 115 - 36 = 79m
   • 剩余宽度重置为23m

第3行排档过程

1. 选择当前队首：

   • 船舶4 (54m×9.8m)
   • 放置位置：(65+36=101, 0)
   • 剩余宽度：23 - 9.8 = 13.2m

2. 尝试放入单艘（无法放多艘）：

   • 选择长度最接近54m且宽度≤13.2m的船舶
   • 船舶5(51m×9.8m) - 长度差3m
   • 船舶6(40m×7.8m) - 长度差14m → 选择船舶5
   • 剩余宽度：13.2 - 9.8 = 3.4m（结束本行）

3. 更新全局状态：

   • 本行最大长度 = max(54,51) = 54m
   • 新剩余长度 = 79 - 54 = 25m

终止条件

• 剩余长度25m < 剩余船舶最小长度(29m)
• 船舶6(40m), 9(60m), 10(70m)无法安排
• 共安排7艘船舶，使用长度：65+36+54=155m

算法特点总结

1. 优先级策略：

   • 严格按等待时间排序（FCFS变种）
   • 等待时间长的绝对优先

2. 空间利用策略：

   • 行式布局：船舶在宽度方向并排
   • 长度方向：每行取最长船舶决定行高
   • 宽度方向：贪心策略（先尝试放最多船舶）

3. 决策点：

实际调度效果分析

使用论文数据在180×23m船闸中：

• 成功安排：7艘（1,2,3,4,5,7,8）
• 未安排：3艘（6,9,10）
• 空间利用率：
  • 长度利用率：155/180 ≈ 86%
  • 宽度利用率：平均每行宽度利用率>90%
• 算法局限：
  • 可能遗留"碎片空间"（如行末的小空隙）
  • 对超长船舶处理不足（如船舶10需要70m>25m剩余）
  • 严格按等待时间排序可能不是最优解

封面图片地址