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

摘要

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.%同时考虑2维装箱和车辆路径2个NP难问题,以碳排放量为目标函数,对低碳环境下带2维装箱约束的车辆路径问题进行研究.求解思路是以禁忌搜索算法(Tabu Search,TS)为主要框架,然后基于贪心的思想采用4种启发式装箱策略生成初始解,并通过改进编码解码方式以及使用动态增长的禁忌长度对TS算法进行改进;由给出算例的计算结果可知,改进的禁忌搜索算法对于求解该类问题具有一定的优越性.