论文部分内容阅读
摘 要：随着世界国际贸易自由化及全球物流的发展，全球海运已经进入蓬勃发展阶段。众所周知，集装箱运输和区域经济发展关系十分密切，而随着越来越多的集装箱运输公司开辟对应的拼箱业务，集装箱拼箱的重要性也日益彰显。引言部分从拼箱开始介绍，通过拼箱中急需解决的问题来引出全文。正文部分先把问题定位为三维约束下的车辆路径问题，然后将具体问题进行对应的描述，并建立相应的数学模型，再提出运用遗传算法对问题加以解决，最后对实验结果进行相应的分析。
关键词：集装箱拼箱 车辆路径问题 遗传算法
一、引言
拼箱通常是指由承运人域国际货运代理人分别揽货并在集装箱货运站或内陆站集中，然后将两票或两票以上的货物拼装在一个集装箱内，在目的地的集装箱货运站或内陆站拆箱，分别将货物交于不同收货人。拼箱的主目的是为了提高集装箱的利用率，从而节省运输的成本。
近来年，随着集装箱吞吐量的提高，我国各大港的集装箱拼箱业务也得迅速发展。而拼箱需求的日益增长，伴随着的问题是拼箱不合理导致海运效率的降低，如何更好的拼箱提高海运效率是目前急需解决的问题。
二、问题描述
本文研究的集装箱拼箱问题的实质是3L-CVRP问题，即三维约束下的车辆路径问题。该问题的研究目标是：在满足一定的约束条件（如货物需求量、发送量、交发货时间、船只容量限制、时间限制等）下，对一系列的需求点的路线进行适当的设计，使船只有序地通过，从而能达到一定的优化目标（如里程最短、费用最少、时间尽量少、、船只利用率高等）。
该具体问题可描述如下：
在某初始港到某目的港的航线上，初始港有t辆相同规格的船只，每艘船的长宽高分别为L，W，H，船的最大载重为Q。集装箱内尺寸分别为l，w，h。每个集装箱的重量为q。现有n个中转港港口需要拼箱服务，每个需求点的需求已知，第i个需求点需配送mi个物品，重量之和为qi，其中第i个需求点的第j个物品用Iij表示，Iij的长用lij表示，Iij的宽用wij表示，Iij的高用hij表示，如何在满足行车线路约束的条件下，使所有船只总的行船路线最短？
行车线路约束是指由于实际运营的需要及船只资源和船只属性本身的限制，规划出来的每条行船线路必须符合如下要求：
（1）船只从起始港出发到达目的港。
（2）每个港口必须且只能被抵达一次。
（3）所有物品的总重量不能超过船只的载重，且所有物品的体积不能超过船舱的容积。
（4）规划出来的线路数目不能超过总共所拥有的船只的数目。
三、数学建模
其中式1是目标函数，表示使所有船只总的行驶路程最短。式2表示规划出来的航线数目不能超过所分配的船只数目，式3 表示每艘船都不会多次经过同一个中转港，式4表示同一个中转港不会同时被不同的船只经过，式3和式4保证了每个中转港必须且只经过一次。式5表示每一个中转港点需要拼箱的数目至少有一个，式6表示需要拼箱的集装箱的数目全部都被船只服务，式7表示每艘船上所装载的物品的总的重量不能超过船只的载重限制，式8表示每艘船上所有装载的物品的体积之和不能超过船只的容积。
四、遗传算法
对于该问题，遗传算法是一种较好的解决方法，这种算法是在自然界遗传机制和生物进化论生物生物学理论基础上，再与随机统计相关理论基础相结合的一种算法。遗传算法的求解过程是在满足收敛判据或要求的迭代次数条件下，从初始变量群体开始迭代的，通过不断的迭代，以此找到相应问题的最优解。遗传算法一种迭代式算法，它是从生物学基础出发的，且用该方法求得的最优解是一个过程搜索最优解。该算法广泛应用于自动控制、计算科学、模式识别、工程设计、智能故障诊断、管理科学和社会科学等相关领域，适用于解决复杂的非线性和多维空间寻优问题。
该算法的步骤可描述为：
第一步：对问题和约束条件的确定，在本问题中是提出相应的海运拼箱的具体问题，然后对它需要满足的行车线路约束进行相应的约束。
第二步：根据提出的问题建立对应的数学模型。在本问题中是将提出的问题和约束条件转化为对应的数学公式。
第三步：确定可行解的染色体编码方法，在本问题中主要是设置初始种群和新生种群来确定。
第四步：确定相应的解码方法，在本问题中主要是对总加工时间进行设置，进而找到种群的最优个体。
第五步：确定出由目标函数值到个体适应度的转换规则，在本问题中是时间越短，适应度越高。主要是先构建轮盘，轮盘赌选下一代，小于交叉发生的概率则进行交叉运算，小于变异发生的概率则进行变异运算。最后通过新种群对老种群的替代，最终把最优解进行保留。
第六步：对遗传算子进行设置，在本问题中主要是对交叉运算、变异运算等遗传算子的具体流程进行确定，其中交叉运算主要是交叉互换运算，变异运算包含了单链切点互换运算、单链片段翻转运算、单链片段互换运算。
第七步：對遗传算法的有关参数进行设置，在本问题中主要是对仿真迭代次数、群体规模、交叉发生的概率进行设置。
五、实验
1.数据源。本文所使用的标杆问题由Gendreau等[4]提出。该文献一共提供了27个测试数据，这些数据中的道路网络、客户所需货物的重量和车辆最大载重量的数据分别来源于27个平面CVRP的测试数据，车厢尺寸、货物尺寸和最大车辆数的数据则由Gendreau等人生成。本文选取了其中的15个平面数据进行测试。车厢的尺寸全部设定为W=25，H=30，L=60，每个需求点所需的货物数在1到3之间随机产生，而每件货物的宽、高和长分别在区间[0.2W，0.6W]、[0.2H，0.6H]和[0.2L，0.6L]内随机产生。
2.实验环境。本文所提出的算法用C语言在MATLAB开发平台下实现，算法执行的平台环境如下：CPU是英特尔酷睿I7-4610M双核处理器（ 3GHz，睿频可达3.7 GHz），内存为8GB，操作系统是Windows7系统。
3.参数设置。在参数设置方面，本文主要对遗传算法里的仿真迭代次数、群体规模、交叉发生的概率仿真、变异发生的概率进行设置。其中迭代次数T_iter设置为200，群体规模N_num设置为100，交叉发生的概率Pc设置为0.8，变异发生的概率Pm设置为0.08。
4.实验结果。
通过实验结果可以看出，对于我们选用的数据，算法生成的初始解的质量也较高，而且每次运行求得的最终解的路径数都满足最大车辆数的限制。我们将最终解与初始解相比，路径总长度有了一定的优化。
六、结语
本文结合海运货物拼箱运输的特点，提出了相应的问题，建立了相应的数学模型，并提出应用遗传算法对相应的拼箱配装优化问题进行求解，然后介绍了相应的步骤，并用实例计算进行相应的求解，最后发现通过遗传算法，本问题得到了一定的优化。
参考文献：
[1]杨占林.拼箱操作三流程[J].中国海关，2009，（07）：42-44.
[2]方金城，张岐山.物流配送车辆路径问题（VRP）算法综述[J].沈阳工程学院学报（自然科学版），2006，（04）：357-360.
[3]周昕，凌兴宏.遗传算法理论及技术研究综述[J]. 计算机与信息技术，2010.
[4]Gendreau M，Iori M，Laporte G.A Tabu Search Algorithm for a Routing and Container Loading Problem[J].Transportation Science，2006，40（3）：342-350.
作者简介：王林荣（1993—）男。浙江台州人。硕士研究生。研究方向：遗传算法。
关键词：集装箱拼箱 车辆路径问题 遗传算法
一、引言
拼箱通常是指由承运人域国际货运代理人分别揽货并在集装箱货运站或内陆站集中，然后将两票或两票以上的货物拼装在一个集装箱内，在目的地的集装箱货运站或内陆站拆箱，分别将货物交于不同收货人。拼箱的主目的是为了提高集装箱的利用率，从而节省运输的成本。
近来年，随着集装箱吞吐量的提高，我国各大港的集装箱拼箱业务也得迅速发展。而拼箱需求的日益增长，伴随着的问题是拼箱不合理导致海运效率的降低，如何更好的拼箱提高海运效率是目前急需解决的问题。
二、问题描述
本文研究的集装箱拼箱问题的实质是3L-CVRP问题，即三维约束下的车辆路径问题。该问题的研究目标是：在满足一定的约束条件（如货物需求量、发送量、交发货时间、船只容量限制、时间限制等）下，对一系列的需求点的路线进行适当的设计，使船只有序地通过，从而能达到一定的优化目标（如里程最短、费用最少、时间尽量少、、船只利用率高等）。
该具体问题可描述如下：
在某初始港到某目的港的航线上，初始港有t辆相同规格的船只，每艘船的长宽高分别为L，W，H，船的最大载重为Q。集装箱内尺寸分别为l，w，h。每个集装箱的重量为q。现有n个中转港港口需要拼箱服务，每个需求点的需求已知，第i个需求点需配送mi个物品，重量之和为qi，其中第i个需求点的第j个物品用Iij表示，Iij的长用lij表示，Iij的宽用wij表示，Iij的高用hij表示，如何在满足行车线路约束的条件下，使所有船只总的行船路线最短？
行车线路约束是指由于实际运营的需要及船只资源和船只属性本身的限制，规划出来的每条行船线路必须符合如下要求：
（1）船只从起始港出发到达目的港。
（2）每个港口必须且只能被抵达一次。
（3）所有物品的总重量不能超过船只的载重，且所有物品的体积不能超过船舱的容积。
（4）规划出来的线路数目不能超过总共所拥有的船只的数目。
三、数学建模
其中式1是目标函数，表示使所有船只总的行驶路程最短。式2表示规划出来的航线数目不能超过所分配的船只数目，式3 表示每艘船都不会多次经过同一个中转港，式4表示同一个中转港不会同时被不同的船只经过，式3和式4保证了每个中转港必须且只经过一次。式5表示每一个中转港点需要拼箱的数目至少有一个，式6表示需要拼箱的集装箱的数目全部都被船只服务，式7表示每艘船上所装载的物品的总的重量不能超过船只的载重限制，式8表示每艘船上所有装载的物品的体积之和不能超过船只的容积。
四、遗传算法
对于该问题，遗传算法是一种较好的解决方法，这种算法是在自然界遗传机制和生物进化论生物生物学理论基础上，再与随机统计相关理论基础相结合的一种算法。遗传算法的求解过程是在满足收敛判据或要求的迭代次数条件下，从初始变量群体开始迭代的，通过不断的迭代，以此找到相应问题的最优解。遗传算法一种迭代式算法，它是从生物学基础出发的，且用该方法求得的最优解是一个过程搜索最优解。该算法广泛应用于自动控制、计算科学、模式识别、工程设计、智能故障诊断、管理科学和社会科学等相关领域，适用于解决复杂的非线性和多维空间寻优问题。
该算法的步骤可描述为：
第一步：对问题和约束条件的确定，在本问题中是提出相应的海运拼箱的具体问题，然后对它需要满足的行车线路约束进行相应的约束。
第二步：根据提出的问题建立对应的数学模型。在本问题中是将提出的问题和约束条件转化为对应的数学公式。
第三步：确定可行解的染色体编码方法，在本问题中主要是设置初始种群和新生种群来确定。
第四步：确定相应的解码方法，在本问题中主要是对总加工时间进行设置，进而找到种群的最优个体。
第五步：确定出由目标函数值到个体适应度的转换规则，在本问题中是时间越短，适应度越高。主要是先构建轮盘，轮盘赌选下一代，小于交叉发生的概率则进行交叉运算，小于变异发生的概率则进行变异运算。最后通过新种群对老种群的替代，最终把最优解进行保留。
第六步：对遗传算子进行设置，在本问题中主要是对交叉运算、变异运算等遗传算子的具体流程进行确定，其中交叉运算主要是交叉互换运算，变异运算包含了单链切点互换运算、单链片段翻转运算、单链片段互换运算。
第七步：對遗传算法的有关参数进行设置，在本问题中主要是对仿真迭代次数、群体规模、交叉发生的概率进行设置。
五、实验
1.数据源。本文所使用的标杆问题由Gendreau等[4]提出。该文献一共提供了27个测试数据，这些数据中的道路网络、客户所需货物的重量和车辆最大载重量的数据分别来源于27个平面CVRP的测试数据，车厢尺寸、货物尺寸和最大车辆数的数据则由Gendreau等人生成。本文选取了其中的15个平面数据进行测试。车厢的尺寸全部设定为W=25，H=30，L=60，每个需求点所需的货物数在1到3之间随机产生，而每件货物的宽、高和长分别在区间[0.2W，0.6W]、[0.2H，0.6H]和[0.2L，0.6L]内随机产生。
2.实验环境。本文所提出的算法用C语言在MATLAB开发平台下实现，算法执行的平台环境如下：CPU是英特尔酷睿I7-4610M双核处理器（ 3GHz，睿频可达3.7 GHz），内存为8GB，操作系统是Windows7系统。
3.参数设置。在参数设置方面，本文主要对遗传算法里的仿真迭代次数、群体规模、交叉发生的概率仿真、变异发生的概率进行设置。其中迭代次数T_iter设置为200，群体规模N_num设置为100，交叉发生的概率Pc设置为0.8，变异发生的概率Pm设置为0.08。
4.实验结果。
通过实验结果可以看出，对于我们选用的数据，算法生成的初始解的质量也较高，而且每次运行求得的最终解的路径数都满足最大车辆数的限制。我们将最终解与初始解相比，路径总长度有了一定的优化。
六、结语
本文结合海运货物拼箱运输的特点，提出了相应的问题，建立了相应的数学模型，并提出应用遗传算法对相应的拼箱配装优化问题进行求解，然后介绍了相应的步骤，并用实例计算进行相应的求解，最后发现通过遗传算法，本问题得到了一定的优化。
参考文献：
[1]杨占林.拼箱操作三流程[J].中国海关，2009，（07）：42-44.
[2]方金城，张岐山.物流配送车辆路径问题（VRP）算法综述[J].沈阳工程学院学报（自然科学版），2006，（04）：357-360.
[3]周昕，凌兴宏.遗传算法理论及技术研究综述[J]. 计算机与信息技术，2010.
[4]Gendreau M，Iori M，Laporte G.A Tabu Search Algorithm for a Routing and Container Loading Problem[J].Transportation Science，2006，40（3）：342-350.
作者简介：王林荣（1993—）男。浙江台州人。硕士研究生。研究方向：遗传算法。