2014年4月北京聯(lián)合大學學報Apr. 2014第28卷第2期總96期Journal of Beijing Union UniversityVol. 28 No. 2 Sum No. 96水果運輸調(diào)度問題的優(yōu)化朱君，蔡延光，湯雅連(廣東工業(yè)大學自動化學院,廣州 510006)[摘要] 針對帶硬時間窗的水果運輸調(diào)度問題( Fruits in Vehicle Routing Problem with HardTime W indows , FVRPHTW),聯(lián)系實際應用中水果易腐的特性及運輸途中的路況因素,采用蟻群算法、模擬退火算法和禁忌搜索算法來對FVRPHTW求解,并分析3種算法的優(yōu)缺點。實例證明,這些算法對求解水果運輸調(diào)度問題是可行的,模擬退火算法略優(yōu)于其他兩種算法。[關(guān)鍵詞]硬時間窗;水果運輸調(diào)度問題;蟻群算法;模擬退火;禁忌搜索[中圖分類號] 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節(jié)性與周期性及水果的易腐性,因此,縮短水果從0引言水果物流集中中心到水果零售店的運輸時間,可以隨著人們生活水平的日益提高以及保健意識大大降低物流成本,促進水果運輸業(yè)的發(fā)展,水果的增強,水果越來越受到廣大消費者的青睞,水果物流主要模式如圖1所示。水果零售店由于所處運輸逐步得到商家的重視，而水果的產(chǎn)量和流通量地段不一樣,且其營業(yè)時間也并非都是一-樣,所以不斷增加,使得全社會對水果的安全和質(zhì)量也提出本文考慮了不同零售店的時間需求,在合理安排車了更高的要求。隨著水果大型批發(fā)市場的日益成輛時間和路線的前提下,最大限度地降低成本。熟,加強水果物流技術(shù),合理利用物流網(wǎng)絡,能促進JTang等人研究了農(nóng)產(chǎn)品的冷鏈運輸調(diào)度問水果物流業(yè)的進一步發(fā)展,也能增加果農(nóng)收人,同.題,以配送中心和20個大型超市之間的帶容量約時滿足消費者對水果的需求。由于水果消費的季束的農(nóng)產(chǎn)品配送為例,分別利用節(jié)約算法和蟻群算[收稿日期] 2013-10-28 .[基金項目]國家自然科學基金 項目(61074147, 61074185),廣東省自然科學基金項目( S201 10005059,5810000000)廣東省教育廳產(chǎn)學研結(jié)合項目(2012091000171, 2011B090400460),廣東省科技計劃項目(2012B050600028 ,2010B090301042)。[作者簡介]朱君(1991-),男,江西新余人,廣 東工業(yè)大學自動化學院中國煤化工信息技術(shù)與應用:蔡延光(1963-),男,湖北咸寧人,廣東工業(yè)大學自動化學院教授,博士生導:YHCNMHGI智能、決策支持系統(tǒng)等;湯雅連(1986--),女,湖南常德人,廣東工業(yè)大學自動化學院博土研究生,冊究萬向為物流信息技術(shù)與應用。.80北京聯(lián)合大學學報2014年4月種車型。3)硬時間窗約束。4)路況約束。1.2 模型的建立督|有l(wèi)個零售店,第i個零售店的需求量為g;,需要從車場將水果物流集中中心的水果配送給各零售店,有1個車場可派出載重量為q的貨車,已知國外主要水果省外及省內(nèi)主要批g, rand,也接受S2作為新的當前解,S,= S2;否則保為車輛行駛距離約束,其中dj表示車輛k行駛了留當前解Si。零售店i到j的路程。式(6)和式(7)表示兩個變6)如果滿足終止條件,則輸出S,,結(jié)束程序，量之間的關(guān)系。式(8)表示車輛完成任務后,回到即在連續(xù)若千個Metropolis 鏈中新解S2都沒有被原車場。式(9)表示當某輛車配送水果到零售店的接受時終止算法,或是設定結(jié)束溫度。否則按衰減個數(shù)大于等于1時,則參與了配送服務,否則,沒有函數(shù)衰減T后返回2)。參與配送。式(10)表示所有零售店都被服務到。設定控制參數(shù) ]式(11)表示不能超過車輛載重量的限制。式(12)廠初始解S表示保證每輛車服務的零售店總數(shù)小于等于總零punt=0售店數(shù)目。式(13)表示到達零售店i的時間必須在時間窗內(nèi)。式(14)S.,S。 是要求配送水果的零售店需求關(guān)聯(lián),S?！躍,表示服務零售店i的時間必須[解變換得到新解S早于到零售店j的時間，由水果物流集中中心人員Metropolis準則判斷根據(jù)零售店的需求緊急程度制定。式(15)表示到是否接受新解.達j的時間T,為車場到i的時間T.零售店i處的C新的S，k+1 ]卸貨時間i與零售店i到零售店j的時間tq之和。N_lbL?2算法設計2.1模擬退火算法 ，count- count+1,T-qT2.1.1算法思想T<結(jié)束)終止規(guī)則利用當前解的鄰域函數(shù)得到其將滿足藐視準則所有中確定若干候選解，開從的解作為當前解，用其對應的對象替換最早進Y打斷是否滿足入禁忌表中的對特赦準則象，其余禁忌對象的禁忌任期減↓N1,更新“bes_sofar判斷候選解禁忌屬性將處于非禁忌狀態(tài)的最佳候選解作為當前解，用其對應的對象替換最早進入禁忌表中的對象，其余禁忌對象的禁忌任期減1中國煤化工圖3禁忌搜索算法的流程框圖.MHCNM HGFig.3 The process diagram of tabu search algorithm第28卷第2期朱君等:水果運輸調(diào)度問題的優(yōu)化8在第20次迭代后,算法收斂。具體配送信息見法求解結(jié)果如表3所示,3種算法對比結(jié)果如表4表2,各車場分別派出一輛車,最優(yōu)配送距離為所示。最優(yōu)配送網(wǎng)絡如圖4所示,3種算法一次迭524. 04 km,總配送費用為5171.03 元。蟻群算法.代的收斂情況如圖5所示,可見模擬退火算法優(yōu)于和模擬退火算法求解結(jié)果如表2所示,禁忌搜索算另外兩種算法。表1零售店信息表Table 1 The information table of retail stores客戶編號位置坐標需求量/1時間窗/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蚊群算法和模擬退火算法 求解結(jié)果Table 2 The results of ant colony algorithm and simulated annealing algorithm路徑配送時間里程/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禁忌搜索算 法求解結(jié)果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)合大學學報2014年4月.表43種算法對比結(jié)果68優(yōu)化過程Table4 The compare result of the three algorithms66算法總里程/km費用/元 最優(yōu)解 所在代數(shù)64蟻群算法524. 045 171. 032:目62模擬退火算法13能6001禁忌搜索算法禁忌搜索算法529. 695 253. 383:雞580i》文獻[1]中算法.560100p9054080100070迭代次數(shù)60f圖5算法收斂情況 .Fig. 5 The convergence condition40中of algorithms3020果運輸調(diào)度問題模型,并采用模擬退火算法、禁忌902030405060708090100搜索算法及文獻[1]中提到的算法對所建立的模型求解,實驗證明，模擬退火算法能有效地求解此類圖4最優(yōu)配送 網(wǎng)絡.問題且優(yōu)于另外兩種算法。接下來可以進一-步考Fig.4 The best distribution network慮水果運輸途中的風險問題、車輛運輸?shù)哪芎膯栴}道路約束、需求模糊問題、速度約束和運輸環(huán)境4結(jié)束語等問題,超大規(guī)模的客戶群模型和算法的不斷改進文章研究了帶硬時間窗的具有需求關(guān)聯(liá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] 黃華芳，門建婷,陳紹慧，等.基于改進蟻群算法的果蔬運輸車輛路徑優(yōu)化的研究[J].保鮮與加工, 2011, 11(3):24 - 27.[3]張 晶成.基于改進蚊群算法的蔬菜物流配送車輛優(yōu)化調(diào)度研究[D].長沙:長沙理工大學, 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.