蒋建林, 程 坤

(南京航空航天大学 理学院,江苏 南京 210016)

0 引言

在现代物流系统中,设施选址是一个具有战略意义的课题,设施选址模型的研究与应用对现实生活有着重要而广泛的指导价值[1-7].韦伯问题(Weber problem,WP)[1]是设施选址领域的经典问题之一,它是指在平面上选择一个新设施,要求新设施到平面上已存在的m个需求点(顾客)间的欧几里得距离和达到最小.韦伯问题的模型是

(1)

其中ai是第i个需求点的已知位置,wi是第i个需求点的权重,m是需求点的数目,是新设施的未知位置,‖·‖2是l2范数.多设施选址问题(multi-source Weber problem,MWP)[2]是设施选址领域中另一个经典问题,其模型为

(2)

其中aj是第j个需求点的已知位置,xi表示第i个设施点的位置,sj表示第j个需求点的权重,sij表示第i个设施点服务第j个需求点的权重,m是待建的设施点的个数.

Weiszfeld算法[3]是求解单设施选址问题的经典算法,后又有改进的Weiszfeld算法[8]、Newton-Weiszfeld[5]等，均可以有效地求解WP.Cooper算法[2]是求解多设施选址问题的经典算法,分支定价算法[6]、Cooper-PC算法[7]等都可以有效地求解MWP.

1 模型的描述

考虑到实际生活中的设施之间会存在相互运输的情况,并且设施的选择也是有一定区域限制的,因此提出如下模型:

(3)

其中aj,xi,sij,sj与(2)是一致的,wij表示设施i与设施j的调运权重,Si为平面上的闭凸集,表示第i个设施的约束区域.在(3)中,‖·‖p表示lp范数(p≥1),是(1)和(2)中l2范数更一般的情形.称上述模型为约束多设施选址-分配模型,简称模型(3).

模型(3)与经典的多设施选址模型MWP主要不同在于:1) 该模型不仅考虑了各个……