[1]王永胜,万 龙,李胜胜.基于改进的禁忌搜索算法求解带2维装箱约束的低碳车辆路径问题[J].江西师范大学学报(自然科学版),2017,(04):354-359.
 WANG Yongsheng,WAN Long,LI Shengsheng.The Enhanced Tabu Search Algorithm for Solving Low-Carbon Vehicle Routing Problem with Two-Dimensional Box Constraints[J].Journal of Jiangxi Normal University:Natural Science Edition,2017,(04):354-359.
点击复制

基于改进的禁忌搜索算法求解带2维装箱约束的低碳车辆路径问题()
分享到:

《江西师范大学学报》(自然科学版)[ISSN:1006-6977/CN:61-1281/TN]

卷:
期数:
2017年04期
页码:
354-359
栏目:
出版日期:
2017-09-01

文章信息/Info

Title:
The Enhanced Tabu Search Algorithm for Solving Low-Carbon Vehicle Routing Problem with Two-Dimensional Box Constraints
作者:
王永胜万 龙李胜胜
1.江西财经大学信息管理学院,江西 南昌 330013
Author(s):
WANG YongshengWAN LongLI Shengsheng
1.School of Information Management,Jiangxi University of Finance and Economics,Nanchang Jiangxi 330013,China
关键词:
低碳车辆路径问题 改进的禁忌搜索 贪心算法 2维装箱约束
Keywords:
the vehicle routing problem in low carbon enhanced tabu search algorithm greedy algorithm two-dimensional packing constraint
分类号:
O 223
文献标志码:
A
摘要:
同时考虑2维装箱和车辆路径2个NP难问题,以碳排放量为目标函数,对低碳环境下带2维装箱约束的车辆路径问题进行研究.求解思路是以禁忌搜索算法(Tabu Search,TS)为主要框架,然后基于贪心的思想采用4种启发式装箱策略生成初始解,并通过改进编码解码方式以及使用动态增长的禁忌长度对TS算法进行改进; 由给出算例的计算结果可知,改进的禁忌搜索算法对于求解该类问题具有一定的优越性.
Abstract:
Two NP hard problems of two-dimensional packing and vehicle path are considered,and Carbon emissions are taken as the objective function,which studies the vehicle routing problem(2L-CVRP)with two-dimensional packing constraints in low-carbon environment.The main idea is to take the tabu search algorithm(Tabu Search TS)as the main frame for this problem and use four heuristic boxing strategy to generate the initial solution based on the greedy idea,by improving the encoding and decoding methods and using the dynamic growth of the tabu length of the TS algorithm to enhance this algorithm.The results show that the enhanced tabu search algorithm has some advantages for solving this kinds of problems.

参考文献/References:

[1] 张如云,刘清.考虑低碳的城市配送车辆路径优化模型研究 [J].工业工程与管理,2015,20(4):29-34.
[2] Baker B S,Coffman E G J,Rivest R L.Orthogonal packings in two dimensions [J].Siam Journal on Computing,1980,9(4):846-855.
[3] Wei Lijun,Qin Hu,Cheang B,et al.An efficient intelligent search algorithm for the two-dimensional rectangular strip packing problem [J].International Transactions in Operational Research,2016,23(1/2):65-92.
[4] 张德富,韩水华,叶卫国.求解矩形Packing问题的砌墙式启发式算法 [J].计算机学报,2008,31(3):509-515.
[5] Huang Wenqi,Chen Duanbing,Xu Ruchu.A new heuristic algorithm for rectangle packing [J].Computers and Operations Research,2007,34(11):3270-3280.
[6] He Kun,Huang Wenqi,Jin Yan.An efficient deterministic heuristic for two-dimensional rectangular packing [J].Computers and Operations Research,2012,39(7):1355-1363.
[7] Gillett B E,Miller L R.A heuristic algorithm for the vehicle-dispatch problem [J].Operations Research,1974,22(2):340-349.
[8] Zachariadis E E,Tarantilis C D,Kiranoudis C T.A guided tabu search for the vehicle routing problem with two-dimensional loading constraints [J].European Journal of Operational Research,2009,195(3):729-743.
[9] Fuellerer G,Doerner K F,Hartl R F,et al.Ant colony optimization for the two-dimensional loading vehicle routing problem [J].Computers & Operations Research,2009,36(3):655-673.
[10] Kirby H R,Hutton B,Mcquaid R W,et al.Modelling the effects of transport policy levers on fuel efficiency and national fuel consumption [J].Transportation Research Part D Transport & Environment,2000,5(4):265-282.
[11] Xiao Yiyong,Zhao Qiuhong,Kaku I,et al.Development of a fuel consumption optimization model for the capacitated vehicle routing problem [J].Computers and Operations Research,2012,39(7):1419-1431.

备注/Memo

备注/Memo:
收稿日期:2017-03-27基金项目:国家自然科学青年基金(11601198),江西省教育厅科技计划(GJJ150464,GJJ160457),江西省社会科学规划(15GL12)和江西财经大学第十一届学生科研课题(XS16486、XS16470)资助项目.通信作者:万 龙(1981-),男,江西南昌人,副教授,博士,主要从事调度问题的算法研究.E-mail:cocu3328@163.com
更新日期/Last Update: 1900-01-01