（运筹学与控制论专业论文）模糊库存运输联合优化及其智能算法.pdf

abs t r a c t i n ven t o 口r o u t 加 g p r o b 1 e m s( 1 r p ) ar 哪 w h e nb ot h i n v e n t o 叮幼d ro uti n gare 证 c 。 印。 r at edina mo d eltoade q u a t elr c ap七 ure t hecharac七 er isti csofa di st r ib utio ns y s t em. the re ason we cons i der 恤: y i nve nt 叼 rou t in g p r o b l e ms( f irp ) i s t h atn o hist o r ic ald at a 肠a v a i 1 a b 1 e andso me d ec is io nv ar i ab1esc an，tb e e x p r essedc r 坦 p 珍 t hi s p aperconsid - er s 玩 v e n t o ryrou t ing p l o b l e ms( i rp) i nwhich cus t om d e m and ， t r avel t ，ar e fu z 盯 讥 灯 运 b l es .af 山 zy o p t in 垃 z at fo nmodel isd es i g n ed fo r f 恤 z zy l 呼 nt o r yroutin gp r o b . le lns( fir p ) w it h ti me wi叼ow， t hen we inte g r at ed油zysi m u l at l o na n da n t 一 cofo ny al- sori t hln into a b y b r i d i n t el l i 罗 ntal sori t l u nt o s o l vet b e fuz叮v e b i c l e rou 桩 鳍 m o d e l in a n 卜 c o 】 o ny a l g o ri t h n l ， a 。 招are d i v id e di nto t ow p arts ， 匆 劝 s inthe 五 r s t p a rtare use dto 6 n d p at h s o f veb icle r out in g ， and ano t her k l n dofa l l t s isd evo t e dt o 罗t the qua n t ity o f d el l v er y ， o p t 汕ajt i m e cyc l e ， v e l l l c lest ar t t i m e et c . f 访 a 】 ly，a numeri c alexa m p l e i s g i ven tos h o wthe e ffect i yelles s oft he al gorit1 i m k e y wo rds :fu z z yvar i abl e ， i nve nto ry-t r ans p o rt 甜o nm o d e l ， 坷b r i d i nte l li g e nce algo ri t h m s ， fu z z y p r o gram m i n g 声明 本学位论文是我在导师的指导下取得的 研究成果， 尽我所知， 在 本学位论文中， 除了加以 标注和致谢的部分外， 不包含其他人己经发 表或公布过的 研究成果， 也不包含我为获得任何教育机构的学位或学 历而使用过的材料。 与我一同工作的同事对本学位论文做出的贡献均 已在论文中 作了明确的说明。 飞 ，咭 人 研 究 生 签 名 : 少 干 型工州 年 ， “ 如 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档， 可以借阅 或上网公布本学位论文的全部或部分 内容， 可以向有关部门或机构送 交并授权其保存、 借阅 或上网公布本学位论文的全部或部分内 容。 对 于保密论文，按保密的有关规宁和程 序朴理。 研 究 生 签 名 : 呼红叶似日 硕士论文模糊库存运输联合优化及其智能算法 第一章引言 ll 问题的提出及描述 在 现 代物流系 统中 ， 物流的 各项活动 ( 运输、 保管、 搬运、 包装、 流通加工等) 之 间 可能 存在 ” 效益背反 ” 现象， 所谓 ” 效益背反 ” ( 肠ade- o 幻是指， 对于同 一资源( 例如成 本 ) 的 两 个 方面处于 相 互矛 盾的 关 系 之中， 想要 较多地达到 某 一目 的， 必 然使另 一方面 的目的受到部分损失” 。针对现代物流系统中，库存与运输之间可能存在” 效益背反” 现 象，库存与运输联合优化问题所追求的目 标是在综合平衡库存费用和运输费用的前提 下，来优化物流系统，确定系统范围的库存策略和运输方案，才能平衡这两个” 效益背 反” 。因为，库存和运输决策是相关的，若使用快速运输方式，运输成本高，而库存量 低; 另一方面，如果用较慢的 运输方式，运输成本低，而库存量却高。 所以，当确定 运输方案时，不能过分追求大批量运输所带来的批量折扣，这样势必增加了整个系统 的库存费用: 在确定库存策略时，也不可以将运输费用简单的作为一项固定费用来处 理，而是作为直接影响配送频率和库存分配的可变费用。在这样一种对立模式的格局 下，库存与运输之间毫无联合优化意识，一方所得必为另一方所失，双方都追求自身 利益的 最大化，最终导致两败俱伤。为此， 库存与运输之间的” 效益背反” 现象应转向 一种新的合作模式一库存与运输联合优化，以求双方的共同发展使得系统最优，物流 成本最低。 现代物流区别与传统物流主要表现在:现代物流把传统物流中分开的诸如 运输、存储、装卸和信息处理等环节有机的结合在一起，进而更加全面地，更加系统 地研究和观察总体的物流活动，其中物流的运输和存储是物流系统中最重要的两个环 节，占 物流费用支出的决大部分， 现在主要的研究还是分别对待进行研究，但将两者 结合在一起来研究的很少，现在发布的计算机辅助管理系统的应用软件中，还几乎是 单独进行研究的，将如此紧密联系又如此重要的两个环节结合成一个问题来研究，具 有极大的理论和应用价值。现在物流很强调专家的知识，就是决策者的经验，就会引 人模糊性，由于缺少大量的历史数据，所以有很多的决策变量就无法准确地刻画，例 硕士论文模糊库存运输联合优化及其智能算法 如客户的需求量还有运输的费用等，产生了更多的模糊性，研究它就需要用模糊的相 关理论， 如可信性理论等，这就更加贴近现实情况。 在理论上运输问 题和库存问题都 是运筹学中的两个重要的研究领域，关于它们的研究都极为丰富，但解决运轿库存联 合优化的资料却很少，涉及这一领域的许多问题还需要进一步给出理论上的支持。在 现实的物流管理中，现代企业的大型化、国际化趋势越来越明显，如沃尔玛，要统一 管理全球3 5 00个超市，此时如何调派车辆和分配库存，谋求最大利益，客观上也要将 两者结合起来作为一个大的系统来进行研究。 无论是运输问题还是库存控制问题，都是经典的运筹学问题，关于它们的参考 文献数以千计，但将两个问题汇集在一个系统中进行研究用一个模型进行刻划这两 个互相矛盾、而在物流系统优化中又如此的重要的领域，则是一个比较新的研究领 域。 fe d ergr ue n 和 zi p ki n 在1 9 84年的文章中 ，称他 们是首次用同 一个模型同时来表述 这两个问题。 不同领域的学者从不同的角度对这类faj题进行了研究，基于前人的研究，库存 运输联合优化问题主要是研究这样的一类问题:在同时考虑运输和库存的相应要素的 前提下，如何有效而经济的组织配送活动，在有限 ( 或无限)周期内，将一种 ( 或多 种)货物从一个 ( 或多个)供货点配送给一个 ( 或多个)客户，或其相反过程。 在同时考虑库存和运输问题去设计或优化一个实际的物流系统时，系统的决策者 必然要对如下三个主要问题进行决策: (l)时间或频率周期长度已确定，需要在什 么时间为哪些客户送货，如时间周期未知，则决定以什么样的频率为客户提供服务; (2) 配送量在了 解客户的需求之后，确定服务客户的配货量 ( 或对供应商的定货量) ; (3) 运输方式和策略采取什么样的方式:公路、 铁路、 还是海运，空运，针对某一种运 输方式，是采取直达还是零担运输，如才用零担运输方式时，该如何优化行驶路线。 前两个方面是库存，第三个方面是运输的问题。在平衡运输和库存相关因素时，把两 个复杂的问题集成到一起而形成库存运输联合优化问题，是一个更加复杂的问题， 是一个n p 一 h a r d问题，其复杂性不仅表现在数学模型的建立，也表现在有效算法的设 硕士论文模糊库存运输联合优化及其智能算法 计。 l z 国内外研究状况 经典的路径问题考虑包括路径长度、运行周期、车辆运载的能力、 协调性、时间等. 库存考虑的因素包括存储能力、消耗特征、脱销后果等 车辆 。库 存运输问题( i nv e n t o ryro ut in g p ro b le ms) 我们简写成 (l rp，s) ， 相关文献第一次出现 在1 97 山 ( 151131 】 ) ， 及 d e r g r u enan d z ivkin !1 刘 ( 1 9 84 ) 在处 理单 周 期 ， 单商品 ， 零售商的 需 求是随机变量， 不考虑定购费用情况下， 在同一个模型考虑分配和车辆路径问题。他们 的方法把问 题分解成两个部分: 库存分配和车辆路径问 题洞题的 解是通过构造和启发 形 成的 . g ol de n etal . 11 勿( 19 84 ) 研究过带有部 分库 存的 路径调 度问 题并且 提出 一种在 每个销售点指派紧急指标的启发式方法， 按照每个销售点的紧急 指标与最佳配送时间的 比 来进行选择服务的点; 紧急指标小于某一界限的销售点就被排除在服务行列中， 带有 时间限制的车辆的路径是通过重复构造， 然后通过限制在配送时强迫每个销售点存满货 物， 分解成一 组可行路 径。 c hi enetal . 11 01 ( 19 89 ) 考虑是同 样的问 题， 不过他使用的 拉 格朗日 共扼梯度法进行求解。 d r ore t a l . 【 1 1 ! ( 1 9 8 5 ) 幼d d r ora n d b a l l l l 2 1 ( 1 9 8 7) 在 短的 计划编制周期内 考虑有 日 需求m卫 ，s问 题，他们利用销售点脱销概率，平均配送成本， 和预期脱货费用去获 得每个销售点最佳的补货时间，如果这个最佳的补货时间在短计划编排周期内，则销 售点就被选择服务，然后在计划编排周期内，若当天被换成最佳的配送时间计算在 将来期望增加的费用，一个利用整数规划解决决定每辆车的最佳配送点，最佳配送 时间，使得包括运输费用在内的总费用最小。相关扩展此种思想的文献有:d ror 叨d 跳灯ls1 ( 19 86) 幼d j a u le 七 etal份 叨(l 朋7 ) . 丫 妞 n o and g er ch ak娜1 ( 19 89 ) 分析的 直 接 装船运输的情况。他们假设每辆装运车辆有固定的费用，在他们单周期的模型中，只 有一个售卖者提供多种商品给特定的点，这样极大的简化运输问题，避免了路径的设 计 a ni lyand 死 de r gr u e n l112 ( 1 9 90， 19 93 ) 考虑 在有限 的 时间内 考 虑客户固 定 书求率 硕士论文 模糊库存运输联合优化及其智能算法 的运输库存问 题，目 标是决定库存准则和行程安排来最小化运输费用和库存费用。运 输的路径是通过把销售点分成不同的区域中形成策略集而决定的， 把销售点划分成不 同的区域，使得每个区域的销售点的需求大约等于每个运输车辆的荷载量。注意到每 个销售点可能同时存在于一个或多个区域，但是其确定需求应给分配给某一个区域。 不能保证存在于多个不同的区域的同一个销售点进行协调服务。假设当一个区的销售 点 服务了 ， 那 么 这 个 区 域所 有的 销 售点 都被 服务。 利用 类 似于111冈 思 想， g 心ego 二d si 1y lc l l卜 l e v i lls ( 19 90 ) 分析比 较了 在一 个 库存中 心， 多客 户的 配 送系 统， 且 有固 定的 消 耗 率， 不 允 许 缺 货 和 订 货的 ir p ，5 ， 他 们 假设 : 不 限 制 车 辆 的 数量， 每 个车 辆 有 额定 荷载量。 他们研究了 直达运输和零担运输 ( m ut i 一 st 叩) 策略的应用效果，其目 标就是 最小化费用 ( 运输费用，配送处理费用，线性库存费用)，并且指出，当每个客户的 需求远低于车辆的 荷载量， 直担运输是一个不好的 策略。 bralne l and s 恤c h i 目 levilr (l 995 ) 考虑一个 库 存中 心提供 不同的 商品 给一组 销售点， 且 每个 销售点的单位时间的 需求是固定的运输库存问题，目 标是决定车辆服务时间和指定车辆服务销售点，使得 单位时间的花费最小，其中花费包括运输费用，配送处理费用，每个销售点的线性库 存费用。为了解决这个问题，他们把问题简化成设备选址问题， ( c c l p )其分割位 置到不相交的集合，这些集合在运输库存中变成固定的划分，类似这样的思想的文献 有01101a 周 。 以 上都是考虑客 户的 需求要么 是固 定常量， 要么是随 机变量，总的 说 来，现实中有很多问 题是缺少大量的历史数据的，许多决策变量就无法准确地刻画， 例如客户的需求量、 运输的费用等，产生了许多的模糊性， 研究它就需要用模糊的 相 关理论，本文利用可信性理论对运输库存联合优化问题进行刻画建模及求解等。 关于侧重点不同的此类问题的有效算法启发式算法也是被研究的一个热 点。 e r l ls t 和p y k el 司 ( 1 9 9 3 ) 为 客 户 具 有随 机 需求的 两 级 物流 系 统设 计 一 种确定 最 优 送 货频率的 启 发式 算 法， 文献叫 设 计的 启 发式 算法 用于同 时 优化经 济生 产批量问 题， 运 输问 题和经济订货批量问题，该文指出这3 种问题结合到一起的问题形成了一个即不凸 也不凹的非线性规划问题，采用的广义简约梯度法和他们设计的启发式算法得到的解 硕士论文模糊库存运输联合优化及其智能算法 的近似，并得到的结论是当确定库存和运输策略时，应该采用联合优化思路。另外一 些学者重点讨论的重点一种称之为基于固定划分原则 ( fi x 阅p a rt 允 i onp ol icies)的方 法 ， 此方法就是预先将客户划分到不同的区域中 ， 形成策 略集圣 . 在考虑车 辆运载能力的 情况下， 垂中的最优策略是指具有最小平均总库存和运输费用策略， 采用固定划分原则 的 方法 解决 库存与运 输 优 化的问 题的 过程分为 3 个部分 : ( 1)对研究的区 域的 所有的客 户 进行划分 ， 形成一组 包 含某些客户的子区域; ( 2 ) 对每一个子区 域， 采用求解t s p 问 题的 算法确定最优的 车 辆行驶路线及路 线长 度; ( 3 ) 将 运费 看成一固定费 用， 采用变 形 e o q 公 式确定每一个子区域的 最优配送量和配 送频率。 但这 种方法不能保证存在于 多 个 子区 域的同 一客 户 进 行协 调 服务等。 还 有 其他的 方 法 如 分支定 界 方 法 等协 3j 。 总的 说来， 这些方法实质上并不是全局最优的方法， 本文采用蚁群算法来解决。本文是首次 研究模糊条件下的运输库存联合优化问题，本文考虑的配送系统包括一个库存中心和 许多 分 布在 不同的区 域的 客户( 零售商 ) ，由 于 很多 不 确定的因 素， 每个零 售商的需求 是一个模糊变量，所有的商品都是由 一组有限荷载量的车队经过最有效的路径将库存 中心的货物配送到每个客户，并且假设不考虑库存中心的贮存费用，只考虑客户的库 存费用。我们的目的就是决定可行的补给策略 ( 最优的系统补给周期、库存策略、运 输路径等) 去最小化长期 平均运输和库存费用，即 利润最大化。 硕士论文模糊库存运输联合优化及其智胎算法 第二章预备知识 2.1 可信性理论 本 章介绍一下可 信性理论及 其基本概念。 2 “比娜1 在1 9 65通 过隶属 度函数提出 模 糊集理 论， 模糊集理 论已 经得到长 足的 发 展， 模糊技术几乎渗 透到了 所有的 领域， 如 控制 论 ， 智能 系 统， 信息 科 学等。 为了 度量一个 模糊事 件， z adeh ( 1 9 78 ) !38 提出了 可能性 理 论 ， 并且很多学者进行深入的 研究， 如d uboi 。 和prade 14 。 但是， 可能性 测度没有自 对 偶 性， 而自 对 偶性 在 理 论 上 还是 实践 上 都 是 非常 重 要的。 l i u( 2 0 0 2 ) !24 1 给出了 满 足自 对 偶性的 可 信性 测度。 li 和li u ! 2 3 1 给出了 完善的 研究模糊性的 公 理体系。 为了 表述可 信 性定义的 公理化体系， 假设 e 是一 个非空 集， 并且双 e)是0 上的 幕集， cr a 来表示每个 模糊事 件a 将出 现的 可 信性， li 和li u l23 给出了 以 下的四个 公理: 公理ic r e =1 . 公理 2 卜 c r a 三cr b 当 acb ， 公理 3 . c r 是自 对偶的，即 cr a 十cr 矛 =1 对任意的 ac 到 e) 公理 4c r u 、 击 =s u rc r a 对任意的 人当 cr a 0 .5 。 定义2. l i任 如2 习 刃 夕 假设e 是一个非 空的 集合， 并且州 e)是e 的 幕集。 如果c 满足上 面的四 条公理， 则 称作为 双 e)上的 一 个可 信性测度. 定义2. 1. 2(l 她招 动 假设e 是一 个非空的 集合， 并且双 e) 是 e 的幕 集。 如果cr是可 信性 测 度， 则三元组( e ， 到 e)， c r)称为 可信性空间。 定义2 l 3邝 如牌 不 刀假设 右 为 一从 可 信性空间 (e， 双 0 ) ， c r)到 实 数集的 一 个函 数， 则 称( 是一个模糊变量。 硕士论文模糊库存运输联合优化及其智能算法 定 义2. 1 .4(l 她阁刀假设 ( 是 一 个 定义 在可 信性空间( e ， 烈 e)，c r)上的 模糊变量， 则 它的隶属度函数定义为 拜 ( 二 ) =( z c r 心 =二 ) 人 1 ， 二 任况 ， 注 2. l i如果模糊变量夸 的隶属度函数是拌 ， 那么对于任意的 集合bc乳 cr 若 任 b 一万介 u p 。 闭 + ， 一 ， up 。 动 定 义2 .1.5(l 如周刀假定 亡 是一 个 模 糊 变 量. 那 么 石 的 期望值 定 义为 、 一 户价恤 一 丘 cr 。 减 只要上面的积分至少有一个是有限的。 例2. 1 . 1 假定 梯形模糊变量右 =( r ， ， 几 ， 勺 ， 八 ) ， 那么它的期望值是 e 仍一 皇 土 全 土 竺 鱼 士 生 . 4 定义2. 1. 6(z她牌 召 刀假定 石 是一模糊变量， 且。 任 。 11 。 则 条 叩 ( 的=5 即 川 c r 心 之好七。 称为模糊变量( 的a 一 乐观值， 公 时 ( a ) 二in f : c r 若 三: 全。 称为 模糊变量( 的a 一 悲观值。 2. 2 模糊模拟 在运筹学、管理科学、信息科学及工程等众多领域都存在客观的或人为的不确定 性，这些不确定性表现形式是多种多样的，如随机性、模糊性、粗糙性、模糊随机性 以及其他的多重不确定性。不确定规划是在不确定环境下的优化理论，包括随机规 7 硕士论文模糊库存运输联合优化及其智能算法 划、模糊规划、粗糙规划、随机模糊规划等。 从建模理念的角度来说，不确定规划处 理 不确 定函 数有三 条 基本 途径: ( 1) 从 期望值的 角度出 发。 用不 确定函 数 的期 望 值分 别 代替原来目 标函 数和约束条件中的不确定函 数， 建立期望值模型。 ( 2 ) 从可信性测度 的角度考虑。当约束条件中含有不确定变量且必须在观测到不确定变量实现之前作出 决策时，采用一种原则:允许所作决策在一定程度上不满足约束条件 ( 不考虑违反约 束条件的惩罚)，即只要求使约束条件得到满足的机会测度不小于预先给定的置信水 平。 ( 3) 极 大化事 件实现的机会 ( 如概率、 可能 性、必要性、 可信性、 信赖性等)。 本 章给出 计算模糊事 件可能性， 可信性， 期望值， 关键值等相关算法。 通过例子来讲述模糊模拟计算模糊事件的可能性。 例 么2 . 1假设 l 二cr f (f) 三0 分 别从 e中 均匀 产生 人 ， 使 得c r 么 之。 ， 并 定 义 雌二( z cr 入 ) 八 1 ， k =1 ， 2 ， 一， n ， 其 中 : 是 个充 分小的 数. 可信性c r 了 ( 幻三0可以由 下式 估计 得到: : 一 合 ( ，黝 、 .， (; (“ 、) 、 。 + ;咒 卜 、 !， (; (、 )卜 ” ) 模糊事件的可信性模拟如下: 步骤1 步骤2 步骤3 分 别 从 e 中 均 匀 产 生 人 ， 使 得 cr伊 公2 号 ， 其 中 。 是 个 充 分小 的 数， 无 二1 ， 2 ， 置咋二( z cr 人 ) a l ， k =1 ， 2 ， ， n 返回l. 通过例子来讲述模糊模拟计算模糊事件的数学期望。 例2. 2. 2假 设 f:缈、俨是 一 个可 测函 数， 七 二佰 ， ， 6 ， ， 玩 ) 是可 信性 空间 ( e ， 烈 e)， c 约 上的 模糊变 量， 则f( 6 也是一 个模糊变量， 它的 数学期望定义 为 、 () 一 关 一 cr f( 、 、 一 左 cr f( 、 恤 硕士论文模糊库存运输联合优化及其智能算法 下面 给出 一 个 模拟 过 程 来 估计 司f 传 )j ， 关于自 变 量为 模 糊变 量函 数的 数学 期望结果可以 参考( liu 和 z b u )1 2 6 ( 2 0 0 7) 、 ( z hu和j i ) 14 1 1 ( 2 0 0 6 ) 分别从 e中 均匀 产生 么 ， 使得 c r 人 全。 ， 并定 义峡二( z c r 凡 ) 八 1 ， 无 =1 ， 2 ， ， 万 ， 其 中 。 是 个充 分 小的 数。 对 任 意的 ， 全 。 ， 可 信 性 c r j 化 ) 全呼 近 似 等 于 诌月产，、n了 月叻 1翌 爵 蛛 f ( ( (久 ) ) 七 r + ， 男 呈 k 1 一 咋 if ( ( ( ) ) h认 对 任意的 : 0 ， 可 信性 c r f( 0三呼 近似等 于 叠 ( 爵、 了 (。 (、 ) : + 1毁“ 一 、 ， “ “ “ ， 模糊事件的数学期望模拟如下: 步骤1 步骤2 步骤3 步骤4 步骤5 步骤6 步骤7 步骤 8 置e =0 分 别 从 。 中 均 匀 产生 入 ，使得 c r 人 全号 ， 并 定 义咋= ( z cr 几 1 ) 人 1 ， k 二1 ， 2 ， ， n， 其中 。 是 个 充分小的 数。 置a =j “ ( 6 1 ) ) 八 八 j “ ( 6 二 ) ) ， b =f “ ( 夕 1 ) ) v 一v f “ ( 断) ) 从ia ， 习 中 均 匀 产生 r 。 如果， 七。 那么 e 一 e +c r f “ ) 2， 。 如 果 ， 七 。 那么 e 一 e + crf(e) 三 r 。 重复步骤4 至步骤6 共n次。 e f ( ( ) =。 v o +b 八 。 +e ( b 一a ) /n 0 下面通过例子给出 。乐观值求解模糊模拟算法。 例2. 2. 3 假设 j:缈*缈是一 个 可测函 数， 若 =(cl， 6 ， ， 氛 ) 是 可 信性空间 ( e ， 域 e)， c f 上的 模 糊向 量 ， 则 f ( 幻 也 是 一 个 模糊变量，我 们 通过 如下 过 程找 到 最大的 j ， 使 得不 等式 c r f ( 若 ) 全 几z a 硕士论文模糊库存运输联合优化及其智能算法 分 别 从 e中 均匀 产 生 入 ， 使 得 c r 人 全 : ， 并 定 义 咋二( z c r 入 ) 八 1 ， k =1 ， 2 ， ， n ， 其 中 : 是 个 充 分 小的 数。 对 任意的 ， ， 可 信 性 c r j ( 日全 呼 近 似 等 于 委 ( ，黝、 ，了 (; (“ 无) : 卜 1黝 一 、 !了 (; (、 ) 0 ， 随 机 产 生一个 方向 节选择 丫 叭 一 : 如果决=叭一 1 k=1 ， 2 一 仇. 1.、 -一 运输费用为: 艺取(x ， ， ) 心 k ，1 在每一个配送周期t内， 在客户 的 存储费用为: 叭+q 在每一个配送周期t内， 在客户玄 的由于缺货罚值费用为: p ( 呐) 0 ， 扒 化 t一伽 +q ) ) ， 如果盘 t叭十认 落 =1 ， 2 n 。 n 了.，、. -一 车辆k 所服务的客户总的存储费用: 从(x ， 功= 州叽 、 _ 1 十 : ) 十 h ( 目 、 _ ， : ) +.二 十 h 怀， ). 车辆k所服务的客户总的由于缺货罚值费用: 凡 伪 ， 刃二 p ( 叽 外 _ 1+ ， ) + p 帆。 _ 1+ : ) 十 十 到 、 、 ) 在客户坛 处的销售收入: c* 心 * 叭如果条 t叭+吼 坛 =1 ， 2 二几 j.，凡.、 一一 欣 车辆k 所服务的客户总的销售收入: 峡( ， 功= 饥 二 。 _ ， 十 ; 十 、 卜 1+ : 十 十 m 、 硕士论文模糊库存运输联合优化及其智能算法 我们令 尸 ( 二 ， ， ， ， ， 。 ， t)一 e 风( 二 ， ， ) 一 1几( x ， ; ) + 凡 ( 二 ， ; ) + * (二 ， ， ) 1 . 显然f (x ， 夕 洋 ， 。 ， t ) 为 决 策变量 : ， ， ， t ， 。 ， t 的函 数. 3.2 模糊期望值模型 如果决策者目的是得到最大期望收益的决策，我们可以给出如下期望值模型: e f ( x ， 夕 ， 云 ， 。 ， t ) ( 1 ) c r 关 ( 二 ， ， ， 忿 ) 任 吟， 认 ， =1 ， 2 ， 二。 全a ( 2 ) 盗 e叽三饭( 3 ) j =脚 _ 1 十1 ()(s)(6)(v)(s)(0) 姚+吼 三q t20 0 二夕 1 三势三 三创 m 一 1 5n 1 三劣 三几 ， 么 二1 ， 2 ， 二 ， n 升尹粉 ， 尹 j ， 礼 j =1 ， 2 ， ， 。 从 ， 功是整数， ， j 二0 ， 1 ， 2， ， 九 狱1 ms.i 一llee 其中 ( 1) 表示的 纯收 入的数学 期望值最大; ( 2 ) 表示所有服务车 辆都 在客户的时间窗口内 到达的可 信性不小 于给定的 常 数粼 3 ) 表示每个车辆配送的 货物的量不能 超过车辆荷载 量; ( 4 ) 表示在客户 的 配 送的 量和 起始库存的 量之和不能 大于其库存的 最大上限; ( 6 ) 最 佳的 配 送周 期 应 大 于 0;(6 ) ( 7 ) ( 5) ( 9 ) 是 关 于决 策 变量的 一 些限 制 ， 本模型的决策变量为 : 二 =( 赴， 勿， ) ， =( 加 ， ， : ， 烧 ， 如一 : ) ，云 =仓 1 ， t : 硫) ，。二 沙 ， ， 吻臼 动 ， t ， 求出 车辆出 发的 时间 ， 最佳的 配送周 期 ， 每个 销售点 的 配送量以 及最 佳的车辆服务路径使得纯收入数学期望最大。 硕士论文模糊库存运输联合优化及其智能算法 3 3 极大化乐观值模型 有时候，决策者希望在约束条件以一定的置信水平成立的前提下，极大化目 标函 数 的 乐 观值。 也就是说 ， 决 策者 希望销 售收 入不少于 户 的 事件以 置 信水平 刀 成立的 前提 下， 最大化收入户 的决策。 ( 1 ) c r f ( 二 ， ， ， t ， 。 ， t)之户 全 尸( 2 ) c r 人 ( x ， ， ， ) 任卜 ， 久 1 ， 云 二1 ， 2 ， 。 之a ( 3 ) 间(s)(e)(s)(0)10) f知 艺吟5帐 j =脚几 _ 1 + 1 呐+q 三 t 0 0 三玩三功三 三骗一 1 三” 1 5众三介 ， 坛 二1 ， 2 ， ， n 二 尹勺， 公 尹j ， 落 ， j 二1 ， 2 ， ， 。 丸 ， 协是整数， ， j =0 ， 1 ， 2.， ， 几 其 中 ( 1) 表 示 极 大 化 纯 收 入的 乐 观 值; ( 2 ) 表 示 销 售 收 入 大 于 夕的 可 信 性 不 小 于 给 定的 置 信水 平 口 ， ( 3 ) ( 4 ) ( 5 ) ( 6 ) ( 7 ) ( 8 ) ( 9 ) ( 1 0 ) 限 制条 件及决 策变量同 模糊期望值模型。目 标是求 出车辆出发的时间，最佳的配送周期， 每个销售点的配送量， 以及决定出最佳的车辆服 务路 径 使 得 销售收入不 少于 夕 的 事件以 置 信水 平 口 ， 最大 化收入 户 的决 策， 求出 车 辆出 发 的时间， 最佳的配送周期， 每个销售点的配送量， 以及决定出 最佳的车辆服务路径。 3.4 目 标规划模型 有时候，决策者对最大收入有一个目 标值6 ， 希望目 标函数的值与与理想值的偏差 硕士论文棋糊库存运输联合优化及其智能算法 最小。 下面我们给出如下模型: m 恤 ( 。 * d + v o +， * d 一 v o ) 5 . 公 . ( 1 ) (a)(s)()(s)(0)门(s)(0)10)11) 召 if ( 二 ， 犷 ， ， w ， t ) 1 一 b =d + b 一 e !f ( 二 ， 夕 ， t ， 。 ， t ) 1 =d - c r 人 ( 二 ， 夕 ， t ) c卜 ， 瓦 ， 云 =1 ， 2 ， 。 全a 朴 艺吟三奴 j = 如卜1 + 1 叭十q 三q t全0 0 三协三势三 5如一 1 三” 1 三众丛几 ， 乞 =1 ， 2 ， ， 几 升尹粉， 尹j ， ， j 二1 ， 2 ， ， ” 二 ， 功 是 整数， ， j =0 ， 1 ， 2 ， “ 其中d + v o 表示收入数学期望偏离目 标值b 的正偏差， d 一 v o 为收入数学期望偏离目 标 值b 的 负 偏 差， v 表 示正 偏 差的 权重因 子， ， 表示 负 偏差的 权重因 子， ( 1) 表示 极小 化 纯 收 入 数学 期 望 与 理 想 收 入的 偏差; ( 3 ) 侈 ) ( 5 ) 但 ) (z)( 5) ( 9 ) 限 制 条 件 及决 策 变 量同 模 糊 期望 值模型。目 标是 求出 车辆出 发的时间， 最佳的 配 送周期， 每个销售点的 配送量， 以 及决 定出最佳的车辆服务路径使得纯收入数学期望与理想收入的偏差最小. 硕士论文模糊库存运输联合优化及其智能算法 另外我们也可以考虑如下模型: 嗯 n ( ” * d+v o + “ * d-v o ) ( 1 ) 宫t (s)()(s)(6)(v)(s)(0)10)11) cr f 沙 ， 夕 ， ， 。 ， t ) 一 b sd+ 之 刀 + c r b 一f 件 ， ， ， t ， w ， t ) 三d 一 七口 - c r 几 ( 二 ， 夕 ， 忿 ) ia， 瓦 1 ， =1 ， 2 ， 。 全a 旅 又叽 三休 j =如 _ 1 + 1 叭十q 三q t全0 0 三叭 三如三 三习 m _ 1 感” 1 5么 二” ， 云 =1 ， 2 ， 一 ， ” 二 尹粉， 尹j ， ， j =1 ， 2 ， 为 ， 功 是 整 数j ， 了 =0 ， 1 ， 2. ， n ， n 其中 d+v 。 为目 标( 纯收 入 ) 偏离目 标值 b 的 口 + 乐 观正 偏差， 少v o 为目 标( 纯收入) 偏离 目 标 值 6 的 广乐 观负 偏 差， ( 1 ) ( 3 ) ( 4 ) ( 5 ) ( 6 ) ( 7 ) ( 8 ) ( 9 ) 同 上. 1 g 硕士论文模糊库存运输联合优化及其智能算法 第四章棍合智能算法及实例 4.1 混合智能算法 本节利用结合模糊模拟和蚁群算法组成的混合智能算法来求解上述模型。由于本 模型的 复 杂 性， 所求 决 策 变量比 较多， 而 且类型 不同 ( 离 散 型 和 连续性 ) ， 采 用两类 相同 数 目 的 蚂蚁， 第一类蚂蚁负责最优路径的 选择， 另外一类蚂蚁负责选择车 辆最佳的出 发时 间，最佳配送量， 最佳运行周期，最佳服务路径等。 第一类第无 只蚂蚁爬行所寻找的解 和第二类对应的蚂蚁爬行所寻找的解组成本模型的 一个解， 我 们叫 第k 对蚂蚁爬行解。 在给出 蚁群算法之前， 先介绍一下把模型中的车辆选择问题转化为经典的旅行商 问题编码过程，而蚁群算法已经非常成功的解决了旅行商问题。如上述假设有n个 客户， k 辆车，则我们就假设有。 +k 个节点，我们举个例子来说明一下，如果库存 中心设为0 ，有6 个客户编码设为1 ，2 ，3 ， 4 ， 5 ， 6 ，服务车辆有三辆车，我们增加 两个节点，都设为0 ，由于车辆都是从库存中心出发，最后还回到库存中心，所以 第一个编码始终设为 0 ，所以编码为0 ， 1 ， 2 ， 3 ， 4 ，5 ，6 ， 0 ， 0 . 然后按照旅行商问题 遍历，不妨假设求得遍历节点的顺序。 ， 3 ，4 ， 0 ，1 ，2 ， 5 ， 0 ，6 ，则3 ， 4 是第一辆 车服务的客户，1 ，2 ，5 是第二辆车车服务的客户，剩下的就是第三辆车服务的。 如出现0 ， 3 ， 4 ， 0 ， 0 ，1 ， 2 ， 5 ， 6 的情况则表示第一辆车服务客户3 ， 4 ，第二辆车不 用，1 ， 2 ， 5 ， 6 是由 第三辆车服务。 假设 咭(t)第 一 类蚂 蚁在 t 时 刻节点 到 j 之间的 信息 量 ， 在 初始时 刻 各 条 路径 上的 信 息 量 相 等 ，并 设 咭 ( 0)= con就 ， 蚂 蚁 k k =1 ， 2 ， ， 。 ) 在 运 动 过 程中 ， 根 据 各 条 路 径 上 的 信息 量决 定 其转 移的 方向 . 这里 用禁 忌 表 云 助 牡 成 k =1 ， 2 ， ， 二 ) 来记 录 蚂 蚁 k 当 前 所 走 过的 城市， 集 合随 着 亡 叻 翻 、 进化 过程 作 动 态调整。 在搜寻 过 程中 ， 蚂 蚁根 据 各 条路 径上 的 信 息 量 及 路 径 的 启 发 信 息 来 计 算 状 态 转 移 概 率 。 垮(t)表 示 在 时 刻 蚂 蚁 k 由 元 素 转 移 到 元素j 的状态转移概率 硕士论文模糊库存运输联合优化及其智能算法 丸= 气 ， 仍 艺几 ，a ( 才 ) a c公止 蒯 曰 ( 4 1 ) 其中 ，al l 、e 橄 二 所 有 节 点 一 ta 阮 好 表 示蚂蚁 k 下 一 步 允 许 选 择 的 城市 ; 假设 嚼 (t)第二 类蚂 蚁 ， 类似 于 第二 章第 3 小 节蚁 群 算 法 的 处 理 方法 ， 不 妨假设向 量 。二( 界认 ， 如 ， ， 坛 ， 叱， ， 叽) 对 应的 分 量 所 处的 区 间 为 卜， 叼 ， 二1 ， 2 ， ， 。 + k + 1 ， 我们假设 。包含于超几何体 l= ( 界tl ， 儿 ， ， 红 ， 叽， ， 叽) c况 叶 k+ 1 a 三认 ， = 1 ， 2 ， ， 。 + k +1 把la.， 叼均匀的 分为 八子区 间 ， 其中 八为正 整数， =0 ， 1 ， 2.二， 氏 这 些 子 区 间 附 加 上 信 息 素 蟋 0)= cdn时 。 蚂蚁爬行构造解顺序为 t一甸一 一奴一叻 一 一叽. 对于 给定的 点 a 已 况 ( 称 为 初始点 ) 不在 l 中 ， 令ao二bo=a ， 叱=1 ， 连接 a 和协 1 ， 01的 所有 的 子区间 ， 连 接每一个 ia.， 叼 子区间 和 所有阮+1 ， 氏 +1 ， =1 ， 2.二， 。 +k 的 子区间， 不妨 假设 在构造 好序 列忆云 : ， 叭 一 卜 2 ) 后 ， 步 将以 如 下概率 在 叭 _ * 一 ，所 在区间 ia.， 划中 按 如下概率选取子区间， 扒j= 几 j (t) f盛 艺几 ，* ( 云 ) k =1 ( 4. 幻 从选取得子区间随 机产生一 个点 t， ， 然后把这个点 变 异成为 叭 一 * 一 1 ， 使得叭 一 卜1 仍然 在 区 间 两， 划 ， 其 变异 过 程 如 下: 给 定 一 个 数 m 0 ， 随 机 产生 一 个 方向 不选 择 m m 使 得 叭 一 。 一 1 二。 十 邝 m a ， b. . 如 果新的 序列不 可 行 ， 则 蚂 蚁停止 运 行， 它的 爬行结 束。 信息素更新: 为了 控制信息素变化范围，我们给出 每条路径上最小信息素为: 丁 恤 ， 我 硕士论文模糊库存运输联合优化及其智能算法 们使用如下信息素更新设 。 妙 15为当 前最 优解 宕 ( 1 一 p)* 吮( 亡 一 1 ) + 户 * 对应的目 标值 了 刀 +四归 ) ，当( 灯 ) 已 宕 ( 4 . 3 ) ( 1 一 夕 ) * 瑞( 卜 1 ) + 夕 * 、n 其它情况， 了.j、.t 一- 叭封少 心 其中 助(t)表 示 信 息 素 挥 发 系 数 ， 0 夕 ( 宫 ) ， 如 可 取 州) ， 纂恶 . 由 信 息 素 更 新 方 法 ， 易 知 ha 喃 (t) ， 一 ， 2 取 上面 信息素 更新， 类似于 t . 5 七 ue ze l a n d m . d or 馆 0巧 证明， 我们有 如下结论: p r o p o s it fo nl考 虑由 ( 4. 3 ) 给出 的 信息 素， 则 1 . 对 任 何 诱 ， 有 : 溉， (t)“一 阮， + 夕 ( 。 中 ) 1 ， 1 =1 ， 2 . 么找 到 最 优解 后， 对 应 最 优 解 路径上 的 信息 素 尹 恤) ， 1 =1 ， 2 单 调 增 加 ， 且 v ( ， j ) 。 * : 恩 二 * ( 忿 ) = 份 =阮面+ 夕 ( 5 币 ) ， 1 =1 ， 2 . t h eore ml 根据(.a) 信息素方法 ， 蚂蚁转移概率根据(.1) (.2 ) ， 假设 尸 * ( 劝为算法在 前忿 次迭代中至少找到一次最优解的概率。那么， 对任意小的 0 和充分大的迭代次 数 艺 ， 有 p (亡 ) 全 1 一 ， 且 溉p. ( ) 一 1 下面我们给出混合智能算法。 混合智能算法_ _ 步骤1 初 始化参数，令时 间 t =。 和循 环次数nc=。 ， 设置 最 大循环次数为 入 喻万 ， 将仇只第一类蚂蚁均匀地放到介 十k 一1 个节点上，并且初始节点之间 的 信息 素 ，(t)= con时 ， 其中 cons 七 表示 常 数， 且 初 始 时 刻 场( 0)=仇 将。只第二类蚂蚁均匀的放到连续变量t 的子区间上，并初始化信息素。 步骤2 循环次数凡*nc+1 步骤3 设禁忌表索引号k 二0 。 硕士论文模糊库存运输联合优化及其智能算法 步骤4 步骤5 步骤6 步骤7 步骤 8 步骤9 置第一类蚂蚁和第二类蚂蚁数目 为k =k 十1 。 第 一 类蚂 蚁根 据 状 态 转 移公 式(.1) 计 算的 概 率 选 择 元素 节点 去 并 前 进，j c 一 艺 。 如 小 第 二类 蚂蚁 根据 状态 转 移 公式( 4. 2 ) 计 算的 概率选 择子区间。 第一类蚂蚁修改 禁忌表指针， 即选择好之后将蚂蚁移动到新的节点。 并把该节点移动到该蚂蚁的 禁忌表中。第二类蚂蚁选择完当前连续 变量的子区间后，移动到下一个连续变量的子区间。 当 第 一 类蚂 蚁 遍 历 完 所 有节点 ， 且 第二 类 蚂蚁 访问 过 所 有的 连续变 量 的 某 一 个子 区间 ， 且 k 饥 则 跳转到 第 ( 4 ) 步 ， 否 则 执行 第 8 步。