分类: 地球科学 >> 地理学 分类: 管理学 >> 管理工程 提交时间: 2021-06-09
摘要: 考虑设施服务区空间连续和设施数量限制,对经典的单源设施区位问题(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增加设施服务区空间连续约束后,目标值增加幅度不大,但最优设施区位可能发生变化。
分类: 地球科学 >> 地理学 提交时间: 2021-05-19
摘要: 本文提出了一个数学启发算法求解单源设施区位问题(SSCFLP)。该算法从一个初始解开始,迭代地对当前解进行超大邻域搜索改进,直到若干次尝试不能该改进当前解为止。算法中,初始解使用拉格朗日松弛启发算法,超大邻域搜索采用子问题数学模型精确求解。算法设计的要点在于超大邻域的选择,既不能太大造成子问题求解困难,也不能太小造成当前解难以改进。使用5组272个基准测试案例进行算法测试,共发现191个案例的最优解,更新36个案例的已知最好解,表明数学启发算法性能优异。与近年的代表性算法(如割平面、核搜索、超图多交换启发、廊道方法)进行比较,在大规模案例上,本文算法无论求解质量还是计算时间均具有显著的优势。