市场经济的改革以及跨地区贸易的发展共同促进了物流业的快速发展。物流配送是指将客户所购的货物及时的送交客户的过程, 物流配送不仅是物流业最重要的环节之一, 同时物流配送的效率也直接影响着整个工作流程的效率, 因此, 需要不断地改进、优化物流配送路径。本文的研究背景是山东的临沂地区, 临沂市被确定为省级物流节点城市, 将利用商贸市场集聚的优势, 以建设大物流促进商贸流通发展为目标, 建立连接江苏、辐射长江三角洲, 连通日照、连云港的商贸物流基地, 服务于省内外商贸流通和经济建设。那么在这样一个重要的物流节点城市, 合理地选择配送路径具有重要的意义, 不仅能偶缩短配送时间, 也能降低配送成本, 在提高服务质量和提高经济效益方面都有较大贡献。
优化配送路径是一个NP-Hard问题, 为了解决这一问题, 近年来提出了不少算法, 比如节约法、扫描法等, 本文通过一系列的研究, 将遗传算法应用于物流配送的决策分析中。遗传算法 (Genetic Algorithms, GA) 最早是由John.H.Holland于1975年提出的, 它是一种结合了生物自然选择和基因遗传学的优化搜索方法。它的优点非常多, 比如鲁棒性强、速度快、搜索范围广等而广泛应用于各个领域。本文针对物流配送路径优化问题, 首先分析了其数学模型, 然后引入了遗传算法来优化, 最后进行了实验计算, 研究表明, 将遗传算法应用于物流配送路径优化问题是行之有效的方法, 取得较好的结果。
物流配送的优化可以描述为:配送中心用多辆汽车向多个客户送货, 其中汽车的载量确定, 客户的位置和需求量确定, 通过优化, 使得汽车所行驶的总路程最短, 并且满足以下条件:
(1) 各路径上的客户的总需求量小于等于汽车载量;
(2) 各路径总长度小于等于汽车配送一次可行驶的最大长度;
(3) 一条路径由一辆汽车进行配送, 且必须满足个客户需求。
通过对以上条件的分析, 建立物流配送路径的数学模型。首先规定以下公式中各字母的意义:K为配送中心拥有的汽车总量;Qk (k=1, 2, …, K) 为各汽车的载量;Dh为汽车进行一次配送所行驶的最大长度;L为客户总数;qi为客户i的需求量;d0j为客户与配送中心的长度;dij为客户i和客户j之间的长度;nk为第k辆汽车负责的配送的客户数, 若此值为0, 则表示此汽车未使用;Rk为集合, 表示第k条路径, 其中rki表示客户rki在路径k中的顺序为i, 令rk0=0表示配送中心。经过分析, 建立如下数学模型:
此式为优化目标函数, 根据条件, 有以下客观限制条件需要满足:, 用来保证汽车不超载; (2) , 用来保证汽车在最大行驶长度以内; (3) 0≤nk≤L, 用来确保各路径的用户总数不超过L; (4) , 用来保证每个客户满足需求; (5) , 用来表示个路径的客户组成; (6) , 在每条路径只能由一辆汽车配送; (7) , 用来表示汽车是否参与配送。
遗传算法是一种很好的搜索优化方法, 它的操作对象为种群的所有个体, 个体与问题的解是一一对应的, 其中选择、交叉和变异是最主要的操作。它的流程图如下:
这种算法主要包括6个基本要素:
(1) 编码:通过编码将空间的数据转变为基因型串数据, 在编码前先进行量化。
(2) 生成种群:通过随机方法产生初始种群, 每个个体对应问题的一个解。
(3) 评估适应度:用来评估个体的优劣, 评估结果作为遗传操作的依据。
(4) 选择:通过“适者生存”的选择方法, 从当前种群中选取适应度高的个体组成新的种群, 适应度越高, 被选择几率越大, 但不能保证一定被选择。
(5) 交叉:将选出的个体存入配对库, 进行随机配对, 产生新的个体。
(6) 变异:引入变异是为了解决在交叉过程中引起的信息遗失现象, 按概率改变染色体基因位。
(1) 编码方法。在本文中, 配送中心用0表示, 客户用1表示 (L个1表示有L个不同客户) 。每条配送路径的起点和终点都是配送中心, 配送路径的最大值由配送中心的汽车总数K决定, 这样, L个1或者K—1个0随机排列成一条染色体, 则对应一种配送路径方案。
(2) 初始种群的产生。由1和0构成的序列称为一条染色体, 那么由多条不同的染色体构成初始种群。
(3) 适应度评估。在评价一种配送方案的优劣时, 既要判断是否能够满足约束条件, 又要计算它的目标函数值。因此, 在进行评估时, 首先判断各配送路径方案是否满足约束条件, 如果不满足, 则该路径为不可行的路径, 然后计算目标函数值。适应度Fi的计算公式如下所示:
其中, Zi为目标函数值, Mi为染色体i所对应的不可行路径数, G为权重因子, 为值较大的正数。
(4) 选择操作。在本文中, 综合使用最优个体保留策略和轮盘赌法, 首先, 将所有染色体按照适应度小进行排序, 对于适应度最高的染色体, 则直接进行复制;然后采用轮盘赌法, 使剩余的染色体产生下一代的N-1条染色体。每条染色体被选中的概率为它本身的适应度与种群中所有染色体的适应度之和的比值。
(5) 交叉操作。交叉操作主要是按照交叉概率将除了第一条染色体外的其他染色体进行交叉配对, 本文采用两点交叉法。
(6) 变异操作。本文所采用的变异操作是为了保证一旦某基因片段需要发生变异, 那么另一片段也要发生变异, 这个片段是随机产生的。
在本实验中, 采用C语言编程, 以2辆汽车为5个客户配送为例, 其中汽车载量为8000千克, 一次配送最大行驶长度为40千米, 配送中心与客户以及客户与客户之间的长度由下表表示 (单位千米) :
在本实验中, 种群大小取50, 交叉概率为0.65, 变异概率为0.005, 权重因子100千米, 计算100次。进过计算, 得到10次运行的结果如下:70.0千米、72.5千米、76.0千米、70.0千米、67.5千米、72.0千米、73.5千米、75.5千米、71.5千米、68.5千米。均优于用节约法所计算的结果 (79.5千米) 。
通过本文的理论分析与实验证明, 将遗传算法应用于物流配送路径优化方案中是可行的。本文首先分析了物流配送路径的数学模型, 然后简介了遗传算法的原理, 并进一步将遗传算法应用于物流配送路径中, 最后通过实验计算, 证明用遗传算法能够得到快速的得到物流配送路径的最优解, 是提高配送效率有效的方法。
摘要：随着社会经济和网络技术的不断发展, 社会物流业也呈快速发展的趋势。在物流业中, 物流配送是很重要的环节之一。本文以临沂地区的物流业为背景, 为了更好地解决物流配送路径优化问题, 建立了一种遗传算法模型。实验计算表明, 通过用遗传算法进行物流配送路径优化, 可以方便有效地得到问题的最优解或者近似最优解。
关键词：遗传算法,物流配送,优化,临沂地区
[1] 王辉.基于改进遗传算法的物流配送路径优化研究[D].山东科技大学, 2010, 5
[2] 黄晓滨, 邹书蓉, 张洪伟.改进的遗传算法及在物流配送路径优化中的应用[J].西南民族大学学报 (自然科学版) .2008 (4)
[3] 易荣贵, 罗大庸.基于遗传算法的物流配送路径优化问题研究[J].计算机技术与发展.2008 (6)
[4] 郭淑红, 杨晓慧.遗传算法在物流配送路径优化问题中的应用[J].硅谷.2009 (1)
推荐阅读：
遗传算法在智能车路径判别中的应用09-12
弹性结构的遗传算法优化设计01-13
免疫遗传算法05-29
遗传算法论文提纲11-15
双链量子遗传算法05-27
基于遗传算法的排课系统研究09-14
基于遗传算法的半导体生产调度问题12-28
遗传算法产品设计论文提纲11-15
遗传算法机械工程论文提纲11-15
基于模糊神经网络与遗传算法的质量成本优化01-24
