多商品流網(wǎng)絡(luò)問題文獻(xiàn)翻譯(word文檔良心出品)

1、多商品流問題（MCF）關(guān)鍵詞和關(guān)鍵短語：多目標(biāo)優(yōu)化，多準(zhǔn)則決策，有效解，帕累托最優(yōu) 解，非劣解，非解方案，弱效解，弱帕累托最優(yōu)解，弱非劣解，弱非解，弱效解。線性多商品流問題是一種以一系列商品和潛在網(wǎng)絡(luò)為特征的線性規(guī)劃問題。這兒指的商品是必須從一個(gè)或多個(gè)原始節(jié)點(diǎn)上，傳輸?shù)骄W(wǎng)絡(luò)中的 另一個(gè)或多個(gè)目的節(jié)點(diǎn)上的商品。實(shí)際上，這些商品可能是 電信網(wǎng)絡(luò)中 撥出的電話，分銷網(wǎng)絡(luò)中的包裹，或航空公司飛行網(wǎng)絡(luò)中的飛機(jī)。每種商品都有獨(dú)特的特征，并且商品是不可互換的。也就是 說，你不能同時(shí)滿足兩種商品的需求。MCF問題的目標(biāo)是通過網(wǎng)絡(luò)以最低的成本流通商品，且要不超過每條弧的容量。提出了做線性多商品流模型和其解決方案

2、的綜 合性研究調(diào)查。整數(shù)多商品流問題（IMCF）是線性多商品流問題中有約束條件的一個(gè)多商品流問題，約束條件是從原點(diǎn)到目的的路徑只有一條。MCF和IMCF問題在許多情況下都普遍存在，例如在運(yùn)輸 通信 和生產(chǎn)中。多商品流問題應(yīng)用實(shí)例交通網(wǎng)絡(luò)中車輛的路徑（動(dòng)態(tài)交通分配）這涉及通過流量網(wǎng)絡(luò)確定車輛從起點(diǎn)到其各自目的地的最小延 遲路線。或者，沒有具體的容量，但 弧上的容量是一個(gè)關(guān)于流量的函數(shù)。在前一種情況下，目標(biāo)函數(shù)是線性 的，而后者則是非線性的。分配系統(tǒng)規(guī)劃 在這個(gè)問題上，在具有已知生產(chǎn)能力的幾家工廠生產(chǎn)不同的產(chǎn)品（或 商品）。每個(gè)商品在每個(gè)客戶區(qū)都有一定的需求。通過具有有限存儲(chǔ)容量 的區(qū)域配送中心的

3、運(yùn)輸來滿足需求。某某【28模擬了通過 配送中心將商 品從制造工廠送到到客戶區(qū)域的路徑問題，即為MCF問題。進(jìn)出口模型可能影響出口的因素之一是港口處理能力。某某【8利用MCF模型 來分析美國港口能力對(duì)小麥，玉米和大豆出口的影響。貨運(yùn)業(yè)務(wù)的優(yōu)化某某【20開發(fā)基于MCF的路徑和調(diào)度優(yōu)化模型，用來解決鐵路 行業(yè)的規(guī)劃問題。某某【48】使用多商品流問題中的公式來研究鐵路的擁 塞問題。零擔(dān)貨運(yùn)中的貨物運(yùn)輸問題零擔(dān)貨運(yùn)的運(yùn)營商必須整合許多貨物，以 便更經(jīng)濟(jì)地使用車輛。這就要求建立大量碼頭來進(jìn)行分貨。貨運(yùn)公司通過 對(duì)需求的預(yù)測來規(guī)劃每輛車輛往返碼頭的運(yùn)輸路線。一旦路線固定，問 題是以最少的總時(shí)間或成本交付所有

4、的貨物。這個(gè)問題在【17】和24中被定義為MCF問題?？爝f發(fā)貨問題 某某【40】模擬聯(lián)邦快遞，美國郵政，聯(lián)合包裹服務(wù)等快遞公司所面臨的貨運(yùn)交付問題，作為空間和時(shí)間網(wǎng)絡(luò)上的MCF問題。電信或計(jì)算機(jī)網(wǎng)絡(luò)中的信息傳輸問題網(wǎng)絡(luò)由傳輸線路組成。每個(gè)消息發(fā)出的請(qǐng)求就相當(dāng)于商品。問題是 以最低的成本將信息從起始點(diǎn)傳到各個(gè)目的地。某某【42】為該問題提供 多商品流問題中的公式。長期水力發(fā)電的優(yōu)化在這種情況下，任務(wù)是在一段時(shí)間內(nèi)確定一個(gè)水庫的水力發(fā)電量，將 一段時(shí)間分為若干間隔使得發(fā)電的預(yù)期成本減至最小。某某【47】認(rèn)為這個(gè)問題可以建模為一個(gè)給定的流入概率密度函數(shù)的 MCF問題。森林管理 對(duì)于每一個(gè)規(guī)劃期，森林

5、管理人員必須就收割的土地面積，和從這些地區(qū)收獲的木材數(shù)量，以及要開發(fā)的娛樂用地面積和建造與維護(hù) 的道路網(wǎng)進(jìn)行決策，以便木材的運(yùn)輸和娛樂活動(dòng)。這個(gè)問題已經(jīng)在【33】中定義為一個(gè)MCF問題。街道規(guī)劃某某在【26介紹了這個(gè)問題，并將其作為一個(gè)MCF問題。目的是確定一套雙向街道，使這些網(wǎng)絡(luò)中的街道單向的總擁塞損失最小化。空間價(jià)格平衡（SPE問題這個(gè)問題需要消費(fèi)者在一般網(wǎng)絡(luò)內(nèi)的流動(dòng)模型。SPE問題決定了每個(gè)市場的最佳生產(chǎn)量和消費(fèi)水平，最優(yōu)流量滿足均衡性。某某在【59】 將SPE問題視為MCF問題并將其解決。為了更全面了解MCF的應(yīng)用，請(qǐng)看到【57】、【2】、【37】。整數(shù)多商品流問題應(yīng)用實(shí)例航空機(jī)隊(duì)指派

6、 給定航班的到達(dá)和起飛時(shí)間表，對(duì)航班和一組飛機(jī)有預(yù)期需求，目標(biāo)是以最低的成本給航班分配飛機(jī)。這個(gè)問題已經(jīng)在【31進(jìn)行了廣泛的研 究。機(jī)組排班這個(gè)問題是將調(diào)度人員的成本降至最低。在解決問題時(shí)，必須考慮工時(shí)限制和聯(lián)邦航空管理?xiàng)l例等因素。深入的研究見【5】、14 o航線維護(hù)路徑問題 要求單個(gè)飛機(jī)飛單個(gè)路徑以滿足維修要求，每一個(gè)航班都被分配到一架飛機(jī)上。這個(gè)問題已經(jīng)在【19】、【10】、25中進(jìn)行了研究。帶寬分配問題 要求在電信網(wǎng)絡(luò)中最好的分配帶寬，從而最大限度地提高總收入。網(wǎng)絡(luò)上的需求或呼叫就是商品，目標(biāo)是將呼叫從其來源地傳到目的地。在視 頻電話會(huì)議的情況下，由于不允許呼叫分配，每個(gè)呼叫必須在一個(gè)網(wǎng)

7、絡(luò) 路徑上進(jìn)行。這個(gè)IMCF問題在【49】中有描述?？爝f包裹流量問題例如快遞包裹交付業(yè)務(wù)中的貨物，要求每一個(gè)具有特定來源和目的地的貨物通過運(yùn)輸網(wǎng)絡(luò)進(jìn)行運(yùn)輸。具有共同來源的每組包裹可以被 認(rèn)為是一種商品，并且通常為了方便操作并確?？蛻魸M意，必須分配到單個(gè)網(wǎng)絡(luò)路徑上。這個(gè)問題在【12】中被作為IMCF問題。數(shù)學(xué)模型多商品流問題可以通過多種方式進(jìn)行建模，這取決于如何定義商品。主要有三種情況：第一種是商品可能是從網(wǎng)絡(luò)節(jié)點(diǎn)子集中的一個(gè) 節(jié)點(diǎn)，指向另一個(gè)子節(jié)點(diǎn)第二種是它可能從某單一節(jié)點(diǎn),指向網(wǎng)絡(luò)節(jié)點(diǎn)子集中的一個(gè)節(jié)點(diǎn)；最后一種是它可能從一個(gè)單一節(jié)點(diǎn)，指向另一個(gè)單一節(jié) 點(diǎn)。某某【34】為每種不同情況提供了不同

8、的模型。為了利益空間最大 化，我們只會(huì)考慮最后一種情況的模型。其他情況也可以參考這里提出的 模型來進(jìn)行建模。我們就MCF問題提供兩種不同的公式：一種是節(jié)點(diǎn)弧和傳統(tǒng)公 式，一種是路徑或列生成公式。MCF的定義是由節(jié)點(diǎn)集N和弧組A行成的網(wǎng) 絡(luò)G。MCF問題中包含決策變量x,其中Xk是商品總量k中分配給弧ij的 商品量（表示為q9。在IMCF問題中，這些變量被限制 在二進(jìn)制下。商品k全部分配給弧ij的費(fèi)用等于弧ij的單位流量費(fèi)用的qk倍，表示為 Cko對(duì)于所有的ij屬于集合A時(shí)，弧ij的容量為djjo節(jié)點(diǎn)i提供的商品k,表 示為b*如果i是k的起始節(jié)點(diǎn)，則等于1;如果i是k的目標(biāo)節(jié)點(diǎn)，則等于1,否則

9、等于0。節(jié)點(diǎn)弧MCF公式為：(1)V V L L minimize ) cAq ijeA由此二爲(wèi)ViG NKKi(3)注意，在沒有限制條件的一般性情況下，我們對(duì)弧流量變量x進(jìn)行了建模，其值在0到1之間。為此，我們將每種商品的需求量化為1,并 相應(yīng)的調(diào)整目標(biāo)函數(shù)(1)和約束(3)中的系數(shù)。還要注意 這個(gè)模型的矩 形結(jié)構(gòu)。流量約束條件(2)形成了不重疊的區(qū)域，每 個(gè)商品對(duì)應(yīng)一個(gè)。只 有弧的容量約束條件(3)將不同商品的流量變 量的值聯(lián)系了起來。相比之下，基于路徑或列生成的MCF公式具有較少的約束條件和更多的變量。再次，潛在的網(wǎng)絡(luò)G由節(jié)點(diǎn)集N和弧集A組成，其中qk表示 商品k的數(shù)量。P (k)表示在

10、網(wǎng)絡(luò)G中，k屬于K的中所有起 始點(diǎn)到目的 點(diǎn)的路徑集合。在列生成模型中，二進(jìn)制決策變量表示為？霧，？ ？?是商品k分配到路徑p屬于P (k)的一部分。將商品k全部分配 給路徑p的費(fèi)用 等于路徑P的單位流量費(fèi)用乘以qk,表示為？舁?表 示在路徑p中，所有 的弧ij上的？?費(fèi)用總和。如前所述，對(duì)于所有屬 于A的弧ij都有容量？?？ 最后，如果弧ij是屬于路徑p屬于P (k)中的且對(duì)于所有k都屬于K, 則？?等于1；否則等于0。然后，路徑或列生成IMCF公式如下:E 展5卩(可工 52 q 秋硝 s dij, Vij 6 A.kEKpeP(k)(8)J/J 0, PpEPg Vt e K.線性規(guī)劃化

11、問題解決方案【37】提供了可用的多商品網(wǎng)絡(luò)流解決方案的全面研究資料?！?】和【38】也提供了這種方法的相關(guān)資料。價(jià)格指導(dǎo)分配方法，是基于MCF模型路徑上的方法。為了限制 在尋 找最優(yōu)解時(shí)考慮的變量的數(shù)目，使用了列生成的方法。價(jià)格指導(dǎo) 分配和 列生成方法的更多內(nèi)容在【22】、【41】、【61】、【18、【45】 中給出。資源指導(dǎo)分配方法是試圖通過分配商品，通過弧的容量來解決MCF問題，并解決每個(gè)商品的最小成本問題。在【52】、【61】、27、【41】、【37】、【30】、【39】、【35】、【60中可找到關(guān)于該方法的附加 說明。價(jià)格和資源指導(dǎo)分配方法的優(yōu)劣比較可以在【3】中找到。某某【4】報(bào)告說

12、，專門的分配代碼的完成預(yù)期可以比一般的線性編程包 快三 到十倍。此外，某某【7報(bào)告說，資源指導(dǎo)分配算法能夠在小問題上快 速收斂，但是對(duì)于大的MCF問題，價(jià)格指導(dǎo)分配方法要優(yōu)于其他方法。某某【56在有束約束的拉格朗日松弛法中使用次梯度方法，提出 了一種能最低成本解決多目標(biāo)流問題的高級(jí)基礎(chǔ)方法。劃分方法通過對(duì)當(dāng)前主要部分進(jìn)行劃分,以便利用底層網(wǎng)絡(luò)結(jié)構(gòu)來形成解決這類問題的單純形方法。已經(jīng)在【51】,【53】,【54】,【55】,32,【43】，【36】，【24等中提供了基礎(chǔ) 劃分方法的研究資料。某某【53】提出了解決角度問題的劃分方法。某某【32提出了一種廣 義上的上邊界算法，用于解決多商品網(wǎng)絡(luò)流問

13、題, 其中用到了關(guān)于MCF問題的特殊結(jié)構(gòu)。他們的原始劃分程序，是由某某【21開發(fā)的一 個(gè)專業(yè)化的廣義上邊界程序，該程序在每一次迭代的基礎(chǔ)上一個(gè)飽和弧 只包含有一行逆矩陣。類似地，某某【44】提出了一種通用的網(wǎng)絡(luò)規(guī)劃 問題的廣義上邊界算法。所有這些過程都利用了區(qū)塊對(duì)角化問題的結(jié) 構(gòu)，并在降維數(shù)為m的基礎(chǔ)上執(zhí)行了單純形法的所有步驟，其中m表示 集合A的大小。內(nèi)點(diǎn)算法和并行計(jì)算技術(shù)也被應(yīng)用于MCF問題。內(nèi)點(diǎn)算法為MCF 問題的多項(xiàng)式時(shí)間算法。最優(yōu)的時(shí)間約束條件是某某【62提出的。某 某【58】提供了一種用大規(guī)模并行計(jì)算技術(shù)來解決多商品流問題的內(nèi)點(diǎn)算 法?！?7】和【9】中分別提供了原始和雙上升式程序

14、，都是解決MCF 問題的新啟發(fā)式程序。某某【29使用障礙懲罰法找到多商品問題的近 似最優(yōu)解，而某某【62】則描述了一種算法，解決多商品流問題幾乎是 可行的。如今，價(jià)格指導(dǎo)分配法或列生成法，如【2】，11 ,23,【34中提出的方法是解決大型線性MCF問題時(shí)最廣泛使用的方法。 列生成的一般思想是，在沒有明確包含約束矩陣（稱為主問題）中所有列 （即變量）的情況下，可以得到線性規(guī)劃問題的最優(yōu)解。事實(shí)上，只有所 有列中的小部分將處于最佳解決方案上，所有其他（非基本）列都可以忽 略。在最小化問題中，這意味著所有降低成本的列都可以忽略。那么多 商品流問題的列生成方法就是：0） RMP建立。在受限制的主問題

15、中包含一個(gè)列的子集，稱為限制主問題即RMP;1）RMP解決方案。解決RMP線性規(guī)劃問題；2）定價(jià)問題解決方案。使用解決RMP獲得的雙重變量來解決定價(jià)問 題。定價(jià)問題可以識(shí)別一個(gè)或多個(gè)負(fù)成本的列（即價(jià)格降低的歹U）,或者確定不存在這樣的列。3）最優(yōu)性測試。如果一個(gè)或多個(gè)列定價(jià)，請(qǐng)將這些列（其中的一個(gè)子集）添加到RMP中并返回到步驟1）否則停止，主問題 解 決。對(duì)于步驟1）中的任何RMP,令-?表示與約束（6）相關(guān)聯(lián)的非負(fù)雙 重變量，？ ？?表示與約束（7）相關(guān)的無限制雙重變量。由于？?可以表示 為爲(wèi)?？ ？ ? ?商品k的p列的降低成本？ ?,是：訝二1知+切）曙-六（9）對(duì)于步驟1）中生成的每

16、個(gè)RMP解決方案，可以有效地解決步 驟2）中的定價(jià)問題。對(duì)于每個(gè)ij屬于A情況下，可以通過解決在商品k屬于K時(shí)的網(wǎng)絡(luò)中弧成本等于？?的最短路徑的問題，來確定每列的定價(jià)。令？ ？表示商品k的最終最短路徑？ ?o那么，如果所有的k屬于K時(shí):主要問題解決了。否則，MP沒有解決，那對(duì)于每個(gè)k屬于K：詩才 O,路徑？ ?（被添加到步驟3中的限制主要問題中。整數(shù)規(guī)劃化問題解決方案有能力解決大型多商品流問題，就有方法解決大型整數(shù)多商品流問 題。解決大型整數(shù)多商品流問題的成功方法是使用基于路徑或列生成的方 法。列生成的線性規(guī)劃問題可以使用熟知的分支和價(jià)格的方法求解，詳見【15】、641、23 o分支和價(jià)格，是

17、一個(gè)廣義化的分支和線性規(guī) 劃松弛的約束，允許列生成應(yīng)用于每個(gè)節(jié)點(diǎn)的分支定界樹。當(dāng)沒有列價(jià)格 進(jìn)入基礎(chǔ)矩陣并且線性規(guī)劃問題解決方案不能滿足完整性條件時(shí)，分支就 產(chǎn)生了。將標(biāo)準(zhǔn)分支定界程序應(yīng)用到已有的約束主問題中并不能保證最優(yōu)解（或可行解）。在分支修改限制住問題之后，可能存在一種情況，即為主 問題提供了有利價(jià)格的列，但在限制主問題中卻沒有。因此，為了找到最 優(yōu)解，我們必須保證在分支后解決定價(jià)問題的能力。在【63】中演示 了，航空公司機(jī)組排班應(yīng)用程序解決初始線性規(guī)劃問題后，生成列的重要性。雖然他們無法找到可行的整數(shù)規(guī)劃問題解決方案，僅使 用列生成法解決初始線性規(guī)劃松弛問題，但他們能夠使用分支和價(jià)格方

18、 法找到質(zhì)量解決方案用于機(jī)組的調(diào)度。每當(dāng)線性規(guī)劃問題的節(jié)點(diǎn)綁定超 過預(yù)設(shè)的整數(shù)規(guī)劃問題目標(biāo)值時(shí)，附加列。執(zhí)行具有分支和約束的列生成法的難點(diǎn)是常規(guī)的整數(shù)規(guī)劃問題在變量 上的分支可能無效，因?yàn)楣潭ㄗ兞靠梢云茐亩▋r(jià)問題的結(jié)構(gòu)。對(duì)于多 商品流問題的應(yīng)用，是需要一個(gè)分支規(guī)則的，用來確保包含分支決策的線性規(guī)劃的定價(jià)問題可以用最短路徑法有效的解決。舉例說 明一下，考慮到基于變量二分法有分支，其中一個(gè)分支將商品K指派給 路徑P，即？?=7,另一個(gè)分支不允許商品K使用路徑p,即？ =0。第一個(gè) 分支很容易執(zhí)行，因?yàn)橐坏﹌分配給路徑p,就不需要生成額 外的路徑。 但是，如果將定價(jià)問題作為最短路徑問題解決，則無法執(zhí)

19、 行后一個(gè)分支。不 能保證最短路徑問題的解不是路徑p。事實(shí)上，k的最短路徑很可能是路徑P。因此，要執(zhí)行分支決策，必須使用下一個(gè)最 短路徑過程來實(shí)現(xiàn)定價(jià)問題的解決方案。一般來說，對(duì)于涉及一組分支 決策的子問題，必須使用第k個(gè)最短路徑過程來實(shí)現(xiàn)定價(jià)問題的解決方 案。開發(fā)分支和價(jià)格程序的關(guān)鍵是確定一個(gè)分支規(guī)則，消除當(dāng)前的分?jǐn)?shù) 解,而不會(huì)影響定價(jià)問題的易處理性。一般來說，某某等人【23認(rèn)為,這可以通過將分支規(guī)則基于原始公式中的變量，而不是列生成公式 中的變量來實(shí)現(xiàn)。這意味著分支規(guī)則應(yīng)該基于問題的節(jié)點(diǎn)弧公式中的弧 流變量X。某某【15】為許多不同主問題結(jié)構(gòu)研發(fā)分支規(guī)則。他們還調(diào)查 在文獻(xiàn)中出現(xiàn)廣泛應(yīng)用的專業(yè)算法。某某【49】提出了帶寬包裝問題的分支和價(jià)格算法。其目的是以最 大限度地提高收益的發(fā)送一套商品。他們使用基于路徑的公式。他們的 分支方案選擇一個(gè)分?jǐn)?shù)路徑，并創(chuàng)建一個(gè)等于路徑長度（以其包含的弧的數(shù)量為單位）的新的子問題。在