時(shí)變網(wǎng)絡(luò)下有能力限制的行包徑路選擇問題研究.pdf

1、普包是由編掛在旅客列車上的行李車運(yùn)送的一類行包貨物。普包徑路選擇問題是按照客戶對遞送時(shí)間和費(fèi)用的要求，合理安排每批貨物的運(yùn)送車次和中轉(zhuǎn)車站，實(shí)現(xiàn)貨物的快速、安全送達(dá)，是普包運(yùn)輸組織的核心問題。 普包徑路選擇問題的重點(diǎn)和難點(diǎn)是：如何合理地設(shè)計(jì)普包運(yùn)輸網(wǎng)絡(luò)，能同時(shí)包含時(shí)間維和空間維的信息，且網(wǎng)絡(luò)規(guī)模合理、易于求解；如何合理地確定中轉(zhuǎn)站點(diǎn)和在中轉(zhuǎn)站的車次接續(xù)方案；如何保證普包徑路能滿足能力約束條件。在分析已有研究應(yīng)用于普包徑路問題的局

2、限性的基礎(chǔ)上，本文引入時(shí)變網(wǎng)絡(luò)描述普包運(yùn)輸網(wǎng)，并將普包徑路選擇問題分解為無能力約束的單一OD對普包最短路問題和考慮行李車載重能力約束的多商品流問題兩個(gè)子問題分別求解。論文主要完成了以下研究工作： (1)構(gòu)建了能夠體現(xiàn)節(jié)點(diǎn)中轉(zhuǎn)信息的時(shí)變普包運(yùn)輸網(wǎng)。 在對普包徑路選擇問題的時(shí)變特性進(jìn)行分析后，構(gòu)建了時(shí)變普包運(yùn)輸網(wǎng)。并通過對節(jié)點(diǎn)狀態(tài)的定義，在時(shí)變網(wǎng)上表達(dá)出中轉(zhuǎn)信息。 (2)研究了無能力約束的單一OD對的普包貨物最短路問

3、題。 將問題的求解分為兩個(gè)階段：首先，為避免后續(xù)計(jì)算的大量無效搜索，不考慮普包運(yùn)輸網(wǎng)絡(luò)的時(shí)變特性，尋找OD對間的可行路徑；其次，在可行路徑的求解基礎(chǔ)上，建立單一OD對普包貨物最短路問題模型，用改進(jìn)的動(dòng)態(tài)規(guī)劃算法對模型進(jìn)行求解。 (3)研究了有能力約束的普包徑路選擇問題。 考慮行李車載重能力約束，將普包徑路選擇問題描述為有能力約束的多商品流問題，建立了廣義費(fèi)用最小的多商品流模型，并借鑒車流徑路調(diào)整的方法設(shè)計(jì)了求解算