物流設(shè)施選址(已修改)
2025-03-13 14:29 本頁面
【正文】 集合覆蓋模型 多設(shè)施選址模型 P中值模型 ?問題描述 ? 在一個給定數(shù)量和位置的需求集合和一個候選設(shè)施位置的集合下，確定 p個設(shè)施的位置，并指派每個需求點到一個特定的設(shè)施，使之達到設(shè)施和需求點之間的運輸費用最低。 最大覆蓋模型 P中值模型 多設(shè)施選址模型 ?模型建立 集合覆蓋模型 P中值模型 最大覆蓋模型 P中值模型 323 公式 集合覆蓋模型 多設(shè)施選址模型 P中值模型 ?模型求解 ? 求解一個 P中值模型需要解決兩方面問題： ?選擇合適的設(shè)施位置（ x變量） ?指派需求點到相應(yīng)的設(shè)施中去（ y變量） ? 與覆蓋模型相似，求解 P中值模型主要有兩大類方法，即精確計算法和啟發(fā)式算法。常用的求解P中值模型的啟發(fā)式算法被稱為：貪婪取走啟發(fā)式算法。 最大覆蓋模型 P中值模型 多設(shè)施選址模型 ?貪婪取走算法 第二步 第三步 ? 將每個需求點指派給 k個設(shè)施點中離其距離最近的一個設(shè)施點。 ? 求出總運輸費用 Z ? 若 k=p，得到 k個設(shè)施點及各需求點的指派結(jié)果，停止 ? 否則，轉(zhuǎn)第四步 第四步 ? 從 k個候選點中確定一個取走點，滿足：若將它取走并將它的需求點指派給其它最近設(shè)施后，總費用增加量最小 ? 從候選集合中刪去取走點，令k=k1，轉(zhuǎn)第二步 第一步 ? 令當(dāng)前選中設(shè)施點數(shù) k=m，即所有 m個候選位置都選中 集合覆蓋模型 最大覆蓋模型 P中值模型 P中值模型 多設(shè)施選址模型 ? 某公司在一新地區(qū)經(jīng)過一段時間的宣傳廣告后，得到了 8個超市的訂單，由于該地區(qū)離總部較遠，公司擬在該地區(qū)新建 2個倉庫，用最低的配送成本來滿足該地區(qū)的需求。經(jīng)過一段時間的實地考察之后，已有 4個候選地址，如下圖所示。從候選地址到各個超市運輸成本 cij、各超市的需求量 di都已經(jīng)確定，如下表所示。試選擇其中的兩個候選點作為倉庫地址，使總運輸成本最小。 集合覆蓋模型 最大覆蓋模型 P中值模型 P中值模型 36 例 1 2 3 41 4 12 20 6 1002 2 10 25 10 503 3 4 16 14 1204 6 5 9 2 805 18 12 7 3 2006 14 2 4 9 707 20 30 2 11 608 24 12 6 22 100jic ij d i?第一步 ?初始化，令 k=m=4； ?將每個客戶指派給運輸成本最低的一個候選位置，指派結(jié)果為： A=(a1, a2, … a 8)=(1,1,1,4,4,2,3,3)； ?總費用 248081?? ??iiia dcZ i多設(shè)施選址模型 集合覆蓋模型 最大覆蓋模型 P中值模型 36 例 1 2 3 41 4 12 20 6 1002 2 10 25 10 503 3 4 16 14 1204 6 5 9 2 805 18 12 7 3 2006 14 2 4 9 707 20 30 2 11 608 24 12 6 22 100jic ij d i100400360140160600120600421 314578632多設(shè)施選址模型 ?第二步 ?分別對取走候選點 1,2,3,4進行分析，并計算各自的費用增量： 集合覆蓋模型 最大覆蓋模型 P中值模型 36 例 1 2 3 41 4 12 20 6 1002 2 10 25 10 503 3 4 16 14 1204 6 5 9 2 805 18 12 7 3 2006 14 2 4 9 707 20 30 2 11 608 24 12 6 22 100jic ij d i?取走候選點 1，結(jié)果 (4,2,2,4,4,2,3,3)，Z=3200，費用增量 ΔZ=720 150060048014016060012060042314578632多設(shè)施選址模型 ?第二步 ?分別對取走候選點 1,2,3,4進行分析，并計算各自的費用增量： 集合覆蓋模型 最大覆蓋模型 P中值模型 36 例 1 2 3 41 4 12 20 6 1002 2 10 25 10 503 3 4 16 14 1204 6 5 9 2 805 18 12 7 3 2006 14 2 4 9 707 20 30 2 11 608 24 12 6 22 100jic ij d i?取走候選點 2，結(jié)果 (1,1,1,4,4,3,3,3)，Z=2620，費用增量 ΔZ=140 100400360280160600120600421 314578632多設(shè)施選址模型 ?第二步 ?分別對取走候選點 1,2,3,4進行分析，并計算各自的費用增量： 集合覆蓋模型 最大覆蓋模型 P中值模型 36 例 1 2 3 41 4 12 20 6 1002 2 10 25 10 503 3 4 16 14 1204 6 5 9 2 805 18 12 7 3 2006 14 2 4 9 707 20 30 2 11 608 24 12 6 22 100jic ij d i?取走候選點 3，結(jié)果 (1,1,1,4,4,2,4,2)，Z=3620，費用增量 ΔZ=1140 1004003601401606001 314563212006604728
物理相關(guān)推薦
鄂ICP備17016276號-1