堆垛约束下基于偏序的路径优化时间窗松弛方法

摘要

在求解车辆路径优化问题时,通常使用时间窗对任务之间的偏序关系进行建模,设计带时间窗约束的路径优化模型与算法,然而时间窗约束与偏序约束是不等价的.在集装箱码头堆垛作业背景下,针对时间窗约束的路径优化模型,提出将时间窗约束转化为偏序约束的松弛方法,并据此设计偏序约束的路径优化模型.在分支定界算法框架下,研究时间窗约束与偏序约束之间的关系,对两种模型的特征进行分析.采用Solomon数据集进行数值分析,验证两个模型在寻优能力与性能之间的差异.结果表明,偏序模型具有更好的优化性能,但是时间窗模型具有更好的计算时间性能,通过时间窗紧缩的特征分析发现基于时间窗分解设计偏序模型求解算法是新的研究方向.