数学建模案例基于遗传算法的多商品配送问题模型分析.pdf

1 基于遗传算法的多商品配送问题模型分析基于遗传算法的多商品配送问题模型分析 摘要 摘要 本文首先通过假设 推导给出一个考虑单个供应商和多个货栈及零售商的供 应商管理库存模型 Vendor Managed Inventory 该模型通过用提前或推迟供 货的形式来解决缺货的问题 其次 通过遗传算法给出解决这个模型的策略 给 出了算例和最优解 在做出某些合理假设的情况下利用简化的模型得到了基于单 纯形法的快速算法 并给出了算例 通过灵敏度分析还讨论了推迟 提前供货的 惩罚系数以及需求波动对库存决策的影响 并且定量的讨论了这些影响 最后作 出了总结 说明在多商品配送问题中推迟 提前供货的惩罚系数和需求波动对库 存决策具有很大影响 对一些提前 推迟供货的惩罚系数很大的易腐商品和一些 惩罚系数较少的耐用品 以及需求波动程度不同的商品 如时令商品和粮食 在 实际问题处理中应该区别对待 关键词 关键词 供应商管理库存模型供应商管理库存模型推迟提前供货推迟提前供货遗传算法遗传算法单纯形法单纯形法灵敏度灵敏度 1 1 问题的重述问题的重述 近几年来 连锁经营在我国得到了迅猛发展 一个典型的连锁经营模型通常 由供应商零售点组成 这样自然提出一个多商品配送问题 对于单供应商多货栈的典型供应链环境 不妨考虑一供货商在某地区有多个 仓储的货栈的情形 其货栈位于该地区的不同地点 供货商的目标是按照不同零 售商的需求将商品及时发送给零售商 使总成本尽可能小 总成本主要由以下两 部分组成 1 运输成本 它与运输的时间和运输的商品相关 2 由于货栈 可以以不同价格将同一种商品供给不同的零售商 且同一种商品在不同货栈的售 价也可以不同 这样零售商会按照价格优先的原则选择发货的货栈 另一方面 每一时段每个商品在货栈中的存储量有一个上限 当一个货栈被指派为一个特定 的零售商提供规定数量的商品的时候 可能会出现零售商的需求和货栈储量不平 衡的情况 当某时段容量不足的时候 货栈通过提前或推迟供货给零售商的方式 来补偿需求 如果提前供应 将会导致零售商的商品持有成本上升 因此零售商 会向供货商索要赔偿 若推迟 则会降低货栈的信誉 且零售商也会向供货商索 要赔偿 所以 提前和推迟所带来的赔偿都是供应成本的一部分 而赔偿费用与 商品的价格和提前 推迟的时间有关 供应商库存策略研究现在已成为供应链管理的一个热点 1 2 早期文献集 中在单个企业 3 商品库存策略研究较少 文 4 5 研究了一个供应商和多个 订货商的产品集成库存模型 但没有考虑缺货的情况 本文着眼于供应链中的供货环节 给出一个采取提前或推迟供货的形式来解 决缺货的模型 应用遗传算法的求解策略 通过算例分析了推迟 提前供货的惩 罚系数对库存决策的影响 说明在多商品配送问题中推迟 提前供货的惩罚系数 对库存决策具有很大影响 对一些提前 推迟供货的惩罚系数很大的易腐商品和 一些惩罚系数较少的耐用品 在实际处理问题中应该区别对待 2 下文的讨论中 假设在一个周期 例如半年 开始时 每个零售商对所有商 品在不同时间 时段 的需求已知 以及商品的价格已知 问题是供货商如何安排 不同时间 时段 的供货 使得一个周期的总成本尽可能小 随着现代仓储业的发展 人们对仓储的理解不仅仅是简单的堆放 商品种类 的日益多样化也对仓储提出了更高的要求 因此不妨理解每一个时段每个商品在 货栈中的存储是相互独立的 其存储量上限当然也是各自独立的 形象的说每个 货栈又分有若干个小货栈 每个小货栈只允许存储某一种特定的商品 多商品的 多 体现在商品之间提前 推迟供货的惩罚系数的不同 如易腐商品和耐用品 以及需求变化速度的不同 对因此多商品配送问题可以简化为单商品的配送问 题 再根据提前 推迟供货的惩罚系数的不同及需求波动不同对不同商品库存策 略区别对待 对于同质商品的简单堆放存储问题 在模型的改进中也会论及 2 2 模型的假设模型的假设 根据实际情况和题目要求 对多商品配送问题模型作出如下假设 1 当货栈的某种商品储量不足以应付需求 只允许通过提前或推迟供货的手段 满足零售商的需求 不允许在货栈间进行调剂 2 由于本文着重关注供应链供货环节 对采购和仓储环节进行了必要的省略 因此不妨设供货商在每个时段开始时对各货栈的商品进行补充 货栈再将该 时段的商品存储量全部供货给各零售商 即每个时段内货栈总要将储存的商 品全部清空 3 某货栈对某零售商因提前或推迟某种商品供货而导致的赔偿费用与该零售 商提交订单时段货栈对零售商的商品价格 以及提前或拖欠时段数成正比 4 在模型考虑的前后共 T 个时段内 所有零售商的需求都通过及时供货或推迟 供货或提前供货的方法得到满足 5 每个时段某零售商的需求是通过对某个货栈的订单实现的 零售商在一个时 段内总选择商品价格最低的某一个货栈 在价格相同的情况下 供货商选择 运输费用最低的货栈发货 6 每个货栈在一个时段内对某种商品的存储量存在一个上限 3 3 模型的建立模型的建立 设共有 K 个货栈 T 个时段 N 个零售商的情形 0kjtC 第 k 个货栈第t个时段对第 j 个零售商的商品价格 1ktt jC 第 k 个货栈第t个时段因推迟供货给第 j 个零售商第t 个时段订单而导 3 致的单位商品赔偿费用 它正比于推迟时间和t 时段价格 显然此处有t t 10 1 ktt jkt j CK Ctt 其中 1 K为推迟供货赔偿系数 与商品的种类有关 2ktt jC 第 k 个货栈第t个时段因提前供货给第 j 个零售商第t 个时段订单而导致 的单位商品赔偿费用 它正比于提前时间和 t 时段价格 显然此处有t t 20 2 ktt jkt j CK Ctt 其中 2 K为推迟供货赔偿系数 与商品的种类有关 3ktjC 第t个时段从货栈 k 到零售商 j 的单位商品运输费用 与运输的商品种类 有关 由假设 7 定义 k V为第 k 个货栈对某种商品的存储量的上限 再由假设 3 易得 ktk SV 1 定义供货商决策矩阵D 111 1 T KK T DD D DD 其中 kt D表示第 k 个货栈第t个时段的供货策略 1111 1 ktkttktT kt kt NkttNktTN ddd D ddd kj kj ktt j ttt t ttt t t d t t 第 个货栈第 个时段提前供货给第 个零售商第 个时段订单的商品数 表示 第 个货栈第 个时段推迟供货给第 个零售商第 个时段订单的商品数 第 个货栈第 个时段按时供货给第 个零售商当前时段订单的商品数 4 定义供货商补充策略矩阵S 代表供货商每个时期初补充各货栈商品的情况 111 1 T kkT SS S SS kt S代表第t个时段供货商补充给第 k 个货栈的商品 数量对每个时期 t 按照假设 3 显然有 11 1 TN ktktt j tj SdtT 2 定义零售商决策矩阵B 代表零售商决策情况 12 N BB BB j B为第 j 个零售商的决策矩阵 111 1 jTj j k jkTj bb B bb 1 0 ktj jtk b jtk 第 个零售商在 时段向第 个货栈提出订单 第 个零售商没有在 时段向第 个货栈提出订单 定义零售商的订单矩阵Q 111 1 N TTN QQ Q QQ 其中 t j Q表示第 j 个供货商第t 个时段订单的商品数量 显然有 11 KT t jktt j kt Qd 3 由于零售商在一个时段最多只能向一个货栈提出订单 12 0 t jt jkt jk t j bbbkb 因此中最多只有一个 使得 对0 k t j b 说明第 k 个货栈在第t个时段内没有收到第 j 个零售商的订单 当然 也不会在任何时段由于第t 个时段的订单向第 j 个零售商供货 因此显然有 0 0 1 2 kitj diT 0 k t j b 0 0 1 2 kitj diT 4 5 由于各零售商订单矩阵与决策矩阵已知 第k个货栈第t个时段收到的订单数 kt M 可以求出 111 TNN ktktt jtjktn tjn MdQb 111 TNN ktt jtjktn tjn dQb 5 模型的目标函数 供货商在 T 个时段内的总成本TC 123 TCTCTCTC 其 中 1 TC表 示 因 推 迟 供 货 导 致 的 总 赔 偿 费 用 1 11 1111 KNTt ktt jktt j kjtt TCdC 2 TC表示因提前供货导致的总赔偿费用 22 1111 KNTT ktt jktt j kjttt TCdC 3 TC表示商品运输总成本 3 1111 3ktj KNTT ktt j kjtt TCdC S t ktk SV 由式 1 11 1 TN ktktt j tj SdtT 由式 2 11 KT t jktt j kt Qd 由式 3 0 k t j b 0 0 1 2 kitj diT 由式 4 111 TNN ktt jtjktn tjn dQb 由式 5 4 4 遗传算法的求解策略及算例遗传算法的求解策略及算例 4 14 1 遗传算法策略遗传算法策略 遗传算法 GA 是一种模拟生物进化的全局随机优化搜索算法 它对待寻优 6 的函数基本无限制 具有较强的自适应和学校能力 本文把GA方法和分布式库存 问题的特点结合起来来对本问题求解 1 编码 这里采用整数编码 和二进制编码相比 整数编码不仅比较方便 而且 在数值优化方面具有更高的精度和效率 搜索范围也更大 2 适应度函数f 这里取f TCMAX TC 当基因是有效的基因时 否则为零 其中TCMAX 为预计的最大费用 3 参数设置 包括对种群大小 保留率 变异概率 交叉概率 最大进化代数 保留 代数 变异方法 交叉方法以及初始群生产函数等等 为了避免早熟现象 变异方法这里采用了交换变异 交叉方法采用了单 点交叉 而且 为了保证最优的个体闭会被淘汰 每次都会保留50 父代的 最优个体作为新一代的个体 而初始群生成函数是采用随机的方法产生新的 个体 并逐个对其检验 不复活要求则重新生成新的一个 考虑到对 j B 中的t 且唯一的kst 0 ktj b 所以可以对 ktt j d进行压缩 使其成为三维的基因 以三维的整数编码的遗传算法对其进行求解 以 jt W表示第t个时段第j个零售商挑选的货栈 定义 jtt ktt j dd 其中 jt kW 那么原目标函数可以表示为 123TCTCTCTC 其中 1 1 1 1 1 0 jt nTT jttWt j jtt t TCKdCtt 1 2 1 11 2 0 jt nTt jttWt j jtt TCKdCtt 1 11 3 3 jt NTT jttWt j jtt TCdC 约束条件为 1 T jttt j t dQ 0 jt jt tk Wk dV 经过这样变换后 空间的利用率能够大大得到提高 而且计算效率也有较大 提高 算法的主要流程如下 1 输入 读取有关的数据 7 2 初始化参数 设定种群大小 保留率 交叉概率 变异概率 3 生成初始种群 4 选择复制 5 对个体进行交叉运算 6 变异 7 循环 4 6 直到满足种植条件 得到最优解 4 24 2 遗传算法算例遗传算法算例 设某供货商在 A 市不同区域有甲 乙 丙三个货栈 且在该市有七家零售商 考虑在六月内 供货商如何安排供货 使总成本最小 各零售商各月的需求如下表 零售商 月 份 123456 A211512131419 B21114071 C161412131416 D171528141316 E417452931 F171613181415 G171415131216 各货栈对各零售商各月份的价格如下表 甲货栈 零售商 月 份 123456 A1548597 B1458964 C1947824 D1259865 E1389541 F1358969 G1258697 乙货栈 零售商 月 份 123456 A11124698 B1435639 C1259876 D1248865 E1025863 F1114698 G986578 丙货栈 8 零售商 月 份 123456 A1315859 B1126978 C1159638 D1159865 E1559865 F1459874 G8951197 各时段各货栈到各零售商的运输费用如下表 甲货栈 零售商 月 份 123456 A2569811 B694587 C698749 D695874 E987126 F556974 G336994 乙货栈 零售商 月 份 123456 A659845 B456123 C458778 D985638 E954123 F967895 G965874 丙货栈 零售商 月 份 123456 A895545 B632145 C698444 D778425 E585596 F695478 G965412 由关于零售商选择发货货栈的原则可得 9 零售商 月 份 ABCDEFG 1乙丙丙丙乙乙丙 2丙丙甲乙乙乙甲 3乙乙甲乙乙乙丙 4甲乙丙甲甲乙乙 5丙乙甲丙甲甲乙 6甲甲甲甲甲丙丙 提前供货惩罚系数 2 推迟供货惩罚系数 3 各货栈某种商品存储上限 甲乙丙 859097 甲货栈最优解 TC 甲 6310 S 甲 160 154 185 164 115 155 乙货栈最优解 TC 乙 5783 S 乙 190 158 165 188 125 159 丙货栈最优解 TC 丙 5766 S 丙 150 184 198 174 105 135 总成本 17859 后附遗传算法源代码 5 5 模型的快速算法及算例模型的快速算法及算例 5 15 1 快速算法策略快速算法策略 原模型为一个线性规划的代数模型 未知量为一四维矩阵 求解十分不便 然而在补充合理假设的前提下 模型可以迅速简化 未知量数量也可以大为减少 从而为快速算法的实现提供了可能 考虑实际情形 在时段总量 T 不大的前提下 商品价格在短期内的波动是相 当小的 运输费用的波动也不可能太大 此外 货栈出于自身成本的考虑 在推迟 或提前供货期不太长的情况下 完全可以与零售商事先商定 提前与推迟供货赔 偿与提前或推迟的时间无关 同时提前与推迟供货赔偿系数相等 由此补充下列 三条重要假设 a 商品的价格不随时间波动 即原模型中的0kjtC变为0kjC b 商品的运输费用不随时间波动 即原模型中的3ktjC变为3kjC 只与发货货栈 与零售商之间的运输时间有关 c 供货商因提前或推迟供货而导致的单位赔偿费用与提前或 推迟的时间无关 且提前与推迟赔偿系数相等 即原模型中 10 的 12 KKK 赔偿系数 1ktt jC 2ktt jC 0kjKC kj C 其中 kj C为第 k 个货栈到第 j 个零售商的运输费用 只与发出订 单时的商品价格和种类有关 由原模型假设 8 零售商选择发货货栈的原则是先商品价格后运输费用 由 上述补充假设 零售商一旦选定了发货货栈 在 T 个时段内就始终选择该货栈 即 在零售商到货栈之间建立了一个映射 各货栈只向选择了它的零售商供货 互相 之间是完全独立的 供货商安排供货的最优解同时也是各货栈安批供货的最优解 因此完全可以将各货栈单独考虑 原模型的四维未知量矩阵 ktt j d变为 tt j d 降低 了一维 同时由于提前或供货的单位赔偿费用与提前或推迟的时间无关 原模型 中目标函数也得以简化 从而大大降低了改进后模型的计算量 时间复杂度和求 解难度 改进后的考虑某货栈 N 个零售商 当然是那些在 T个时段内向该货栈至少提 交过一次订单的那些零售商 T 个时段内对某种商品的线性规划模型标准形式 为 min 12 TCTCTC 11111 3 NTTT kjkj N tt jttj jttj j t k CCdCd 其中 1 111 NTT tt j jtt kj CTCd 11 kj TN ttj tj dC 表示因提前或推迟供货导致的总赔偿 费用 3 111 3 NTT kjtt j jtt TCdC 表示商品运输总成本 S t 1 t tSVT 由式 1 11 1 TN ttt j tj SdtT 由式 2 1 1 1 T t jtt j t QdtTjN 由式 3 其中 t S为供货商第t个时段向货栈补充的商品数量 t j Q为第 j 个零售商第 t个时向该货栈下的订单量 简化后的模型可用线性规划的改进单纯形法或 matlab 中的 linprog 工具箱快速 11 求解 附改进单纯形法的源代码 5 25 2 快速算法算例快速算法算例 各零售商各月的需求如下表 零售商 月 份 1234 A14151213 B211140 C16141213 D715910 E41745 各货栈对各零售商各月份的价格如下表 甲货栈 零售商 月 份 1 A15 B14 C19 D12 E10 乙货栈 零售商 月 份 1 A11 B14 C12 D9 E13 丙货栈 零售商 月 份 1 A13 B11 C11 D11 E15 各时段各货栈到各零售商的运输费用如下表 甲货栈 零售商 月 份 1 12 A2 B6 C6 D6 E9 乙货栈 零售商 月 份 1 A6 B4 C4 D9 E9 丙货栈 零售商 月 份 1 A8 B6 C6 D7 E5 由关于零售商选择发货货栈的原则可得 零售商 月 份 ABCDE 1乙丙丙乙甲 惩罚系数 K 2 各货栈某种商品存储上限 甲乙丙 152527 解得 甲货栈最优解 TC 甲 310 S 甲 4 15 6 5 D1 4 0 0 0 D2 0 17 0 0 D3 0 0 4 0 D4 0 0 0 5 乙货栈最优解 TC 乙 783 D1 14000 7400 D2 01500 01000 D3 00120 0190 D4 00013 00010 S 乙 25 25 22 23 丙货栈最优解 TC 丙 766 13 D1 21000 600 D2 01100 21400 D3 0040 07120 D4 0000 01013 S 丙 27 27 23 14 Matlab工具箱linporg显示转轴次数为六次 单纯形法确保求得最优解 6 6 模型的讨论模型的讨论 6 16 1描述供货链性质参量的定义描述供货链性质参量的定义 首先对描述这个供货链性质的参量作出定义 1 设成本增长因子 TC a TC TC表示其他条件 如惩罚系数 给定时的总成 本 TC 表示其他条件变化时 总成本的增加量 2 设需求波动因子 XE X bD D X 其中 X是总需求的随机变量 XE X D X 是X的标准化随机变量 单位为1 XE X bD D X 表示 XE X D X 的标准化均访差 单位为1 它表征需求的波动程度 3 设库存利用因子c 总需求 总供货上限 它表征货栈的利用率 在我门模型中 01c 因为1c 说明不管怎样安排 都无法满足零售商需求 6 26 2推迟 提前供货的惩罚系数灵敏度分析及其对库存策略的影响推迟 提前供货的惩罚系数灵敏度分析及其对库存策略的影响 右图利用不同库存利 用因子 c 总需求 总供货上限 的五组数据 分析了惩罚 系数对成本增长因子 TC a TC 的影响 算例 中 设 定 需 求 波 动 因 子 b 0 5 可以看出 惩罚系数 较少时 成本增长较缓 惩罚系数大于3 5时 成本 基本成线性增长 另一方面 由曲线增长的斜率可以看到 随着库存利用因子的增长 总成本 对惩罚系数越来越灵敏 特别是在库存利用因子从0 7到0 8的过程中 成本增长 惩罚系数灵敏度分析 0 0 01 0 02 0 03 0 04 0 05 0 06 0 07 0 08 0 09 1 522 533 544 555 5 惩罚系数 成本增长因子a 库存因 子 c 0 5 库存因 子 c 0 6 库存因 子 c 0 7 库存因 子 c 0 8 库存因 子 c 0 9 14 明显加快 而库存利用因子大于0 8时 成本增长放缓 说明总成本渐趋饱和 结论 惩罚系数较大时 库存利用因子c 总需求 总供货上限 尽可能不要超过0 7 这就是说对惩罚系数大的商品 供货商接的订单数不要超过该商品总供货上限的 0 7 6 36 3需求变化的灵敏度分析对及其对需求变化的灵敏度分析对及其对库存策略库存策略的影响的影响 实际当中 不同商品的需求变化速度是不一样的 如烟酒 节日前后需求量 明显增多 粮食 一般需求量比较平稳 下面研究总订货量恒定 需求变化速度对库存成本的影响 从而得出不同商 品需求波动程度对库存策略的影响 变化的大小用需求标准化方差 XE X bD D X 表 征 右图利用不同库 存利用因子的五组数 据 分析了波动因子对 成本增长因子 TC a TC 的影响 算 例中设定提前 推迟的 惩罚系数为3 可以看出 图中曲 线 主要分为三部分 b 0 3时 成本增长较 慢 0 3 b0 7时 增长再次放缓 另一方面 由曲线增长的斜率可以看到 随着库存利用因子的增长 总成本 对波动因子的灵敏度增长迅速 特别是在库存利用因子大于0 6时 成本增长明 显加快 但区别于惩罚系数的是 总成本增长没有渐趋饱和 结论 需求波动因子大于0 7时 库存利用因子c 总需求 总供货上限 尽可能不要 超过0 6 需求波动因子0 3 b 0 7时 库存利用因子尽可能不要超过0 8 需 求波动因子b 0 3时 库存利用因子对总成本几乎没有影响 这时供货商应尽可 能提高库存利用因子 6 46 4模型的评价模型的评价 本模型的创新点在于缺货情形的考虑 文 4 5 研究了一个供应商和多个订 货商的产品集成库存模型 但没有考虑缺货的情况 文 6 给出了一种允许缺货 的模型 但其仅仅用罚款来补救 所缺的货物不再兑现 这些假设在实际中都有 不合理的地方 而本文通过用提前或推迟供货的形式来解决缺货的问题 比较合 需求波动灵敏度分析 0 0 05 0 1 0 15 0 2 0 25 0 3 0 10 30 50 70 9 波动因子b 成本增长因子a 库存利 用因子 c 0 2 c 0 4 c 0 6 c 0 8 c 0 9 15 理的解决了仓储量上限而导致的缺货情形 其次 在提前或推迟供货的形式的基础上进一步讨论了惩罚系数对库存策略 的影响 这是不同商品区别对待的关键所在 不足之处在于对计算结果的分析和检验做得不够透彻 另外快速算法采用单 纯形法在时间复杂度上没有保证 6 56 5模型的改进和推广模型的改进和推广 首先 有限生产力的限制 实际情况中 作为供货商的来源 生产商的 生产能力是有上限的 这种情况下我们必须多加一个约束条件 1 K ktt k SP t时段个货栈的进货量的和不能超过t时段的生产量 这对我们的模型的求解 并没有实质性的影响 其次 本模型假设每个时段内货栈总要将储存的商品全部清空 若考虑 仓储和采购环节 我们可以增加一个期初库存量 111 1 T KKT II I II 其中 kt I 表示第k个货栈在t时段的期初库存 此时 11 TN ktktt j tj Sd 变为过渡公式 11 TN ktktktt j tj SId 考虑采购环节 不妨假设供货商采取 S Q 联合采购策略 即每个时段最多联 合采购一次并分配给各货栈 其采购成本由单位商品采购成本与单次采购的固定 成本组成 再考虑同质商品的简单堆放问题 正如本文开头所述 本模型适用于对存储 有技术要求的非同质商品的供货问题 对于同质商品 在不至于造成损耗的情况 下可以采取简单的堆放策略 此时原模型中的 ktt j d变为 yktt j d 其中y代表商品种 类 ktk SV 也变为 1 Y yktyk y SVV 其中 y V为第y种商品的体积 这是模型比原模 型未知量在规模上增大了一维 求解难度增大 但性质没有发生变化 仍是一个线