軸輻式輸運(yùn)網(wǎng)絡(luò)中的選址優(yōu)化問(wèn)題研究.pdf

1、隨著經(jīng)濟(jì)全球化不斷發(fā)展，以樞紐為核心的軸輻式輸運(yùn)網(wǎng)絡(luò)是整合輸運(yùn)資源、提高資源利用率、降低輸運(yùn)成本的有效網(wǎng)絡(luò)結(jié)構(gòu)，已成為現(xiàn)代輸運(yùn)網(wǎng)絡(luò)結(jié)構(gòu)發(fā)展的主流趨勢(shì)。具有合并轉(zhuǎn)發(fā)功能的樞紐和具有運(yùn)輸流量?jī)?yōu)勢(shì)的軸線作為軸輻式輸運(yùn)網(wǎng)絡(luò)的重要組成部分，對(duì)整個(gè)網(wǎng)絡(luò)的運(yùn)營(yíng)有著重大影響，因此，合理的樞紐及軸線選址極其重要。樞紐選址問(wèn)題和軸線選址問(wèn)題是軸輻式輸運(yùn)網(wǎng)絡(luò)設(shè)計(jì)中研究選址優(yōu)化的兩大熱點(diǎn)，其中，建立符合實(shí)際的選址模型和設(shè)計(jì)高效快速的優(yōu)化算法是關(guān)鍵研究。本文對(duì)樞

2、紐選址問(wèn)題中的多分配p-樞紐中位選址和軸線選址問(wèn)題中的變折扣軸線選址進(jìn)行了深入研究，主要工作包括:
　　(1)多分配p-樞紐中位問(wèn)題的算法優(yōu)化
　　傳統(tǒng)用于求解多分配p-樞紐中位問(wèn)題的算法在尋找最優(yōu)樞紐集的過(guò)程中，需要計(jì)算每個(gè)OD(Origin-Destination)流經(jīng)過(guò)集合中任意樞紐對(duì)(Hub-pair)的中轉(zhuǎn)成本，存在大量重復(fù)計(jì)算現(xiàn)象。為此，我們提出一種存儲(chǔ)及索引的方法，即先通過(guò)預(yù)處理將每個(gè)OD流經(jīng)過(guò)所有潛在樞紐對(duì)的

3、中轉(zhuǎn)成本存儲(chǔ)起來(lái)，再在需要時(shí)直接進(jìn)行索引查找。對(duì)于索引，我們?cè)O(shè)計(jì)了一個(gè)哈希函數(shù)，它將每個(gè)潛在樞紐對(duì)映射到唯一的整型數(shù)值，建立哈希索引，從而實(shí)現(xiàn)快速查找。結(jié)合該存儲(chǔ)及索引的方法，我們實(shí)現(xiàn)了優(yōu)化的枚舉算法和優(yōu)化的禁忌搜索算法。在CAB(CivilAeronauticsBoard)標(biāo)準(zhǔn)數(shù)據(jù)集上的計(jì)算實(shí)驗(yàn)表明，對(duì)于不同的數(shù)據(jù)規(guī)模，優(yōu)化算法均能夠得到最優(yōu)解，且比傳統(tǒng)算法節(jié)約10％～25％的求解時(shí)間;當(dāng)需要選定的樞紐個(gè)數(shù)p值越大時(shí)，優(yōu)化算法節(jié)約的時(shí)

4、間越多。
　　(2)變折扣軸線選址問(wèn)題的建模及求解
　　不同于樞紐選址問(wèn)題需要確定網(wǎng)絡(luò)中最優(yōu)的樞紐節(jié)點(diǎn)，軸線選址問(wèn)題主要確定網(wǎng)絡(luò)中具有流量?jī)?yōu)勢(shì)的路段——軸線，對(duì)其進(jìn)行運(yùn)輸費(fèi)用折扣來(lái)實(shí)現(xiàn)整個(gè)網(wǎng)絡(luò)的運(yùn)輸成本優(yōu)化?，F(xiàn)有研究大都采用固定折扣的軸線，因而不能有效地針對(duì)實(shí)際網(wǎng)絡(luò)中軸線上流量差別較大的情形。為此，我們提出一個(gè)變折扣軸線選址問(wèn)題(HALPUD:HubArcLocationProblemwithUnfixedDiscounts