線狀需求下兩階段設施選址問題

王紫萌　周建勤

摘要：鑒于大型交通線路建設項目的物資需求隨時間變化（在初期階段需求較低;在后續階段項目全面展開，需求顯著上升），本文采用線積分對沿線連續分布的線狀物資需求進行刻畫，構建兩階段設施選址模型，第一階段進行部分設施的選址，第二階段對剩余設施選址，以實現系統總成本最低的目標。針對模型特點，設計基于Voronoi圖的兩階段交替定位-分配（alternative location-allocation，ALA）算法進行求解，并進行實例分析，比較兩階段模型與傳統模型的異同。研究表明，將兩階段設施選址模型應用于交通線路建設項目多物流節點選址，能節約運營成本，并緩解初期資金壓力。

關鍵詞：設施選址; 線狀需求; 交替定位-分配（ALA）算法; Voronoi圖

中圖分類號：? U492.1+44

文獻標志碼：A

Two-stage facility location problems with linear demands

WANG Zimeng， ZHOU Jianqin

（School of Economics and Management， Beijing Jiaotong University， Beijing 100044， China）

Abstract：

The material demand of a large-scale traffic line construction project changes with time： the demand is lower in the initial stage; the project is fully carried out in the subsequent stage， and the demand is significantly increased.In view of this， the line integral is adopted to describe the linear material demands with the continuous distribution along the line， and a two-stage facility location model is constructed， where some facilities are located in the first stage， and the others are located in the second stage so as to minimize the total cost. According to the characteristics of the model， a two-stage alternative location-allocation （ALA） algorithm based on Voronoi diagram is designed to solve the model. An example analysis is carried out to compare the similarities and differences between the two-stage model and the traditional model. The research shows that the application of the two-stage facility location-allocation model to the multi-logistics node location of the traffic line construction project can save the operation cost and relieve the initial financial pressure.

Key words：

facility location; linear demand; alternative location-allocation （ALA） algorithm; Voronoi diagram

0 引 言

大型交通線路覆蓋距離較長，建設過程中涉及海量的物資供給，同時產生巨大的物流費用。物流節點選址對于大型交通線路建設項目影響重大。因此，在實際建設中需要進行科學合理的物流節點選址，控制物流成本，保障物資供應。

在交通線路建設項目中，物資需求在空間上沿擬建交通線路分布。擬選址的物流節點需要為整條路段提供服務。需求以一定的密度連續分布在一條曲線上的設施選址問題被定義為線狀需求設施選址問題，它不同于經典的離散需求設施選址問題。GDEN等[1]研究了鐵路建設工程沿線的物流節點選址問題，計明軍等[2]研究了線狀需求下長江航道危險品應急中心選址優化問題，但他們都將連續線狀需求離散成若干個點狀需求，這與實際連續線狀需求存在差異[3]。ALEXANDRIS等[4]證明了需求刻畫方式會對選址結果產生影響。連續線狀需求可以采用線積分進行刻畫。BERMAN等[5]和GASTNER[6]用密度函數描述連續線狀需求。

在交通線路建設項目中，物資需求的時間分布特點也會對物流節點選址產生影響。在項目建設初期階段，需要完成“三通一平”工作，物資需求量和物流工作量較小;進入項目建設中期階段，隨著大規模土建類施工展開，物資需求量和物流量顯著增加：擬建交通線路上的物資需求密度在兩個階段內差異明顯。針對需求動態變化的設施選址問題：陳鑫等[7]考慮了需求動態變化下的情形;BRANCOLINI等[8]提出了根據當前階段需求進行多階段選址的策略;SUZUKI等[9]對設施多階段選址的幾種策略進行了對比分析，認為分階段選址節省的設施運作成本可能足以彌補增加的運輸成本。針對需求兩階段變化的情況，一些學者研究了兩階段設施選址模型的實際應用，這里的兩階段設施選址指先進行部分設施的選址，隨后進行其余設施的選址。代文強[10]設計了兩階段設施選址優化模型，針對離散需求，使用近似優化算法進行了求解。姜秀山等[11]研究了鐵路應急服務設施的兩階段選址問題。魏明等[12]針對公交站場選址布局問題，也設計了兩階段模型與算法。然而，這些兩階段選址文獻多集中在離散需求領域，未見針對連續需求的研究。

為此，本文引入線密度函數，用線積分對連續線狀需求進行刻畫，以此取代經典需求離散化處理方式。考慮需求兩階段變化的實際情況，本文建立兩階段設施選址模型。在初期階段需求密度較低時進行部分設施的選址，在后續階段需求密度上升時對其余的設施進行選址。線狀需求下的兩階段設施選址模型可為實際的交通線路建設項目中的設施選址決策提供支持。

1 問題描述與建模

1.1 問題描述

在交通線路建設項目中，物資需求沿擬建線路連續分布。物流節點可以位于交通線路所在二維平面內的任意一點，物流節點的選址分兩個階段展開。在項目建設初期階段，物資需求量較低，需要按照當時的物資需求密度建設一定數量的物流節點。隨著項目建設的推進，物資需求量顯著增大，需要在已有物流節點的基礎上增加一定數量的物流節點，并由全部物流節點共同為項目建設提供服務，以滿足需求并有效降低成本。

為此，本文提出以下假設：（1）各個物流節點的功能無差異;（2）物流節點具有足夠大的服務能力，無容量限制;（3）物資需求密度在兩個階段內都是確定的;（4）采用歐氏距離度量距離;（5）從各個物流節點到需求線路的運輸費率相同。

首先定義參數和變量：k表示階段，k=1，2;P為物流節點集合，P={1，2，…，p};Q為第一階段待選址的物流節點集合，Q={1，2，…，q};μk為單個設施在第k階段的運營費率;g為運輸費率;L為物資需求線路;Lj為由物流節點j服務的物資需求線路子區段;X為物資需求線路上的點，X=（x，y）;ρk（X）為第k階段X處的需求密度;Xj為物流節點j的坐標，Xj=（xj，yj）;T為整條擬建線路上所有需求點的集合，t∈T;Tj為Lj內所有需求點的集合。

物資需求線路L的參數方程表示為

x=u（t）， y=v（t）， t∈T

（1）

由物流節點j提供服務的物資需求線路子區段Lj的參數方程表示為

x=u（t）， y=v（t）， t∈Tj

（2）

1.2 模型構建

交通線路建設項目的物流總成本主要包括物流節點的總運營成本、從供應商到物流節點的上游運輸成本和從物流節點運輸到交通線路的末端運輸成本。由于從供應商到物流節點的距離很遠，物流節點位置對上游運輸成本影響較小，所以從供應商到物流節點的上游運輸成本不予考慮。

物流節點j的運輸成本可以表示為

其中X-Xj表示從物流節點j到物資需求線路上的點X的距離。結合式（2）～（4）可以得到

對第一階段的q個物流節點進行選址，選址模型如下：

式（6）為目標函數，表示第一階段末端運輸總成本最低;式（7）刻畫了需求分配的靠近性原則，即任一物流節點服務的需求線路子區段都是距離該節點最近的;式（8）表示整條物資需求線路都有物流節點提供服務。

第二階段共有p個物流節點提供服務，其中q個物流節點的坐標已經在第一階段確定，需要對p-q個新增物流節點進行選址。第二階段物流節點選址模型如下：

式（9）為目標函數，表示第二階段末端運輸總成本最低;式（10）和（11）的意義分別與式（7）和（8）類似。

總運營成本與設施數量和運營費率成正比，建設期內總運營成本可以表示為

物流總成本為第一階段末端運輸成本、第二階段末端運輸成本和總運營成本之和，可以表示為

2 求解算法

2.1 單設施選址算法

單設施選址算法是多設施選址算法的基礎。為求解連續線狀需求下物流節點的運輸成本（式（4）），根據定積分的定義，在Tj=[tj，tj]區間內插入n-1個分點，tj=t0

當λ→0，即n→∞時，需求線路等同于無窮多個需求點的集合，可將式（14）寫成如下形式：

利用式（19），通過迭代即可最終求得需求線路子區段Lj內物流節點j的最優位置（xj，yj）。

單設施選址算法步驟如下：

步驟1 輸入Lj{x=u（t），y=v（t）}、Tj、g、ρk（X）、δ（迭代終止容差值）、n。

步驟2 初始化：m=0，隨機生成初始坐標（x（m）j，y（m）j），根據式（17）計算初始運輸成本Z（m）j。

步驟3 迭代：將（x（m）j，y（m）j）代入式（19）右側，計算并更新坐標（x（m+1）j，y（m+1）j）。

步驟4 計算運輸成本：將（x（m+1）j，y（m+1）j）代入式（17），計算運輸成本Z（m+1）j。

步驟5 收斂判定：若滿足Z（m+1）j-Z（m）j≤δ，則Xj=（x（m+1）j，y（m+1）j）;否則，令m←m+1，返回步驟3。

步驟6 輸出Xj。

式（17）中，物資需求線路等同于無窮多個需求點的集合，這相當于將連續需求線路離散為充分多個需求點，將連續線狀需求下的設施選址問題轉化為離散需求下的設施選址問題進行求解。WESOLOWSKY等[13]證明了離散需求下迭代選址算法的收斂性，因此連續線狀需求單設施選址算法也是收斂的。

2.2 第一階段模型求解算法

解決多設施選址分配問題有很多經典算法，其中最為廣泛使用的是COOPER[14]提出的交替定位-分配（alternative location-allocation，ALA）算法。該算法具有收斂速度快、精度高的特點，關鍵思路在于給定設施初始坐標，劃分需求，將多設施選址問題轉化成單設施選址問題進行求解，得到新的設施位置后再進行分配和迭代，直到滿足容差值，最終得到多設施選址分配問題的最優解。

二維平面內需求的劃分多采用Voronoi圖的方法。Voronoi圖是計算幾何領域對平面區域進行分割的經典方法之一。

定義1 設Xj（j∈P）為二維平面內p個設施的坐標，則由給出平面內需求的劃分，劃分后的圖形被稱為以物流節點j為生成元的Voronoi圖。圖1中各多邊形被稱為以物流節點為生成元的Voronoi多邊形，Voronoi多邊形的交點稱為節點。

性質1 Voronoi圖各多邊形區域內任意一點到該多邊形區域內生成元的距離不大于到任意其他多邊形內的生成元的距離。

性質2 Voronoi圖的每個多邊形區域內只存在一個生成元。

本文將Voronoi圖與經典的ALA算法相結合，設計了改進算法。使用Voronoi圖劃分需求線路，將多設施選址問題轉化為若干單設施選址問題。再使用單設施選址算法求解。隨后，進行交替選址和需求劃分迭代，對兩階段模型多設施選址問題進行求解。第一階段模型算法步驟如下：

步驟1 輸入L{x=u（t），y=v（t）}、T、q、g、ρ1（X）、δ、n。

步驟2 初始化：m=0，隨機生成q個坐標為X（m）j（j∈Q）的點，作為初始坐標。

步驟3 需求劃分：根據式（7）對需求線路L進行劃分，確定各需求線路子區段L（m）j（j∈Q）。

步驟4 計算運輸成本：

步驟4.1 計算需求線路子區段運輸成本：根據式（17），分別計算L（m）j內運輸成本Z（m）j（j∈Q）。

步驟4.2 計算總需求線路運輸成本：根據式（6），計算總運輸成本C（m）1。

步驟5 再選址：在需求線路子區段內，使用單設施選址算法求解各物流節點新坐標X（m+1）j（j∈Q）。

步驟6 再次劃分需求：與步驟3類似，將X（m+1）j（j∈Q）代入，確定L（m+1）j（j∈Q）。

步驟7 再次計算運輸成本：與步驟4類似，計算得到C（m+1）1。

步驟8 收斂判定：若滿足C（m+1）1-C（m）1≤δ，則Xj=X（m+1）j（j∈Q）;否則，返回步驟5，令m←m+1。

步驟9 輸出Xj（j∈Q）。

2.3 第二階段模型求解算法

第二階段需求密度上升，需要加入其他物流節點提供服務。在第一階段已確定q個物流節點位置，在第二階段再加入p-q個物流節點，使第二階段在滿足需求的條件下總運輸成本最低。第二階段模型求解算法步驟如下：

步驟1 輸入L{x=u（t），y=v（t）}、T、p、q、g、ρ2（X）、δ、n。

步驟2 初始化：m=0，隨機生成p-q個坐標為X（m）j（j∈P＼＼Q）的點，作為初始坐標。

步驟3 需求劃分：根據式（10）對需求線路L進行劃分，確定各需求線路子區段L（m）j（j∈P）。

步驟4 計算運輸成本：

步驟4.1 計算需求線路子區段運輸成本：根據式（17），分別計算L（m）j內運輸成本Z（m）j（j∈P）。

步驟4.2 計算總需求線路運輸成本：根據式（9），計算總運輸成本C（m）2。

步驟5 部分節點再選址：

步驟5.1 在Lj（j∈P＼＼Q）內使用單設施選址算法求解物流節點j的新坐標X（m+1）j（j∈P＼＼Q）。

步驟5.2 X（m+1）j=X（m）j（j∈Q）。

步驟6 再次劃分需求：與步驟3類似，將X（m+1）j（j∈P）代入，確定L（m+1）j（j∈P）。

步驟7 再次計算運輸成本：與步驟4類似，計算得到C（m+1）2。

步驟8 收斂判定：若滿足C（m+1）2-C（m）2≤δ，則停止計算;否則，返回步驟5，m←m+1。

步驟9 輸出Xj（j∈P）。

3 算例分析

3.1 算例設計

江蘇南沿江城際鐵路于2018年10月開工，建設工期4年。線路自南京南站引出，向東經過句容市、金壇區、武進區、江陰市、張家港市和常熟市，終至滬通鐵路太倉站。線路全長270.2 km，具體走向如圖2所示。

本文算例基于江蘇南沿江城際鐵路建設的實際背景，探究物流節點的選址問題。首先收集沿線重要站點經緯度坐標，轉化為平面坐標系坐標。將線路擬合成若干首尾相連的折線段表示。由于整條線路均位于江蘇省南部，地形地貌與交通運輸情況無顯著區別，故設定全線的運輸費率均為1元/（t·km）。在該建設項目開始前，進行施工組織調查，根據《鐵路工程施工組織設計規范》和《鐵路大型臨時工程計算方法及設計技術研究》的規定，結合項目實際情況，編寫組織設計方案，制定沿線各子區段在各階段內級配碎石的用料計劃，可簡化為表1中的數據。在建設過程中擬建8個物流節點，為建設項目沿線提供級配碎石等物料。建設期第一年為第一階段，進行5個物流節點選址;第二年至第四年為第二階段，進行3個物流節點選址。

3.2 結果分析

首先確定沿線8個關鍵城市的經緯度坐標，使用高斯-克呂格投影轉化為平面直角坐標，對擬建線路進行擬合。隨后根據兩階段選址模型和算法，使用MATLAB編寫程序進行求解，可以獲得第一階段和第二階段物流節點最優位置以及需求的劃分。兩階段物流節點在平面直角坐標系中的選址分配見圖3，其經緯度坐標見表2。

對于第一階段進行5個物流節點選址，第二階段進行3個物流節點選址的兩階段選址模型，可以求解出其第一階段運輸成本C1（5，3）、第二階段運輸成本C2（5，3）分別為1 185.987 8萬元和5 875.038 6萬元。

為將兩階段選址模型與傳統的一次性選址模型進行比較，針對第一階段即對全部的8個物流節點進行一次性選址的傳統選址模型，同樣進行運輸成本的計算，得到C1（8，0）和C2（8，0）分別為572.305 1萬元和5 723.051 0萬元。比較可知，兩階段選址模型的運輸成本略高于一次性選址模型的運輸成本。

兩階段選址模型的物流總成本為

C（5，3）=C1（5，3）+C2（5，3）+C3（5，3）

傳統的一次性選址模型的物流總成本為

C（8，0）=C1（8，0）+C2（8，0）+C3（8，0）

如果兩階段選址模型優于傳統的一次性選址模型，則兩階段選址模型的物流總成本應當小于等于傳統的一次性選址模型的物流總成本，即

C（5，3）≤C（8，0）

整理得到

μ1≥C1（5，3）+C2（5，3）-C1（8，0）-C2（8，0）3

計算可得：當μ1≥255.223 4萬元/a時，兩階段選址模型的物流總成本低于一次性選址模型的物流總成本，選擇兩階段選址模型比一次性選址模型更加有利;反之，即當μ1<255.223 4萬元/a時，選擇一次性選址模型更能節約成本。

μ1是單個物流節點第一階段的運營費率，第一階段的運營費率與第一階段物流節點運營的時間和單個物流節點單位時間內運營成本正相關。當該工程項目第一階段建設期較長，物流節點單位時間內運營成本較高，且運輸費率較低時，與傳統的一次性選址模型相比，選擇兩階段選址模型，能夠節約物流總成本，為工程建設帶來經濟效益。相反地，如果第一階段建設期較短，物流節點單位時間內運營成本較低，且運輸費率較高時，則應考慮選擇傳統的一次性選址模型。

總之，兩階段選址模型與傳統的一次性選址模型相比，增加了一定的運輸成本，但節約了物流節點的運營成本，同時降低了項目建設初期資金籌措的壓力。在工程建設項目中，應根據實際的相關參數進行計算與比較，選擇最優的選址策略。

4 結 論

針對大型交通線路建設項目中的物流節點選址問題，考慮交通線路需求連續線狀分布且需求隨時間兩階段變化的特點，采用線密度函數刻畫需求，構建了線狀需求下兩階段選址模型。分析連續線狀需求與經典離散需求的異同，設計了基于Voronoi圖的改進交替定位-分配（ALA）算法。以江蘇南沿江城際鐵路物流節點建設項目為例進行實證研究，證明了模型和算法的有效性。兩階段選址模型與傳統的一次性選址模型相比，增加了少量的運輸成本，但節約了運營成本，緩解了項目建設初期資金籌措的壓力，具有現實意義。本文提出的模型為交通線路建設項目中物流節點選址的實際問題提供了解決思路。進一步的研究可以考慮在有物流節點容量限制的情況下的物流節點兩階段選址問題。另外，需求不確定的兩階段設施選址問題也值得研究。

參考文獻：

[1]GDEN H，SRAL H. Locating mobile facilities in railway construction management[J]. Omega， 2014， 45： 71-79. DOI： 10.1016/j.omega.2014.01.001.

[2]計明軍， 宋婷婷， 宋佳， 等. 線狀需求下的長江航道危險品應急中心選址優化[J].運籌與管理， 2016， 25（5）： 68-74.DOI： 10.12005/orms.2016.0163.

[3]WESOLOWSKY G O， LOVE R F. Location of facilities with rectangular distances among point and area destination[J].Naval Research Logistics Quarterly， 1971， 18： 83-90.DOI： 10.1002/nav.3800180107.

[4]ALEXANDRIS G， GIANNIKOS I. A new model for maximal coverage exploiting GIS capabilities[J]. European Journal of Operational Research，2010， 202（2）： 328-338. DOI： 10.1016/j.ejor.2009.05.037.

[5]BERMAN O， KRASS D， MENEZES M. Location and reliability problems on a line： impact of objectives and correlated failures on optimal location patterns[J]. Omega， 2013， 41： 766-779.DOI： 10.1016/j.omega.2012.09.002.

[6]GASTNER M T. Scaling and entropy in p-median facility location along a line[J].Physical Review E， 2011， 3（16）： 1-7. DOI： 10.1103/PhysRevE.84.036112.

[7]陳鑫， 汪傳旭， 石劉紅.模糊隨機需求下應急救援中心排隊選址模型及算法[J].上海海事大學學報， 2011， 32（1）： 74-79. DOI： 10.3969/j.issn.1672-9498.2011.01.016.

[8]BRANCOLINI A， BUTTAZZO G， SANTAMBROGIO F， et al. Long-term planning versus short-term planning in the asymptotical location problem[J]. Control， Optimisation and Calculus of Variations， 2009， 15（3）： 509-524. DOI： 10.1051/cocv：2008034.

[9]SUZUKI T， ASAMI Y， OKABE A. Sequential location-allocation of public facilities in one- and two-dimensional space： comparison of several policies[J]. Mathematical Programming， 1991， 52： 125-146. DOI： 10.1007/BF01582883.

[10]代文強.兩階段選址優化問題研究[J].運籌與管理， 2007， 16（6）： 47-50. DOI： CNKI：SUN：YCGL.0.2007-06-009.

[11]姜秀山， 張贛， 匡敏. 鐵路應急服務設施雙階段組合選址模型研究[J]. 交通運輸系統工程與信息， 2015， 15（3）： 152-159. DOI： 10.3969/j.issn.1009-6744.2015.03.024.

[12]魏明， 陳學武， 孫博. 公交站場選址布局優化模型和算法[J]. 交通運輸系統工程與信息， 2015， 15（4）： 113-117. DOI： 10.3969/j.issn.1009-6744.2015.04.017.

[13]WESOLOWSKY G O， TRUSCOTT W O. The multiperiod location-allocation problem with relocation of facilities[J]. Management Science， 1975，22（1）： 57-65. DOI： 10.2307/2629789.

[14]COOPER L. Location-allocation problems[J]. Operations Research， 1963， 11： 331-343. DOI： 10.1287/opre.11.3.331.

（編輯 趙勉）

收稿日期： 2019-09-09

修回日期： 2020-02-24

基金項目： 國家自然科學基金（71372013）

作者簡介：

王紫萌（1996—），女，遼寧遼陽人，碩士研究生，研究方向為物流管理與工程，（E-mail）1679605902@qq.com;

周建勤（1975—），男，湖北黃岡人，教授，博導，博士，研究方向為物流管理與工程，（E-mail）jqzhou@bjtu.edu.cn