设施服务分区问题的求解算法框架设计

设施服务分区问题(facility service districting problem,FSDP)是指在一个地理区域内,根据服务设施位置和服务能力为其划分服务区,满足供需平衡、形状紧凑和空间连续等要求。空间连续约束使FSDP能更好地满足学区划分、医疗区划分等问题的政策需求,但同时增加了它的求解难度。构造了一个FSDP混合整型线性规划模型,并设计了一个算法框架。框架包括问题定义、初始解、搜索算子和策略等基本模块,支持精确算法、元启发算法和混合算法设计。基于算法框架,实现了数学模型、模拟退火算法、迭代局部搜索算法和数学启发混合算法,并使用4个中大规模案例进行算法测试。实验结果表明,算法框架能够很好地处理空间连续约束的FSDP,支持多种算法快速实现,且求解质量接近案例目标值下界。