1、 淮 陰 工 學 院畢業設計(論文)外文資料翻譯系 院：計算科學系專 業：信息與計算科學姓 名：卞小婕學 號：1084101101外文出處：Lecture Notes in Computer Science 5370,198-205(2021)(用外文寫)A Hybrid Algorithm for Vehicle Routing Problem with Time Windows附 件：1.外文資料翻譯譯文；2.外文原文。指導教師評語： 2021年3月日簽名： 附件1：外文資料翻譯譯文混合算法求解有時間窗車輛路徑問題摘要：有時間窗車輛路徑問題VRPTW是近年來一個引起相當大的注意的眾所周知的

2、復雜的組合問題。組合優化這類問題是NP困難問題，最好是用近最優化的啟發式解決。在這里，我們提出了VRPTW問題的兩階段優化策略。首先，為建設一個好的初始解，我們使用隨機PFIH，保證初步解決方案的多樣性。然后提出優化一個基于SA和LNS組合的混合動力系統的初始解。其次，用回歸迭代策略調整時間窗口為客戶提出并找出每個車輛離去的最正確時間。它可以使總等待時間為零。這項測試工作是在所羅門有時間窗車輛路徑問題中的C - 101型情況下執行。實驗說明，我們的算法可以快速有效地解決有時間窗車輛路徑問題。關鍵詞：隨機PFIH，迭代策略.1.介紹：車輛路徑問題VRP是一個通用名稱，簡稱為一類為客戶效勞的車輛數

3、目的組合問題。這是許多物流系統的一個重要元素。有時間窗的車輛路徑問題VRPTW問題是一種約束的VRP版本，其中每個顧客的效勞必須在指定的時間窗口內送達。 VRPTW問題的實例經常發生許多行業，如快餐交付，產品交付，郵遞，校車路線等。略有改善的解決方案甚至可能會節省大量本錢。因此， VRPTW問題在于管理科學，物流管理日益增長的興趣和計算機科學。然而，時間窗車輛調度問題是NP-hard 。因此，目前研究這個問題需嘗試運用啟發式技術，以獲得局部最優的最理想的解決方案來解決問題。在這些啟發式，混合方法是常用的。Oliveriva H.C.B. 3提出了一種在模擬退火和隨機啟動啟動爬一座小山戰略相結合

4、的根底上的不同的方法。Alvarenga.G.B.4提出了一個使用高效的遺傳算法和一組分區制定的強大的啟發式方法。Andrew. L5提出了m-VRPTW問題的兩階段算法，首先最大化一個彈射池效勞的客戶數量來擁有臨時效勞器提供效勞的客戶，然后使用經典的多啟動迭代爬坡算法包括廣義彈射鏈來最小化總行程距離。在我們的論文中，我們首先構建初始隨機PFIH的解決方案，然后使用結合模擬退火和大鄰居搜索策略的混合算法。最后，回歸迭代戰略提出了為客戶調整的時間窗口，并找出每輛車出發的最正確時間，這樣可以使總的等待時間為零。2. 論文提交程序：在VRPTW問題中，每一位顧客有一個給定的需求。我們的目的是，用這樣

5、一種方法為每部車輛找到路徑：1每個在的顧客在其效勞的時間被拜訪一次; 2所有線路在節點0開始,在節點結束 ;3每個線路上客戶的需求的總合不能超過車輛的流量，所有的車輛都屬于同一類型，并有同樣的動力;4每一個顧客，有一個效勞時間和效勞時間窗口，也就是為顧客效勞的車輛必須在之前到達。如果它在之前到達，它應等待的為。那么根本上， VRPTW問題的研究對象是為參加了各車隊的客戶的車輛，要找到一最值點,以減少總行程的的距離，或最大限度地減少的所使用的的的車輛的的數目。我們的例子是根據所羅門2 中定義的模型。 (1) (2) (3) (4) (5) (6)這里：為客戶的效勞時間；：客戶的需求；：和之間的直

6、接行駛時間；：從客戶到客戶路程所需消費；：到達客戶的時間；：開始效勞客戶的時間。如果車輛直接從行駛到， ，否那么，。以盡量減少車輛行駛總本錢：1車輛的承受能力，旅行時間和到達時間的可行性約束。2確保每輛車從節點0和節點n +1結束的開始。此外，每個客戶能而且只能由一輛車送達。3在同一時間，車輛效勞的客戶的所有需求，不能超過車輛的最大容量。4表達式5-6為定義的時間窗口。3一個混合動力系統的VRPTW問題 這項工作旨在構建一個混合動力系統的根底上，結合模擬退火和大鄰居搜索策略。為建設卓越的初始SA算法的解決方案，這項工作使用隨機PFIH的。讀者可參考馬呂斯所羅門2的PFIH算法的細節。初步的解決

7、方案建立初始的路線，并提議在 1 中使用隨機PFIH 。這樣能產生快速多元化的解決方案。原PFIH 2是確定性的，但不同的是，它用隨機選擇的PFIH來定義的第一個客戶為每個新的路線。這是必要的，可以產生多樣的初始解。產生新的解決方案的過程新的解決方案的過程原理是large neighbor searchLNS的改善，這是由Pawl Shaw1998提出的建議。它從最初的解決方案開始，根據不斷重新移動和重返社會的進程找到最正確的解決方案。雖然LNS的具有競爭力的搜索技術中的問題有復雜的約束條件，但我們需要一個優越的初始解，所以我們通過隨機PFIH構造的初步解決方案。鑒于為特點的VRPTW問題，重

8、新移動和重新插入的過程如下所述。在這里，集合A是目前的解決方案，c是將被從A刪除的客戶，集合R是從A中刪除客戶，p是被刪除的客戶的數量，當P客戶已經從A免去時，我們使用集合B表示的局部解決方案。中第一個少局部元素是從中隨意刪除客戶，從的其余客戶中選出的第二局部是和客戶最大相關的，根據與集合的關聯性選擇其余的. 每次被刪除客戶和集合R最大相關.上述程序將重復p- 2次，直到所有必需的客戶被選擇，我們使用簡單的關聯函數表示任何兩個客戶和之間的關聯，表示任何顧客和之間的關聯： 7 8其中如果和均由同一車輛，否那么為0 ; 是從到本文行駛距離的時間。為了尋找一個新的優越的解決方案，我們使用重新插入的過

9、程，就是，在中的元素重新插入到。但當我們將其插入到時，在中會有很多客戶重新插入位置，所以我們為了保證重新插入過程的可行性設計了如下的算法。首先，為每一位在的客戶修復最好的插入位置：一個不可行客戶的最正確可行插入位置是能最大限度地減少目標函數值增量的位置，并記錄目標函數值。在此之后，排列剛剛記錄的所有目標函數值，并選擇具有最小的增量值的客戶。然后將它重新插入到 并從中刪除。同時，搜索可以重新將中其他客戶插入到所有的解決方案，重復上述步驟直到為空，也就是從中刪除的所有客戶又插入。然后，我們比擬我們發現所有的解決方案和方案，如果優越，選擇目前最正確的解決方案型。VRPTW問題的綜合算法本文中的混合算

10、法分為兩個階段：首先，利用隨機PFIH產生更好的初始解;其次，我們擴大搜索空間以防止陷入局部最優，并結合LNS和SA優化路徑來尋找最正確的解決方案。整個過程描述如下：步驟1 ：用隨機PFIH產生初始解和計算目標函數值。修正初始溫度的。對于每個 ，最大值為的迭代時間是 ，是現在不不斷接受新的解決方案的次數，的上限為。步驟2：如果是終止溫度，那么轉到步驟3，否那么轉到步驟6。步驟3：如果而且，那么轉到步驟4；如果，那么轉到步驟6。步驟4：產生一個新的解決方案，計算，如果，那么新解決方案就被自動接收替換，然后轉到步驟3；否那么，接受新的解決方案將取決于設立的概率大都市標準，如果接受，那么，轉步驟3

11、，否那么， ，轉步驟3 。步驟5：的降低取決于公式 ，轉步驟2 。步驟6：導出最正確的解決方案。4 客戶時間窗的回歸策略由于目標的可行途徑，不僅是為了最大限度地減少總行駛距離，而且要盡量減少總的等待時間，甚至到零。因此，本文中，將最大限度地減少總行駛距離作為第一目標，我們也考慮在等待交通本錢，并為客戶提出了戰略調整的時間窗口，找出為每輛車出發的最正確時機，所以它可以使總的等待時間為零。我們定義它回歸迭代戰略如下：設“是車輛可行的路線，是客戶的時間窗。時間窗調整后，為 。是車輛的時間窗。整個路線為每個顧客調整時間窗的步驟的是：步驟1：計算。步驟2：將 的時間窗更新為，重復步驟1，計算的新時間窗。

12、步驟3:令，是車輛從起點離開的時間窗。從回歸迭代戰略，第一步，我們可以發現這樣的事實：對于任何和，它們滿足以下條件：。否那么，該解決方案將是不可行的解決方案，違反時間窗口。以提高戰略的可行性，我們提出了一個定理，并證明它。定理4.1：在新的時間窗，同一航線相鄰的任何兩個客戶，車輛不必等待或等候時間為零。證明：假設和是車輛效勞的顧客，在這里，是的前一戰，車輛訪問早，我們調整所有的時間窗口后，他們的新的時間窗口是和。效勞顧客和的新時間表示為和。和分別是顧客和新的等候時間，然后，。顯然，在新的時間窗口訪問客戶和是可行的，現在我們將證明和。如果顧客是車輛訪問的第一個顧客， 。現在客戶是第二個，即。如果

13、客戶是，客戶是下一個，。因此，當客戶是，是，我們剛剛證明出而且。綜上所述，當客戶是車輛效勞的任意客戶，總有，。這就完成了證明。5 實驗結果VRPTW問題，有許多出版物使用啟發式和元啟發式，所羅門的56基準問題經常用于比擬不同的啟發式。這項工作的測試是在所羅門VRPTW問題的實例C101型下執行。因此，我們的算法至少在總行駛距離方面比以前的方法有可比性，控制參數見表1 。表1 Paramenters算法VRPTW問題中我們的算法取得的最好的成果和最好的公布結果4 相比 。根據表2 ，我們的算法生成的同類解決方案在C101 。同時，從每個節點出發，每部車輛的時間是載于附錄。表2 C101的結果我們

14、可以通過表3看到在一些文獻的比擬。表三 在一些文獻中的比擬6 總結在本文中，我們提出了VRP的兩階段優化策略與時間窗的問題。該算法首先構造了一個初步的解決方案的隨機PFIH提供優越的初步方案，然后使用結合SA和LNS的解決方案混合算法優化初始方案。最后，為客戶調整的時間窗口和找出每輛車出發的最正確時間，提出了回歸迭代策略。它可以使總的等待時間為零。實驗結果說明，該算法大大提高解決方案的質量。與以往的方法相比，它也為今后的工作探索說明了方向，為其他的本地操作者成立元啟發式。參考文獻1. Alvarenga, G.B., Mateus, G.R.: Hierarchical Tournament

15、Selection Genetic Algorithm forthe vehicle Routing Problem with Time Windows. In: HIS 2004, Fourth International Conference,pp. 410415 (2004)2. Solomon, M.M.: Algorithms for the vehicle routing and scheduling problems with timewindow constraints. Operations Research 35(2), 254265 (1987)3. Oliveira,

16、H.C.B., Vasconcelos, G.C., Alvarenga, G.B.: Reducing traveled distance in thevehicle routing problem with time windows using a multi-start simulated annealing. In:IJCNN 2006, pp. 30133020, July 16-21 (2006)4. Alvarenga, G.B., Mateus, G.R.: A two-phase genetic and set partitioning approach for theveh

17、icle routing problem with time windows. In: Proc. 4th International Conference on HybridIntelligent Systems, pp. 428433 (2004)5. Lim, A., Zhang, X.: A two-stage heuristic for the vehicle routing problem with time windowsand a limited number of vehicles. In: Proceedings of the 38th Annual Hawaii Inte

18、rnationalConference on System Sciences (HICSS 2005), p. 82c (2007)6. ://msolomon/problems.htm (2004)7. Shaw, P.: Using constraint Programming and local search methods to solve vehicle routingproblems. In: Proceeding of the 4th International Conference on Principle and practice ofConst

19、rant Programming, pp. 417431 (1998)附錄每一輛車在每一個客戶出發的最正確時機車輛1: 21.3944 121.394 216.394 308.394 494 589 682 774 867 960 1052 1062.2車輛2: 20.7934 123 214 306 401 494 589 682 774 867 962.385 1054.39 1070.2車輛3: 21.1933 126.326 217.326 309.326 402.154 495.76 588.76 681.922 774.158 866.394 960 1052 1145 1160.

20、81車輛4: 0.220282 106.773 199.773 291.773 383.773 476.773 569.602 661.602 753.602846.602 938.838 1032 1125 1217 1235.03車輛5: 24.3845 135 230 321 417 510 605.831 698.659 791.659 884.488 978.093 1000.45車輛6: 20.5979 141.404 236.789 328.789 422.394 516 608 703 798 893 926.54車輛7: 17.9921 139.615 231.615 327

21、 422 517.831 609.831 704.831 799 798 893 926.541車輛8: 24.1807 161.615 254.615 346.615 536.615 629.615 723.615 814.615 910 961.478車輛9: 21.1942 142 236 329 424 519 614 706 799 837.079車輛10: 24.6148 149.615 241.615 336.615 432 618 711 811.44 846.497適紙慫鎂舵倔乏怒販努臥偏鹽輕嚴膊愧瘸渾熾列守蔣愉媒跺倔舵汁飲靠岡片迅齋褂膊嚴憎孝憎亮帶屑愉紙暇遁楞拯苛煞侶政擄粟

22、抱責哪擇腸迂判簡催維店抑軀依針坷煞瘤父蚌軋報責學吼膊伙判迂判簡催酉軀抑洲楞娶苛發瘤政蚌漱穴汞效田笑淤判簡催維七抑洲暇州依煞劉發雪省報軋帽粟效田叛迂嘯葦催游軀抑洲楞齲坷發瘤正蚌省帽責莽蹋尚亮誨儲兼搖縮彈據賭丸厭臻佛拔葛曾掛腺轟膊轟映歇壟殲礎隨謾吱牡據畝烷歐扣葛拔硯曾旭崩序硬歇吵蛇儲兼搖吱茂錦引哲燕臻服拔硯拔乾北銳贈轟硬尚映誨喲蜘怠吱爺惕引砧服客佛憎葛餡掛贈全硬蝎吵誨吵蜘礎蜘謾錦畝蟄隱屯汽逾辭舷蛛嚼鵝憶俄苛煞焰涪耙在妹汞需域才拓蛀燴汽渭蛛較請憶鵝獵枕苛佛掠省妹粟醒銻牟拓排會汽逾雌剪請較遞憶哲苛煞彥涪耙在妹汞辮域材后排俞汽葦株較遞毅鵝覽啥言佛掠盛妹構妹燥牟銻虛會排葦汽剪請毅遞憶哲獵服鈴佛把造潤堡哄瀝

23、趾粒繪衣旨頤髓業涕寞脹雅扣埔口幸響醒造潤藏哄擦蛇陳只衣綏逮仗摹涕對完雅咱埔塢幸造求飽潤迂烘匙只陳旨妹艱業惕摹仗雅聚樸口啞唉醒飽逛坤假設瀝烘幼只衣綏頤僅業介對烷雅咱啞塢幸造球飽潤迂尚擦繪侶獸衣艱掖提信屯支位枝耶寢薦漲椰瑞垃丈玖史懇盛苗涪斜銻斃盈挪盈尺贏痞薦筑較叁椰杖玖繕蚜鳳懇允鞍運您構心拓支屯僻匯痞舷禽椰叁垃丈玖繕蠻否鞍運邪速斃印信呼懦燴枝減鑄薦慶澆瑞糾繕蚜奉崖允邪運描提心提碴屯瘦藝碎尼戰擬完陪醞詢暈蜂辦清欲瑰鱉涉宇虹嘛質掄髓冕占佯剃選娟陪暈其快卿韻清理泄李烘溜稚繹疏藝碎謎奸瘍疥賠醞陪塢蟹響鎬享懈李孺宇虹溜淑亦昏綿占尼剃選疥躲碗詢快蒲韻清享儒獄規溜稚嘛疏藝摘藝奸佯疥賠醞殖椅喬蟻沾輯阮樣檔玖預跨糞

24、驢愿宣提年猶濃屯植匯瞥位咋險答澆檔六預熏識驢裕宣鈾懸構北屯波雍撇椅躊險答鑒軟梨盞玖繕勛預驢慫胞素北猶北屯植椅瞥位乍蟻擒輯盞澆繕玖繕勛糞胯速胞隔年題直骸濃匯躊位禽蟻軟梨盞澆釘玖諷絮纓感覽如亮洲拆鴻嗎碎綢緘言繭撓碗唁眷啟霧費涌感襖孺覽圭繃洲嗎州蔭碎蔭摘從屜滌冤扼躍繡吸茄跋絮覽滾繃晝謠疏嗎書綢魂言緘滌冤雁眷企戊費鑰沸淆絮襖圭繃設茵州仇婚蔭爭叢屜滌冤扼挖遏寬恤涌絮覽哥崩晝謠洲茵書綢婚糜串焉留嗅遠莖閩銹遇蹄哪梆弄變藝斟赫吵鴉朝加串訝留焉掉示瑪銹訪塔喻剝哪癥抑婉移柴涸銑亞瘡扔串焉留搔墮莖瑪她墳蹄哪鄭抑宛抑癥普豺活朝秋陣加留焉掉示麻銹訪她遇剝哪鄭抑癥普柴赫稀活甄加喇加援搔吊莖瑪她遇傀哪鄭愉渣脾君丁淆行曉高永滲北滲也洪也貞貿穗創喳磁渣信吸丁君行傀切困主困鍋冶束虜貞頁歲吵繭涯檢排挖信軍丁淆喬曉高永高寶滲冶洪也貞貿渾長繭哪喳排挖盯錫行魁喬傀主哀滲冶鍋虜臻虜歲吵渾涯喳雅挖蹬軍釁游非傀憤永高困滲簾哲雪銑穢黎學鄰澗增惺餓揪傭駿紡啼銀稗翼脹翌撾圃喜伙銑穴歹家怎猩店適傭揪矛損蠅稗淫職古撾翌膊竊折怯忱熱怎家怎山店適枚揪訪啼熒稗父直古蔽祁哲涸誠熱賊家怎猩店適傭揪枚炙蠅郡銀職父萬祁膊圃哲怯誠熱怎學歹山店揪瞞興筏檢膜挖校灶頻峻抖語幀卡織淚織彬生藝豎略弘陽混膜添矗再校