第15卷第1期 智能系统学报 Vol.15 No.1 2020年1月 CAAI Transactions on Intelligent Systems Jan.2020 D0L:10.11992tis.201905042 多配送中心下生鲜农产品同步取送选址-路径优化 李冰，党佳俊 (郑州大学管理工程学院，河南郑州450001) 摘要：多配送中心下生鲜农产品配送工作中配送中心选址和车辆取送是两项最为重要的工作，故本文研究带 同步取送的生鲜农产品选址一路径问题。首先，建立考虑车辆容量、货物作业时间、取送作业时间窗等约束条 件的非线性规划模型，模型以各配送区域内产生的运输成本、惩罚费用、货损费用总和最小为目标函数。然 后，根据模型特点设计融合中心评估指数和改进遗传算法的启发式算法，算法先利用中心评估指数确定配送中 心和车辆的配送区域，将区域划分的信息传递给改进遗传算法进行各区域内的路径优化。最后，通过对比取送 分离和同步取送两种配送方式验证本文提出的配送模式及模型是合理有效的，可为企业的生鲜农产品配送提 供决策依据。 关键词：生鲜农产品；多配送中心；同步取送；选址-路径问题；路径优化；时间窗；中心评估指数；改进遗传算法 中图分类号：TP391文献标志码：A 文章编号：1673-4785(2020)01-0050-09 中文引用格式：李冰，党佳俊.多配送中心下生鲜农产品同步取送选址-路径优化.智能系统学报，2020,15(1)：50-58. 英文引用格式：LI Bing,.DANGJiajun..Fresh agricultural cargoes location-routing optimization with simultaneous pickup and de- livery for multiple distribution centers[Jl.CAAI transactions on intelligent systems,2020,15(1):50-58. Fresh agricultural cargoes location-routing optimization with simultaneous pickup and delivery for multiple distribution centers LI Bing,DANG Jiajun (School of Management Engineering,Zhengzhou University,Zhengzhou 450001,China) Abstract:The distribution center location and the vehicle pick-up and delivery are two important parts in the fresh agri- cultural cargoes organization for multiple distribution centers.In this paper,we present the location-routing problem with simultaneous pick-up and delivery of fresh agricultural cargoes.Firstly,a non-linear programming model is formu- lated with the constraints of vehicle capacity,operation time for cargoes and time windows for pick-up and delivery.The objective function of the model is to minimize the total distribution cost that is composed of transportation cost,penalty cost and damage cost in all distribution areas.Secondly,the heuristic algorithm combining central evaluation indicator and improved genetic algorithm are given according to the characteristics of the model.The distribution center and the vehicle distribution area are determined by the central evaluation indicator.After that,the result of distribution areas di- vision is put into the improved genetic algorithm for improving vehicle routing.Finally,the separate mode and simultan- eous mode of pick-up and delivery are compared,proving that the later mode proposed in this paper is reasonable and effective.The study can provide the the basis for decision-making of fresh agricultural cargoes organization for enterprise. Keywords:fresh agricultural cargoes,distribution center,simultaneous pickup and delivery;location-routing problem; route optimization;time windows;central evaluation indicator;improved genetic algorithm 选址-路径(location-routing problem,LRP)问problem,LAP)和车辆路径问题(vehicle routing 题是配送中心选址分配问题(location allocation problem,VRP)的组合问题。生鲜农产品配送对 收稿日期：2019-05-23. 服务时效性有很高的要求，且同一客户经常具备 基金项目：国家自然科学基金项目(U1604150,U1804151):河南 送货和回收被取货的双向需求。因此，对传统的 省科技攻关计划项目(202102310310). 通信作者：李冰.Email:Ibing@zzu.edu.cn 选址一路径问题进行扩展，同时解决生鲜农产品
DOI: 10.11992/tis.201905042 多配送中心下生鲜农产品同步取送选址−路径优化 李冰，党佳俊 （郑州大学 管理工程学院，河南 郑州 450001） 摘 要：多配送中心下生鲜农产品配送工作中配送中心选址和车辆取送是两项最为重要的工作，故本文研究带 同步取送的生鲜农产品选址−路径问题。首先，建立考虑车辆容量、货物作业时间、取送作业时间窗等约束条 件的非线性规划模型，模型以各配送区域内产生的运输成本、惩罚费用、货损费用总和最小为目标函数。然 后，根据模型特点设计融合中心评估指数和改进遗传算法的启发式算法，算法先利用中心评估指数确定配送中 心和车辆的配送区域，将区域划分的信息传递给改进遗传算法进行各区域内的路径优化。最后，通过对比取送 分离和同步取送两种配送方式验证本文提出的配送模式及模型是合理有效的，可为企业的生鲜农产品配送提 供决策依据。 关键词：生鲜农产品；多配送中心；同步取送；选址−路径问题；路径优化；时间窗；中心评估指数；改进遗传算法 中图分类号：TP391 文献标志码：A 文章编号：1673−4785(2020)01−0050−09 中文引用格式：李冰, 党佳俊. 多配送中心下生鲜农产品同步取送选址−路径优化 [J]. 智能系统学报, 2020, 15(1): 50–58. 英文引用格式：LI Bing, DANG Jiajun. Fresh agricultural cargoes location-routing optimization with simultaneous pickup and delivery for multiple distribution centers[J]. CAAI transactions on intelligent systems, 2020, 15(1): 50–58. Fresh agricultural cargoes location-routing optimization with simultaneous pickup and delivery for multiple distribution centers LI Bing，DANG Jiajun (School of Management Engineering, Zhengzhou University, Zhengzhou 450001, China) Abstract: The distribution center location and the vehicle pick-up and delivery are two important parts in the fresh agricultural cargoes organization for multiple distribution centers. In this paper, we present the location-routing problem with simultaneous pick-up and delivery of fresh agricultural cargoes. Firstly, a non-linear programming model is formulated with the constraints of vehicle capacity, operation time for cargoes and time windows for pick-up and delivery. The objective function of the model is to minimize the total distribution cost that is composed of transportation cost, penalty cost and damage cost in all distribution areas. Secondly, the heuristic algorithm combining central evaluation indicator and improved genetic algorithm are given according to the characteristics of the model. The distribution center and the vehicle distribution area are determined by the central evaluation indicator. After that, the result of distribution areas division is put into the improved genetic algorithm for improving vehicle routing. Finally, the separate mode and simultaneous mode of pick-up and delivery are compared, proving that the later mode proposed in this paper is reasonable and effective. The study can provide the the basis for decision-making of fresh agricultural cargoes organization for enterprise. Keywords: fresh agricultural cargoes; distribution center; simultaneous pickup and delivery; location-routing problem; route optimization; time windows; central evaluation indicator; improved genetic algorithm 选址-路径 (location-routing problem, LRP) 问 题是配送中心选址分配问题 (location allocation problem, LAP) 和车辆路径问题 (vehicle routing problem, VRP) 的组合问题。生鲜农产品配送对 服务时效性有很高的要求，且同一客户经常具备 送货和回收被取货的双向需求。因此，对传统的 选址−路径问题进行扩展，同时解决生鲜农产品 收稿日期：2019−05−23. 基金项目：国家自然科学基金项目 (U1604150，U1804151)；河南 省科技攻关计划项目 (202102310310). 通信作者：李冰. Email：lbing@zzu.edu.cn. 第 15 卷第 1 期 智 能 系 统 学 报 Vol.15 No.1 2020 年 1 月 CAAI Transactions on Intelligent Systems Jan. 2020
第1期 李冰，等：多配送中心下生鲜农产品同步取送选址一路径优化 ·51· 配送中心选址和基于同步取送方式下的路径优化 送货、取货需求。冀巨海等20考虑配送过程带取 问题有利于帮助企业全面协调配送系统中的各个 送的双向作业模式，使用Gurobi对问题进行求 环节，在最少成本下满足客户的取送需求。 解，但该模式为统一取完后再统一送的取送分离 近年来，国内外学者对生鲜农产品路径优化 配送方式，求解后每条路径中车辆的配送性质相 问题进行了大量研究。缪小红等山采用遗传算法 同，对车辆的利用率不能达到最高且行驶距离及 求解包含配送途中产生的货损成本、超出时间窗 行驶时间较长。 的惩罚成本等的生鲜农产品物流配送模型。吴 综上所述，本文提出考虑同步取送的选址-路 瑶等设计混合遗传算法解决带时间窗的易腐食 径问题(ocation-routing problem with simultaneous 品集成生产-配送问题优化模型。Hsiao等)应用 pickup and delivery,LRPSPD)。设计一种融合中心 混合遗传算法研究考虑食品类型和温度变化的路 评估指数及改进遗传算法的启发式算法(hybrid 径优化问题。王淑云等设计集K-means聚类算 procedure combining central evaluation index and im- 法、蚁群算法和随机动态规划算法为一体的路径 proved genetic algorithm,CEI&IGA),以中心评估指 优化算法求解冷链商品多温共配路径优化模型。 数解决选址问题、以改进遗传算法解决路径优化 鲍春玲等考虑企业拥有多个配送中心、有限车 问题。本文提出的选址-路径问题解决方法合理 辆数且各车辆可回到任一配送中心继续配送的情 结合了企业按需求进行分区配送及取送同步路径 况，通过改进遗传算法解决冷链物流联合配送路 优化两阶段问题，属于全局优化过程，可有效降 径优化模型。在选址问题上，陈绍洵等建立双 低配送成本，为物流企业决策提供依据。 层规划选址模型来刻画企业选址决策及消费者偏 好行为之间的相互关系。肖建华等研究非等覆 1问题建模 盖半径思想下的生鲜农产品配送中心选址问题。 1.1问题描述 狄卫民等图考虑到农产品的易腐败特征和配送中 本文研究多车辆服务多个配送中心即“多对 心的配送能力限制建立了易腐农产品配送中心选 多”的生鲜农产品同步取送选址-路径优化问题。 址问题的0-1整数非线性规划模型。现有生鲜农 在该配送网络中，客户既有对生鲜农产品的送货 产品选址-路径问题中以单一配送为主。其中包 需求，又有对腐烂变质农产品的取回需求。所有 括带低碳-1o、时间窗121、容量约束31、多目 车辆从企业出发到各配送中心装货并前往客户点 标的等因素的选址-路径问题。对该问题的解决 完成送货、取货后返回配送中心继续下一批任 方法包括两阶段启发式算法6、量子进化算法m 务，所有任务按批次进行处理。各配送批次中既 量子进化算法与遗传算法协同的双智能算法、 可以有送货任务也可以有取货任务，即车辆同步 模拟退火算法等。 取送。该选址-路径优化问题目标是首先选择配 基本LRP以及衍生出不同类型的LRP中路 送中心、并为车辆指派配送区域，其次优化各车 径优化大多未考虑客户的取货双向需求。但是由 辆的配送路径以使车辆的总配送费用最小化。对 于生鲜农产品易腐及易变质的特点，配送网点有 比单一配送中心取送问题，本文提出多配送中心 退回商品的需求，因此企业需要同时满足客户的 优化方案如图1所示。 (a)单一配送中心取送 (b)多配送中心取送 图1基于多配送中心取送优化前后对比图 Fig.1 Contrast figure before and after optimization of delivery and pickup based on multiple distribution centers
配送中心选址和基于同步取送方式下的路径优化 问题有利于帮助企业全面协调配送系统中的各个 环节，在最少成本下满足客户的取送需求。 近年来，国内外学者对生鲜农产品路径优化 问题进行了大量研究。缪小红等[1] 采用遗传算法 求解包含配送途中产生的货损成本、超出时间窗 的惩罚成本等的生鲜农产品物流配送模型。吴 瑶等[2] 设计混合遗传算法解决带时间窗的易腐食 品集成生产−配送问题优化模型。Hsiao 等 [3] 应用 混合遗传算法研究考虑食品类型和温度变化的路 径优化问题。王淑云等[4] 设计集 K-means 聚类算 法、蚁群算法和随机动态规划算法为一体的路径 优化算法求解冷链商品多温共配路径优化模型。 鲍春玲等[5] 考虑企业拥有多个配送中心、有限车 辆数且各车辆可回到任一配送中心继续配送的情 况，通过改进遗传算法解决冷链物流联合配送路 径优化模型。在选址问题上，陈绍洵等[6] 建立双 层规划选址模型来刻画企业选址决策及消费者偏 好行为之间的相互关系。肖建华等[7] 研究非等覆 盖半径思想下的生鲜农产品配送中心选址问题。 狄卫民等[8] 考虑到农产品的易腐败特征和配送中 心的配送能力限制建立了易腐农产品配送中心选 址问题的 0−1 整数非线性规划模型。现有生鲜农 产品选址−路径问题中以单一配送为主。其中包 括带低碳[9-10] 、时间窗[11-12] 、容量约束[13-14] 、多目 标 [15] 等因素的选址−路径问题。对该问题的解决 方法包括两阶段启发式算法[16] 、量子进化算法[17] 、 量子进化算法与遗传算法协同的双智能算法[18] 、 模拟退火算法[19] 等。 基本 LRP 以及衍生出不同类型的 LRP 中路 径优化大多未考虑客户的取货双向需求。但是由 于生鲜农产品易腐及易变质的特点，配送网点有 退回商品的需求，因此企业需要同时满足客户的 送货、取货需求。冀巨海等[20] 考虑配送过程带取 送的双向作业模式，使用 Gurobi 对问题进行求 解，但该模式为统一取完后再统一送的取送分离 配送方式，求解后每条路径中车辆的配送性质相 同，对车辆的利用率不能达到最高且行驶距离及 行驶时间较长。 综上所述，本文提出考虑同步取送的选址-路 径问题 (ocation-routing problem with simultaneous pickup and delivery, LRPSPD)。设计一种融合中心 评估指数及改进遗传算法的启发式算法 (hybrid procedure combining central evaluation index and improved genetic algorithm，CEI&IGA)，以中心评估指 数解决选址问题、以改进遗传算法解决路径优化 问题。本文提出的选址−路径问题解决方法合理 结合了企业按需求进行分区配送及取送同步路径 优化两阶段问题，属于全局优化过程，可有效降 低配送成本，为物流企业决策提供依据。 1 问题建模 1.1 问题描述 本文研究多车辆服务多个配送中心即“多对 多”的生鲜农产品同步取送选址−路径优化问题。 在该配送网络中，客户既有对生鲜农产品的送货 需求，又有对腐烂变质农产品的取回需求。所有 车辆从企业出发到各配送中心装货并前往客户点 完成送货、取货后返回配送中心继续下一批任 务，所有任务按批次进行处理。各配送批次中既 可以有送货任务也可以有取货任务，即车辆同步 取送。该选址−路径优化问题目标是首先选择配 送中心、并为车辆指派配送区域，其次优化各车 辆的配送路径以使车辆的总配送费用最小化。对 比单一配送中心取送问题，本文提出多配送中心 优化方案如图 1 所示。 (a) 单一配送中心取送 10 9 8 7 1 2 3 4 6 5 (b) 多配送中心取送 10 9 7 1 3 6 5 4 2 8 图 1 基于多配送中心取送优化前后对比图 Fig. 1 Contrast figure before and after optimization of delivery and pickup based on multiple distribution centers 第 1 期 李冰，等：多配送中心下生鲜农产品同步取送选址−路径优化 ·51·
·52 智能系统学报 第15卷 1.2 LRPSPD问题假设 1.3.2数学模型 假定企业将生鲜产品储存于配送中心，根据 以总配送成本最小为优化目标构建物流配送 顾客订单，在优化的配送路线下进行物流配送。 优化模型如下： 为将现实的NP难题转换为数学模型进行量化求 minZ=C】 解，需要进行如下假设：1)企业拥有多辆车但车 辆有限，车辆从配送中心出发完成配送任务后返 回配送中心；2)车辆从企业到各配送中心过程中 622---- 的成本忽略不计；3)有多个配送中心；4)客户位 置及取送货需求已知；5)每个客户只能由一辆车 c盆2，-功+-+ (1) 服务；6)每辆车每批完成客户订单的量不能超过 e 车辆的最大装载量，当承载量达到最大装载量 盆之2小n4+aoa 时，车辆驶回配送中心；7)每辆车的规格相同。 S.t. 1.3模型建立 ∑em+xaU≤Q.keKj (2) 1.31符号说明 1)符号 N表示客户集合，N={ii=0,1,2,,N},其中 ∑=%j∈NkeK (3) i为客户编号，N为客户总数，0表示企业车场。 M表示配送中心集合，M={m|m=0,1,2,…,M},其 ∑t=y,ieN,k∈K (4) 中m为配送中心编号，M为配送中心总数。K表 示企业拥有的车辆集合，K={kk=l,2,…,R},其中 Txt+a()'t≤T,i,jeN,k∈K (5) k为车辆编号，R为车辆总数。Z表示配送性质集 合，Z={z|z=1,2},其中=1代表送货，=2代表取 Ti=Ti+tj.Vi.jeN,keK (6) 货。d表示由客户i到客户j的走行距离。，表 T=T+,Yi,jeN,k∈K (7) 示客户i到客户j的走行时间，1表示单位货物作 xig=0or 1,V i,j.k (8) 业时间。 2)参数 ya =0 or 1,Vi,k (9) a(i)表示客户i的配送需求量；当=1时， 目标式()表示使总配送成本最小，总配送成 a()'0表示客户i的取货需求量；ET表示客户 第3项中x表示max(x,0),意昧着车辆送取过程 j要求的最早送货时间，LT表示客户j要求的最晚 中到达客户的时刻如果符合时间窗要求则惩罚成 送货时间；ET表示客户j要求的最早取货时间， 本为0，否则早到或者晚到都会产生成本。约束 LT表示客户j要求的最晚取货时间；ET,LT和 条件式(2)表示车辆k在每个客户点完成卸货或 ET,L分别表示客户j要求的送货、取货时间 者装货任务后车辆承载的货物量不能超过该车辆 窗；C,表示车辆单位运输成本；C2表示早于时间 最大装载量。约束条件式(3)、(4)表示对于任一 窗配送的单位惩罚成本；C,表示晚于时间窗配送 客户点，仅能有一辆车访问并离开。约束条件式 的单位惩罚成本；Q表示车辆的最大承载量；e表 (⑤)表示车辆k到达点j进行取货的时刻必须晚于 示生鲜产品单位价格：m,表示运输过程中的单位 车辆k在点j完成卸货作业的时间：约束条件式 货损比例，m2表示装卸过程中的货损比例。 (6)、(7)保证配送过程的连续性；约束条件式(8)、 3)变量 (9)表示变量约束。 T*、T表示配送车辆k分别进行送货、取货 2CEI&IGA算法设计 到达客户中心j的时刻；fm表示车辆到达客户 i时的承载量；x狱表示如果车辆k由客户i驶向客 本文所讨论的同步取送选址-路径问题首先 户j,则决策变量x联等于1，否则等于0：yk表示如 要解决的问题就是确定配送中心，其次是为车辆 果客户i由车辆k服务，则决策变量y等于1，否 指派配送区域并完成取送货过程中的路径优化。 则等于0。 为解决此问题，第1步通过设计综合客户间距
1.2 LRPSPD 问题假设 假定企业将生鲜产品储存于配送中心，根据 顾客订单，在优化的配送路线下进行物流配送。 为将现实的 NP 难题转换为数学模型进行量化求 解，需要进行如下假设：1) 企业拥有多辆车但车 辆有限，车辆从配送中心出发完成配送任务后返 回配送中心；2) 车辆从企业到各配送中心过程中 的成本忽略不计；3) 有多个配送中心；4) 客户位 置及取送货需求已知；5) 每个客户只能由一辆车 服务；6) 每辆车每批完成客户订单的量不能超过 车辆的最大装载量，当承载量达到最大装载量 时，车辆驶回配送中心；7) 每辆车的规格相同。 1.3 模型建立 1.3.1 符号说明 1) 符号 0,1,2,··· N¯ N¯ 0,1,2,··· M¯ M¯ 1,2,··· K¯ K¯ N 表示客户集合，N={i |i= , }，其中 i 为客户编号， 为客户总数，0 表示企业车场。 M 表示配送中心集合，M={m | m= , }，其 中 m 为配送中心编号， 为配送中心总数。K 表 示企业拥有的车辆集合，K={k |k= , }，其中 k 为车辆编号， 为车辆总数。Z 表示配送性质集 合，Z={z | z =1, 2}，其中 z=1 代表送货，z=2 代表取 货。dij 表示由客户 i 到客户 j 的走行距离。tij 表 示客户 i 到客户 j 的走行时间，t 表示单位货物作 业时间。 2) 参数 ET1 j LT1 j ET2 j LT2 j [ ET1 j ,LT1 j ] [ ET2 j ,LT2 j ] α(i) z 表示客户 i 的配送需求量；当 z=1 时 ， α(i) 1 0 表示客户 i 的取货需求量； 表示客户 j 要求的最早送货时间， 表示客户 j 要求的最晚 送货时间； 表示客户 j 要求的最早取货时间， 表示客户 j 要求的最晚取货时间； 和 分别表示客户 j 要求的送货、取货时间 窗；C1 表示车辆单位运输成本；C2 表示早于时间 窗配送的单位惩罚成本；C3 表示晚于时间窗配送 的单位惩罚成本；Q 表示车辆的最大承载量；e 表 示生鲜产品单位价格；m1 表示运输过程中的单位 货损比例，m2 表示装卸过程中的货损比例。 3) 变量 T 1 jk T 2 jk f i wagon 、 表示配送车辆 k 分别进行送货、取货 到达客户中心 j 的时刻； 表示车辆到达客户 i 时的承载量；xijk 表示如果车辆 k 由客户 i 驶向客 户 j，则决策变量 xijk 等于 1，否则等于 0；yik 表示如 果客户 i 由车辆 k 服务，则决策变量 yik 等于 1，否 则等于 0。 1.3.2 数学模型 以总配送成本最小为优化目标构建物流配送 优化模型如下： minZ = C1 ∑ i∈M∪N ∑ j∈M∪N ∑ k∈K xi jkti j+ C2 ∑ i∈M∪N ∑ j∈M∪N ∑ k∈K xi jk[(LT1 j −T 1 jk) + ( LT2 j −T 2 jk)]+ + C3 ∑ i∈M∪N ∑ j∈M∪N ∑ k∈K xi jk[(T 1 jk −EL1 j ) + ( T 2 jk −EL2 j )]+ + e ∑ i∈M∪N ∑ j∈M∪N ∑ k∈K xi jk [ m1di j +m2 ( α(i) 1 +α(i) 2 )] (1) s ∑.t. z∈Z ∑ i∈N f i wagon + xi jkα(j) z ⩽ Qk , k ∈ K, j ∈ N (2) ∑N¯ i=1 xi jk = yjk, ∀ j ∈ N, k ∈ K (3) ∑N¯ j=1 xi jk = yik,∀i ∈ N, k ∈ K (4) T 1 jk xi jk +α(i) 1 t ⩽ T 2 jk xi jk,∀i, j ∈ N, k ∈ K (5) T 1 jk = T 1 ik +ti j,∀ i, j ∈ N, k ∈ K (6) T 2 jk = T 2 ik +ti j, ∀ i, j ∈ N, k ∈ K (7) xi jk = 0 or 1,∀ i, j, k (8) yik = 0 or 1, ∀i, k (9) 目标式 (1) 表示使总配送成本最小，总配送成 本包括：运输成本、过早配送时间惩罚成本、过晚 配送时间惩罚成本和货损成本。其中第 2 项和 第 3 项中 x +表示 max(x，0)，意味着车辆送取过程 中到达客户的时刻如果符合时间窗要求则惩罚成 本为 0，否则早到或者晚到都会产生成本。约束 条件式 (2) 表示车辆 k 在每个客户点完成卸货或 者装货任务后车辆承载的货物量不能超过该车辆 最大装载量。约束条件式 (3)、(4) 表示对于任一 客户点，仅能有一辆车访问并离开。约束条件式 (5) 表示车辆 k 到达点 j 进行取货的时刻必须晚于 车辆 k 在点 j 完成卸货作业的时间；约束条件式 (6)、(7) 保证配送过程的连续性；约束条件式 (8)、 (9) 表示变量约束。 2 CEI&IGA 算法设计 本文所讨论的同步取送选址−路径问题首先 要解决的问题就是确定配送中心，其次是为车辆 指派配送区域并完成取送货过程中的路径优化。 为解决此问题，第 1 步通过设计综合客户间距 ·52· 智 能 系 统 学 报 第 15 卷
第1期 李冰，等：多配送中心下生鲜农产品同步取送选址一路径优化 ·53· 离、送取货的需求量、配送时间窗要求的中心评 7)令i=计1，回到2)： 估指数确定配送中心，同时根据配送量均衡原则 8)得到各个车辆服务的客户集合A{m,…, 为各车指派配送区；第2步根据第1步车辆配送 i,…,ak,m∈M,i∈N},1≤k≤M,其中ak表示车 区域的信息使用改进遗传算法完成路径优化。在 辆k负责的客户总个数。 算法设计中，基于配送区域划分信息生成车辆的 2.1.3生成初始解 初始解，此外，通过引入自适应参数的交叉、变异 首先编码，车辆k要访问同一客户点两次分 操作以及选择操作完成所有车辆路径的迭代优化。 别进行送货、取货，因此路径中某客户点会出现 2.1初始解的生成 两次。一个解中包括2a.个客户。采用特殊编码 2.1.1基于CEI的配送中心确定 方式，记X={m),…,i),…,a,m,…,),… 1)计算各客户时间窗要求相关度系数，记为 (a)}为车辆k的一个取送顺序解，解的长度记 =ET-ET引+T-LT 为2a;采用自然数进行编码，其中i)表示车辆 第1次访问客户i送货时的服务顺序，()表示车 辆第2次访问客户i取货时的服务顺序。针对车 ET-ET引+LT-LT 辆k随机生成R个长度为2a.初始解集合，记为 2)计算任意两客户间的关联度)一号两客 A={X,…,X,…,X}。 户间距离越近、时间窗要求相关度系数越大，关 2.2选择操作 联度越大。 将适应度函数定义为总配送成本最小的倒 3)计算中心评估指数n=∑，ieN,即客户 数，即y)=1/Zy),其中y代表一个路径解X。根 据式(11)计算路径解y的选择概率py)并根据轮 i评估指数，等于客户i与其他客户∫的站间关联 盘赌规则从A中选出数量为及的顺序解集合 度r之和。 H进人算法迭代中，集合H={X…,X,…,X。 4)初步确定聚类中心，根据中心评估指数分 py)计算如下： 布，当客户i的”，明显高于其他客户时，确定该客 p(y)= f(y) 户i为一个配送中心m,m∈M,但配送中心的数 R (11) 量M应小于企业拥有的车辆总数丞。 乙s1f0) 2.1.2配送区域指派 2.3交叉和变异操作 本文引入遗传参数的自适应调整策略以提高 确定配送中心后，根据距离最短原则为各车 遗传算法的收敛精度和收敛速度。迭代初期安排 指派要服务的客户集合，指派过程中保持各车辆 配送量均衡，步骤如下： 较大的p,待迭代稳定后减小Pc;对适应度大的个 1)记A,为车辆k负责的客户集合，1≤k≤ 体安排较小的P以保持其优良性，对适应度小的 M。计算在配送区域数量确定的情况下各区域的 个体给予较大的P。以加速求解。Pm同样也与迭 代数及适应度有关。如下： 平均需求量a()a()=∑a间'+la川/m。将 0.8,8≤4 M个配送中心随机依次放人客户集合A,中。 2)计算车辆k的配送量a(A),a(A)= Pcmax三 0.7, 4<8≤4 (12) ga0i+hoi1。 3 0.6, 4<8≤G 3)while i<N,a(A)≤a(④e 4)计算客户i和M个配送中心的距离，记与 0m,8e号 i距离最近的配送中心为m。将客户i放人m,所 G pmin={0.05, (13) 在的客户集合4中。 4 5)while i<N,a(A:)a(A). 0.01, 3 4<8≤G 6)根据式(10)计算客户i将要放入的客户集 合A,中，保证各客户集内的需求量均衡： Ji △S=min (10 Pemax,fi<f (14)
离、送取货的需求量、配送时间窗要求的中心评 估指数确定配送中心，同时根据配送量均衡原则 为各车指派配送区；第 2 步根据第 1 步车辆配送 区域的信息使用改进遗传算法完成路径优化。在 算法设计中，基于配送区域划分信息生成车辆的 初始解，此外，通过引入自适应参数的交叉、变异 操作以及选择操作完成所有车辆路径的迭代优化。 2.1 初始解的生成 2.1.1 基于 CEI 的配送中心确定 1) 计算各客户时间窗要求相关度系数，记为 ξi j = 1 ET1 i −ET1 j + LT1 i −LT1 j + 1 ET2 i −ET2 j + LT2 i −LT2 j ri j = ξi j di j 2) 计算任意两客户间的关联度 ，两客 户间距离越近、时间窗要求相关度系数越大，关 联度越大。 ri = ∑ f rf i 3) 计算中心评估指数 ,i ∈ N ，即客户 i 评估指数 ri 等于客户 i 与其他客户 f 的站间关联 度 rfi 之和。 M¯ K¯ 4) 初步确定聚类中心，根据中心评估指数分 布，当客户 i 的 ri 明显高于其他客户时，确定该客 户 i 为一个配送中心 m，m∈M，但配送中心的数 量 应小于企业拥有的车辆总数 。 2.1.2 配送区域指派 确定配送中心后，根据距离最短原则为各车 指派要服务的客户集合，指派过程中保持各车辆 配送量均衡，步骤如下： M¯ α ( A¯ ) α ( A¯ ) = ∑ i∈N α(i) 1 + α(i) 2 /M¯ M¯ 1) 记 Ak 为车辆 k 负责的客户集合，1≤k≤ 。计算在配送区域数量确定的情况下各区域的 平均需求量 ， 。将 个配送中心随机依次放入客户集合 Ak 中。 α(Ak) α(Ak) = ∑ i∈Ak α(i) 1 + α(i) 2 2) 计算车 辆 k 的配送量 ， 。 N¯ α(Ak) α ( A¯ ) 3) while i 。 6) 根据式 (10) 计算客户 i 将要放入的客户集 合 Ak 中，保证各客户集内的需求量均衡： ∆S k = min ∑M¯ k=1 [ α(Ak)−α(A¯) ]2 /M¯ 1/2 (10) 7) 令 i = i+1，回到 2)； m,··· i,··· M¯ 8) 得到各个车辆服务的客户集合 Ak={ , ,ak , m ∈M, i∈N }，1≤ k ≤ ，其中 ak 表示车 辆 k 负责的客户总个数。 2.1.3 生成初始解 ··· , ··· , ··· , ··· , H¯ k = { X 1 k ,··· ,X s k ,··· ,X R k } 首先编码，车辆 k 要访问同一客户点两次分 别进行送货、取货，因此路径中某客户点会出现 两次。一个解中包括 2ak 个客户。采用特殊编码 方式，记 Xk ={δ(m), δ(i), δ(ak ),Φ(m), Φ(i), Φ(ak )}为车辆 k 的一个取送顺序解，解的长度记 为 2ak；采用自然数进行编码，其中 δ(i) 表示车辆 第 1 次访问客户 i 送货时的服务顺序，Φ(i) 表示车 辆第 2 次访问客户 i 取货时的服务顺序。针对车 辆 k 随机生成 R 个长度为 2ak 初始解集合，记为 。 2.2 选择操作 H¯ k R¯ Hk = { X 1 k ,··· ,X s k ,··· ,X R¯ k } 将适应度函数定义为总配送成本最小的倒 数，即 f(y)=1/Z(y)，其中 y 代表一个路径解 Xk。根 据式 (11) 计算路径解 y 的选择概率 p(y) 并根据轮 盘赌规则从 中选出数量为 的顺序解集合 Hk 进入算法迭代中，集合 。 p(y) 计算如下： p(y) = f(y) ∑R y=1 f(y) (11) 2.3 交叉和变异操作 本文引入遗传参数的自适应调整策略以提高 遗传算法的收敛精度和收敛速度。迭代初期安排 较大的 pc，待迭代稳定后减小 pc；对适应度大的个 体安排较小的 pc 以保持其优良性，对适应度小的 个体给予较大的 pc 以加速求解。pm 同样也与迭 代数及适应度有关。如下： pcmax = 0.8, g ⩽ G 4 0.7, G 4 < g ⩽ 3G 4 0.6, 3G 4 < g ⩽ G (12) pmmin = 0.002, g ⩽ G 4 0.05, G 4 < g ⩽ 3G 4 0.01, 3G 4 < g ⩽ G (13) pci = pcmax −(pcmax − pcmin) ( g G + fi fmax − f ) , fi ⩾ f pcmax, fi < f (14) 第 1 期 李冰，等：多配送中心下生鲜农产品同步取送选址−路径优化 ·53·
·54· 智能系统学报 第15卷 迭代完成后，输出某一车辆的最优路径，继续 Pm三 生成其他车辆的初始解并进行路径优化，直至所 Pmmin,f0 eZ i.jeN 输出各车辆的 (16) 最优路径 否则 iEN (结束) 式(16)表示车辆在前往下一客户时对当前装 载量进行计算并判断是否能继续前进。当车辆剩 图2算法流程图 Fig.2 Flow of algorithm 余装载量空间不能满足下一客户的需求时，车辆 需返回其配送中心使承载量归零。同时，车辆从 3算例验证及分析 配送中心出发、完成配送任务返回配送中心。记 车辆k的配送中心为m,依次对H。中每个解 假设某物流企业有3辆车可供使用，配送车 X进行修正，除在解的前后增加m外，车辆在运 辆的单位运输费用为40元m,早到的单位损失 输途中超载也要在相应的位置加上mk,可得到 成本为C2为10元/h,晚到的单位损失成本C X={me…,)…,me…,60)%…,m}o 为20元h,车辆的最大承载量Q为50箱，生鲜产 2.5解码 品价格为400元/箱，单位货物作业时间1为0.02h/ 根据客户和编码的对应关系对自然数编码解 箱，运输过程的货损比例m1为0.01%，装卸过程 码可形成路径解，在m,处对路径进行拆分得到车 中的货损比例m2为0.03%。如表1所示，设计有 辆配送的各条子路径。计算适应度、根据轮盘赌 30个客户的实验场景，第3第4列表示客户的送 选择后继续下一次迭代。 货需求和取货需求，如表1所示。 表1实例信息 Table 1 Information of example 客户编号 坐标 送货需求号 取货需求号 送货时间窗 取货时间窗 1 (34,47) -2 6 [7,13] [13,16 2 (22,35)） -16 15 [8,13] [13,17刀 3 (2,48) -1 J [7,13] [14,16 4 (44,23) -10 3 [7,8 [14,17刀 5 (6,45) -24 17 [8.10] [14,17刀
pmi = pmmin −(pmmax − pmmin) ( g G + fi fmax − f ) , fi ⩾ f pmmin, fi Q ∑ i∈N f i wagon, 否则 (16) ,··· ,··· ,··· ,··· 式 (16) 表示车辆在前往下一客户时对当前装 载量进行计算并判断是否能继续前进。当车辆剩 余装载量空间不能满足下一客户的需求时，车辆 需返回其配送中心使承载量归零。同时，车辆从 配送中心出发、完成配送任务返回配送中心。记 车辆 k 的配送中心为 mk，依次对 Hk 中每个解 Xk 进行修正，除在解的前后增加 mk 外，车辆在运 输途中超载也要在相应的位置加上 mk，可得到 Xk={mk ,δ(i) ,mk ,δ(j) ,mk}。 2.5 解码 根据客户和编码的对应关系对自然数编码解 码可形成路径解，在 mk 处对路径进行拆分得到车 辆配送的各条子路径。计算适应度、根据轮盘赌 选择后继续下一次迭代。 迭代完成后，输出某一车辆的最优路径，继续 生成其他车辆的初始解并进行路径优化，直至所 有车辆都得到最优路径。 2.6 算法流程图 算法流程图如图 2。 开始 确定配送中心 为车辆指派配送区域 生成车辆的初始解 遗传算法迭代 自适应交叉 自适应变异 插入配送中心 染色体解码 计算适应度值 产生各子路径 输出各车辆的 最优路径 结束 N Y Y N 是否每辆车都找 到最优路径 染色体选择 是否迭代结束 图 2 算法流程图 Fig. 2 Flow of algorithm 3 算例验证及分析 假设某物流企业有 3 辆车可供使用，配送车 辆的单位运输费用为 40 元/km，早到的单位损失 成本为 C2 为 10 元/h，晚到的单位损失成本 C3 为 20 元/h，车辆的最大承载量 Q 为 50 箱，生鲜产 品价格为 400 元/箱，单位货物作业时间 t 为 0.02 h/ 箱，运输过程的货损比例 m1 为 0.01%，装卸过程 中的货损比例 m2 为 0.03%。如表 1 所示，设计有 30 个客户的实验场景，第 3 第 4 列表示客户的送 货需求和取货需求，如表 1 所示。 表 1 实例信息 Table 1 Information of example 客户编号 坐标 送货需求号 取货需求号 送货时间窗 取货时间窗 1 (34,47) −2 6 [7,13] [13,16] 2 (22,35) −16 15 [8,13] [13,17] 3 (2,48) −1 5 [7,13] [14,16] 4 (44,23) −10 3 [7,8] [14,17] 5 (6,45) −24 17 [8,10] [14,17] ·54· 智 能 系 统 学 报 第 15 卷
第1期 李冰，等：多配送中心下生鲜农产品同步取送选址-路径优化 ·55· 续表1 客户编号 坐标 送货需求号 取货需求号 送货时间窗 取货时间窗 6 (13,47) > 3 [7,13] [13,17J 7 (37,24) -6 13 [7,9] [14,16] 8 (48,30) -15 14 [8,10 [13,16] 9 (823) -16 12 [7,13] [14,16] 10 (36,7) -4 J [8,10 [13,17刀 (37,34) -13 14 [7,9 [13,16 12 (18,24) -12 f [8,8 [14,1刀 13 (47,34) -14 [6,刀 [13,16 女 (23,34) -6 > [7,9] [14,16] 15 (44,46) -2 16 [8,1 [13,16 16 (42,16) -14 14 [8,13] [14,16 少 (67,45) -12 9 [8,12] [13,17 e (21,36) -17 13 [6,9] [14,17刀 9 (86,32) -29 11 [6,9] [14,17刀 20 (45,27) -3 11 [11,14] [14,16] 21 (16,31) 3 J [8,9] [13,17刀 22 (34,45) -5 18 [6,12] [13,17刀 23 (14,10) -11 15 [7,12] [13,16 24 (34.44) -20 y [7,1 [14,17刀 25 (32,26) -5 7 [8,10] [14,16 26 (51,28) -17 13 [7,10] [14,16] 27 (34,15) -17 3 [6,9 [14,16 28 (45,35) -19 伊 [7,12] [14,16] 29 (47,12) -9 6 [6,9] [13,16] 30 (34,9) -16 7 [8,13] [13,16] 使用本文提出的CEI&IGA算法设定种群个 表车辆前往该地分别进行送货、取货，这体现了 数为200、迭代次数为160次，使用MATLAB进 本文提出的同步取送配送方式。 行编程求解。 表2路径优化结果 3.1配送区划分 Table 2 Results of path optimization 计算中心评估指数，以最大化原则利用企业 区域批次 路径 内部的3辆车并确定3个配送中心：客户7、客户 7-25-27-29-20 14、客户24。根据距离和配送均衡原则将其他客 7—26—104-27-10—8 户匹配给各配送中心形成3个配送区，如下： 37-4-26-30-18-16-25-30-16-20-29-7 A1={7,4,8,10,16,20,25,26,27,29,30}a(A1)=212 4 14-2-21-18-2-18 A2={14,2,3,5,6,9,12,18,21,23}a(42)=213 A25 14-5-2-236—21-5-18 A3={24,1,11,13,15,17,19,22,28}a(A)=214 6 149-3126—9232—12-14 3.2路径优化 24—22-11—19 各车辆配送区域的路径优化结果如表2所 A38 2417-28-11—13-17-28-1-15 示，可以看出，各子路径的开头或结束为配送中 9 2419-15-13-12-24 心。同时，同一批次中同一客户点会出现两次代
使用本文提出的 CEI&IGA 算法设定种群个 数为 200、迭代次数为 160 次，使用 MATLAB 进 行编程求解。 3.1 配送区划分 计算中心评估指数，以最大化原则利用企业 内部的 3 辆车并确定 3 个配送中心：客户 7、客户 14、客户 24。根据距离和配送均衡原则将其他客 户匹配给各配送中心形成 3 个配送区，如下： A1 = {7,4,8,10,16,20,25,26,27,29,30} α(A1) = 212 A2 = {14,2,3,5,6,9,12,18,21,23} α(A2) = 213 A3 = {24,1,11,13,15,17,19,22,28} α(A3) = 214 3.2 路径优化 各车辆配送区域的路径优化结果如表 2 所 示，可以看出，各子路径的开头或结束为配送中 心。同时，同一批次中同一客户点会出现两次代 表车辆前往该地分别进行送货、取货，这体现了 本文提出的同步取送配送方式。 表 2 路径优化结果 Table 2 Results of path optimization 区域批次 路径 A1 1 7—25—27—29—20 2 7—26—10—4—27—10—8 3 7—4—26—30—18—16—25—30—16—20—29—7 A2 4 14—2—21—18—2—18 5 14—5—2—23—6—21—5—18 6 14—9—3—12—6—9—23—2—12—14 A3 7 24—22—11—19 8 24—17—28—11—13—17—28—1—15 9 24—19—15—13—12—24 续表 1 客户编号 坐标 送货需求号 取货需求号 送货时间窗 取货时间窗 6 (13,47) −7 3 [7,13] [13,17] 7 (37,24) −6 13 [7,9] [14,16] 8 (48,30) −15 14 [8,10] [13,16] 9 (8,23) −16 12 [7,13] [14,16] 10 (36,7) −4 5 [8,10] [13,17] 11 (37,34) −13 14 [7,9] [13,16] 12 (18,24) −12 8 [8,8] [14,17] 13 (47,34) −14 4 [6,7] [13,16] 14 (23,34) −6 7 [7,9] [14,16] 15 (44,46) −2 16 [8,11] [13,16] 16 (42,16) −14 14 [8,13] [14,16] 17 (67,45) −12 9 [8,12] [13,17] 18 (21,36) −17 13 [6,9] [14,17] 19 (86,32) −29 11 [6,9] [14,17] 20 (45,27) −3 11 [11,14] [14,16] 21 (16,31) −3 5 [8,9] [13,17] 22 (34,45) −5 18 [6,12] [13,17] 23 (14,10) −11 15 [7,12] [13,16] 24 (34,44) −20 2 [7,11] [14,17] 25 (32,26) −5 7 [8,10] [14,16] 26 (51,28) −17 13 [7,10] [14,16] 27 (34,15) −17 3 [6,9] [14,16] 28 (45,35) −19 18 [7,12] [14,16] 29 (47,12) −9 6 [6,9] [13,16] 30 (34,9) −16 7 [8,13] [13,16] 第 1 期 李冰，等：多配送中心下生鲜农产品同步取送选址−路径优化 ·55·
·56· 智能系统学报 第15卷 各配送区内配送费用计算结果见表3，各车 3.3取送分离与同步取送对比 辆的路径优化收敛结果见图3，因为a1>a2>a,所 取送分离方式下车辆统一送完货物后再进行 以车辆1负责的配送区域A,产生的配送费用要 取货，各批路线中配送性质相同，而本文提出的 大于其他两个配送区域。 同步取送方式中各批配送性质不同。基于此，采 表3配送费用 用本文的实例及算法，针对3辆车在各自的配送 Table 3 Distribution costs 区域以同步取送和取送分离的配送模式进行路径 配送区配送成本 运输费用时间惩罚费用 货损费用 优化。取送分离优化后的路径结果如表4所示， A 2388.33 1897.20 181.32 309.81 优化后两种方式产生的路径数及各费用对比如 A 1789.44 1365.87 123.75 299.82 表5所示。 A 1719.35 1299.04 115.6 304.71 从表4可看出，取送分离模式下路径数比较 多且因为车辆容量约束的限制，部分路径总装载 3200 量很少，造成了车辆利用率低的问题。从表5可 3000 以看出，在同步取送模式下，路径数量大大减少， 2800 1R2600 车辆1 配送费用减少了13.71%。各费用降低验证了本 文提出同步取送方式对车辆利用的有效性。 2200 车辆2 3.4算法对比 车辆3 在实验中保持控制参数不变，使用本文实例 1600 1400 以及31中配送区域划分信息，使用传统遗传算 120 0 20406080100120140160 法与本文提出的改进遗传算法进行3辆车在各自 迭代次数 配送区域的路径优化。3组实验对比中，每组实 图3车辆路径优化迭代结果 验对应各个车辆在两个算法运行下的寻优迭代 Fig.3 Iterative results of vehicle routing optimization 过程。 表4取送分离优化结果 Table 4 Optimized result of separate pick-up and delivery 区域 性质 批次 路径 装载量 A 送 1 7-25-27-29-10-8 % A 送 2 74-20-26—30 46 A 送 3 7-167 14 A 取 4 7-2529-26-20 37 A 取 5 7-8-16—27-4—10-307 46 送 6 24—186-3—23 47 送 7 24-9-12-2-21 24 送 8 24-5-24 g 取 9 24-2-5-23-36 45 A 取 10 24-9-12-18-21-24 % 送 11 24-22-19-28 43 送 12 24-11-13-1-17-15-24 49 A 取 13 24-1-11-13-15-17 49 A 取 14 24-19-22 ) As 取 15 24-28-24 5
各配送区内配送费用计算结果见表 3，各车 辆的路径优化收敛结果见图 3，因为 a1>a2>a3，所 以车辆 1 负责的配送区域 A1 产生的配送费用要 大于其他两个配送区域。 表 3 配送费用 Table 3 Distribution costs 配送区 配送成本 运输费用 时间惩罚费用 货损费用 A1 2 388.33 1 897.20 181.32 309.81 A2 1 789.44 1 365.87 123.75 299.82 A3 1 719.35 1 299.04 115.6 304.71 0 20 40 60 80 100 120 140 160 1 200 1 400 1 600 1 800 2 000 2 200 2 400 2 600 2 800 3 000 3 200 迭代次数 总配送成本/元 车辆1 车辆2 车辆3 图 3 车辆路径优化迭代结果 Fig. 3 Iterative results of vehicle routing optimization 3.3 取送分离与同步取送对比 取送分离方式下车辆统一送完货物后再进行 取货，各批路线中配送性质相同，而本文提出的 同步取送方式中各批配送性质不同。基于此，采 用本文的实例及算法，针对 3 辆车在各自的配送 区域以同步取送和取送分离的配送模式进行路径 优化。取送分离优化后的路径结果如表 4 所示， 优化后两种方式产生的路径数及各费用对比如 表 5 所示。 从表 4 可看出，取送分离模式下路径数比较 多且因为车辆容量约束的限制，部分路径总装载 量很少，造成了车辆利用率低的问题。从表 5 可 以看出，在同步取送模式下，路径数量大大减少， 配送费用减少了 13.71%。各费用降低验证了本 文提出同步取送方式对车辆利用的有效性。 3.4 算法对比 在实验中保持控制参数不变，使用本文实例 以及 3.1 中配送区域划分信息，使用传统遗传算 法与本文提出的改进遗传算法进行 3 辆车在各自 配送区域的路径优化。3 组实验对比中，每组实 验对应各个车辆在两个算法运行下的寻优迭代 过程。 表 4 取送分离优化结果 Table 4 Optimized result of separate pick-up and delivery 区域 性质 批次 路径 装载量 A1 送 1 7—25—27—29—10—8 50 A1 送 2 7—4—20—26—30 46 A1 送 3 7—16—7 14 A1 取 4 7—25—29—26—20 37 A1 取 5 7—8—16—27—4—10—30—7 46 A2 送 6 24—18—6—3—23 47 A2 送 7 24—9—12—2—21 24 A2 送 8 24—5—24 44 A2 取 9 24—2—5—23—3—6 45 A2 取 10 24—9—12—18—21—24 40 A3 送 11 24—22—19—28 43 A3 送 12 24—11—13—1—17—15—24 49 A3 取 13 24—1—11—13—15—17 49 A3 取 14 24—19—22 47 A3 取 15 24—28—24 5 ·56· 智 能 系 统 学 报 第 15 卷
第1期 李冰，等：多配送中心下生鲜农产品同步取送选址一路径优化 ·57· 表5不同配送方式费用对比 实验结果如图4所示，优化后的算法能够在 Table 5 Cost comparison of different distribution modes 更短的时间内得到全局最优解。两种算法在寻 配送方式路径数总成本 运输费惩罚费货损费 找3次最优路径的计算机总运行时间对比详见 取送分离 6884.794881.111003.69949.22 表6，改进后的遗传算法寻优效率更高，能够更快 同步取送 9 5897.124331.9 420.67914.34 找到最优路径。 改进率% 14.3 13.71 6.55 58 3.6 3400 2400 2400 3300 2300 2300 尺3200， 3100 39 s389 册 3000 2000 2900 1900 1900 2800 1800 1800 2700 1700 1700 2600 1600 1600 2500 1500 100 2400 1400 1400 0 20406080100120140160 020406080100120140160 0 20406080100120140160 迭代次数 迭代次数 迭代次数 (a)车辆1 (b)车辆2 (c)车辆3 图4两种算法的收敛过程 Fig.4 Convergence process (IGA and GA) 表6传统遗传算法和改进遗传算法性能对比 MIAO Xiaohong,ZHOU Xinnian,LIN Sen,et al.Study on Table 6 Performance comparison between traditional ge- routing optimization for cold-chain logistics distribution of netic algorithm and improved genetic algorithm 3PL[J].Operations research and management science, 算法 总配送成本 运行时间s 2011.20(4):32-38. [2]吴瑶，马祖军.时变路网下带时间窗的易腐食品生产配 传统遗传算法 5621.23 69.632 送问题).系统工程理论与实践，2017,371)：172-181. 改进遗传算法 5326.63 60.632 WU Yao,MA Zujun.Time-dependent production-delivery problem with time windows for perishable foods[J].Sys- 4结束语 tems engineering-theory practice,2017,37(1):172-181. [3]HSIAO Y H,CHEN Muchen,CHIN C L.Distribution 针对传统生鲜产品选址-路径优化未考虑客 planning for perishable foods in cold chains with quality 户的取送双向需求以及取送分离配送模式下对车 concerns:formulation and solution procedure[].Trends in 辆利用不足、配送费用较高等问题，提出将多配 food science technology,2017,61:80-93. 送中心和取送同步结合的车辆同步取送机制。同 [4]王淑云，孙虹.随机需求下冷链品多温共配路径优化研 步取送模式下，车辆在配送路径中可以既送货又 究[).工业工程与管理，2016,21(2)：49-58 取货。最后通过对比取送分离及同步取送两种配 WANG Shuyun,SUN Hong.Optimization of multi-tem- 送模式的路径数、运输费用、时间惩罚费用及货 perature joint distribution with stochastic demands[J].In- 损费用证明了本文提出的同步取送的合理性及有 dustrial engineering and management,2016,21(2):49-58. 效性，同时也将本文提出的算法与传统遗传算进 [5]鲍春玲，张世斌.考虑碳排放的冷链物流联合配送路径 行对比，验证了算法改进的有效性。 优化).工业工程与管理，2018,23(5)95-100,107 本文对选址问题采取了为车辆分派区域的方 BAO Chunling,ZHANG Shibin.Route optimization of cold chain logistics in joint distribution:with considera- 式解决，在对车辆的利用上有一定局限，可在选 tion of carbon emission[J.Industrial engineering and man- 址问题上采用联合配送的方式，使车辆可回到任 agement,2018,23(5):95-100,107. 意配送中心继续配送，同时目标函数可以考虑低 [6]陈绍洵，兰洪杰.基于双层规划的生鲜自提柜节点选址 碳成本来更好优化生鲜农产品的物流配送。 研究U.工业工程与管理，2018,23(6：57-63 参考文献： CHEN Shaoxun,LAN Hongjie.Location of fresh product self-collection cabinet based on bi-level programming[J]. [1]缪小红，周新年，林森，等.第3方冷链物流配送路径优 Industrial engineering and management,2018,23(6): 化研究U.运筹与管理，2011,20(4)：32-38. 57-63
实验结果如图 4 所示，优化后的算法能够在 更短的时间内得到全局最优解。两种算法在寻 找 3 次最优路径的计算机总运行时间对比详见 表 6，改进后的遗传算法寻优效率更高，能够更快 找到最优路径。 1 400 1 500 1 600 1 700 1 800 1 900 2 000 2 100 2 200 2 300 2 400 总配送成本/元 0 20 40 60 80 100 120 140 160 迭代次数 (c)车辆3 GA IGA 1 400 1 500 1 600 1 700 1 800 1 900 2 000 2 100 2 200 2 300 2 400 总配送成本/元 0 20 40 60 80 100 120 140 160 迭代次数 (b)车辆2 GA IGA 2 400 2 500 2 600 2 700 2 800 2 900 3 000 3 100 3 200 3 300 3 400 总配送成本/元 0 20 40 60 80 100 120 140 160 迭代次数 (a)车辆1 GA IGA 图 4 两种算法的收敛过程 Fig. 4 Convergence process (IGA and GA) 表 6 传统遗传算法和改进遗传算法性能对比 Table 6 Performance comparison between traditional genetic algorithm and improved genetic algorithm 算法 总配送成本 运行时间/s 传统遗传算法 5 621.23 69.632 改进遗传算法 5 326.63 60.632 4 结束语 针对传统生鲜产品选址−路径优化未考虑客 户的取送双向需求以及取送分离配送模式下对车 辆利用不足、配送费用较高等问题，提出将多配 送中心和取送同步结合的车辆同步取送机制。同 步取送模式下，车辆在配送路径中可以既送货又 取货。最后通过对比取送分离及同步取送两种配 送模式的路径数、运输费用、时间惩罚费用及货 损费用证明了本文提出的同步取送的合理性及有 效性，同时也将本文提出的算法与传统遗传算进 行对比，验证了算法改进的有效性。 本文对选址问题采取了为车辆分派区域的方 式解决，在对车辆的利用上有一定局限，可在选 址问题上采用联合配送的方式，使车辆可回到任 意配送中心继续配送，同时目标函数可以考虑低 碳成本来更好优化生鲜农产品的物流配送。 参考文献： 缪小红, 周新年, 林森, 等. 第 3 方冷链物流配送路径优 化研究 [J]. 运筹与管理, 2011, 20(4): 32–38. [1] MIAO Xiaohong, ZHOU Xinnian, LIN Sen, et al. Study on routing optimization for cold-chain logistics distribution of 3PL[J]. Operations research and management science, 2011, 20(4): 32–38. 吴瑶, 马祖军. 时变路网下带时间窗的易腐食品生产-配 送问题 [J]. 系统工程理论与实践, 2017, 37(1): 172–181. WU Yao, MA Zujun. Time-dependent production-delivery problem with time windows for perishable foods[J]. Systems engineering-theory & practice, 2017, 37(1): 172–181. [2] HSIAO Y H, CHEN Muchen, CHIN C L. Distribution planning for perishable foods in cold chains with quality concerns: formulation and solution procedure[J]. Trends in food science & technology, 2017, 61: 80–93. [3] 王淑云, 孙虹. 随机需求下冷链品多温共配路径优化研 究 [J]. 工业工程与管理, 2016, 21(2): 49–58. WANG Shuyun, SUN Hong. Optimization of multi-temperature joint distribution with stochastic demands[J]. Industrial engineering and management, 2016, 21(2): 49–58. [4] 鲍春玲, 张世斌. 考虑碳排放的冷链物流联合配送路径 优化 [J]. 工业工程与管理, 2018, 23(5): 95–100, 107. BAO Chunling, ZHANG Shibin. Route optimization of cold chain logistics in joint distribution: with consideration of carbon emission[J]. Industrial engineering and management, 2018, 23(5): 95–100, 107. [5] 陈绍洵, 兰洪杰. 基于双层规划的生鲜自提柜节点选址 研究 [J]. 工业工程与管理, 2018, 23(6): 57–63. CHEN Shaoxun, LAN Hongjie. Location of fresh product self-collection cabinet based on bi-level programming[J]. Industrial engineering and management, 2018, 23(6): 57–63. [6] 表 5 不同配送方式费用对比 Table 5 Cost comparison of different distribution modes 配送方式 路径数 总成本 运输费 惩罚费 货损费 取送分离 15 6 884.79 4 881.11 1 003.69 949.22 同步取送 9 5 897.12 4 331.9 420.67 914.34 改进率% 14.3 13.71 6.55 58 3.6 第 1 期 李冰，等：多配送中心下生鲜农产品同步取送选址−路径优化 ·57·
·58· 智能系统学报 第15卷 [7]肖建华，王飞，白焕新，等.基于非等覆盖半径的生鲜农 2015,22(3:314-329 产品配送中心选址[J.系统工程学报，2015,30(3)： [16]王道平，徐展，杨岑.基于两阶段启发式算法的物流配 406-416. 送选址-路径问题研究.运筹与管理，2017,26(4)： XIAO Jianhua,WANG Fei,BAI Huanxin,et al.Location 70-75,83 of distribution centers for fresh agricultural products based WANG Daoping,XU Zhan,YANG Cen.Study on loca- on non-equal coverage radius[J].Journal of systems engin- tion-routing problem of logistics distribution based on eering,2015,30(3):406-416. two-stage heuristic algorithm[J.Operations research and [8]狄卫民，岳耀雪，陈国民.有配送能力限制的易腐农产品 management science,2017,26(4):70-75,83. 配送中心选址方法.计算机应用研究，2013,30(1)： [17刀黄凯明，卢才武，连民杰.多层级设施选址-路径规划问 202-205 题建模及算法[J].控制与决策，2017,32(10)： DI Weimin,YUE Yaoxue,CHEN Guomin.Capacitated 1803-1809. distribution center location approach for perishable agricul- HUANG Kaiming,LU Caiwu,LIAN Minjie.Modeling tural product[J].Application research of computers,2013, and algorithm for multi-echelon location-routing 30(1):202-205 problem[J].Control and decision,2017,32(10): [9]DEMIR E.BEKTAS T,LAPORTE G.A review of recent 1803-1809. research on green road freight transportation[J].European [18]黄凯明，卢才武，连民杰.三层级设施选址-路径规划问 journal of operational research,2014,237(3):775-793. 题建模及算法研究].系统工程理论与实践，2018， [10]张春苗，赵燕伟，张景玲，等.低碳定位一车辆路径问 38(3743-754. 题).计算机集成制造系统，2017,23(12)：2768-2777. HUANG Kaiming,LU Caiwu,LIAN Minjie.Research on ZHANG Chunmiao,ZHAO Yanwei,ZHANG Jingling,et modeling and algorithm for three-echelon location-rout- al.Location and routing problem with minimizing ing problem[J].Systems engineering-theory practice, carbon[J].Computer integrated manufacturing systems, 2018,38(3)743-754. 2017,23(12:2768-2777. [19]张晓楠，范厚明，李剑锋.变动补偿的多模糊选址-路径 [11]王琪瑛，李英，李惠.带软时间窗的电动车换电站选址 路径问题研究[J.工业工程与管理，2019,24(3)： 机会约束模型及算法[).系统工程理论与实践，2016， 36(2)少：442-453. 99-106. WANG Qiying,LI Ying,LI Hui.Battery swap station ZHANG Xiaonan,FAN Houming,LI Jianfeng.Chance- constrained model and algorithm for LRP with multiple location-routing problem of electric vehicles with soft time windows[J].Industrial engineering and management, fuzzy variables under change-reward[J].Systems engin- 2019.24(3:99-106. eering-theory practice,2016,36(2):442-453. [12]邱晗光，李海南，宋寒.需求依赖末端交付与时间窗的 [20]冀巨海，张璇.考虑取送作业的生鲜农产品配送路径优 城市配送自提柜选址一路径问题.计算机集成制造 化模型与算法).系统科学学报，2019,27(1)少：130-135. 系统，2018,24(10)：2612-2621. JI Juhai,ZHANG Xuan.Optimization model and al- QIU Hanguang,LI Hainan,SONG Han.Reception box gorithm of the vehicle routing problem of perishable food locating-vehicle routing problems in urban distribution with pickup and delivery[J].Journal of systems science, considering demand depending on last-mile delivery and 2019,27(1):130-135 time slots[J].Computer integrated manufacturing systems, 作者简介： 2018,24(10):2612-2621. 李冰，教授，博士，主要研究方向 [13]YU V F,LIN S W,LEE W,et al.A simulated annealing 为物流优化与控制。 heuristic for the capacitated location routing problem[J]. Computers industrial engineering,2010,58(2): 288-299. [14]GHEZAVATI V,MORAKABATCHIAN S.Application of a fuzzy service level constraint for solving a multi-ob- jective location-routing problem for the industrial hazard- 党佳俊，硕士研究生，主要研究方 ous wastes[J].Journal of intelligent fuzzy systems, 向为运输组织优化与控制。 2015,28(5):2003-2013. [15]LIU J,KACHITVICHYANUKUL V.A Pareto-based particle swarm optimization algorithm for multi-objective location routing problem[J].International journal of in- dustrial engineering:theory,applications and practice
肖建华, 王飞, 白焕新, 等. 基于非等覆盖半径的生鲜农 产品配送中心选址 [J]. 系统工程学报, 2015, 30(3): 406–416. XIAO Jianhua, WANG Fei, BAI Huanxin, et al. Location of distribution centers for fresh agricultural products based on non-equal coverage radius[J]. Journal of systems engineering, 2015, 30(3): 406–416. [7] 狄卫民, 岳耀雪, 陈国民. 有配送能力限制的易腐农产品 配送中心选址方法 [J]. 计算机应用研究, 2013, 30(1): 202–205. DI Weimin, YUE Yaoxue, CHEN Guomin. Capacitated distribution center location approach for perishable agricultural product[J]. Application research of computers, 2013, 30(1): 202–205. [8] DEMIR E, BEKTAŞ T, LAPORTE G. A review of recent research on green road freight transportation[J]. European journal of operational research, 2014, 237(3): 775–793. [9] 张春苗, 赵燕伟, 张景玲, 等. 低碳定位—车辆路径问 题 [J]. 计算机集成制造系统, 2017, 23(12): 2768–2777. ZHANG Chunmiao, ZHAO Yanwei, ZHANG Jingling, et al. Location and routing problem with minimizing carbon[J]. Computer integrated manufacturing systems, 2017, 23(12): 2768–2777. [10] 王琪瑛, 李英, 李惠. 带软时间窗的电动车换电站选址 路径问题研究 [J]. 工业工程与管理, 2019, 24(3): 99–106. WANG Qiying, LI Ying, LI Hui. Battery swap station location-routing problem of electric vehicles with soft time windows[J]. Industrial engineering and management, 2019, 24(3): 99–106. [11] 邱晗光, 李海南, 宋寒. 需求依赖末端交付与时间窗的 城市配送自提柜选址—路径问题 [J]. 计算机集成制造 系统, 2018, 24(10): 2612–2621. QIU Hanguang, LI Hainan, SONG Han. Reception box locating-vehicle routing problems in urban distribution considering demand depending on last-mile delivery and time slots[J]. Computer integrated manufacturing systems, 2018, 24(10): 2612–2621. [12] YU V F, LIN S W, LEE W, et al. A simulated annealing heuristic for the capacitated location routing problem[J]. Computers & industrial engineering, 2010, 58(2): 288–299. [13] GHEZAVATI V, MORAKABATCHIAN S. Application of a fuzzy service level constraint for solving a multi-objective location-routing problem for the industrial hazardous wastes[J]. Journal of intelligent & fuzzy systems, 2015, 28(5): 2003–2013. [14] LIU J, KACHITVICHYANUKUL V. A Pareto-based particle swarm optimization algorithm for multi-objective location routing problem[J]. International journal of industrial engineering: theory, applications and practice, [15] 2015, 22(3): 314–329. 王道平, 徐展, 杨岑. 基于两阶段启发式算法的物流配 送选址-路径问题研究 [J]. 运筹与管理, 2017, 26(4): 70–75, 83. WANG Daoping, XU Zhan, YANG Cen. Study on location-routing problem of logistics distribution based on two-stage heuristic algorithm[J]. Operations research and management science, 2017, 26(4): 70–75, 83. [16] 黄凯明, 卢才武, 连民杰. 多层级设施选址-路径规划问 题建模及算法 [J]. 控制与决策, 2017, 32(10): 1803–1809. HUANG Kaiming, LU Caiwu, LIAN Minjie. Modeling and algorithm for multi-echelon location-routing problem[J]. Control and decision, 2017, 32(10): 1803–1809. [17] 黄凯明, 卢才武, 连民杰. 三层级设施选址-路径规划问 题建模及算法研究 [J]. 系统工程理论与实践, 2018, 38(3): 743–754. HUANG Kaiming, LU Caiwu, LIAN Minjie. Research on modeling and algorithm for three-echelon location-routing problem[J]. Systems engineering-theory & practice, 2018, 38(3): 743–754. [18] 张晓楠, 范厚明, 李剑锋. 变动补偿的多模糊选址-路径 机会约束模型及算法 [J]. 系统工程理论与实践, 2016, 36(2): 442–453. ZHANG Xiaonan, FAN Houming, LI Jianfeng. Chanceconstrained model and algorithm for LRP with multiple fuzzy variables under change-reward[J]. Systems engineering-theory & practice, 2016, 36(2): 442–453. [19] 冀巨海, 张璇. 考虑取送作业的生鲜农产品配送路径优 化模型与算法 [J]. 系统科学学报, 2019, 27(1): 130–135. JI Juhai, ZHANG Xuan. Optimization model and algorithm of the vehicle routing problem of perishable food with pickup and delivery[J]. Journal of systems science, 2019, 27(1): 130–135. [20] 作者简介： 李冰，教授，博士，主要研究方向 为物流优化与控制。 党佳俊，硕士研究生，主要研究方 向为运输组织优化与控制。 ·58· 智 能 系 统 学 报 第 15 卷