新一代信息技术背景下循环取货路径规划问题

张慧，宋少忠，安毅，辛刚，钟天择

（1.长春汽车工业高等专科学校 信息技术学院，长春 130013；2.吉林工程技术师范学院 数据科学与人工智能学院，长春 130052；3.吉林工程技术师范学院 电气与信息工程学院，长春 130052；4.吉林工商学院 工学院，长春 130062；5.吉林大学 管理学院，长春 130012）

0 引言

新一代信息技术在传统产业转型升级过程中起到非常重要的作用，尤其是有一定生产需求的汽车制造业，在国务院发布的《关于深化制造业与互联网融合发展的指导意见》［1］政策推动下，以人工智能为代表的新一代信息技术在生产物流方面拥有了广阔的市场空间，占据了指引城市物流发展的主导地位.其中，生产物流的体系结构是否具有科学且正确的指导性是与企业的生产效率和经济效益密不可分.为了提高汽车制造厂、物流管理人员和各个供应商对物流管理方法的认可度，既要有合理的路线要求、规范的运行时刻，还应当考虑高集载率来保证车辆取送货的各方成本降低，但其方案的设计与实现过程是非常复杂的.循环取货物流模式高集载率的特性可以在降低汽车厂A库存量的同时，减少汽车零部件供应商本身的物流风险以及缺货甚至停线的风险.

国内外研究者们尝试使用基本的人工智能算法解决路径规划问题，包括禁忌搜索算法［2］、智能水滴算法［3］、遗传算法［4］、蚁群算法［5］等.实际物流配送过程中，在满足时间窗约束条件下，需要对生产需求量拆分和物流车辆容载量拆分，这使得如何解决城市物流的车辆路径规划问题也显得越来越紧迫［6］.因而，越来越多的改进智能算法涌现出来，例如运用改进的蚁群算法与遗传算法基于时间窗和送货需求可拆分车辆路径问题［7-8］、利用改进搜索方法通过拆分解决车辆路径问题［9］等等.

在实现基础经济效益的前提下，按时取货送货、合理分配空间也是汽车制造厂、物流管理人员和各个供应商对运输服务的目标需求.传统汽车零部件运输过程设计要求的单一性会造成车辆集载率过度和容量浪费等问题，导致物流运输成本没有达到最小化.新一代信息技术的赋能使城市物流行业的此类资源浪费问题得以解决.本文以汽车厂A为例，在同城面对多目标、多车程的汽车零部件循环取货的实际问题入手，以该厂运营需求和实际动态反馈作为依据，旨在基于人工智能和经济发展方面解决物流车辆路径规划问题，充分考虑汽车厂A的实际生产需求、其他供应商的实际生产供应量、依据汽车零部件的体积占比与物流车辆容载率之间的关系，以及参与其中的各方时间窗需求等因素，进而改进粒子群算法.

1 问题描述

在企业生产与物流管理过程中，多目标、多车程、多时间窗、多容载量的汽车零部件循环取货路径规划问题是通过一个总体的物流管理中心分配若干辆不同车型的运输车，为一个总体装配中心和多个服务供应商提供取送货服务，根据总体装配中心生产所需要汽车零部件的数量、不同服务供应商提供零部件的种类和数量、不同车型运输车的最大载重量、基于Q市智能地图的总体装配中心（汽车厂A）与各个供应商之间形成的拓扑结构，以及各个供应商的服务时间窗等约束条件，高集载率的循环取送货物流模式如下：选配车辆可以为多个供应商提供运输服务，从汽车厂A的总体装配中心出发再回到汽车厂A的总体装配中心是一次完整的循环取送货过程.假设某个供应商由一辆选配运输车辆在规定的时间窗约束条件下完成了取货服务，当前供应商提供装货的时间窗固定、用每一辆配送车辆的成本和单位行驶距离成本均固定的前提下，运输车辆仍有空间供其他供应商的汽车零部件使用时，在考虑以上约束情形下，要充分合理地规划物流车辆的路径，确保运输车辆行驶的总距离和时间相对最少.

文章以Q市的45个汽车零部件供应商为例，按照计划对不同数量的汽车零部件提出需求，即总体装配中心向供应商客户取回货物，由一个车队（包含不同车型）负责分取汽车零部件，组织适当的行车路线，目标是使得汽车厂A的需求得到满足，并能在一定约束下，如A厂与供应商双方的时间窗、选配车辆的容载率及利用率等条件，达到以路程最优、成本最小等目的.基于A厂产业需求和物流管理实际情况需要不断更新最优运输方案，更新过程如图1所示，汽车厂A高集载率的循环取送货物流模式的流程如图2所示.

图1 循环取货动态制定最优方案示意图

图2 汽车厂A循环取送货流程图

2 改进的算法设计

在传统的智能优化算法中，将每一个粒子看作问题的一个解的形式就是粒子群算法.目前该算法已经成功应用于多个领域，如云工作流调度、文档聚类、经济负荷分配、水库系统运行优化问题、移动机器人的定位以及车辆路径规划问题等.相比较而言，粒子群算法的理论概念易理解、参数设计和改进策略结构鲜明，尤其在解决多维度目标的路径规划问题具有绝对的优势.其内在特点在于可以通过全局更新与个体更新相结合的方式更新粒子的位置.在随机搜索过程中最核心的环节就是如何定义全局和个体，选择一个到当前迭代完成时的最好粒子个体作为整个粒子群的示例，这个示例就是全局最优粒子，它随着迭代次数的增加，可能会不断发生变化以完成更高质量的搜索.个体最优粒子就是当前粒子到当前迭代完成时的最好粒子.随着粒子群位置的更新，搜索到的解的质量也随之提高.但粒子的速度和位置都是有范围限制的，在这里，该范围是基于Q市智能地图的汽车厂A与各个供应商之间的位置信息，并将想要超越范围的路线加以惩罚的方式融入设计当中，避免出现路线超出市区范围的问题.

无论是全局更新还是个体更新，粒子的位置必然离不开速度的影响，粒子位置更新公式为

其中：Xk、Xk+1分别表示第k代和第k+1代时粒子i的位置；Vk、Vk+1分别表示第k代和第k+1代时粒子i的速度分别表示第k代个体与全局最优粒子的位置；r1和r2设置为0至1之间的随机数；c1和c2为常数.

本文提出的新算法在利用粒子群算法求解路径优化问题时，不仅传承了基本框架、编码方式简洁及参数少的特点，又将多种搜索算法融合在由粒子构成的异质网络中，并将汽车厂A循环取货过程中的反馈加入到动态调整物流方案当中.进一步在每个粒子更新位置过程中嵌入重新定位操作，在主循环结束后对全局最优粒子再进行大邻域上和自适应搜索（ALNS）［10］操作.通过带有随机性的destroy、repair方法构造新解，基于物流实际反馈动态评估每种方法，从而对解空间进行启发式搜索，直至找到高质量的解.

3 基于粒子群和大规模自适应邻域搜索算法的设计

为了验证本文提出的基于粒子群和大规模自适应邻域搜索算法的正确性、适用性与优越性，将Solomon数据集［11］中包含的rc205算例的随机23个点（包含一个总体装配中心）作为测试集算例，分别应用于遗传算法、应急运输路径问题中提出的改进遗传算法［12］和本文提出的新算法.其中，测试集算例中包含供应商的坐标、总体装配中心的货物需求量、供应商的服务时间、每个供应商的时间窗要求、可选配车辆总数、运输车辆的最大容载率等多种信息.接下来，将三种算法求解目标函数的性能作为目标，对三种算法求解目标函数进行对比分析，分别对三个算法的程序运行10次，将车辆数、最小成本、最小里程求平均值，结果得出，在使用车辆数量相同时，新算法的平均最小成本和最小里程均是三者最低.整个试验过程中，遗传算法收敛速度较慢，而且基于成本的收敛值也不大理想，大概在360代时收敛到最小值613.551 8元.而应急运输路径问题中提出的改进遗传算法的全局收敛性比前者强，大概在260代时候收敛到最小值419.994 4元.而新提出的算法全局收敛性更强，前期就能迅速收敛至最小值附近，而且相比较而言，收敛值更好，大概120代时收敛到最小值331.802元，其最优配送方案路线如表1所示.

表1 最优配送方案路线表

4 数值仿真结果

针对带有左右时间窗容量受限的循环取货车辆路径优化问题，为验证新提出算法的有效性及优化过程中的收敛情况，以Q市地图为例，选取45个汽车零配件供应商和汽车厂A总体装配中心实际地址建立坐标系并进行算法仿真，坐标系建立及具体的最优配送方案路线如图3所示.基于Q市实际路况选取坐标原点，将各个配送方案的起始点设为汽车厂A，即配送中心坐标为（100，100），汽车厂A选配车辆分别向各个汽车零部件供应商按需循环取货，45个汽车零配件供应商与汽车厂A的相对位置换算成坐标距离，东西方向为横向距离，即x轴，南北方向为纵向距离，即y轴，单位为百米.例如2号零部件供应商在A厂的西南方向，西向2.1 km，南向3.4 km处；车辆对零部件供应商服务时间包括其进出供应商公司的时间和装载汽车零部件的时间，设为30 min；假设各个供应商公司汽车零配件包装箱大小相同，根据选配车辆的大小不同，普通车辆容载率设为100箱，加长车辆容载率设为150箱；选取A厂总装中心和所有供应商的左时间窗的最小值，将其设为0，其他时间窗以0为界，以分钟为单位换算成每个供应商的左右时间窗，例如已选取左时间窗2：30为最小值，3号供应商的服务时间是3：35~4：56，则3号供应商的左时间窗为3：35~2：30=65 min，右时间窗4：56~2：30=146 min.最优配送方案路线如表2所示.仿真参数设置种群初始值随机，优化收敛过程如图4所示，仿真结果显示当迭代次数为第14代左右时，最优值开始呈现收敛状态.当迭代次数为第100代时，全局最优解总成本为9 916.651 1元，其车辆使用数目为18辆，车辆行驶总距离为2 910.718 km，违反受限容量车辆数目为1辆，违反约束左右时间窗车辆为1辆，算法寻优时间为110.678 171 s.

图3 最优配送方案路线图

图4 优化收敛图

表2 最优配送方案路线

5 结语

本文提出了一种基于新一代信息技术下的粒子群和大规模自适应邻域搜索算法，解决了以汽车厂A为实例的汽车零部件运输最优路径规划问题.首先，以实际限制将范围设定为Q市内，将A厂与各个供应商之间的配送任务关系进行初始化；其次，建立满足容载率约束和时间窗约束惩罚值的适应度函数；第三，在粒子群更新过程中，选择利用大规模自适应邻域搜索算法移除和插入供应商，使总运输距离尽量小.基于相同测试集对三种不同的算法运行结果进行了对比分析，对比结果显示新提出的算法在性能上具有显著的优越性；最后，以实际运营数据为例进行了数值仿真，求解出汽车零部件的最优配送方案和线路图.数值仿真结果阐明了新算法的有效性和优化过程中的收敛情况.以汽车厂A实际运营需求和动态反馈作为依据，新提出算法面对多目标、多车程的汽车零部件循环取货的实际问题是一种有效的智能路径规划方法，既能使循环取货速度提升、成本费用降低，还可以有效缓解物流车辆造成城市内部的交通压力.