公司新闻 行业动态

物流配送途径优化论文

发布时间:2022-09-26 10:47:23 来源:天博官网下载链接

  摘要………………………………………………………………ⅰ 一、导言(问题的提出)………………………………………… 1 二、物流配送途径优化问题的数学模型……………………………X 三、物流配送途径优化问题的遗传算法……………………………X (一)遗传算法的基本要素 ………………………………………X (二)物流配送途径优化问题的遗传算法的结构……………………X 四、试验核算与成果剖析 …………………………………………X 五、 定论…………………………………………………………X 参考文献 …………………………………………………………X 称谢 ………………………………………………………………X

  求解该问题的遗传算法,并进行了试验核算。核算成果标明,用遗传算法进行物 流配送途径优化,能够便利有用地求得问题的最优解或近似最优解。

  跟着市场经济的开展和物流技能专业化水平的进步,物流配送业得到了迅猛 开展。物流配送是指按用户的订购要求,在配送中心进行分货、配货,并将配好 的货品及时送交收货人。在物流配送事务中,存在许多优化决策问题,本文评论 其间的物流配送途径优化问题, 即经过拟定合理的配送途径,快速而经济地将货 物送达用户手中。配送途径的挑选是否合理,对加速配送速度、进步服务质量、 下降配送本钱及添加经济效益都有较大影响。 研讨标明, 配送途径优化问题是一个 NP 难题, 只要在需求点和路段较少时, 才干求得准确解。 因而,用启发式算法求解该问题就成为人们研讨的一个重要方 向, 并呈现了多种启发式算法, 如 Clarke 和 Wright 提出的节约法, Gillett 和 Miller 提出的扫描法①等,尽管这些算法为求解配送途径优化问题供给了有用的办法, 但也存在必定的问题, 如节约法尽管具有运算速度快的长处, 但也有组合点零乱、 边际点难以组合的问题, 扫描法为非渐进优化等。怎么针对物流配送途径优化问 题的特色,结构运算简略、寻优功能优秀的启发式算法,是一个值得深入研讨的 课题。 遗传算法的呈现为求解物流配送途径优化问题供给了新的东西,该算法是由 美国的 J.Holland 教授于 1975 年提出的, 它是一种学习生物界天然挑选和天然遗 传机制的随机化查找办法。 因为遗传算法选用随机挑选, 对查找空间无特殊要求, 无需求导,具有运算简略、收敛速度快等长处,特别适用于处理传统查找办法难 于处理的杂乱和非线性的问题,现在已广泛使用于组合优化、机器学习、自习惯 操控等范畴。 本文针对物流配送途径优化问题的特色,结构了求解该问题的遗传 算法,经过试验核算,得到了较好的成果。

  物流配送途径优化问题能够描绘为:从配送中心(或称物流据点)用多辆汽 车向多个需求点(或称顾客)送货,每个需求点的方位和需求量必定,每辆轿车 的载重量必定,要求合理安排轿车道路,使总运距最短,并满足以下条件: (1) 每条配送途径上各需求点的需求量之和不超越轿车载重量; (2)每条配送途径的 长度不超越轿车一次配送的最大行进间隔; (3)每个需求点的需求有必要满足,且

  Z·米凯利维茨. 演化程序——遗传算法和数据编码的结合[M]. 北京:科学出版社,2000.

  只能由一辆轿车送货。本文学习文献[3]树立的车辆途径问题的数学模型,并通 过考虑上述物流配途径优化问题的束缚条件和优化方针, 树立了物流配送途径优 化问题的数学模型。 设配送中心有 K 辆轿车,每辆轿车的载重量为 Qk(k=1,2, · · · ,K) ,其一 次配送的最大行进间隔为 Dk,需求向 L 个需求点送货,每个需求点的需求量为 qi(i=1,2, · · · ,L) ,需求点 i 到 j 的运距为 dij,配送中心到各需求点的间隔为 d0j(i、j=1,2, · · · ,L) ,再设 nk 为第 k 辆轿车配送的需求点数(nk=0 标明未使 用第 k 辆轿车) ,用调集 Rk 标明第 k 条途径,其间的元素 rki 标明需求点 rki 在路 径 k 中的次序为 i(不包含配送中心) ,令 rk0=0 标明配送中心,则可树立如下物 流配送途径优化问题的数学模型:

  上述模型中, (1)式为方针函数; (2)式确保每条途径上各需求点的需求量 之和不超越轿车的载重量; (3)式确保每条配送途径的长度不超越轿车一次配送 的最大行进间隔; (4)式标明每条途径上的需求点数不超越总需求点数; (5)式 标明每个需求点都得到配送服务; (6)式标明每条途径的需求点的组成; (7)式

  束缚每个需求点仅能由一辆轿车送货; (8)式标明当第 k 辆轿车服务的客户数≥ 1 时,阐明该辆轿车参加了配送,则取 sign(nk)=1,当第 k 辆轿车服务的客户数 1 时,标明未运用该辆轿车,因而取 sign(nk)=0。

  (一)遗传算法的基本要素 遗传算法是一种“生成检测”的迭代查找算法。该算法以集体中的全部个 体为操作方针,每个个别对应研讨问题的一个解。挑选、穿插和变异是遗传算法 的三个首要操作算子。该算法包含以下 6 个基本要素: 1、编码。因为遗传算法不能直接处了解空间的数据,因而,有必要经过编码 将它们标明成遗传空间的基因型串结构数据。 2、初始集体生成。因为遗传算法是一种集体型查找办法,所以有必要为遗传 操作预备一个由若干个别组成的初始集体,每个个别都应经过随机办法发生,并 别离对应研讨问题的一个解。 3、习惯度评价。遗传算法在查找过程中一般不需求其他外部信息,仅用适 应度来评价个别的好坏,并以其作为遗传操作的依据。 4、挑选。挑选操作是为了从当时集体中选出优秀的个别,使它们有时机作 为父代为下一代繁衍后代,个别的习惯度越高,其被挑选的时机就越大。 5、穿插。它是遗传算法中最首要的操作,一般分两步进行,一是对集体中 的个别进行随机配对;二是在配对个别中,随机设定穿插处,使配对个别互相交 换部分信息。 6、变异。即按必定的概率改动个别的基因链。变异操作同样是随机进行的, 其意图是发掘集体中个别的多样性,战胜遗传操作或许限于部分解的坏处。 (二)物流配送途径优化问题的遗传算法的结构 针对物流配送途径优化问题的特色,作者结构了求解该问题的遗传算法。 1、编码办法的确认。依据物流配送途径优化问题的特色,作者选用了简略 直观的天然数编码办法,用 0 标明配送中心,用 1、2、 · · · 、L 标明各需求点。 因为在配送中心有 K 辆轿车,则最多存在 K 条配送途径,每条配送途径都始于 配送中心,也总算配送中心,为了在编码中反映车辆配送的途径,作者奇妙地采

  用了添加 K-1 个虚拟配送中心的办法,别离用 L1、L2、 · · · 、LK-1 标明。这 样,1、2、 · · · 、LK-1 这 LK-1 个互不重复的天然数的随机摆放就构成一个个 体,并对应一种配送途径计划。例如,关于一个有 7 个需求点,用 3 辆轿车完结 配送使命的问题,则可用 1、2、 · · · 、9(8、9 标明配送中心)这 9 个天然数的随 机摆放,标明物流配送途径计划。如个别 129638547 标明的的配送途径计划为: 途径 1:0-1-2-9(0) ,途径 2:9(0)-6-3-8(0) ,途径 3:8(0)-5-4-7-0,共有 3 条配送途径;个别 573894216 标明的配送途径计划为:途径 1:0-5-7-3-8(0) , 途径 2:9(0)-4-2-1-6-0,共有 2 条配送途径。 2、 初始集体的确认。随机发生一种 1~LK-1 这 LK-1 个互不重复的天然数 的摆放,即构成一个个别。设集体规划为 N,则经过随机发生 N 个这样的个别, 即构成初始集体。 3、习惯度评价。关于某个个别所对应的配送途径计划,要断定其好坏,一 是要看其是否满足配送的束缚条件;二是要核算其方针函数值(即各条配送途径 的长度之和) 。本文依据配送途径优化问题的特色所确认的编码办法,隐含能够 满足每个需求点都得到配送服务及每个需求点仅由一辆轿车配送的束缚条件, 但 不能确保满足每条途径上各需求点需求量之和不超越轿车载重量及每条配送路 线的长度不超越轿车一次配送的最大行进间隔的束缚条件。为此,对每个个别所 对应的配送途径计划, 要对各条途径逐个进行判别,看其是否满足上述两个束缚 条件,若不满足,则将该条途径定为不可行途径,终究核算其方针函数值。关于 某个个别 j,设其对应的配送途径计划的不可行途径数为 Mj(Mj=0 标明该个别 对应一个可行解) ,其方针函数值为 Zj,则该个别的习惯度 Fj 可用下式标明: Fj=1/(ZjMj×G) (9)

  式中,G 为对每条不可行途径的赏罚权重,可依据方针函数的取值规划取一 个相对较大的正数。 4、挑选操作。将每代集体中的 N 个个别按习惯度由大到小摆放,排在榜首 位的个别功能最优,将它仿制一个直接进入下一代,并排在榜首位。下一代集体 的另 N-1 个个别需求依据前代集体的 N 个个别的习惯度, 选用赌轮挑选法[4]发生。 具体地说,便是首要核算上代集体中全部个别习惯度的总和(ΣFj) ,再核算每 个个别的习惯度所占的份额(Fj/ΣFj) ,以此作为其被挑选的概率。这样挑选方

  法既可确保最优个别生计至下一代, 又能确保习惯度较大的个别以较大的时机进 入下一代。 5、穿插操作。对经过挑选操作发生的新集体,除排在榜首位的最优个别外, 另 N-1 个个别要按穿插概率 Pc 进行配对穿插重组。本文选用了一种相似 OX 法[2] 的穿插办法,现举例阐明之:①随机在父代个别中挑选一个交配区域,如两父代 个别及交配区域选定为:A=478563921,B=834691257;②将 B 的交配区域加 到 A 的 前 面 , A 的 交 配 区 域 加 到 B 的 前 面 , 得 : A’=21 , B’=57;③在 A’、B’中自交配区域后顺次删去与交配区相同的天然 数,得到终究的两个别为:A”=469178532,B”=856349127。与其他穿插办法相 比, 这种办法在两父代个别相同的情况下仍能发生必定程度的变异效果,这对维 持集体的多样化特性有必定的效果。 6、变异操作。因为在挑选机制中选用了保存最佳样本的办法,为坚持集体 内个别的多样化, 本文选用了接连屡次对换的变异技能,使个别在摆放次序上的 有较大改变。变异操作是以概率 Pm 发生的,一旦变异操作发生,则用随机办法 发生交流次数 J,对所需变异操作的个别的基因进行 J 次对换(对换基因的方位 也是随机发生的) 。

  作者依据上述遗传算法编制了 C 言语程序,并对文献列出的一个某配送中 心运用 2 辆轿车对 8 个需求点进行送货的物流配送途径优化问题实例进行了试验 核算。设轿车的载重量为 8t,每次配送的最大行进间隔为 40km,配送中心与各 需求点之间、各需求点相互之间的间隔及各需求点的需求量见表 1。 表1

  依据上述实例的特色,作者在试验核算中选用了以下参数:集体规划取 20, 穿插概率和变异概率别离取 0.95 和 0.05,进化代数取 50,变异时基因换位次数 取 5,对不可行途径的赏罚权重取 100km。对上述问题,使用核算机随机求解 10 次,得到的核算成果见表 2。

  从表中数据能够看出, 10 次运转得到的成果均优于节约法所得的成果 79.5km。并且第 5 次还得到了该问题的最优解 67.5km,其对应的配送途径计划 为:途径 1:0-4-7-6-0;途径 2:0-2-8-5-3-1-0。可见,使用遗传算法能够便利有 效地求得物流配送途径优化问题的最优解或近似最优解(或称满足解) 。

  (一)在物流配送事务中,合理确认配送途径是进步服务质量、下降配送成 本、添加经济效益的重要手法。因为物流配送途径优化问题是一个 NP 难题,因 此,选用启发式算法求解是一个重要的研讨方向。 (二) 本文在树立物流配送途径优化问题的数学模型的基础上,结构了求解 物流配送途径优化问题的遗传算法。试验核算成果标明,遗传算法是一种功能优 良的启发式查找办法, 使用该办法能够便利有用地求得物流配送途径优化问题的 最优解或满足解。 (三) 本文所结构的进行物流配送途径优化的遗传算法,包含奇妙规划的个 体编码办法、个别习惯值的核算办法以及挑选、穿插和变异算子,对处理相似的 组合优化问题具有必定的参考价值。

  [1]蔡希贤,夏士智. 物流合理化的数量办法[M]. 武汉:华中工学院出版社,1985. [2 陈国良,王煦法,庄镇泉,王东生. 遗传算法及其使用[M]. 北京:人民邮电出版社,1996. [3]姜大立, 杨西龙, 杜文, 周贤伟. 车辆途径问题的遗传算法研讨[J]. 系统工程理论与实践, 1999, (6) :40-44. [4]Z·米凯利维茨. 演化程序——遗传算法和数据编码的结合 [M]. 北京:科学出版社, 2000.

  衷心感谢辅导教师李桂娥对我的精心培养和耳提面命。 本文是在教师的辅导 下完结的, 教师谨慎的治学情绪、广博的学问和忘我的敬业精神给我留下了难忘 的形象,并使我毕生获益。教师所给予我的全部,我将铭刻在心,永志不忘!

天博官网下载链接 粤ICP备14071706号-1   Powered by :www.aiorange.cn