《表3 大规模算例的计算结果》
注:UDS为使用单向走行求解MIP的最优解;“7.90/1/1 800.04”表示“与最优解的相对偏差(%)/找到最优解的个数(个)/计算时间(s)”,“23.74/6/1 800.10”表示“与最优解的平均相对偏差(%)/找到最优解的总数(个)/平均计算时间(s)”,其余依此类推。
表3所示为大规模算例计算结果。当任务数n≥20时MIP的求解时间明显变长,耗尽时间限定的1 800 s。随着算例的增加,使用Gurobi求解的UDS平均运行时间显著增加。UDS_A和UDS_D都耗尽了给定的限制时间,并且仅仅6个算例找到了最优解。UDS求解大规模算例平均相对偏差为19.56%,由此表明算例规模增加,问题的复杂程度也急剧增加。初始解的平均相对偏差为3.83%,这比UDS策略解的质量要高得多。此外,初始解的平均计算用时仅为8.09 s;对于ANPS算法,相对偏差从0%到0.71%不等,120个算例的平均相对偏差仅为0.08%。从表3可以发现ANPS算法为120个算例中的115个提供了最优解,平均运行时间为275.15 s。值得注意的是,当作业任务数n大于60个时,ANPS算法总能给出最优解,由此证明ANPS算法在求解大规模算例时是有效的。初始解给出最优解数量为24,这意味着91个算例的最优解是由ANPS算法搜索得出的。
图表编号 | XD00128517800 严禁用于非法目的 |
---|---|
绘制时间 | 2019.11.26 |
作者 | 郭鹏、何迅、许素瑕 |
绘制单位 | 西南交通大学机械工程学院、西南交通大学机械工程学院、西南交通大学机械工程学院 |
更多格式 | 高清、无水印(增值服务) |