谢 维,关嘉欣,周 游,朱文斌

(华南理工大学 工商管理学院,广州 510641)

登机口分配问题求解的目标函数通常考虑两个主要目标:最小化登机口的使用数量和最小化所有航班的延误时间[1,2].在与登机口相关的约束条件当中,例如登机口只能容纳特定类型的飞机、两个大型飞机不能同时被分配到两个登机口等,这些条件必须进行考虑[3,4].当飞机的数量比较少时,可以通过变换不同的目标条件来生成有效的分配计划.但是当飞机数量的显著增加时,我们就很难生成有效的分配方案[5].在目前国内外的研究中,有关登机口分配问题的求解方法可以分为两类:(1)精确算法,其能够产生最优的解决方案.比较典型的有:Mangoubi 等[6]提出了整数线性规划模型,并以最小化旅客的行走距离为目标.Bihr[7]提出了一种原始对偶单纯形算法,并找到了最优解.Yan等[8]建立了多目标0-1 整数规划模型,并使用加权方法、列生成方法、单纯形法和分支定界法来求解该模型.李云鹏等[9]使用CPLEX 求解混合整数规划模型.Bolat[10],Xu 等[11]和Li[12]使用分支定界法来求解他们建立的模型.但是由于登机口分配问题是一个NP-hard的组合优化问题,当扩大求解规模后,可行解的数量将呈指数增加,如果仍然采用精确算法来求解的话,会导致维数灾难,因此研究学者们提出了启发式算法和元启发式算法来对该问题进行求解.(2)启发式算法和元启发式算法.Xu 等[11]采用禁忌搜索算法对登机口分配的0-1 混合整数二次规划模型……