基于聚类-粒子群算法的冷链物流配送中心选址分析.pdf

收稿日期：作者简介：徐超毅（），男，河南上蔡人，副教授，博士，主要研究方向为绿色物流。基于聚类 粒子群算法的冷链物流配送中心选址分析徐超毅，刘涛（安徽理工大学 经济与管理学院，安徽 淮南 ）摘要：针对冷链市场需求不断扩大，冷链物流产业却无法快速升级的情况，终端配送企业为了提高企业效益，需要在保证满足客户需求的同时，构建以成本最小化为目标的冷链配送中心选址模型。为解决上述问题，首先使用 聚类算法对未知形状、未知特征的需求点进行处理，确保配送中心选址在空间分布上的合理性，同时降低运算难度；其次引入反向搜索、变异和交叉策略对传统粒子群算法（）进行改进，使用改进粒子群算法（）对模型进行求解。相关实例分析结果表明，使用 算法的选址总成本相比 算法减少 ，迭代次数相比减少 ，验证了 算法可以得到质量更高的解，有效节省了选址成本。关键词：物流配送中心选址；聚类算法；改进粒子群算法；成本最小化中图分类号：文献标识码：文章编号：（）：，（，）：，（），（），：；引言近年来，我国冷链物流市场需求不断增长，从而推动冷链物流迅速发展，但仍存在着许多卡口问题，冷链物流配送效率仍然不尽如人意。年底，国务院发布了“十四五”冷链物流发展规划，明确提出了要打造“”冷链物流运行体系，并且构建“四横四纵”的国家冷链物流骨干通道网络。我国的冷第 卷第 期 黄河科技学院学报 年 月 链物流体系与发达国家相比还有较大差距，资源综合利用率较低，因此在冷链物流产业无法快速升级、损耗率难以下降的情况下，基于需求量的合理配送中心选址是建成高效畅通的冷链物流网络的关键条件。国内外多名学者对于各种条件下的冷链物流配送中心选址问题分别运用不同的启发式算法进行求解和优化，其中有很多创新点及方法值得学习和借鉴，填补了此类问题研究领域的许多空白。等 构建了基于进化算法的两层优化模型以解决供应地和配送中心双决策主体的选址问题；等 运用混合粒子群算法对配送中心选址模型进行优化，提高配送效率的同时降低了物流成本。王勇等 提出了应用 方法来确定聚类中心位置，然后通过 法来选出配送中心位置；孟军 通过引入基于控制因子的非线性惯性权重和遗传算法中的交叉变异策略对飞蛾优化算法进行改进，从而对农业物流配送中心选址模型进行优化；计莹峰等 考虑了以满足客户对货物完好量需求的三级货损成本下的冷链物流配送中心选址模型；刘琳等 提出了在新鲜度限制条件下的双层目标规划模型，并证实不同新鲜度要求对配送中心的选址有明显改变；袁群等 构造了一种基于遗传算法和禁忌搜索算法相结合的、并用贪婪算法改进交叉算子的混合遗传算法对模型进行求解；陈淑童等 考虑到冷链物流的特殊性，构建了同时考虑时效和货损的选址模型，对冷链物流网络建设具有实际意义。由于选址目标地区的需求点数量众多，同时需求点各指标之间区别较大，因此首先需要利用 聚类分析对目标地区需求点进行区域划分 ，然后基于聚类结果确定配送中心数量以及各区域所包含的需求点，降低后续求解冷链物流配送中心选址模型的复杂性，同时确保冷链配送中心选址地点在空间上的合理性。最后运用 算法对以最小总成本为目标的江苏省农产品冷链物流配送中心选址模型进行迭代求解，为实际解决冷链物流配送中心选址问题提供一定程度上的建议。研究方法及模型构建 聚类算法 与 最早提出 算法（均值漂移算法），随后 为 算法定义了核函数并增加了权重系数，扩大了算法的适用范围。算法基本思想是基于核函数密度估计，假设所有特征数据具有不同的概率分布，将特征数据不断进行自适应函数迭代计算，某一特征数据将会在规定半径的圆中向概率密度最大的点平滑收敛，从而得出概率密度分布的局部极值点，收敛到同一极值点的数据可以作为同一簇。算法的数据不需要标签，也不需要事先将数据进行分类，因此更擅长处理任意形状的簇类。相比于 算法，算法不需要进行样本初始化，算法结果更加稳定。算法的核密度估计根据带宽的设置而变化，带宽设置过小，收敛越慢从而导致聚类结果簇类过多；反之，设置过大，收敛太快会丢失大量数据导致簇类过少。在处理区域内冷链物流配送中心选址时，由于区域城市群的多中心化，随机性，因此聚类的个数未知，从而选择 聚类算法来解决冷链物流配送中心选址点的初步确定，聚类结果的每个簇类只拥有一个配送中心。假设存在一个大小为 的 维数据集 ，核函数 的带宽为参数 。数据集的核密度估计：（）()（）其中 （）是径向对称函数，定义满足核函数条件的 （）（）（）其中系数 是归一化常数，使 （）的积分等于 。根据式（）和式（），得到核密度估计的梯度为：（）（）()()()()（）其中 （）（），第一项为实数值，所以第二项的向量方向与梯度方向一致，第二项的表达式为：（）()()（）黄河科技学院学报由上可知，算法基本流程为：（）计算每个样本的均值漂移向量（）（）将每个样本点进行平移，即（）（）（）重复步骤 和 ，直到样本点收敛，将收敛到相同点的样本归为同一簇类，即（）（）算法粒子群算法（，）最早是基于鸟群寻找最佳觅食区域过程而提出的一种智能算法。鸟群在觅食过程中，所有个体均处于随机位置，觅食目标也同样未知，并且每只个体的移动方向也是随机的。随着时间的推移，不同的个体在觅食过程中可以互相学习、共享信息，从而判断当下所处觅食点是否为最优。鸟群中的每个个体可用粒子代表，粒子有两个属性分别是位置 和速度 ，每个个体在某位置能够觅食成功的概率可以通过适应值来表示，所有个体都能记住当前觅食位置，并找到局部最优，记为当前粒子的极值。基于信息共享，所有粒子共同向群体更新自己当前个体极值，随着觅食时间与次数不断更新迭代，粒子群将会不断调整当前位置和速度，向全局最优的位置不断逼近。假设搜索空间为 维，由 个粒子组成的总群为 （，），第 个粒子位置向量表示为（，），每个粒子都代表一个潜在解；单个粒子 历史中的最优位置为（，），为群体的最优位置，即所有（，）中的最优位置；第 个粒子的位置变化率（速度）为向量（，），则每个粒子的速度和位置变化如下公式：，（，）（，）（），（）式（）中，为惯性权重；，为加速因子；，为 ，之间相互独立的两个随机数；，、，为第 次迭代的速度和位置。传统 算法求最优解是通过不断搜索空间中个体和群体的极值来完成的，但是随着运算的进行，粒子群在空间内不断移动，靠近粒子的相似性越来越大，造成局部搜索能力较差，所以很难跳出局部最优解。同时算法的搜索精度不够高，容易错失全局最优解。因此，本文将反向搜索和变异交叉策略引入算法，扩大搜索范围，提高搜索精度，从而更快更精准得逼近全局最优解。（）反向搜索策略反向搜索策略是同时考虑当前位置得解和相反方向的解得策略，能扩大搜索范围，从而使解更容易从局部最优中跳脱出来。（）（）若粒子位置超出范围则重新初始化粒子的范围。，（）（）（）变异和交叉策略变异操作：，（，）（）式（）中，为变异向量；为缩放因子；，为 ，之间不相等的两个随机数。交叉操作：，或，其他（）式（）中，为试探向量 的第 维；为交叉概率。若均是可行解，则使粒子搜索方向更新为目标值相对更优的区域；若一个为可行解，一个为不可行解，则使粒子搜索方向更新为可行解的区域；若均为不可行解，则使粒子搜索方向更新为约束越界值相对更小的区域。选址模型构建问题描述：农产品冷链物流损耗率与产地管理、仓储、配送等多个物流环节有关，对于终端企业而言，上游环节损耗率难以控制，因此在区域内建立合理的冷链物流配送中心能够优化配送路径，最容易节约成本，提高企业效益。本模型是以成本最小化为目标而构建，研究配送中心到需求点的冷链产品供应问题。模型包括冷链配送中心到需求点的运输成本，冷链配送中心的建设成本和管理成本。相较于普通物流的运输模式，冷链运输成本中还需要考虑额外的制冷能耗。已知区域内需求点有 个，同时从 个需求点中选取 个冷链物流配送中心，冷链物流配送中心数量 由聚类结果确定（），确保在空间分布上的合理。基本假设如下：需求点位置已知，只选取部分需求点建立配送中心；配送中心只由总库进行配送，总库承担区域冷链物流配送中心功能，总库所在区域无须另选其他配送中心；配送中心只向需求点配送，每个需求点只能徐超毅，等：基于聚类 粒子群算法的冷链物流配送中心选址分析由一个配送中心配送；已知各需求点的需求量且互不影响；冷链物流运输中只考虑额外的制冷能耗成本，且制冷能耗系数恒定；各个节点的运输效率和运输费率相同，具体费率参考市场价格。本文构建的数学模型如下：（）运输成本在考虑冷链物流配送中心选址时，运输成本最能体现选址是否更合适。本模型的运输成本包括由总库到冷链物流配送中心的运输费用、由配送中心到需求点的配送运输费用以及在冷链运输过程中产生的较高的制冷能耗成本。运输费用为配送活动双方的货运量、运输距离、单位运价三者的乘积，制冷能耗成本为配送活动双方货运量、运输距离、制冷能耗系数的乘积。（）式（）中，为选址方案的总运输成本；为总库到配送中心的每吨公里运费；为总库到配送中心的距离；为总库到配送中心的货运量；为需求点到其对应配送中心的每吨公里运费；为需求点到其对应配送中心的距离；为配送中心到需求点的货运量；为每吨公里的制冷能耗成本系数；为 变量，值为 表示在 点建立冷链物流配送中心；为 变量，值为 表示 需求点由 配送中心进行配送。（）建设成本冷链物流配送中心由于对制冷条件有要求，仓库需要有额外的制冷功能，因此在建设初期资金投入较大。同时，建设成本也与所处城市的地价、区域内总需求量有关。区域内农产品冷链产品的需求量越高，所需冷链物流配送中心的规模越大。模型的总建设成本为 个冷链配送中心成本的总和：（）（）（）（）（）式（）中，为选址方案的总建设成本；为冷链物流配送中心固定建设成本；为配送中心选址点所在城市的建设单价；为配送中心 的区域总货运量；为区域总货运量对冷链物流配送中心面积的转化系数；为配送中心的年折旧率；为预计净残值率；为预计使用年限。（）管理成本冷链物流配送中心的管理成本由员工薪资、水电成本、日常开销等部分组成，需要调研配送中心所在地区实际情况计算。（）式（）中，为选址方案的总管理成本；为各冷链物流配送中心的管理费用。（）基于费用最小化的冷链物流配送中心选址模型为：（）（）约束条件：当冷链物流配送中心 被选中才能向其区域内所有需求点配送，否则不配送：，（，；，）（）需求点 只由其区域内被选中冷链物流配送中心配送：，（，）（）冷链物流配送中心数量为 个：（）每个冷链物流配送中心需要配送其区域内所有需求点，需求点数量大于等于 ：，（，）（）总库到冷链物流配送中心的货运量等于该配送中心区域内所有需求点的需求量：，（，）（）实例研究和分析 数据概况为验证模型的合理性和实用性，本文以江苏省农产品冷链需求为例，冷链物流企业总库位于盐城（）。盐城地区农业总产值居于全省第一位，同时各品类农产品物优价廉，考虑到江苏人口密集，总产值高，消费能力巨大，因此企业计划在江苏省建立若干个农产品冷链物流配送中心，构建江苏省内的冷链物流网络。企业考虑到人口数量、经济环境、交通运输等因素，冷链物流配送中心将在已选定的 个需求点中选取建设，同时根据聚类分析结果数据簇个数确定配送中心数量。将江苏省各需求点按市整理并进行编号，如表 所示。黄河科技学院学报表 江苏省各需求点编号编号城市编号城市编号城市编号城市南京 武进 灌云 江都浦口 溧阳 灌南 邗江江宁 苏州 淮安 宝应六合 吴江 淮阴 仪征溧水 吴中 洪泽 高邮高淳 常熟 清江浦 镇江无锡 张家港 盱眙 丹徒江阴 太仓 涟水 句容宜兴 昆山 金湖 丹阳 徐州 南通 盐城 扬中 铜山 海门 大丰 泰州 丰县 海安 东台 兴化 沛县 如皋 滨海 靖江 睢宁 如东 阜宁 泰兴 新沂 启东 射阳 宿迁 邳州 连云港 建湖 沭阳 常州 赣榆 响水 泗阳 金坛 东海 扬州 泗洪各需求点的地理坐标通过高德地图确定，并根据坐标来计算各需求点到配送中心的距离。江苏省内各需求点拾取的坐标如表 所示。表 江苏省各需求点经纬度坐标编号编号编号 徐超毅，等：基于聚类 粒子群算法的冷链物流配送中心选址分析企业调研地区消费能力提取各需求点过去 年需求量最大值的平均值作为该需求点的计划需求量，以确保能满足各需求点的供货需求，然后统计各区域内所有需求点总需求量作为该区域冷链物流配送中心的总货运量，江苏省各需求点需求量明细如表 所示。根据实际情况调研得知，冷链物流运输的每吨公里运费 为 元，制冷能耗系数 为 元 。企业根据统计的区域冷链物流配送中心年总货运量来决定各仓库面积，区域总货运量与仓库面积的转换系数 为 ，冷链物流配送中心固定建设成本 为 万元，建设费用为各仓库面积与其所处地区每平方米建设单价的乘积，建设单价参考省内各市实际情况进行确定；冷链物流配送中心属于固定资产，因此有使用年限，需要按期进行固定资产计提折旧。本文使用平均年限法进行固定资产计提折旧，预计固定资产净残值为 ，使用年限为 。备选冷链物流配送中心的管理成本由员工薪资，水电成本、日常开销三部分组成，根据 企业在其他省份的运营经验，三者与配送中心面积呈比例相关，同时员工薪资还需要结合各市平均薪资估算得出，江苏省各市建设单价及平均薪资如表所示。表 江苏省各需求点需求量编号需求量编号需求量编号需求量编号需求量 表 江苏省各市建设单价及平均薪资城市建设单价（元）平均薪资（元月）南京 无锡 徐州 常州 苏州 南通 连云港 淮安 盐城 扬州 镇江 泰州 宿迁 结果分析首先将所提取的各个冷链物流需求点坐标数据集导入 软件，然后进行 聚类分析，根据实际情况设置带宽 ，将 个需求点划分为若干个区域，具体结果如图 所示，号表示为各聚类中心点。由于 聚类算法是通过漂移量不断更新球心位置，基于 系数所进行的最优解估计不一定是实际位置 ，所以聚类中心并不代表配送中心的具体落脚点，需要在各个簇类中重新进行迭代优化，从而保证冷链物流配送中心选址位置更加合理，以达到费用最小化的目标。黄河科技学院学报图 江苏省需求点 聚类结果由图 可知，江苏省各需求点被分为 簇，每簇需要以费用最小化为目标各自选出 个冷链物流配送中心，具体城市的聚类结果如表 所示。表 区域划分及聚类结果区域城市编号，公司农产品冷链物流配送中心选址目标函数包括运输成本、建设成本、管理成本，结合实际情况可以得到公式如下：（）（）（）根据 聚类结果可以得到 个簇类，且每个簇类内的需求点只能由簇类里的配送中心配送，因此需要 个配送中心，约束条件如下：（）?（）?（）?，（）?式（）表示在区域 中，选 、其中一个需求点为冷链物流配送中心；式（）表示在区域 中，选 、其中一个需求点为冷链物流配送中心；式（）表示在区域 中，选 、其中一个需求点作为冷链物流配送中心；式（）表示在区域 中，只选 号城市为冷链物流配送中心。本文为求解江苏省农产品冷链物流配送中心选址成本最小化模型，将 算法和 算法进行对比分析，迭代次数为 ，粒子种群规模为需求点个数 ，加速因子，为 ；算法内缩放参数 为 ，交叉概率 为 。图 、图 分别为 算法和 算法的农产品冷链配送中心选址连接图。图 、图 分别为 算法和 算法的收敛曲线。图 改进粒子群算法（）连接图徐超毅，等：基于聚类 粒子群算法的冷链物流配送中心选址分析图 传统粒子群算法（）连接图图 改进粒子群算法（）收敛曲线表 是 算法和 算法结果对比，以表中改进粒子群算法（）结果进行说明，企业将会选择江都（）、沭阳（）、泰州（）、盐城（）作为区域 、区域 、区域 、区域 的农产品冷链物流配送中心，分别向区域内的其他需求点进行配送。算法求解模型的最优值为 万元，迭代次数为 ；算法求解模型的最优值为 万元，迭代次数为 。算法相比 算法总成本降低了 ，迭代次数相比 算法减少了 。算法由于在求解目标函数过程于引入了反向搜索策略，搜索面积更广阔，有着更强的收敛能力，同时不易陷入局部最优解；变异和交叉策略会将当前解与个体极值和全局极值分别作交叉处理，然后对粒子位置某个点位进行变异，从而得到全新解的位置，使算法逼近全局最优解的速度更快，求得的值更优。由图 可以看出，算法在迭代后期，由于交叉变异产生的全新解，更容易跳出局部最优解，达到更优解，因此迭代曲线相比较 算法更趋于陡峭，目标函数值的变化程度更大。因此，算法相比 算法更加适用于冷链物流配送中心选址问题。图 传统粒子群算法（）收敛曲线表 算法和 算法结果对比改进粒子群算法（）江都（）沭阳（）泰州（）盐城（）总成本 万元，传统粒子群算法（）邗江（）泗洪（）南通（）盐城（）总成本 万元，黄河科技学院学报 结论我国冷链物流发展不平衡不充分问题突出，农产品损耗率居高不下，与发达国家相比仍有不少差距。冷链链条缺乏统筹规划，产地基础设施不完善，专业化水平有待提升；冷链物流体系不健全，缺少集约化、规模化运作的冷链物流枢纽设施，存量资源整合和综合利用率不高。因此，在上游环节问题无法迅速解决的情况下，合理的冷链物流配送中心选址可以完善城市末端冷链物流链条，减少资源损耗，降低企业成本。本文针对冷链物流配送中心选址问题，提出了以 聚类算法和改进粒子群算法结合的求解方案，建立了以成本最小化为目标的配送中心选址模型。由于区域未知，区域内需求点散乱分布，没有共性特征，选址点数量未知，因此首先用 聚类算法对需求点进行区域划分，确保区域内各点向密度最大趋近，使选址点在分布上更加合理。其次，针对传统粒子群算法容易在局部最优解周围难以跳出以及只适用于连续变化粒子的缺点，本文将反向搜索、变异和交叉策略引入到传统粒子群算法中，考虑当前位置和相反方向的解，尽量拓展粒子在整个解空间的搜索区域，从而更快得逼近全局最优解。最后将改进粒子群算法（）应用于江苏省农产品冷链物流配送中心选址问题，并与传统粒子群算法（）进行比较，结果可知 算法可以有效降低农产品配送中心选址总成本，总成本相比 算法减少了 ，迭代次数减少了 ，验证了算法的有效性。参考文献：，（）：，王勇，黄思奇，刘永，等 基于 聚类方法的物流多配送中心选址优化研究 公路交通科技，（）：孟军，高佳慧 基于改进飞蛾优化算法的农业物流配送中心选址策略研究 中国农机化学报，（）：计莹峰，闫芳园，杨华龙 考虑三级货损成本的冷链物流配送中心选址优化 数学的实践与认识，（）：刘琳，贾鹏，高?，等 新鲜度限制约束下物流配送中心选址 路径优化 包装工程，（）：袁群，左弈 基于改进混合遗传算法的冷链物流配送中心选址优化 上海交通大学学报，（）：陈淑童，王长军，刘泳 考虑时效与货损的多产品冷链物流配送中心选址与流量分配仿真 东华大学学报（自然科学版），（）：李向可 基于改进粒子群聚类算法的农村物流配送中心选址研究 哈尔滨：东北林业大学，耿建平，雷梦英 和粒子滤波实现红外人体跟踪算法综述 计算机工程与应用，（）：徐超毅，等：基于聚类 粒子群算法的冷链物流配送中心选址分析