帶約束多設施選址分配模型與基于變分不等式的啟發式算法

蔣建林, 程 坤

(南京航空航天大學 理學院,江蘇 南京 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) 該模型不僅考慮了各個……