【正文】 蘭 州 商 學 院 本科生畢業(yè)論文（設計） 論文（設計）題目： 物流配送車輛調(diào)度問題 學 院、 系： 信息工程學院 數(shù)學系 專 業(yè) (方 向 )： 信息與計算科學專業(yè) 年 級、 班： 2021級信息與計算科學班 學 生 姓 名： 陳海燕 指 導 教 師： 王國興 _______年 月 日 聲 明 本人鄭重聲明：所呈交的畢業(yè)論文（設計）是本人在導師的指導下取得的成果。對本論文（設計）的研究做出重要貢獻的個人和集體，均已在文中以明確方式標明。因本畢業(yè)論文（設計）引起的法律結(jié)果完全由本人承擔。 本畢業(yè)論文（設計）成果歸蘭州商學院所有。 特此聲明 畢業(yè)論文（設計）作者簽名： 年 月 日 I 物流配送車輛調(diào)度問題 摘 要 隨著經(jīng)濟全球化和網(wǎng)絡信息技術發(fā)展步伐的加快，現(xiàn)代物流作為一個新的經(jīng)濟增長點引起了全社會廣泛的關注。作為客戶服務的直接手段，物流配送無疑是現(xiàn)代物流管理中的重要環(huán)節(jié)，配送線路的合理與否對配送速度、運營成本及經(jīng)濟效益影響很大。采用科學合理的方法確定配送路線，是物流配送活動中非常重要的工作，對提高企業(yè)服務質(zhì)量，增強企業(yè)的競爭力具有重要的意義。車輛優(yōu)化調(diào)度問題 (Vehicle Scheduling Problem 簡稱 VSP)是物流配送中的最為核心的內(nèi)容，它是一個典 型的 NP 難題，涉及到運籌學、應用數(shù)學，組合優(yōu)化、圖論與網(wǎng)絡分析、計算機軟件、計算機應用、物流科學、運輸管理等眾多學科領域。 VSP 是運籌學與組合優(yōu)化領域的前沿與研究熱點問題，對它的研究為組合優(yōu)化理論與方法的發(fā)展有著積極的推動作用。 本文在已有數(shù)學模型的基礎上，提出了適合制造企業(yè)實際需求的物流配送車輛調(diào)度問題模型的目標函數(shù)和約束條件，建立了無時限的純裝或純卸的非滿載車輛調(diào)度問題模型。在解決問題的過程中，對經(jīng)典的 WC? 節(jié)約算法進行適當?shù)男拚?，結(jié)合 Dijkstra 單源最短路徑算 法，求得滿足實際需求的可行解。 [關鍵詞 ] 物流配送 車輛優(yōu)化調(diào)度問題 WC? 節(jié)約算法 Dijkstra 算法 II ABSTRACT Along with the economic globalization and the work 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 work 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 III 目 錄 一、引言 ............................................................................................................................ 1 二、物流配送業(yè)務概述 .................................................................................................... 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 問題概述 .................................................................................................. 19 TSP的數(shù)學模型 ....................................................................................... 19 五、物流配送車輛優(yōu)化調(diào)度模型及求解算法 .............................................................. 21 （一）物流配送車輛優(yōu)化調(diào)度問題的提出 ......................................................... 21 （二） Dijkstra 單源最短路徑算法原理及實現(xiàn)流程 ............................................ 21 Dijkstra 單源最短路徑算法的基本原理 ................................................ 21 Dijkstra 單源最短路徑算法實現(xiàn)流程 .................................................... 22 （三）無時限的純裝或純卸非滿載 VSP 實現(xiàn) ..................................................... 24 WC? 節(jié)約算法基本原理 .......................................