本論文研究了供需匹配與多批次取送貨車輛路徑問(wèn)題。在此問(wèn)題中,客戶點(diǎn)之間的供需匹配關(guān)系事先未知;每個(gè)客戶點(diǎn)的取貨請(qǐng)求和送貨請(qǐng)求允許通過(guò)多次訪問(wèn)該客戶點(diǎn)來(lái)分批次滿足;需做供需匹配決策和車輛路徑?jīng)Q策。此問(wèn)題是經(jīng)典車輛路徑問(wèn)題的一種復(fù)雜衍生體,普遍存在于國(guó)際原油運(yùn)輸、煙草制造行業(yè)中的生產(chǎn)原料調(diào)撥、零售行業(yè)中的商品庫(kù)存重新布局及共享單車系統(tǒng)中的自行車重新分配等網(wǎng)絡(luò)中�；诖藛�(wèn)題高度復(fù)雜且受到的關(guān)注較少,本文分別從模型建立、啟發(fā)式算法求解和精確算法求解的角度對(duì)此問(wèn)題進(jìn)行深入研究。本文的主要研究成果呈現(xiàn)如下:(1)本文所研究的問(wèn)題包含了兩個(gè)相互影響的決策:供需匹配和車輛路徑。先建立一個(gè)混合整數(shù)線性規(guī)劃模型作為基礎(chǔ)模型。然后,通過(guò)消除兩個(gè)決策變量之間的耦合關(guān)系,提出一個(gè)新穎的單元化模型。緊接著,提出一系列多項(xiàng)式型有效不等式來(lái)加強(qiáng)單元化模型。實(shí)驗(yàn)結(jié)果表明,單元化模型比基礎(chǔ)模型更容易求解,且所提出的有效不等式顯著地提高了單元化模型的性能。最后,驗(yàn)證了所提出的模型和不等式對(duì)文獻(xiàn)中相關(guān)問(wèn)題的有效性。(2)為快速求解現(xiàn)實(shí)中的較大規(guī)模的問(wèn)題,基于所提出的單元化模型,先設(shè)計(jì)一個(gè)貪婪式算法來(lái)構(gòu)建初始解。然后,基于優(yōu)化... 

【文章來(lái)源】：華中科技大學(xué)湖北省 211工程院校 985工程院校 教育部直屬院校

【文章頁(yè)數(shù)】：132 頁(yè)

【學(xué)位級(jí)別】：博士

【部分圖文】：

圖１－１研究的技術(shù)路線??１．４論文總體結(jié)構(gòu)與主要內(nèi)容??

目前煙草行業(yè)中的生產(chǎn)原料調(diào)運(yùn)模式也屬于單次訪問(wèn)的情況。直觀上看，允??許＂多次訪問(wèn)＂（即單車多次訪問(wèn)一個(gè)客戶點(diǎn)）使得問(wèn)題的優(yōu)化空間更大，帶來(lái)更多??的經(jīng)濟(jì)效益。如圖３－１所示，假設(shè)網(wǎng)路中有３個(gè)王廠、４種生產(chǎn)原料且車輛的最大裝??載量為３個(gè)單位。每個(gè)工廠的供應(yīng)信息和需求信息如列＂供應(yīng)＂／＂需求＂所示，其??中括號(hào)中的數(shù)值表示生產(chǎn)原料的供應(yīng)／需求量。所有車輛必須從車場(chǎng)出發(fā)，執(zhí)行運(yùn)輸??任務(wù)后返回到車場(chǎng)且每輛車最多被使用一次。在單次訪問(wèn)模式下（如圖３－１?（ａ）所??示），需要兩輛車來(lái)滿足所有工廠的需求，路線分別是：車場(chǎng)一工廠１?一工廠２?—??工廠３?—車場(chǎng)（實(shí)線部分）和車場(chǎng)一工廠３?—工廠１?一工廠２?—車場(chǎng)（虛??線部分）。車輛從一個(gè)工廠到另一個(gè)工廠的裝載信息呈現(xiàn)在兩個(gè)工廠之間的連線上。??然而，在多次訪問(wèn)模式下（如圖３－１?（ｂ）所示），Ｗ上兩條路線可Ｗ合并。即只需一??輛車就能完成運(yùn)輸任務(wù)且相應(yīng)的路線為；車場(chǎng)一工廠１?一工廠２?—工廠３?—工??廠１?一工廠２?—車場(chǎng)。與單次訪問(wèn)的調(diào)運(yùn)模式相比，單車訪問(wèn)了工廠１和工廠２??兩次。顯然，多次訪問(wèn)模式下的調(diào)運(yùn)方案比單次訪問(wèn)模式下的運(yùn)輸方案需要更少的??運(yùn)輸車輛和運(yùn)輸成本。因此，多次訪問(wèn)模式下的調(diào)運(yùn)方案更優(yōu)。??原料：＾一畫?＜３

一個(gè)＂單元化＂方法來(lái)化簡(jiǎn)基礎(chǔ)模型，把化簡(jiǎn)后的模型稱作＂單元化＂模型。??單元化方法的主要思想是頂點(diǎn)拆分。為了方便，本文用＂節(jié)點(diǎn)＂表示從原頂點(diǎn)??拆分出的子頂點(diǎn)。圖３－２通過(guò)列舉一個(gè)簡(jiǎn)單的例子來(lái)說(shuō)明頂點(diǎn)拆分過(guò)程。圖３－２中的??頂點(diǎn)供應(yīng)２種產(chǎn)品，需求２種產(chǎn)品。??巧點(diǎn)?Ｉ?（供應(yīng)?１?個(gè)單位）▲??供應(yīng)?節(jié)點(diǎn)２?（供應(yīng)１個(gè)單位）▲??節(jié)點(diǎn)３?（供應(yīng)１個(gè)單位）▲??／Ｊｉ＾?Ａ?（ｇ）節(jié)點(diǎn)４?（供腳個(gè)單位）參??／?３個(gè)單位?＼?節(jié)點(diǎn)５?（供應(yīng)１個(gè)單位）＞????－?叫??ｍｍ?紛?節(jié)點(diǎn)６?（需求３個(gè)單位）??３?個(gè)單位??需求?（＃＾?巧點(diǎn)７?（需求２個(gè)單位）〇??圖３－２?—個(gè)頂點(diǎn)的拆分過(guò)程??基于Ｗ上頂點(diǎn)拆分過(guò)程，每個(gè)頂點(diǎn)根據(jù)供應(yīng)和需求信息，拆分成一個(gè)或兩個(gè)節(jié)點(diǎn)??集合。這些節(jié)點(diǎn)和原頂點(diǎn)的位置坐標(biāo)相同。其中一個(gè)為供應(yīng)節(jié)點(diǎn)集合，該集合中的每??個(gè)節(jié)點(diǎn)只供應(yīng)一種產(chǎn)品且供應(yīng)量為１。因此，拆分出的供應(yīng)節(jié)點(diǎn)數(shù)等于原頂點(diǎn)針對(duì)所??有產(chǎn)品的總供應(yīng)量。另一個(gè)為需求節(jié)點(diǎn)集合，在該集合中，每個(gè)節(jié)點(diǎn)只需求一種產(chǎn)品??且需求量等于原頂點(diǎn)對(duì)該種產(chǎn)品的需求量。因此，拆分出的需求節(jié)點(diǎn)個(gè)數(shù)等于原頂點(diǎn)??■所需的產(chǎn)品類型數(shù)。例如，在圖３－２中，該頂點(diǎn)供應(yīng)５個(gè)單位的產(chǎn)品，需求２種產(chǎn)品??類型


本文編號(hào)：2922910