报废汽车资源化具有巨大的经济价值和资源环境价值。在报废汽车回收物流网络中，其结构如图 1所示,拆解中心和中转场的两级选址-路径决策将对整个网络的运作效率与效益有重大影响，进而影响报废汽车的回收利用率。

图 1 报废汽车回收物流网络结构 Fig. 1 Structure of ELVs recycling logistics network

图选项

赵佳虹等构建了一个危险废物回收物流系统选址-路径问题的多目标改进模型。该模型特别考虑了废物类型与运输车辆的多样性，废物与运输车辆的相容性，并采用暴露人口吨数表示风险，以最小化最大风险区域代表风险公平性优化目标。同时，该模型主要确定了回收中心的位置，回收中心配备的运输车辆类型，以及各类危险废物的车辆运输路径^[1]。闻轶对LRP问题进行了多目标优化，以最短时间、客户需求和最小成本为目标建立了多目标随机优化模型，随机性在于论文考虑了客户需求的不确定性、车辆行驶时间的不确定性、以及车辆载重约束等影响因素^[2]。张长星对选址-路径问题的算法进行了研究分析，设计了改进遗传算法求解LRP问题^[3]。曾庆成等建立了物流配送系统网络优化的双层规划模型。配送中心的选址问题为模型上层，车辆路径优化问题为模型下层。先由上层选址模型给出初始配送中心选址方案，在此基础上再由一下层VRP模型获得最优车辆路径，然后计算上层选址模型中的供应商到已选配送中心的运输成本，构成系统模型目标函数，通过对目标函数的优化过程再对上层选址模型方案进行调整^[4]。张潜对LRP问题中的选址配给、路径优化、选址-路径优化3类问题的具体优化算法进行了分析和比较，并提出采用两阶段启发式算法来求解LRP问题^[5]。

报废汽车回收物流网络选址-路径问题主要包括：(1)拆解中心选址问题。拆解中心的选址尽可能满足：远离居民区、学校等民用建筑；尽可能靠近中转量大的中转场。(2)中转场选址问题。中转场的选址尽可能满足：回收点到相应的中转站距离最短；报废汽车数量多的回收点尽可能靠近中转站。(3)拆解中心和中转场的建设数目。在模型构建中考虑拆解中心和中转站本身的建设费用。(4)车辆路径问题。车辆路径包括收集车辆及运输车辆的路径问题，需解决收集车辆在每一个周期内的运行路线。

报废汽车回收物流系统可看作由集合G=(V,E) 表示的一个网络图。V为节点位置，V={o|o=1,2,…,p,p+1,p+2,…,p+n,p+n+1,p+n+2,…,p+n+m}；节点 H={h|h=1,2,…,p} 为拆解中心候选点的位置； J={j|j=1,2,…,n} 为中转场候选点的位置； I={i|i=1,2,…,m} 为m个回收点的位置。

报废汽车回收物流系统中，共配备两种车型，一种是从回收站点将收集到的废旧汽车运往中转场的收集车辆；另一种是从中转场大批量运送废旧汽车到拆解中心的运输车辆。

报废汽车回收物流网络中选址-路径问题属于两级设施选址、多车型回收并包含车辆载重约束、设施容量约束、无时间窗的LRP问题。选址-路径优化模型构建的目标是使得整个系统的固定投资和周期内的运行成本之和最小，即拆解中心和中转场的建设成本、收集车辆的收集成本及运输车辆的运输成本之和最小。

模型的前提假设：(1)拆解中心和中转场候选点的数目、位置及建设费用已知；(2)回收点数目、位置及日回收量已知；(3)每个回收点的报废汽车仅由一辆收集车辆进行收集，车辆运载量不得超过其最大载重，且同类型的车辆最大载重相同；(4)假定车辆在每条路径上行驶的最长时间为1 d；(5)每条路径上回收点的报废汽车收集量小于或等于收集车辆的额定载重；(6)每辆收集车辆的始发点和终点为同一中转场或拆解中心，且只负责一次收集活动；(7)拆解中心具有中转场的全部功能，即拆解中心是一个特殊的中转场，故拆解中心可越级收集报废汽车；(8)车辆收集和运输成本与运输距离和运量成正比；(9)道路状况稳定，不考虑交通堵塞问题或车辆本身故障情况，车辆恒速稳定运行；(10)拆解中心建成后的使用年限为M年，中转场建成后的使用年限为N年。

模型符号假设： H={h|h=1,2,…,p} 为拆解中心候选点集合；J={j|j=1,2,…,n}为中转场候选点集合； I={i|i=1,2,…,m}为回收点集合； U=H∪I为拆解中心和回收点的集合；W=H∪J为 拆解中心和中转场的集合；O=I∪J为中转场和回收点的集合；V=H∪J∪I为拆解中心、中转场和回收点的集合； K={k|k=1，2，…,a} 为收集车辆集合； S={s|s=1，2，…,b}为运输车辆集合；f_h为拆解中心候选点h的建设费用；f_j为中转场候选点j的建设费用；g_h为拆解中心h拆解单位报废汽车的成本；g_j为中转场j处理单位报废汽车的成本；c_a为收集车辆的单位距离行驶费用；c_b为运输车辆的单位距离行驶费用；p_h为拆解中心h的拆解能力；p_j为中转场j的中转能力；Q_a为收集车辆的额定载重量；Q_b为运输车辆的额定载重量；M为拆解中心建成后的使用年限；N为中转场建成后的使用年限；q_i为回收点i的日报废汽车收集量；d_ij为从点i到点j的直线距离(其中i∈V，j∈V);d_jh为从点j到点h的直线距离；d_ih为从点i到点h的直线距离；Y_h=1为在h处建立拆解中心，否则Y_h=0; Y_j=1为在j点建立中转场，否则Y_j=0；X_ih^k=0为从i点到j点的报废汽车由收集车辆k负责收集，否则X_ih^k=0；X_ih^k=1为从i点到h点的报废汽车由收集车辆k负责收集，否则X_ih^k=0；Z_hj^s=1为第j(j∈J)个中转场的废旧汽车由运输车辆s运送至拆解中心h,否则Z_hj^s=0。

由于拆解中心成本F₁主要指拆解中心建设成本与拆解成本,成本为：中转场成本主要指中转场建设成本与中转成本，中转场成本为：收集车辆年运行成本为运输车辆年运行成本为：

故模型构建如下：

点击浏览公式

点击浏览公式

点击浏览公式

点击浏览公式

点击浏览公式

点击浏览公式

点击浏览公式

点击浏览公式

点击浏览公式

点击浏览公式

点击浏览公式

点击浏览公式

点击浏览公式

点击浏览公式

点击浏览公式

点击浏览公式

上述式(1)表示总目标函数，即中转场和拆解中心建设及运行成本、各节点间运输成本之和最小；式(2)表示每个回收点仅由一辆收集车辆负责收集；式(3)表示路径连续性约束，即到达任何节点的车辆必须离开该节点；式(4)表示收集车辆最大载重约束；式(5)表示每辆收集车辆在每条收集路径上只经过一个拆解中心或中转场，并保证拆解中心或中转场的每一辆收集车辆都能投入运行；式(6)表示拆解中心一旦为某个回收点服务，该拆解中心一定建设；式(7)表示中转场一旦为某个回收点服务，该中转场一定建设；式(8)表示中转场容量约束；式(9)表示拆解中心容量约束；式(10)表示每个中转场只能被运输车辆访问一次；式(11)表示从回收点运往中转场的报废汽车和回收点运往拆解中心的报废汽车的总和等于回收点的回收量；式(12)~式(16)为决策变量0-1取值约束。

针对遗传算法和禁忌搜索算法各自的搜索不足，文章将构造遗传算法和禁忌搜索的组合算法。采用两阶段算法进行求解：第一阶段进行中转场选址,按照实际问题结合已构建的数学模型初始化问题，设计遗传算法算子以及禁忌搜索算法的参数。其次设定遗传算法和禁忌搜索算法之间的结合条件，规定结合点。执行遗传搜索，在遗传搜索的过程中判定是否满足禁忌搜索的条件，若满足，则进行禁忌搜索，否则继续进行遗传搜索，最终输出最优解。第二阶段在中转场已选的基础上进行拆解中心选址。

(1)编码

选址-路径问题的解包括四部分内容：选址、分派、车辆分配、路径选择，文章拟采用非定长实数编码方式。①对候选拆解中心、候选中转场、回收站点、车辆进行编号，利用编号进行编码；②根据解的特点构建染色体，染色体的长度各不相等，但所有染色体均由3个子串构成。其中子串3表示各回收点的排列顺序；子串1和子串3一一对应表示为各回收点服务的车辆编号；子串2表示的是子串1中车辆归属的中转场的编号。具体编码过程参照以下实例：现已知收集车辆4辆，编号1，2，3，4；回收点10个，编号4，5，…，14；3个中转场，编号1，2，3；拆解中心2个，编号为4，5。具体编码如下：

其中子串1中1，2，3，4车辆都有，表示没有多余车辆，每辆车都得到合理利用。另外子串1中基因位1，6，7均为1，一一对应的子串3中回收点10，9，13，表示由车辆1按照10-9-13的顺序回收。同理，车辆2按12-8-14的顺序进行回收，车辆3按6-7-11的顺序回收，车辆4单独对回收点5进行回收。子串2按照3-1-4-2的顺序排列，表示车辆1，2，4分别归属于中转场和拆解中心3，1，2，车辆3归属于拆解中心4。

(2)初始化种群

设种群规模为num，随机产生初始种群，方法如下：随机产生一条染色体，判断是否满足车辆容量和中转场容量的限制。若满足，即为可行解，否则另外产生一条染色体，直到产生num条可行染色体为止。其具体的生成步骤如下：①设置种群规模为m。②从待选拆解中心和中转场中随机选择3个作为已选物流节点。③对已选的3个物流节点进行分派，分别计算r_u，r_iu(r_u表示拆解中心或中转场与其他拆解中心或中转场之间的最短距离的一半，r_iu表示客户点与拆解中心或中转场之间的距离)。④判定是否r_iu≤r_u，若是，则将客户点i分配给拆解中心或中转场u；否则，将客户点i分配给距离最近的拆解中心或中转场。⑤已选拆解中心或中转场u从分派的回收点中随机选择产生一条新路径，判定该路线的运载量超限与否，若不超限，继续随机选择客户点插入路线，累加路线的总回收量；否则，进行调整。⑥所有回收站点均加入路线中，并且均满足车容量和场站容量限制，得到一个初始解。

(3)适应度函数

令适应度函数为f_i=Z_min/Z_l，其中f_i为染色体l的适应度函数值；Z_min为同一代染色体中目标函数值的最小值；Z_l为第l条染色体的目标函数值。故适应度函数值取值范围为0,1]。

(4)选择操作

采用轮盘赌选择和精英保留相结合的选择策略。①采用精英保留策略。每次生成下一代种群时，先将父代种群以及交叉、变异操作产生的临时种群中的最优个体直接复制进入下一代种群；②对除精英外的其他个体的适应函数值求和，③对除精英以外的染色体分别进行选择概率计算，i=1,2,…，m；④以概率分布P_k从除精英外的上一代种群p(t)中随机选择染色体和精英染色体一起构成新一代种群 p(t+1)。

(5)交叉和变异操作

①选择交叉操作的概率 P_c，并生产伪随机数r_k[r_k∈(0,1)，k=1,2,…，n]，若r_k<P_c，则选择V_k作为父代，然后随机配对选择出的父代(V_i，V_j)； ②选择父代V_i和V_j 的子串1和子串2进行单点交叉和两点交叉操作，同时进行对换变异操作；子串3采用顺序交叉和部分匹配交叉操作，并进行逆转变异操作。

(6)禁忌搜索操作

①设定遗传算法迭代过程中，每隔N代对种群中所有染色体执行禁忌搜索算法(设迭代步数为IN，每次迭代共搜索当前解的NS个邻近解，禁忌长度为TL)，之后继续执行遗传算法。②在遗传算法计算过程中若当前最优解连续保持L代不变，也对其执行禁忌搜索算法(设迭代步数为IN′，每次迭代共搜索当前解的NS′个邻近解，禁忌长度为TL′)，之后继续执行遗传搜索。③当前最优解已连续保持2×L代不变，则对其再次执行禁忌搜索算法，之后继续执行遗传算法。④当前最优解已连续保持3×L代不变，则终止遗传/禁忌混合算法。

Step 1：初始化问题。

Step 2：设置遗传算法的种群规模num和最大迭代次数maxgen，交叉概率P_c，变异概率P_m和禁忌搜索算法的参数N,L。

Step 3：生成种群规模为num的初始种群；设遗传算法的当前进化代数gen=0。

Step 4：计算初始种群中每个个体的目标函数值和适应度函数值。

Step 5：将初始种群的最优目标函数值best作为当前最优目标函数值best_new，记录当前最优解连续保持代数β=0。

Step 6：若β=3L，转Step 16；否则，转Step 7。

Step 7：若β<L，转Step 9；否则，转Step 8。

Step 8：若β%L≠0，转Step 9。否则，对当前最优解执行禁忌搜索算法，将当前种群的最优目标函数值best和best_new进行比较，若best<best_new，令best_new=best，β=0，转Step 9；否则，直接转Step 9。

Step 9：若gen%N=0，对当前种群中所有染色体执行禁忌搜索算法，转Step 10；否则，直接转Step10。

Step 10：采用轮盘赌选择和精英保留策略相结合的选择策略选择染色体。

Step 11：采用替代策略使用种群中最优的染色体替代种群中适应能力较差的个体。

Step 12：按照交叉概率P_c，两两配对执行交叉操作。

Step 13：按照变异概率P_m，在种群中选择进行变异的个体执行变异操作。

Step 14：令gen=gen+1，计算当前种群中每个个体的目标函数值和适应度函数值。将当前种群的最优目标函数值best和best_new进行比较，若best<best_new，令best_new=best，β=0；否则，令β=β+1。

Step 15：若gen>maxgen，转Step 16；否则，转Step 6。

Step 16：算法结束，输出结果。

以上算法步骤中禁忌搜索算法的具体步骤如下：

Step 1：在遗传搜索过程生产的最优解中产生初始解。

Step 2 ：令禁忌表为空，制定禁忌长度L及迭代次数StopL。

Step 3：令初始解为当前解和best_new。

Step 4：若p<StopL，执行Step 5，若否，输出结果；其中，p为当前迭代次数。

Step 5：设计邻域产生策略。

Step 6：产生当前解的25个邻域解。

Step 7：将这25个邻域解进行从小到大的排序。

Step 8：选出其中前面10个邻域解作为候选解。

Step 9：若best<best_new，令best_new=best，更新禁忌表，当前解对应的禁忌对象的禁忌长度为n,禁忌表中其他对象分别减1；若否，转Step 12。

Step 10：若该解的禁忌对象的禁忌长度≠0，排名第一的候选解被删除，排名第二的候选解成为排名第一，转Step 13；若否更新当前解；更新禁忌表，当前解对应的禁忌对象的禁忌长度为n,禁忌表中其他对象分别减1。

Step 11：p=p+1转step 4。

经调研可知，成都市某报废汽车回收拆解公司正面临选址-路径决策。该公司有20家报废汽车回收点，6家中转场候选点，3家拆解中心候选点，其位置如图 2所示。

注：实心圆圈表示拆解中心候选点；“米”形表示中转场候选点；空心圆圈表示回收点。 图 2 回收站点、中转场和拆解中心的位置图 Fig. 2 Locations of recycling sites,transit depots and disassembly centers

图选项

假定在收集报废汽车过程中，单位运费一致，且假设所有路段的运输条件均相同，即报废汽车运价函数相同。利用网络Google地图测距，得到回收点与候选中转场及拆解中心之间的距离(l_z表示回收点到中转场的距离；l_c表示回收点到拆解中心的距离)如表 1所示，各中转场候选点至拆解中心候选点距离如表 2所示。

从回收点到中转场、回收站点到拆解中心以及回收点到拆解中心均采用整车运输，根据对2006年以来的公路货物运输价格指数的分析，结合汽车的平均质量，从回收点到中转场和拆解中心每辆车每千米的运价为0.000 3元/(kg·km),即0.3元/(t·km)，中转场到处理中心单位车辆单位里程的运价为0.000 35元/(kg·km)，即0.35元/(t·km)。

X公司中转场是基于已有站点的改造扩建，中转场1，2，3，4，5，6的固定建设成本分别为9，10，7，13，12，10。资源整合背景下成立的X公司，其拆解中心采用两条机械拆解线，其专业化和机械化程度较高，拆解中心1，2，3的建设成本分别为500，600，1 000。中转场和拆解中心的建设投资回收期均为15 a。各中转场最大回收能力与最小回收能力、拆解中心最大处理能力与最小处理能力的值如表 3和表 4所示。

此外，收集车辆的最大车容量为4辆，运输车辆的最大车容量为12辆。

参数设置如下：

(1)遗传算法初始种群规模num=80；最大迭代次数maxgen=500；交叉概率P_c=0.3；变异概率P_m=0.1。

(2)禁忌搜索算法禁忌长度L=10；最大迭代次数stopL=90。

(3)规定遗传搜索过程中gen%N=0(其中N=200)，执行禁忌搜索。

采用仿真计算，使用MATLAB7.9编程实现。最终报废汽车回收网络选址-路径如图 3所示，搜索过程中平均迭代次数变化趋势如图 4所示，搜索过程中最优解迭代次数的变化趋势如图 5所示。

注： 实心圆圈表示拆解中心；正方形表示中转场；空心圆圈表示回收点。 图 3 废旧汽车回收物流网络选址-选线 Fig. 3 Location-routing inELVs recycling logistics network

图选项

图 4 平均迭代次数变化趋势图 Fig. 4 Changing trend of average iteration number

图选项

图 5 最优解迭代次数变化趋势 Fig. 5 Changing trend ofiteration number of optimal solution

图选项

故搜索最终得到的最优解如表 5~表 7所示。

我国即将进入报废汽车数量激增的时期，高效率、高效益的回收物流体系是报废汽车回收利用的重要基础，而报废汽车回收物流节点的布局及回收线路的安排在整个回收物流体系构建中又起着举足轻重的作用。本文构建了报废汽车回收物流网络选址-路径优化模型，针对该模型设计了遗传搜索和禁忌搜索组合算法，并以成都某公司为例，采用matlab7.9编程，对模型进行了实例验证。该研究以期能为企业进行报废汽车回收网络设施选址及车辆路径安排提供决策依据，从而实现企业资源利用效率的最大化，并提高报废汽车的回收利用率。文章在各回收点回收量已知的基础上构建模型，将来可以将回收量的不确定性纳入研究范畴，还可进行回收质量、回收时间等的不确定性研究。