物流系統(tǒng)規(guī)劃與設計-選址模型及應用課件

本章基本要求了解選址的影響因素，掌握選址中的距離計算，理解和掌握實際選址問題的分析、模型的構建和基本的求解算法。本章重點要求掌握交叉中值模型、重心模型、覆蓋模型、P——中值模型以及這些模型的應用。第3章 選址模型及應用2023/9/201集美大學航海學院物流管理教研室本章目錄選址的意義選址決策的影響因素選址模型的分類選址問題中的距離計算選址模型連續(xù)點選址模型離散點選址模型家樂福選址實例剖析本章小結第3章 選址模型及應用2023/9/202集美大學航海學院物流管理教研室3.1

選址的意義選址在整個物流系統(tǒng)中占有非常重要的地位，從圖1-11，物流縱向結構圖看出，物流分為生產(chǎn)物流、商業(yè)物流、回歸物流三類。各類問題的特征各不相同，但每一類問題的不同環(huán)節(jié)都包含了選址問題，如供應商、制造商、分銷商、零售商的選

址問題，由此說明了選址在整個物流系統(tǒng)中的重要性，屬于物流管理戰(zhàn)略層的研究問題，是物流系統(tǒng)規(guī)劃的一大內(nèi)容。（該問題：小到倉庫中貨物存儲位置的分配）第3章 選址模型及應用2023/9/203集美大學航海學院物流管理教研室3.1

選址的意義⒈選址決策的內(nèi)容：選址決策：確定物流系統(tǒng)中所要分配的設施（節(jié)點）的數(shù)量、

位置以及分配方案（數(shù)學的方法）。（設施 節(jié)點）對單個企業(yè)，選址決定了整個物流系統(tǒng)及其他層次結構。所以，選址、庫存、運輸成本之間存在著密切聯(lián)系。如：企業(yè)分布問

題（二維選址） 其他層次（庫存、運輸?shù)龋┑囊?guī)劃。第3章 選址模型及應用2023/10/14集美大學航海學院物流管理教研室3.1

選址的意義⒉選址與庫存、運輸成本之間的關系。降低成本的措施：①合并減少設施數(shù)量，擴大設施規(guī)模是降低庫存成本的一個措施。②確定設施的合理數(shù)量，也是選址規(guī)劃的主要任務之一。第3章 選址模型及應用2023/10/15集美大學航海學院物流管理教研室3.1

選址的意義⒉選址與庫存、運輸成本之間的關系。就供應鏈系統(tǒng)而言，核心企業(yè)的選址決策會影響所有供應商物流系統(tǒng)的選址決策。如DELL、摩托羅拉實例本章內(nèi)容：實際選址問題的分析、模型構建、求解算法。第3章 選址模型及應用2023/10/16集美大學航海學院物流管理教研室

為什么目前我國很多城市熱衷于建物流園區(qū)、物流中心等大規(guī)模物流節(jié)點設施？討論2023/10/17集美大學航海學院物流管理教研室思考選址的影響因素有哪些？？2023/10/18集美大學航海學院物流管理教研室3.2.1

選址決策的外部因素分析⒈ 宏觀政治、 經(jīng)濟因素↓政權、法制、貿(mào)易集運政策等↘稅收政策、關稅、匯率等↓是無法量化的指標,由企業(yè)主觀評價↓與企業(yè)選址決策直接相關

目標：尋求最寬松的經(jīng)濟環(huán)境⒉基礎設施

及↓交通設施、通信設施等環(huán)境↘自然環(huán)境、社會環(huán)境↓降低物流成本↓勞動力的成本、素質等3.2

選址決策的影響因素2023/10/19集美大學航海學院物流管理教研室3.2.1

選址決策的外部因素分析⒊競爭對手競爭對手的布局情況、自身產(chǎn)品或服務↘

↙靠近還是遠離競爭對手3.2

選址決策的影響因素2023/10/110集美大學航海學院物流管理教研室3.2.2

選址決策的內(nèi)部因素分析企業(yè)的內(nèi)部因素是最主要的。選址決策首先要與企業(yè)的發(fā)展戰(zhàn)略相適應。3.2

選址決策的影響因素2023/10/111集美大學航海學院物流管理教研室思考臺灣的鞋廠到晉江、莆田開店，而電子產(chǎn)品則不會的原因？？2023/10/112集美大學航海學院物流管理教研室選址模型：用數(shù)學方法確定設施的數(shù)量、位置和規(guī)模以使物流成本最小。建選址模型前需弄清以下幾個問題：①選址的對象？②選址的目標區(qū)域？③選址目標和成本函數(shù)？④約束條件？①②③④選址問題 選址類型→選址模型→算法→選址方案目前可將選址問題分為以下幾類：3.3

選址模型的分類2023/10/113集美大學航海學院物流管理教研室3.3.1

根據(jù)定位設施的維數(shù)及數(shù)量分類⒈根據(jù)設施的維數(shù)體選址：定位三維物體，如：卡車、船舶的裝卸；面選址：定位二維物體，如：企業(yè)的部門布置；線選址：定位一維物體，如：配送中心分揀區(qū)傳送帶；點選址：定位零維物體，忽略物體的尺寸。（大多數(shù)選址問題和算法都基于此情況）動態(tài)選址問題：+時間因素的四維選址問題。⒉根據(jù)設施選址的數(shù)量：單一設施選址：主要考慮運輸成本多設施選址：運輸成本、競爭力、設施間需求的分配、設施成本與數(shù)量間的關系。3.3

選址模型的分類2023/10/114集美大學航海學院物流管理教研室3.3.2

據(jù)選址問題目標區(qū)域的特征分類⒈連續(xù)選址待選區(qū)域為平面，可選位置不限，選址模型為連續(xù)的。如：企業(yè)配送中心的初步選址。⒉網(wǎng)格選址待選區(qū)域為平面網(wǎng)格區(qū)域候選地址有限（相當大）。↓許多相等面積的區(qū)域，如正方形如:倉庫中不同貨物的存儲位置的分配或展覽中心展區(qū)的布置。⒊離散選址（最切合實際）待選區(qū)域是離散的候選位置集合，數(shù)量有限（甚少）。如：企業(yè)配送中心的詳細選址設計。3.3

選址模型的分類2023/10/115集美大學航海學院物流管理教研室3.3.3

據(jù)選址成本分類根據(jù)選址成本，有幾種類型：尋求可行成本方案或最優(yōu)成本方案；尋求總成本最小或成本最大值的最小化；固定權重或可變權重；確定性的或隨機性的；被定位設施間有無相互聯(lián)系；靜態(tài)或是動態(tài)的選址問題。⒈

可行性/最優(yōu)性即是尋求可行成本方案還是最優(yōu)成本方案？對于許多選址問題：第一目標：得到一個可行的解決方案，即滿足所有約束的解決方案；（多個）第二目標：找到一個更好的解決方案，即關于目標函數(shù)的優(yōu)化。（一個）3.3

選址模型的分類2023/10/116集美大學航海學院物流管理教研室；3.3.3

據(jù)選址成本分類⒉

Minisum/Minimax/Maximin目標函數(shù)①

Minisum目標函數(shù)問題：尋求整個設施選址的成本總和為最小。

目標：優(yōu)化全部或者平均性能。適用：企業(yè)問題。故稱“經(jīng)濟效益性”或稱網(wǎng)絡上的中值問題。其中：X——新的待定位設施物體的坐標

j——已存在且位置固定的物體編號；——對于已經(jīng)存在的物體j，新物體定位在X時的成本。3.3

選址模型的分類2023/10/117集美大學航海學院物流管理教研室3.3.3

據(jù)選址成本分類⒉

Minisum/Minimax/Maximin目標函數(shù)①

Minisum目標函數(shù)3.3

選址模型的分類2023/10/118集美大學航海學院物流管理教研室3.3.3

據(jù)選址成本分類⒉

Minisum/Minimax/Maximin目標函數(shù)②

Minimax目標函數(shù)問題：尋求已存在設施的單個成本最大的成本值為最小。

目標：優(yōu)化最壞的情況。適用：軍隊、緊急情況和公共部門。稱作“經(jīng)濟平衡性”，也稱為網(wǎng)絡上的中心問題 （照顧到最邊遠的地區(qū)）（離客戶到最近的設施的成本“最大值”最小的原則）3.3

選址模型的分類2023/10/119集美大學航海學院物流管理教研室3.3.3

據(jù)選址成本分類⒉

Minisum/Minimax/Maximin目標函數(shù)③Maximin目標函數(shù)問題：尋求已存在設施的單個成本最小的成本值為最大。

目標：使最壞的情況最優(yōu)化。適用：有害設施（廢水處理廠、軍工廠等）的選址。此時，物體被定位在使最小距離最大化的地方。稱作“經(jīng)濟平衡性”，也稱為

網(wǎng)絡上的“反中心”問題。3.3

選址模型的分類2023/10/120集美大學航海學院物流管理教研室3.3.3

據(jù)選址成本分類⒉

Minisum/Minimax/Maximin目標函數(shù)例：設一直線上在0，5，6，7上有4個點，成本與點到新設施間的距離成比例。注：中值點：minisum；中心點：minimax；反中心點：maximin3.3

選址模型的分類2023/10/121集美大學航海學院物流管理教研室⒉

Minisum/Minimax/Maximin目標函數(shù)①Minisum.

——中值點 （成本只與距離有關）

解：設新點設在x，則：當 時，當 時，當 時，∴ 的x的取值為注:在選址的左右側有同樣多的點。5和6間的點均為中值位置。3.3

選址模型的分類2023/10/122集美大學航海學院物流管理教研室3.3.3

據(jù)選址成本分類⒉

Minisum/Minimax/Maximin目標函數(shù)②

Minimax

——中心點，，∴——選址位置到最左邊點和到最右邊點的距離是相等的。（中心點唯一）3.3

選址模型的分類2023/10/123集美大學航海學院物流管理教研室3.3.3

據(jù)選址成本分類⒉

Minisum/Minimax/Maximin目標函數(shù)擴展：若

， 不變。（中值點左右側各點的實際位置不重要，只要兩側點的數(shù)目相同。）若在

、 之間增加1000個點， 不變。（中心選址是由那些極端位置決定的，即最左和最右兩點的中心。）中值選址由固定位置的順序決定，非實際位置。中心選址由那些極端位置決定，與內(nèi)部位置無關。3.3

選址模型的分類2023/10/124集美大學航海學院物流管理教研室3.3.3

據(jù)選址成本分類⒉

Minisum/Minimax/Maximin目標函數(shù)③

Maximin

：

——反中心點當3.3

選址模型的分類2023/10/125集美大學航海學院物流管理教研室⒉

Minisum/Minimax/Maximin目標函數(shù)③

Maximin

：

——反中心點

當——選址位置為相鄰間距離最大兩點的中點。（反中心點唯一）3）反中心選址由相鄰間距離最大的位置決定。3.3

選址模型的分類2023/10/126集美大學航海學院物流管理教研室討論2023/10/127集美大學航海學院物流管理教研室

建急救中心宜選用哪類

選址目標函數(shù)？

建垃圾清潔樓宜選用哪類選址目標函數(shù)？

建物流配送中心宜選用哪類選址目標函數(shù)？3.3.3

據(jù)選址成本分類固定權重與可變權重① 單純選址問題（固定權重）：新設施和已存在設施間的關系與新設施的位置無關,是固定的② 選址——分配問題（可變權重）：這種權重或關系與新設施的位置相關。被定位設施間有無相互聯(lián)系（一次or二次）（多設施選址）①一次目標函數(shù)：無②二次或高次目標函數(shù)：有3.3

選址模型的分類2023/10/128集美大學航海學院物流管理教研室3.3.3

據(jù)選址成本分類確定性與隨機性①確定性：選址的成本或參數(shù)值是確定的。②隨機性：選址的成本或參數(shù)是一個隨機分布的概率值。（如：客戶需求）靜態(tài)與動態(tài)成本或參數(shù)是否隨時間變化。3.3

選址模型的分類2023/10/129集美大學航海學院物流管理教研室3.3.4

選址約束1．有能力約束與無能力約束：新設施的能力有否被限制。

2．不可行區(qū)域約束：在目標區(qū)域內(nèi)有（無）不適合作為選址地點的區(qū)域。3.3

選址模型的分類2023/10/130集美大學航海學院物流管理教研室3.4.1 直線距離（歐幾里得距離）適用：大范圍的選址問題，城市間配送問題和通信問題。↓實際路線距離 （如在美國大陸

，在東南美洲 ）

——分形理論3.4

選址問題中的距離計算2023/10/131集美大學航海學院物流管理教研室3.4.2 折線距離（城市距離）適用：城市(道路較規(guī)則的)內(nèi)的配送問題，具有直線通道的工廠

及倉庫內(nèi)的布置、物料搬運設備的順序移動等問題。3.4

選址問題中的距離計算2023/10/132集美大學航海學院物流管理教研室選址模型的功能：①選址定位：為設施找到一個最優(yōu)的位置；②系統(tǒng)設計：是物流系統(tǒng)設計中的一個重要部分。*直線型設施選址模型：①單距離因素情況：街上各個位置可能出現(xiàn)顧客的概率相同，取中心點。目標：所有顧客到達新設施點的平均距離最小。（單點選址，minisum型，中值解。）②加權重的離散模型：街上各個位置可能出現(xiàn)顧客的概率不一樣目標：到目標點的絕對距離的總和最小。（單點選址，minisum型，中值解。）3.5

選址模型2023/10/133集美大學航海學院物流管理教研室②加權重的離散模型：其中：——第i個位置的權重；——第i個位置的坐標；——新設施選址的坐標。3.5

選址模型2023/10/134集美大學航海學院物流管理教研室②加權重的離散模型：求解：( 的左、右側權重相等。)3.5

選址模型2023/10/135集美大學航海學院物流管理教研室③加權重的連續(xù)模型：（屬minisum解，即中值解）3.5

選址模型2023/10/136集美大學航海學院物流管理教研室③加權重的連續(xù)模型：（屬minisum解，即中值解）

求解：（s兩邊的權重都是50%，即權重的中點。）3.5

選址模型2023/10/137集美大學航海學院物流管理教研室3.5.1

連續(xù)點選址模型（在一條路徑或一個區(qū)域內(nèi)，無不可行區(qū)域）1. 交叉中值模型

（x，y方向的中值點）

距離：城市距離（折線距離）類型：單一選址問題目標：加權的城市距離總和最?。傎M用最?。?。適用：小范圍的城市內(nèi)的選址問題。3.5

選址模型2023/10/138集美大學航海學院物流管理教研室3.5.1

連續(xù)點選址模型1.

交叉中值模型其中：

——與第i點相對應的權重；——第i個需求點的坐標；——新設施點的坐標；

n——需求點的總數(shù)目。求解：是在x方向對所有權重

是在y方向對所有權重的中值點；的中值點。最優(yōu)解：可能是一個點，或是線，或是一個區(qū)域。3.5

選址模型2023/10/139集美大學航海學院物流管理教研室3.5.1

連續(xù)點選址模型1.

交叉中值模型

例1：報刊亭選址。3.5

選址模型2023/10/140集美大學航海學院物流管理教研室3.5.1

連續(xù)點選址模型1.

交叉中值模型

例

1：

報刊亭選址。：第個月潛在的顧客需求總量，近似為i區(qū)中的總的居民數(shù)量或戶數(shù)。問題（目標）：每個月顧客到報刊點所走距離的總和為最小。

解：①模型選擇：城市距離，交叉中值選址方法。②確定中值：3.5

選址模型2023/10/141集美大學航海學院物流管理教研室3.5.1

連續(xù)點選址模型1.

交叉中值模型:例1：報刊亭選址。③求

,

：在x方向：左→右：右→左：3.5

選址模型2023/10/142集美大學航海學院物流管理教研室，，，，3.5.1

連續(xù)點選址模型1.

交叉中值模型:例1：報刊亭選址。在y方向：上→下：

（即

）下→上：

（即

）最優(yōu)解為AB（A=(3,3),

B=(4,3)）3.5

選址模型2023/10/143集美大學航海學院物流管理教研室3.5.1

連續(xù)點選址模型1.

交叉中值模型:例1：報刊亭選址。比較A，B兩個位置的加權距離；A：B：根據(jù)實際情況，選址為A、B之間的任何一點。(交叉中值法可為決策提供更多的選擇和靈活性。)作業(yè)：P58 習題2-7，13.5

選址模型2023/10/144集美大學航海學院物流管理教研室3.5.1

連續(xù)點選址模型2.

精確重心法距離：直線距離類型：單點的選址問題問題（目標）：尋求加權的直線距離總和最?。傎M用最小）。適用：平面上大范圍的選址，無受限區(qū)域。（連續(xù)區(qū)域、直線距離的單點選址）（最優(yōu)解唯一）其中：各變量的含義同交叉中值模型。3.5

選址模型2023/10/145集美大學航海學院物流管理教研室3.5.1

連續(xù)點選址模型2.

精確重心法求解：其中：

(含xs,ys,無法一次求得顯式解)∴只能用迭代的方法對上式求近似解。3.5

選址模型2023/10/146集美大學航海學院物流管理教研室3.5.1

連續(xù)點選址模型2.

精確重心法求解：迭代公式：（j為迭代次數(shù)）其中：應用上述迭代公式，可采用逐步逼近算法求得最優(yōu)解。3.5

選址模型2023/10/147集美大學航海學院物流管理教研室3.5.1

連續(xù)點選址模型2.

精確重心法求解：算法（單一選址的不動點算法）：輸入：n——客戶數(shù)；——各客戶點的坐標，——各客戶點對應的權重，；;(包括運費和運量)輸出：——設施坐標；

Z——總運費。，步驟：①選取初始迭代點

，如：或以交叉中值模型選址的結果之一作為。3.5

選址模型2023/10/148集美大學航海學院物流管理教研室3.5.1

連續(xù)點選址模型2.

精確重心法求解：算法（單一選址的不動點算法）：計算A到各客戶點的直線距離

和：3.5

選址模型2023/10/149集美大學航海學院物流管理教研室3.5.1

連續(xù)點選址模型2. 精確重心法求解：算法（單一選址的不動點算法）：②令計算：3.5

選址模型2023/10/150集美大學航海學院物流管理教研室3.5.1

連續(xù)點選址模型2. 精確重心法求解：算法（單一選址的不動點算法）：③若 ，運費已無法減小；輸出最優(yōu)解 、Z和迭代次數(shù)j，結束。，

， （可能迭代無限次）否則，轉②注1：若工廠到設施的運費包含在成本中，則可將工廠視為一個

客戶點Pi；注2：若直線距離與實際距離有差異，可用一定的修正系數(shù)

來修正差異。3.5

選址模型2023/10/151集美大學航海學院物流管理教研室3.5.1

連續(xù)點選址模型2. 精確重心法求解：算法（單一選址的不動點算法）：終止準則：根據(jù)經(jīng)驗和以前的試驗結果，設置迭代次數(shù)N；③若j>N, 則輸出 和Z，結束。否則，轉②。取閾值

， （較合理，常用）若則輸出 、Z和則迭代過程結束。③若

，迭代次數(shù)j，結束；否則，轉②

(3)求得最優(yōu)解。不動點算法步驟③。3.5

選址模型2023/10/152集美大學航海學院物流管理教研室（即A(3,3)開始）3.5.1

連續(xù)點選址模型2.

精確重心法例1’：取

，則3.5

選址模型2023/10/153集美大學航海學院物流管理教研室3.5.1

連續(xù)點選址模型2.

精確重心法

例1’：3.5

選址模型2023/10/154集美大學航海學院物流管理教研室3.5.1

連續(xù)點選址模型2.

精確重心法例1’：取

，則

，， （選or ，由Z決定。)注：精確重心法得到的最優(yōu)解只有一個點，且交叉中值法和精確

重心法得到的最優(yōu)解一般不一致。作業(yè)：P58 習題2-7，2(用歐幾米得距離計算時取初值點(7,7),閾值0.15)3.5

選址模型2023/10/155集美大學航海學院物流管理教研室3.5.2

離散點選址模型離散點選址問題：在有限的候選位置里，選取最為合適的一個或一組位置為最優(yōu)方案，相應的模型叫離散點選址模型。1.覆蓋模型問題：對于需求已知的一些需求點，如何確定一組服務設施來滿足這些需求點的需求。在該模型中，需要確定服務設施的最小數(shù)量和合適的位置。適用范圍：①商業(yè)物流系統(tǒng)：零售點、加油站或配送中心等的選址。②公用事業(yè)系統(tǒng)：急救中心、預防中心等的選址。③計算機與通信系統(tǒng)：有線電視網(wǎng)的基站、無線通信網(wǎng)絡基站、計算機網(wǎng)絡中的集線器設置等。3.5

選址模型2023/10/156集美大學航海學院物流管理教研室3.5.2

離散點選址模型1）集合覆蓋模型

（由解決問題的方法不同分為兩種。）問題:已知需求點的位置、需求量和候選點的位置，求滿足各需求點的服務需求的條件下，使所投建的設施點的數(shù)目為最小。

目標:用最小數(shù)量的設施去覆蓋所有需求點。(覆蓋全部需求點)模型：

(教材上：M=N)s.t

(各需求點的需求得到100%的滿足)

(各設施點服務能力的限制)(一個地方最多只能建一個設施)

(允許一個設施只提供部分需求)3.5

選址模型2023/10/157集美大學航海學院物流管理教研室1）集合覆蓋模型3.5.2

離散點選址模型其中：；N——需求點的集合，M——可建設施的候選點集合，；——第i個需求點的需求量；——設施節(jié)點j的容量；A(j)

——設施節(jié)點j所覆蓋的需求節(jié)點i的集合；（候選設施點j覆蓋的需求點集。）B(i)——可以覆蓋需求點i的設施節(jié)點j的集合；（覆蓋i的候選設施點集。）xj——yij——節(jié)點i需求中被分配給節(jié)點j的部分。3.5

選址模型2023/10/158集美大學航海學院物流管理教研室3.5.2

離散點選址模型1）集合覆蓋模型（3）求解：① 精確算法：規(guī)模較小時可用分枝定界求解法（整數(shù)規(guī)劃中的一個重要解法）求模型的最優(yōu)解，但運算量很大；② 近似算法：實際問題中，n和m一般較大（也可能n=m），故需設計近似算法來求解?！獑l(fā)式方法。（結果為可行解。）集合覆蓋啟發(fā)式算法步驟：

（該算法最常用，也最簡單。）①確定A(j)，B(i)；②簡化問題。若A(j1) A(j2)，則省去A(j1)，即匆略

j1作為候選點，M′=M-{j1}，最后得M*③

確定合適的組合解。3.5

選址模型2023/10/159集美大學航海學院物流管理教研室：3.5.2

離散點選址模型1）集合覆蓋模型例2．鄉(xiāng)村醫(yī)療診所選址問題：問題：如圖9個村，希望在每一個村周邊30km內(nèi)至少有一個診所，

不考慮診所服務能力的限制。除第6村外，其他村均可作為候選點。3.5

選址模型2023/10/160集美大學航海學院物流管理教研室3.5.2

離散點選址模型1）集合覆蓋模型解：①求A(j)，B(i)，，，（候選點j覆蓋的需求點集合）（覆蓋i的候選點集合）②簡化問題：若A(j1) A(j2)，則省去A(j1)，即忽略在j1村建，其提供的可能

服務已含在j2村的范圍。3.5

選址模型2023/10/161集美大學航海學院物流管理教研室3.5.2

離散點選址模型1）集合覆蓋模型（盡可能少地建設施。）3.5

選址模型村編號1×(1,2,3,4)1,2,3,42×(1,2,3)1,2,331,2,3,4,51,2,3,4,541,3,4,5,6,71,3,4,5,75×（3,4,5,6）3,4,56×4,5,7,874,6,7,84,7,886,7,8,97,8,99×（8,9）8,92023/10/162集美大學航海學院物流管理教研室3.5.2

離散點選址模型1）集合覆蓋模型③

確定合適的組合解?？尚薪猓簕3,4,7,8}、{3,4,8}、{3,8}最優(yōu)解：{3,8}∵{3,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

選址模型2023/10/163集美大學航海學院物流管理教研室3.5.2

離散點選址模型1）集合覆蓋模型擴展解題算法思路： （貪婪法，一般只得到可行解。）如： ，保留 ，省去 的子集，

得A(4)，對N-A(4)={2,8,9}中的每個i，尋找包含i的最大的=A(8)，并省去 的子集A(9)，，得：{4,8,2}or

{4,8,3}*or{4,8,1}3.5

選址模型2023/10/164集美大學航海學院物流管理教研室3.5.2

離散點選址模型2）最大覆蓋模型問題：已知需求點的位置和需求量，候選點的位置和所建設施的數(shù)量中p，選擇p個設施位置，使盡可能多地滿足需求點的服務。目標：對有限的服務網(wǎng)點進行選址，為盡可能多的對象提供服務。建立模型(最大可能地滿足需求)s.t.(i需求的滿足不超過100%)(服務能力的限制)3.5

選址模型2023/10/165集美大學航海學院物流管理教研室3.5.2

離散點選址模型2）最大覆蓋模型其中：N——M——(最多建p個設施)(一處最多建一個設施)

(允許一個設施只提供部分需求)，需求點集；

（i），可建設施的候選點集；

（j）3.5

選址模型2023/10/166集美大學航海學院物流管理教研室3.5.2

離散點選址模型2）最大覆蓋模型di——第i個需求點的需求量；Cj

——j設施節(jié)點的相應容量；A(j)

——設施節(jié)點j所覆蓋的需求點i的集合；

B(i)——可以覆蓋需求點i的設施節(jié)點j的集合；

p——允許投建的設施數(shù)目；xj

——yij——節(jié)點i需求中被分配給節(jié)點j的部分。3.5

選址模型2023/10/167集美大學航海學院物流管理教研室3.5.2

離散點選址模型2）最大覆蓋模型（3）模型的求解——貪婪算法（近似算法）貪婪方法：逐步構造最優(yōu)解的方法。每一步都在一定的準則下作出最優(yōu)的決策，決策一旦作出，就不可更改。作出貪婪決策的依據(jù)稱為貪婪準則。步驟：①設解集

，

；②若

， 點設施具有最大的滿足能力，則

，

；③若|S|=p或全部需求得到滿足，結束。否則，轉②。3.5

選址模型2023/10/168集美大學航海學院物流管理教研室3.5.2

離散點選址模型2）最大覆蓋模型例2’

建醫(yī)療站問題,仍不考慮服務能力的限制。P=2解：①

,由前得②③,結束。注：第2個需求點沒覆蓋。（由最大覆蓋法得到的解集非最優(yōu)解，

此仍啟發(fā)式算法的特點。）3.5

選址模型2023/10/169集美大學航海學院物流管理教研室3.5.2

離散點選址模型2．P—中值模型（1）問題：已知數(shù)量和位置的需求集合，候選設施位置集合，①分別為p個設施選址，②并指派每一需求點到一個特定的設施，使之達到在設施和需求點之間的運輸費用最低。目標：p個設施選址并確定各設施的服務對象，使總運輸成本最少。（適用于工廠、倉庫或配送中心的選址。）3.5

選址模型2023/10/170集美大學航海學院物流管理教研室3.5.2

離散點選址模型2．P—中值模型（2）建立模型s.t.(客戶的需求獲得100%的滿足)(投建的總設施數(shù)為p)(無設施的點無客戶對應)3.5

選址模型2023/10/171集美大學航海學院物流管理教研室3.5.2

離散點選址模型2．P—中值模型（2）建立模型(一處最多建一個設施)(一客戶只由一設施服務)其中：N，M，di，p，xj同前；Cij——從點i到點j的單位運輸費用；yij——3.5

選址模型2023/10/172集美大學航海學院物流管理教研室3.5.2

離散點選址模型（總費用最小。）2．P—中值模型（3）模型的求解：求解P—中值模型需解決兩方面問題：①選擇合適的設施位置（x變量）；②指派客戶到相應的設施中去。求解方法：①精確計算法（只能求解規(guī)模較小的P—中值問題）；②啟發(fā)式算法。3.5

選址模型2023/10/173集美大學航海學院物流管理教研室3.5.2

離散點選址模型2．P—中值模型（3）模型的求解：貪婪取走啟發(fā)式算法：①令當前選中設施點數(shù)k=m；

(即將所有m個候選位置都選中)②將每個客戶指派給(k個設施中)離其最近的設施點，求出總運費Z；③若k=p,輸出k個設施點及各客戶的指派結果,結束;否則,轉④;④從k個候選點中確定一個取走點，滿足：若將它取走并將它的客戶重新指派后，總費用增加量最小。⑤從候選點集中刪去取走點，令k:=k-1，轉②。3.5

選址模型2023/10/174集美大學航海學院物流管理教研室3.5.2

離散點選址模型例3：某飲料公司的倉庫選址問題。

N=8，m=4，p=2目標：運輸成本最低。3.5

選址模型2023/10/175集美大學航海學院物流管理教研室3.5.2

離散點