基于改进分支定价算法的ASC车辆路径问题

摘要

针对自动化集装箱码头自主驾驶无人跨运车(Autonomous Straddle Carrier,ASC)的车辆路径问题,提出了一种改进的分支定价算法.考虑ASC的载荷量、每个作业点的时间窗和需求量等因素,以ASC总行驶距离最短为目标建立混合整数规划模型.根据Danzig-Wolf分解原理将模型分解为主问题和子问题,设计剪枝策略缩小解搜索空间,采用脉冲算法求解定价子问题,并嵌入列生成算法不断迭代寻优.在Java中调用Cplex求解小规模和较大规模算例,通过与传统分支定界算法的对比实验,以及对定界策略的时间步长和ASC不同载荷量的灵敏度分析,验证了模型的可行性和算法的有效性.