【正文】 。同時(shí)，還要感謝那些不斷給予我鞭策，教會(huì)我做人道理的老師和同學(xué)們。老師嚴(yán)謹(jǐn)?shù)闹螌W(xué)態(tài)度，淵博的專業(yè)學(xué)識(shí)和深邃的學(xué)術(shù)思想 ，都給我留下了深刻的印象，為我今后的工作和學(xué)習(xí)樹立了榜樣。 參考文獻(xiàn) [1]郎茂樣 .物流配送車輛調(diào)度問題的模型和算法研究 [D][博士學(xué)位論文 ].北京 :北方交通大學(xué)， 2021 [2]中國(guó)物流與采購(gòu)聯(lián)合會(huì) .現(xiàn)代物流產(chǎn)業(yè)是我國(guó)經(jīng)濟(jì)新的增長(zhǎng)點(diǎn)閉 [J].中國(guó)物流與采購(gòu)， 2021 10(8):811 [3]丁俊發(fā) .高度重視現(xiàn)代物流對(duì)經(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].北京 :中國(guó)物資出版社， 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]胡運(yùn)權(quán) .運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用 [M].高等教育出版社， 2021 33 致 謝 在本論文完成之際，我由衷地感謝我的導(dǎo)師王老師。 ⅳ )在現(xiàn)實(shí)生活中一個(gè)配送中心可能有許多輛汽車，車輛的載重量可能有所不同，在應(yīng)用該模型時(shí)也應(yīng)考慮到對(duì)于非滿載的線路應(yīng)該適當(dāng)安排小載重量的汽車配送，但如果回收物量較多 ，則應(yīng)該根據(jù)實(shí)際情況選擇合適的載重量。 ⅱ )不完備信息系統(tǒng)的數(shù)據(jù)補(bǔ)齊算法有很多，再者 VRP 問題自身又是一個(gè)復(fù)雜且影 響因素眾多的問題，其影響因素的數(shù)據(jù)采集也不是容易的事情，對(duì)每一種影響因素的缺失值應(yīng)該分別討論，再來(lái)選擇針對(duì)不同的缺失值數(shù)據(jù)補(bǔ)齊算法。 由于本人實(shí)踐經(jīng)驗(yàn)不夠豐富，在許多方面還存在不足 : ⅰ )對(duì)車輛路徑問題有影響的因素很多，在實(shí)際的企業(yè)生產(chǎn)運(yùn)作中，也往往是多個(gè)因素的共同作用。這個(gè)模型可以根據(jù)不同單位對(duì)各目標(biāo)的重視程度給每個(gè)目標(biāo)輔以不同的權(quán)重值，或者將五個(gè)目標(biāo)按優(yōu)先權(quán)合理安排目標(biāo)模型。本章中，首先對(duì)問題進(jìn)行抽象，在 TSP 數(shù)學(xué)模型的基礎(chǔ)上，加入車載重量約束條件，建立 VSP數(shù)學(xué)模型來(lái)描述問題。 當(dāng)考慮車輛載重量限制時(shí)， TSP 問題就轉(zhuǎn)化為無(wú)時(shí)限的純裝或純卸非滿載 VSP。車輛路徑問題由于在管理學(xué)和運(yùn)籌學(xué)上的重要性，一直以來(lái)是一類求解較難的組合優(yōu)化問題，是一個(gè)極其具有魅力的優(yōu)化問題，主要是因?yàn)樗哂泻軓?qiáng)的現(xiàn)實(shí)價(jià)值，可產(chǎn)生極其可觀的經(jīng)濟(jì)效益。隨著物流業(yè)向全球化、信息化及一體化發(fā)展，配送在整個(gè)物流系統(tǒng)中的作用變得越來(lái)越重要。 單獨(dú)進(jìn)行配送得到初始配送距離為 km84242 ?? ，用修正的 WC? 節(jié)約算法構(gòu)造路徑后 ,總行程為 km60 ,節(jié)約里程 km24 ，節(jié)約時(shí)間為 ? 。 最后得到線路為 : 04320 ???? 或 02340 ???? ，行程為 km26 。 在連接點(diǎn)對(duì)時(shí)，要從從左到右和從右到左兩個(gè)方向考察，點(diǎn)對(duì) )3,2( 從左到右連接過程 如表 8 所示，從右到左的連接也滿足車輛裝載量的要求，所以 23? 也滿足，與 32? 的連接原理相同得到線路 234 ?? 。表中第 2 列表示考察的兩點(diǎn)的位置，若不滿足位置條件，顯然不能連接，不再考察其它各項(xiàng)，在第 4列劃 ?，轉(zhuǎn)其它點(diǎn)對(duì)。 例如，連接點(diǎn) 1和點(diǎn) 2 時(shí)，有： 612108)2,1( 120210 ??????? dddS 類似地 ，可得到連接其它各點(diǎn)對(duì)時(shí)的費(fèi)用節(jié)約值，按從大到小的順序示于表 7 中。 ⅰ ) Dijkstra 單源最短路徑算法求點(diǎn)對(duì)之間的最短路徑 按照表 5 給定的點(diǎn)對(duì)之間的距離，先用 Dijkstra 單源最短路徑算法求點(diǎn)對(duì)之間的最短路徑，得到最短距離表格，如表 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 可以看到點(diǎn) 0 和 2 之間的距離由 11變?yōu)?10 ，中間經(jīng)過點(diǎn) 3 ，表格內(nèi)括號(hào)中的數(shù)字表示中間經(jīng)過的點(diǎn)。 應(yīng)用舉例 設(shè)配送中心 0 有 5 項(xiàng)貨物運(yùn)輸任務(wù)，任務(wù)用 i 表示 ? ?5,2,1 ??i ，這些任務(wù)由配送中心發(fā)出的 4 噸車完成，車速均為 skm/40 ，客戶的貨物需求量如表 4所示，客戶與配送中心以及各客戶間的距離用 )5,1,0,( ??jidij 表示，如表 5所示。否則，在未被劃去的元素中選擇最大元素，轉(zhuǎn)第三步。 27 第四步 :劃去第 i 行和第 j 列，即 i 點(diǎn)不能再到其它點(diǎn)，而 j 也不能由其它點(diǎn)到達(dá)。 ⅲ )若點(diǎn) i 和點(diǎn) j 位于兩條不同的己構(gòu)成線路上，且一個(gè)為線路中的第一個(gè) ?？靠蛻?，另一個(gè)為線路中的最后一個(gè)?？靠蛻簦瑒t連接后得到線路段“ 00 ???? ji ?? ” ,轉(zhuǎn)第四步。 ⅰ )若點(diǎn) i 和點(diǎn) j 都在初始化線路上，則可連接點(diǎn) i 和點(diǎn) j ,形成以構(gòu)成線路“ 00 ??? ji ” ,轉(zhuǎn)第四步。 第二步 :計(jì)算節(jié)約值 ),( jiS ，并排列成表格形式。己知 0 點(diǎn)為配送中心， 4,3,2,1 點(diǎn)為配送點(diǎn)，在圖 3 中我們發(fā)現(xiàn) 0 到 4 點(diǎn)直接距離為 10 ，但并非最短路徑，其最短路徑為)4230(60 ??? 。 WC? 節(jié)約算法實(shí)現(xiàn)流程 本系統(tǒng)中，已知條件為配送中心與配送點(diǎn)以及各配送點(diǎn)之間距離、車輛載重量、車輛的數(shù)量、車速以及各個(gè)配送點(diǎn)的貨物需求量，求在不違背車輛裝載量要求的約束條件下，如何構(gòu)成配送線路，使得經(jīng)過所有配送點(diǎn)(且僅經(jīng)過一次 )并且所走的總路程最少?？傎M(fèi)用為 : ?? ?? 00 ii CCZ ，對(duì) i 求和 ni ?,2,1? (51) 然后計(jì)算將點(diǎn) i 和 j 連接在一條線路上，費(fèi)用的“節(jié)約值”為 : ijjijijijjii CCCCCCCCCCjiS ?????????? 00000000 )(),( (52) jiij CCCijS ??? 00),( (53) ),( jiS 越大，說(shuō)明把 i 和 j 連接在一起時(shí)總路程減少越多。它簡(jiǎn)單、易于理解、靈活性好，可分析性及交互 式特性都較好，不少算法都局部或是全部應(yīng)用了 WC? 節(jié)約算法。圖 3 中所產(chǎn)生的最短路徑列表如表 3 所示。 0 10 100 30 1 4 50 10 60 2 3 20 圖 3 距離和最短路徑示意圖 第一步：初始化變量 表 1初始化變量表 變量名稱 初始值 含義 S S={0},0為圖 3中的源點(diǎn) 最短路徑已確定的頂點(diǎn)集 VS VS={1,2,3,4} 最短距離尚未確定的頂點(diǎn)集 D 表 2 中第一行 D{0},? D{4},∞ 表示頂點(diǎn)與原點(diǎn)之間沒有連線 已知原點(diǎn)到任意頂點(diǎn)的距離集合 P 表 2 中第一行 P{0},? P{4},1 表示頂點(diǎn)和原點(diǎn)之間沒有 連線 算法實(shí)現(xiàn)過程當(dāng)前產(chǎn)生的最短距離被哪個(gè)頂點(diǎn)改變 第二步：求解 若用 ijd 表示圖中兩相鄰點(diǎn) i與 j 的距離，若 i與 j 不相鄰，令??ijd ，顯然 0?iid ，用 siL 表示從 s點(diǎn)到 i點(diǎn)的最短距離，現(xiàn)要求從源點(diǎn) 0 ? ?000?L 到其余各點(diǎn)的最短路，如下： 24 ⅰ ) V － S 中找出最短距離 10}1{ ?D 和相應(yīng)的頂點(diǎn) 1，則此時(shí)有最短距離 10100001 ??? LL ， 將相應(yīng)的頂點(diǎn) 1加入到集合 S 中。 ⅱ )從源點(diǎn) s 到終點(diǎn) v 的最短路徑簡(jiǎn)稱為 v 的最短路徑； s 到 v 的最短路 23 徑長(zhǎng)度簡(jiǎn)稱為 v 的最短距離。 當(dāng) V － S 集中僅剩下最短距離為∞的頂點(diǎn)，或者所有 V － S 集中的頂點(diǎn)己擴(kuò)充到 S 集時(shí)，源 點(diǎn)到所有頂點(diǎn)的最短路徑就求出來(lái)了。因此， S 中僅含有源點(diǎn)， V － S 為空。設(shè) s為源點(diǎn)， v 為終點(diǎn)。 Dijkstra 是一種按路徑長(zhǎng)度遞增序產(chǎn)生各頂點(diǎn)最短路徑的算法。本章中，根據(jù)系統(tǒng)的實(shí)際需求，考慮車輛裝載量限制，研究無(wú)時(shí)限的純裝或純卸的非滿載 VSP 及 單源最短路徑問題， 建立合理的數(shù)學(xué)模型，通過經(jīng)典的WC? 節(jié)約算法進(jìn)行修正與 Dijkstra 單源最短路徑算法分別求解問題。 如何按時(shí)按量、經(jīng)濟(jì)高效地配送商品，在很大程度上取決于有效的車輛調(diào)度安排，調(diào)度方案的優(yōu)化與否，對(duì)增加配 送效率、減少總費(fèi)用和提高服務(wù)水平具有重要的意義。因此，在滿足貨運(yùn)任務(wù)要求的前提下，如何選擇最經(jīng)濟(jì)的運(yùn)行路線，是一項(xiàng)重要的工作。 由于運(yùn)輸任務(wù)的性質(zhì)和特點(diǎn)不同，道路條件及車輛類型不同，即使在相同收發(fā)貨運(yùn)點(diǎn)間完成同樣任務(wù)時(shí)，采用的行駛路線方案也可能不同。 S 為支路消去約束 (subtour breaking約束 )，即削去構(gòu)成不完整線路的解，如圖 2所示，兩條支路均滿足分配 約束，但沒有構(gòu)成一條完整的線路，因此不是 VSP 問題的解。定義變量如下 : ???? 不在線路上，若 在線路上，若 ),(0 ),(1 ji jix ij 則得到以下數(shù)學(xué)模型 : iji j ij xCZ ? ??min (41) 10???ni ijx nj ,1,0 ?? (42) 10???nj ijx ni ,1,0 ?? (43) SxX ij ?? )( 錯(cuò)誤 ! 未找到引用源。 求解 TSP 即要求在加權(quán)圖 G 中找到總費(fèi)用最小的哈密爾頓 (Hamilton)回路，這里點(diǎn) 0 稱為源點(diǎn)。 },1,0,),{( njijiA ??? — 弧集，表示旅行商可能走過的線路段集合。 TSP的數(shù)學(xué)模型 一般 TSP 指一個(gè)旅行商訪問所有城市。 TSP 一般描述為 :旅行商從駐地出發(fā)，經(jīng)所要去的城市至少一次后返回原地，應(yīng)如何安排其旅行線路，才能使總的旅行距離 (或時(shí)間、費(fèi)用等 )最少。 （三）旅行商問題 問題概述 旅行商問題 (Traveling Salesman Problem，簡(jiǎn)稱 TSP)是運(yùn)籌學(xué)、圖論以及組合優(yōu)化中的著名難題，由于其有廣泛的應(yīng)用背景，引起了人們的極大興趣。 Dijkstra 算法是目前公認(rèn)的解決在權(quán) ij? 錯(cuò)誤 !未找到引用源。求解物流網(wǎng)絡(luò)的最短路就是求出在每一對(duì) O ― D 對(duì)子之間的最短運(yùn)輸距離、最短行駛時(shí)間以及最省的運(yùn)輸費(fèi)用。 在運(yùn)輸網(wǎng)絡(luò)的每一個(gè) O ― D 對(duì)子之間的最小路徑，稱為最短路。 （二）最短路問題 最短路問題 是圖論中的基本問題，許多實(shí)際問題都可以用它來(lái)解決，例如管道的鋪設(shè)、線路的安排、廠區(qū)的布局、設(shè)備更新等等。賦權(quán)的圖稱為網(wǎng)絡(luò)圖。 對(duì)于實(shí)際問題構(gòu)成的圖，不僅