鐵路行包上門(mén)取送貨的調(diào)度問(wèn)題研究

1、    摘要：從鐵路行包運(yùn)輸中上門(mén)取送貨物的現(xiàn)狀出發(fā)，提出了取送貨物的調(diào)度問(wèn)題，并建立了2個(gè)模型。2個(gè)模型的目標(biāo)函數(shù)分別是最少走行里程和最少噸公里數(shù)。應(yīng)用節(jié)約法求解出2個(gè)模型的最優(yōu)解，得到最優(yōu)取送路徑。最后比較2個(gè)模型的結(jié)果，指出它們分別適用的條件及應(yīng)用范圍。在市場(chǎng)經(jīng)濟(jì)條件下，社會(huì)對(duì)小宗貨物及高附加值小宗貨物的快速運(yùn)輸需求日益增長(zhǎng)，鐵路行包市場(chǎng)在此背景下也被激活，并且持續(xù)發(fā)展。公路、航空等運(yùn)輸方式的激烈競(jìng)爭(zhēng)更促使鐵路行包運(yùn)輸部門(mén)必須提供更多更好的服務(wù)來(lái)擴(kuò)大市場(chǎng)，提高份額，增加競(jìng)爭(zhēng)力。服務(wù)是針對(duì)貨主需求來(lái)完善的。傳統(tǒng)的行包運(yùn)輸中貨主自己送貨、自己取貨，這中

2、間還有許多繁雜的手續(xù)，貨主希望從這些繁雜的事物中解脫出來(lái)，要運(yùn)輸部門(mén)實(shí)現(xiàn)門(mén)到門(mén)服務(wù)，上門(mén)取送貨。中鐵快運(yùn)公司雖然開(kāi)始適應(yīng)市場(chǎng)的要求，并取得較好的效果，但送取貨的路徑選擇還只是憑借司機(jī)的經(jīng)驗(yàn)，而且取送貨物的車輛調(diào)度也有不合理之處；各類代理企業(yè)也積極地展開(kāi)上門(mén)服務(wù)，但苦于車輛不足，運(yùn)力有限，不能很好地解決問(wèn)題；鐵路客運(yùn)行包房根本就沒(méi)有開(kāi)展此類服務(wù)，還是采用傳統(tǒng)方式，因而更加缺乏競(jìng)爭(zhēng)力，不符合市場(chǎng)化的需要；而專門(mén)運(yùn)送貨物的公司卻苦于沒(méi)有更多的市場(chǎng)，浪費(fèi)了大量的運(yùn)力。在這些現(xiàn)狀下研究并解決鐵路行包上門(mén)取送貨的調(diào)度問(wèn)題很有必要。送取貨有很多情況，以下研究的是一輛車只送貨或只取貨，對(duì)同一輛車既送又取的情況

3、另文討論。 1解決上門(mén)取送貨調(diào)度問(wèn)題的第一個(gè)模型 11模型的建立行包作為小宗貨物而言，貨源比較分散，重量輕，體積小，而且在上門(mén)取送時(shí)發(fā)生的取送距離較短(一般在城市內(nèi))，針對(duì)這些情況對(duì)問(wèn)題做出假設(shè)(因送貨和取貨是一對(duì)逆問(wèn)題，解決了送貨也就解決了取貨問(wèn)題，所以這里只討論送貨問(wèn)題。):P0為一行包運(yùn)輸單位，資源及運(yùn)力充分；Pi為需送貨的貨主點(diǎn)，(j=1，2，3，n)；對(duì)應(yīng)每貨主點(diǎn)的送貨量為si(j=1，2，3，n)；dij(i,j=0，1， 2，3，,n且)為pi與pj之間的最短距離；送貨車輛按裝載量的大小分為m種，其中裝載量為wi的汽車有xi輛(i=1，2，3，n)，且每輛送貨車每次送貨走行里程不

4、能超過(guò)L(上門(mén)送貨都是短距離運(yùn)輸，超過(guò)一定距離便無(wú)意義)。定義變量tij(ij)；對(duì)于每一pi只要符合送貨條件且已經(jīng)安排送貨路徑就有：其目標(biāo)函數(shù)為最短送貨總里程，下面來(lái)求解模型。 12模型求解對(duì)此類模型的研究成果很多，這里采用啟發(fā)式算法的節(jié)約法來(lái)求解。假設(shè)po向pi、pj各派1輛車送貨，則總里程為若裝載量及一次走行里程允許，則可按的路徑，可節(jié)約里程根據(jù)節(jié)約量可以不斷優(yōu)化初始解，最終得到最優(yōu)解。下面是節(jié)約法的算法步驟：第一步，計(jì)算節(jié)約量及各點(diǎn)之間的最短距離，制定初始解表，對(duì)每個(gè)貨主點(diǎn)派車送貨，即第二步，在初始解表中選取最大節(jié)約量及對(duì)應(yīng)的貨主點(diǎn)pi、pj。第三步，判斷是否滿足下面條件：toi>

5、;0且toj>0；toi=2或toj=2；pi,pj未分配在同一路徑；將分別送貨的si、sj改為采用裝載量大于si+sj的車，并調(diào)整車輛使用情況，以免已用車超出可使用的車輛數(shù)。若4個(gè)條件均滿足則轉(zhuǎn)入第四步，否則轉(zhuǎn)入第五步。第四步，連接pi、pj，即tij=1，將修改該路徑上其他的tij：對(duì)toj=0的j，令sj=0；對(duì)的j，將路徑內(nèi)的sj相加得到新的sj。其目的是將已經(jīng)連接的貨主點(diǎn)的送貨量合并，以免下一步重新計(jì)算。第五步，在初始解表中依次查找次大的節(jié)約量及其對(duì)應(yīng)的pi，pj，若有則轉(zhuǎn)入第三步，否則轉(zhuǎn)入第六步。第六步，停止連線，得到最優(yōu)解。 13舉例設(shè)一鐵路行包部門(mén)在某一時(shí)間向貨主pj(j

6、=1，2，3，10)上門(mén)送貨，貨物重量為sj(j=1，2，3，10)；pi與pj之間的最短距離為dij(i，j=0，1，2，3，10)；可利用的車輛的載重有2t和4t，數(shù)量分別為5、5，且汽車的一次巡回路徑所走里程不能超過(guò)30km。具體數(shù)值見(jiàn)送貨網(wǎng)絡(luò)圖(見(jiàn)圖1)：圖1中貨主點(diǎn)兩點(diǎn)問(wèn)的連線上的數(shù)字表示公路里程(km)，靠近貨主點(diǎn)的數(shù)字表示貨物重量(t)。現(xiàn)在來(lái)求解最優(yōu)送貨方案。根據(jù)所給數(shù)值得到節(jié)約量表(見(jiàn)表1)：表1中第1列是貨物重量，第2列以后的每格中逗號(hào)前的數(shù)字表示節(jié)約量逗號(hào)后的數(shù)字表示最短距離(dij)。先制定初始解：假設(shè)向每一貨主各派1輛汽車單獨(dú)送貨，并按原路返回。此方案的總里程為148

7、km，汽車使用情況為2t車9輛，4t車1輛。接著對(duì)初始解進(jìn)行優(yōu)化，在表中找到最大節(jié)約量為15km，對(duì)應(yīng)的pi、pj為pl、p2，用條件進(jìn)行檢驗(yàn)均滿足，故連接pl和p2,得sl=31=sl+s2=03+28)，s2=31(sl)，t01=1，t02=1,t12=1。得到第一次優(yōu)化解，該解比初始解減少的里程數(shù)等于節(jié)約量，即15km，總里程為148-15=133km，汽車的使用情況為2t車8輛，4t車1輛。按照前面的優(yōu)化步驟反復(fù)優(yōu)化得到最優(yōu)解，送貨總里程為80km，車輛使用情況為2t車1輛，4t車2輛。送貨路徑為： 2解決上門(mén)取送貨調(diào)度問(wèn)題的第二個(gè)模型第一個(gè)模型解決了最短里程問(wèn)題，但在實(shí)際中評(píng)價(jià)指標(biāo)

8、還有貨物噸公里的大小，也就是在貨物取送量一定的情況下，使得貨物的噸公里最小，才能更有實(shí)效地降低運(yùn)輸費(fèi)用。現(xiàn)在對(duì)第一個(gè)模型進(jìn)行改進(jìn)，將目標(biāo)函數(shù)定為噸公里數(shù)，并使得噸公里數(shù)為最少，修改約束條件便可得到問(wèn)題的第二個(gè)模型：(wij為從pi到pj之間的車輛的實(shí)際裝載量）約束條件同第一個(gè)模型。仍以第一個(gè)模型的例子來(lái)求解。顯而易見(jiàn)，送貨量大的對(duì)整個(gè)噸公里數(shù)影響要大，因此可優(yōu)先送貨，然后再考慮其他貨主點(diǎn)。這樣就要修改第一個(gè)模型的一些求解條件。先選出送貨量大的貨主點(diǎn)，將它們的數(shù)字標(biāo)號(hào)寫(xiě)入集合F=中，其中f表示貨主點(diǎn)的標(biāo)號(hào)，例中的。初始解不變，把第一個(gè)模型求解步驟的第三步中的條件2改為：其他不變，在初始解表中按已修改的方法進(jìn)行優(yōu)化，可得到新的結(jié)果：送貨的總里程為90km，貨物噸公里數(shù)為1003，車輛使用情況為：2t車1輛，4t車3輛，送貨的路徑為： 32種模型的分析比較及結(jié)論第1個(gè)模型的送貨總里程為80km，貨物噸公里數(shù)為1275，第2個(gè)模型的送貨總里程為90km，貨物噸公里數(shù)為1003。2種模型的結(jié)果相比較可以看出，后者雖然總里程增加了10km，但噸公里數(shù)減少了22，幅度比較大。這