【正文】 cle Routing Problem，即車輛路徑問題)和VSP (Vehicle Scheduling 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)域的前沿與熱點問題。可見，物流配送是一種集集貨、分貨、配貨、配裝、送貨等多種功能為一體的物資流通方式。物流配送是現(xiàn)代化物流中的一個重要環(huán)節(jié)，它是指按客戶(包括零售商、用戶等)的訂貨要求(包括貨物種類、數(shù)量和時間等方面的要求)，在物流中心(也稱物流基地、物流據(jù)點，包括配送中心、倉庫、車站、港口等)進(jìn)行分貨、配貨工作，并將配好的貨物及時送交收貨人的物流活動。這些費用和時間上的消耗以及大量存在的庫存正是潛在的實施物流管理的領(lǐng)域，為物流的發(fā)展留下了巨大的空間。另據(jù)有關(guān)資料，目前我國一般工業(yè)品從產(chǎn)品出廠經(jīng)過裝卸、儲存、運輸?shù)雀鱾€物流環(huán)節(jié)到消費者手中的流通費用約占商品價格的50%左右；而新鮮水果、易變質(zhì)食品、某些化工產(chǎn)品的流通費用有的高達(dá)商品售價的7080%；我國汽車零配件的生產(chǎn)中，其加工裝配時間僅占2%，而98%的時間是原材料、零配件的儲存、裝卸和搬運時間。與發(fā)達(dá)國家相比，我國的物流產(chǎn)業(yè)效率較低[1]。[關(guān)鍵詞] 物流配送 車輛優(yōu)化調(diào)度問題 節(jié)約算法 Dijkstra算法 ABSTRACTAlong with the economic globalization and the network information technique stepping up, 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 influence 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 petition. The vehicle scheduling problem is the very core of the content in the logistics scopes, it is a typical NPhard problem, involving in many research subjects such as operations research, applied mathematics, binatorial optimization, transportation network analysis, puter software, puter applications, logistics science management, etc. VSP bees advanced and hot spots in the field of operations research and binatorial optimization research, researches for VSP can promote actively the development of the theory and method of binatorial optimization.The research based 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 nonfull loaded pure pickup or pure delivery without time windows model is builded. In the course of solving problem, the CW saving methods is modified properly and bines with the Dijkstra singlesource shortest path algorithm, which the feasible result for the actual requests is analysied.[Key words] Logistics Distrubution, Vehicle Scheduling Problem, CW Savings Methods, Dijkstra Methods目 錄一、引言 1二、物流配送業(yè)務(wù)概述 3（一）物流配送概述 3（二）物流配送產(chǎn)生的原因 6消費者消費行為的變化 6生產(chǎn)商生產(chǎn)策略的轉(zhuǎn)變 6零售商向連鎖經(jīng)營發(fā)展的趨勢 7無在庫經(jīng)營的傾向 7（三）物流配送的流程 8物流配送的主要操作 8物流配送的一般流程 11三、物流車輛調(diào)度現(xiàn)狀 12（一）物流車輛調(diào)度模式 12（二）物流車輛調(diào)度存在問題分析 14四、基本問題 17（一）圖的基本概念 17（二）最短路問題 18（三）旅行商問題 19問題概述 19TSP的數(shù)學(xué)模型 19五、物流配送車輛優(yōu)化調(diào)度模型及求解算法 21（一）物流配送車輛優(yōu)化調(diào)度問題的提出 21（二）Dijkstra單源最短路徑算法原理及實現(xiàn)流程 21Dijkstra單源最短路徑算法的基本原理 21Dijkstra單源最短路徑算法實現(xiàn)流程 22（三）無時限的純裝或純卸非滿載VSP實現(xiàn) 24節(jié)約算法基本原理 24節(jié)約算法實現(xiàn)流程 25應(yīng)用舉例 27六、總結(jié) 30參考文獻(xiàn) 32致 謝 3332物流配送車輛調(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)營成本的3050%，當(dāng)一個有效的物流系統(tǒng)與企業(yè)主要商業(yè)系統(tǒng)集成之后，可使倉儲量降低50%，準(zhǔn)時交貨率提高40%，營業(yè)收入增加10%以上[1]。本文在已有數(shù)學(xué)模型的基礎(chǔ)上，提出了適合制造企業(yè)實際需求的物流配送車輛調(diào)度問題模型的目標(biāo)函數(shù)和約束條件，建立了無時限的純裝或純卸的非滿載車輛調(diào)度問題模型。車輛優(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)域。作為客戶服務(wù)的直接手段，物流配送無疑是現(xiàn)代物流管理中的重要環(huán)節(jié)，配送線路的合理與否對配送速度、運營成本及經(jīng)濟(jì)效益影響很大。畢業(yè)論文（設(shè)計）作者簽名： 年 月 日 特此聲明本畢業(yè)論文（設(shè)計）成果歸蘭州商學(xué)院所有。對本論文（設(shè)計）的研究做出重要貢獻(xiàn)的個人和集體，均已在文中以明確方式標(biāo)明。蘭 州 商 學(xué) 院本科生畢業(yè)論文（設(shè)計）論文（設(shè)計）題目： 物流配送車輛調(diào)度問題 學(xué) 院、 系： 信息工程學(xué)院 數(shù)學(xué)系 專 業(yè) (方 向)： 信息與計算科學(xué)專業(yè) 年 級、 班： 2008級信息與計算科學(xué)班 學(xué) 生 姓 名： 陳海燕 指 導(dǎo) 教 師： 王國興 _______年 月 日2聲 明本人鄭重聲明：所呈交的畢業(yè)論文（設(shè)計）是本人在導(dǎo)師的指導(dǎo)下取得的成果。因本畢業(yè)論文（設(shè)計）引起的法律結(jié)果完全由本人承擔(dān)。物流配送車輛調(diào)度問題摘 要隨著經(jīng)濟(jì)全球化和網(wǎng)絡(luò)信息技術(shù)發(fā)展步伐的加快，現(xiàn)代物流作為一個新的經(jīng)濟(jì)增長點引起了全社會廣泛的關(guān)注。采用科學(xué)合理的方法確定配送路線，是物流配送活動中非常重要的工作，對提高企業(yè)服務(wù)質(zhì)量，增強企業(yè)的競爭力具有重要的意義。VSP是運籌學(xué)與組合優(yōu)化領(lǐng)域的前沿與研究熱點問題，對它的研究為組合優(yōu)化理論與方法的發(fā)展有著積極的推動作用。在解決問題的過程中，對經(jīng)典的節(jié)約算法進(jìn)行適當(dāng)?shù)男拚Y(jié)合Dijkstra單源最短路徑算法，求得滿足實際需求的可行解。在經(jīng)濟(jì)發(fā)達(dá)國家和一些經(jīng)濟(jì)水平較高的發(fā)展中國家，現(xiàn)代物流水平己成為影響企業(yè)競爭力的關(guān)鍵因素[1,2] 。根據(jù)全國第三產(chǎn)業(yè)普查資料，我國交通運輸、倉儲、代理和批發(fā)等行業(yè)的成本費用之和占國民生產(chǎn)總值的比重為15%左右，如果考慮其它相關(guān)流通環(huán)節(jié)的費用和流通過程中的物流損失，則全社會物流費用支出約占國民生產(chǎn)總值的20%以上，而美國的全社會物流費用支出僅占其國民生產(chǎn)總值的10%左右。在各種產(chǎn)品的生產(chǎn)和流通環(huán)節(jié)中還有大量原材料、零部件和產(chǎn)品的“庫存”[3]。在這種形勢下，研究如何通過實施科學(xué)的物流管理，以提高物流效率、降低物流成本、提高服務(wù)質(zhì)量是十分必要的。物流配送過程主要包括以下作業(yè)環(huán)節(jié)：從生產(chǎn)工廠進(jìn)貨或運達(dá)并集結(jié)的集貨作業(yè)；根據(jù)各個客戶的不同需求，在物