论文部分内容阅读
摘 要：本文研究速度变化对三维装箱车辆路径问题的影响，并且考虑车辆路径中的能源消耗，建立了一个考虑变速的绿色3L-CVRP模型，提出了求解该问题的禁忌搜索和局部搜索相结合的算法。
关键词：三维装箱 变速 禁忌搜索 局部搜索
一、引言
进入新世纪以来，物流引起的环境污染问题越来越引起人们的重视。节约能耗费用、减少排污相关税费以成为企业控制物流成本的重要环节。在我国，随着工业化进程的加快，由于运输导致的温室气体问题也日趋严重。而在车辆实际行驶过程中，由于各种因素的影响，车辆的行驶速度也是时变的，从而导致了车辆的运营成本也跟着发生变化。而车辆行驶速度对于旅行时间和碳排放的影响也是非常直接的，所以研究时变的绿色3L-CVRP问题具有很强的理论和现实意义。
二、模型建立
1.问题描述。考虑时变的绿色3L-CVRP问题可描述为：配送中心派几辆车为客户服务，车辆从配送中心出发，送完货后都要回到配送中心，目标是在考虑速度变化，道路，载重，运行距离和三维装箱的情形下，找出满足全部客户需求的总油耗最小的路线安排。约束如下：
1.1车辆路径约束：车辆从配送中心出发，必须返回配送中心，每个客户都被访问到且只被一辆车访问一次，使用车辆不能超过配送中心的车辆数。
1.2三维装箱约束：物体必须正交放进车厢且只能以底面做90度旋转的摆放，必须满足后进先出原则，物体不能有重叠，易碎品上方不能放非易碎品，物体与其下面接触物体的接触面积必须满足一定的阈值，即假设接触面积设为A，设该物体的底面积为A，则必须满足A>α*A。
2.能耗计算。车辆从客户 i到客户j 的单位燃油行驶距离表达式为：
其中α0、α1为正常数；v 表示车辆的平均速度；γij为道路的坡度系数；πij为负载系数，表达式为：
其中β0、β1为正常数；为车辆从客户i到客户 j 的载重量，为车辆长期运营下的平均载重量。
本文把速度区间化，假设分M个区间，第z个速度时间区间的范围是，设车辆离开i时的速度介于第τ个速度时间区间内，跨越p个区间，则车辆离开i的速度可以记为，则车辆在路段内的速度可以按其跨越的时间区间表示为集合，则考虑时变的弧产生的总油耗计算如下：
3.模型构建。目标函数：
其中：；a为 配送中心所拥有的车辆数，xijk：表示车辆k访问弧的次数，xijk={0，1}。
约束条件：（1）使用车辆数不能超过配送中心拥有的车辆数；（2）每个客户都有被服务且只能被一辆车服务一次；（3）装载的货物必须满足车辆的体积和载重约束；（4）货物只能以底面做90度旋转；（5）非易碎品不能放易碎品上方；（6）支持面积必须满足一定的阈值；（7）货物不能有重叠；（8）必须满足后進先出原则。
三、算法求解
本文采用禁忌搜索与局部搜索相结合的方法求解3L-CVRP。整个算法分为两个层次：外层用禁忌搜索求解每辆车的客户分配和行使路径，内层调用局部搜索算法判断每辆车的装箱可行性以及求解装箱方案，并把结果返回给TS算法，TS算法对此路径进行调整，以寻找更好的路径方案。
1.局部搜索算法。为使每个物体在车厢中寻找到合适的位置，本文选择了基于最深位置填充法和最大接触面积填充算法的局部搜索算法求解三维装箱问题。其中装箱的初始解是按照物体先进后出和最大体积优先的原则生成的，然后随机选择两个位置进行交换生成新解，当算法迭代次数达到一定阈值或成功装箱，则算法结束。
2.禁忌搜索算法。本文按照文献[3]提出的改进二维扫描算法生成初始解；使用1-swap，2-opt，3-opt三种邻域结构生成领域解，使用状态本身的变化作为禁忌对象。
四、实验结果分析
本文的算法是以MATLAB语言编写的，使用的算例是基于3L-CVRP的测试算例，本文最后的结果不但给出了路径结果，同时也给出了装箱方案。为了验证算法的有效性，本文以E16-03算例为例，对比考虑能耗和不考虑能耗两种方案的差别。
1.基于3L-CVRP的仿真实验。求解基于3L-CVRP的仿真实验的最优距离是300.47。其中车辆1的路径是12-4-13。车辆2的路径是：2-3-8-1。车辆3的路径是：11-9-10-15-5。车辆4的路径是：7-6-14。
2.基于时变的绿色3L-CVRP的仿真实验。求解基于时变的绿色3L-CVRP的仿 真实验的最优能耗是55.65，行驶距离是334.6507。其中车辆1的路径是：6-8-3-1。车辆2的路径是：13-14-7。车辆3的路径是：12-5-9-11。车辆4的路径是：2-10-15-4。
经过计算显示以能耗为目标和以最优距离为目标的结果是完全不同的，企业以后不能仅仅考虑行驶距离，也要把能耗考虑进去。
参考文献：
[1]Gendreau M，Iori M ，Laporte G， et al. A tabu search algorithm for a routing and container loading problem[J].Transportation Science， 2006， 40（3）：342-350.
[2]彭碧涛.三维装载约束下车辆路径问题研究：[博士学位论文].广州：华南理工大学，2013.
[3]杨培颖.低碳型机车接送服务的改进二维码扫描算法[J].东北大学学报，2013（4）：478-481.
[4]周慧，周良.多目标动态车辆路径问题建模及优化[J].计算机科学，2015，42（6）：204-209.
关键词：三维装箱 变速 禁忌搜索 局部搜索
一、引言
进入新世纪以来，物流引起的环境污染问题越来越引起人们的重视。节约能耗费用、减少排污相关税费以成为企业控制物流成本的重要环节。在我国，随着工业化进程的加快，由于运输导致的温室气体问题也日趋严重。而在车辆实际行驶过程中，由于各种因素的影响，车辆的行驶速度也是时变的，从而导致了车辆的运营成本也跟着发生变化。而车辆行驶速度对于旅行时间和碳排放的影响也是非常直接的，所以研究时变的绿色3L-CVRP问题具有很强的理论和现实意义。
二、模型建立
1.问题描述。考虑时变的绿色3L-CVRP问题可描述为：配送中心派几辆车为客户服务，车辆从配送中心出发，送完货后都要回到配送中心，目标是在考虑速度变化，道路，载重，运行距离和三维装箱的情形下，找出满足全部客户需求的总油耗最小的路线安排。约束如下：
1.1车辆路径约束：车辆从配送中心出发，必须返回配送中心，每个客户都被访问到且只被一辆车访问一次，使用车辆不能超过配送中心的车辆数。
1.2三维装箱约束：物体必须正交放进车厢且只能以底面做90度旋转的摆放，必须满足后进先出原则，物体不能有重叠，易碎品上方不能放非易碎品，物体与其下面接触物体的接触面积必须满足一定的阈值，即假设接触面积设为A，设该物体的底面积为A，则必须满足A>α*A。
2.能耗计算。车辆从客户 i到客户j 的单位燃油行驶距离表达式为：
其中α0、α1为正常数；v 表示车辆的平均速度；γij为道路的坡度系数；πij为负载系数，表达式为：
其中β0、β1为正常数；为车辆从客户i到客户 j 的载重量，为车辆长期运营下的平均载重量。
本文把速度区间化，假设分M个区间，第z个速度时间区间的范围是，设车辆离开i时的速度介于第τ个速度时间区间内，跨越p个区间，则车辆离开i的速度可以记为，则车辆在路段内的速度可以按其跨越的时间区间表示为集合，则考虑时变的弧产生的总油耗计算如下：
3.模型构建。目标函数：
其中：；a为 配送中心所拥有的车辆数，xijk：表示车辆k访问弧的次数，xijk={0，1}。
约束条件：（1）使用车辆数不能超过配送中心拥有的车辆数；（2）每个客户都有被服务且只能被一辆车服务一次；（3）装载的货物必须满足车辆的体积和载重约束；（4）货物只能以底面做90度旋转；（5）非易碎品不能放易碎品上方；（6）支持面积必须满足一定的阈值；（7）货物不能有重叠；（8）必须满足后進先出原则。
三、算法求解
本文采用禁忌搜索与局部搜索相结合的方法求解3L-CVRP。整个算法分为两个层次：外层用禁忌搜索求解每辆车的客户分配和行使路径，内层调用局部搜索算法判断每辆车的装箱可行性以及求解装箱方案，并把结果返回给TS算法，TS算法对此路径进行调整，以寻找更好的路径方案。
1.局部搜索算法。为使每个物体在车厢中寻找到合适的位置，本文选择了基于最深位置填充法和最大接触面积填充算法的局部搜索算法求解三维装箱问题。其中装箱的初始解是按照物体先进后出和最大体积优先的原则生成的，然后随机选择两个位置进行交换生成新解，当算法迭代次数达到一定阈值或成功装箱，则算法结束。
2.禁忌搜索算法。本文按照文献[3]提出的改进二维扫描算法生成初始解；使用1-swap，2-opt，3-opt三种邻域结构生成领域解，使用状态本身的变化作为禁忌对象。
四、实验结果分析
本文的算法是以MATLAB语言编写的，使用的算例是基于3L-CVRP的测试算例，本文最后的结果不但给出了路径结果，同时也给出了装箱方案。为了验证算法的有效性，本文以E16-03算例为例，对比考虑能耗和不考虑能耗两种方案的差别。
1.基于3L-CVRP的仿真实验。求解基于3L-CVRP的仿真实验的最优距离是300.47。其中车辆1的路径是12-4-13。车辆2的路径是：2-3-8-1。车辆3的路径是：11-9-10-15-5。车辆4的路径是：7-6-14。
2.基于时变的绿色3L-CVRP的仿真实验。求解基于时变的绿色3L-CVRP的仿 真实验的最优能耗是55.65，行驶距离是334.6507。其中车辆1的路径是：6-8-3-1。车辆2的路径是：13-14-7。车辆3的路径是：12-5-9-11。车辆4的路径是：2-10-15-4。
经过计算显示以能耗为目标和以最优距离为目标的结果是完全不同的，企业以后不能仅仅考虑行驶距离，也要把能耗考虑进去。
参考文献：
[1]Gendreau M，Iori M ，Laporte G， et al. A tabu search algorithm for a routing and container loading problem[J].Transportation Science， 2006， 40（3）：342-350.
[2]彭碧涛.三维装载约束下车辆路径问题研究：[博士学位论文].广州：华南理工大学，2013.
[3]杨培颖.低碳型机车接送服务的改进二维码扫描算法[J].东北大学学报，2013（4）：478-481.
[4]周慧，周良.多目标动态车辆路径问题建模及优化[J].计算机科学，2015，42（6）：204-209.