基于隨機場景數(shù)據(jù)的運輸網(wǎng)絡(luò)流問題模型與算法.pdf

1、本文以運輸網(wǎng)絡(luò)為研究背景，在戰(zhàn)略層面上綜合考慮運輸網(wǎng)絡(luò)流問題。具體的，考慮到運輸網(wǎng)絡(luò)中的不確定性因素對路段通行能力和站點中轉(zhuǎn)能力的影響，運用基于場景數(shù)據(jù)的離散隨機表示方法及不同場景下的唯一解約束，建立基于隨機場景數(shù)據(jù)的整數(shù)規(guī)劃模型。同時利用不確定規(guī)劃方法，探討基于隨機場景數(shù)據(jù)的隨機機會約束模型及模糊機會約束模型。為了得到原問題的近似最優(yōu)解，設(shè)計拉格朗日松弛算法和遺傳算法進行求解，最后通過數(shù)值算例驗證所提算法的有效性和計算效率。主要內(nèi)容包

2、括：
　　(1)不確定環(huán)境下基于隨機場景數(shù)據(jù)的運輸網(wǎng)絡(luò)流問題模型
　　本文提出基于場景數(shù)據(jù)表示能力參數(shù)的隨機性及用多等式表示不同場景下唯一解約束的方法，系統(tǒng)分析并建立了原問題的整數(shù)規(guī)劃模型。然后根據(jù)不確定規(guī)劃，考慮能力參數(shù)的隨機機會函數(shù)和模糊機會函數(shù)，分別建立了隨機機會約束模型和模糊機會約束模型。最后討論了特殊情形下，能力參數(shù)的隨機機會約束和模糊機會約束的確定等價類。
　　(2)拉格朗日松弛算法
　　鑒于原模型中

3、涉及復(fù)雜的能力約束和多等式唯一解約束，本文設(shè)計了拉格朗日松弛算法求解原問題的下界。首先通過引入拉格朗日乘子將復(fù)雜約束松弛到目標(biāo)函數(shù)中，然后將其依據(jù)場景數(shù)據(jù)d和商品k分解為K×D個子問題，得到的每個子問題等價于單個OD對的最短路問題，用標(biāo)號修正或標(biāo)號設(shè)定算法即可求解。為了得到該松弛對偶問題的最優(yōu)解，同時設(shè)計了次梯度算法，在迭代過程中更新拉格朗日乘子，逐步提高解的質(zhì)量。最終得到的松弛對偶問題最優(yōu)解即為原問題的一個緊下界LB*。
　　(

4、3)遺傳算法
　　為了求解原問題的近似最優(yōu)解，本文進一步設(shè)計遺傳算法，該算法首先利用分枝定界搜索策略，尋找運輸網(wǎng)絡(luò)中每個OD對滿足一定條件的潛在路徑，然后在此基礎(chǔ)上，設(shè)計了包括選擇、交叉、變異等操作的遺傳算法求解原問題的近似最優(yōu)解，該近似最優(yōu)解與拉格朗日松弛所求下界相結(jié)合，考察原問題最優(yōu)解的質(zhì)量。
　　(4)算例研究
　　為了驗證拉格朗日松弛算法與遺傳算法相結(jié)合求解原問題最優(yōu)解的有效性和計算效率，本文設(shè)計了運輸網(wǎng)絡(luò)流問