1、行車路線和時刻表制定的改進方法研究摘 要：運輸中起迄點相同的配送問題是目前許多配送企業面臨的一個難題，對于需求站點較多、需求批量小而頻次多的零擔運輸的情況，尋求最佳配送方案更是難以實現。本文從需求站點的路線分類下手，引入模糊聚類分析方法，對所有需求站點進行科學分類，并用動態規劃的方法對各站點群進行求解，從而確定最佳行車路線和時刻表。最后與傳統方法所做出的配送方案相比較，實現了成本的較大節約，具有良好的可操作性，可以有效地解決路線規劃的問題。關鍵詞：行車路線，模糊聚類，動態規劃，時間窗口The research of improving the methods of Routings and S

2、chedules development Abstract: The issue of the transportation which comes back to the same point is the distribution of many distribution enterprises are facing a problem, to demand more sites, demand volume and frequency of the small number of the transport load, find the best distribution program

3、 is more difficult to achieve. From Site Classification start line, the introduction of fuzzy clustering analysis of all sites demand for scientific classification, and use dynamic programming method for the site-solving, in order to determine the best routes and schedules. Finally made by the tradi

4、tional method of distribution program, compared to the cost of the larger economies, with good workability, can be effectively resolved route planning. Keywords: routings, fuzzy clustering, dynamic programming, the time window運輸是物流決策中的關鍵所在，除采購產品的成本外，一般來講，運輸成本占物流總成本的40%左右，比倉儲成本、庫存成本等任何其他物流成本所占的比重都高。對

5、于運輸問題，需要解決的包括運輸方式的選擇、運輸路線的選擇、車輛調度和合并運輸這些內容。其中最常見的問題就是，找到運輸工具在公路網、鐵路線、水運航道和航空線運行的最佳路線以盡可能的縮短運輸時間或運輸距離。運輸路線選擇問題種類繁多，在這里將其分為三類：一是起訖點不同的單一路徑規劃；二是多個起訖點的路徑規劃；三是起訖點相同的路徑規劃。第三類問題時起訖點不同問題的擴展形式，由于要求車輛必須回到起點行程才結束，問題的難度提高了。本文就是針對起訖點相同的路徑規劃這一問題展開的，我們的目標是找出途徑站點的最佳順序，使行車路線必須經過所有站點，且總出行時間或總距離最短。人們已經提出不少方法來解決起訖點重合的路

6、徑問題。對于現實的運輸問題，使用感知式和啟發式的求解方法，例如掃描法（The Sweep Method）、節約法（The Saving Method）等方法來解決。但這些方法都或多或少的存在一些問題，掃描法將分派車輛服務地點和決定行車路線分成兩步，對諸如在途總運行時間和時間窗口等問題處理得不好。而節約法將各個站點合并來確定各條路線，無法滿足約束條件，例如不符合時間窗口的要求、超過車輛的承載能力、在途時間過長等，而導致節約距離最多的點不能并入路線，只能考慮節約距離次多的點。如果運輸問題中包括很多站點，要找出最優路徑是不切實際的，因為現實中還有其他問題，例如駕駛員的總駕駛時間限制、途中用餐及休息時

7、間、服務水平的高低問題等，因此，現實問題的規模太大，即使使用最快的計算機進行計算，求最優解的時間也非常長。所以，我們面臨的問題就是找出一種有效的方法，確保我們所規劃的每一條運輸路線上的站點及其順序是合理的，并且所有這些運輸路線加起來的總運輸距離是最短的，同時滿足現實約束條件。合理路線和時刻表的制定應服從以下原則：（1）安排車輛負責相互距離最接近的站點的貨物運輸，站點群應該盡可能得緊湊；（2）安排行車路線時應該盡量避免各條線路交叉；（3）注意時間窗口的限制；（4）各行車路線應盡可能呈水滴狀或凸形；（5）對于遙遠而無法歸入群落的站點，可以采用外包的配送方式。由上述的五點原則可以看出，合理的分配站點

8、是解決問題的關鍵。在這里，我們引入一種科學的分類方法模糊聚類分析方法。聚類分析又稱點群分析、群分析等，是按照研究對象在性質上的親疏關系進行分類的一種多元統計方法，它能夠反映樣本之間的內在組合關系?，F實中的分類問題大多伴隨模糊性，類與類之間并無清晰的界限，在聚類分析中引進模糊技術更為合理，也就是模糊聚類分析。本文將應用模糊聚類分析對需求站點進行分類,確定企業自營物流的需求點和物流外包的需求點,通過建立車輛調度的數學模型,使用動態規劃的方法確定各類中的行車最優路線。1、配送站點模糊聚類分析（1）數據標準化對于論域U=x1,x2,，xn為被分類的對象，每個對象又有m個指標表示其形狀，于是得到原始數據

9、矩陣為：X=n*m。根據模糊矩陣的要求將數據標準化，通過平移標準差變換壓縮到0，1區間上。 （2）標定（建立模糊矩陣）使用距離法確定聚類統計量，在這里采用歐式距離。歐式距離為：令，其中c為適當選取的參數。（3）聚類（并畫出聚類圖）根據聚類圖，按照每一輛卡車的裝載量合理的分配站點，并計算出相關系數。2 建立數學模型問題可以描述為：從某個倉庫用多臺配送車輛向多個客戶送貨，每個客戶的位置和貨物需求量一定，各配送車輛的載重量一定，各司機每天的工作時間上限一定，要求合理安排車輛配送路線，使目標函數得到優化，并滿足以下條件：每條配送路徑上各客戶的需求量之和不超過配送車輛的載重量；每條配送路線所花費的時間不

10、超過司機的最長駕駛時間；必須滿足每個客戶的需求，該客戶的需求貨物只能由一輛車一次性配送。 設倉庫有K臺配送車輛，每臺車輛的載重量為(k=1,2,K)，需要向L個客戶送貨，每個客戶的貨物需求量為(i=1,2,L)，需求站點i到j的運距為，物流中心到各客戶的距離為 (i=1,2,L)。再設為第k臺車輛配送的客戶數(=0表示未使用第k臺車輛)，用集合表示第k條路徑。其中的元素表示客戶在路徑k中的順序為i(不包括物流配送中心)，并令=0表示物流中心。以配送總里程最短為目標函數，建立車輛優化調度問題的數學模型為：（1）以需要訪問的站點數作為階段，狀態變量為，為車輛當前所在的站點，/為車輛尚未到達的站點，

11、其中。（2）決策變量與有關，是在的狀態下做出的選擇，允許決策集合為/，形成的序列即為決策序列。（3）從第m個狀態到達第m+1個狀態的狀態轉移方程為。（4）指標函數為 從出發，遍訪中的每一個點回到倉庫的最優路線。3、實例分析某公司有5輛送貨汽車以及足夠的司機為預售客戶提供服務，每輛卡車可裝載500箱貨物，卡車的運行成本為每英里0.9美元，每小時付司機13美元?？ㄜ嚤仨氃谠绯?：30至8：30之間離開倉庫開始送貨。如果司機每天在路上的時間超過8小時（不包括午餐時間），就要支付雙倍的標準工資。運輸途中有半小時的午餐時間，午餐時間應該在中午11：30至13：30之間。有幾個客戶要求在特定時間（時間窗口

12、）送貨。在時間窗口開始或結束之后，不允許送貨。客戶數據間表1。該地區的公路網建設得很好，沒有河流、湖泊或其他需要繞行的障礙。運輸距離和運輸時間是直接相關的，平均車速為25英里/小時?？蛻粜蛱栕鴺怂拓洉r間X（英里）Y（英里）需求量（箱）服務時間（分鐘）時間窗口17.528.5120608:00-17:002109200908:00-10:3031224120608:00-17:0041330150808:00-17:00513.53450408:00-17:00617.516.590508:00-17:0072338.5140708:00-8:3082316.560408:00-17:00923

13、.525110608:00-17:00102733.5180908:00-10:4511292830208:00-11:0014:00-16:0012114090508:00-8:3013324080508:00-10:00147.518503012:30-17:3015513.5160908:00-12:4516238100608:00-17:0017278140608:00-17:001836850308:00-17:0019324905012:00-16:002032.522150708:00-17:002131.51380408:00-17:00總計2240箱1190分鐘倉庫1335表

14、1由于運輸不受道路狀況的影響，在分析這21個需求站點時，可以僅僅針對其地理位置使用模糊聚類分析。使用MATLAB編程，聚類圖如下圖1所示：圖1根據上圖，按照卡車運量可將21個客戶分為為五組，這種分類的相干系數為0.6731。如表2所示：第一條運輸線路16，17，18，18，21第二條運輸線路9，10，11，20第三條運輸線路2，8，14，15第四條運輸線路1，3，5，6，12第五條運輸線路4，7，13表2將每條線路按照各自時間窗口的要求使用動態規劃求得其各條線路的途徑站點順序、出發時間和最終回到倉庫的時間如下表3：線路名稱出發時間途徑站點順序回倉庫時間第一條運輸線路7：5516，17，午餐，1

15、9，18，2115：59第二條運輸線路7：2610，11，20，午餐，914：06第三條運輸線路7：098，2，15，午餐，1414：30第四條運輸線路7：4712，1，3，午餐，6，514：45第五條運輸線路7：347，13，4，午餐13：16表35條路線共行駛295.29925英里，5位司機工作時間總和為31.6453小時，一天的運輸成本為677.1582683美元。若是用掃描法安排路線，其結果如下表4所示：線路名稱出發時間途徑站點順序第一條運輸線路7：4512，15，1，14，5第二條運輸線路7：332，3，4第三條運輸線路7：221，16，17，8，9第四條運輸線路8：0011，20，18，21，19第五條運輸線路7：397，13，10，6表45條路線共行駛375.29978英里，5位司機工作時間總和為34.8253小時，一天的運輸成本為790.75626美元。二者相比較，每天可節約113美元的成本。4、結果分析（1）將各個站點進行模糊聚類分析，根據各需求點的地理位置進行合理的劃分，然后采用動態規劃的算法求解客戶子類中的最優運輸路線，為解決行車路線選擇問題提供了新的思路和途徑。（2）使用模糊聚類的方法可以使站點群更加緊湊，站點之間的行車時間最短。最大程度的避免了不同行車線路的交叉，加大了對每一輛車的充分利用。（3）各個站點群