陳立婷，北京航空航天大學電子信息工程學院在讀研究生，研究方向:運籌優(yōu)化算法設計與應用、樞紐選址、空中交通管理

顧少英，多倫多大學工業(yè)工程與運籌學研究生，研究方向: 應用統(tǒng)計，隨機過程與優(yōu)化，機器學習

江镕行，同濟大學經(jīng)濟與管理學院碩博連讀生，研究方向：優(yōu)化算法設計及應用、物流與供應鏈、共享汽車

編者按

選址問題是運籌學中非常經(jīng)典的問題。該問題是指在確定選址對象，選址目標區(qū)，成本函數(shù)以及約束條件的前提下，以總物流成本最低或總服務水平最優(yōu)或社會效益最大化為目標，確定物流系統(tǒng)中物流節(jié)點的數(shù)量，位置，從而合理規(guī)劃物流網(wǎng)絡結構。

選址問題在公司實現(xiàn)其經(jīng)營戰(zhàn)略與目標的過程中有著重大的意義。選址的好壞直接影響到生產(chǎn)成本，服務時間，服務質(zhì)量等等，進而影響公司的利潤與其在商業(yè)市場上的競爭力，甚至決定了企業(yè)的命運。一個好的選址可以減少生產(chǎn)成本，節(jié)省顧客購買時間，便利顧客，而差的選址會帶來物流中的不便與損失。由于選址是一項長期性投資，一旦確定下來就不能隨意更改，因此規(guī)劃其位置前必須進行深入的調(diào)查和周密的考慮。

1  選址問題基本介紹

選址問題，旨在選址目標區(qū)內(nèi)確定設施的位置以及數(shù)量，并滿足一定的約束條件，使得目標最優(yōu)。選址問題根據(jù)規(guī)劃區(qū)域，距離，目標有多種分類。

（1）規(guī)劃區(qū)域

連續(xù)選址問題：設施可以在全平面內(nèi)任意范圍內(nèi)選址。當選址區(qū)域過大，需考慮地球的球面效應時，規(guī)劃區(qū)域為曲面。

離散選址問題：設施的候選位置為有限個。

（2）距離

歐幾里得距離：兩點間的直線距離；

方格線距離：兩個點上在標準坐標系上的絕對軸距之總和。

圖中綠色線段為兩點間的歐幾里得距離，黃色線，藍色線，紅色線為方格線距離。方格線距離也稱為計程車幾何或城市區(qū)塊距離。

大圓距離：指的是從球面上兩點間的最短距離。

（3）目標

單目標選址：總運輸成本最低，總費用最低（包含運輸成本，配送中心固定費用等），中樞紐數(shù)目最少，總服務最優(yōu)。其中最低成本的目標函數(shù)為MiniSum形式，總服務最優(yōu)的多為MiniMax形式。如應急設施選址時目標為使需求點盡可能快的得到應急服務。

多目標選址：單目標選址中的多個組合，可通過將多個單目標加權轉化為單目標進行求解。

2  選址問題求解模型綜述

近年來，選址問題在物流管理，交通運輸，通信電訊，醫(yī)療服務等領域有了廣泛的研究和應用。下面介紹下幾種常用的模型。

2.1 重心法選址模型

重心法適用于選址區(qū)域為連續(xù)平面，以歐幾里得距離作為距離形式，以總運輸成本最低為目標函數(shù)的選址問題。重心法選址模型來源于解析幾何，其將物流網(wǎng)絡中的需求點看作一平面內(nèi)的點，把需求量作為重量，一般選取出這一平面內(nèi)的需求點的重心點作為樞紐，以達到減少運輸成本的目的。

重心法目標函數(shù)為：

2.2 p-中值（p-median）模型

p-中值問題中，選址區(qū)域為有限點組成的集合，距離形式為任意形式，目標函數(shù)為總運輸成本最低。P-中值問題限制了樞紐個數(shù)為p個，每個需求點只能與一個樞紐建立連接，可用以下模型表示：

式中，（1）保證了每個需求點僅與一個樞紐節(jié)點有連接，（2）保證了備選節(jié)點集中只有被選中設為樞紐的節(jié)點可與需求點建立連接，（3）保證了樞紐個數(shù)為p個。

2.3 p-中心（p-center）模型

p-中心問題與p-中值問題的唯一不同點在于目標函數(shù)的形式。在p-中心問題中，目標函數(shù)為MinMax形式，目標是使每個需求點到最近設施的最大距離最小，通常用于消防站，警察局等應急設施的選址中。如消防站設施選址問題中，目標為使區(qū)域內(nèi)的每個用戶都能在某個閾值時間內(nèi)得到消防服務，在滿足約束的條件下，該閾值越小越好。

2.4 集合覆蓋模型

集合覆蓋模型是指在覆蓋所有需求點的前提下，使得總建設費用最低，當每個設施的建設費用相同時，問題簡化為樞紐數(shù)目最少，該模型可以表示為：

3  重心法求解介紹

下面我們輔以一個簡單的例子來詳細介紹重心法的求解過程：

如圖所示，共有五個需求點，其各自對應的V,R,X,Y如表所示，

3.1 單設施選址問題：

單設施選址問題的一般求解使用的是迭代重心法，注意到目標函數(shù)的形式為：

求偏導數(shù)可得：

則迭代法的整個流程為：

1） 使用等效重心公式，求得初始等效重心作為初始解，計算花費cost1

2） 使用迭代重心公式，求得迭代后的解，計算花費cost2

3） 比較cost1和cost2，如相等或相差小于閾值，迭代結束，此時的解即為最終的解；否則令cost1=cost2，回到步驟2）

結合例子來看，使用各個需求點的等效重心坐標作為初始解， 

在此例子中等效重心坐標為 （12.4167，12.75）（圖中黑點所示），此時總費用為11323.90

要注意，初始解大部分情況下不是最優(yōu)解。

舉一個簡單的例子，如在（0，0）處需求點P 需求量為10，（10，0）點處需求點Q需求量為1，根據(jù)直接重心法倉庫應選址在（1，0）處，此時花費為19。然而若直接選址在（0, 0）處，總花費僅為10。

當二十次迭代時，

可以看到，解趨于穩(wěn)定，最終的花費為10861.30。

3.2 多設施選址問題

多設施選址問題較單設施選址問題復雜得多，一種常用解法是將其看成多個單設施選址問題來解決。對于一個p設施選址問題來說，求解步驟如下：

1） 隨機選擇p個初始坐標作為初始解，計算花費cost1

2） 使用當前解，將每個需求點分配個距離最近的設施，從而得到p個需求點簇，在每個需求點簇內(nèi)迭代得解，計算花費cost2

3） 比較cost1和cost2，如相等或相差小于閾值，迭代結束，此時的解即為最終的解；否則令cost1=cost2，令迭代后的解作為當前解，回到步驟2）

以p=2為例，

初始解花費為10534：

迭代二十次后，解已經(jīng)穩(wěn)定，此時最終解為9302.43：

3.3其他求解方法

上文介紹了重心法求解單設施選址問題和多設施選址問題，但重心法的應用場景有限，僅適應于約束簡單的選址問題，當問題變得復雜，約束條件增加或目標函數(shù)改變時就難以適用，本節(jié)簡單介紹了一些方法求解更復雜的選址問題。

1.解析解

求解純數(shù)學模型，獲得最優(yōu)解。然而本文提到的幾個選址問題均為NP-Hard問題，在問題規(guī)模較小時可通過CPLEX、Gurobi等求解器求解，但隨著問題規(guī)模擴大，在多項式時間內(nèi)無法獲得解析解。

2.近似解

該方法是解析解的改編方法，常見的方式為采用松弛算法將約束吸收到目標函數(shù)中，減少求解的復雜程度，減少求解時間，但同樣無法應對大規(guī)模問題。

3.啟發(fā)式算法

該方法是較為常用的求解NP-Hard問題的方法，如遺傳算法、蟻群算法、粒子群算法等，思路是隨機產(chǎn)生多個初始解，通過特殊的迭代尋優(yōu)規(guī)則進行優(yōu)化并更新狀態(tài)，到達一定迭代次數(shù)或者其他終止條件時結束。此類算法在應對大規(guī)模問題時往往求解時間短，一般均能得到一個較優(yōu)的可行解，確點是容易陷入局部最優(yōu)，無法得到最優(yōu)解，同時求解過程與問題高度相關，改變問題結構對算法影響很大，難以擴展。

4.仿真法

對于大型、復雜的選址問題，可通過仿真的方式重現(xiàn)系統(tǒng)活動。一般而言，采用仿真時需要對現(xiàn)實情況有較好的統(tǒng)計，獲取一些關鍵參數(shù)的統(tǒng)計分布，對實踐的要求較高。與其他方法相比，仿真方法對計算機的算力要求較小，不需要嚴格的編程。

4  悠樺林在倉儲選擇的實踐

4.1.倉儲資源規(guī)劃與布局項目

由于業(yè)務擴張需求，某公司希望在湖南省內(nèi)進一步優(yōu)化當前的供應鏈倉網(wǎng)布局: 其中幾個重要板塊包括如何在考慮現(xiàn)有銷售信息和倉儲布局下，增添新的前置倉庫以滿足業(yè)務的增長需求；如何根據(jù)歷史訂單數(shù)據(jù)/倉儲成本/運輸價格，尋找供應鏈成本最低模型與最優(yōu)庫存策略；如何基于當前倉網(wǎng)布局與其他可獲得信息周期性地預測庫存與峰值，并可視化，等等。在該項目中，悠樺林基于大規(guī)混合整數(shù)規(guī)劃模型，開發(fā)客戶可視化前端，力圖建立全面的倉網(wǎng)規(guī)劃能力，為倉儲網(wǎng)絡決策的科學性和精準性提供系統(tǒng)支持。

4.2.項目背景回顧

本文著重介紹其中的前置倉庫選址問題: 即如何在諸多條件約束下(具體參見下一節(jié))，選擇數(shù)量最少的新前置倉庫地址，以滿足對整個湖南省的門店的服務支持。同時輸出每個門店的具體地理位置。

4.3. 前置倉選址方案

該混合整數(shù)規(guī)劃的建模思想為2.4節(jié)的集合覆蓋模型的加強衍生升級版。這里主要想介紹的是這個項目所特有的若干約束項/前提條件，包括但不限制于

·  前置倉所選地址的最大范圍邊界(湖南省)

·  每個前置倉服務半徑為150KM的圓

·  一個門店僅能被一個前置倉服務且總覆蓋率至少達到95%

·  每個門店所需總量額的范圍上下限

同時設定成本系數(shù)，包括但不限制于

·  倉庫存儲成本

·  倉庫與門店間的運輸成本

優(yōu)化目標

·  最小化倉庫數(shù)量

輸出結果

·  倉庫數(shù)量與每個倉庫對應的地理位置

此外，悠樺林額外在這里為該公司提供了兩種可選約束條件下的優(yōu)化策略與結果：

·  所有客戶一視同仁，至少滿足95%客戶服務水平，此時優(yōu)化結果為11倉

·  更好的服務大客戶，至少滿足95%需求覆蓋率，此時優(yōu)化結果為8倉

最終，對比兩種優(yōu)化結果，第二種可選約束條件下總倉數(shù)更少且總距離最短，以下為兩種結果對比:

在該項目中，悠樺林基于大規(guī)模混合整數(shù)規(guī)劃模型，為該公司提供了最優(yōu)化的前置倉庫選址方案，同時為客戶提供了多種可選約束條件，與相應的不同種決策方案。以上倉庫選擇問題為悠樺林為該公司指定的供應鏈網(wǎng)絡全局規(guī)劃的一個重要環(huán)節(jié)，為全網(wǎng)布局預測與優(yōu)化提供輸入。

參考文獻：

Facility Location and Strategic Supply Chain Management, Prof. Dr. Stefan Nickel, 2008-2009