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

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

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

3、另文討論。 1解決上門取送貨調(diào)度問題的第一個模型 11模型的建立行包作為小宗貨物而言，貨源比較分散，重量輕，體積小，而且在上門取送時(shí)發(fā)生的取送距離較短(一般在城市內(nèi))，針對這些情況對問題做出假設(shè)(因送貨和取貨是一對逆問題，解決了送貨也就解決了取貨問題，所以這里只討論送貨問題。):P0為一行包運(yùn)輸單位，資源及運(yùn)力充分；Pi為需送貨的貨主點(diǎn)，(j=1，2，3，n)；對應(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、能超過L(上門送貨都是短距離運(yùn)輸，超過一定距離便無意義)。定義變量tij(ij)；對于每一pi只要符合送貨條件且已經(jīng)安排送貨路徑就有：其目標(biāo)函數(shù)為最短送貨總里程，下面來求解模型。 12模型求解對此類模型的研究成果很多，這里采用啟發(fā)式算法的節(jié)約法來求解。假設(shè)po向pi、pj各派1輛車送貨，則總里程為若裝載量及一次走行里程允許，則可按的路徑，可節(jié)約里程根據(jù)節(jié)約量可以不斷優(yōu)化初始解，最終得到最優(yōu)解。下面是節(jié)約法的算法步驟：第一步，計(jì)算節(jié)約量及各點(diǎn)之間的最短距離，制定初始解表，對每個貨主點(diǎn)派車送貨，即第二步，在初始解表中選取最大節(jié)約量及對應(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個條件均滿足則轉(zhuǎn)入第四步，否則轉(zhuǎn)入第五步。第四步，連接pi、pj，即tij=1，將修改該路徑上其他的tij：對toj=0的j，令sj=0；對的j，將路徑內(nèi)的sj相加得到新的sj。其目的是將已經(jīng)連接的貨主點(diǎn)的送貨量合并，以免下一步重新計(jì)算。第五步，在初始解表中依次查找次大的節(jié)約量及其對應(yīng)的pi，pj，若有則轉(zhuǎn)入第三步，否則轉(zhuǎn)入第六步。第六步，停止連線，得到最優(yōu)解。 13舉例設(shè)一鐵路行包部門在某一時(shí)間向貨主pj(j

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

7、km，汽車使用情況為2t車9輛，4t車1輛。接著對初始解進(jìn)行優(yōu)化，在表中找到最大節(jié)約量為15km，對應(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解決上門取送貨調(diào)度問題的第二個模型第一個模型解決了最短里程問題，但在實(shí)際中評價(jià)指標(biāo)

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