基于自适应遗传算法的物流配送中心选址.pdf

年第 卷第 期总第 期物流工程与管理 物流论坛:./.基于自适应遗传算法的物流配送中心选址 秦芳芳张珈瑞张 霆罗竣文(南京邮电大学 理学院江苏 南京)【收稿日期】基金项目:国家自然科学基金资助项目()江苏省博士后科研资助项目()【作者简介】秦芳芳()女南京邮电大学讲师博士研究方向:偏微分方程数值解 【摘 要】物流配送中心选址问题是现代物流配送设置中重要的规划问题 通过分析物流配送中心配送区域内的运输成本、建设成本、运营管理成本以及维护成本建立函数模型采用自适应遗传算法对函数模型进行求解并对基因编码的设计、交叉和变异的运行规则以及目标函数的设置进行创新优化最终确定最优解方案以及多个次优解方案通过某地区实例论证该算法的可行性【关键词】选址问题自适应遗传算法基因编码【中图分类号】【文献标识码】【文章编号】()()【】.【】物流配送中心选址问题是现代物流配送设置中重要的规划问题 物流配送中心是物流系统网络中的核心节点以及重要的基础设施在整个物流系统网络规划中起着枢纽性的作用 通过定量分析每个确定位置的物流配送中心的配送区域内的运输成本、建设成本、运营管理成本以及维护成本来确定最终选址方案并以此来指导实际物流系统网络规划从而实现该物流配送中心选址问题上各项社会资源的成本缩减当前在选址问题模型的研究方面主要有混合整数规划选址模型、大规模群体决策模型、单点物流选址决策模型、两阶段随机规划模型、随机模糊系数的多目标网络优化模型、多准则种群决策模型、机会约束规划模型、混合整数线性规划模型、多成本要素的遗传算法选址模型 本文采用改进的自适应遗传算法进行求解 将选址问题的成本分为运输成本、物流中心建设成本、运营管理成本以及维护浮动成本四个方面通过算法求得成本最低的可行解以及成本相对较低的可行解 并根据该选址问题的特点对物流中心的建设成本建立了以需求量为变量的线性函数对运营成本建立了以建设成本和需求量为变量的嵌套函数构造了更适合该选址问题的数学模型 通过自主设计对应的基因编码、改进交叉互换函数、改进变异函数并且调整收敛准则函数控制精度得到了更高效、更稳定的算法和更可靠的选址结果 模型.模型假设该模型是对物流配送中心位置的选择以及各配送中心与需求点的对应情况即链接方式的选择该模型具有以下假设约束:需要满足所有需求点的覆盖需求点的数量一定大于物流中心点的数量单个需求点仅能由单个物流配送中心满足配送需求单个物流配送中心可以覆盖多个需求点数量上不设限制物流配送中心的容量一定大于等于所对应的需求点的需求量之和各需求点需求量一致且运输统一采用公路运输成本主要包含两个部分分别是公路产生的公路运输成本和选址后的浮动成本浮动成本包括物流配送中心建设成本、运营管理成本其中建设成本、运营管理成本与该物流配送中心的总配送量物流工程与管理第 卷具有正比例关系忽略除了上述以外的其他成本.变量设置设需求点数量为 个物流配送中心数量为 其他符号、参数及变量设置如表 所示表 变量设置变量符号变量说明第 号可选点是否选择建立物流配送中心第 号物流配送中心到需求点的距离第 号物流配送中心是否覆盖第 号需求点第 号物流配送中心所承受的需求量和第 号物流配送中心距离城市中心的距离()建设成本函数()运营管理成本函数可建立物流配送中心的可选点集合 为需求点集合需求点的个数为 个实际选择的 个物流配送中心单位运输成本(元/(吨千米)在 个需求点中第 个需求点的需求量(吨).模型构建 ()()().()()()()()()().()().()式中:和 为决策变量在上述各式子中式()代表目标函数等号右边第 项为从需求点到物流配送中心的公路运输成本第 项和第 项为建设物流配送中心的成本和运营管理的成本式()表示选择 个物流配送中心式()表示是否选择第 号可选点建立物流配送中心式()表示所有需求点被物流配送中心所覆盖式()和式()表示单个需求点仅能由单个物流配送中心满足配送需求式()()为除运输成本外的其他成本控制函数 遗传算法.算法求解策略基因编码将需要解决的选址问题的配送中心点可选方案转化为染色体中基因的编码是遗传算法的重要操作其中染色体上的基因代表一个解决方案 针对决策变量本文采用二进制编码的方法利用自然数将可选中心点通过二进制编码变成由所构成的个体 代表该中心点被选择 代表该中心点未被选择 编码串即染色体的长度 和数量 由选址问题中的可选中心点数量和每一代的种群个数来确定的适应度函数为了保证种群会尽可能地将具有优良性质的个体基因遗传到下一代利用遗传进化过程中的适者生存定理建立了一个可以评价个体生存机会大小的适应度函数个体的目标函数值越小其适应度函数值越大其将自己优良基因遗传到下一代的可能性也就越大相反目标函数值越大其适应度函数值越小被选择的可能性就越小 根据此原理建立了与目标函数之间存在映射关系的适应度函数公式():.()轮盘赌选择本文使用轮盘赌来模拟自然选择过程即对种群内每个个体进行筛选适应度越高的个体存活的概率越大而适应度相对较低的个体也保有一定程度上存活的可能性 使用此法构建出个体适应度函数令种群中每个个体根据自身的目标函数值对适应度进行计算得到种群中每个个体的适应度适应度可以表示种群中的个体表现的优劣使程序对个体基因优劣进行判断和评价 该种群方案中适应度较高的个体将更容易存活适应度较低的个体则更容易被淘汰符合生物种群的自然选择操作而存活下来的种群中将会随机选择两个个体作为父母进行交配来补充后代个数交叉操作交叉操作根据自然选择过程中的遗传规律模拟遗传过程中的基因重组来进行交叉将父母染色体中的基因分别取出相应的部分进行互换来实现基因重组一次该过程将会产生两个新个体分别包含父母的部分基因 本文采用了部分匹配交叉来进行交叉操作通过随机函数()随机选择交叉点位和交叉数量然后对父母的基因进行交叉得到两个具有更复杂结构的新个体变异操作变异操作是模仿基因在遗传过程中发生的基因突变现象而形成的程序操作 对自适应遗传算法而言变异操作发生在父母产生子代的过程中 交叉操作完成后对于产生的子代中间体将会保留一个可以控制的概率发生变异在变异操作的进行过程中子代染色体上的基因将会发生突变其中的一个或多个基因涵盖的信息将会改变 在本文中变异是指基因上的点位值和点位值之间的变化 变异概率会对遗传算法后续的整体表现产生较大的影响当变异概率较小时不利于出现带有新基因的个体因此适应度曲线收敛迅速但难以保证得到了最优解当变异概率较大时染色体内部基因结构将会很容易被破坏从而使遗传算法的运行效率变得低下使得适应度曲线波动较大不收敛 因此在变异操作的变异概率编写设置中本文参考了自适应遗传算法中的变异概率该遗传算法中的变异概率能够随着目标函数值和平均目标函数值的改变而发生改变 当种群中个体间的目标函数值差别较第 期秦芳芳等:基于自适应遗传算法的物流配送中心选址大时变异概率将会变小而当种群中个体的目标函数值趋于局部最优时变异概率将会增加跳出这个局部最优解的限制使变异概率变小自适应变异概率如下:()()其中 为种群中的最小目标函数值为种群中的平均目标函数值为常数图 流程图 图 是具体的遗传算法流程图最后将末代的最优秀个体和四个较优秀个体的目标函数值输出.算法求解步骤初始化:设置最大进化代数 使用()随机生成 个初始对象作为初始种群每个个体代表一个方案每个方案都含有特定的基因编码表示 个体的基因编码方式为:用二进制编码来表示基因码长为物流配送中心可选点的个数可选点被选中则修改值为 不被选中即为 的数量取决于题设要求适应度计算:使用()计算某代种群中每个方案的适应度、表示当代方案适应度的最小值、最大值 表示当前方案的值本文通过比例函数进行适应度计算使得每个个体的适应度在的区间内 目标函数值越小则适应度越大代表被选择的几率越高存活的概率也越高目标函数值越大则适应度越小代表被淘汰的几率越高选择运算:选择运算将模仿生物学中的自然选择原理进行选择选择的方式为轮盘赌 选择开始时利用()函数得到一个随机值若个体的适应度大于该随机值则该个体被选择如果小于随机值则该个体被淘汰 轮盘赌的运行过程中将会根据个体适应度对每个个体进行选择适应度大的有更大几率被选择而适应度小的也有机会被选择实现优胜劣汰的同时也保留一定的进化空间交叉运算:将交叉算子作用于被选择下来的种群 假设 个个体只有 个被选择但下一代仍然需要 个通过交叉、变异得到剩下的 个个体 首先对通过选择运算保留下来的个体进行随机选择得到父母个体再通过随机函数随机选择交叉点位和交叉数量最后通过父母基因重组得到的两个基因进行接下来的变异运算操作变异运算:将变异算子作用于经过交叉运算后得到的基因通过变异对基因的某些点位上的点位值进行修改 据生物学原理可知当选出的父母在进行交叉互换产生子代时会因为基因重组的进行而有概率发生变异 本文采用自适应的变异概率当父母进行交叉操作产生基因时将根据基因点位上的点位值求得目标函数值从而得到基因的变异概率目标函数值越小其变异概率越小当目标函数值太大甚至超过了平均目标函数值时则变异概率变成较大的固定值 接着使用()函数得出随机数若该随机数小于得到的变异概率则对子代随机两个的基因编码进行反码操作将 变成、变成 并最终得到变异的基因作为子代新个体 最后种群()经过选择、交叉、变异运算之后得到下一代种群()迭代次数 终止条件判断:若迭代次数 则以进化过程中所得到的具有最优目标函数值的一个个体和其余四个具有较优目标函数值的个体作为最优解输出此时终止程序计算 实例分析.实例参数现有某地区考察该地区在一年的时间内在 个物流配送中心备选点选取 个点位来建设物流配送中心对 个快递需求点进行物流配送的最小成本方案 默认该地区的面积为 平方千米默认快递运输单位为.万元/(万吨千米)中转中心建设成本、运营管理成本根据对应快递配送需求点数量规定 一般的物流中心一年内的物流吞吐量为 万吨左右 预期设想中最终需要从十个中心点中选得 个物流配送中心因此所有物流中心的大概需求量为.(.为大概估计)万吨分摊到每个需求点为/万吨因此认定每个需求点的年需求量在物流工程与管理第 卷的区间内取值.模型求解实验过程首先得到 个物流配送中心可选点和 个需求点的坐标然后使用 函数读入 个物流配送中心可选点和 个需求点的坐标其中物流配送中心可选点坐标如表 所示需求点坐标如表 所示生成的地图如图 所示通过 编程将初始种群规模大小设置为 个交叉概率根据适应度函数变化变异概率根据自适应函数变化进行 次迭代通过算法不断迭代直至适应度函数值收敛使结果总用时在 以内并最终找出一个最优方案和四个较优方案其中最优方案分布如图 所示 模型求解和算法迭代所得最终的最优基因编码为()即在备选点、建立物流配送中心该最优方案的最小成本为.(万元)图 是通过计算适应值得到除了最优方案外的前四个较优方案结果图表 为较好的四个方案选取的可选点及其对应的目标函数值 图 为程序运行的目标函数值进化曲线表 可选点坐标可选点 横坐标()纵坐标()可选点 横坐标()纵坐标().表 描述了十个物流配送中心可选点的横纵坐标可选点下面的数字 表示了可选点的序号为第 个到第 个每个可选点都在平面上 轴 和 轴 围成的区域范围以内以模拟该地区的可选点区域范围表 需求点坐标需求点横坐标()纵坐标()需求点横坐标()纵坐标().表 描述了 个需求点的物流需求点的横纵坐标需求点下面的数字 表示了需求点的序号为第 个到第 个每个需求点都在平面上 轴 和 轴 围成的区域范围以内以模拟该地区的需求点区域范围图 初始点位分布图 图 描述了选址前的初始点位分布图图中的空心圆形点为可选物流配送中心点共有 个空心正方形点为需求点共有 个图 最优方案图 图 描述了选址问题通过 次迭代以后的最优方案图由此可以看出四个实心物流配送中心点分别和 个需求点进行了连接其目标函数值最小第 期秦芳芳等:基于自适应遗传算法的物流配送中心选址图 较优方案图 图 描述了除了最优方案外的四个较优方案图表 方案的适应值方案点位目标函数值(万元)方案.方案.方案.方案.方案.表 选取了五个目标函数值相对较小即成本相对较低以及最低的方案 方案 是目标函数值最小的一个方案说明其拥有最小成本是最合适的物流配送中心选址方案 其他四个方案相对于方案 来说目标函数值较高即成本相对较高但由于其超出部分较小从而列入较优的方案图 目标函数值进化曲线图 图 描述了迭代了 次的平均目标函数值可以看到当迭代次数超过 代后平均目标函数值的大小已经趋于稳定.结果分析对该实例构建模型框架同时在该框架模型的基础上使用改进的自适应遗传算法进行求解其算法程序运行的过程中随着过程的不断迭代目标函数的取值最终趋于收敛 程序运行完毕之后得到了一组包含最小目标函数值的一个最优方案和另外四个具有相对较小目标函数值的近似最优解方案在考察不同迭代次数对于算法执行的时间影响时为了对自适应遗传算法运行不同迭代次数所用的时间进行比较本文利用编写完成的函数文件随机生成 个地图即生成 个全新的初始条件每个地图拥有不同的物流配送中心可选点和需求点 对它们采用不同的迭代次数进行时间上的对比观察在迭代次数为、时多次运行且分别记录运行时间并求出相应平均值运行结果如表 所示表 迭代所需时间(秒)问题序号问题.问题.问题.问题.问题.平均时间(秒).由此可见随着迭代次数的不断提高程序运行所需要的平均时间也在不断延长 在迭代次数提高至 代时程序能在 秒以内完成对该物流配送中心选址问题的求解为考察不同迭代次数与遗传算法运行结果的关系本文对该物流配送中心选址问题的同一初始条件分别迭代、次记录运行结果中五个方案的目标函数值的变化情况并求出每个方案的平均值运行结果如表 所示表 不同迭代数的目标函数值(万元)运行代数方案 方案 方案 方案 方案.平均目标函数值.由此可见随着迭代次数的不断提高较优方案的目标函数值不断减小遗传算法寻找较优方案的能力随迭代次数的增多而增强在考察最优方案是否会由于多次运行而出现变化时为了对遗传算法多次运行的结果目标函数值进行比较本文用程序对该物流中心选址问题的同一初始条件进行了 次求解并分别记录它们运行结果中 个选址方案的目标函数值如表 所示物流工程与管理第 卷表 运行的目标函数值(万元)运行序号方案 方案 方案 方案 方案.由此可见除了方案 其他较优方案都出现了运行结果不一致的情况这是因为在自适应遗传算法的迭代过程中模拟自然选择的轮盘赌操作在一定程度上也具有使某些优秀个体方案无法出现的概率从而导致一些相对较优的个体方案未被记录的可能 结论选址问题是一个种类庞杂的问题集合本文对 中心问题的物流配送中心选址问题进行分析并建立函数模型利用自适应遗传算法对问题模型进行求解通过自主设计对应的基因编码、改进交叉互换函数、改进变异函数并且调整收敛准则函数控制精度得到了更高效、更稳定的算法和更可靠的选址结果并通过实例证明了该算法的可行性和普遍性对物流配送中心选址问题具有重要实用价值和指导意义参考文献 胡莹.基于 遗传算法的物流中心选址问题研究.中国水运(下半月)():.霍雪咪傅航.基于 的物流配送中心选址问题研究.物流工程与管理():.王莫凡等.公众参与视角下基于大规模群决策的物流中心选址研究.物流工程与管理():.周兴龙金鹏飞.基于遗传算法的单点物流选址问题探析.物流工程与管理():.():.():.():.():.周思育等.基于遗传算法的烟草物流配送中心选址问题.湖北工业大学学报():.(上接第 页)借助自媒体等监督成本更低廉的途径来积极维护自身的权益行使自身权力培养维权意识共同努力形成良好有序的市场价格环境本文并未涉及突发事件发生后原材料成本可能会上升及消费者的恐慌心理导致需求暴增等情形所造成应急物资价格浮动这也是今后的研究方向参考文献 陈兵马贤茹.从依法战“疫”看应急物资价格监管法治化.中国价格监管与反垄断():.孙宇.新冠疫情背景下哄抬价格的法律规制与反思.河南科技大学学报(社会科学版)():.龙俊.重大突发公共事件中价格管制的正当性及其法律规制.中国政法大学学报():.冯永晟管世杰.重大突发事件下的哄抬价格与价格监管研究.价格月刊():.():.:.():.周泽辉张桂涛尹晓娜.低碳背景下政府、企业与低碳服务提供商的演化博弈/.运筹与管理:.钱鑫阳李芳.基于云平台的闭环供应链信息共享演化博弈分析.上海理工大学学报():.李芳安娜.医联体下医疗服务供应链创新激励机制与协调研究.中国医院():.():.