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