水果運輸調度問(wèn)題的優(yōu)化

2014年4月北京聯(lián)合大學(xué)學(xué)報Apr. 2014第28卷第2期總96期Journal of Beijing Union UniversityVol. 28 No. 2 Sum No. 96水果運輸調度問(wèn)題的優(yōu)化朱君，蔡延光，湯雅連(廣東工業(yè)大學(xué)自動(dòng)化學(xué)院,廣州 510006)[摘要] 針對帶硬時(shí)間窗的水果運輸調度問(wèn)題( Fruits in Vehicle Routing Problem with HardTime W indows , FVRPHTW),聯(lián)系實(shí)際應用中水果易腐的特性及運輸途中的路況因素,采用蟻群算法、模擬退火算法和禁忌搜索算法來(lái)對FVRPHTW求解,并分析3種算法的優(yōu)缺點(diǎn)。實(shí)例證明,這些算法對求解水果運輸調度問(wèn)題是可行的,模擬退火算法略?xún)?yōu)于其他兩種算法。[關(guān)鍵詞]硬時(shí)間窗;水果運輸調度問(wèn)題;蟻群算法;模擬退火;禁忌搜索[中圖分類(lèi)號] F 252.1[文獻標志碼] A[文章編號] 1005-0310(2014 )02-0079-06Optimization of Vehicle Routing Problem for FruitsZHU Jun, CAI Yan-guang, TANG Ya-lian( School of Automation, Guangdong University of Technology, Guangzhou 510006 , China)Abstract: Aiming at FVRPHTW ( Fruits in Vehicle Routing Problem with Hard Time W indows)，considering thepractical problem of fruit decay as well as the road condition, the fundamental principle of SA ( simulatedannealing) and TS( tabu search) were introduced, and analysis on the advantages and disadvantages of thesealgorithms were made. The result shows that these algorithms are flexible to solve FVRPHTW, and SA is betterthan the other two algorithms.Key words: Hard time windows; FVRPHTW; Ant colony algorithm; Simulated annealing; Tabu search節性與周期性及水果的易腐性,因此,縮短水果從0引言水果物流集中中心到水果零售店的運輸時(shí)間,可以隨著(zhù)人們生活水平的日益提高以及保健意識大大降低物流成本,促進(jìn)水果運輸業(yè)的發(fā)展,水果的增強,水果越來(lái)越受到廣大消費者的青睞,水果物流主要模式如圖1所示。水果零售店由于所處運輸逐步得到商家的重視，而水果的產(chǎn)量和流通量地段不一樣,且其營(yíng)業(yè)時(shí)間也并非都是一-樣,所以不斷增加,使得全社會(huì )對水果的安全和質(zhì)量也提出本文考慮了不同零售店的時(shí)間需求,在合理安排車(chē)了更高的要求。隨著(zhù)水果大型批發(fā)市場(chǎng)的日益成輛時(shí)間和路線(xiàn)的前提下,最大限度地降低成本。熟,加強水果物流技術(shù),合理利用物流網(wǎng)絡(luò ),能促進(jìn)JTang等人研究了農產(chǎn)品的冷鏈運輸調度問(wèn)水果物流業(yè)的進(jìn)一步發(fā)展,也能增加果農收人,同.題,以配送中心和20個(gè)大型超市之間的帶容量約時(shí)滿(mǎn)足消費者對水果的需求。由于水果消費的季束的農產(chǎn)品配送為例,分別利用節約算法和蟻群算[收稿日期] 2013-10-28 .[基金項目]國家自然科學(xué)基金 項目(61074147, 61074185),廣東省自然科學(xué)基金項目( S201 10005059,5810000000)廣東省教育廳產(chǎn)學(xué)研結合項目(2012091000171, 2011B090400460),廣東省科技計劃項目(2012B050600028 ,2010B090301042)。[作者簡(jiǎn)介]朱君(1991-),男,江西新余人,廣 東工業(yè)大學(xué)自動(dòng)化學(xué)院中國煤化工信息技術(shù)與應用:蔡延光(1963-),男,湖北咸寧人,廣東工業(yè)大學(xué)自動(dòng)化學(xué)院教授,博士生導:YHCNMHGI智能、決策支持系統等;湯雅連(1986--),女,湖南常德人,廣東工業(yè)大學(xué)自動(dòng)化學(xué)院博土研究生,冊究萬(wàn)向為物流信息技術(shù)與應用。.80北京聯(lián)合大學(xué)學(xué)報2014年4月種車(chē)型。3)硬時(shí)間窗約束。4)路況約束。1.2 模型的建立督|有l個(gè)零售店,第i個(gè)零售店的需求量為g;,需要從車(chē)場(chǎng)將水果物流集中中心的水果配送給各零售店,有1個(gè)車(chē)場(chǎng)可派出載重量為q的貨車(chē),已知國外主要水果省外及省內主要批g, rand,也接受S2作為新的當前解,S,= S2;否則保為車(chē)輛行駛距離約束,其中dj表示車(chē)輛k行駛了留當前解Si。零售店i到j(luò )的路程。式(6)和式(7)表示兩個(gè)變6)如果滿(mǎn)足終止條件,則輸出S,,結束程序，量之間的關(guān)系。式(8)表示車(chē)輛完成任務(wù)后,回到即在連續若千個(gè)Metropolis 鏈中新解S2都沒(méi)有被原車(chē)場(chǎng)。式(9)表示當某輛車(chē)配送水果到零售店的接受時(shí)終止算法,或是設定結束溫度。否則按衰減個(gè)數大于等于1時(shí),則參與了配送服務(wù),否則,沒(méi)有函數衰減T后返回2)。參與配送。式(10)表示所有零售店都被服務(wù)到。設定控制參數 ]式(11)表示不能超過(guò)車(chē)輛載重量的限制。式(12)廠(chǎng)初始解S表示保證每輛車(chē)服務(wù)的零售店總數小于等于總零punt=0售店數目。式(13)表示到達零售店i的時(shí)間必須在時(shí)間窗內。式(14)S.,S。 是要求配送水果的零售店需求關(guān)聯(lián),S?！躍,表示服務(wù)零售店i的時(shí)間必須[解變換得到新解S早于到零售店j的時(shí)間，由水果物流集中中心人員Metropolis準則判斷根據零售店的需求緊急程度制定。式(15)表示到是否接受新解.達j的時(shí)間T,為車(chē)場(chǎng)到i的時(shí)間T.零售店i處的C新的S，k+1 ]卸貨時(shí)間i與零售店i到零售店j的時(shí)間tq之和。N_lbL?2算法設計2.1模擬退火算法 ，count- count+1,T-qT2.1.1算法思想T<結束)終止規則利用當前解的鄰域函數得到其將滿(mǎn)足藐視準則所有中確定若干候選解，開(kāi)從的解作為當前解，用其對應的對象替換最早進(jìn)Y打斷是否滿(mǎn)足入禁忌表中的對特赦準則象，其余禁忌對象的禁忌任期減↓N1,更新“bes_sofar判斷候選解禁忌屬性將處于非禁忌狀態(tài)的最佳候選解作為當前解，用其對應的對象替換最早進(jìn)入禁忌表中的對象，其余禁忌對象的禁忌任期減1中國煤化工圖3禁忌搜索算法的流程框圖.MHCNM HGFig.3 The process diagram of tabu search algorithm第28卷第2期朱君等:水果運輸調度問(wèn)題的優(yōu)化8在第20次迭代后,算法收斂。具體配送信息見(jiàn)法求解結果如表3所示,3種算法對比結果如表4表2,各車(chē)場(chǎng)分別派出一輛車(chē),最優(yōu)配送距離為所示。最優(yōu)配送網(wǎng)絡(luò )如圖4所示,3種算法一次迭524. 04 km,總配送費用為5171.03 元。蟻群算法.代的收斂情況如圖5所示,可見(jiàn)模擬退火算法優(yōu)于和模擬退火算法求解結果如表2所示,禁忌搜索算另外兩種算法。表1零售店信息表Table 1 The information table of retail stores客戶(hù)編號位置坐標需求量/1時(shí)間窗/h(40. 00 ,40.00)1.9[5:00 7:00]2(46. 47 ,46.10)3.3[5:00 6:00](82. 47 ,94.44)2.8[5 :006:00](30. 09 ,92.54)1.2[6:30 7:30](72. 39 ,53.37)2.3(45. 23,17.24)3. 2[6:30 7:00](22. 00 ,56.05)2.5[5:30 6:00](80. 47 ,27.02)1.1[6:30 8:10](47. 20 ,96.29)[7:00 8:00](80. 30 ,37.38)1.5[6:00 8:00]1(14. 05 ,78.12)0.9[6:00 6:30](86. 53 ,47.38)0.6[6:00 7:30](21. 52 ,95.59)0.8[6:30 8:00]4(89.41,67. 13)2. 2(18. 09 ,92.55)1.3[6:00 7:00] .6(95. 00 ,56.00)2.2[5 :30 7:10](19. 00 ,30.00)[5 :50 6:30](44. 00 ,55.00)[5 :00 6:00](66. 00 ,10.00)2.0[7 :00 8:00]20(90. 00 ,95.00)4.5[6:00 7:00 ]表2蚊群算法和模擬退火算法 求解結果Table 2 The results of ant colony algorithm and simulated annealing algorithm路徑配送時(shí)間里程/km載重/t費用/元0-2-1-17-6-05:00-5:05 -5:24-5:57 -6:36 -7:1999.709.91 007. 030-5-16-12-10-8-19-0 5:00-5:23 -5:56 -6:18-6:40 -7:00 -7:32 -8:25145. 059. 71426.99.0-3-20-14-05:00-5:33 -6:32-7:10 -8:03133. 449.51 287. 680-18-7-11-15-13-4-9 5:00-5:08 -5:40-6:13 -6:38-6:53 -7:12 -7:38-8: 145. 859.81 449.33-34合計524.0438.9.5 171. 03表3禁忌搜索算 法求解結果Table3 The results of tabu search里程/km載重/1費用0-2-1-17-6-19-05:00-5:05 -5:24-5:57 -6:36 -7:08 -8:01131. 6611.9 1 586. 750-5-14-16-12-10-8-0.5:00-5:23-6:00-7:00 -7:22 -7:44-8:04-8:52 129. 389.9 1 300. 860-3-20 -0.5:00-5:33 -6:32 -7:42122. 807.3916. 440-18-7-11-15-13-4-9-05:00-5:08 -5:40-6:13-6:38 -6:53 -7:12 -7:38145. 859.81 449. 33-8:34中國煤化工MYHCNMHG.9 5253.38 ..84北京聯(lián)合大學(xué)學(xué)報2014年4月.表43種算法對比結果68優(yōu)化過(guò)程Table4 The compare result of the three algorithms66算法總里程/km費用/元 最優(yōu)解 所在代數64蟻群算法524. 045 171. 032:目62模擬退火算法13能6001禁忌搜索算法禁忌搜索算法529. 695 253. 383:雞580i》文獻[1]中算法.560100p9054080100070迭代次數60f圖5算法收斂情況 .Fig. 5 The convergence condition40中of algorithms3020果運輸調度問(wèn)題模型,并采用模擬退火算法、禁忌902030405060708090100搜索算法及文獻[1]中提到的算法對所建立的模型求解,實(shí)驗證明，模擬退火算法能有效地求解此類(lèi)圖4最優(yōu)配送 網(wǎng)絡(luò ).問(wèn)題且優(yōu)于另外兩種算法。接下來(lái)可以進(jìn)一-步考Fig.4 The best distribution network慮水果運輸途中的風(fēng)險問(wèn)題、車(chē)輛運輸的能耗問(wèn)題道路約束、需求模糊問(wèn)題、速度約束和運輸環(huán)境4結束語(yǔ)等問(wèn)題,超大規模的客戶(hù)群模型和算法的不斷改進(jìn)文章研究了帶硬時(shí)間窗的具有需求關(guān)聯(lián)的水.也是下一步需要研究的熱點(diǎn)。[參考文獻][ 1 ] TangJ, Liu K, Chen Q. Study on cold chain logistics of vehicle rouing problem for agricultural products[C]//SericeOperations and Logistics, and Infomatics (SOLI) , 2013 IEEE Inemational Conference on, IEEE, 2013: 317 -322.[2] 黃華芳，門(mén)建婷,陳紹慧，等.基于改進(jìn)蟻群算法的果蔬運輸車(chē)輛路徑優(yōu)化的研究[J].保鮮與加工, 2011, 11(3):24 - 27.[3]張 晶成.基于改進(jìn)蚊群算法的蔬菜物流配送車(chē)輛優(yōu)化調度研究[D].長(cháng)沙:長(cháng)沙理工大學(xué), 2008.[ 4] Banos R, OrtegaJ, Gil C, et al. A Simulated Anealing-based parallel muliobjective approach to vehicle routing problemswith time windows[J]. Expert Systems with Applications, 2013, 40(4) :1696 - 1707.[5 ] ZidiI, Mesghouni K, Zidi K, et al. A mulibjective simulated annealing for the muli-criteria dial a ride problem[J].Engineering Applications of Artificial Intelligence, 2012, 25(6):1121 -1131.[6] Cordeau JF, Maischberger M. A parallel iterated tabu search heurstie for vehicle rouing problems [J]. Computers &Operations Research, 2012, 39(9): 2033 - 2050. .[7] Khanh P N, Crainic T C, Toulouse M. A Tabu Search for Time-dependent Multi zone Muli tip Vehicle Routing Problemwith Time w indows[J]. European Jourmal of Operational Research, 2013, 231(1):43 -56.(責任編輯 李亞青)中國煤化工MHCNMHG.