選址問題課件

選址問題（LocationProblem）選址理論--是關(guān)于選址問題的模型和算法的理論。選址問題復(fù)雜多樣，涉及到非常大的方面，如定位一個新的制造企業(yè)或者軍事基地；也涉及到非常小的方面，如在電路板上印刷完整的電路。按照被定位的對象的空間維數(shù)劃分，可以分為：立體選址、平面選址、線選址、點選址。第15章選址問題（LocationProblem）15.1概述（Introduction）15.2三維選址問題（Three-DimensionLocationProblem）15.2.1遺傳算法實現(xiàn)（GeneticAlgorithm）15.2.2算例（Parexample）15.2.3小結(jié)（Summary）15.3集裝箱船配載優(yōu)化方法研究（ResearchontheOptimalMethodsforContainerAboardLoaded）15.3.1集裝箱重量分布的優(yōu)化模型（TheOptimalModelofContainerWeight）15.3.2的確定（Confirm）15.3.3最少壓載量的確定（TheMinimumBallast）15.3.4計算實例（Parexample）15.4點選址問題（DotLocationProblem）15.4.1連續(xù)點選址問題（ContinuousLocationProblem）15.4.2離散點選址問題（DiscreteLocationProblem）15.5無能力約束設(shè)施選址問題（UncapacitiedFacilitesLocationProblem（UFL））15.5.1問題描述（Introduction）15.5.2UFL問題的線性規(guī)劃模型（LinerModelofUFL）15.5.3對偶問題（Dualproblem）15.5.4UFL的啟發(fā)式算法（HeuristicMethodsforUFL）15.1概述選址理論——是關(guān)于選址問題的模型和算法的理論。選址問題復(fù)雜多樣，涉及到非常大的方面，如定位一個新的制造企業(yè)或者軍事基地；也涉及到非常小的方面，如在電路板上印刷完整的電路。為選址問題設(shè)計算法和模型時通常要考慮以下因素：（1）被定位的對象具有什么特性，（2）目標(biāo)選址地區(qū)的結(jié)構(gòu)特點是什么，（3）目標(biāo)和成本參數(shù)是什么，（4）其它限制條件是什么。以上因素影響到模型結(jié)構(gòu)和算法設(shè)計，可據(jù)此對選址問題進行分類。15.1概述按照被定位的對象的空間維數(shù)劃分，可以分為：立體選址、平面選址、線選址、點選址。立體選址中，物體具三維空間，這類選址問題的例子是集裝箱裝箱問題。若物體具二維空間，這類選址問題稱為平面選址，其例子是工廠或貨運站設(shè)施布局。若物體具一維空間，這類選址問題稱為線選址，其例子是在倉庫的巷道兩邊劃出合適的揀選帶。若物體是一個點，這類選址問題稱為點選址，點選址常被用在物體尺寸相對于目標(biāo)區(qū)域尺寸忽略不計的情況下。這種類型在物流中占絕大多數(shù)，最常見的是制造和配送系統(tǒng)的選址，如圖15-1維數(shù)空間選址的問題是存在的，但是很少見。如果限制條件或者參數(shù)隨時間而變化，這時需要考慮時間維，這類問題統(tǒng)稱為動態(tài)選址問題。15.1概述圖15-1點選址的例子15.1概述按照目標(biāo)區(qū)域的結(jié)構(gòu)來劃分，可分為：連續(xù)選址、網(wǎng)格選址、網(wǎng)絡(luò)選址和離散點選址。連續(xù)選址中，候選區(qū)域是一個平面或球面并且沒有其它任何結(jié)構(gòu)。這時可能選址的數(shù)量是無限大的。距離的數(shù)值是以一個距離準(zhǔn)則來確定的。這些模型在數(shù)學(xué)上是連續(xù)的并且通常都可以采用分析的方法。圖15-2連續(xù)選址的示意圖15.1概述網(wǎng)格選址中，目標(biāo)區(qū)域被劃分為許多個單元，要求為對象分配其中若干個單元。例如：在一個大型倉庫中為成千上萬種不同商品分配存儲單元。盡管存儲單元是有限的，但是很多。很明顯采用離散選址既沒有必要，也難以處理。圖15-3網(wǎng)格選址示例15.1概述網(wǎng)絡(luò)選址中，目標(biāo)選址區(qū)域是一個網(wǎng)絡(luò),即節(jié)點和邊的集合。通常而言，如果網(wǎng)絡(luò)不存在諸如樹形等特殊結(jié)構(gòu)時，不存在有效的算法。最佳選址問題是建立在運輸網(wǎng)絡(luò)基礎(chǔ)上時，通常都屬于這類問題。圖15-4網(wǎng)絡(luò)選址問題15.1概述離散點選址問題中，候選點數(shù)量是有限的并且較少。這些模型是現(xiàn)實中最常用的模型，但是相關(guān)的計算和數(shù)據(jù)采集的值都比較大。典型的例子是對企業(yè)的配送網(wǎng)絡(luò)進行詳細設(shè)計。從目標(biāo)函數(shù)來分類，基本上可以分為中位問題（medianproblem）和中心問題（CenterProblem）兩類。中位問題以總成本最小為目標(biāo)函數(shù)。這個指標(biāo)常用于商業(yè)系統(tǒng)，又稱最小總和目標(biāo)（MinisumObjective）。

5-1其中X表示選址方案,表示方案X對于目標(biāo)j的成本。15.1概述中心問題以服務(wù)于各個顧客的最大成本最小化為總目標(biāo)。這個指標(biāo)經(jīng)常被用在軍隊，公共服務(wù)系統(tǒng)和其他緊急情況處理，又稱為最小化最大值（MinimaxObjective），目標(biāo)函數(shù)被寫成：

5-2例如：假設(shè)在一條直線上有4個點分別為0，5，6，7。假定要在直線上選一個中心為上述四個點提供服務(wù)。假設(shè)服務(wù)這些點的成本是與距離嚴(yán)格成比例的。根據(jù)最小總和指標(biāo)，中位問題的最優(yōu)化選址應(yīng)該是在5和6之間任何一個點。而根據(jù)最小化最大值目標(biāo)，中心問題的最優(yōu)化選址應(yīng)該是，以使最遠的服務(wù)距離最小化。15.1概述通過觀察上述例子可以發(fā)現(xiàn)，當(dāng)被服務(wù)點在0和7之間增加若干個時，中位問題的最優(yōu)解要發(fā)生變化，而中心問題則不會，因為中心問題的一個重要特點是，最優(yōu)解取決于某些極端情形。圖15-5中位問題和中心問題的比較15.1概述第三種類型的指標(biāo)函數(shù)是獲取最大最小目標(biāo)值。比如污水處理工廠選址或者某些軍事裝備選址。這類問題又稱為反中心問題（anti-CenterProblem）。其目標(biāo)函數(shù)可寫為：式5-3同樣以上述例子來討論，可知反中心問題的最優(yōu)解是X=2.5。圖15-6反中心問題和中心問題的比較15.1概述根據(jù)問題中的參數(shù)是否與解存在關(guān)聯(lián)，可分為純選址問題和選址—分配問題。純選址問題中參數(shù)或結(jié)構(gòu)不依賴新建設(shè)施而改變，是事先已確定。相反則稱為選址--分配問題。例如：指派顧客到最近的配送中心，如果移動了配送中心不但可能增加了與顧客的距離而且有可能使顧客去其它的配送中心。根據(jù)問題中的參數(shù)是否隨時間而改變，可以分為靜態(tài)選址問題和動態(tài)選址問題；根據(jù)參數(shù)確定性的還是隨機性的還可以分為確定性選址問題和隨機選址問題。此外，依據(jù)候選點是否存在服務(wù)能力約束，可以分為無限能力選址和有限能力選址。15.2三維選址問題集裝箱裝載問題廣泛地出現(xiàn)在鐵路貨車車廂裝載、汽車車廂裝載、輪船配載、集裝箱裝載等情況。問題的提法是：將一批待布箱體(長方體)裝入長方體容器中，目標(biāo)是使容器空間利用率和重量利用率達到最高。同時要考慮到的約束有：(1)箱體本身的承重性(易碎性)；(2)箱體搬運的難易性；(3)一些貨物必須隔離；(4)不允許超過最大承重量；(5)重心與幾何形心偏差不應(yīng)太大；(6)貨物碼放的穩(wěn)定性等等。15.2三維選址問題有關(guān)布局問題的綜述性工作，其中大部分是研究二維或三維矩形物體在矩形容器中的布局。目前常用的布局優(yōu)化方法有數(shù)學(xué)規(guī)劃法、圖論法、啟發(fā)式方法、人工智能，多為不帶約束的簡化布局問題。楊傳民等人通過全面枚舉搜索方法來研究相同大小的立方體的裝箱優(yōu)化問題。Mannchen設(shè)計的數(shù)搜索算法，理論上對三維箱體布局有效，但由于三維箱體布局屬于NP完全問題，隨著布局箱體的增多，解空間劇增，因而計算效率較低。H．GEHRING提出按階段填充，在深度方向按層布局的啟發(fā)式算法，不僅考慮了空間利用率，而且還考慮了重心平衡。戴佐采用八叉樹描述三維物體，并以八叉樹為基礎(chǔ)設(shè)計啟發(fā)式算法．王金敏以相同尺寸的物體布局為研究對象，特約束處理加入啟發(fā)式規(guī)則中，提出關(guān)于約束底盤裝載問題的啟發(fā)式方法。以上求解都建立在簡化模型的基礎(chǔ)上，而現(xiàn)實生活中存在著大量多目標(biāo)、多約束的布局，人們在研究集裝箱布局時，往往采用簡化模型，以回避這一問題。許多實際約束，如裝載穩(wěn)定性、重心平衡使得集裝箱布局問題更加復(fù)雜(本文定義這種問題為復(fù)雜集裝箱裝載問題)。通常需要將這些約束考慮到啟發(fā)式規(guī)則中，而不能只是先考慮空間利用率，待布局完成后再檢查約束，因為有些復(fù)雜的布局很難憑經(jīng)驗撿查出是否滿足約束。15.2三維選址問題因此，開發(fā)實用的綜合考慮多種約束，多種目標(biāo)的集裝箱空間規(guī)劃算法有待于進一步加以研究。由于存在多目標(biāo)、多約束的空間規(guī)劃問題的計算復(fù)雜性，利用數(shù)學(xué)規(guī)劃法和圖論法不太有效；啟發(fā)式方法雖然較為有效，但大多只能解一類問題，局限性較大。因此，本文采用遺傳算法作為工具，通過權(quán)重系數(shù)變化法處理多目標(biāo)問題，通過罰函數(shù)法處理約束，在采用遺傳算法處理復(fù)雜集裝箱裝載問題方面做了一些嘗試。求解問題的目標(biāo)包括：①空間利用率最大；②貨物總重量最大；③貨物總體重心盡量低，以使穩(wěn)定性最大，搬運方便。其約束包括：①總重量不允許超過集裝箱最大承重量；②物體間不允許出現(xiàn)空間干涉。15.2三維選址問題遺傳算法是模擬生物在自然環(huán)境中的遺傳和進化過程而形成的一種自適應(yīng)全局優(yōu)化概率搜索算法。遺傳算法在空間規(guī)劃領(lǐng)域中的應(yīng)用剛剛開始，集裝箱空間規(guī)劃問題為NP完全問題，而遺傳算法本身的魯棒性、并行性以及在NP完全問題求解中的廣泛應(yīng)用表明，遺傳算法是解決復(fù)雜集裝箱空間規(guī)劃問題的有效途徑。如何將遺傳算法應(yīng)用于集裝箱空間規(guī)劃是值得深入研究的，這對于推廣遺傳算法在實際空間規(guī)劃設(shè)計中的應(yīng)用，具有重要的實際意義。15.2.1遺傳算法實現(xiàn)15.2三維選址問題1.問題解的數(shù)字串表示——編碼平面布局一般采用待布物體在平面上的坐標(biāo)組成解串，但是，坐標(biāo)值的調(diào)整變化僅描述了待布物本身位置的改變，可能會使待布物之間出現(xiàn)干涉，為此需要進行判斷，以避免出現(xiàn)干涉，亦即坐標(biāo)值的變化是受限制的，這不適合于用遺傳算法求解。而且，在三維空間布局中，干涉的計算量要大得多。因此，需要構(gòu)造一種新的、更適合的表示方式。把待布物的編號按排放顧序排列成串，即15.2.1遺傳算法實現(xiàn)15.2三維選址問題15.2.1遺傳算法實現(xiàn)其中表示待布物的個數(shù)；為整數(shù)，其值代表盒子的編號。交叉和變異算子對其進行的操作實際上就是改變待布物的排放順序，從而產(chǎn)生不同的空間規(guī)劃圖（不同的解）。數(shù)字串是解的基因型表示，能否簡單、快速地將其轉(zhuǎn)化為表現(xiàn)型（即空間規(guī)劃圖），從而求出其有關(guān)評價參數(shù)，就成為遺傳算法能否有效應(yīng)用的關(guān)鍵，為此，本文提出如下譯碼算法。15.2三維選址問題2.空間分解算法——譯碼布局空間分解過程采用三叉樹數(shù)據(jù)結(jié)構(gòu)表示。先對原始布局空間求解，此時，原始布局空間為當(dāng)前布局空間，對應(yīng)于三叉樹的根結(jié)點。按照第15.1節(jié)中數(shù)字串的先后順序，從可選布局物體中選擇一個相對于當(dāng)前布局空間為最優(yōu)的布局物體，其擺放方式通過可行域的形狀確定，將其定位于當(dāng)前布局空間后部的左下角。如圖15-1位置所示，并將布入的物體編號從中刪除。這樣，原布局空間的剩余空間可分為，，這3個子空間，分別對應(yīng)于三叉樹根結(jié)點的左、中、右3個子結(jié)點。剩余的布局空間就變成3個獨立的布局空間，依次將，，當(dāng)作當(dāng)前空間，對這3個布局空間重復(fù)上述分解過程，直至沒有待布局物體滿足要求或集裝箱沒有可利用空間時停止。15.2.1遺傳算法實現(xiàn)15.2三維選址問題

這樣，數(shù)字串就轉(zhuǎn)化為布局圖，并且克服了空間干涉約束。由此可見，三叉樹結(jié)構(gòu)對于求解復(fù)雜集裝箱布局的空間分解問題有著明顯的優(yōu)勢。但對于具有特殊形狀的容器的布局問題，目前還無法很好地應(yīng)用。圖15-7空間分解示意圖15.2.1遺傳算法實現(xiàn)15.2三維選址問題3.適宜度函數(shù)遺傳算法對一個解的好壞用適宜度函數(shù)值的大小來評價，適宜度的值越大，解的質(zhì)量超好。在討論遺傳算法的實現(xiàn)之前，應(yīng)先定義適宜度函數(shù)。4.空間利用率函數(shù)

其中，表示第個布入的盒子的體積，表示集裝箱體積，m為布入的盒子數(shù)15.2.1遺傳算法實現(xiàn)15.2三維選址問題重量考察函數(shù)。其中，表示i第個布入盒子的質(zhì)量，表示集裝箱最大承載重量。超過最大重量，懲罰為0。重心考察函數(shù)15.2.1遺傳算法實現(xiàn)15.2三維選址問題其中，表示集裝箱高度，表示第個盒子的重心高度，通常取盒子高度的一半。表示第個盒子的重量。該函數(shù)主要考察碼放的穩(wěn)定性和撒運的難易性。若重物體都在下面，則碼放穩(wěn)定，且易搬運。因此，根據(jù)懲罰函數(shù)法和處理多目標(biāo)優(yōu)化的加權(quán)系數(shù)法，定義適宜度函數(shù)為

其中，為權(quán)重，根據(jù)經(jīng)驗來選擇。15.2.1遺傳算法實現(xiàn)15.2三維選址問題5.遺傳算子（1）選擇算子采用比例選擇法和最優(yōu)保存策略，既能保證適應(yīng)度較高的個體遺傳到下一代，又能保證有較高的全局收斂性。比例選擇方法（proponionalmodel）的基本思想是：各個個體被選中的概率與其適應(yīng)度大小成正比，適應(yīng)度越高的個體被選中的概率越大；反之，適應(yīng)度越低的個體被選中的概率小。15.2.1遺傳算法實現(xiàn)15.2三維選址問題我們希望適應(yīng)度最好的個體要盡可能地保留到下一代群體中。為了達到這個目的，可以便用最優(yōu)保存策略進化模型(elitistmodel)來進行優(yōu)勝劣汰操作，即當(dāng)前群體中適應(yīng)度最高的個體不參與交叉運算和變異運算，而是用它來替換掉本代群體中經(jīng)過交叉、變異等遺傳操作后所產(chǎn)生的適應(yīng)度最低的個體。最優(yōu)保存策略可視為選擇操作的一部分。該策略的實施可保證迄今為止所得的最優(yōu)個體不被交叉、變異等遺傳運算所破壞，它是遺傳算法以概率1收斂到全局最優(yōu)解的一個重要保證條件。15.2.1遺傳算法實現(xiàn)15.2三維選址問題15.2.1遺傳算法實現(xiàn)（2）交叉算子對于本文這種類似于旅行商的以符號編碼的基因串，交叉方式有部分映射交叉、順序交叉、循環(huán)交叉等。本文采用部分映射交叉方式。部分映射交叉也稱為部分匹配交叉〔patiallymatchedcrossover)。這種交叉操作的主要思想是：整個交叉操作過程由兩步來完成，首先對個體編碼串進行常規(guī)的雙點交叉操作，然后根據(jù)交叉區(qū)域內(nèi)各個基因值之間的映射關(guān)系來修改交叉區(qū)域之外的各個基因座的基因值。15.2三維選址問題15.2.1遺傳算法實現(xiàn)（3）變異算子本文采用如下變異操作，以較小的概率一對數(shù)字串中任意兩個基因座和Q之間的基因進行逆排列。5.終止準(zhǔn)則進化代以后，停止計算，輸出最好的解作為所求得的最優(yōu)解。15.2三維選址問題6.運算過程（1）初始化，設(shè)置進化代數(shù)計數(shù)器t＝0，設(shè)置最大進化代數(shù)T＝200，隨機生成2*M個個體作為初試群體P(0)，M＝20。（2）個體評價，按前述計算群體P(t)中各個個體的適應(yīng)度F()。（3）選擇運算，將前述的選擇算子作用于群體。（4）交叉運算，將前述的交叉算子作用于群體。15.2.1遺傳算法實現(xiàn)15.2三維選址問題（5）變異運算，將前述的變異算子作用于群體。（6）群體經(jīng)過選擇、交叉、變異運算之后得到下一代群體，終止條件判斷。，則，轉(zhuǎn)到步驟2；若，則以進化過程中所得到的具有最大適應(yīng)度的個體作為最優(yōu)解輸出，終止計算。15.2.1遺傳算法實現(xiàn)15.2三維選址問題設(shè)布局空間為國際標(biāo)準(zhǔn)的20英尺集裝箱，尺寸為2.352*2.388*5.899，單位是米，最大載重量為18.07噸，已知其最優(yōu)解是體積利用率為100％，重量利用率為100％，重心高度為集裝箱高度的1／2，重心評價函數(shù)為100，總體適宜度函數(shù)為100，待布局貨物數(shù)據(jù)，計算結(jié)果如圖15-8所示，見表15-1。15.2.2算例圖15-8集裝箱計算結(jié)果圖15.2三維選址問題15.2.2算例表15-1集裝箱計算結(jié)果表15.2三維選址問題CH表示在H方向的坐標(biāo)，CW表示在方向的坐標(biāo)，W表示在方向的坐標(biāo)，CD表示在方向盒子的尺寸，D表示在方向盒子的尺寸，表示在方向盒子的尺寸(坐標(biāo)見圖15-7)，共布入18個盒子，體積利用率為95.32％，重量利用率為99.9％，重心高為118.16cm，重心評價函數(shù)為100．56，總體適宜度函數(shù)為97.48，計算時間為0.1小時，此結(jié)果與最優(yōu)結(jié)果相差很小。同一組數(shù)據(jù)采用中的啟發(fā)式算法，不考慮約束，空間規(guī)劃結(jié)果如圖所示，見表15-2，求得的空間利用率為90.7％p低于本算法，重量利用率為118％，超過最大允許重量，顯然，本算法即使考慮約束，結(jié)果也優(yōu)，說明本算法是有效的。15.2.2算例15.2三維選址問題15.2.2算例表15-2空間規(guī)劃結(jié)果15.2三維選址問題空間規(guī)劃問題大量出現(xiàn)在工程領(lǐng)域，通過集裝箱空間規(guī)劃實驗可以看出，利用遺傳算法解三維物體空間規(guī)劃是行之有效的。本文僅以典型約束、優(yōu)化目標(biāo)為例，更多的約束或目標(biāo)可以類似地加人到本算法之中。本文為利用遺傳算法求解集裝箱空間規(guī)劃提供了經(jīng)驗和基礎(chǔ)，對推廣遺傳算法在空間規(guī)劃設(shè)計中的應(yīng)用具有一定的意義。15.2.3小結(jié)15.2三維選址問題15.3集裝箱船配載優(yōu)化方法研究

在集裝箱船配載設(shè)計過程中，充分發(fā)揮集裝箱船裝載能力，保證集裝箱船的強度以及適度的穩(wěn)性和適當(dāng)?shù)某运钍欠e載設(shè)計的關(guān)鍵。15.3.1集裝箱重量分布的優(yōu)化模型集裝箱重量合理的縱向分布有利于減小船體所受的彎矩，合理的垂向的分布則有利于保證適度的穩(wěn)性，充分發(fā)揮船舶載貨能力，減少壓載，改善航行性能和減小綁扎設(shè)備受力。集裝箱重量的縱向分布和垂向分布無關(guān)，集裝箱船的受力和穩(wěn)性優(yōu)化這一多目標(biāo)優(yōu)化問題可轉(zhuǎn)化為單目標(biāo)優(yōu)化問題。1.集裝箱縱向受力優(yōu)化集裝箱船積載時對強度的考慮，主要是船舶的總縱強度、局部強度和扭轉(zhuǎn)強度。在積載時應(yīng)盡量將各行位內(nèi)各載荷重量左右對稱分布以使轉(zhuǎn)矩最小。對于局部強度，主要是使各部位集裝箱的垂向累計重量不超過甲板或艙底的允許負(fù)荷，可在縱向受力的優(yōu)化模型中以約束條件來處理。因此受力優(yōu)化的關(guān)鍵是縱向受力，即使船體所受的靜水彎矩最小。15.3集裝箱船配載優(yōu)化方法研究15.3.1集裝箱重量分布的優(yōu)化模型15.3集裝箱船配載優(yōu)化方法研究15.3.1集裝箱重量分布的優(yōu)化模型為求解方便，可以根據(jù)集裝箱的縱向分布情況，沿船長方向在船上劃分若干個站點，并以集裝箱區(qū)域的前端剖面作為0號(n＝0)，該處彎矩為此，01行箱的后端剖面為1號(n＝1)，該處彎矩為此，03行位的后端剖面站號為n＝2，該處彎矩為此，依此類推。船體各區(qū)段的船體重力，浮力，壓載量為，船舶燃油、淡水、備品和船舶常數(shù)的重量為，相應(yīng)行位的集裝箱重量為。15.3集裝箱船配載優(yōu)化方法研究15.3.1集裝箱重量分布的優(yōu)化模型設(shè)

各區(qū)段內(nèi)的負(fù)荷

船體站點處的靜水彎矩為15-415.3集裝箱船配載優(yōu)化方法研究15.3.1集裝箱重量分布的優(yōu)化模型式中，為除集裝箱以外的其他各項載荷和船體重量產(chǎn)生的彎矩；為前后兩站點的間距，m；為對應(yīng)于的兩行箱位之間的空隙，m；為對應(yīng)于的負(fù)荷作用中心點距該區(qū)段中點的距離，m，位于中點之后取正?？稍诖翱沾亓壳€上求得。平均吃水和吃水差由航次具體情況確定。吃水和吃水差確定后，相應(yīng)各段船體的浮力矩也可通過邦戎曲線(banjean’scurve)求得。如果事先擬定壓載方案，可作為常數(shù)項，因此只有為隨機變量。15.3集裝箱船配載優(yōu)化方法研究15.3.1集裝箱重量分布的優(yōu)化模型由于每一行位集裝箱的重量分為甲板和艙內(nèi)兩部分，則，每行箱位集裝箱重量的限制為。式中，和分別為在某一行箱位上甲板和艙內(nèi)所能承載的最大集裝箱重量。假設(shè)所有的箱位均裝有集裝箱(如果實際箱數(shù)少于總箱位容量，則空余的箱位重量取0，集裝箱縱向受力的線型優(yōu)化模型可表示為

15-515.3集裝箱船配載優(yōu)化方法研究15.3.1集裝箱重量分布的優(yōu)化模型式中，為最輕個集裝箱的平均重量；為最重個集裝箱的平均重量；為第排(行)集裝箱重量為第行的箱位數(shù)；為集裝箱總行位數(shù)。當(dāng)機艙后部有箱位時，可將機艙范圍看成一行，以該范圍集裝箱重量取零作為約束條件。有時需要指定具體行位的裝箱方案，也可在約束條件中實現(xiàn)。式15-5還應(yīng)受條件的約束(為集裝箱的總重量)。求解時，可先按式5—5從01行開始，采用逐行位迭代的方法，求出每一行箱位處集裝箱重量的解，然后按線性比例的方法考慮條件的約束，求出每一行箱位處集裝箱重量的最優(yōu)解。15.3集裝箱船配載優(yōu)化方法研究15.3.1集裝箱重量分布的優(yōu)化模型2.集裝箱船穩(wěn)性優(yōu)化設(shè)第層集裝箱重心距基線高分別為，第行箱位共有的層數(shù)，則全船集裝箱的垂向重力力矩為：

式中，。又船舶合重心位置：。令，有：15-615.3集裝箱船配載優(yōu)化方法研究15.3.1集裝箱重量分布的優(yōu)化模型在一定排水量條件下，如果事先擬定壓載和油水裝載方案，則式中只有一個變量，如果給定的最優(yōu)值，則可找到相應(yīng)最優(yōu)的。在受力優(yōu)化問題中，可求出使得集裝箱船所受總縱彎矩最小的各行位重量分布?，F(xiàn)假設(shè)各行箱位上集裝箱的重量分布服從一級優(yōu)化的結(jié)果，具體分配到各行箱位的最優(yōu)集裝箱垂向重量力矩與各行位集裝箱重量呈線性比例。實際裝載時，可能要根據(jù)情況指定某一行位的某些集裝箱必須裝于甲板上。根據(jù)集裝箱到港等情況，設(shè)有r只集裝箱限定裝于第行甲板上，重量為，其合重心距基線高，其它各行均自艙內(nèi)開始裝。15.3集裝箱船配載優(yōu)化方法研究15.3.1集裝箱重量分布的優(yōu)化模型令，有

（m?kN）

15-7式中，當(dāng)時，。在求出各行箱位集裝箱垂向重量矩的基礎(chǔ)上，可進一步求出第行第層集裝箱的重量分布。其線性優(yōu)化模型為

15-815.3集裝箱船配載優(yōu)化方法研究15.3.1集裝箱重量分布的優(yōu)化模型式中，為集裝箱船第i行、k層的箱位數(shù)，和分別為最小和最大個集裝箱的平均重量。對于上兩式，可從01行開始，求出該行各層的集裝箱重量分布優(yōu)化解。該線性優(yōu)化問題可利用單純形法求解。01行的求解后，順次進入其他各行求解。對于40ft集裝箱，則以兩個20ft集裝箱的重量計算到相鄰兩行的箱位中。15.3集裝箱船配載優(yōu)化方法研究15.3.2的確定上述優(yōu)化問題求解時，需要計算，也就是必須首先確定最優(yōu)重心高度或最優(yōu)的初穩(wěn)性高度的值。根據(jù)有經(jīng)驗的集裝箱船船長的意見，一般具有12列集裝箱寬的集裝箱船，取=1.0m左右；具有8列集裝箱寬的小型集裝箱船，取=1.2m左右。但這一結(jié)論顯得較為粗略，船舶在不同排水量和不同海況條件下，其應(yīng)該是有所區(qū)別的。在確定最優(yōu)或的值時，應(yīng)考慮臨界初穩(wěn)性高度(或極限重心高度)、橫搖周期、裝載能力、綁扎設(shè)備設(shè)計時設(shè)定的最大、航行區(qū)域及其風(fēng)浪情況、船員安全感(如果值偏小，船員安全感差)等要求。15.3集裝箱船配載優(yōu)化方法研究15.3.2的確定在綜合考慮上述各項因素的前提下，一般應(yīng)在保證安全和船員安全感的條件下，盡量取較小的值或較大的值。為此，作者主張在滿足臨界初穩(wěn)性高度的前提下適當(dāng)增加一個安全余量作為最優(yōu)初穩(wěn)性高度。在分析實踐中經(jīng)驗數(shù)據(jù)的基礎(chǔ)上對的大小提出如下算式。

15-10式中，C為考慮航區(qū)風(fēng)浪及甲板上浪程度的系數(shù)，取0.8~1.2，航區(qū)風(fēng)浪大或船較小、受風(fēng)浪影響大時，取大值，反之取小值。15.3集裝箱船配載優(yōu)化方法研究15.3.2的確定如果根據(jù)綁扎設(shè)備設(shè)計所假定的最大初穩(wěn)性高度小于根據(jù)上述方法確定的值，則可取，即有

15-11如船寬為20.8m的某614TEU集裝箱船，的取值范圍為0.37~0.66m，其滿載時的約為0.96~1.26m，但其綁扎系統(tǒng)允許的初穩(wěn)性高度為1.04m．航區(qū)風(fēng)浪大時可?。?.04m．必要時也可取＝1.26m，但有必要對綁扎系統(tǒng)采取加固措施。15.3集裝箱船配載優(yōu)化方法研究15.3.3最少壓載量的確定集裝箱船的穩(wěn)性特點決定了它必須依靠壓載來保證穩(wěn)性，但壓載會減少船舶的集裝箱載重能力，增加航行阻力。這里提供一種通過在預(yù)定壓載方案下求取穩(wěn)性范圍，并使初穩(wěn)性上限值接近且略大于的方法來確定最少壓載量的方法。的上限值可由將全部承運的集裝箱從艙底自下而上按重量由大到小的順序配船后求得。而的下限值則可按上述相反的順序?qū)⒓b箱配船后求得。15.3集裝箱船配載優(yōu)化方法研究15.3.3最少壓載量的確定要在配載時能得到與相吻合的值且壓載量最少，應(yīng)有且。如果在預(yù)定壓載方案下計算的，使得，或比小很多，則可按通過調(diào)整壓載方案對初穩(wěn)性的上限值進行調(diào)整。根據(jù)調(diào)整穩(wěn)性的一般計算公式計算出需要在具體位置調(diào)整的壓載量。在實際操作時，應(yīng)修正自由液面的影響。考慮到優(yōu)化縱向受力、中途油水消耗等需要，應(yīng)有一定的富裕壓載量。15.4點選址問題15.4.1連續(xù)點選址問題連續(xù)選址分析中，點與點之間的距離計算標(biāo)準(zhǔn)有兩種：直線距離準(zhǔn)則和距離準(zhǔn)則。設(shè)平面上兩點i和j兩點之間的笛卡爾坐標(biāo)分別是。直線距離準(zhǔn)則用公式表達為：，上標(biāo)E表明是直線距離。折線距離準(zhǔn)則用公式表達為：，上標(biāo)R表明是折線距離。15.4點選址問題15.4.1連續(xù)點選址問題在大范圍地理空間有關(guān)的選址問題中，實際的道路距離通常被近似為直線距離乘上一個近似因子。例如，在美國大陸，因子為1.2，在美國的東南部為1.26。而在城市范圍內(nèi)選址時，由于道路系統(tǒng)多數(shù)具有網(wǎng)格特性，此時通常采用折線距離準(zhǔn)則。1.直線距離準(zhǔn)則下選址關(guān)于折線距離準(zhǔn)則下選址問題，我們提供重心法和網(wǎng)絡(luò)流算法。在使用了歐幾密德距離之后，目標(biāo)函數(shù)變成了：

15.4點選址問題15.4.1連續(xù)點選址問題這是一個雙變量系統(tǒng)，分別對和進行求偏微分，并卻令其為零，這樣就可以得到兩個微分等式。應(yīng)用這兩個等式分別對和進行求解，既可以求出下面的一對隱含有最優(yōu)解的等式：

其中，。15.4點選址問題15.4.1連續(xù)點選址問題在上式中，在等式的左右兩邊都出現(xiàn)了和（在右邊包含了項），因此該微分方程組不能直接求解。對于這個問題，可以通過迭代的方法進行求解，這需要提供一組初始值和。然后利用和求出，再用它去求出和，迭代公式如下：

其中，。15.4點選址問題15.4.1連續(xù)點選址問題

如果該迭代過程具有收斂性，那么經(jīng)過無限次的迭代之后，可以得到一個最優(yōu)解。但是在實際中，可以迭代的次數(shù)是有限的，所以在迭代過程中需要確定一個中止準(zhǔn)則。設(shè)置中止準(zhǔn)則由兩個方法，其一是：根據(jù)經(jīng)驗和以前的實驗結(jié)果，直接設(shè)置一個確定的迭代次數(shù)N；其二是：將第一次得到的迭代結(jié)果、跟前面一次的迭代結(jié)果、 ，當(dāng)兩次的迭代結(jié)果變化小于某一個值時，迭代過程結(jié)束。15.4點選址問題15.4.1連續(xù)點選址問題2.折線距離準(zhǔn)則下選址（1）重心法對以總和最小為目標(biāo)函數(shù)的單一設(shè)施選址問題求解，可以采用重心法。記n個需求點的笛卡爾坐標(biāo)分別為，需求量分別為，平面內(nèi)運輸費率保持一致。要確定一個供應(yīng)點的坐標(biāo)，使總的運輸成本最小化。對于折線距離準(zhǔn)則，該問題的模型為：

15.4點選址問題15.4.1連續(xù)點選址問題顯然，問題可以拆分為兩個相似而獨立的模型：

即坐標(biāo)x和y是單獨確定的。我們只對x求解第一個模型。觀察目標(biāo)函數(shù)，可知它是連續(xù)而且分段線性的，分段區(qū)間以為界限。并且，隨著x的增大，直線的斜率是增加的。（2）網(wǎng)絡(luò)流算法無論是單一設(shè)施選址，還是多設(shè)施選址，折線距離準(zhǔn)則下的連續(xù)選址問題度可以轉(zhuǎn)化為一個圖上的最小費用最大流問題，相應(yīng)的網(wǎng)絡(luò)流算法在運輸問題一章中給出，本節(jié)主要介紹轉(zhuǎn)化過程。首先，我們著重介紹單一設(shè)施選址問題，進而擴展到多設(shè)施選址問題。觀察目標(biāo)函數(shù)：為了避免非線性問題，如下定義和：

15.4點選址問題15.4.1連續(xù)點選址問題15.4點選址問題15.4.1連續(xù)點選址問題從而有：

用上等式，先前的公式將會把非線性的函數(shù)變?yōu)榫€性來解決。

上述變換中將約束去掉了，因為目標(biāo)函數(shù)極小化以及等式約束的特點，所以最優(yōu)解中必然滿足該約束。上述變換中等式約束右邊的表示對偶問題中該約束對應(yīng)的對偶變量（以后的表述中我們不再作說明）。15.4點選址問題15.4.1連續(xù)點選址問題觀察其對偶問題：

定義如下變量：

15-12則可將對偶問題轉(zhuǎn)化為如下極小問題：

再增加下述約束顯然不影響對偶問題的可行域。

15.4點選址問題15.4.1連續(xù)點選址問題15.4點選址問題15.4.1連續(xù)點選址問題該問題實際上就是一個流量為f的最小費用流問題的線性規(guī)劃模型。、別表示弧j上的流量和單位流量產(chǎn)生的費用。0，2wj分別為弧j上流量的下限和上限。表示該網(wǎng)絡(luò)流問題的網(wǎng)絡(luò)圖如圖15-10。

圖15-10單個設(shè)施運輸網(wǎng)絡(luò)顯然，盡量安排流量流經(jīng)較小費用弧是最優(yōu)的。15.4點選址問題15.4.2離散點選址問題1.集覆蓋問題(SetCoveringProblemSCP)（1）集覆蓋問題及其復(fù)雜性給定有限集X及X上的幾個子集,集覆蓋問題就是要求子集的最小組合滿足。X中的元素稱為點，一個點稱之為被覆蓋，當(dāng)且僅當(dāng)它屬于。若每一個子集有一成本，要求總成本最小的覆蓋方案，稱為最小成本覆蓋問題。求解集覆蓋問題時，通常用矩陣A（|X|行，n列）描述覆蓋關(guān)系，表示點可以（不可以）被覆蓋。定義，其中，表示集合是否啟用。15.4點選址問題15.4.2離散點選址問題則SCP問題的線性規(guī)劃模型為：

而最小成本覆蓋問題的目標(biāo)函數(shù)為：SCP的應(yīng)用實例很多，如信息檢索方法設(shè)計，乘務(wù)員排班，最小路徑分割問題等。對乘務(wù)員排班而言，有個航班，根據(jù)航班的要求，其中若干個航班可有一組乘務(wù)員完成空乘工作，這樣的組合有四組，問如何安排，使所有航班都有乘務(wù)員且乘務(wù)員組數(shù)最少。

以下介紹集覆蓋問題的幾種算法。SCP是NP難題。對于NP難題既然沒有多項式時間算法，那么尋求有效的近似算法就很有必要。近似算法是指就問題的所有實例來說，所獲得的解距最優(yōu)解的相對誤差小于某一個固定值。15.4點選址問題15.4.2離散點選址問題（2）矩陣簡化法矩陣簡化法只是簡化問題規(guī)模的一種方法，不一定能給出最終解來。其基本思想是：按照基本規(guī)則，不斷地簡化集覆蓋問題中覆蓋矩陣A，同時增加集合進入。具體步驟如下：算法：集覆蓋問題的矩陣簡化算法input：覆蓋矩陣A（行對應(yīng)于中的點；離對應(yīng)于）。Output：以及簡化后的覆蓋矩陣，的解；為A的解。Step0：可行性檢查IfA存在一行，所有元素均為0，Then無可行解，算法終止。End15.4點選址問題15.4.2離散點選址問題（3）貪婪算法以下介紹的貪婪算法是一個近似算法。算法：貪婪算法(思想：在二分圖中的候選頂點集中選擇頂點度最大的頂點，去掉該點及其覆蓋的所有頂點，循環(huán)上述步驟，直至該圖為空。)input,Xoutput滿足；（U表示目前尚未覆蓋的點的集合）15.4點選址問題15.4.2離散點選址問題15.4點選址問題15.4.2離散點選址問題

；當(dāng)，循環(huán)以下運算：在尚未入選的集合中選擇，使其在中能覆蓋的點數(shù)最多，即最大，令，

end(while)；outputJ；15.4點選址問題15.4.2離散點選址問題（4）貪婪算法的有效性定理：對于集覆蓋問題F={}，，。用以上貪婪法獲得的解與最優(yōu)解Jopt有如下關(guān)系：

其中函數(shù)（d為正整數(shù)），（證明從略）15.4點選址問題15.4.2離散點選址問題（5）最小成本覆蓋問題的貪婪算法對于最小成本覆蓋問題F={}，，存在成本，用以下貪婪算法同樣可獲得近似解。input,Xoutput滿足；（U表示目前尚未覆蓋的點的集合）；15.4點選址問題15.4.2離散點選址問題當(dāng)，循環(huán)以下運算：在尚未入選的集合中選擇，使其在中所覆蓋點平均成本最小，即滿足，令

end(while)；outputJ；2.中心問題與中位問題（1）介紹物流配送中常見的選址問題有如下幾類：a.中心問題（Centerproblems）要選擇如干個服務(wù)點，以便與最遠的顧客距離最小。通常應(yīng)急服務(wù)系統(tǒng)選址都屬于這類問題。15.4點選址問題15.4.2離散點選址問題b.中位問題(Medianproblems)要選擇如干個服務(wù)點，以便與所有顧客的距離總和最小。c.無約束工廠選址問題(Uncapacitatedfacilitylocationproblems)從一組被選點中選出如干個用于建設(shè)工廠。工廠無生產(chǎn)能力約束，開設(shè)工廠有固定成本支出。工廠服務(wù)于顧客點有收益，要確定總收入最大的選址方案。15.4點選址問題15.4.2離散點選址問題15.4點選址問題15.4.2離散點選址問題（2）符號表述在離散選址中，常用加權(quán)無向圖來表述問題。每一節(jié)點是一需求點，有非負(fù)的需求量。每一條邊有服務(wù)成本表示邊長。問題是在圖上選擇若干個點作為服務(wù)站，為需求點提供某種服務(wù)，以便特定的目標(biāo)函數(shù)極大化或極小化。服務(wù)站可設(shè)在節(jié)點上，也可設(shè)在邊上。定義節(jié)點間最短路徑長為。若位于邊上，用表示點到點的距離，作如下定義：

又，對于點集與，定義，其含義為到集合的最小距離或服務(wù)網(wǎng)點服務(wù)于顧客的最小成本。15.4點選址問題15.4.2離散點選址問題（3）中心問題中心問題：給定圖，對于上任意點集，定義 ，求取一點集，滿足使。若，局限為頂點，即，則稱為頂點中心問題；若，局限為邊上，則稱為局部中心問題；若可為圖上任意點，則稱為絕對中心問題。對于，通常還相應(yīng)地稱為頂點p中心問題；局部p中心問題，絕對p中心問題。15.4點選址問題15.4.2離散點選址問題對于頂點單中心問題，可以計算圖的最小距離矩陣，對每行取最大值。最大值中的最小值所在行對應(yīng)的節(jié)點即為頂點單中心問題的最優(yōu)解。在下圖所示頂點單中心問題中，都是最優(yōu)解。圖15-13頂點單中心問題15.4點選址問題15.4.2離散點選址問題（4）中位問題在圖中，任意頂點存在非負(fù)實數(shù)與之對應(yīng)，存在非負(fù)實數(shù)。對于任意點集，定義 ，求使，這就是中位問題。中位問題的應(yīng)用實例很多，如建設(shè)若干個中央倉庫，以滿足各地的物資需求，使總的運輸成本最小化，見下圖。若約定，稱為頂點中位問題。15.4點選址問題15.4.2離散點選址問題圖15-17中位問題15.4點選址問題15.4.2離散點選址問題下面給出關(guān)于中位問題的一個性質(zhì)：定理：（Hakimi定理），頂點中位問題的解同時也是中位問題的解；即：中位問題至少存在一個解，所有點都位于頂點上。從而，利用上述定理，可以將中位問題簡化為頂點中位問題。15.5無能力約束設(shè)施選址問題15.5.1問題描述給定候選點集，顧客集，以及相關(guān)的成本收益數(shù)據(jù)。無能力約束設(shè)施選址問題要求在候選點集中選出若干個點作為工廠，滿足所有顧客要求，使總收入最大。一般地UFL問題包含以下要素：候選點集，顧客集，由j滿足I產(chǎn)生的收益 ，啟用j產(chǎn)生的成本，問題是求取，并為每一顧客分配唯一候選點，使凈收益最大化。下圖是一個例子，UFL也是NP難題。15.5無能力約束設(shè)施選址問題15.5.1問題描述圖15-19一個UFL問題顯然，將最后一個（0，1）約束松弛為如下約束，所得混合整數(shù)規(guī)劃與原問題是等價的。15.5無能力約束設(shè)施選址問題15.5.2UFL問題的線性規(guī)劃模型15.5無能力約束設(shè)施選址問題15.5.2UFL問題的線性規(guī)劃模型若將（）約束條件轉(zhuǎn)換為，稱為；顯然與有相同的可行解集。

分別將與中約束條件替換為。得到兩個松弛問題，分別稱為和。顯然，的可行解集是 可行解集的子集。實踐當(dāng)中，比求解效果更好，但由于約束數(shù)目較多，故計算量大些。15.5無能力約束設(shè)施選址問題15.5.3對偶問題

的對偶問題是：

其中，變量:分別對應(yīng)約束條件 ，；15.5無能力約束設(shè)施選址問題15.5.3對偶問題該對偶問題有兩種變換：1.第一種變換觀察的對偶問題：若給定，為使目標(biāo)函數(shù)最小化，滿足 ，應(yīng)使最小化，且。也就是說，

其中定義為。15.5無能力約束設(shè)施選址問題15.5.3對偶問題又 ，從而 ；進而， 。因而的對偶問題可變換為：

15.5無能力約束設(shè)施選址問題15.5.3對偶問題2.第二種變換若存在使，即 ；則存在使 。從目標(biāo)函數(shù)看，略微增加ul，目標(biāo)函數(shù)值不變。從而，對任意 的情況，總存在的解具有相同目標(biāo)函數(shù)值。又，由的對偶問題可看出，最優(yōu)解總滿足。15.5無能力約束設(shè)施選址問題15.5.3對偶問題因此，可將對偶問題的第一種變換變換為：15.5無能力約束設(shè)施選址問題15.5.4UFL的啟