资源描述：
《基于改进遗传算法的物流配送点选址问题研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、第24卷第4期兰州交通大学学报(自然科学版)Vol.24No.42005年8月JournalofLanzhouJiaotongUniversity(NaturalSciences)Aug.2005文章编号:1001O4373(2005)04O0135O03基于改进遗传算法的物流配送点选址问题研究*于波,李引珍(兰州交通大学交通运输学院,甘肃兰州730070)摘要:在已知物流配送点数目的条件下,以最低送货运输费用为目标,利用最小二乘法推导出多物流配送点的选址模型及其迭代算法;根据遗传算法的基本思想,设计了求解已知物流配送点数目条件下的选址和物流服务分配问题的遗传算法.通过实例证明该
2、模型及算法具有较好的应用价值.关键词:配送点选址模型;迭代算法;遗传算法;最小二乘法中图分类号:O224文献标识码:A物流配送点选址是物流系统规划的一项重要内客始终只能从某一个配送点进货,由此确定了物流服[1]m容,选址是否合理将直接影响到物流配送点的各项务分配的约束条件:Elij=1(j=1,2,,,n).经营成本和获利程度.随着社会分工的日益专业化,i=1为了满足顾客日益增长的需要和实现规模效益,企业由最小二乘法原理,对于一个给定的矩阵将不得不建立多个配送点.我国对物流配送点选址问(lij)m@n,欲使送货运输费用最低(目标函数最小),[2,3]题较为成熟的研究多为单配送点选
3、址问题.本文必有5c=0,5c=0,从而可推导出迭代公式[4]5ui5vi运用高效有向搜索的遗传算法来确定物流服务分配nn方案,借鉴最小二乘法推导的迭代公式进行选址计uki=lijtjwjxj/lijtjwj(2)EkEkj=1dijj=1dij算,有效地解决了多物流配送点的选址问题.nnklijtjwjyjlijtjwjvi=Ek/Ek(3)1模型的建立与分析j=1dijj=1dijk+1k2k2dij=(ui-xj)+(vi-yj)(4)建设费用一般为固定费用,对多物流配送点选(i=1,2,,,m;j=1,2,,,n)址采用运输成本最小化原则,即用占物流成本绝大当配送点位置未
4、知时,解决此问题可用迭代方部分的运输费用代替物流成本.建立目标函数[5]mn法,迭代方法能保证收敛到最优值.方法如下:令22f=EElijtjwj(ui-xj)+(vi-yj)(1)d00000ij=1,代入式(2),(3)得到ui,vi;再将ui,vi代入i=1j=11111式中:m为已知物流配送点数目;n为已知顾客数目;式(4)求出dij,将dij代入式(2),(3)求出ui,vi的kkk+1k+1(xj,yj)为位置已知的顾客地址坐标,j=1,2,,,n;值;如此反复,直到(ui,vi)与(ui,vi)的变化值k+1k+1(ui,vi)为位置待定的物流配送点地址坐标,i=1
5、,2,小于某一指定的较小值E时为止.此时(ui,vi)即,,m;wj为顾客j的货物需求量;tj为到顾客j的单位为这一服务分配方案的最优地址.运输费用;lij=1表示第i个配送点向第j个顾客送当m和n的值较小时,可通过排列组合列举出货;lij=0表示第i个配送点不向顾客j送货.lij的值每一服务分配方案,然后由迭代算法求出每一方案共有m@n个,若以m为行、Fn为列,就形成一个物流相对应的配送点坐标并求出送货运输费用,经过比服务分配矩阵(lij)m@n,每一个布尔矩阵(lij)m@n对应较后,即可确定出送货运输费用最低的配送点坐标一种物流服务分配方案,多物流配送点选址问题必须及容量;
6、但当m和n的值较大时,将出现配送方案组先确定物流服务分配方案,所以也称为选址分配问合爆炸,成为一个较为复杂的组合优化问题,此时必[4]题.为简化多配送点选址分配问题,假设每一个顾须运用优化算法来求解,遗传算法便成为解决这一*收稿日期:2005O03O12作者简介:于波(1980O),女,内蒙古海拉尔人,硕士研究生.136兰州交通大学学报(自然科学版)第24卷问题的有效算法之一.2.3确定适应度函数和评价函数根据模型特点,提出了如下求解方法:适应度函数常为目标函数,由于此问题的目标1)由遗传算法随机产生可行的初始服务分配函数取最小值,可重新构造一个新的适应度函数方案;2)将每一服务
7、分配方案通过上述迭代方法求fc(x)=C-f(x)(5)出各配送点的位置;3)根据求出的配送点位置及分式中:fc(x)为适应度函数;C为一个较大的常数;配方案,计算送货运输费用;4)经过遗传算法的选f(x)为目标函数.在已确定服务分配方案(lij)m@n择、交叉、变异操作产生新的服务分配方案.如此反后,应先由迭代算法求出各配送点的地址坐标(ui,复将遗传算法与迭代方法有效结合,便可求出多个vi),再由目标函数经过式(5)的转换后求出各染色物流配送点的最优服务分配方案及最优地址.体
