物流配送車輛調(diào)度問題畢業(yè)設(shè)計

1、蘭 州 商 學(xué) 院本科生畢業(yè)論文（設(shè)計）論文（設(shè)計）題目： 物流配送車輛調(diào)度問題 學(xué) 院、 系： 信息工程學(xué)院 數(shù)學(xué)系 專 業(yè) (方 向)： 信息與計算科學(xué)專業(yè) 年 級、 班： 2008級信息與計算科學(xué)班 學(xué) 生 姓 名： 陳海燕 指 導(dǎo) 教 師： 王國興 _年 月 日聲 明本人鄭重聲明：所呈交的畢業(yè)論文（設(shè)計）是本人在導(dǎo)師的指導(dǎo)下取得的成果。對本論文（設(shè)計）的研究做出重要貢獻(xiàn)的個人和集體，均已在文中以明確方式標(biāo)明。因本畢業(yè)論文（設(shè)計）引起的法律結(jié)果完全由本人承擔(dān)。本畢業(yè)論文（設(shè)計）成果歸蘭州商學(xué)院所有。 特此聲明畢業(yè)論文（設(shè)計）作者簽名： 年 月 日物流配送車輛調(diào)度問題摘 要隨著經(jīng)濟(jì)全球化和

2、網(wǎng)絡(luò)信息技術(shù)發(fā)展步伐的加快，現(xiàn)代物流作為一個新的經(jīng)濟(jì)增長點引起了全社會廣泛的關(guān)注。作為客戶服務(wù)的直接手段，物流配送無疑是現(xiàn)代物流管理中的重要環(huán)節(jié)，配送線路的合理與否對配送速度、運營成本及經(jīng)濟(jì)效益影響很大。采用科學(xué)合理的方法確定配送路線，是物流配送活動中非常重要的工作，對提高企業(yè)服務(wù)質(zhì)量，增強(qiáng)企業(yè)的競爭力具有重要的意義。車輛優(yōu)化調(diào)度問題(vehicle scheduling problem簡稱vsp)是物流配送中的最為核心的內(nèi)容，它是一個典型的np難題，涉及到運籌學(xué)、應(yīng)用數(shù)學(xué)，組合優(yōu)化、圖論與網(wǎng)絡(luò)分析、計算機(jī)軟件、計算機(jī)應(yīng)用、物流科學(xué)、運輸管理等眾多學(xué)科領(lǐng)域。vsp是運籌學(xué)與組合優(yōu)化領(lǐng)域的前沿與

3、研究熱點問題，對它的研究為組合優(yōu)化理論與方法的發(fā)展有著積極的推動作用。本文在已有數(shù)學(xué)模型的基礎(chǔ)上，提出了適合制造企業(yè)實際需求的物流配送車輛調(diào)度問題模型的目標(biāo)函數(shù)和約束條件，建立了無時限的純裝或純卸的非滿載車輛調(diào)度問題模型。在解決問題的過程中，對經(jīng)典的節(jié)約算法進(jìn)行適當(dāng)?shù)男拚?，結(jié)合dijkstra單源最短路徑算法，求得滿足實際需求的可行解。關(guān)鍵詞 物流配送 車輛優(yōu)化調(diào)度問題 節(jié)約算法 dijkstra算法 abstractalong with the economic globalization and the network information technique stepping up,

4、the modern logistics catches the whole social attention extensively as a new economy growth point. being the direct means of the customer service, the model logistics is the important tache in the modern logistics undoubtedly, whether the distribution route is reasonable or not, it has great influen

5、ce on distribution rate, transport cost and economic benefit. it is a very important work in the logistics distribution activity to constitute the distribution route by scientific and reasonable methods. it is significant meaning to raise the enterprise service quantity and strengthen the enterprise

6、 competition. the vehicle scheduling problem is the very core of the content in the logistics scopes, it is a typical np-hard problem, involving in many research subjects such as operations research, applied mathematics, combinatorial optimization, transportation network analysis, computer software,

7、 computer applications, logistics science management, etc. vsp becomes advanced and hot spots in the field of operations research and combinatorial optimization research, researches for vsp can promote actively the development of the theory and method of combinatorial optimization.the research based

8、 on the mathematics model, the target function and subject condition for logistics vehicle scheduling problem model is presented which adapt to the actual request of manufacturing. the non-full loaded pure pickup or pure delivery without time windows model is builded. in the course of solving proble

9、m, the c-w saving methods is modified properly and combines with the dijkstra single-source shortest path algorithm, which the feasible result for the actual requests is analysied.key words logistics distrubution, vehicle scheduling problem, c-w savings methods, dijkstra methods目 錄一、引言1二、物流配送業(yè)務(wù)概述3（一

10、）物流配送概述3（二）物流配送產(chǎn)生的原因61、消費者消費行為的變化62、生產(chǎn)商生產(chǎn)策略的轉(zhuǎn)變63、零售商向連鎖經(jīng)營發(fā)展的趨勢74、無在庫經(jīng)營的傾向7（三）物流配送的流程81、物流配送的主要操作82、物流配送的一般流程11三、物流車輛調(diào)度現(xiàn)狀12（一）物流車輛調(diào)度模式12（二）物流車輛調(diào)度存在問題分析14四、基本問題17（一）圖的基本概念17（二）最短路問題18（三）旅行商問題191、問題概述192、tsp的數(shù)學(xué)模型19五、物流配送車輛優(yōu)化調(diào)度模型及求解算法21（一）物流配送車輛優(yōu)化調(diào)度問題的提出21（二）dijkstra單源最短路徑算法原理及實現(xiàn)流程211、dijkstra單源最短路徑算法的基

11、本原理212、dijkstra單源最短路徑算法實現(xiàn)流程22（三）無時限的純裝或純卸非滿載vsp實現(xiàn)241、節(jié)約算法基本原理242、節(jié)約算法實現(xiàn)流程253、應(yīng)用舉例27六、總結(jié)30參考文獻(xiàn)32致 謝33物流配送車輛調(diào)度問題一、引言當(dāng)前，現(xiàn)代物流已被公認(rèn)為是企業(yè)在降低物質(zhì)消耗、提高勞動生產(chǎn)率以外創(chuàng)造利潤的第三個重要源泉，也是企業(yè)降低生產(chǎn)經(jīng)營成本，提高產(chǎn)品市場競爭力的重要途徑，據(jù)專家測算，現(xiàn)代物流成本約占企業(yè)經(jīng)營成本的30-50%，當(dāng)一個有效的物流系統(tǒng)與企業(yè)主要商業(yè)系統(tǒng)集成之后，可使倉儲量降低50%，準(zhǔn)時交貨率提高40%，營業(yè)收入增加10%以上1。在經(jīng)濟(jì)發(fā)達(dá)國家和一些經(jīng)濟(jì)水平較高的發(fā)展中國家，現(xiàn)代物

12、流水平己成為影響企業(yè)競爭力的關(guān)鍵因素1,2 。與發(fā)達(dá)國家相比，我國的物流產(chǎn)業(yè)效率較低1。根據(jù)全國第三產(chǎn)業(yè)普查資料，我國交通運輸、倉儲、代理和批發(fā)等行業(yè)的成本費用之和占國民生產(chǎn)總值的比重為15%左右，如果考慮其它相關(guān)流通環(huán)節(jié)的費用和流通過程中的物流損失，則全社會物流費用支出約占國民生產(chǎn)總值的20%以上，而美國的全社會物流費用支出僅占其國民生產(chǎn)總值的10%左右。另據(jù)有關(guān)資料，目前我國一般工業(yè)品從產(chǎn)品出廠經(jīng)過裝卸、儲存、運輸?shù)雀鱾€物流環(huán)節(jié)到消費者手中的流通費用約占商品價格的50%左右；而新鮮水果、易變質(zhì)食品、某些化工產(chǎn)品的流通費用有的高達(dá)商品售價的70-80%；我國汽車零配件的生產(chǎn)中，其加工裝配時間

13、僅占2%，而98%的時間是原材料、零配件的儲存、裝卸和搬運時間。在各種產(chǎn)品的生產(chǎn)和流通環(huán)節(jié)中還有大量原材料、零部件和產(chǎn)品的“庫存”3。這些費用和時間上的消耗以及大量存在的庫存正是潛在的實施物流管理的領(lǐng)域，為物流的發(fā)展留下了巨大的空間。在這種形勢下，研究如何通過實施科學(xué)的物流管理，以提高物流效率、降低物流成本、提高服務(wù)質(zhì)量是十分必要的。物流配送是現(xiàn)代化物流中的一個重要環(huán)節(jié)，它是指按客戶(包括零售商、用戶等)的訂貨要求(包括貨物種類、數(shù)量和時間等方面的要求)，在物流中心(也稱物流基地、物流據(jù)點，包括配送中心、倉庫、車站、港口等)進(jìn)行分貨、配貨工作，并將配好的貨物及時送交收貨人的物流活動。物流配送過

14、程主要包括以下作業(yè)環(huán)節(jié)：從生產(chǎn)工廠進(jìn)貨或運達(dá)并集結(jié)的集貨作業(yè)；根據(jù)各個客戶的不同需求，在物流中心將所需要的貨物挑選出來的分貨和配貨作業(yè)；考慮配送貨物的重量和體積，充分利用車輛的載重和容積的貨物配裝作業(yè)；合理確定車輛配送路線并及時送貨的作業(yè)?？梢姡锪髋渌褪且环N集集貨、分貨、配貨、配裝、送貨等多種功能為一體的物資流通方式。在物流配送業(yè)務(wù)中，存在許多優(yōu)化決策的問題，車輛優(yōu)化調(diào)度問題涉及面較廣，需要考慮的因素較多，本文將著重研究物流配送車輛調(diào)度的一般問題。國外將物流配送車輛調(diào)度問題歸結(jié)為vrp ( vehicle routing problem，即車輛路徑問題)和vsp (vehicle sched

15、uling problem，即車輛調(diào)度問題)，該問題于1959年由dantzig和ramse提出后4 ：很快便引起運籌學(xué)、應(yīng)用數(shù)學(xué)、組合數(shù)學(xué)、圖論與網(wǎng)絡(luò)分析、物流科學(xué)、計算機(jī)應(yīng)用等學(xué)科的專家以及運輸計劃制定者的極大重視，并一直是運籌學(xué)與組合優(yōu)化領(lǐng)域的前沿與熱點問題。vrp與vsp是根據(jù)問題的空間特性和時間特性的相對重要性來劃分的，一般認(rèn)為當(dāng)不考慮時間要求，僅根據(jù)空間位置安排線路的稱為routing，根據(jù)時間要求安排線路的稱為scheduling，同時考慮空間位置和時間要求的稱為routing和scheduling混合問題，也有不區(qū)分兩者的，若有具體約束則加上定語，例如將有時間要求的車輛調(diào)度問題

16、稱為vehicle routing problem with time windows。在現(xiàn)實應(yīng)用中，由于scheduling涉及的內(nèi)容和關(guān)鍵技術(shù)比routing寬泛，因此絕大多數(shù)研究者的主要研究興趣集中在scheduling問題上，且主要對車輛調(diào)度問題(vehicle scheduling problem簡稱vsp)開展廣泛的研究。在現(xiàn)實生產(chǎn)和生活中1，郵政投遞問題、飛機(jī)、鐵路車輛、水運船舶及公共汽車的調(diào)度問題、電力調(diào)度問題、管道鋪設(shè)問題、計算機(jī)網(wǎng)絡(luò)拓?fù)湓O(shè)計問題都可以抽象為物流配送車輛調(diào)度問題。因此，將物流配送車輛調(diào)度問題作為研究對象具有一定的理論和現(xiàn)實意義。二、物流配送業(yè)務(wù)概述（一）物流配

17、送概述配送的概念有多種表述。日本工業(yè)標(biāo)準(zhǔn)表述，將貨物從物流結(jié)點送交收貨人。日本1991年版物流手冊的表述:生產(chǎn)廠到配送中心之間的物品空間移動叫“運輸”，從配送中心到顧客之間的物品空間移動叫“配送”。美國物流管理供應(yīng)鏈過程一體化表述:實物配送這一領(lǐng)域涉及將制成品交給顧客的運輸。實物配送過程，可以使顧客服務(wù)的時間和空間的需求成為營銷的一個整體組成部分我國現(xiàn)代物流學(xué)表述:配送是以現(xiàn)代送貨形式實現(xiàn)資源最終配置的經(jīng)濟(jì)活動；按用戶訂貨要求，在配送中心或其他物流結(jié)點進(jìn)行的貨物配備并以最合理方式送交用戶。一般認(rèn)為物流配送是指物流過程的中轉(zhuǎn)型送貨(也稱為二次輸送、支線輸送、終端輸送)。也就是在產(chǎn)品用戶集中區(qū)域，

18、按用戶的訂貨要求和時間計劃，在物流中心配貨并將配好的貨物采用汽車巡回運送的方式交收貨人的小范圍、近距離、小批量、多品種、為用戶服務(wù)的運輸3。配送不是單純的運輸或送貨，而是運輸與其它活動的組成，除了各種“運”、“送”活動外，還要從事大量的集貨、分貨、配貨、配裝等工作，是配與送的結(jié)合。對于配送的深入認(rèn)識，應(yīng)當(dāng)掌握以下幾個要點:(1)配送的資源配置作用配送是“最終配置”，因而是接近顧客的配置。對于現(xiàn)代企業(yè)而言，“接近顧客”是至關(guān)重要的。美國蘭德公司對“幸?！彪s志所列的五百家大公司進(jìn)行一項調(diào)查表明“經(jīng)營戰(zhàn)略和接近顧客至關(guān)重要”，所以接近顧客的配送，自然取得了它在現(xiàn)代經(jīng)濟(jì)中的地位。(2)配送的實質(zhì)是送貨

19、配送的主要經(jīng)濟(jì)活動，尤其是接近顧客的經(jīng)濟(jì)活動是送貨。(3)配送是現(xiàn)代送貨現(xiàn)代兩個字表述了和舊式送貨的區(qū)別。其區(qū)別主要在于:)一般送貨可以是一種偶然的行為，而配送卻是一種體制行為，是市場經(jīng)濟(jì)的一種體制形式。)一般送貨是完全被動的服務(wù)行為，而配送則是有一定組織形式的計劃行為。)配送依靠現(xiàn)代生產(chǎn)力，依靠科技進(jìn)步支撐，實現(xiàn)對用戶的送貨服務(wù)。(4)配送是“配”和“送”有機(jī)結(jié)合的形式配送利用有效的分揀、配貨等理貨工作，使送貨達(dá)到一定的規(guī)模，以利用規(guī)模優(yōu)勢取得較低的送貨成本。如果不進(jìn)行分揀、配貨，有一件運一件，需要一點送一點，這就會加大送貨成本。所以，追求整個配送的優(yōu)勢，分揀、配貨等工作是必不可少的。(5)

20、配送是市場經(jīng)濟(jì)產(chǎn)物配送是在市場經(jīng)濟(jì)條件下，在“供大于求”的買方市場環(huán)境中所派生的一種形式。 在買方市場環(huán)境下，用戶具有選擇權(quán)，而賣方需要通過有效的服務(wù)來售出自己的產(chǎn)品，爭奪一塊份額，這就形成了有提供者、有需求者的理想市場環(huán)境，使配送得以發(fā)展。(6)配送以用戶的要求為出發(fā)點“按用戶的訂貨要求”明確了用戶的主導(dǎo)地位。配送是從用戶利益出發(fā)，按用戶要求進(jìn)行的一種活動，因此，在觀念上必須明確“用戶第一”、“質(zhì)量第一”。配送企業(yè)的地位是服務(wù)地位而不是主導(dǎo)地位，不能從本企業(yè)利益出發(fā)，而應(yīng)從用戶利益出發(fā)，在滿足用戶利益基礎(chǔ)上取得本企業(yè)的利益。更重要的是，不能利用配送損傷或控制用戶，不能利用配送作為部門分割、行

21、業(yè)分割、割據(jù)市場的手段。 (7)以最“合理的方式”的提法是基于這樣一種考慮:過分強(qiáng)調(diào)“按用戶要求”是不妥的，受用戶本身的局限，要求有時候存在不合理性，在這種情況下會損失自我或雙方的利益。對于配送而言，應(yīng)當(dāng)在時間、速度、服務(wù)水平、成本、數(shù)量等多方面尋求最優(yōu)，實現(xiàn) “雙贏”的原則。（二）物流配送產(chǎn)生的原因配送作為先進(jìn)的物流形式，它的產(chǎn)生以及推廣并不是偶然的，而是隨著現(xiàn)代商業(yè)經(jīng)營環(huán)境和經(jīng)營形式的變化而出現(xiàn)的。這些變化主要體現(xiàn)在:1、消費者消費行為的變化隨著人們生活水平的提高，20世紀(jì)90年代以來，人們對生活的追求已逐漸從原來的溫飽型、數(shù)量型轉(zhuǎn)向小康型，對生活質(zhì)量的要求越來越高。伴隨著這種生活觀念的變

22、化，在經(jīng)濟(jì)社會向國際化、信息化急劇轉(zhuǎn)變的基礎(chǔ)上，消費者價值觀趨于多元化和多樣化，喜歡購買具有差別化的商品。這種消費行為變化對企業(yè)的生產(chǎn)和經(jīng)營產(chǎn)生了深遠(yuǎn)的影響，使生產(chǎn)和銷售企業(yè)在適應(yīng)消費者消費行為變化的過程中，開始強(qiáng)化物流管理，通過少批量、多品種、快速化、柔性化的生產(chǎn)和經(jīng)營來滿足消費者的需求。2、生產(chǎn)商生產(chǎn)策略的轉(zhuǎn)變在傳統(tǒng)消費模式中，當(dāng)新產(chǎn)品被廠家研制、開發(fā)出來后，通過各種各樣的媒體、特別是電視廣告等促銷手段的運用和商業(yè)推廣，其一般能喚起全國規(guī)模的需求，這種營銷模式背后隱含的是消費者具有“與他人一致”的消費意識。與這種消費者相對應(yīng)，零售業(yè)以百貨業(yè)和綜合超市為中心，通過大量購進(jìn)、大量陳列廉價的商品

23、來推動銷售額的增長。但是隨著消費個性化、多樣化的發(fā)展，原來那種商品在一部分人中開始流行后，大家爭相購買的情況會越來越少，而且流行商品的生命周期也越來越短。在這種狀況下，廠家要準(zhǔn)確預(yù)測特定商品的流行程度十分困難。此外，基本生活品在全社會普及之后，商品在質(zhì)量上的稍微改進(jìn)或價格的稍微降低都不能大量激發(fā)消費者的購買欲望，因而能開發(fā)出具有爆發(fā)性需求規(guī)模的革新產(chǎn)品也會越來越困難。 正因為如此，如今很多廠商都在積極開展多品種戰(zhàn)略，即將原來的產(chǎn)品加以改良，附加各種機(jī)能，形成產(chǎn)品間微妙的差異，積極開展多品種生產(chǎn)戰(zhàn)略。3、零售商向連鎖經(jīng)營發(fā)展的趨勢在傳統(tǒng)的流通模式下，商品從制造商生產(chǎn)出來后，經(jīng)由層層的批發(fā)商再到零

24、售商，最后到達(dá)消費者手上，批發(fā)商在此扮演著整個通路的樞紐作用。隨著消費形態(tài)的改變，整個市場成為消費者導(dǎo)向，這種趨勢迫使企業(yè)改變傳統(tǒng)的經(jīng)營方式，建立新的競爭策略，許多制造商為了將自己生產(chǎn)的產(chǎn)品直接輸往末端市場，紛紛構(gòu)建自有的通路體系，這使得超級市場、便利點、連鎖店一時之間快速成長。伴隨著連鎖經(jīng)營的興起，配送服務(wù)的重要性越來越為人們所關(guān)注。4、無在庫經(jīng)營的傾向零售業(yè)中與消費個性化、多樣化以及廠商多品種生產(chǎn)相對應(yīng)，無論在既存的零售業(yè)態(tài)百貨店和超市中，還是新型的24小時店等新業(yè)態(tài)中，經(jīng)營的商品品種數(shù)越來越多。但是，與此同時，由于政策、環(huán)境、房地產(chǎn)價格等原因，店鋪的規(guī)模和倉庫規(guī)模不可能無限擴(kuò)大，特別是在

25、大都市中，由于人口密度大、地價高昂、消費更新快、環(huán)境規(guī)制嚴(yán)格等原因，更加限制了倉儲點和倉儲空間的擴(kuò)大，在這種情況下，只有提高店內(nèi)管理效率，通過加快商品周轉(zhuǎn)來抵消倉儲空間不足等問題。如今，在國際上，大型零售業(yè)的方針均已從原來通過開設(shè)新店尋求外延型發(fā)展，轉(zhuǎn)向充實內(nèi)部管理和投資，積極探索內(nèi)涵型發(fā)展。除此之外，推動無在庫經(jīng)營的原因是，由于消費行為的多樣化、個性化發(fā)展，商品品牌、品種、式樣的急劇增多，使零售商對顧客實際需求的預(yù)測十分困難。在這種狀況下，庫存越大，零售企業(yè)承擔(dān)的資金占用和滯銷風(fēng)險也越大，因此為了加速資金周轉(zhuǎn)和降低風(fēng)險，零售企業(yè)必須盡可能地壓縮庫存，實現(xiàn)實時銷售。具體看，現(xiàn)代零售業(yè)的管理重點

26、是：)實行“單品管理”，迅速制定經(jīng)營中的“暢銷品”與“滯銷品”，以此為基礎(chǔ)確定定貨商品的種類和數(shù)量。)實行“無在庫經(jīng)營”，在有限的空間里陳列更多的商品，降低銷售風(fēng)險，極力抑制各類商品的在庫量，徹底實現(xiàn)在庫管理和在庫成本的削減。（三）物流配送的流程1、物流配送的主要操作(1)備貨配送的準(zhǔn)備工作和基礎(chǔ)工作。備貨工作包括籌集貨源、訂貨、采購、集貨、進(jìn)貨及有關(guān)的質(zhì)量檢查、結(jié)算、交接等。配送的優(yōu)勢之一就是可以集中若干用戶的需求進(jìn)行一定規(guī)模的備貨。備貨是決定配送成敗的初期工作，如果備貨成本太高，會大大降低配送的效益。(2)儲存配送中的儲存有儲備及暫存兩種形態(tài):)儲備 配送儲備是按一定時期的配送經(jīng)營要求，形

27、成的對配送的資源保證。這種類型的儲備數(shù)量較大，儲備結(jié)構(gòu)也較完善，視貨源及到貨情況，可以有計劃地確定周轉(zhuǎn)儲備及保險儲備結(jié)構(gòu)及數(shù)量。配送的儲備保證有時在配送中心附近單獨設(shè)庫解決。)暫存另一種儲存形態(tài)是暫存，是具體執(zhí)行配送時，按分揀配貨要求在理貨場地所做的少量儲存準(zhǔn)備。由于總體儲存效益取決于儲存總量，所以這部分暫存數(shù)量只會對工作方便與否造成影響，而不會影響儲存的總效益，因而在數(shù)量上控制并不嚴(yán)格。還有另一種形式的暫存，即是分揀、配貨之后，形成的發(fā)送貨載的暫存，這個暫存主要是調(diào)節(jié)配貨與送貨的節(jié)奏，暫存時間不長。(3) 分揀及配貨這是配送不同于其他物流形式的有特點的功能要素，也是配送成敗的一項重要支持性工

28、作。分揀及配貨是完善送貨、支持送貨的準(zhǔn)備性工作，是不同配送企業(yè)在送貨時進(jìn)行競爭和提高自身經(jīng)濟(jì)效益的必然延伸，所以，也可以說是送貨向高級形式發(fā)展的必然要求。有了分揀及配貨，就會大大提高送貨服務(wù)水平，所以，分揀及配貨是決定配送系統(tǒng)水平的關(guān)鍵要素。(4)配裝在單個用戶配送數(shù)量不能達(dá)到車輛的有效載運負(fù)荷時，就存在如何集中不同用戶的配送貨物，進(jìn)行搭配裝載以充分利用運能、運力的問題，這就需要配裝。和一般送貨不同之處在于，通過配裝可以大大提高送貨水平及降低送貨成本，所以配裝也是配送系統(tǒng)中有現(xiàn)代特點的功能要素，是現(xiàn)代配送不同于傳統(tǒng)送貨的重要區(qū)別之處。(5)配送運輸配送運輸屬于運輸中的末端運輸、支線運輸，和一般

29、運輸形態(tài)主要區(qū)別在于:配送運輸是較短距離、較小規(guī)模、頻度較高的運輸形式，一般使用汽車和其他小型車輛做運輸工具。與干線運輸?shù)牧硪粋€區(qū)別是，配送運輸路線選擇問題是一般干線運輸所沒有的，干線運輸?shù)母删€是惟一的運輸線，而配送運輸由于配送用戶多，一般城市交通路線又較復(fù)雜，如何組成最佳路線，如何使配裝和路線有效搭配等，是配送運輸?shù)奶攸c，也是難度較大的工作。(6)送達(dá)服務(wù) 配好的貨運輸?shù)接脩暨€不算配送工作的完結(jié)，這是因為送達(dá)貨和用戶接貨往往還會出現(xiàn)不協(xié)調(diào)，使配送前功盡棄。因此，要圓滿地實現(xiàn)運到交貨的移交，并有效地、方便地處理相關(guān)手續(xù)并完成結(jié)算，還應(yīng)講究卸貨地點、卸貨方式等。送達(dá)服務(wù)也是配送獨具的特殊性。 (

30、7)配送加工在配送中，配送加工這一功能要素不具有普遍性，但是往往是有重要作用的功能要素。主要原因是通過配送加工，可以大大提高用戶的滿意程度并提高被配送貨物的附加價值。配送加工是流通加工的一種，但配送加工有它不同于一般流通加工的特點，即配送加工一般只取決于特殊用戶要求，其加工的目的較為單一。(8)回程在執(zhí)行完配送的使命之后，車輛需要回程，在一般情況下，回程車輛往往是空駛，這是降低配送效益、提高配送成本的因素之一。在規(guī)劃配送路線時，回程路線應(yīng)當(dāng)盡量縮短；在進(jìn)行穩(wěn)定的、計劃配送時，回程車輛可將包裝物、廢棄物、殘次品運回集中處理，或者將用戶的產(chǎn)品運回配送中心，作為配送中心的資源，向其他用戶進(jìn)行配送。2

31、、物流配送的一般流程不同的配送對象有不同的配送流程，但一般來說，物流配送的流程可用圖1表示： 訂貨協(xié)議/貨物運到驗貨 退貨代理協(xié)議理貨 廢棄物的處理訂單履行 暫存包裝、疏通、加工 驗貨/揀選上貨架 配貨發(fā)貨區(qū)暫存發(fā)貨發(fā)貨圖1物流配送的一般流程三、物流車輛調(diào)度現(xiàn)狀（一）物流車輛調(diào)度模式物流車輛調(diào)度過程是整個物流過程中重要的步驟，在降低運輸成本上有著關(guān)鍵的作用。但是目前，我國貨物運輸車輛調(diào)度方法比較落后，多采用傳統(tǒng)的人工方法編制調(diào)度方案。目前仍然被大多數(shù)公司采用的車輛調(diào)度模式，是一種基于傳統(tǒng)設(shè)備和調(diào)度員、駕駛員經(jīng)驗的調(diào)度模式，并且由于很多物流企業(yè)的一部分車輛的所有權(quán)不屬于物流企業(yè)，這一部分車輛的所

32、有權(quán)屬于車主，車主帶車加入物流企業(yè)，完成所分配的任務(wù)并且按照所完成的任務(wù)數(shù)量來得到收入，車主與物流企業(yè)并不屬于從屬的關(guān)系，加大了管理的難度。所以，調(diào)度決策者只對駕駛員分配和安排調(diào)度任務(wù)，對路徑的選擇很多情況下都由司機(jī)憑經(jīng)驗做出選擇。這種調(diào)度模式的基本過程如下:(1)集貨過程:集貨有專門負(fù)責(zé)的車輛來完成，由于在集貨過程中，貨物主要來自物流點周圍，所以根據(jù)貨物來自于不同區(qū)域把為物流企業(yè)集貨服務(wù)的車輛分為不同的組別，比如某公司把該公司專門負(fù)責(zé)集貨的車輛分為4個組，分別負(fù)責(zé)來自周邊4個市區(qū)的貨物的集結(jié)任務(wù)。當(dāng)顧客向該物流公司提出運輸需求時，調(diào)度管理人員便電話通知相應(yīng)的車主，之后車主便去完成相應(yīng)的任務(wù)。

33、(2)聯(lián)系收獲人:對于一部分貨物，貨主會在提出運輸需求的同時提出該貨物的目的地和到達(dá)目的地的準(zhǔn)確時間。對于另一部分貨物而言，物流公司調(diào)度管理人員就會及時與收貨人進(jìn)行聯(lián)系，確認(rèn)交貨的時間和地點。在服務(wù)過程中出現(xiàn)問題時，最重要的就是要及時與顧客及時溝通，協(xié)商解決。(3)貨物的存放:貨物被送到公司所屬的倉庫后，根據(jù)貨物的去向和出貨的先后順序存放于倉庫中。把未知出貨去向和時間的貨物放于倉庫的其他角落。(4)送貨過程:物流公司把專門用來負(fù)責(zé)送貨的車輛分為兩種，第一種為長途送貨車輛;第二種為市內(nèi)配送車輛。第一類車輛由于運輸距離遠(yuǎn)、載重噸位大、購買費用高，所以這一部分車輛大多屬于公司的固定資產(chǎn);第二類車輛負(fù)

34、責(zé)武漢市內(nèi)的貨物配送，這一部分車輛大多不屬于物流公司。在第二類車輛中，物流公司又把它們分為4個組，分別負(fù)責(zé)來自周邊4個地區(qū)的貨物的配送任務(wù)。當(dāng)?shù)挠兴拓浫蝿?wù)時，調(diào)度管理人員會電話通知車主，車主開車到倉庫后裝貨，然后把貨物按要求送到其收貨人指定地點卸貨，收貨人檢查貨物的完整性后簽字確認(rèn)完成運輸任務(wù)。從上述所說的物流車輛調(diào)度過程，我們可以知道，這些物流企業(yè)中的車輛調(diào)度其實只分配了運輸任務(wù)，對行駛路徑?jīng)]有做規(guī)定。那么對路徑的選擇很多情況下都由駕駛員憑經(jīng)驗做出選擇，駕駛員選擇所走路徑時考慮最多的幾個因素如下:)運行費用因素:包括燃油費與過路費，所選擇路徑滿足運行費用最小。)時間因素:在顧客規(guī)定的時間內(nèi)把

35、貨物送達(dá)口但是我國的物流需求大多屬于低端的物流需求，很多情況下，顧客對時間的要求并不是那么嚴(yán)格。)路況條件因素:選擇比較適合自己的道路或者是路況條件較好的路徑但是每個駕駛員都有自己的價值取向，這個影響因素的隨機(jī)性比較大。)貨物種類因素:對不同的貨物，可能會選擇出不同的路徑。比如，對于易碎品，司機(jī)可能會選擇路況條件好的路徑;對于貴重品，則會選擇即安全又快捷的路徑，使得貴重物品最先卸載。)目的地的距離因素:一般情況都是先送距離較近，然后再送距離遠(yuǎn)的貨物。（二）物流車輛調(diào)度存在問題分析上節(jié)所描述的基于經(jīng)驗的車輛調(diào)度模式，基于傳統(tǒng)設(shè)備和調(diào)度員、駕駛員經(jīng)驗。例如，某物流公司經(jīng)理對該企業(yè)的物流車輛地調(diào)度總

36、結(jié)為:實事求是，能用為主。由于沒有一套規(guī)范的、完整的、科學(xué)的理論進(jìn)行指導(dǎo)，當(dāng)出現(xiàn)突發(fā)情況，正常的秩序較容易被打破，現(xiàn)場調(diào)度就可能出現(xiàn)問題。比如某輛車在中途出現(xiàn)故障，但是一時也找不到其他空閑車輛;一旦正常的秩序被打亂，那么就會影響到物流企業(yè)的經(jīng)營效益和該企業(yè)在顧客心中的信心。這種狀況也很難跟上現(xiàn)代化發(fā)展的步伐。這種基于經(jīng)驗的傳統(tǒng)調(diào)度模式存在著以下一些問題:(1)我國物流實際與理論研究差距很大，限制了充分發(fā)揮物流車輛調(diào)度的功能和優(yōu)勢。當(dāng)今大部分物流企業(yè)管理者都認(rèn)為，現(xiàn)在整個物流運輸市場現(xiàn)狀為粗放服務(wù)，缺乏高標(biāo)準(zhǔn)的物流需求，所以對物流車輛調(diào)度的要求也不高。例如顧客大部分時候?qū)r間的要求彈性很大，物流

37、企業(yè)有充分的時間來完成顧客的需求服務(wù)，所以時間因素很多時候并不是物流企業(yè)首要考慮的問題，而考慮最多的是經(jīng)濟(jì)因素。(2)物流企業(yè)的規(guī)模大都偏小，這導(dǎo)致很多為物流企業(yè)服務(wù)的車輛的所有權(quán)不屬于物流企業(yè)，而是屬于駕駛員的私人財產(chǎn)，這在很大程度上制約了物流企業(yè)對車輛和駕駛員的管理，最終導(dǎo)致整個物流車輛調(diào)度的效率不高。因為物流企業(yè)對駕駛員的管理一般基于任務(wù)管理，即根據(jù)駕駛員每天完成的任務(wù)，物流企業(yè)給他相對應(yīng)于任務(wù)的報酬，但是駕駛員在服務(wù)過程中物流企業(yè)卻沒有能力去進(jìn)行管理。(3)任務(wù)分配和路線選擇相互脫離，這在整個物流調(diào)度過程中，就不能達(dá)到整體的最優(yōu)，并且服務(wù)的質(zhì)量也大大降低。在上節(jié)所分析的現(xiàn)行的車輛調(diào)度過

38、程，不論是集貨過程還是送貨過程，物流企業(yè)的調(diào)度管理員只對駕駛員分配和安排任務(wù)，具體的路徑選擇由駕駛員根據(jù)自己的偏好進(jìn)行選擇，這就可能會導(dǎo)致一系列不良的后果。首先，任務(wù)分配和路徑選擇的相互分離，物流成本不可能盡可能的降低；其次，車輛等其他資源不可能充分利用，導(dǎo)致資源的閑置和浪費；最后，由于具體路徑選擇有駕駛員選擇，具有很強(qiáng)的主觀性、隨機(jī)性，服務(wù)質(zhì)量的標(biāo)準(zhǔn)沒有統(tǒng)一的認(rèn)識，服務(wù)質(zhì)量也參差不齊。(4)集貨過程與送貨過程相互脫離，這導(dǎo)致物流企業(yè)運作成本增加，并且物流企業(yè)對所掌握的資源利用率降低。在理論學(xué)習(xí)中，混合任務(wù)運輸將大大提高車輛的利用率，降低物流成本和企業(yè)運作成本。但是在實際工作中，由于每次分配給

39、每個司機(jī)的任務(wù)一般都在5個以上，等司機(jī)完成這些任務(wù)后，時間己經(jīng)不應(yīng)許司機(jī)再去完成其他的運輸任務(wù)。(5)物流企業(yè)所掌握的運輸資源規(guī)格不一，但在調(diào)度過程中沒有特別考慮這個問題。服務(wù)于城市集貨和城市配送工作的車輛來自社會，車型五花八門，每輛車的新舊程度、載重噸位、單位油耗等參數(shù)都不盡相同，但是在具體的車輛調(diào)度過程中，很少考慮到那種車型更適合于什么貨物、什么路線的運輸。(6)物流企業(yè)在車輛調(diào)度工作上的資金投入有限，限制了車輛調(diào)度工作所需要的設(shè)備的更新。物流企業(yè)屬于資金密集型企業(yè)，其投資資金大多用于車場的建設(shè)、車輛的購買、倉庫的建設(shè)等大規(guī)模資金投資的基礎(chǔ)項目建設(shè)，這也導(dǎo)致現(xiàn)行的調(diào)度模式還是基于電話、傳統(tǒng)

40、倉庫、人力搬運設(shè)備的等傳統(tǒng)設(shè)備，車輛調(diào)度工作效率的提升空間便受到了限制。(7)物流企業(yè)信息化水平較低，物流企業(yè)的信息技術(shù)水平較低，是車輛調(diào)度發(fā)展的巨大障礙。由于我國物流企業(yè)總體上信息化起步較晚，信息化程度較低，對企業(yè)信息化存在著許多分歧，不少物流企業(yè)還處在電話聯(lián)系、手工操作、人工裝卸的低級階段，并且信息化建設(shè)的難度也比較大。例如，在某物流企業(yè)中，把本來安裝在負(fù)責(zé)該公司長途貨運的大型車輛上的gps系統(tǒng)全部拆了，理論上很好的系統(tǒng)，但是在實際工作中，顧客不愿付出多余的代價來了解貨物的實時信息。(8)一些融入當(dāng)今先進(jìn)的數(shù)字移動通信技術(shù)、計算機(jī)實時信息處理技術(shù)、全球衛(wèi)星定位系統(tǒng)(gps)、地理信息系統(tǒng)(

41、gis)、數(shù)據(jù)庫處理技術(shù)于一體的比較先進(jìn)的車輛調(diào)度系統(tǒng)己經(jīng)開始運用在120救護(hù)車調(diào)度、城市出租車調(diào)度等。但是在貨物運輸領(lǐng)域的運用還比較少見。(9)物流車輛調(diào)度觀念的落后并且缺乏相應(yīng)的人才。在調(diào)研過程中，大多數(shù)物流企業(yè)中的車輛調(diào)度工作人員的文化水平不高并且沒有接受過專業(yè)的學(xué)習(xí)和培訓(xùn)。比如，在運輸過程中，一味的追求成本最小化，就會出現(xiàn)一些不應(yīng)出現(xiàn)的情形，超載運輸是最常見的一種，運輸安全受到比較大的威脅。從總體上來看，我國的物流車輛調(diào)度還處于發(fā)展的處級階段，建立完善的交通車輛調(diào)度系統(tǒng)和科學(xué)的交通車輛調(diào)度方案，對于我們的物流產(chǎn)業(yè)及其與相關(guān)行業(yè)的發(fā)展，都有著非常重要的意義。四、基本問題（一）圖的基本概念

42、在生產(chǎn)和日常生活中，人們常常用點和線畫出的示意圖來反映一些對象之間的關(guān)系。如一個地區(qū)的交通圖是表明這個地區(qū)的一些城鎮(zhèn)及這些城鎮(zhèn)之間的道路溝通情況的示意圖。這里所研究的圖是反映實際生活中某些對象之間某種特定關(guān)系的一種工具。以點代表研究的對象，點和點的連線表示這兩個對象之間的特定關(guān)系，與通常的幾何圖形或函數(shù)圖像中的圖是不同的。這里的點不是真正的幾何點，它只是某種事物的一種抽象，連線也不是幾何中的線段，而是代表某些事物之間的關(guān)系6，因此點與連線的畫法具有隨意性。則圖可以表示為： =, 式中是點的集合，是邊的集合。上面定義的圖 區(qū)別于幾何學(xué)中的圖。在幾何學(xué)中，圖中點的位置、線的的長度和斜率等都十分重要

43、，而這里只關(guān)心圖中有多少個點以及哪些點之間有線相連。有向圖上的連線是有規(guī)定指向的，稱作弧?；〉拇柺? ,),表明方向是從點指向點。有向圖是點與弧的集合，記作=,。上一段介紹的圖是無向的。無向圖中兩個方向均可以通過，但有向圖中只能沿著箭頭方向通過。對于實際問題構(gòu)成的圖，不僅需要表明各元素之間的聯(lián)系，還需要表明這些聯(lián)系的強(qiáng)弱程度。這時，可給圖中的反映聯(lián)系的邊賦一數(shù)值，稱為權(quán)，來表明一定的含義，一般標(biāo)在邊上。賦權(quán)的圖稱為網(wǎng)絡(luò)圖。這里的權(quán)在不同的情況下具有不同的含義，它可以表示距離，也可以表示時間，甚至還可以表示費用。（二）最短路問題最短路問題是圖論中的基本問題，許多實際問題都可以用它來解決，例如管

44、道的鋪設(shè)、線路的安排、廠區(qū)的布局、設(shè)備更新等等。另外，諸如運價最小、運行時間最短、最可靠路等問題，都可以轉(zhuǎn)化為最短路問題加以解決7。在運輸網(wǎng)絡(luò)的每一個對子之間的最小路徑，稱為最短路。最短路在物流運輸、配送活動中的意義是不言而喻的，一般情況下，最短路的權(quán)重是以對之間的距離、車輛行駛時間、費用來表示。求解物流網(wǎng)絡(luò)的最短路就是求出在每一對對子之間的最短運輸距離、最短行駛時間以及最省的運輸費用。由此可見，求解最短路意義是很重大的。dijkstra算法是目前公認(rèn)的解決在權(quán) 0的情形下，此類問題的最好算法，在物流運輸中，這一約束條件是完全能夠滿足的。（三）旅行商問題1、問題概述 旅行商問題(traveli

45、ng salesman problem，簡稱tsp)是運籌學(xué)、圖論以及組合優(yōu)化中的著名難題，由于其有廣泛的應(yīng)用背景，引起了人們的極大興趣。tsp本身可以直接用于解決類似tsp的最優(yōu)巡回線路等問題，其它例如交通車輛的巡回線路問題、民航機(jī)組人員的輪班安排問題、教師任課班級負(fù)荷分配問題、裝配線進(jìn)度問題、數(shù)控機(jī)床的運行問題以及生產(chǎn)系統(tǒng)傳送帶順序問題等，都可以直接或間接引用 tsp的求解方法加以解決。tsp一般描述為:旅行商從駐地出發(fā)，經(jīng)所要去的城市至少一次后返回原地，應(yīng)如何安排其旅行線路，才能使總的旅行距離(或時間、費用等)最少。對于現(xiàn)實問題，由于限制條件的增加，tsp可衍生出許許多多相關(guān)的問題。2、

46、tsp的數(shù)學(xué)模型一般tsp指一個旅行商訪問所有城市。這里設(shè)城市0為旅行商出發(fā)城市，需要訪問的個城市編號為1,2,，為了便于說明問題，把旅行商問題構(gòu)造成網(wǎng)絡(luò)圖以表示: 點集，表示旅行商需要經(jīng)過的地點。 弧集，表示旅行商可能走過的線路段集合。 費用矩陣，表示旅行商經(jīng)過對應(yīng)弧段(,)所花的費用，如時間、距離、花費等7。求解tsp即要求在加權(quán)圖中找到總費用最小的哈密爾頓(hamilton)回路，這里點0稱為源點。所謂哈密爾頓(hamilton)回路即指從源點出發(fā)，經(jīng)過每個頂點一次，且僅僅一次的回路8。定義變量如下:則得到以下數(shù)學(xué)模型: (4-1) (4-2) (4-3) (4-4) (4-5)其中，（

47、）; s為支路消去約束(sub-tour -breaking約束)，即削去構(gòu)成不完整線路的解，如圖2所示，兩條支路均滿足分配約束，但沒有構(gòu)成一條完整的線路，因此不是vsp問題的解。3 42 6 1 5圖2 支路示意圖五、物流配送車輛優(yōu)化調(diào)度模型及求解算法（一）物流配送車輛優(yōu)化調(diào)度問題的提出雖然物流配送具有多種類型和形式，但大部分物流配送形式中運輸?shù)奶攸c是基本相同的，即將商品從配送中心按一定的要求發(fā)送到多個需求點。由于運輸任務(wù)的性質(zhì)和特點不同，道路條件及車輛類型不同，即使在相同收發(fā)貨運點間完成同樣任務(wù)時，采用的行駛路線方案也可能不同。而車輛按不同運行線路完成同樣的運輸工作時，其利用效果是不一樣的

48、，有時甚至?xí)泻艽蟮牟顒e。因此，在滿足貨運任務(wù)要求的前提下，如何選擇最經(jīng)濟(jì)的運行路線，是一項重要的工作。所謂最經(jīng)濟(jì)的運行路線，就是在保證貨物需求的前提下，運輸時間或運輸費用最省的路線。如何按時按量、經(jīng)濟(jì)高效地配送商品，在很大程度上取決于有效的車輛調(diào)度安排，調(diào)度方案的優(yōu)化與否，對增加配送效率、減少總費用和提高服務(wù)水平具有重要的意義。約束條件和目標(biāo)函數(shù)不同，對vsp描述和研究方法也不盡相同。本章中，根據(jù)系統(tǒng)的實際需求，考慮車輛裝載量限制，研究無時限的純裝或純卸的非滿載vsp及單源最短路徑問題，建立合理的數(shù)學(xué)模型，通過經(jīng)典的節(jié)約算法進(jìn)行修正與dijkstra單源最短路徑算法分別求解問題。（二）dij

49、kstra單源最短路徑算法原理及實現(xiàn)流程1、dijkstra單源最短路徑算法的基本原理單源最短路徑問題就是已知有向帶權(quán)圖(簡稱有向網(wǎng))找出從某個源點到中其余各頂點的最短路徑。dijkstra是一種按路徑長度遞增序產(chǎn)生各頂點最短路徑的算法。其算法思想為:設(shè)為最短距離已確定的頂點集，一個頂點屬于集合當(dāng)且僅當(dāng)從源到該頂點的最短路徑長度已知；是最短距離尚未確定的頂點集。設(shè)為源點，為終點。)初始化初始化時，只有源點的最短距離是已知的，將源點的最短路徑看作是己生成的源點到其自身的長度為0的路徑。因此，中僅含有源點，為空。)重復(fù)以下工作，按路徑長度遞增次序產(chǎn)生各頂點最短路徑在當(dāng)前集中選擇一個最短距離最小的頂

50、點來擴(kuò)充集，以保證算法按路徑長度遞增的次序產(chǎn)生各頂點的最短路徑。當(dāng)集中僅剩下最短距離為的頂點，或者所有集中的頂點己擴(kuò)充到集時，源點到所有頂點的最短路徑就求出來了。 需要注意是:)從源點到某頂點的路徑不存在，則可假設(shè)該頂點的最短路徑是一條長度為無窮大的虛擬路徑。)從源點到終點的最短路徑簡稱為的最短路徑；到的最短路徑長度簡稱為的最短距離。2、dijkstra單源最短路徑算法實現(xiàn)流程在本小節(jié)中，以圖3為例，描述dijkstra單源最短路徑算法的實現(xiàn)流程。0 10 100301 4 50 10 60 2 3 20圖3 距離和最短路徑示意圖 第一步：初始化變量 表1初始化變量表變量名稱初始值含義ss=0

51、,0為圖3中的源點最短路徑已確定的頂點集v-sv-s=1,2,3,4最短距離尚未確定的頂點集d表2中第一行d0,d4,表示頂點與原點之間沒有連線已知原點到任意頂點的距離集合p表2中第一行p0,p4,-1表示頂點和原點之間沒有連線算法實現(xiàn)過程當(dāng)前產(chǎn)生的最短距離被哪個頂點改變 第二步：求解 若用表示圖中兩相鄰點與的距離，若與不相鄰，令，顯然，用表示從點到點的最短距離，現(xiàn)要求從源點到其余各點的最短路，如下：) 中找出最短距離和相應(yīng)的頂點，則此時有最短距離，將相應(yīng)的頂點加入到集合中。)查看其余頂點是否與點有連接，若沒有，維持集合,的和,的值不變；如果有，將與這兩點之間的距離相加(點和點有相連，距離為)，和為，小于原來的距離，更新為,為，如表2中循環(huán)行所示： 表2 dijkstra算法生成最短路徑過程循環(huán)sd0d1d2d3d4p0p1p2p3p4始化化001030100-10-10010,101060301