《物流配送是物流中直接与消费者相连的重要环节》由会员分享，可在线阅读，更多相关《物流配送是物流中直接与消费者相连的重要环节（27页珍藏版）》请在金锄头文库上搜索。
1、物流配送是物流中直接与消费者相连的重要环节, 是在集货、配货基础上, 按货物种类、品 种搭配、 数量、时间等要求所进行的运送, 是“配”和“送”的有机结合. 在物流配送业务中, 存在 许多优化决策 的问题, 本文只讨论车辆优化调度问题. 车辆优化调度问题(vehicle routing problem , 简称 VRP) 是由 Dantzig 和Ramser 于1959 年首次提出 1 . 一般定义为: 对一系列发货点和/ 或收货点, 组织适当的行车 路线, 使车辆有序地通过它们, 在满足一定的约束条件(如货物需求量、车辆容量限制、行 驶里程限制、 时间限制等) 下, 达到一定的目标(如路程最
2、短、费用最小、使用车辆数尽量少等) . 车辆优 化调度问题 是一个有约束的组合优化问题, 已经被证明是个NP 难题, 随着问题规模的扩大, 求解时间 呈几何级数上 升. 因此人们逐渐倾向于采用近似算法, 启发式方法作为一种简单而行之有效的近似方法, 既能满足详细 描述问题和求解的需要, 又便于计算机实现. 为此国内外研究车辆优化调度问题的文献主要 把精力放在构 造高质量的启发式算法上. 通过现代优化算法做出决策和判断, 追求运输系统总体最优、总 费用最低的最 优解. 2 物流配送车辆优化调度问题的数学模型 本文针对一种最普遍的, 也是大多数有关车辆优化调度问题文献所讨论的一类问题, 即集货 或
3、送货的 非满载车辆优化调度问题. 比如一个配送中心拥有容量为q 的车辆, 现有n 项货物运输任务, 以1 , , n 表示, 已知任务 i 的 货运量为g i ( i = 1 , , n) , 且gi Fq , 求满足货运要求的费用最小的车辆行驶路线. 为方便构造数学模型, 将配送中心编号为0 , 任务编号为1 , , n , 任务及配送中心均以点i ( i = 0 ,1 , , n) 来表示, 并定义变量如下: yki = 1 , 点i 的任务由车辆k 完成; 否则, yki = 0 xij k = 1 , 车辆k 从点i 行驶到点j ; 否则, xij k = 0 则这个车辆调度模型如下:
4、mini j k cij x ij k (1)i g i y ki Fq; Pk (2)k y ki = 1 i = 0 , 1 , , n (3)i x ij k = ykj j = 0 , 1 , , n; Pk (4) j x ij k = ykj i = 0 , 1 , , n; Pk (5) xij k 0 , 1 i , j = 0 , 1 , , n; Pk (6) yki 0 , 1 i , j = 0 , 1 , , n; Pk (7) X = ( xij k ) s i , j = 0 , 1 , , n (8) 上述数学模型中, 式(1) 为目标函数, cij 表示从i
5、到j 需花的运输成本, 它的含义可以是时 间、距 离、费用等; 式(2) 保证每条路径上各需求点的需求量之和不超过汽车的载重; 式(3) 限制 每个需求点 有且仅能由一辆汽车送货; 式(4) 和(5) 表明两个变量之间的关系; 式(8) 中的为支路消去 约束, 避 免出现与配送中心相分离的线路. 2 3 车辆优化调度的混合遗传算法设计 遗传算法具有并行搜索能力且能一定程度上保留历史信息, 但选择操作无法产生种群外的 个体, 交叉 变异只具有有限的进化能力, 所以常出现进化缓慢和过早收敛的现象, 另外算法收敛性很难 控制. 而模拟 退火算法的概率突跳性使得它有避免局部极小的能力, 但算法不具有并
6、行性, 每一时刻仅保 留一个解, 没 有冗余和历史信息, 且优化过程中若退温过快会遗失优良解, 同时抽样稳定条件或退温速率 的限制使得算 法需要很长的寻优时间. 所以这两者结合所构成的混合优化策略能进行优势互补, 提高算法 的运行效率和 效果. 并在混合遗传算法上的基础上加入自适应的交叉和变异概率以及精英保留策略的思 想, 提出一种混 合优化策略自适应的模拟退火遗传算法. 基本思想是: 将遗传算法与模拟退火算法相结合, 构成一种混合遗传算法, 与基本遗传算法 的总体运 行过程相类似, 它从一组随机产生的初始解开始搜索, 先通过附带精英保留策略的选择、交 叉、变异等遗 传操作来产生一组新的个体,
7、 然后再独立地对所产生的各个个体进行模拟退火操作, 以其结 果作为下一代 遗传操作的群体, 这个过程反复迭代直到满足某个终止条件. 求解过程为: (1) 选择初始解群, 给定初温. (2) 确定每一个体的适应度. (3) 重复以下步骤直至算法收敛准则满足: (311) 进行复制操作(附带精英保留策略) ; (312) 进行交叉操作(附带精英保留策略) ; (313) 进行变异操作(附带精英保留策略) . (314) 对种群中每一个体进行模拟退火操作直至抽样稳定: (31411) 由状态产生函数产生新个体;(31412) 利用状态接受函数以一定概率接受新状态. (315) 退温操作. (4) 输
8、出最优结果. 311 确定车辆数 首先为了安排线路, 须预先对需要的车辆数进行一个估计. 一般来说, 当问题的约束越多, 组织线路 就越难, 一辆车所完成的满足所有约束的任务越少, 这时, 一辆车实际所能容纳的任务量要 小, 而所用的 车辆数可能要多. 本文使用文献3 的公式来确定需要的车辆数:k = n i = 1 gi / aq + 1 (9) 式中, k 为所需的车辆数, 表示不大于括号内数字的最大整数; 其中0 q , 将S 至n 的基因逐一向后移动一位, 使S 位空出, 将0 插入第S 位. 接着若 t - 1 j = s g ij Fq 且 t j = s g ij q , 如上面
9、的操作, 使t 位空出, 将0 插入第t 位和. 如此继续, 直到将k - 1 个0 全部插入染色体为止, 然后在生成的染色体的首尾加0 , 作为起点和终点. 如此反复, 直至满足群 体数. 315 参数控制 参数控制主要是初始温度, 交叉和变异概率的选择. 实验表明, 初温越大, 获得高质量解的 几率越 大, 但花费的计算时间将增加. 因此, 初温的确定应折衷考虑优化质量和优化效率, 这里采 用一种最常用 且可理解的初温确定方案: 首先随机产生一组状态, 确定两两状态间的最大目标值差max , 然后由式T0 = 2max / ln pr , 其中pr 为初始接受概率(理论上应接近于1 , 实
10、际设计时也可取011) 5 . 采用自适应的交叉和变异概率: Pc = Pc1 -( Pc1 - Pc2 ) ( f- f avg ) f max - f avgfE f avg Pc1 f random 0 , 1 作为接受新状态 的条件, 其中为新旧状态的目标值差, Tk 为当前温度值. 温度更新函数, 即温度的下降方式, 用于在算法外循环中修改温度值. 理论上温度应以很慢 的速度下 降, 如对数的倒数方式, 但为了避免过于冗长的搜索过程, 较好地折衷兼顾优化质量和时间 性能, 指数退 温函数是最常用的退温策略, 即Tk + 1 =Tk , 为退温速率. 4 仿真实验分析 本文用功能强大的
11、Matlab 软件进行实例的仿真实验的编程, Matlab 是以矢量和矩阵为基本 运算单 元, 所以利用Matlab 编写VRP 问题的算法, 具有编程简单、容易实现的优点. 在Matlab 的 图形窗口下, 可以方便地给出点阵, 其分析结果更具一般性. 经过计算找到最小费用(或最短路径) 后有 Matlab 强大 绘图功能的支持, 将所得路径标注出来, 非常直观. 实验的初始数据参照文献6 . 每个客户i 的货运量为g i ( i = 1 , , n) , 且gi Fq , q 为车辆的最大 承载量, 此处 q = 8. 各仓库间运输成本 cij , 由各客户间的直线距离决定, 即: Cij
12、 = ( xi - x j ) 2 + ( yi - y j ) 2 首先确定所需的车辆数, 这里k = n i = 1 gi / aq + 1 = 36173/ (0185 3 8) + 1 = 6. 按照上一节给出的标准进行A GASA 的算法设计和参数选择. 对算例进行10 次随机的运算, 每次的 结果为: 84710572 85610681 84617847 87612293 84617847 85416347 86817677 84617847 86213122 84617847 (注: 加粗的为已知的最优解) 最优值对应的染色体为: 0 15 14 17 13 11 9 5 3 0
13、 18 6 0 4 16 2 8 0 1 2012 0 0 10 7 19 0即配送路线为: 子路径1 : 0 15 14 17 13 11 9 5 3 0 子路径2 : 0 18 6 0 子路径3 : 0 4 16 2 8 0 子路径4 : 0 1 20 12 0 子路径5 : 0 10 7 19 0 图1 是最优解对应的进化过程图, 图2 是对应最优解的路线图.图1 进化过程图图2 最优解路线图从10 次实验得出的数据上可以看出有4 次达到最优值84617847 , 具有很高的达优率. 平均值agasa _ mean = 8551220 8 , 说明算法具有很高的鲁棒性(可靠性) . 10
14、 次随机实验的平均运行时间 agasa _ time = 141183 1 , 算法收敛的时间性能可以满足实际车辆调度的要求. 最优解对应的染色体存在两个并在一起的“0”, 说明没有必要派出6 辆车, 只要5 辆车就 可以完成配 送任务, 这样在现实中可以节约车辆调用的固定成本. 如果算法得出的运输成本大于M , 可 以认为算法 产生了不可行解, 这是因为指定的车辆数过少的缘故, 解决的办法是调节公式(9) 中的a 的 值, 适当增 加车辆数. 5 结束语 混合遗传算法A GASA 结合遗传算法和模拟退火算法的优化机制以及邻域搜索结构的混合 策略, 大 大提高了算法的全局优化度和鲁棒性. 虽然
15、 A GASA 算法对参数的选择没有单一算法那样摘要： 配送是物流系统中一个直接与消费者相连的重要环节， 对配送系统进行优化， 可 以提高物流经济效益、实现物流 科学化， 因此配送系统的优化问题显得尤为重要。进行配送系统优化， 主要是配送车辆 调度的优化。文章在全面分析研究物流 配送业务特点的基础上， 针对配送中的核心问题车辆调度优化问题进行了深入的研 究， 建立了单源点物流配送车辆调度优 化问题的数学模型， 并运用遗传算法对其进行求解， 仿真实例证明了该方法的有效性。 关键词： 物流配送； 车辆调度； 遗传算法Abstract: Distribution is an important li
16、nk in logistics, which is joined to consumers directly. Vehicle Routing Problem （VRP） is the main part of optimizing the distribution system. It can advance the economic benefits and make logistics scientific. Firstly, the paper analyzes VRP, and sorts it according to given conditions. Secondly, it chooses a typical one to analyze.
