畢業(yè)設計--物流配送車輛調度問題

1、<p>　　本科生畢業(yè)論文（設計）</p><p>　　論文（設計）題目： 物流配送車輛調度問題 </p><p>　　學 院、 系： 信息工程學院 </p><p>　　數學系 </p><p>　　專 業(yè) (方 向)： 信息與計算科學專業(yè) </

2、p><p>　　年 級、 班： 2008級信息與計算科學班 </p><p>　　學 生 姓 名： </p><p>　　指 導 教 師： xx </p><p>　　_______年 月 日</p><p&

3、gt;　　物流配送車輛調度問題</p><p><b>　　摘 要</b></p><p>　　隨著經濟全球化和網絡信息技術發(fā)展步伐的加快，現(xiàn)代物流作為一個新的經濟增長點引起了全社會廣泛的關注。作為客戶服務的直接手段，物流配送無疑是現(xiàn)代物流管理中的重要環(huán)節(jié)，配送線路的合理與否對配送速度、運營成本及經濟效益影響很大。采用科學合理的方法確定配送路線，是物流配送活動中非常

4、重要的工作，對提高企業(yè)服務質量，增強企業(yè)的競爭力具有重要的意義。車輛優(yōu)化調度問題(Vehicle Scheduling Problem簡稱VSP)是物流配送中的最為核心的內容，它是一個典型的NP難題，涉及到運籌學、應用數學，組合優(yōu)化、圖論與網絡分析、計算機軟件、計算機應用、物流科學、運輸管理等眾多學科領域。VSP是運籌學與組合優(yōu)化領域的前沿與研究熱點問題，對它的研究為組合優(yōu)化理論與方法的發(fā)展有著積極的推動作用。</p>&

5、lt;p>　　本文在已有數學模型的基礎上，提出了適合制造企業(yè)實際需求的物流配送車輛調度問題模型的目標函數和約束條件，建立了無時限的純裝或純卸的非滿載車輛調度問題模型。在解決問題的過程中，對經典的節(jié)約算法進行適當的修正，結合Dijkstra單源最短路徑算法，求得滿足實際需求的可行解。</p><p>　　[關鍵詞] 物流配送 車輛優(yōu)化調度問題 節(jié)約算法 Dijkstra算法</p><

6、p><b>　　ABSTRACT</b></p><p>　　Along with the economic globalization and the network information technique stepping up, the modern logistics catches the whole social attention extensively as a n

7、ew 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 i

8、nfluence on distribution rate, transport cost and economic benefit. It is a very important work in the logistics dist</p><p>　　The research based on the mathematics model, the target function and subject con

9、dition 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

10、 of solving problem, 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.</p><p>　

11、　[Key words] Logistics Distrubution, Vehicle Scheduling Problem, C-W Savings Methods, Dijkstra Methods</p><p><b>　　目 錄</b></p><p><b>　　一、引言1</b></p><

12、;p>　　二、物流配送業(yè)務概述3</p><p>　?。ㄒ唬┪锪髋渌透攀?</p><p>　　（二）物流配送產生的原因6</p><p>　　1、消費者消費行為的變化6</p><p>　　2、生產商生產策略的轉變6</p><p>　　3、零售商向連鎖經營發(fā)展的趨勢7</p><

13、;p>　　4、無在庫經營的傾向7</p><p>　?。ㄈ┪锪髋渌偷牧鞒?</p><p>　　1、物流配送的主要操作8</p><p>　　2、物流配送的一般流程11</p><p>　　三、物流車輛調度現(xiàn)狀12</p><p>　?。ㄒ唬┪锪鬈囕v調度模式12</p><p&g

14、t;　?。ǘ┪锪鬈囕v調度存在問題分析14</p><p><b>　　四、基本問題17</b></p><p>　?。ㄒ唬﹫D的基本概念17</p><p>　?。ǘ┳疃搪穯栴}18</p><p>　?。ㄈ┞眯猩虇栴}19</p><p><b>　　1、問題概述19<

15、;/b></p><p>　　2、TSP的數學模型19</p><p>　　五、物流配送車輛優(yōu)化調度模型及求解算法21</p><p>　?。ㄒ唬┪锪髋渌蛙囕v優(yōu)化調度問題的提出21</p><p>　?。ǘ〥ijkstra單源最短路徑算法原理及實現(xiàn)流程21</p><p>　　1、Dijkstra單源最

16、短路徑算法的基本原理21</p><p>　　2、Dijkstra單源最短路徑算法實現(xiàn)流程22</p><p>　?。ㄈo時限的純裝或純卸非滿載VSP實現(xiàn)24</p><p>　　1、節(jié)約算法基本原理24</p><p>　　2、節(jié)約算法實現(xiàn)流程25</p><p><b>　　3、應用舉例27

17、</b></p><p><b>　　六、總結30</b></p><p><b>　　參考文獻32</b></p><p><b>　　致 謝33</b></p><p>　　物流配送車輛調度問題</p><p><b>

18、　　一、引言</b></p><p>　　當前，現(xiàn)代物流已被公認為是企業(yè)在降低物質消耗、提高勞動生產率以外創(chuàng)造利潤的第三個重要源泉，也是企業(yè)降低生產經營成本，提高產品市場競爭力的重要途徑，據專家測算，現(xiàn)代物流成本約占企業(yè)經營成本的30-50%，當一個有效的物流系統(tǒng)與企業(yè)主要商業(yè)系統(tǒng)集成之后，可使倉儲量降低50%，準時交貨率提高40%，營業(yè)收入增加10%以上[1]。在經濟發(fā)達國家和一些經濟水平較高的發(fā)展

19、中國家，現(xiàn)代物流水平己成為影響企業(yè)競爭力的關鍵因素[1,2] 。</p><p>　　與發(fā)達國家相比，我國的物流產業(yè)效率較低[1]。根據全國第三產業(yè)普查資料，我國交通運輸、倉儲、代理和批發(fā)等行業(yè)的成本費用之和占國民生產總值的比重為15%左右，如果考慮其它相關流通環(huán)節(jié)的費用和流通過程中的物流損失，則全社會物流費用支出約占國民生產總值的20%以上，而美國的全社會物流費用支出僅占其國民生產總值的10%左右。另據有關資料

20、，目前我國一般工業(yè)品從產品出廠經過裝卸、儲存、運輸等各個物流環(huán)節(jié)到消費者手中的流通費用約占商品價格的50%左右；而新鮮水果、易變質食品、某些化工產品的流通費用有的高達商品售價的70-80%；我國汽車零配件的生產中，其加工裝配時間僅占2%，而98%的時間是原材料、零配件的儲存、裝卸和搬運時間。在各種產品的生產和流通環(huán)節(jié)中還有大量原材料、零部件和產品的“庫存”[3]。這些費用和時間上的消耗以及大量存在的庫存正是潛在的實施物流管理的領域，為物

21、流的發(fā)展留下了巨大的空間。在這種形勢下，研究如何通過實施科學的物流管理，以提高物流效率、降低物流成本、提高服務質量是十分必要的。</p><p>　　物流配送是現(xiàn)代化物流中的一個重要環(huán)節(jié)，它是指按客戶(包括零售商、用戶等)的訂貨要求(包括貨物種類、數量和時間等方面的要求)，在物流中心(也稱物流基地、物流據點，包括配送中心、倉庫、車站、港口等)進行分貨、配貨工作，并將配好的貨物及時送交收貨人的物流活動。物流配送過程

22、主要包括以下作業(yè)環(huán)節(jié)：從生產工廠進貨或運達并集結的集貨作業(yè)；根據各個客戶的不同需求，在物流中心將所需要的貨物挑選出來的分貨和配貨作業(yè)；考慮配送貨物的重量和體積，充分利用車輛的載重和容積的貨物配裝作業(yè)；合理確定車輛配送路線并及時送貨的作業(yè)。可見，物流配送是一種集集貨、分貨、配貨、配裝、送貨等多種功能為一體的物資流通方式。</p><p>　　在物流配送業(yè)務中，存在許多優(yōu)化決策的問題，車輛優(yōu)化調度問題涉及面較廣，需要

23、考慮的因素較多，本文將著重研究物流配送車輛調度的一般問題。國外將物流配送車輛調度問題歸結為VRP ( Vehicle Routing Problem，即車輛路徑問題)和VSP (Vehicle Scheduling Problem，即車輛調度問題)，該問題于1959年由Dantzig和Ramse提出后[4] ：很快便引起運籌學、應用數學、組合數學、圖論與網絡分析、物流科學、計算機應用等學科的專家以及運輸計劃制定者的極大重視，并一直是運

24、籌學與組合優(yōu)化領域的前沿與熱點問題。VRP與VSP是根據問題的空間特性和時間特性的相對重要性來劃分的，一般認為當不考慮時間要求，僅根據空間位置安排線路的稱為Routing，根據時間要求安排線路的稱為Scheduling，同時考慮空間位置和時間要求的稱為Routing和Scheduling混合問題，也有不區(qū)分兩者的，若有具體約束則加上定語，例如將有時間要求的車輛調度問題稱為Vehicle Routing Problem with Time

25、 Windows。在現(xiàn)實應用中，由于Sched</p><p>　　在現(xiàn)實生產和生活中[1]，郵政投遞問題、飛機、鐵路車輛、水運船舶及公共汽車的調度問題、電力調度問題、管道鋪設問題、計算機網絡拓撲設計問題都可以抽象為物流配送車輛調度問題。因此，將物流配送車輛調度問題作為研究對象具有一定的理論和現(xiàn)實意義。</p><p>　　二、物流配送業(yè)務概述</p><p>&l

26、t;b>　　（一）物流配送概述</b></p><p>　　配送的概念有多種表述。</p><p>　　日本工業(yè)標準表述，將貨物從物流結點送交收貨人。</p><p>　　日本1991年版《物流手冊》的表述:生產廠到配送中心之間的物品空間移動叫“運輸”，從配送中心到顧客之間的物品空間移動叫“配送”。</p><p>　　美國

27、《物流管理供應鏈過程一體化》表述:實物配送這一領域涉及將制成品交給顧客的運輸?！瓕嵨锱渌瓦^程，可以使顧客服務的時間和空間的需求成為營銷的一個整體組成部分……</p><p>　　我國《現(xiàn)代物流學》表述:配送是以現(xiàn)代送貨形式實現(xiàn)資源最終配置的經濟活動；按用戶訂貨要求，在配送中心或其他物流結點進行的貨物配備并以最合理方式送交用戶。</p><p>　　一般認為物流配送是指物流過程的中轉型送貨

28、(也稱為二次輸送、支線輸送、終端輸送)。也就是在產品用戶集中區(qū)域，按用戶的訂貨要求和時間計劃，在物流中心配貨并將配好的貨物采用汽車巡回運送的方式交收貨人的小范圍、近距離、小批量、多品種、為用戶服務的運輸[3]。配送不是單純的運輸或送貨，而是運輸與其它活動的組成，除了各種“運”、“送”活動外，還要從事大量的集貨、分貨、配貨、配裝等工作，是配與送的結合。對于配送的深入認識，應當掌握以下幾個要點:</p><p>　　

29、(1)配送的資源配置作用</p><p>　　配送是“最終配置”，因而是接近顧客的配置。</p><p>　　對于現(xiàn)代企業(yè)而言，“接近顧客”是至關重要的。美國蘭德公司對“幸福”雜志所列的五百家大公司進行一項調查表明“經營戰(zhàn)略和接近顧客至關重要”，所以接近顧客的配送，自然取得了它在現(xiàn)代經濟中的地位。</p><p>　　(2)配送的實質是送貨</p>&

30、lt;p>　　配送的主要經濟活動，尤其是接近顧客的經濟活動是送貨。</p><p>　　(3)配送是現(xiàn)代送貨</p><p>　　現(xiàn)代兩個字表述了和舊式送貨的區(qū)別。其區(qū)別主要在于:</p><p>　　ⅰ)一般送貨可以是一種偶然的行為，而配送卻是一種體制行為，是市場經濟的一種體制形式。</p><p>　?、?一般送貨是完全被動的服務行

31、為，而配送則是有一定組織形式的計劃行為。</p><p>　?、?配送依靠現(xiàn)代生產力，依靠科技進步支撐，實現(xiàn)對用戶的送貨服務。</p><p>　　(4)配送是“配”和“送”有機結合的形式</p><p>　　配送利用有效的分揀、配貨等理貨工作，使送貨達到一定的規(guī)模，以利用規(guī)模優(yōu)勢取得較低的送貨成本。如果不進行分揀、配貨，有一件運一件，需要一點送一點，這就會加大送貨

32、成本。所以，追求整個配送的優(yōu)勢，分揀、配貨等工作是必不可少的。</p><p>　　(5)配送是市場經濟產物</p><p>　　配送是在市場經濟條件下，在“供大于求”的買方市場環(huán)境中所派生的一種形式。</p><p>　　在買方市場環(huán)境下，用戶具有選擇權，而賣方需要通過有效的服務來售出自己的產品，爭奪一塊份額，這就形成了有提供者、有需求者的理想市場環(huán)境，使配送得以

33、發(fā)展。</p><p>　　(6)配送以用戶的要求為出發(fā)點</p><p>　　“按用戶的訂貨要求”明確了用戶的主導地位。配送是從用戶利益出發(fā)，按用戶要求進行的一種活動，因此，在觀念上必須明確“用戶第一”、“質量第一”。配送企業(yè)的地位是服務地位而不是主導地位，不能從本企業(yè)利益出發(fā)，而應從用戶利益出發(fā)，在滿足用戶利益基礎上取得本企業(yè)的利益。更重要的是，不能利用配送損傷或控制用戶，不能利用配送

34、作為部門分割、行業(yè)分割、割據市場的手段。</p><p>　　(7)以最“合理的方式”的提法是基于這樣一種考慮:過分強調“按用戶要求”是不妥的，受用戶本身的局限，要求有時候存在不合理性，在這種情況下會損失自我或雙方的利益。對于配送而言，應當在時間、速度、服務水平、成本、數量等多方面尋求最優(yōu)，實現(xiàn) “雙贏”的原則。</p><p>　　（二）物流配送產生的原因</p><

35、p>　　配送作為先進的物流形式，它的產生以及推廣并不是偶然的，而是隨著現(xiàn)代商業(yè)經營環(huán)境和經營形式的變化而出現(xiàn)的。這些變化主要體現(xiàn)在:</p><p>　　1、消費者消費行為的變化</p><p>　　隨著人們生活水平的提高，20世紀90年代以來，人們對生活的追求已逐漸從原來的溫飽型、數量型轉向小康型，對生活質量的要求越來越高。伴隨著這種生活觀念的變化，在經濟社會向國際化、信息化急劇轉

36、變的基礎上，消費者價值觀趨于多元化和多樣化，喜歡購買具有差別化的商品。這種消費行為變化對企業(yè)的生產和經營產生了深遠的影響，使生產和銷售企業(yè)在適應消費者消費行為變化的過程中，開始強化物流管理，通過少批量、多品種、快速化、柔性化的生產和經營來滿足消費者的需求。</p><p>　　2、生產商生產策略的轉變</p><p>　　在傳統(tǒng)消費模式中，當新產品被廠家研制、開發(fā)出來后，通過各種各樣的媒體

37、、特別是電視廣告等促銷手段的運用和商業(yè)推廣，其一般能喚起全國規(guī)模的需求，這種營銷模式背后隱含的是消費者具有“與他人一致”的消費意識。與這種消費者相對應，零售業(yè)以百貨業(yè)和綜合超市為中心，通過大量購進、大量陳列廉價的商品來推動銷售額的增長。但是隨著消費個性化、多樣化的發(fā)展，原來那種商品在一部分人中開始流行后，大家爭相購買的情況會越來越少，而且流行商品的生命周期也越來越短。在這種狀況下，廠家要準確預測特定商品的流行程度十分困難。此外，基本生活

38、品在全社會普及之后，商品在質量上的稍微改進或價格的稍微降低都不能大量激發(fā)消費者的購買欲望，因而能開發(fā)出具有爆發(fā)性需求規(guī)模的革新產品也會越來越困難。</p><p>　　正因為如此，如今很多廠商都在積極開展多品種戰(zhàn)略，即將原來的產品加以改良，附加各種機能，形成產品間微妙的差異，積極開展多品種生產戰(zhàn)略。</p><p>　　3、零售商向連鎖經營發(fā)展的趨勢</p><p>

39、;　　在傳統(tǒng)的流通模式下，商品從制造商生產出來后，經由層層的批發(fā)商再到零售商，最后到達消費者手上，批發(fā)商在此扮演著整個通路的樞紐作用。隨著消費形態(tài)的改變，整個市場成為消費者導向，這種趨勢迫使企業(yè)改變傳統(tǒng)的經營方式，建立新的競爭策略，許多制造商為了將自己生產的產品直接輸往末端市場，紛紛構建自有的通路體系，這使得超級市場、便利點、連鎖店一時之間快速成長。</p><p>　　伴隨著連鎖經營的興起，配送服務的重要性越來

40、越為人們所關注。</p><p>　　4、無在庫經營的傾向</p><p>　　零售業(yè)中與消費個性化、多樣化以及廠商多品種生產相對應，無論在既存的零售業(yè)態(tài)百貨店和超市中，還是新型的24小時店等新業(yè)態(tài)中，經營的商品品種數越來越多。但是，與此同時，由于政策、環(huán)境、房地產價格等原因，店鋪的規(guī)模和倉庫規(guī)模不可能無限擴大，特別是在大都市中，由于人口密度大、地價高昂、消費更新快、環(huán)境規(guī)制嚴格等原因，更

41、加限制了倉儲點和倉儲空間的擴大，在這種情況下，只有提高店內管理效率，通過加快商品周轉來抵消倉儲空間不足等問題。如今，在國際上，大型零售業(yè)的方針均已從原來通過開設新店尋求外延型發(fā)展，轉向充實內部管理和投資，積極探索內涵型發(fā)展。除此之外，推動無在庫經營的原因是，由于消費行為的多樣化、個性化發(fā)展，商品品牌、品種、式樣的急劇增多，使零售商對顧客實際需求的預測十分困難。在這種狀況下，庫存越大，零售企業(yè)承擔的資金占用和滯銷風險也越大，因此為了加速資

42、金周轉和降低風險，零售企業(yè)必須盡可能地壓縮庫存，實現(xiàn)實時銷售。具體看，現(xiàn)代零售業(yè)的管理重點是：</p><p>　?、?實行“單品管理”，迅速制定經營中的“暢銷品”與“滯銷品”，以此為基礎確定定貨商品的種類和數量。</p><p>　?、?實行“無在庫經營”，在有限的空間里陳列更多的商品，降低銷售風</p><p>　　險，極力抑制各類商品的在庫量，徹底實現(xiàn)在庫管理

43、和在庫成本的削減。</p><p>　?。ㄈ┪锪髋渌偷牧鞒?lt;/p><p>　　1、物流配送的主要操作</p><p><b>　　(1)備貨</b></p><p>　　配送的準備工作和基礎工作。備貨工作包括籌集貨源、訂貨、采購、集貨、進貨及有關的質量檢查、結算、交接等。</p><p>　　

44、配送的優(yōu)勢之一就是可以集中若干用戶的需求進行一定規(guī)模的備貨。備貨是決定配送成敗的初期工作，如果備貨成本太高，會大大降低配送的效益。</p><p><b>　　(2)儲存</b></p><p>　　配送中的儲存有儲備及暫存兩種形態(tài):</p><p><b>　?、?儲備</b></p><p>　

45、　配送儲備是按一定時期的配送經營要求，形成的對配送的資源保證。這種類型的儲備數量較大，儲備結構也較完善，視貨源及到貨情況，可以有計劃地確定周轉儲備及保險儲備結構及數量。配送的儲備保證有時在配送中心附近單獨設庫解決。</p><p><b>　　ⅱ)暫存</b></p><p>　　另一種儲存形態(tài)是暫存，是具體執(zhí)行配送時，按分揀配貨要求在理貨場地所做的少量儲存準備。由于

46、總體儲存效益取決于儲存總量，所以這部分暫存數量只會對工作方便與否造成影響，而不會影響儲存的總效益，因而在數量上控制并不嚴格。</p><p>　　還有另一種形式的暫存，即是分揀、配貨之后，形成的發(fā)送貨載的暫存，這個暫存主要是調節(jié)配貨與送貨的節(jié)奏，暫存時間不長。</p><p><b>　　(3) 分揀及配貨</b></p><p>　　這是配送

47、不同于其他物流形式的有特點的功能要素，也是配送成敗的一項重要支持性工作。分揀及配貨是完善送貨、支持送貨的準備性工作，是不同配送企業(yè)在送貨時進行競爭和提高自身經濟效益的必然延伸，所以，也可以說是送貨向高級形式發(fā)展的必然要求。有了分揀及配貨，就會大大提高送貨服務水平，所以，分揀及配貨是決定配送系統(tǒng)水平的關鍵要素。</p><p><b>　　(4)配裝</b></p><p&

48、gt;　　在單個用戶配送數量不能達到車輛的有效載運負荷時，就存在如何集中不同用戶的配送貨物，進行搭配裝載以充分利用運能、運力的問題，這就需要配裝。</p><p>　　和一般送貨不同之處在于，通過配裝可以大大提高送貨水平及降低送貨成本，所以配裝也是配送系統(tǒng)中有現(xiàn)代特點的功能要素，是現(xiàn)代配送不同于傳統(tǒng)送貨的重要區(qū)別之處。</p><p><b>　　(5)配送運輸</b>

49、;</p><p>　　配送運輸屬于運輸中的末端運輸、支線運輸，和一般運輸形態(tài)主要區(qū)別在于:配送運輸是較短距離、較小規(guī)模、頻度較高的運輸形式，一般使用汽車和其他小型車輛做運輸工具。</p><p>　　與干線運輸的另一個區(qū)別是，配送運輸路線選擇問題是一般干線運輸所沒有的，干線運輸的干線是惟一的運輸線，而配送運輸由于配送用戶多，一般城市交通路線又較復雜，如何組成最佳路線，如何使配裝和路線有效

50、搭配等，是配送運輸的特點，也是難度較大的工作。</p><p><b>　　(6)送達服務</b></p><p>　　配好的貨運輸到用戶還不算配送工作的完結，這是因為送達貨和用戶接貨往往還會出現(xiàn)不協(xié)調，使配送前功盡棄。因此，要圓滿地實現(xiàn)運到交貨的移交，并有效地、方便地處理相關手續(xù)并完成結算，還應講究卸貨地點、卸貨方式等。送達服務也是配送獨具的特殊性。</p&g

51、t;<p><b>　　(7)配送加工</b></p><p>　　在配送中，配送加工這一功能要素不具有普遍性，但是往往是有重要作用的功能要素。主要原因是通過配送加工，可以大大提高用戶的滿意程度并提高被配送貨物的附加價值。配送加工是流通加工的一種，但配送加工有它不同于一般流通加工的特點，即配送加工一般只取決于特殊用戶要求，其加工的目的較為單一。</p><p

52、><b>　　(8)回程</b></p><p>　　在執(zhí)行完配送的使命之后，車輛需要回程，在一般情況下，回程車輛往往是空駛，這是降低配送效益、提高配送成本的因素之一。在規(guī)劃配送路線時，回程路線應當盡量縮短；在進行穩(wěn)定的、計劃配送時，回程車輛可將包裝物、廢棄物、殘次品運回集中處理，或者將用戶的產品運回配送中心，作為配送中心的資源，向其他用戶進行配送。</p><p&

53、gt;　　2、物流配送的一般流程</p><p>　　不同的配送對象有不同的配送流程，但一般來說，物流配送的流程可用圖1表示：</p><p>　　訂貨協(xié)議/貨物運到驗貨 退貨</p><p><b>　　代理協(xié)議</b></p><p>　　理貨 廢棄物的處理</p><

54、;p>　　訂單履行 暫存包裝、疏通、加工</p><p><b>　　驗貨/揀選上貨架</b></p><p>　　配貨發(fā)貨區(qū)暫存發(fā)貨發(fā)貨</p><p>　　圖1物流配送的一般流程</p><p>　　三、物流車輛調度現(xiàn)狀</p><p>　　（一）物流車輛調度模式

55、</p><p>　　物流車輛調度過程是整個物流過程中重要的步驟，在降低運輸成本上有著關鍵的作用。但是目前，我國貨物運輸車輛調度方法比較落后，多采用傳統(tǒng)的人工方法編制調度方案。目前仍然被大多數公司采用的車輛調度模式，是一種基于傳統(tǒng)設備和調度員、駕駛員經驗的調度模式，并且由于很多物流企業(yè)的一部分車輛的所有權不屬于物流企業(yè)，這一部分車輛的所有權屬于車主，車主帶車加入物流企業(yè)，完成所分配的任務并且按照所完成的任務數量來

56、得到收入，車主與物流企業(yè)并不屬于從屬的關系，加大了管理的難度。所以，調度決策者只對駕駛員分配和安排調度任務，對路徑的選擇很多情況下都由司機憑經驗做出選擇。這種調度模式的基本過程如下:</p><p>　　(1)集貨過程:集貨有專門負責的車輛來完成，由于在集貨過程中，貨物主要來自物流點周圍，所以根據貨物來自于不同區(qū)域把為物流企業(yè)集貨服務的車輛分為不同的組別，比如某公司把該公司專門負責集貨的車輛分為4個組，分別負責來

57、自周邊4個市區(qū)的貨物的集結任務。當顧客向該物流公司提出運輸需求時，調度管理人員便電話通知相應的車主，之后車主便去完成相應的任務。</p><p>　　(2)聯(lián)系收獲人:對于一部分貨物，貨主會在提出運輸需求的同時提出該貨物的目的地和到達目的地的準確時間。對于另一部分貨物而言，物流公司調度管理人員就會及時與收貨人進行聯(lián)系，確認交貨的時間和地點。在服務過程中出現(xiàn)問題時，最重要的就是要及時與顧客及時溝通，協(xié)商解決。<

58、;/p><p>　　(3)貨物的存放:貨物被送到公司所屬的倉庫后，根據貨物的去向和出貨的先后順序存放于倉庫中。把未知出貨去向和時間的貨物放于倉庫的其他角落。</p><p>　　(4)送貨過程:物流公司把專門用來負責送貨的車輛分為兩種，第一種為長途送貨車輛;第二種為市內配送車輛。第一類車輛由于運輸距離遠、載重噸位大、購買費用高，所以這一部分車輛大多屬于公司的固定資產;第二類車輛負責武漢市內的貨

59、物配送，這一部分車輛大多不屬于物流公司。在第二類車輛中，物流公司又把它們分為4個組，分別負責來自周邊4個地區(qū)的貨物的配送任務。當的有送貨任務時，調度管理人員會電話通知車主，車主開車到倉庫后裝貨，然后把貨物按要求送到其收貨人指定地點卸貨，收貨人檢查貨物的完整性后簽字確認完成運輸任務。</p><p>　　從上述所說的物流車輛調度過程，我們可以知道，這些物流企業(yè)中的車輛調度其實只分配了運輸任務，對行駛路徑沒有做規(guī)定。

60、那么對路徑的選擇很多情況下都由駕駛員憑經驗做出選擇，駕駛員選擇所走路徑時考慮最多的幾個因素如下:</p><p>　　ⅰ)運行費用因素:包括燃油費與過路費，所選擇路徑滿足運行費用最小。</p><p>　?、?時間因素:在顧客規(guī)定的時間內把貨物送達口但是我國的物流需求大多屬于低端的物流需求，很多情況下，顧客對時間的要求并不是那么嚴格。</p><p>　?、?路況條

61、件因素:選擇比較適合自己的道路或者是路況條件較好的路徑但是每個駕駛員都有自己的價值取向，這個影響因素的隨機性比較大。</p><p>　?、?貨物種類因素:對不同的貨物，可能會選擇出不同的路徑。比如，對于易碎品，司機可能會選擇路況條件好的路徑;對于貴重品，則會選擇即安全又快捷的路徑，使得貴重物品最先卸載。</p><p>　?、?目的地的距離因素:一般情況都是先送距離較近，然后再送距離遠的

62、貨物。</p><p>　?。ǘ┪锪鬈囕v調度存在問題分析</p><p>　　上節(jié)所描述的基于經驗的車輛調度模式，基于傳統(tǒng)設備和調度員、駕駛員經驗。例如，某物流公司經理對該企業(yè)的物流車輛地調度總結為:實事求是，能用為主。由于沒有一套規(guī)范的、完整的、科學的理論進行指導，當出現(xiàn)突發(fā)情況，正常的秩序較容易被打破，現(xiàn)場調度就可能出現(xiàn)問題。比如某輛車在中途出現(xiàn)故障，但是一時也找不到其他空閑車輛;一

63、旦正常的秩序被打亂，那么就會影響到物流企業(yè)的經營效益和該企業(yè)在顧客心中的信心。這種狀況也很難跟上現(xiàn)代化發(fā)展的步伐。這種基于經驗的傳統(tǒng)調度模式存在著以下一些問題:</p><p>　　(1)我國物流實際與理論研究差距很大，限制了充分發(fā)揮物流車輛調度的功能和優(yōu)勢。當今大部分物流企業(yè)管理者都認為，現(xiàn)在整個物流運輸市場現(xiàn)狀為粗放服務，缺乏高標準的物流需求，所以對物流車輛調度的要求也不高。例如顧客大部分時候對時間的要求彈性

64、很大，物流企業(yè)有充分的時間來完成顧客的需求服務，所以時間因素很多時候并不是物流企業(yè)首要考慮的問題，而考慮最多的是經濟因素。</p><p>　　(2)物流企業(yè)的規(guī)模大都偏小，這導致很多為物流企業(yè)服務的車輛的所有權不屬于物流企業(yè)，而是屬于駕駛員的私人財產，這在很大程度上制約了物流企業(yè)對車輛和駕駛員的管理，最終導致整個物流車輛調度的效率不高。因為物流企業(yè)對駕駛員的管理一般基于任務管理，即根據駕駛員每天完成的任務，物流

65、企業(yè)給他相對應于任務的報酬，但是駕駛員在服務過程中物流企業(yè)卻沒有能力去進行管理。</p><p>　　(3)任務分配和路線選擇相互脫離，這在整個物流調度過程中，就不能達到整體的最優(yōu)，并且服務的質量也大大降低。在上節(jié)所分析的現(xiàn)行的車輛調度過程，不論是集貨過程還是送貨過程，物流企業(yè)的調度管理員只對駕駛員分配和安排任務，具體的路徑選擇由駕駛員根據自己的偏好進行選擇，這就可能會導致一系列不良的后果。首先，任務分配和路徑選

66、擇的相互分離，物流成本不可能盡可能的降低；其次，車輛等其他資源不可能充分利用，導致資源的閑置和浪費；最后，由于具體路徑選擇有駕駛員選擇，具有很強的主觀性、隨機性，服務質量的標準沒有統(tǒng)一的認識，服務質量也參差不齊。</p><p>　　(4)集貨過程與送貨過程相互脫離，這導致物流企業(yè)運作成本增加，并且物流企業(yè)對所掌握的資源利用率降低。在理論學習中，混合任務運輸將大大提高車輛的利用率，降低物流成本和企業(yè)運作成本。但是

67、在實際工作中，由于每次分配給每個司機的任務一般都在5個以上，等司機完成這些任務后，時間己經不應許司機再去完成其他的運輸任務。</p><p>　　(5)物流企業(yè)所掌握的運輸資源規(guī)格不一，但在調度過程中沒有特別考慮這個問題。服務于城市集貨和城市配送工作的車輛來自社會，車型五花八門，每輛車的新舊程度、載重噸位、單位油耗等參數都不盡相同，但是在具體的車輛調度過程中，很少考慮到那種車型更適合于什么貨物、什么路線的運輸。&

68、lt;/p><p>　　(6)物流企業(yè)在車輛調度工作上的資金投入有限，限制了車輛調度工作所需要的設備的更新。物流企業(yè)屬于資金密集型企業(yè)，其投資資金大多用于車場的建設、車輛的購買、倉庫的建設等大規(guī)模資金投資的基礎項目建設，這也導致現(xiàn)行的調度模式還是基于電話、傳統(tǒng)倉庫、人力搬運設備的等傳統(tǒng)設備，車輛調度工作效率的提升空間便受到了限制。</p><p>　　(7)物流企業(yè)信息化水平較低，物流企業(yè)的信

69、息技術水平較低，是車輛調度發(fā)展的巨大障礙。由于我國物流企業(yè)總體上信息化起步較晚，信息化程度較低，對企業(yè)信息化存在著許多分歧，不少物流企業(yè)還處在電話聯(lián)系、手工操作、人工裝卸的低級階段，并且信息化建設的難度也比較大。例如，在某物流企業(yè)中，把本來安裝在負責該公司長途貨運的大型車輛上的GPS系統(tǒng)全部拆了，理論上很好的系統(tǒng)，但是在實際工作中，顧客不愿付出多余的代價來了解貨物的實時信息。</p><p>　　(8)一些融入當

70、今先進的數字移動通信技術、計算機實時信息處理技術、全球衛(wèi)星定位系統(tǒng)(GPS)、地理信息系統(tǒng)(GIS)、數據庫處理技術于一體的比較先進的車輛調度系統(tǒng)己經開始運用在120救護車調度、城市出租車調度等。但是在貨物運輸領域的運用還比較少見。</p><p>　　(9)物流車輛調度觀念的落后并且缺乏相應的人才。在調研過程中，大多數物流企業(yè)中的車輛調度工作人員的文化水平不高并且沒有接受過專業(yè)的學習和培訓。比如，在運輸過程中，

71、一味的追求成本最小化，就會出現(xiàn)一些不應出現(xiàn)的情形，超載運輸是最常見的一種，運輸安全受到比較大的威脅。</p><p>　　從總體上來看，我國的物流車輛調度還處于發(fā)展的處級階段，建立完善的交通車輛調度系統(tǒng)和科學的交通車輛調度方案，對于我們的物流產業(yè)及其與相關行業(yè)的發(fā)展，都有著非常重要的意義。</p><p><b>　　四、基本問題</b></p><

72、;p><b>　?。ㄒ唬﹫D的基本概念</b></p><p>　　在生產和日常生活中，人們常常用點和線畫出的示意圖來反映一些對象之間的關系。如一個地區(qū)的交通圖是表明這個地區(qū)的一些城鎮(zhèn)及這些城鎮(zhèn)之間的道路溝通情況的示意圖。這里所研究的圖是反映實際生活中某些對象之間某種特定關系的一種工具。以點代表研究的對象，點和點的連線表示這兩個對象之間的特定關系，與通常的幾何圖形或函數圖像中的圖是不同的

73、。這里的點不是真正的幾何點，它只是某種事物的一種抽象，連線也不是幾何中的線段，而是代表某些事物之間的關系[6]，因此點與連線的畫法具有隨意性。則圖可以表示為：</p><p><b>　　={,} </b></p><p>　　式中是點的集合，是邊的集合。上面定義的圖 區(qū)別于幾何學中的圖。在幾何學中，圖中點的位置、線的的長度和斜率等都十分重要，而這里只關心圖中有多少個

74、點以及哪些點之間有線相連。</p><p>　　有向圖上的連線是有規(guī)定指向的，稱作弧?；〉拇柺? ,),表明方向是從點指向點。有向圖是點與弧的集合，記作={,}。上一段介紹的圖是無向的。無向圖中兩個方向均可以通過，但有向圖中只能沿著箭頭方向通過。</p><p>　　對于實際問題構成的圖，不僅需要表明各元素之間的聯(lián)系，還需要表明這些聯(lián)系的強弱程度。這時，可給圖中的反映聯(lián)系的邊賦一數值，稱

75、為權，來表明一定的含義，一般標在邊上。賦權的圖稱為網絡圖。這里的權在不同的情況下具有不同的含義，它可以表示距離，也可以表示時間，甚至還可以表示費用。</p><p><b>　　（二）最短路問題</b></p><p>　　最短路問題是圖論中的基本問題，許多實際問題都可以用它來解決，例如管道的鋪設、線路的安排、廠區(qū)的布局、設備更新等等。另外，諸如運價最小、運行時間最短

76、、最可靠路等問題，都可以轉化為最短路問題加以解決[7]。</p><p>　　在運輸網絡的每一個―對子之間的最小路徑，稱為最短路。最短路在物流運輸、配送活動中的意義是不言而喻的，一般情況下，最短路的權重是以―對之間的距離、車輛行駛時間、費用來表示。求解物流網絡的最短路就是求出在每一對―對子之間的最短運輸距離、最短行駛時間以及最省的運輸費用。由此可見，求解最短路意義是很重大的。</p><p&g

77、t;　　Dijkstra算法是目前公認的解決在權 >0的情形下，此類問題的最好算法，在物流運輸中，這一約束條件是完全能夠滿足的。</p><p><b>　?。ㄈ┞眯猩虇栴}</b></p><p><b>　　1、問題概述</b></p><p>　　旅行商問題(Traveling Salesman Proble

78、m，簡稱TSP)是運籌學、圖論以及組合優(yōu)化中的著名難題，由于其有廣泛的應用背景，引起了人們的極大興趣。TSP本身可以直接用于解決類似TSP的最優(yōu)巡回線路等問題，其它例如交通車輛的巡回線路問題、民航機組人員的輪班安排問題、教師任課班級負荷分配問題、裝配線進度問題、數控機床的運行問題以及生產系統(tǒng)傳送帶順序問題等，都可以直接或間接引用 TSP的求解方法加以解決。</p><p>　　TSP一般描述為:旅行商從駐地出發(fā)，

79、經所要去的城市至少一次后返回原地，應如何安排其旅行線路，才能使總的旅行距離(或時間、費用等)最少。對于現(xiàn)實問題，由于限制條件的增加，TSP可衍生出許許多多相關的問題。</p><p>　　2、TSP的數學模型</p><p>　　一般TSP指一個旅行商訪問所有城市。這里設城市0為旅行商出發(fā)城市，需要訪問的個城市編號為1,2,…，，為了便于說明問題，把旅行商問題構造成網絡圖以表示:</

80、p><p>　　— 點集，表示旅行商需要經過的地點。</p><p>　　— 弧集，表示旅行商可能走過的線路段集合。</p><p>　　— 費用矩陣，表示旅行商經過對應弧段(,)所花的費用，如時間、距離、花費等[7]。</p><p>　　求解TSP即要求在加權圖中找到總費用最小的哈密爾頓(Hamilton)回路，這里點0稱為源點。所謂哈密爾頓

81、(Hamilton)回路即指從源點出發(fā)，經過每個頂點一次，且僅僅一次的回路[8]。定義變量如下:</p><p>　　則得到以下數學模型:</p><p><b>　　(4-1)</b></p><p><b>　　(4-2)</b></p><p><b>　　(4-3)</b&g

82、t;</p><p><b>　　(4-4)</b></p><p><b>　　(4-5)</b></p><p>　　其中，（）; S為支路消去約束(sub-tour -breaking約束)，即削去構成不完整線路的解，如圖2所示，兩條支路均滿足分配約束，但沒有構成一條完整的線路，因此不是VSP問題的解。</p&

83、gt;<p>　　3 4</p><p>　　2 6</p><p>　　1 5</p><p><b>　　圖2 支路示意圖</b></p><p>　　五、物流配送車輛

84、優(yōu)化調度模型及求解算法</p><p>　　（一）物流配送車輛優(yōu)化調度問題的提出</p><p>　　雖然物流配送具有多種類型和形式，但大部分物流配送形式中運輸的特點是基本相同的，即將商品從配送中心按一定的要求發(fā)送到多個需求點。</p><p>　　由于運輸任務的性質和特點不同，道路條件及車輛類型不同，即使在相同收發(fā)貨運點間完成同樣任務時，采用的行駛路線方案也可能不

85、同。而車輛按不同運行線路完成同樣的運輸工作時，其利用效果是不一樣的，有時甚至會有很大的差別。因此，在滿足貨運任務要求的前提下，如何選擇最經濟的運行路線，是一項重要的工作。所謂最經濟的運行路線，就是在保證貨物需求的前提下，運輸時間或運輸費用最省的路線。</p><p>　　如何按時按量、經濟高效地配送商品，在很大程度上取決于有效的車輛調度安排，調度方案的優(yōu)化與否，對增加配送效率、減少總費用和提高服務水平具有重要的意

86、義。</p><p>　　約束條件和目標函數不同，對VSP描述和研究方法也不盡相同。本章中，根據系統(tǒng)的實際需求，考慮車輛裝載量限制，研究無時限的純裝或純卸的非滿載VSP及單源最短路徑問題，建立合理的數學模型，通過經典的節(jié)約算法進行修正與Dijkstra單源最短路徑算法分別求解問題。</p><p>　?。ǘ〥ijkstra單源最短路徑算法原理及實現(xiàn)流程</p><p&

87、gt;　　1、Dijkstra單源最短路徑算法的基本原理</p><p>　　單源最短路徑問題就是已知有向帶權圖(簡稱有向網)找出從某個源點到中其余各頂點的最短路徑。Dijkstra是一種按路徑長度遞增序產生各頂點最短路徑的算法。其算法思想為:</p><p>　　設為最短距離已確定的頂點集，一個頂點屬于集合當且僅當從源到該頂點的最短路徑長度已知；－是最短距離尚未確定的頂點集。設為源點，為

88、終點。</p><p><b>　?、?初始化</b></p><p>　　初始化時，只有源點的最短距離是已知的，將源點的最短路徑看作是己生成的源點到其自身的長度為0的路徑。因此，中僅含有源點，－為空。</p><p>　?、?重復以下工作，按路徑長度遞增次序產生各頂點最短路徑</p><p>　　在當前－集中選擇一個最

89、短距離最小的頂點來擴充集，以保證算法按路徑長度遞增的次序產生各頂點的最短路徑。</p><p>　　當－集中僅剩下最短距離為∞的頂點，或者所有－集中的頂點己擴充到集時，源點到所有頂點的最短路徑就求出來了。</p><p><b>　　需要注意是:</b></p><p>　?、?從源點到某頂點的路徑不存在，則可假設該頂點的最短路徑是一條長度為無

90、窮大的虛擬路徑。</p><p>　?、?從源點到終點的最短路徑簡稱為的最短路徑；到的最短路徑長度簡稱為的最短距離。</p><p>　　2、Dijkstra單源最短路徑算法實現(xiàn)流程</p><p>　　在本小節(jié)中，以圖3為例，描述Dijkstra單源最短路徑算法的實現(xiàn)流程。</p><p><b>　　0</b><

91、;/p><p>　　10 100</p><p><b>　　30</b></p><p>　　1 4</p><p>　　50 10 60</p><p>　　2 3</p>

92、<p><b>　　20</b></p><p>　　圖3 距離和最短路徑示意圖 </p><p>　　第一步：初始化變量 </p><p><b>　　表1初始化變量表</b></p><p><b>　　第二步：求解</b></p><p

93、>　　若用表示圖中兩相鄰點與的距離，若與不相鄰，令，顯然，用表示從點到點的最短距離，現(xiàn)要求從源點到其余各點的最短路，如下：</p><p>　?、? －中找出最短距離和相應的頂點，則此時有最短距離，將相應的頂點加入到集合中。</p><p>　?、?查看其余頂點是否與點有連接，若沒有，維持集合,,的和,,的值不變；如果有，將與這兩點之間的距離相加(點和點有相連，距離為)，和為，小于原

94、來的距離∞，更新為,為，如表2中循環(huán)行所示：</p><p>　　表2 Dijkstra算法生成最短路徑過程</p><p>　?、?依次類推，進行循環(huán)，得到表2中的循環(huán)行，當算法結束時，可從任一反復上溯至源點求得頂點的最短路徑，的最后一行就是源點到各頂點的最短路徑長度。圖3中所產生的最短路徑列表如表3所示。</p><p><b>　　表3最短路徑列表&

95、lt;/b></p><p>　　（三）無時限的純裝或純卸非滿載VSP實現(xiàn)</p><p>　　1、節(jié)約算法基本原理</p><p>　　節(jié)約算法是由Clarke和Wright于1964年首次提出的[7] ，自提出后，便得到了普遍的認同。它簡單、易于理解、靈活性好，可分析性及交互式特性都較好，不少算法都局部或是全部應用了節(jié)約算法。它的基本思想是:</p&

96、gt;<p>　　首先把各點單獨與源點相連，構成條僅含一個點的線路?？傎M用為:</p><p>　　，對求和 (5-1)</p><p>　　然后計算將點和連接在一條線路上，費用的“節(jié)約值”為:</p><p><b>　　(5-2)</b></p><p><b&g

97、t;　　(5-3)</b></p><p>　　越大，說明把和連接在一起時總路程減少越多。構造線路時，根據從大到小的順序進行。</p><p>　　2、節(jié)約算法實現(xiàn)流程</p><p>　　本系統(tǒng)中，已知條件為配送中心與配送點以及各配送點之間距離、車輛載重量、車輛的數量、車速以及各個配送點的貨物需求量，求在不違背車輛裝載量要求的約束條件下，如何構成配送線

98、路，使得經過所有配送點(且僅經過一次)并且所走的總路程最少。為滿足實際需求，對經典的節(jié)約算法進行修正，具體流程描述如下:</p><p>　　第一步:使用Dijkstra單源最短路徑算法求配送中心到配送點、配送點到配送點的最短路徑，經典的節(jié)約算法求解物流配送車輛調度問題時，要求知道所有配送點與配送中心以及各配送點之間的最短路徑，然而，我們通常己知的是配送點與配送中心以及各配送點之間的距離，這個距離不一定是最短路徑

99、，如圖3所示。己知點為配送中心，點為配送點，在圖3中我們發(fā)現(xiàn)到點直接距離為，但并非最短路徑，其最短路徑為 。因此，需要通過某些算法求出各點之間最短距離，例如采用單源最短路徑算法求最短路徑。</p><p>　　第二步:計算節(jié)約值，并排列成表格形式。</p><p>　　第三步:在表格中選擇最大元素，考察對應的點和點，檢查是否滿足下列條件。</p><p>　?、?若

100、點和點都在初始化線路上，則可連接點和點,形成以構成線路“”,轉第四步。</p><p>　?、?若點和點中有一個點在已構成的線路上，且或中與配送中心相連，而另一個點在初始化線路上，則連接點和點，得到線路“”或“”,轉第四步。 </p><p>　?、?若點和點位于兩條不同的己構成線路上，且一個為線路中的第一個?？靠蛻簦硪粋€為線路中的最后一個?？靠蛻?，則連接后得到線路段“”,轉第四步。&l

101、t;/p><p>　?、?若點和點在己構成的同一條線路上，則不能再進行連接，轉第四步。</p><p>　　第四步:劃去第行和第列，即點不能再到其它點，而也不能由其它點到達。</p><p>　　第五步:若所有元素均被劃去，則已得到完整線路，算法終止;否則，在未被劃去的元素中選擇最大元素，轉第三步。</p><p>　　由此得到完成客戶需求的車輛

102、的行駛路線，且每輛車滿載運行，當車輛的載重量小于剩余客戶最小需求量時即視為車輛滿載。</p><p><b>　　3、應用舉例</b></p><p>　　設配送中心有項貨物運輸任務，任務用表示，這些任務由配送中心發(fā)出的噸車完成，車速均為，客戶的貨物需求量如表4所示，客戶與配送中心以及各客戶間的距離用表示，如表5所示。</p><p><

103、b>　　表4 貨物需求量表</b></p><p>　　表5點對之間的距離表</p><p>　　把各點之間的距離作為費用，即，如何安排車輛的行駛的行駛路線，使總運行費用最少。</p><p>　　ⅰ) Dijkstra單源最短路徑算法求點對之間的最短路徑</p><p>　　按照表5給定的點對之間的距離，先用Dijkstr

104、a單源最短路徑算法求點對之間的最短路徑，得到最短距離表格，如表6所示：</p><p><b>　　表6最短路徑表格</b></p><p>　　可以看到點和之間的距離由變?yōu)?，中間經過點，表格內括號中的數字表示中間經過的點。</p><p><b>　?、?計算節(jié)約量值</b></p><p>　　

105、根據節(jié)約量公式計算各點對間連接的費用節(jié)約值。</p><p>　　例如，連接點和點時，有：</p><p>　　類似地，可得到連接其它各點對時的費用節(jié)約值，按從大到小的順序示于表7中。</p><p><b>　　表7節(jié)約量表格</b></p><p><b>　?、?構造線路</b></p&

106、gt;<p>　　按照前面所述的無時限的節(jié)約算法實現(xiàn)流程，構造線路，過程如表8所示：</p><p>　　表8點對之間的連接過程</p><p>　　表中第列表示根據表7的順序考察點。表中第列表示考察的兩點的位置，若不滿足位置條件，顯然不能連接，不再考察其它各項，在第列劃，轉其它點對。表中第列表示連接后線路的總任務量，若大于車輛容量，則在第列中劃。</p>&l

107、t;p>　　在連接點對時，要從從左到右和從右到左兩個方向考察，點對從左到右連接過程如表8所示，從右到左的連接也滿足車輛裝載量的要求，所以也滿足，與的連接原理相同得到線路。同理，點對從右到左連接得到線路。 </p><p><b>　　最后得到線路為:</b></p><p><b>　　或，行程為。</b></p>

108、<p><b>　　或，行程為。</b></p><p>　　單獨進行配送得到初始配送距離為，用修正的節(jié)約算法構造路徑后,總行程為,節(jié)約里程，節(jié)約時間為。 </p><p><b>　　六、總結</b></p><p>　　近年來國內外物流產業(yè)正在快速發(fā)展，物流市場在壯大的同時，競爭日趨激烈。隨著物流業(yè)向全球化

109、、信息化及一體化發(fā)展，配送在整個物流系統(tǒng)中的作用變得越來越重要。顧客對物流服務質量要求的提高，以及行業(yè)競爭使物流企業(yè)格外注重在物流配送作業(yè)上的科學與高效管理。車輛路徑問題由于在管理學和運籌學上的重要性，一直以來是一類求解較難的組合優(yōu)化問題，是一個極其具有魅力的優(yōu)化問題，主要是因為它具有很強的現(xiàn)實價值，可產生極其可觀的經濟效益。因此，吸引了全世界無數的科學家、工程師的興趣。</p><p>　　當考慮車輛載重量限制

110、時，TSP問題就轉化為無時限的純裝或純卸非滿載VSP。所以，可以用解決TSP的方法來解決此類VSP。本章中，首先對問題進行抽象，在TSP數學模型的基礎上，加入車載重量約束條件，建立VSP數學模型來描述問題。解決TSP的方法多種多樣，本文首先將物流配送問題及物流配送環(huán)節(jié)中的VRP問題進行系統(tǒng)詳細地闡述，包括對該問題研究的理論依據及存在的問題均作出剖析和總結，將在VRP問題中需要考慮的目標及約束進行綜合，列出一個統(tǒng)一的數學模型。這個模型可以

111、根據不同單位對各目標的重視程度給每個目標輔以不同的權重值，或者將五個目標按優(yōu)先權合理安排目標模型。然后，分析準備采用的算法解決該問題的優(yōu)勢，然后根據建立的數學模型，本文采用C-W節(jié)約算法，通過對經典的C-W節(jié)約算法進行適當的修正，與Dijkstra單源最短路徑算法相結合，得到無時限的純裝或純卸的非滿載車輛調度問題的滿意解。</p><p>　　由于本人實踐經驗不夠豐富，在許多方面還存在不足:</p>