物流配送車輛調度問題畢業設計-資料下載頁

　　

【正文】 各點之間最短距離，例如采用 Dijkstra 單源最短路徑算法求最短路徑。 第二步 :計算節約值 ),( jiS ，并排列成表格形式。 第三步 :在表格中選擇最大元素 ),( jiS ，考察 ),( jiS 對應的點 i 和點 j ，檢查是否滿足下列條件。 ⅰ )若點 i 和點 j 都在初始化線路上，則可連接點 i 和點 j ,形成以構成線路“ 00 ??? ji ” ,轉第四步。 ⅱ )若點 i 和點 j 中有一個點在已構成的線路上，且 i 或 j 中與配送中心相連，而另一個點在初始化線路上，則連接點 i 和點 j ，得到線路“ 00 ??? ji?? ”或“ 00 ??? ??ji ” ,轉第四步。 ⅲ )若點 i 和點 j 位于兩條不同的己構成線路上，且一個為線路中的第一個 停靠客戶，另一個為線路中的最后一個停靠客戶，則連接后得到線路段“ 00 ???? ji ?? ” ,轉第四步。 ⅳ )若點 i 和點 j 在己構成的同一條線路上，則不能再進行連接，轉第四步。 27 第四步 :劃去第 i 行和第 j 列，即 i 點不能再到其它點，而 j 也不能由其它點到達。 第五步 :若所有元素均被劃去，則已得到完整線路，算法終止 。否則，在未被劃去的元素中選擇最大元素，轉第三步。 由此得到完成客戶需求的車輛的行駛路線，且每輛車滿載運行，當車輛的載重量小于剩余客戶最小需求量時即視為車輛滿載。 應用舉例 設配送中心 0 有 5 項貨物運輸任務，任務用 i 表示 ? ?5,2,1 ??i ，這些任務由配送中心發出的 4 噸車完成，車速均為 skm/40 ，客戶的貨物需求量如表 4所示，客戶與配送中心以及各客戶間的距離用 )5,1,0,( ??jidij 表示，如表 5所示。 表 4 貨物需求量表 任務ｉ 1 2 3 4 5 ig （噸） 表 5 點對之間的距離表 i j 0 1 2 3 4 5 0 0 8 11 6 7 10 1 2 8 0 12 13 15 16 8 12 0 4 9 18 3 6 13 4 0 5 16 4 7 15 9 5 0 12 5 10 16 18 16 12 0 28 把各點之間的距離作為費用，即 )5,1,0,( ???? jidc ijij ，如何安排車輛的行駛的行駛路線，使總運行費用最少。 ⅰ ) Dijkstra 單源最短路徑算法求點對之間的最短路徑 按照表 5 給定的點對之間的距離，先用 Dijkstra 單源最短路徑算法求點對之間的最短路徑，得到最短距離表格，如表 6 所示： 表 6最短路徑表格 i j 0 1 2 3 4 5 0 0 8 10(3) 6 7 10 1 2 8 0 12 13 15 16 8 12 0 4 9 18 3 6 13 4 0 5 16 4 7 15 9 5 0 12 5 10 16 18 16 12 0 可以看到點 0 和 2 之間的距離由 11變為 10 ，中間經過點 3 ，表格內括號中的數字表示中間經過的點。 ⅱ )計算節約量值 根據節約量公式 ijjiijji dddCCCjiS ?????? 0000),( 計算各點對間連接的費用節約值。 例如，連接點 1和點 2 時，有： 612108)2,1( 120210 ??????? dddS 類似地 ，可得到連接其它各點對時的費用節約值，按從大到小的順序示于表 7 中。 29 表 7節約量表格 (i， j) （ 2， 3） （ 3， 4） （ 2， 4） （ 1， 2） （ 4， 5） （ 2， 5） （ 1， 5） （ 1， 3） S（ i， j） 12 8 8 6 5 2 2 1 ⅲ )構造線路 按照前面所述的無時限的 WC? 節約算法實現流程，構造線路，過程如表 8 所示 ： 表 8點對 之間的連接過程 1 2 3 4 i → j 兩點位置 ?? igQ 連接否 2 → 3 非線路上點 qggQ ???? 32? 3 → 4 外點 非線路上點 qgggQ ????? 4432 432 ?? 1 → 2 2 → 5 一點為內點 ? 5 → 4 外點 非線路上點 qQ? ? 1 → 5 非線路上點 qggQ ???? 51? 3 → 1 非線路上點 外點 qQ? ? 表中第 1列表示根據表 7 的順序考察點 ji? 。表中第 2 列表示考察的兩點的位置，若不滿足位置條件，顯然不能連接，不再考察其它各項，在第 4列劃 ?，轉其它點對。表中第 3 列表示連接后線路的總任務量，若大于車輛容量，則在第 4 列中劃 ?。 在連接點對時，要從從左到右和從右到左兩個方向考察，點對 )3,2( 從左到右連接過程 如表 8 所示，從右到左的連接也滿足車輛裝載量的要求，所以 23? 也滿足，與 32? 的連接原理相同得到線路 234 ?? 。同理，點對 )5,1( 30 從右到左連接得到線路 0150 ??? 。 最后得到線路為 : 04320 ???? 或 02340 ???? ，行程為 km26 。 0510 ??? 或 0150 ??? ，行程為 km34 。 單獨進行配送得到初始配送距離為 km84242 ?? ，用修正的 WC? 節約算法構造路徑后 ,總行程為 km60 ,節約里程 km24 ，節約時間為 ? 。 六、總結 近年來國內外物流產業正在快速發展 ，物流市場在壯大的同時，競爭日趨激烈。隨著物流業向全球化、信息化及一體化發展，配送在整個物流系統中的作用變得越來越重要。顧客對物流服務質量要求的提高，以及行業競爭使物流企業格外注重在物流配送作業上的科學與高效管理。車輛路徑問題由于在管理學和運籌學上的重要性，一直以來是一類求解較難的組合優化問題，是一個極其具有魅力的優化問題，主要是因為它具有很強的現實價值，可產生極其可觀的經濟效益。因此，吸引了全世界無數的科學家、工程師的興趣。 當考慮車輛載重量限制時， TSP 問題就轉化為無時限的純裝或純卸非滿載 VSP。所以， 可以用解決 TSP 的方法來解決此類 VSP。本章中，首先對問題進行抽象，在 TSP 數學模型的基礎上，加入車載重量約束條件，建立 VSP數學模型來描述問題。解決 TSP 的方法多種多樣，本文首先將物流配送問題及物流配送環節中的 VRP 問題進行系統詳細地闡述，包括對該問題研究的理論依據及存在的問題均作出剖析和總結，將在 VRP 問題中需要考慮的 31 目標及約束進行綜合，列出一個統一的數學模型。這個模型可以根據不同單位對各目標的重視程度給每個目標輔以不同的權重值，或者將五個目標按優先權合理安排目標模型。然后，分析準備采用的算法解決該問題 的優勢，然后根據建立的數學模型，本文采用 CW 節約算法，通過對經典的 CW節約算法進行適當的修正，與 Dijkstra 單源最短路徑算法相結合，得到無時限的純裝或純卸的非滿載車輛調度問題的滿意解。 由于本人實踐經驗不夠豐富，在許多方面還存在不足 : ⅰ )對車輛路徑問題有影響的因素很多，在實際的企業生產運作中，也往往是多個因素的共同作用。應該進而對多因素對 VRP 模型和算法的影響進行分析，而不是單一因素對基本 VRP 問題的模型和算法的影響分析。 ⅱ )不完備信息系統的數據補齊算法有很多，再者 VRP 問題自身又是一個復雜且影 響因素眾多的問題，其影響因素的數據采集也不是容易的事情，對每一種影響因素的缺失值應該分別討論，再來選擇針對不同的缺失值數據補齊算法。 ⅲ )在建立數學模型時，實際上還有多種因素需要考慮，如路況信息 (如堵車現象 )、路面是否粗糙、路口的多少等，均可能影響到車輛的行駛速度和車輛的運送成本，另外還有一些問題需要考慮，如路面粗糙的路線不適宜運載易碎物品等。 ⅳ )在現實生活中一個配送中心可能有許多輛汽車，車輛的載重量可能有所不同，在應用該模型時也應考慮到對于非滿載的線路應該適當安排小載重量的汽車配送，但如果回收物量較多 ，則應該根據實際情況選擇合適的載重量。 32 本文的研究還只是一個初步的探索和嘗試，提出的模型和算法也有待進一步提高和完善，在今后的工作中，將對存在的不足不斷地調整和改進。 參考文獻 [1]郎茂樣 .物流配送車輛調度問題的模型和算法研究 [D][博士學位論文 ].北京 :北方交通大學， 2021 [2]中國物流與采購聯合會 .現代物流產業是我國經濟新的增長點閉 [J].中國物流與采購， 2021 10(8):811 [3]丁俊發 .高度重視現代物流對經濟建設的巨大作用 [J].物流技術， 1998 21(1):2124 [4]李軍 .貨物車輛優化調度理論與方法研究 [D][博士學位論文 ].西安 :西南交通大學， 2021 [5]楊海榮，現代物流系統與管理 [M]，北京郵電大學出版社， 2021 [6]李軍 .郭耀煌 .物流配送車輛優化調度理論與方法 [M].北京 :中國物資出版社， 2021 155156 [7] Dabbzubg G ,Ramser Truck Dispatching Problem Management Science[J]， 1959 10(6):8091 [8] Clark .G Wright J. Scheduling and vehicles from a central depot to number of delivery points [J]. Operations Research， 1964 12(4):1218 [9]胡運權 .運籌學基礎及應用 [M].高等教育出版社， 2021 33 致 謝 在本論文完成之際，我由衷地感謝我的導師王老師。在完成畢業設計期間，王老師在學習和生活各方面給予了我很大的指導和幫助。老師嚴謹的治學態度，淵博的專業學識和深邃的學術思想 ，都給我留下了深刻的印象，為我今后的工作和學習樹立了榜樣。 在大學學習以及畢業論文的寫作期間，得到了很多朋友的支持和鼓勵，特別是舍友們，她們對我在學習上、生活上以及精神上給予了熱心的幫助，在此對他們表示深深的謝意。同時，還要感謝那些不斷給予我鞭策，教會我做人道理的老師和同學們。 最后，要感謝我的家人，感謝他們給我生命，感謝他們給予我生活上的無限關懷和思想上的無限支持，這份親情是我永遠的精神依靠和前進動力。