CN117592898A - 一种汽车零部件入厂物流同步循环取货方法及系统 - Google Patents

Abstract

本发明公开了一种汽车零部件入厂物流同步循环取货方法及系统，方法包括：考虑需求按零件拆分、多行程、零件同步交付等特征，构建多行程路径规划模型；基于多行程路径规划模型，设计了改进的自适应大规模邻域搜索算法；以运输费用最小为准则，利用前向插入启发式方法构造初始解；利用毁坏算子破坏初始解，后利用修复算子进行修复，生成新解；基于模拟退火机制处理新解，得到输出解；利用后局部搜索法对输出解进行优化，得到最优取货解。本发明将循环取货与同步取货相结合，以最小化运输成本为目标，通过构建多行程路径规划模型和设计改进算法有效降低零部件入厂物流成本，为汽车主机厂零部件入厂物流提供管理对策和建议。

Description

一种汽车零部件入厂物流同步循环取货方法及系统

技术领域

本发明属于汽车零部件物流规划技术领域，具体涉及一种汽车零部件入厂物流同步循环取货方法及系统。

背景技术

零部件入厂物流涉及从供应商到制造企业的运输、仓储和管理的过程，对于汽车制造业企业的生产连续性、库存成本控制和物流成本降低至关重要。合理的零部件入厂物流可以使零部件按时到达生产线，避免因缺少零部件而导致的停产或生产延误；零部件的准时到货可以降低库存持有成本，减少仓储空间需求；物流路线的优化能帮助企业降低运输成本。尤其在新能源汽车行业，车型配置繁多，个性化零部件众多，如何优化零部件入厂物流已经成为新能源汽车制造企业提高竞争优势的关键。

目前对循环取货和同步取货的研究已经有较多成果，但二者结合的成果较少。随着新能源汽车个性化需求的日益普及，汽车同步零部件种类成增长趋势，传统的专车直送的同步取货难以兼顾物流效率和物流成本的双重需求。

发明内容

本发明旨在解决现有技术的不足，提出一种汽车零部件入厂物流同步循环取货方法及系统，针对新能源汽车制造企业多品种小批量零部件同步取货问题，将循环取货与同步取货相结合。

为实现上述目的，本发明提供了如下方案：

一种汽车零部件入厂物流同步循环取货方法，包括以下步骤：

构建多行程路径规划模型；

基于所述多行程路径规划模型，以运输费用最小为准则，利用前向插入启发式方法构造初始解；

利用毁坏算子将所述初始解进行破坏，并使用修复算子对破坏后的解进行修复，生成新解；

基于模拟退火机制处理所述新解，得到输出解；

利用后局部搜索法对所述输出解进行优化，得到最优取货解。

优选的，运输费最小准则包括：

其中，α为单位时间运输成本，i、j分别为节点i和节点j，V为所有节点集合，k为车辆k，K为车辆集合，g为第g次行程，G为车辆行程集合。

优选的，所述初始解的构建方法包括：

构建车辆k的空路径集W₁和空路径集W₂，构建集合U₁和集合U₂，所述集合U₁为为按主机厂与供应商距离升序排序的零件集合，所述集合U₂为最晚允许出发时间的升序的零件集合；

从所述集合U₁和所述集合U₂中分别取出距离最远的零件和最晚允许出发时间中最早的零件/>并构造路径集W₁和路径集W₂；

遍历所述所述集合U₁和所述集合U₂，计算后续零件插入费用，在所述路径集W₁和所述路径集W₂中插入所述零件和所述零件/>

从所述路径集W₁和所述路径集W₂中选择运输费用最低的作为所述初始解。

优选的，所述毁坏算子包括：随机破坏算子、最差破坏算子、交货期相关破坏算子和位置相关破坏算子；

所述随机破坏算子用于随机选择一辆车的一个行程，随机选择一定数量的零件从当前路径序列中移除；

所述最差破坏算子用于将所有零件按照距离排序，移除距离最远的零件；

所述交货期相关破坏算子用于对任意两个相异的供应商的零件计算零件相关度，移除交货期相关度较高的零件；

所述位置相关破坏算子用于对任意零件计算位置相关度，移除位置相关度较高的零件。

优选的，所述修复算子包括：贪婪修复算子和后悔修复算子；

所述贪婪修复算子用于将由所述毁坏算子移除的零件按修复后目标函数值增量ΔF_m进行升序排列，将零件逐一插入到修复后目标函数值增量ΔF_m最小的位置；

所述后悔修复算子用于计算零件的最优插入位置的目标函数值增量和次优插入位置的目标函数值增量/>基于所述目标函数值增量/>和所述目标函数值增量之差的绝对值计算零件的后悔值，并选择所述后悔值大的位置进行修复。

优选的，所述模拟退火机制包括：

设置当前迭代代数为ε，总迭代次数为τ，则接受新解的概率为：

其中ΔF是目标函数值增量，T_ε为当前迭代的温度；

在下一次迭代中，T_ε+1的降温概率为：

其中，和/>分别为第ε代开始和结束时的目标值，τ-ε为剩余迭代代数。

优选的，所述优化的方法包括：

当未满足弱扰动迭代次数时，对所述输出解进行弱扰动操作，并判断扰动后是否满足强扰动条件；

当满足所述强扰动条件时，对所述输出解进行强扰动操作，完成优化，得到所述最优取货解。

优选的，所述弱扰动操作包括：

利用Or-opt算子任选一个行程中两个供应商，在保证原有供应商先后顺序下，将供应商插入到行程内任意节点；

利用Exchange算子任意交换两个行程中的两个供应商的位置；

利用2-opt算子任意交换一个行程中的两个供应商所有零件的位置。

优选的，所述强扰动操作包括：利用强2-opt算子选择行程中一个供应商，遍历该行程中其他供应商，取所述最优取货解。

本发明还提供了一种汽车零部件入厂物流同步循环取货系统，所述取货系统应用上述任一项所述的取货方法，包括：模型构建模块、初始解构建模块、新解生成模块、退火迭代模块和结果优化模块；

所述模型构建模块用于构建多行程路径规划模型；

所述初始解构建模块用于基于所述多行程路径规划模型，以运输费用最小为准则，利用前向插入启发式方法构造初始解；

所述新解生成模块用于利用毁坏算子将所述初始解进行破坏，并使用修复算子对破坏后的解进行修复，生成新解；

所述退火迭代模块用于基于模拟退火机制处理所述新解，得到输出解；

所述结果优化模块用于利用后局部搜索法对所述输出解进行优化，得到最优取货解。

与现有技术相比，本发明的有益效果为：

本发明将循环取货与同步取货相结合，以最小化运输成本为目标，通过构建多行程路径规划模型和改进的自适应大规模邻域搜索算法，有效提升了车辆利用效率，降低了零部件入厂物流成本，为汽车主机厂入厂物流提供了管理对策和管理建议。

附图说明

为了更清楚地说明本发明的技术方案，下面对实施例中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动性的前提下，还可以根据这些附图获得其他的附图。

图1为本发明实施例的方法流程示意图；

图2为本发明实施例的方法流程框图；

图3为本发明实施例的编码示意图；

图4为本发明实施例的中大规模算例算法效果对比，其中，(a)表示不同零件规模的平均费用，(b)表示三种算法的效果箱型图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

为使本发明的上述目的、特征和优点能够更加明显易懂，下面结合附图和具体实施方式对本发明作进一步详细的说明。

实施例一

在本实施例中，如图1、图2所示，一种汽车零部件入厂物流同步循环取货方法，包括以下步骤：

S1.构建多行程路径规划模型。

首先，设置假设条件：(1)车辆均从汽车主机厂出发和返回；(2)每个供应商的访问次数不大于其订单的个数；(3)车辆在一次行程之中装载量之和不超过车辆容量；(4)每辆车不能同时执行多个行程的任务。

定义符号：

V＝{i|i＝0，1，2，...，n，n+1}：V为所有节点集合，节点0和n+1表示汽车主机厂，V_e＝{i|i＝1，2，...，n}表示供应商集合；

K＝{k|k＝1，2，...，k_max}：车辆集合；

P＝{m|m＝1，2，...，p_max}：零件集合，包含同步供应商提供的零件；

G＝{g|g＝1，2，...，g_max}：车辆行程集合，其中g_max＝p_max；

α：单位时间运输成本(元/千米)；

t_ij：从节点i到节点j的运输时间(分钟)；

set_mj＝1，如果订单m由供应商j供应为1；

q_m：零件m的容量大小；

d_m：订单m的交货期；

Q：车辆容量限制；

M：一个极大的正数。

定义决策变量：

车辆k在第g次行程中访问节点i的时间。

构建多行程路径规划模型：

其中，约束条件为：

目标(1)是最小化车辆运输费用，为车辆行驶时间乘以单位时间行驶费用。约束(2)表示车辆单次行程中进入节点j的次数小于等于1。约束(3)确保车辆单次行程中从节点j出来的次数小于等于1。约束(4)为网络流守恒约束，单次行程中车辆进入供应商节点的次数和离开的次数相等。约束(5)确保车辆进出主机厂的次数相等。约束(6)表示车辆在单次行程中，装载零件的总容量不超过车辆容量限制。约束(7)确保单次行程中车辆访问节点满足先后顺序。约束(8)确保车辆的下一次行程的从主机厂出发时间大于本次行程中到达任意节点j的时间。其中，表示车辆k在第g次行程中从主机厂出发的时间。约束(9)-(11)决定了车辆在每次行程中是否到达供应商j。约束(12)限制了每个行程中每个零件的送达时间均小于指定的交货期，该约束保证了总装线的同步供货需求。约束(13)确保每个零件均被送到，且只被送一次。约束(14)-(15)定义了决策变量。

约束(12)为非线性约束，通过引入辅助变量进行线性化转换。

设辅助变量则有：

其次，引入辅助变量则约束(12)可被线性化为：

实施例中研究问题的决策包括四个方面：车辆访问供应商的次序、车辆运输过程中装载的零件、访问供应商的时间点以及车辆的多行程安排。

为使染色体序列能够完整表达全部解空间，每个车辆的编码包含行程层、路径层以及零件层。其中，行程层表示该车辆的行程安排，路径层表示该车辆访问供应商节点的顺序，零件层表示该车辆在对应行程和供应商装载的零件。以10个零件4个供应商1辆车的问题为例，如图3所示，该编码表示车辆1的初始解，即车辆1包含两个行程，其中行程1先后访问供应商1和供应商2，从供应商1取零件1、6、5，从供应商2取零件2、4、8；行程2同行程1。

S2.基于多行程路径规划模型，以运输费用最小为准则，利用前向插入启发式方法构造初始解。

初始解的构建方法包括：构建车辆k的空路径集W₁和空路径集W₂，构建集合U₁和集合U₂，集合U₁为按主机厂与供应商距离升序排序的零件集合，集合U₂为最晚允许出发时间的升序的零件集合；从集合U₁和集合U₂中分别取出距离最远的零件和最晚允许出发时间中最早的零件/>并构造路径集W₁和路径集W₂；遍历集合U₁和集合U₂，计算后续零件插入费用，在路径集W₁和路径集W₂中插入零件/>和零件/>从路径集W₁和路径集W₂中选择运输费用最低的作为初始解。

在本实施例中，初始解对求解速度和求解质量有着重要影响，构建方法主要有C-W节约法，最近邻域法，插入法等。其中插入法中的前向插入启发式算法是一种贪婪启发式构造方法，针对带有时间约束的问题，具有较好的性能。本实施例采用前向插入启发式方法构造初始解，具体流程如下：

S2.1将车辆k的路径集W₁和路径集W₂设为空集。构建两个集合U₁和U₂，U₁为按主机厂与供应商距离升序排序的零件集合和U₂为最晚允许出发时间的升序的零件集合。最晚允许出发时间定义为：

t_l＝d_m-2×t_0j (25)

零件m的最晚允许出发时间为零件交货期d_m减去两倍的从主机厂到零件m对应供应商j的运输时间。

S2.2针对集合U₁和U₂分别取出距离最远和最晚允许出发时间最早的零件和零件/>插入路径集W₁和W₂，并从U₁和U₂中删除/>和/>构造两个路径集。

S2.3遍历集合U₁和U₂，计算后续零件插入费用，在路径集W₁和W₂中加入该零件和/>依次插入费用最低零件。并且进行可行性检查，如果不能满足约束，则创建新的行程，执行S1.2和S1.3。

S2.4如果该车辆某行程的容量已满，则创建新的行程，执行S1.2和S1.3。至无零件可以插入该车辆。

S2.5如果无零件可以插入，则使用新车辆创建行程，直至所有零件插入完成。

S2.6从路径集W₁和路径集W₂中选择运输费用最低的一个路径集作为初始解。

S3.利用毁坏算子将初始解进行破坏，并使用修复算子对破坏后的解进行修复，生成新解。

毁坏算子包括：随机破坏算子、最差破坏算子、交货期相关破坏算子和位置相关破坏算子；随机破坏算子用于随机选择一辆车的一个行程，随机选择一定数量的零件从当前路径序列中移除；最差破坏算子用于将所有零件按照距离排序，移除距离最远的零件；交货期相关破坏算子用于对任意两个相异的供应商的零件计算零件相关度，移除交货期相关度较高的零件；位置相关破坏算子用于对任意零件计算位置相关度，移除位置相关度较高的零件。

修复算子包括：贪婪修复算子和后悔修复算子；贪婪修复算子用于将由毁坏算子移除的零件按修复后目标函数值增量ΔF_m进行升序排列，将零件逐一插入到修复后目标函数值增量ΔF_m最小的位置；后悔修复算子用于计算零件的最优插入位置的目标函数值增量和次优插入位置的目标函数值增量/>基于目标函数值增量/>和目标函数值增量之差的绝对值计算零件的后悔值，并选择后悔值大的位置进行修复。

在本实施例中，为严格满足零件交付要求，针对每个路径进行破坏操作时需要对行程中同一供应商关联零件进行破坏，设计以下4个毁坏算子：

(1)随机破坏算子rdr

随机选择一辆车的一个行程，随机选择一定数量的零件(该数量依据算例规模改变，与总零件数成一定比例)，将其从当前路径序列中移除。

(2)最差破坏算子wdr

在当前局部最优解中，将所有零件按照距离排序，优先移除距离最远的零件点，该算子能尽量保留之前迭代过程的成果，若序列中零件的距离越近，则零件被破坏的可能性越低。例如，运输距离最远的零件为零件4，则以最大概率移除零件4。

(3)交货期相关破坏算子drdr

对任意两个相异的供应商的零件计算其零件相关度，优先移除交货期相关度较高的零件。任意两个零件的交货期相关度定义为：

l_mn＝1/|d_m-d_n| (26)

当两个零件的交货期相关度较高时，同时将他们从不同供应商移除后进行修复时，较大可能分配到同一个行程，较高概率得到较优解。而两个零件的交货期相关度较低时，如果修复过程中无法交货期约束，则将被移除的零件放回原有位置，避免无效破坏。

(4)位置相关破坏算子lrdr

位置相关破坏算子lrdr与交货期相关破坏算子drdr的思想类似，移除位置相关度较高的零件，然后在修复时以较大的概率将他们分配到同一辆车的同一个行程，以达到行程聚集的效果，从而减少运输距离。

还设计了以下2个修复算子：

(1)贪婪修复算子gfr

将毁坏算子移除的零件m按修复后的目标函数值增量ΔF_m进行升序排列。将零件逐一插入到修复后目标函数值增加值最小的位置。

(2)后悔修复算子rfr

首先计算最优插入位置的目标函数值增量之后计算次优插入位置的目标函数值增量/>并根据两者之差的绝对值计算零件m的后悔值，优先选择后悔值较大的位置进行修复。

S4.基于模拟退火机制处理初始解和新解，得到输出解。

基于模拟退火机制接受解。比较新解和初始解，若新解比初始解好，则将初始解更新为新解，否则按模拟退火接收机制采取一定概率接受新解。

在本实施例中，模拟退火接受机制按概率接受劣解，有助于跳出局部最优，避免局部收敛。模拟退火机制包括：设置当前迭代代数为ε，总迭代次数为τ，则接受新解的概率为：

其中ΔF是目标函数值增量，T_ε为当前迭代的温度；在下一次迭代中，T_ε+1的降温概率为：

其中，和/>分别为第ε代开始和结束时的目标值，τ-ε为剩余迭代代数。

在迭代初期，T_ε较低，目标函数值下降较快，因此前期迭代解可以快速收敛；在迭代中期，目标函数值变化量减小，此时T_ε增加的概率变大，从而以较大的概率接受劣解，有利于逃离局部最优；在迭代后期，T_ε上升概率减小，仅接受趋于收敛的解，避免迭代后期效果变差。

S5.利用后局部搜索法对输出解进行优化，得到最优取货解。

优化的方法包括：当未满足弱扰动迭代次数时，对输出解进行弱扰动操作，并判断扰动后是否满足强扰动条件；当满足强扰动条件时，对输出解进行强扰动操作，完成优化，得到最优取货解。

在本实施例中，根据问题特征，设计2种局部优化算子：Or-opt算子和Exchange算子，以及2种扰动算子：2-opt算子和强2-opt算子。Or-opt算子能继承比较好的路径，保留原有的行程路线，以保证交付时间需求。交换算子不会破坏原有的行程结构，并且可以对行程进行进一步优化。2-opt算子不会被Or-opt算子和交换算子的操作抵消，并且针对交货期有较好的搜索效果。强2-opt算子通过遍历一个行程中所有供应商，实现不同行程的邻域搜索，相比2-opt算子可以搜索更多路径组合。

弱扰动操作包括：利用Or-opt算子任选一个行程中两个供应商，在保证原有供应商先后顺序下，将供应商插入到行程内任意节点；利用Exchange算子任意交换两个行程中的两个供应商的位置；利用2-opt算子任意交换一个行程中的两个供应商所有零件的位置。

强扰动操作包括：利用强2-opt算子选择行程中一个供应商，遍历该行程中其他供应商，取最优取货解。

实施例二

在本实施例中，一种汽车零部件入厂物流同步循环取货系统，包括：模型构建模块、初始解构建模块、新解生成模块、退火迭代模块和结果优化模块。

模型构建模块用于构建多行程路径规划模型。其中，运输费最小准则包括：

其中，α为单位时间运输成本，i、j分别为节点i和节点j，V为所有节点集合，k为车辆k，K为车辆集合，g为第g次行程，G为车辆行程集合。

初始解构建模块用于基于多行程路径规划模型，以运输费用最小为准则，利用前向插入启发式方法构造初始解。

初始解构建模块的工作流程包括：构建车辆k的空路径集W₁和空路径集W₂，构建集合U₁和集合U₂，集合U₁为按主机厂与供应商距离升序排序的零件集合，集合U₂为最晚允许出发时间的升序的零件集合；从集合U₁和集合U₂中分别取出距离最远的零件和最晚允许出发时间中最早的零件/>并构造路径集W₁和路径集W₂；遍历集合U₁和集合U₂，计算后续零件插入费用，在路径集W₁和路径集W₂中插入零件/>和零件/>从路径集W₁和路径集W₂中选择运输费用最低的作为初始解。

所述新解生成模块用于利用毁坏算子将所述初始解进行破坏，并使用修复算子对破坏后的解进行修复，生成新解。

毁坏算子包括：随机破坏算子、最差破坏算子、交货期相关破坏算子和位置相关破坏算子；随机破坏算子用于随机选择一辆车的一个行程，随机选择一定数量的零件从当前路径序列中移除；最差破坏算子用于将所有零件按照距离排序，移除距离最远的零件；交货期相关破坏算子用于对任意两个相异的供应商的零件计算零件相关度，移除交货期相关度较高的零件；位置相关破坏算子用于对任意零件计算位置相关度，移除位置相关度较高的零件。

修复算子包括：贪婪修复算子和后悔修复算子；贪婪修复算子用于将由毁坏算子移除的零件按修复后目标函数值增量ΔF_m进行升序排列，将零件逐一插入到修复后目标函数值增量ΔF_m最小的位置；后悔修复算子用于计算零件的最优插入位置的目标函数值增量和次优插入位置的目标函数值增量/>基于目标函数值增量/>和目标函数值增量之差的绝对值计算零件的后悔值，并选择后悔值大的位置进行修复。

所述退火迭代模块用于基于模拟退火机制处理所述新解，得到输出解。

退火迭代模块基于模拟退火机制接受解。比较新解和初始解，若新解比初始解好，则将初始解更新为新解，否则按模拟退火接收机制采取一定概率接受新解。

在本实施例中，模拟退火接受机制按概率接受劣解，有助于跳出局部最优，避免局部收敛。模拟退火机制包括：设置当前迭代代数为ε，总迭代次数为τ，则接受新解的概率为：

其中ΔF是目标函数值增量，T_ε为当前迭代的温度；在下一次迭代中，T_ε+1的降温概率为：

其中，和/>分别为第ε代开始和结束时的目标值，τ-ε为剩余迭代代数。

在迭代初期，T_ε较低，目标函数值下降较快，因此前期迭代解可以快速收敛；在迭代中期，目标函数值变化量减小，此时T_ε增加的概率变大，从而以较大的概率接受劣解，有利于逃离局部最优；在迭代后期，T_ε上升概率减小，仅接受趋于收敛的解，避免迭代后期效果变差。

所述结果优化模块用于利用后局部搜索法对所述输出解进行优化，得到最优取货解。

结果优化模块的工作流程包括：当未满足弱扰动迭代次数时，对输出解进行弱扰动操作，并判断扰动后是否满足强扰动条件；当满足强扰动条件时，对输出解进行强扰动操作，完成优化，得到最优取货解。

弱扰动操作包括：利用Or-opt算子任选一个行程中两个供应商，在保证原有供应商先后顺序下，将供应商插入到行程内任意节点；利用Exchange算子任意交换两个行程中的两个供应商的位置；利用2-opt算子任意交换一个行程中的两个供应商所有零件的位置。

强扰动操作包括：利用强2-opt算子选择行程中一个供应商，遍历该行程中其他供应商，取最优取货解。

实施例三

在本实施例中，将通过数值实验来验证本发明的优越性。

本实施例基于广东省某新能源汽车企业的脱密数据，生成测试算例进行实验。

随机生成小规模、中规模和大规模三种规模算例，算例类型及参数如表1所示，小规模算例为9个，中大规模规模算例为24个，总算例数量为33个。例如5辆车，20个零件的算例表示为“5-20”。

表1

主机厂(序号0)和供应商(序号1到10)的经纬度及坐标见表2。

表2

1、性能分析

(1)本发明与Gurobi最优解对比

首先基于小规模算例进行性能分析。对于每个问题规模，运行5次取平均值。cost(Gurobi)表示Gurobi求解器求解本发明所提模型的最优解，cost(IALNS)表示本发明所求得的目标值。算法求解时间为Time(s)，Gap表示算法和最优解的相对误差。

表3可见，本发明与最优解的平均相对误差为0.3％，其平均求解时间远小于Gurobi。随着零件规模的增多，Gurobi求解时间大大增加，而本发明仍能在短时间内完成求解，体现了本发明在性能和速度方面的优势。

表3

(2)本发明与其他启发式算法对比

针对较大规模算例，Gurobi难以求得最优解，本实施例将本发明与启发式算法进行大规模算例比较。根据Elshaer等对求解MTVRP问题的启发式算法的分析发现，ALNS算法、蚁群算法、变邻域搜索算法(Variable Neighborhood Search，VNS)和遗传算法(GeneticAlgorithms，GA)等启发式算法性能较优，本实施例选取VNS算法、GA算法作为对比算法。

针对中规模和大规模算例，记录每种算法的求解时间和目标函数值，将IALNS的结果作为基准，相对误差计算公式为：

其中，cost(X)表示VNS或GA算法求得的目标值，cost(IALNS)指的是本发明求得的目标值。在实验中，VNS算法和GA算法均使用前向插入启发式初始解生成方式。每个算例进行五次实验取平均值，实验结果如表4和表5所示。

表4

表5

表4可见，在中规模算例中，本发明在绝大多数规模下的求解结果都优于VNS、GA算法，仅在“6-75”规模下VNS算法略优于本发明，本发明求出的平均值相较于VNS和GA平均改进了3.8％和9.6％，并且运行速度均优于其他启发式算法。表5可见，在大规模算例中，仅在“10-250”算例中，VNS优于本发明，其他规模中，本发明均为最优，本发明相较于VNS和GA平均改进了4.1％和9.4％，并且运行速度优于GA和VNS。本发明在不同规模算例中与VNS和GA算法比较，本发明可以更快的找到全局最优解。

图4(a)表示对于不同零件规模，本发明优于VNS和GA算法。图4(b)表示所有算例三种算法的箱型图。本发明相较于VNS和GA两个算法具有更小的中位数，并且具有更小的上下界和上下四分位，说明结果的离散程度更小。

2.敏感性实验

下面对零件容量和交货期进行敏感性实验，旨在分析在相同零件参数下，不同的零件大小和零件交货期对运输费用和所需运输车辆数量和行程数的影响。

(1)零件容量敏感性实验

为研究零件大小对于运输成本和运输车辆的影响，选取零件数量为10到300等12组算例，考虑小零件、中零件、大零件三种类型，零件容量q_m分别设置为U(6,12)、U(12,18)、U(18,24)，分析所需车辆数与运输费用，实验结果如表6所示。

表6

实验发现，当零件数量增多时，在交货期约束下，需要安排更多的车辆进行配送，所需车辆数量也逐渐增加，且总运输距离增加，导致运输费用增加。

随着零件容量q_m增大，运输费用和车辆使用数量也逐渐增加。因为在零件数量相同时，零件容量的增加，会占用车辆更多的储存空间，需要增加行程及增加车辆来满足配送需求。

(2)零件交货期敏感性实验

零件交货期d_m决定了零件的交货紧急程度，交货期影响了运输费用以及车辆行程数。当交货期十分紧急时，由于零件交货期较为紧急，车辆无法在单次行程中装载多个交货期较为紧急的零件，所以车辆数较高，但车辆行程数较低。

为了充分分析d_m对运输费用和车辆平均行程数的影响，在保证其他参数不变的情况下，选取零件数量p_max为50、100、200、300的不同规模算例，零件交货期设置为U(ξ，ξ+η×p_max)，实验结果如表7所示。

表7

随着参数ξ和η的增大，设定的交货期逐渐宽松，随着交货紧急程度逐渐降低，运输费用呈逐渐降低趋势，车辆平均行程数呈现先增加后逐渐平稳的趋势。

当交货期逐渐宽松时，更多零件会被安排到同一辆车或同一个行程，增加了装载率，因此降低了总的运输费用，并且减少车辆数量，提高单个车辆平均行程数。当交货期十分宽松时，仅需较少的车辆即可完成配送，此时车辆行程数达到最大，且运输费用达到最小值。

以上所述的实施例仅是对本发明优选方式进行的描述，并非对本发明的范围进行限定，在不脱离本发明设计精神的前提下，本领域普通技术人员对本发明的技术方案做出的各种变形和改进，均应落入本发明权利要求书确定的保护范围内。

Claims (10)

1.一种汽车零部件入厂物流同步循环取货方法，其特征在于，包括以下步骤：

构建多行程路径规划模型；

基于所述多行程路径规划模型，以运输费用最小为准则，利用前向插入启发式方法构造初始解；

利用毁坏算子将所述初始解进行破坏，并使用修复算子对破坏后的解进行修复，生成新解；

基于模拟退火机制处理所述新解，得到输出解；

利用后局部搜索法对所述输出解进行优化，得到最优取货解。

2.根据权利要求1所述一种汽车零部件入厂物流同步循环取货方法，其特征在于，运输费最小准则包括：

其中，α为单位时间运输成本，i、j分别为节点i和节点j，V为所有节点集合，k为车辆k，K为车辆集合，g为第g次行程，G为车辆行程集合。

3.根据权利要求1所述一种汽车零部件入厂物流同步循环取货方法，其特征在于，所述初始解的构建方法包括：

构建车辆k的空路径集W₁和空路径集W₂，构建集合U₁和集合U₂，所述集合U₁为为按主机厂与供应商距离升序排序的零件集合，所述集合U₂为最晚允许出发时间的升序的零件集合；

从所述集合U₁和所述集合U₂中分别取出距离最远的零件和最晚允许出发时间中最早的零件/>分别加入所述空路径集W₁和所述空路径集W₂；

遍历所述所述集合U₁和所述集合U₂，计算后续零件插入费用，依次在所述路径集W₁和所述路径集W₂中插入所述零件和所述零件/>

从所述路径集W₁和所述路径集W₂中选择运输费用最低的作为所述初始解。

4.根据权利要求1所述一种汽车零部件入厂物流同步循环取货方法，其特征在于，所述毁坏算子包括：随机破坏算子、最差破坏算子、交货期相关破坏算子和位置相关破坏算子；

所述随机破坏算子用于随机选择一辆车的一个行程，随机选择一定数量的零件从当前路径序列中移除；

所述最差破坏算子用于将所有零件按照距离排序，移除距离最远的零件；

所述交货期相关破坏算子用于对任意两个相异的供应商的零件计算零件相关度，移除交货期相关度较高的零件；

所述位置相关破坏算子用于对任意零件计算位置相关度，移除位置相关度较高的零件。

5.根据权利要求1所述一种汽车零部件入厂物流同步循环取货方法，其特征在于，所述修复算子包括：贪婪修复算子和后悔修复算子；

所述贪婪修复算子用于将由所述毁坏算子移除的零件按修复后目标函数值增量ΔF_m进行升序排列，将零件逐一插入到修复后目标函数值增量ΔF_m最小的位置；

所述后悔修复算子用于计算零件的最优插入位置的目标函数值增量和次优插入位置的目标函数值增量/>基于所述目标函数值增量/>和所述目标函数值增量/>之差的绝对值计算零件的后悔值，并选择所述后悔值大的位置进行修复。

6.根据权利要求1所述一种汽车零部件入厂物流同步循环取货方法，其特征在于，所述模拟退火机制包括：

设置当前迭代代数为ε，总迭代次数为τ，则接受新解的概率为：

其中ΔF为目标函数值增量，T_ε为当前迭代的温度；

在下一次迭代中，T_ε+1的降温概率为：

其中，和/>分别为第ε代开始和结束时的目标值，τ-ε为剩余迭代代数。

7.根据权利要求1所述一种汽车零部件入厂物流同步循环取货方法，其特征在于，所述优化的方法包括：

当未满足弱扰动迭代次数时，对所述输出解进行弱扰动操作，并判断扰动后是否满足强扰动条件；

当满足所述强扰动条件时，对所述输出解进行强扰动操作，完成优化，得到所述最优取货解。

8.根据权利要求7所述一种汽车零部件入厂物流同步循环取货方法，其特征在于，所述弱扰动操作包括：

利用Or-opt算子任选一个行程中两个供应商，在保证原有供应商先后顺序下，将供应商插入到行程内任意节点；

利用Exchange算子任意交换两个行程中的两个供应商的位置；

利用2-opt算子任意交换一个行程中的两个供应商所有零件的位置。

9.根据权利要求7所述一种汽车零部件入厂物流同步循环取货方法，其特征在于，所述强扰动操作包括：利用强2-opt算子选择行程中一个供应商，遍历该行程中其他供应商，取所述最优取货解。

10.一种汽车零部件入厂物流同步循环取货系统，所述取货系统应用权利要求1-9任一项所述的取货方法，其特征在于，包括：模型构建模块、初始解构建模块、新解生成模块、退火迭代模块和结果优化模块；

所述模型构建模块用于构建多行程路径规划模型；

所述初始解构建模块用于基于所述多行程路径规划模型，以运输费用最小为准则，利用前向插入启发式方法构造初始解；

所述新解生成模块用于利用毁坏算子将所述初始解进行破坏，并使用修复算子对破坏后的解进行修复，生成新解；

所述退火迭代模块用于基于模拟退火机制处理所述新解，得到输出解；

所述结果优化模块用于利用后局部搜索法对所述输出解进行优化，得到最优取货解。