数学启发算法求解单源设施区位及其变种问题

摘要: 考虑设施服务区空间连续和设施数量限制，对经典的单源设施区位问题(SSCFLP)进行扩展，形成变种问题：设施服务区空间连续SSCFLP(CFLSAP)、设施数量限制的SSCFLP (SSCKFLP)和设施服务区空间连续及数量限制的SSCFLP(CKFLSAP)。针对SSCFLP及其变种问题，提出了一个数学启发算法。该算法从一个初始解开始，迭代地对当前解进行超大邻域搜索改进，直到若干次尝试不能该改进当前解为止。超大邻域定义步骤如下：随机选择一个客户，从当前解中选择客户附近Q个最邻近设施及其客户，再挑选这些客户的最邻近候选设施。使用所选择候选设施子集和客户子集，构建子问题数学模型，求解模型，并使用模型解更新当前解。构造2组案例数据测试本文算法，结果表明：数学启发算法能够有效地求解SSCFLP及其变种问题，求解结果极其接近问题最优解或目标值下界，相对差异为0.01%(SSCFLP)、0.22%(CFLSAP)、0.00%(SSCKFLP)和0.08%(CKFLSAP)。另外，SSCFLP或SSCKFLP增加设施服务区空间连续约束后，目标值增加幅度不大，但最优设施区位可能发生变化。