多商品流網(wǎng)絡(luò)問題文獻翻譯

多商品流問題〔MCF〕關(guān)鍵詞和關(guān)鍵短語：多目標(biāo)優(yōu)化，多準(zhǔn)那么決策，有效解，帕累托最優(yōu)解，非劣解，非解方案，弱效解，弱帕累托最優(yōu)解，弱非劣解，弱非解，弱效解。線性多商品流問題是一種以一系列商品和潛在網(wǎng)絡(luò)為特征的線性規(guī)劃問題。這兒指的商品是必須從一個或多個原始節(jié)點上，傳輸?shù)骄W(wǎng)絡(luò)中的另一個或多個目的節(jié)點上的商品。實際上，這些商品可能是電信網(wǎng)絡(luò)中撥出的，分銷網(wǎng)絡(luò)中的包裹，或航空公司飛行網(wǎng)絡(luò)中的飛機。每種商品都有獨特的特征，并且商品是不可互換的。也就是說，你不能同時滿足兩種商品的需求。MCF問題的目標(biāo)是通過網(wǎng)絡(luò)以最低的本錢流通商品，且要不超過每條弧的容量。提出了做線性多商品流模型和其解決方案的綜合性研究調(diào)查。整數(shù)多商品流問題〔IMCF〕是線性多商品流問題中有約束條件的一個多商品流問題，約束條件是從原點到目的的路徑只有一條。MCF和IMCF問題在許多情況下都普遍存在，例如在運輸、通信和生產(chǎn)中。多商品流問題應(yīng)用實例交通網(wǎng)絡(luò)中車輛的路徑(動態(tài)交通分配)這涉及通過流量網(wǎng)絡(luò)確定車輛從起點到其各自目的地的最小延遲路線。或者，沒有具體的容量，但弧上的容量是一個關(guān)于流量的函數(shù)。在前一種情況下，目標(biāo)函數(shù)是線性的，而后者那么是非線性的。分配系統(tǒng)規(guī)劃在這個問題上，在具有生產(chǎn)能力的幾家工廠生產(chǎn)不同的產(chǎn)品〔或商品〕。每個商品在每個客戶區(qū)都有一定的需求。通過具有有限存儲容量的區(qū)域配送中心的運輸來滿足需求。某某【28】模擬了通過配送中心將商品從制造工廠送到到客戶區(qū)域的路徑問題，即為MCF問題。進出口模型可能影響出口的因素之一是港口處理能力。某某【8】利用MCF模型來分析美國港口能力對小麥，玉米和大豆出口的影響。貨運業(yè)務(wù)的優(yōu)化某某【20】開發(fā)基于MCF的路徑和調(diào)度優(yōu)化模型，用來解決鐵路行業(yè)的規(guī)劃問題。某某【48】使用多商品流問題中的公式來研究鐵路的擁塞問題。零擔(dān)貨運中的貨物運輸問題零擔(dān)貨運的運營商必須整合許多貨物，以便更經(jīng)濟地使用車輛。這就要求建立大量碼頭來進行分貨。貨運公司通過對需求的預(yù)測來規(guī)劃每輛車輛往返碼頭的運輸路線。一旦路線固定，問題是以最少的總時間或本錢交付所有的貨物。這個問題在【17】和【24】中被定義為MCF問題?？爝f發(fā)貨問題某某【40】模擬聯(lián)邦快遞，美國郵政，聯(lián)合包裹效勞等快遞公司所面臨的貨運交付問題，作為空間和時間網(wǎng)絡(luò)上的MCF問題。電信或計算機網(wǎng)絡(luò)中的信息傳輸問題網(wǎng)絡(luò)由傳輸線路組成。每個消息發(fā)出的請求就相當(dāng)于商品。問題是以最低的本錢將信息從起始點傳到各個目的地。某某【42】為該問題提供多商品流問題中的公式。長期水力發(fā)電的優(yōu)化在這種情況下，任務(wù)是在一段時間內(nèi)確定一個水庫的水力發(fā)電量，將一段時間分為假設(shè)干間隔使得發(fā)電的預(yù)期本錢減至最小。某某【47】認(rèn)為這個問題可以建模為一個給定的流入概率密度函數(shù)的MCF問題。森林管理對于每一個規(guī)劃期，森林管理人員必須就收割的土地面積，和從這些地區(qū)收獲的木材數(shù)量，以及要開發(fā)的娛樂用地面積和建造與維護的道路網(wǎng)進行決策，以便木材的運輸和娛樂活動。這個問題已經(jīng)在【33】中定義為一個MCF問題。街道規(guī)劃某某在【26】介紹了這個問題，并將其作為一個MCF問題。目的是確定一套雙向街道，使這些網(wǎng)絡(luò)中的街道單向的總擁塞損失最小化?？臻g價格平衡〔SPE〕問題這個問題需要消費者在一般網(wǎng)絡(luò)內(nèi)的流動模型。SPE問題決定了每個市場的最正確生產(chǎn)量和消費水平，最優(yōu)流量滿足均衡性。某某在【59】將SPE問題視為MCF問題并將其解決。為了更全面了解MCF的應(yīng)用，請看到【57】、【2】、【37】。整數(shù)多商品流問題應(yīng)用實例航空機隊指派給定航班的到達和起飛時間表，對航班和一組飛機有預(yù)期需求，目標(biāo)是以最低的本錢給航班分配飛機。這個問題已經(jīng)在【31】進行了廣泛的研究。機組排班這個問題是將調(diào)度人員的本錢降至最低。在解決問題時，必須考慮工時限制和聯(lián)邦航空管理條例等因素。深入的研究見【5】、【14】。航線維護路徑問題要求單個飛機飛單個路徑以滿足維修要求，每一個航班都被分配到一架飛機上。這個問題已經(jīng)在【19】、【10】、【25】中進行了研究。帶寬分配問題要求在電信網(wǎng)絡(luò)中最好的分配帶寬，從而最大限度地提高總收入。網(wǎng)絡(luò)上的需求或呼叫就是商品，目標(biāo)是將呼叫從其來源地傳到目的地。在視頻會議的情況下，由于不允許呼叫分配，每個呼叫必須在一個網(wǎng)絡(luò)路徑上進行。這個IMCF問題在【49】中有描述?？爝f包裹流量問題例如快遞包裹交付業(yè)務(wù)中的貨物，要求每一個具有特定來源和目的地的貨物通過運輸網(wǎng)絡(luò)進行運輸。具有共同來源的每組包裹可以被認(rèn)為是一種商品，并且通常為了方便操作并確?？蛻魸M意，必須分配到單個網(wǎng)絡(luò)路徑上。這個問題在【12】中被作為IMCF問題。數(shù)學(xué)模型多商品流問題可以通過多種方式進行建模，這取決于如何定義商品。主要有三種情況：第一種是商品可能是從網(wǎng)絡(luò)節(jié)點子集中的一個節(jié)點，指向另一個子節(jié)點；第二種是它可能從某單一節(jié)點，指向網(wǎng)絡(luò)節(jié)點子集中的一個節(jié)點；最后一種是它可能從一個單一節(jié)點，指向另一個單一節(jié)點。某某【34】為每種不同情況提供了不同的模型。為了利益空間最大化，我們只會考慮最后一種情況的模型。其他情況也可以參考這里提出的模型來進行建模。我們就MCF問題提供兩種不同的公式：一種是節(jié)點弧和傳統(tǒng)公式，一種是路徑或列生成公式。MCF的定義是由節(jié)點集N和弧組A行成的網(wǎng)絡(luò)G。MCF問題中包含決策變量x，其中xijk是商品總量k中分配給弧ij的商品量〔表示為qk〕。在IMCF問題中，這些變量被限制在商品k全局部配給弧ij的費用等于弧ij的單位流量費用的qk倍，表示為cijk。對于所有的ij屬于集合A時，弧ij的容量為dij。節(jié)點i提供的商品k，表示為bik，如果i是k的起始節(jié)點，那么等于1；如果i是k的目標(biāo)節(jié)點，那么等于-1，否那么等于0minimize(1)由此(2)(3)(4)注意，在沒有限制條件的一般性情況下，我們對弧流量變量x進行了建模，其值在O到1之間。為此，我們將每種商品的需求量化為1，并相應(yīng)的調(diào)整目標(biāo)函數(shù)〔1〕和約束〔3〕中的系數(shù)。還要注意這個模型的矩形結(jié)構(gòu)。流量約束條件〔2〕形成了不重疊的區(qū)域，每個商品對應(yīng)一個。只有弧的容量約束條件〔3〕將不同商品的流量變量的值聯(lián)系了起來。相比之下，基于路徑或列生成的MCF公式具有較少的約束條件和更多的變量。再次，潛在的網(wǎng)絡(luò)G由節(jié)點集N和弧集A組成，其中qk表示商品k的數(shù)量。P(k)表示在網(wǎng)絡(luò)G中，k屬于K的中所有起始點到目的點的路徑集合。在列生成模型中，二進制決策變量表示為ypk，ypk是商品k分配到路徑p屬于P(k)的一局部。將商品k全局部配給路徑p的費用等于路徑p的單位流量費用乘以qk，表示為cpk。cpk表示在路徑p中，所有的弧ij上的cijk費用總和。如前所述，對于所有屬于A的弧ij都有容量dij。最后，如果弧ij是屬于路徑p屬于P(k)中的且對于所有k然后，路徑或列生成IMCF公式如下：minimize(5)(6)(7)(8)線性規(guī)劃化問題解決方案【37】提供了可用的多商品網(wǎng)絡(luò)流解決方案的全面研究資料?！?】和【38】也提供了這種方法的相關(guān)資料。價格指導(dǎo)分配方法，是基于MCF模型路徑上的方法。為了限制在尋找最優(yōu)解時考慮的變量的數(shù)目，使用了列生成的方法。價格指導(dǎo)分配和列生成方法的更多內(nèi)容在【22】、【41】、【61】、【18】、【45】中給出。資源指導(dǎo)分配方法是試圖通過分配商品，通過弧的容量來解決MCF問題，并解決每個商品的最小本錢問題。在【52】、【61】、【27】、【41】、【37】、【30】、【39】、【35】、【60】中可找到關(guān)于該方法的附加說明。價格和資源指導(dǎo)分配方法的優(yōu)劣比擬可以在【3】中找到。某某【4】報告說，專門的分配代碼的完成預(yù)期可以比一般的線性編程包快三到十倍。此外，某某【7】報告說，資源指導(dǎo)分配算法能夠在小問題上快速收斂，但是對于大的MCF問題，價格指導(dǎo)分配方法要優(yōu)于其他方法。某某【56】在有束約束的拉格朗日松弛法中使用次梯度方法，提出了一種能最低本錢解決多目標(biāo)流問題的高級根底方法。劃分方法通過對當(dāng)前主要局部進行劃分，以便利用底層網(wǎng)絡(luò)結(jié)構(gòu)來形成解決這類問題的單純形方法。已經(jīng)在【51】，【53】，【54】，【55】，【32】，【43】，【36】，【24】等中提供了根底劃分方法的研究資料。某某【53】提出了解決角度問題的劃分方法。某某【32】提出了一種廣義上的上邊界算法，用于解決多商品網(wǎng)絡(luò)流問題，其中用到了關(guān)于MCF問題的特殊結(jié)構(gòu)。他們的原始劃分程序，是由某某【21】開發(fā)的一個專業(yè)化的廣義上邊界程序，該程序在每一次迭代的根底上一個飽和弧只包含有一行逆矩陣。類似地，某某【44】提出了一種通用的網(wǎng)絡(luò)規(guī)劃問題的廣義上邊界算法。所有這些過程都利用了區(qū)塊對角化問題的結(jié)構(gòu)，并在降維數(shù)為m的根底上執(zhí)行了單純形法的所有步驟，其中m表示集合A的大小。內(nèi)點算法和并行計算技術(shù)也被應(yīng)用于MCF問題。內(nèi)點算法為MCF問題的多項式時間算法。最優(yōu)的時間約束條件是某某【62】提出的。某某【58】提供了一種用大規(guī)模并行計算技術(shù)來解決多商品流問題的內(nèi)點算法?！?7】和【9】中分別提供了原始和雙上升式程序，都是解決MCF問題的新啟發(fā)式程序。某某【29】使用障礙懲罰法找到多商品問題的近似最優(yōu)解，而某某【62】那么描述了一種算法，解決多商品流問題幾乎是可行的。如今，價格指導(dǎo)分配法或列生成法，如【2】，【11】，【23】，【34】中提出的方法是解決大型線性MCF問題時最廣泛使用的方法。列生成的一般思想是，在沒有明確包含約束矩陣〔稱為主問題〕中所有列〔即變量〕的情況下，可以得到線性規(guī)劃問題的最優(yōu)解。事實上，只有所有列中的小局部將處于最正確解決方案上，所有其他〔非根本〕列都可以忽略。在最小化問題中，這意味著所有降低本錢的列都可以忽略。那么多商品流問題的列生成方法就是：RMP建立。在受限制的主問題中包含一個列的子集，稱為限制主問題即RMP；RMP解決方案。解決RMP線性規(guī)劃問題；定價問題解決方案。使用解決RMP獲得的雙重變量來解決定價問題。定價問題可以識別一個或多個負(fù)本錢的列〔即價格降低的列〕，或者確定不存在這樣的列。最優(yōu)性測試。如果一個或多個列定價，請將這些列〔其中的一個子集〕添加到RMP中并返回到步驟1〕否那么停止，主問題解決。對于步驟1〕中的任何RMP，令-πij表示與約束〔6〕相關(guān)聯(lián)的非負(fù)雙重變量，σk表示與約束〔7〕相關(guān)的無限制雙重變量。由于cpk可以表示為ij∈Acijk〔9〕對于步驟1〕中生成的每個RMP解決方案，可以有效地解決步驟2〕中的定價問題。對于每個ij屬于A情況下，可以通過解決在商品k屬于K時的網(wǎng)絡(luò)中，弧本錢等于cijk+πij時的最短路徑的問題，來確定每列的定價。令p*表示商品k的最終最短路徑p主要問題解決了。否那么，MP沒有解決，那對于每個k屬于K：路徑p*?P(k整數(shù)規(guī)劃化問題解決方案有能力解決大型多商品流問題，就有方法解決大型整數(shù)多商品流問題。解決大型整數(shù)多商品流問題的成功方法是使用基于路徑或列生成的方法。列生成的線性規(guī)劃問題可以使用熟知的分支和價格的方法求解，詳見【15】、【64】、【23】。分支和價格，是一個廣義化的分支和線性規(guī)劃松弛的約束，允許列生成應(yīng)用于每個節(jié)點的分支定界樹。當(dāng)沒有列價格進入根底矩陣并且線性規(guī)劃問題解決方案不能滿足完整性條件時，分支就產(chǎn)生了。將標(biāo)準(zhǔn)分支定界程序應(yīng)用到已有的約束主問題中并不能保證最優(yōu)解〔或可行解〕。在分支修改限制住問題之后，可能存在一種情況，即為主問題提供了有利價格的列，但在限制主問題中卻沒有。因此，為了找到最優(yōu)解，我們必須保證在分支后解決定價問題的能力。在【63】中演示了，航空公司機組排班應(yīng)用程序解決初始線性規(guī)劃問題后，生成列的重要性。雖然他們無法找到可行的整數(shù)規(guī)劃問題解決方案，僅使用列生成法解決初始線性規(guī)劃松弛問題，但他們能夠使用分支和價格方法找到質(zhì)量解決方案用于機組的調(diào)度。每當(dāng)線性規(guī)劃問題的節(jié)點綁定超過預(yù)設(shè)的整數(shù)規(guī)劃問題目標(biāo)值時，附加列。執(zhí)行具有分支和約束的列生成法的難點是常規(guī)的整數(shù)規(guī)劃問題在變量上的分支可能無效,，因為固定變量可以破壞定價問題的結(jié)構(gòu)。對于多商品流問題的應(yīng)用，是需要一個分支規(guī)那么的，用來確保包含分支決策的線性規(guī)劃的定價問題可以用最短路徑法有效的解決。舉例說明一下，考慮到基于變量二分法有分支，其中一個分支將商品K指派給路徑p，即ykp=1，另一個分支不允許商品K使用路徑p，即ykp=0。第一個分支很容易執(zhí)行，因為一旦k分配給路徑p，就不需要生成額外的路徑。但是，如果將定價問題作為最短路徑問題解決，那么無法執(zhí)行后一個分支。不能保證最短路徑問題的解不是路徑p。事實上，k的最短路徑很可能是路徑p。因此，要執(zhí)行分支決策，必須使用下一個最短路徑過程來實現(xiàn)定價問題的解決方案。一般來說，對于涉及一組分支決策的子問題，必須使用第k開發(fā)分支和價格程序的關(guān)鍵是確定一個分支規(guī)那么，消除當(dāng)前的分?jǐn)?shù)解，而不會影響定價問題的易處理性。一般來說，某某等人【23】認(rèn)為，這可以通過將分支規(guī)那么基于原始公式中的變量，而不是列生成公式中的變量來實現(xiàn)。這意味著分支規(guī)那么應(yīng)該基于問題的節(jié)點弧公式中的弧流變量x。某某【15】為許多不同主問題結(jié)構(gòu)研發(fā)分支規(guī)那么。他們還調(diào)查在文獻中出現(xiàn)廣泛應(yīng)用的專業(yè)算法。某某【49】提出了帶寬包裝問題的分支和價格算法。其目的是以最大限度地提高收益的發(fā)送一套商品。他們使用基于路徑的公式。他們的分支方案選擇一個分?jǐn)?shù)路徑，并創(chuàng)立一個等于路徑長度〔以其包含的