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