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

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

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

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

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

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

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

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

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

15-515.3集裝箱船配載優(yōu)化方法研究15.3.1集裝箱重量分布的優(yōu)化模型式中，為最輕個(gè)集裝箱的平均重量；為最重個(gè)集裝箱的平均重量；為第排(行)集裝箱重量為第行的箱位數(shù)；為集裝箱總行位數(shù)。當(dāng)機(jī)艙后部有箱位時(shí)，可將機(jī)艙范圍看成一行，以該范圍集裝箱重量取零作為約束條件。有時(shí)需要指定具體行位的裝箱方案，也可在約束條件中實(shí)現(xiàn)。式15-5還應(yīng)受條件的約束(為集裝箱的總重量)。求解時(shí)，可先按式5—5從01行開(kāi)始，采用逐行位迭代的方法，求出每一行箱位處集裝箱重量的解，然后按線性比例的方法考慮條件的約束，求出每一行箱位處集裝箱重量的最優(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)化模型在一定排水量條件下，如果事先擬定壓載和油水裝載方案，則式中只有一個(gè)變量，如果給定的最優(yōu)值，則可找到相應(yīng)最優(yōu)的。在受力優(yōu)化問(wèn)題中，可求出使得集裝箱船所受總縱彎矩最小的各行位重量分布。現(xiàn)假設(shè)各行箱位上集裝箱的重量分布服從一級(jí)優(yōu)化的結(jié)果，具體分配到各行箱位的最優(yōu)集裝箱垂向重量力矩與各行位集裝箱重量呈線性比例。實(shí)際裝載時(shí)，可能要根據(jù)情況指定某一行位的某些集裝箱必須裝于甲板上。根據(jù)集裝箱到港等情況，設(shè)有r只集裝箱限定裝于第行甲板上，重量為，其合重心距基線高，其它各行均自艙內(nèi)開(kāi)始裝。15.3集裝箱船配載優(yōu)化方法研究15.3.1集裝箱重量分布的優(yōu)化模型令，有

（m?kN）

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

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

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

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

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

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

其中，。15.4點(diǎn)選址問(wèn)題15.4.1連續(xù)點(diǎn)選址問(wèn)題

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

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

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

15.4點(diǎn)選址問(wèn)題15.4.1連續(xù)點(diǎn)選址問(wèn)題15.4點(diǎn)選址問(wèn)題15.4.1連續(xù)點(diǎn)選址問(wèn)題從而有：

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

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

定義如下變量：

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

再增加下述約束顯然不影響對(duì)偶問(wèn)題的可行域。

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

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

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

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

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

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

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

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

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

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

的對(duì)偶問(wèn)題是：

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

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

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