1、2022/8/17集美大學航海學院物流管理教研室物流系統規劃與設計第3章 選址模型及應用2022/8/17集美大學航海學院物流管理教研室本章基本要求 了解選址的影響因素，掌握選址中的距離計算，理解和掌握實際選址問題的分析、模型的構建和基本的求解算法。本章重點要求 掌握交叉中值模型、重心模型、覆蓋模型、P中值模型以及這些模型的應用。物流系統規劃與設計第3章 選址模型及應用2022/8/17集美大學航海學院物流管理教研室本章目錄3.1 選址的意義3.2 選址決策的影響因素3.3 選址模型的分類3.4 選址問題中的距離計算3.5 選址模型 3.5.1 連續點選址模型 3.5.2 離散點選址模型家樂福

2、選址實例剖析 本章小結物流系統規劃與設計第3章 選址模型及應用2022/8/17集美大學航海學院物流管理教研室3.1 選址的意義 選址在整個物流系統中占有非常重要的地位，從圖1-11，物流縱向結構圖看出，物流分為生產物流、商業物流、回歸物流三類。各類問題的特征各不相同，但每一類問題的不同環節都包含了選址問題，如供應商、制造商、分銷商、零售商的選址問題，由此說明了選址在整個物流系統中的重要性，屬于物流管理戰略層的研究問題，是物流系統規劃的一大內容。（該問題：小到倉庫中貨物存儲位置的分配）物流系統規劃與設計第3章 選址模型及應用2022/8/17集美大學航海學院物流管理教研室3.1 選址的意義選址

3、決策的內容：選址決策：確定物流系統中所要分配的設施（節點）的數量、位置以及分配方案（數學的方法）。（設施 節點）對單個企業，選址決定了整個物流系統及其他層次結構。所以，選址、庫存、運輸成本之間存在著密切聯系。如：企業分布問題（二維選址） 其他層次（庫存、運輸等）的規劃。 物流系統規劃與設計第3章 選址模型及應用2022/8/17集美大學航海學院物流管理教研室3.1 選址的意義選址與庫存、運輸成本之間的關系。降低成本的措施：合并減少設施數量，擴大設施規模是降低庫存成本的一個措施。確定設施的合理數量，也是選址規劃的主要任務之一。 物流系統規劃與設計第3章 選址模型及應用2022/8/17集美大學航

4、海學院物流管理教研室3.1 選址的意義選址與庫存、運輸成本之間的關系。 就供應鏈系統而言，核心企業的選址決策會影響所有供應商物流系統的選址決策。如DELL、摩托羅拉實例本章內容： 實際選址問題的分析、模型構建、求解算法。物流系統規劃與設計第3章 選址模型及應用2022/8/17集美大學航海學院物流管理教研室為什么目前我國很多城市熱衷于建物流園區、物流中心等大規模物流節點設施？ 物流系統規劃與設計討論2022/8/17集美大學航海學院物流管理教研室物流系統規劃與設計思考選址的影響因素有哪些？2022/8/17集美大學航海學院物流管理教研室3.2.1 選址決策的外部因素分析 宏觀政治、 經濟因素

5、政權、法制、貿易集運政策等 稅收政策、關稅、匯率等 是無法量化的指標, 與企業選址決策直接相關 由企業主觀評價 目標：尋求最寬松的經濟環境 基礎設施 及 環境 交通設施、通信設施等 自然環境、社會環境 降低物流成本 勞動力的成本、素質等物流系統規劃與設計3.2 選址決策的影響因素2022/8/17集美大學航海學院物流管理教研室3.2.1 選址決策的外部因素分析競爭對手競爭對手的布局情況、自身產品或服務 靠近還是遠離競爭對手 物流系統規劃與設計3.2 選址決策的影響因素2022/8/17集美大學航海學院物流管理教研室3.2.2 選址決策的內部因素分析 企業的內部因素是最主要的。選址決策首先要與企

6、業的發展戰略相適應。物流系統規劃與設計3.2 選址決策的影響因素2022/8/17集美大學航海學院物流管理教研室物流系統規劃與設計思考臺灣的鞋廠到晉江、莆田開店，而電子產品則不會的原因？2022/8/17集美大學航海學院物流管理教研室 選址模型：用數學方法確定設施的數量、位置和規模以使物流成本最小。 建選址模型前需弄清以下幾個問題：選址的對象？選址的目標區域？選址目標和成本函數？約束條件？ 選址問題 選址類型選址模型算法選址方案目前可將選址問題分為以下幾類： 物流系統規劃與設計3.3 選址模型的分類2022/8/17集美大學航海學院物流管理教研室3.3.1 根據定位設施的維數及數量分類根據設施

7、的維數體選址：定位三維物體，如：卡車、船舶的裝卸；面選址：定位二維物體，如：企業的部門布置；線選址：定位一維物體，如：配送中心分揀區傳送帶；點選址：定位零維物體，忽略物體的尺寸。 （大多數選址問題和算法都基于此情況）動態選址問題：+時間因素的四維選址問題。根據設施選址的數量：單一設施選址：主要考慮運輸成本多設施選址：運輸成本、競爭力、設施間需求的分配、設施成本與數量間的關系。物流系統規劃與設計3.3 選址模型的分類2022/8/17集美大學航海學院物流管理教研室3.3.2 據選址問題目標區域的特征分類連續選址 待選區域為平面，可選位置不限，選址模型為連續的。如：企業配送中心的初步選址。網格選址

8、 待選區域為平面網格區域候選地址有限（相當大）。 許多相等面積的區域，如正方形如:倉庫中不同貨物的存儲位置的分配或展覽中心展區的布置。離散選址（最切合實際） 待選區域是離散的候選位置集合，數量有限（甚少）。如：企業配送中心的詳細選址設計。 物流系統規劃與設計3.3 選址模型的分類2022/8/17集美大學航海學院物流管理教研室3.3.3 據選址成本分類 根據選址成本，有幾種類型：尋求可行成本方案或最優成本方案；尋求總成本最小或成本最大值的最小化；固定權重或可變權重；確定性的或隨機性的；被定位設施間有無相互聯系；靜態或是動態的選址問題。 可行性/最優性 即是尋求可行成本方案還是最優成本方案？對于

9、許多選址問題：第一目標：得到一個可行的解決方案，即滿足所有約束的解決方案；（多個）第二目標：找到一個更好的解決方案，即關于目標函數的優化。（一個）物流系統規劃與設計3.3 選址模型的分類2022/8/17集美大學航海學院物流管理教研室3.3.3 據選址成本分類 Minisum/Minimax/Maximin目標函數 Minisum目標函數問題：尋求整個設施選址的成本總和為最小。目標：優化全部或者平均性能。適用：企業問題。故稱“經濟效益性”或稱網絡上的中值問題。其中：X新的待定位設施物體的坐標； j已存在且位置固定的物體編號； 對于已經存在的物體j，新物體定位在X時的成本。 物流系統規劃與設計3

10、.3 選址模型的分類2022/8/17集美大學航海學院物流管理教研室3.3.3 據選址成本分類 Minisum/Minimax/Maximin目標函數 Minisum目標函數物流系統規劃與設計3.3 選址模型的分類2022/8/17集美大學航海學院物流管理教研室3.3.3 據選址成本分類 Minisum/Minimax/Maximin目標函數 Minimax目標函數問題：尋求已存在設施的單個成本最大的成本值為最小。目標：優化最壞的情況。適用：軍隊、緊急情況和公共部門。稱作“經濟平衡性”，也稱為網絡上的中心問題 （照顧到最邊遠的地區）（離客戶到最近的設施的成本“最大值”最小的原則） 物流系統規劃

11、與設計3.3 選址模型的分類2022/8/17集美大學航海學院物流管理教研室3.3.3 據選址成本分類 Minisum/Minimax/Maximin目標函數Maximin目標函數問題：尋求已存在設施的單個成本最小的成本值為最大。目標：使最壞的情況最優化。適用：有害設施（廢水處理廠、軍工廠等）的選址。此時，物體被定位在使最小距離最大化的地方。稱作“經濟平衡性”，也稱為網絡上的“反中心”問題。 物流系統規劃與設計3.3 選址模型的分類2022/8/17集美大學航海學院物流管理教研室3.3.3 據選址成本分類 Minisum/Minimax/Maximin目標函數例：設一直線上在0，5，6，7上有

12、4個點，成本與點到新設施間的距離成比例。注：中值點：minisum；中心點：minimax；反中心點：maximin物流系統規劃與設計3.3 選址模型的分類2022/8/17集美大學航海學院物流管理教研室 Minisum/Minimax/Maximin目標函數Minisum. 中值點 （成本只與距離有關） 解：設新點設在x，則： 當 時，當 時，當 時， 的x的取值為注:在選址的左右側有同樣多的點。5和6間的點均為中值位置。物流系統規劃與設計3.3 選址模型的分類2022/8/17集美大學航海學院物流管理教研室3.3.3 據選址成本分類 Minisum/Minimax/Maximin目標函數

13、Minimax 中心點 ， ，選址位置到最左邊點和到最右邊點的距離是相等的。 （中心點唯一）物流系統規劃與設計3.3 選址模型的分類2022/8/17集美大學航海學院物流管理教研室3.3.3 據選址成本分類 Minisum/Minimax/Maximin目標函數擴展：若 ， 不變。（中值點左右側各點的實際位置不重要，只要兩側點的數目相同。）若在 、 之間增加1000個點， 不變。（中心選址是由那些極端位置決定的，即最左和最右兩點的中心。） 1）中值選址由固定位置的順序決定，非實際位置。 2）中心選址由那些極端位置決定，與內部位置無關。 物流系統規劃與設計3.3 選址模型的分類2022/8/17

14、集美大學航海學院物流管理教研室3.3.3 據選址成本分類 Minisum/Minimax/Maximin目標函數 Maximin ： 反中心點當 物流系統規劃與設計3.3 選址模型的分類2022/8/17集美大學航海學院物流管理教研室 Minisum/Minimax/Maximin目標函數 Maximin ： 反中心點當選址位置為相鄰間距離最大兩點的中點。（反中心點唯一） 3）反中心選址由相鄰間距離最大的位置決定。 物流系統規劃與設計3.3 選址模型的分類2022/8/17集美大學航海學院物流管理教研室物流系統規劃與設計討論建急救中心宜選用哪類選址目標函數？建垃圾清潔樓宜選用哪類選址目標函數？

15、建物流配送中心宜選用哪類選址目標函數？2022/8/17集美大學航海學院物流管理教研室3.3.3 據選址成本分類3. 固定權重與可變權重 單純選址問題（固定權重）： 新設施和已存在設施間的關系與新設施的位置無關,是固定的 選址分配問題（可變權重）： 這種權重或關系與新設施的位置相關。4. 被定位設施間有無相互聯系（一次or二次）（多設施選址）一次目標函數：無二次或高次目標函數：有物流系統規劃與設計3.3 選址模型的分類2022/8/17集美大學航海學院物流管理教研室3.3.3 據選址成本分類5. 確定性與隨機性確定性：選址的成本或參數值是確定的。隨機性：選址的成本或參數是一個隨機分布的概率值。

16、 （如：客戶需求）6. 靜態與動態 成本或參數是否隨時間變化。 物流系統規劃與設計3.3 選址模型的分類2022/8/17集美大學航海學院物流管理教研室3.3.4 選址約束1有能力約束與無能力約束：新設施的能力有否被限制。2不可行區域約束：在目標區域內有（無）不適合作為選址地點的區域。物流系統規劃與設計3.3 選址模型的分類2022/8/17集美大學航海學院物流管理教研室3.4.1 直線距離（歐幾里得距離） 適用：大范圍的選址問題，城市間配送問題和通信問題。 實際路線距離 （如在美國大陸 ， 在東南美洲 ） 分形理論物流系統規劃與設計3.4 選址問題中的距離計算2022/8/17集美大學航海學

17、院物流管理教研室3.4.2 折線距離（城市距離）適用：城市(道路較規則的)內的配送問題，具有直線通道的工廠及倉庫內的布置、物料搬運設備的順序移動等問題。 物流系統規劃與設計3.4 選址問題中的距離計算2022/8/17集美大學航海學院物流管理教研室選址模型的功能：選址定位：為設施找到一個最優的位置；系統設計：是物流系統設計中的一個重要部分。*直線型設施選址模型：單距離因素情況：街上各個位置可能出現顧客的概率相同，取中心點。目標：所有顧客到達新設施點的平均距離最小。（單點選址，minisum型，中值解。）加權重的離散模型：街上各個位置可能出現顧客的概率不一樣目標：到目標點的絕對距離的總和最小。（

18、單點選址，minisum型，中值解。）物流系統規劃與設計3.5 選址模型2022/8/17集美大學航海學院物流管理教研室加權重的離散模型：其中： 第i個位置的權重； 第i個位置的坐標； 新設施選址的坐標。物流系統規劃與設計3.5 選址模型2022/8/17集美大學航海學院物流管理教研室加權重的離散模型：求解： ( 的左、右側權重相等。)物流系統規劃與設計3.5 選址模型2022/8/17集美大學航海學院物流管理教研室加權重的連續模型：（屬minisum解，即中值解） 物流系統規劃與設計3.5 選址模型2022/8/17集美大學航海學院物流管理教研室加權重的連續模型：（屬minisum解，即中值

19、解）求解： （s兩邊的權重都是50%，即權重的中點。） 物流系統規劃與設計3.5 選址模型2022/8/17集美大學航海學院物流管理教研室3.5.1 連續點選址模型 （在一條路徑或一個區域內，無不可行區域）1. 交叉中值模型 （x，y方向的中值點）距離：城市距離（折線距離）類型：單一選址問題目標：加權的城市距離總和最?。傎M用最小）。適用：小范圍的城市內的選址問題。 物流系統規劃與設計3.5 選址模型2022/8/17集美大學航海學院物流管理教研室3.5.1 連續點選址模型 交叉中值模型其中： 與第i點相對應的權重； 第i個需求點的坐標； 新設施點的坐標； n需求點的總數目。求解： 是在x方向

20、對所有權重 的中值點； 是在y方向對所有權重 的中值點。最優解：可能是一個點，或是線，或是一個區域。 物流系統規劃與設計3.5 選址模型2022/8/17集美大學航海學院物流管理教研室3.5.1 連續點選址模型 交叉中值模型例1：報刊亭選址。物流系統規劃與設計3.5 選址模型2022/8/17集美大學航海學院物流管理教研室3.5.1 連續點選址模型 交叉中值模型例1：報刊亭選址。 ：第個月潛在的顧客需求總量，近似為i區中的總的居民數量或戶數。問題（目標）：每個月顧客到報刊點所走距離的總和為最小。解：模型選擇：城市距離，交叉中值選址方法。確定中值：物流系統規劃與設計3.5 選址模型2022/8/

21、17集美大學航海學院物流管理教研室3.5.1 連續點選址模型 交叉中值模型:例1：報刊亭選址。求 , ：在x方向：左右： 右左：物流系統規劃與設計3.5 選址模型2022/8/17集美大學航海學院物流管理教研室3.5.1 連續點選址模型 交叉中值模型:例1：報刊亭選址。在y方向：上下： （ ， ， 即 ） 下上： （ ， ， 即 ） 最優解為AB （A=(3,3), B=(4,3)） 物流系統規劃與設計3.5 選址模型2022/8/17集美大學航海學院物流管理教研室3.5.1 連續點選址模型 交叉中值模型:例1：報刊亭選址。比較A，B兩個位置的加權距離；A： B： 根據實際情況，選址為A、B之

22、間的任何一點。 (交叉中值法可為決策提供更多的選擇和靈活性。)作業：P58 習題2-7，1物流系統規劃與設計3.5 選址模型2022/8/17集美大學航海學院物流管理教研室3.5.1 連續點選址模型2. 精確重心法距離：直線距離類型：單點的選址問題問題（目標）：尋求加權的直線距離總和最小（總費用最?。?。適用：平面上大范圍的選址，無受限區域。 （連續區域、直線距離的單點選址） （最優解唯一）其中：各變量的含義同交叉中值模型。 物流系統規劃與設計3.5 選址模型2022/8/17集美大學航海學院物流管理教研室3.5.1 連續點選址模型2. 精確重心法求解：其中： (含xs,ys,無法一次求得顯式解

23、)只能用迭代的方法對上式求近似解。 物流系統規劃與設計3.5 選址模型2022/8/17集美大學航海學院物流管理教研室3.5.1 連續點選址模型2. 精確重心法求解：迭代公式： （j為迭代次數） 其中：應用上述迭代公式，可采用逐步逼近算法求得最優解。物流系統規劃與設計3.5 選址模型2022/8/17集美大學航海學院物流管理教研室3.5.1 連續點選址模型2. 精確重心法求解：算法（單一選址的不動點算法）：輸入：n客戶數； 各客戶點的坐標， ； 各客戶點對應的權重， ;(包括運費和運量)輸出： 設施坐標； Z總運費。步驟：選取初始迭代點 ，如： ，或以交叉中值模型選址的結果之一作為 。物流系統

24、規劃與設計3.5 選址模型2022/8/17集美大學航海學院物流管理教研室3.5.1 連續點選址模型2. 精確重心法求解：算法（單一選址的不動點算法）：計算A到各客戶點的直線距離 和 ： 物流系統規劃與設計3.5 選址模型2022/8/17集美大學航海學院物流管理教研室3.5.1 連續點選址模型2. 精確重心法求解：算法（單一選址的不動點算法）：令 計算：物流系統規劃與設計3.5 選址模型2022/8/17集美大學航海學院物流管理教研室3.5.1 連續點選址模型2. 精確重心法求解：算法（單一選址的不動點算法）：若 ，運費已無法減小；輸出最優解 、Z和迭代次數j，結束。 ， ， （可能迭代無限

25、次）否則，轉注1：若工廠到設施的運費包含在成本中，則可將工廠視為一個客戶點Pi；注2：若直線距離與實際距離有差異，可用一定的修正系數 來修正差異。 物流系統規劃與設計3.5 選址模型2022/8/17集美大學航海學院物流管理教研室3.5.1 連續點選址模型2. 精確重心法求解：算法（單一選址的不動點算法）：終止準則：(1)根據經驗和以前的試驗結果，設置迭代次數N； 若jN, 則輸出 和Z，結束。否則，轉。(2)取閾值 ， （較合理，常用）若則迭代過程結束。 若 ， 則輸出 、Z和迭代次數j，結束；否則，轉(3)求得最優解。不動點算法步驟。物流系統規劃與設計3.5 選址模型2022/8/17集美

26、大學航海學院物流管理教研室3.5.1 連續點選址模型2. 精確重心法例1：取 ， （即A(3,3)開始）則 物流系統規劃與設計3.5 選址模型2022/8/17集美大學航海學院物流管理教研室3.5.1 連續點選址模型2. 精確重心法例1：物流系統規劃與設計3.5 選址模型2022/8/17集美大學航海學院物流管理教研室3.5.1 連續點選址模型2. 精確重心法例1：取 ， 則 ， ， （選 or ，由Z決定。)注：精確重心法得到的最優解只有一個點，且交叉中值法和精確重心法得到的最優解一般不一致。作業：P58 習題2-7，2(用歐幾米得距離計算時取初值點(7,7),閾值0.15)物流系統規劃與設

27、計3.5 選址模型2022/8/17集美大學航海學院物流管理教研室3.5.2 離散點選址模型離散點選址問題：在有限的候選位置里，選取最為合適的一個或一組位置為最優方案，相應的模型叫離散點選址模型。1.覆蓋模型問題：對于需求已知的一些需求點，如何確定一組服務設施來滿足這些需求點的需求。在該模型中，需要確定服務設施的最小數量和合適的位置。適用范圍：商業物流系統：零售點、加油站或配送中心等的選址。公用事業系統：急救中心、預防中心等的選址。計算機與通信系統：有線電視網的基站、無線通信網絡基站、計算機網絡中的集線器設置等。 物流系統規劃與設計3.5 選址模型2022/8/17集美大學航海學院物流管理教研

28、室3.5.2 離散點選址模型1）集合覆蓋模型 （由解決問題的方法不同分為兩種。）(1)問題:已知需求點的位置、需求量和候選點的位置，求滿足各需求點的服務需求的條件下，使所投建的設施點的數目為最小。目標:用最小數量的設施去覆蓋所有需求點。(覆蓋全部需求點)(2)模型： (教材上：M=N) (各需求點的需求得到100%的滿足) (各設施點服務能力的限制) (一個地方最多只能建一個設施) (允許一個設施只提供部分需求)物流系統規劃與設計3.5 選址模型2022/8/17集美大學航海學院物流管理教研室3.5.2 離散點選址模型 1）集合覆蓋模型其中： N需求點的集合， ； M可建設施的候選點集合， ；

29、 第i個需求點的需求量； 設施節點j的容量； A(j) 設施節點j所覆蓋的需求節點i的集合； （候選設施點j覆蓋的需求點集。） B(i)可以覆蓋需求點i的設施節點j的集合； （覆蓋i的候選設施點集。） xj yij節點i需求中被分配給節點j的部分。物流系統規劃與設計3.5 選址模型2022/8/17集美大學航海學院物流管理教研室3.5.2 離散點選址模型 1）集合覆蓋模型（3）求解： 精確算法：規模較小時可用分枝定界求解法（整數規劃中的一個重要解法）求模型的最優解，但運算量很大； 近似算法：實際問題中，n和m一般較大（也可能n=m），故需設計近似算法來求解。啟發式方法。（結果為可行解。）集合覆

30、蓋啟發式算法步驟： （該算法最常用，也最簡單。）確定A(j)，B(i)；簡化問題。若A(j1) A(j2)，則省去A(j1)，即匆略j1作為候選點，M=M-j1，最后得M* 確定合適的組合解。 物流系統規劃與設計3.5 選址模型2022/8/17集美大學航海學院物流管理教研室3.5.2 離散點選址模型 1）集合覆蓋模型例2鄉村醫療診所選址問題：問題：如圖9個村，希望在每一個村周邊30km內至少有一個診所，不考慮診所服務能力的限制。除第6村外，其他村均可作為候選點。 物流系統規劃與設計3.5 選址模型2022/8/17集美大學航海學院物流管理教研室3.5.2 離散點選址模型 1）集合覆蓋模型解：

31、求A(j)，B(i)， ， ， （候選點j覆蓋的需求點集合） （覆蓋i的候選點集合）簡化問題：若A(j1) A(j2)，則省去A(j1)，即忽略在j1村建，其提供的可能服務已含在j2村的范圍。物流系統規劃與設計3.5 選址模型2022/8/17集美大學航海學院物流管理教研室3.5.2 離散點選址模型 1）集合覆蓋模型 （盡可能少地建設施。） 物流系統規劃與設計3.5 選址模型8,9（8,9）97,8,96,7,8,984,7,84,6,7,874,5,7,863,4,5（3,4,5,6）51,3,4,5,71,3,4,5,6,741,2,3,4,51,2,3,4,531,2,3(1,2,3)2

32、1,2,3,4(1,2,3,4)1村編號2022/8/17集美大學航海學院物流管理教研室3.5.2 離散點選址模型 1）集合覆蓋模型 確定合適的組合解?？尚薪猓?,4,7,8、3,4,8、3,8最優解：3,83,4,7,8中，2唯一A(3)，9唯一A(8)，且A(3)A(8)覆蓋全部需求點，即N-A(3)A(8)=。 （若N-A(3)A(8)，再用唯一的方法找。） 物流系統規劃與設計3.5 選址模型2022/8/17集美大學航海學院物流管理教研室3.5.2 離散點選址模型 1）集合覆蓋模型擴展解題算法思路： （貪婪法，一般只得到可行解。）如： ，保留 ，省去 的子集，得A(4)，對N-A(4)

33、=2,8,9中的每個i，尋找包含i的最大的 =A(8)，并省去 的子集A(9)， ，得：4,8,2or 4,8,3*or 4,8,1物流系統規劃與設計3.5 選址模型2022/8/17集美大學航海學院物流管理教研室3.5.2 離散點選址模型 2）最大覆蓋模型（1）問題：已知需求點的位置和需求量，候選點的位置和所建設施的數量中p，選擇p個設施位置，使盡可能多地滿足需求點的服務。目標：對有限的服務網點進行選址，為盡可能多的對象提供服務。（2）建立模型 (最大可能地滿足需求). (i需求的滿足不超過100%) (服務能力的限制) 物流系統規劃與設計3.5 選址模型2022/8/17集美大學航海學院物

34、流管理教研室3.5.2 離散點選址模型 2）最大覆蓋模型 (最多建p個設施) (一處最多建一個設施) (允許一個設施只提供部分需求)其中：N ，需求點集； （i） M ，可建設施的候選點集； （j）物流系統規劃與設計3.5 選址模型2022/8/17集美大學航海學院物流管理教研室3.5.2 離散點選址模型 2）最大覆蓋模型 di第i個需求點的需求量； Cj j設施節點的相應容量； A(j) 設施節點j所覆蓋的需求點i的集合； B(i)可以覆蓋需求點i的設施節點j的集合； p允許投建的設施數目； xj yij 節點i需求中被分配給節點j的部分。 物流系統規劃與設計3.5 選址模型2022/8/1

35、7集美大學航海學院物流管理教研室3.5.2 離散點選址模型 2）最大覆蓋模型（3）模型的求解貪婪算法（近似算法）貪婪方法：逐步構造最優解的方法。每一步都在一定的準則下作出最優的決策，決策一旦作出，就不可更改。作出貪婪決策的依據稱為貪婪準則。步驟：設解集 ， ；若 ， 點設施具有最大的滿足能力，則 ， ；若|S|=p或全部需求得到滿足，結束。否則，轉。物流系統規劃與設計3.5 選址模型2022/8/17集美大學航海學院物流管理教研室3.5.2 離散點選址模型 2）最大覆蓋模型例2 建醫療站問題,仍不考慮服務能力的限制。P=2解： ,由前得 ,結束。注：第2個需求點沒覆蓋。（由最大覆蓋法得到的解集

36、非最優解，此仍啟發式算法的特點。）物流系統規劃與設計3.5 選址模型2022/8/17集美大學航海學院物流管理教研室3.5.2 離散點選址模型 2P中值模型（1）問題：已知數量和位置的需求集合，候選設施位置集合，分別為p個設施選址，并指派每一需求點到一個特定的設施，使之達到在設施和需求點之間的運輸費用最低。目標：p個設施選址并確定各設施的服務對象，使總運輸成本最少。（適用于工廠、倉庫或配送中心的選址。）物流系統規劃與設計3.5 選址模型2022/8/17集美大學航海學院物流管理教研室3.5.2 離散點選址模型 2P中值模型（2）建立模型 . (客戶的需求獲得100%的滿足) (投建的總設施數為

37、p) (無設施的點無客戶對應)物流系統規劃與設計3.5 選址模型2022/8/17集美大學航海學院物流管理教研室3.5.2 離散點選址模型 2P中值模型（2）建立模型 (一處最多建一個設施) (一客戶只由一設施服務)其中：N，M，di，p，xj同前；Cij從點i到點j的單位運輸費用；yij物流系統規劃與設計3.5 選址模型2022/8/17集美大學航海學院物流管理教研室3.5.2 離散點選址模型 2P中值模型（3）模型的求解：求解P中值模型需解決兩方面問題：選擇合適的設施位置（x變量）； （總費用最小。）指派客戶到相應的設施中去。求解方法：精確計算法（只能求解規模較小的P中值問題）；啟發式算法

38、。物流系統規劃與設計3.5 選址模型2022/8/17集美大學航海學院物流管理教研室3.5.2 離散點選址模型 2P中值模型 （3）模型的求解：貪婪取走啟發式算法：令當前選中設施點數k=m； (即將所有m個候選位置都選中)將每個客戶指派給(k個設施中)離其最近的設施點，求出總運費Z； 若k=p,輸出k個設施點及各客戶的指派結果,結束;否則,轉;從k個候選點中確定一個取走點，滿足：若將它取走并將它的客戶重新指派后，總費用增加量最小。從候選點集中刪去取走點，令k:=k-1，轉。 物流系統規劃與設計3.5 選址模型2022/8/17集美大學航海學院物流管理教研室3.5.2 離散點選址模型例3：某飲料公司的倉庫選址問題。N=8，m=4，p=2 目標