多商品配送问题论文.doc
《多商品配送问题论文.doc》由会员分享,可在线阅读,更多相关《多商品配送问题论文.doc(21页珍藏版)》请在咨信网上搜索。
1、多商品配送问题摘要:多商品配送问题是物流管理领域经常要涉及到的问题,其基本关系抽象后可用右图表示。题目要求建模分析确定供货商如何安排各个货栈在各时段的供货方式,使得其在一个经营周期内的总成本最低。经分析,本文将其归结为一个分步优化问题:由于运输成本在保证每趟运输尽量满载的前提下即可得到优化,故本文首先对货栈的货物配给方式进行优化,找出了求解怎样安排各个时段每个货栈给各零售商不同商品的供货量(包括当时段供货量、提前供货量、延迟供货量)从而使整个周期内赔偿损失最小的合理算法和数学模型; 在此优化的基础上,本文利用启发式算法,结合计算机程序选择的运输成本最小路径,将每个货栈给不同零售商的不同商品供货
2、量中不能够整车运送完的额外商品量进行共同配送(合并运输),降低了运输成本,使得到的方案更趋于最优方案。在进行货物配给方式优化的过程中,本文由浅入深,首先针对单货栈、单商品的简单情况(本模型的基本构建单元)进行数学模拟和算法设计,然后根据不同商品以及不同货栈之间的相对独立性,对前述模型进行推广,成功得到了适用于多货栈、多商品的题设情况下的货物配给方式优化方案。此外,本文的独到之处还在于其严谨周密的解题过程本文在模型求解的过程中给出了两种不同的方法:采用LINGO软件求解线形规划的途径,和从算法设计出发的计算机编程途径,并在模型检测中得到了完全相同的解。可以说不仅实现了殊途同归,更通过相互校验体现
3、了算法的合理性和正确性。 在模型简化过程中,本文充分结合题设条件和模型建立背景(同一地区范围内的短线配送),并从实际生活中的商品配送问题出发,提出了对赔偿函数、运输函数等因素的合理简化方案,使算法在不失实用性的前提下实现了求解效率的提高。尽管出于可操作性的考虑,本文通过增加特定假设对该多商品配送问题的背景进行了限定,使模型的适用范围受到了一定约束,但这些假设的提出基本是有实际依据可循或至少不会跟实际情况发生抵触的,因此本文所给出的模型和算法具有较高的参考利用价值。关键词:物流配送 分步优化 启发式算法 质量-服务损失函数 Lingo软件 1 一、问题重述 多商品配送方案的设计是现实生活中很多供
4、货商所面临的问题。现某供货商在一地区内的不同地点有若干仓储货栈。其目标是按照不同零售商的需求将商品及时发送给零售商,使总成本尽可能小。这里考虑总成本由两个主要部分构成:1)运输成本,它与运输时间和运输商品有关;2)由于货栈可以以不同价格将同种商品供给不同的零售商,且同种商品在不同货栈的售价也可以不同,故零售商会按照价格优先的原则选择供货的货栈。另一方面,每一时段每个商品在货栈中的存储量有一个上限当一个货栈被指派为一个特定的零售商提供规定数量的商品的时候,可能会出现零售商的需求和货栈储量不平衡的情况当某时段容量不足的时候,货栈通过提前或推迟供货给零售商的方式来补偿需求如果提前供应,将会导致零售商
5、的商品持有成本上升, 因此零售商会向供货商索要赔偿;若推迟, 则会降低货栈的信誉,且零售商也会向供货商索要赔偿所以,提前和推迟所带来的赔偿都是供应成本的一部分,而赔偿费用与商品的价格和提前、推迟的时间有关现假设在一个周期(例如一年)开始时,每个零售商对所有商品在不同时间(时段)的需求已知,以及商品的价格已知,问题是供货商如何安排不同时间(时段)的供货,使得一个周期的总成本尽可能小1对此问题,并针对你所理解的实际中的多商品配送问题,建立数学模型, 讨论求解算法的设计2分析当运输成本和运输的时间是什么关系, 提前、推迟惩罚与商品的价格以及提前、推迟的时间是什么关系时,或在其他你认为合理的假设下,该
6、问题可以有快速算法求解这里,你对这些关系的假设应与实际背景较吻合3举一个和几个实际算例来说明你的算法或模型二、对象分析及基本假设 背景:为了使模型更接近于现实,在进行建模之前,我们对各种物资配送商经营的实际情况进行了大量的信息搜集,分析工作,从而得出了模型的主要模拟对象同地区内短线物流配送系统的一些特点1: 1、 在激烈竞争的环境下,对货物交付的及时性要求较高,大多数情况下都是在订货的当天交货,鲜有有货故意不发的情况;2、 供货商大多数拥有自己的运输车辆,以利于降低运营成本; 题设条件:l 在一个周期开始时,每个零售商对所有商品在不同时段的需求已知l 一个周期内,对于不同的商品各货栈给各零售商
7、的价格已知,且价格不随时段变化 增加假设:l 所讨论区域半径在300km以内,运输时间远小于时段长度 2l 当货栈容量不足时,供应商提前或推迟供货最多只能跨越一个时段(否则零售商必然因为供货商失信严重而终止合作)l 供应商在每个时段开始时刻给所有货栈填充货物,并可在较短时间内完成l 某时段内,供货商给某零售商送货需在零售商指定时间区间内完成,只要不超出该时间范围即无需赔偿l 货栈给零售商送货以及时性为第一准则,不存在为了减少成本而在供求不发生冲突时为了减少运输次数而故意提前或推迟供货导致零售商发生损失的情况l 供货商采用同样的货车送货且货车数量足够多三、主要参数说明及名词解释 首先我们引入4个
8、下标i,j,k,l,分别表示第i个货栈,第j 个零售商,第k种商品和第l个时段。以下是本文中一些主要参数的说明,对其他一些参数及变量我们将在使用时说明。 对第k种商品第i个货栈给第j个零售商的价格 第j个零售商在第l个时段对第k种商品的需求量 第k种商品在第i个货栈的存储量上限 第i个货栈和第j个零售商之间的距离 第i个货栈与第j个零售商之间第k种商品的单位运输价格 第j1个零售商和第j2个零售商之间的距离 第k种商品的单位体积 货车的容量 第i个货栈与第j个零售商在第l时段是否存在第k种商品的运输持有成本 持有某种货物一段时间所必须支付的成本,包括管理费、仓储费、管理费、利息费用等缺货成本
9、当需要某种货物而又不能从库存得到供应时所导致的零售商在商誉、 名声、及潜在的未来销售上的损失 共同型配送为了提高车辆装载率而对多个企业、零售商的需求货品共同进行运输的配送方案2四、问题分析及模型准备 3本文的目标是要讨论供货商的多商品配送,由题意可知需满足两个基本要求:即供货及时性和成本尽可能小。在成本构成中,运输成本的优化余地较损失赔偿成本为小,且由于总的供货需求既定,故只要在赔偿损失最小的前提下保证每次发货车辆尽可能满载,即可以得到满足题意的近似最优解。为此,我们采用分步优化策略,即先完成对损失赔偿成本的优化得出每个时段对于不同商品各货栈给各零售商的供货量,再对既定的供货量考虑采用怎样的运
10、输策略(如共同型配送)可以使运输成本最优,这样可以减少各步优化的设计变量数,提高优化的速度且得到较好的优化方案。因此,我们可以将问题划分为如下三个步骤处理:1) 单商品、单货栈情况下的损失赔偿最优(即该供应商仅有一个货栈且多个零售商仅需求一种商品)。2) 多商品、多货栈情况下的损失赔偿最优(此即本题所探讨的情况)。由于各种商品之间、各个货栈之间相互独立,故只要对第一所得模型进行推广即可解决此问题。3) 多商品、多货栈情况在已得赔偿最优供货分配方案的前提下确定最优运输方案,此时可引入启发式算法和共同行配送策略解决。3 4 用框图表示如下: 深化运输优化推广多商品多货栈损失赔偿优化单商品单货栈损失
11、赔偿优化损失赔偿函数此处我们根据田口玄一质量-服务损失函数 5 L-以钱数表示的单位损失(惩罚成本)y-质量变量的值m-质量变量y的目标值k-常数,取决于质量变量在财务上的重要性在本题中,我们认为k与商品的价格及其他因素(如季节性等因素)有关,故用,表示其他因素,表示价格因素,两者乘积表示上述k值我们令赔偿Cf与提前的发送时间与推退的发送时间存在如下关系: 4其中 是第k种商品的提前赔偿系数,是第k种商品的推迟赔偿系数,由于持有成本一般小于缺货成本,故运输成本函数根据常用的运价递减原则6 ,可绘出运输成本图线大致如下侧所示,故我们将运输成本函数定为下面形式:, 其中为运输成本系数,为运输距离,
12、为幂指数,q为运量,b为单车发车成本,n为发车辆数。五、模型建立与求解(一) 单商品、单货栈情况(模型基本构成单元)首先,我们将零售商对货物k的需求做离散化处理。下图a所示曲线q(t)为第j个零售商在一个周期时间内对某特定商品k的需求密度曲线。为了研究方便,我们取t1到t2时间为一个时段,则将曲线在该时段内积分即可得到对应第L时段内的零售商需求量Qjkl, 如下方柱状图b所示。 即 图 a 5图 b 我们将单商品情况下,某个货栈在一个周期时间内对不同零售商的供货情况表示如下图。中间时段为当前所研究的时段L,t1 - t2 为零售商a的要求到货时间(供货商在这段时间内供货即不用赔偿),ta,tb
13、 分别为提前供货和推迟供货的时间。 货栈充货货栈充货货栈充货 时段 L+1 时段 L 时段 L-1 t. . ta t1 t2 tb定理1当时段L货栈容量不足而必须对某零售商提前或推迟供货时,提前供货时间ta 必为前一时段L-1的最后一天,推迟供货时间tb必为后一时段L+1的第一天 证明: 根据前面所引述的损失赔偿函数 可见,欲提前供货的赔偿最小,只需ta-t1 的绝对值值最小,而提前供货必在上一时段内发生,故取ta为上一时段的最后一天。同理可证得tb 为下一时段的第一天方法一:线形规划对于单商品单货栈的情况,我们可以建立下面的规划模型求解。此时的目标函数是使供货商的损失赔偿最小,而约束条件主
14、要由两方面构成:1)保证一个时段内货栈给各个零售商的发货量不超过货栈容量上限R ;2)对于每个零售商而言,当前时段发货量N,提前发货量A与推迟发货量B之和恰好等于该零售商在该时段的商品需求量Q,通过规划求解软件Lingo可以较为方便的处理该问题。 6Objective: S. t 式中,分别表示在第L时段,该货站给第j个零售商的当时段发货量、提前时段发货量和推迟时段发货量(注:若在实际算例中三者中某一项或两项并不存在,则等价于其值为0);为货栈将第个零售商下一时段的需求量中提前到本时段发送的部分, 为货栈将第个零售商上一时段的需求量推迟到本时段发送的部分;R为货栈对该种商品的存储上限;为该时段
15、第j个零售商对该商品的需求量;Cfa为单位商品的提前赔偿量,k1为提前赔偿系数, Cfb为单位商品的延迟赔偿量,k2为延迟赔偿系数;tjl1,tjl2分别为第j个零 售商在第L时段的期望到货时间范围的起始时间和终止时间;ta(l-1), tb(l+1)分别为第L-1个时段的终止时间和第L+1个时段的起始时间。方法二: 计算机编程 除了上述线形规划的方法之外,我们还可通过编程求出赔偿最小的发货方式程序算法核心:针对单个货栈,一种商品,多个零售商的情况求出最小赔偿损失(利用C语言,引入哈希表结构存储)将哈希表中的每个子链表表示每一充货周期中货栈与零售商之间存在的买卖关系,所有子链表构成哈希表,预处
16、理:首先用0-1矩阵表示零售商与货栈之间存在的是否存在购买行为,若第i个货栈给第j个零售商的价格是同种商品在所有货栈中最低的,就说明第i个货栈与第j个零售商之间存在购买行为,以下的工作只针对对该矩阵中是零的元素进行,大大减少了工作量。 7第二步,如果货栈容量大于不同零售商的总需求则直接按要求发送货物,若连续三次的货栈存储上限总和仍小于三次的需求,则表明货栈的容量太小,需要扩充。我们将对此给出提示。(对于一个周期中第一时段和最后一个时段,由于其特殊性,仅判断连续两次的货栈存储上限总合是否小于两次的需求)。第三步,针对一个不能满足需求的时段进行处理,分别求出其提前与推迟带来的赔偿,并根据其单位赔偿
17、数额从小到大排成一个链表。进行比较工作并删除。具体操作见下面流程图:针对某时段L, 累计得出所有零售商在该货栈对此商品的需求总量检查是否超过货栈容量上限R是否超过货栈容量未超出()分别计算出对于每个零售商该时段需求的全部商品若提前(或推迟)供应所造成的供应商潜在赔偿损失aj, bj 计算并输出给每个零售商的商品数量及发送时间将所有潜在的提前/延迟赔偿损失aj, bj 按照从小到大的顺序排列得到形如左图所示的顺序表b2a3a4b1a2()a1b4a3a4b3Ptr1创建两个指针Ptr1,Ptr2,在一次循环开始时刻分别指向顺序表表头和表尾。首先根据货栈容量上限将指针Ptr2上移,直到它所指位置以
18、下的所有零售商需求总和为(遇同一零售商的不同赔偿如b3,a3,只记一次)。Ptr从上往下移动,每次指向一个位置(b2)时便检查前一时段货栈余量是否能够满足当前零售商(b)的需求,若可以则遍历该表,将对应该零售商的另一个损失赔偿(a2)的节点删除;若不可全部满足则同样遍历该表,在对应该零售商另一损失赔偿的节点修改商品量值为原值减去可提前供应的量值。将Ptr1下移一位,再上移Ptr2到新的满足上限要求的位置。循环执行上述步骤直到两指针相遇。Ptr2此时Ptr2以下部分对应为该时段内可以供货的零售商及供货量;需要提前或推迟的则已处理 8定理2 上述算法中对于潜在损失赔偿顺序表的处理方法可以保证得到使
19、赔 偿损失最小的供货方式证明: 假设存在新的赔偿损失,其单位赔偿总和小于用上述计算机处理方法所得的赔偿损失,则新的赔偿损失可看成是用一定数量的新的单位赔偿损失交换原先的赔偿损失,即下式:是假设的新的最小的潜在赔偿损失,是按计算机处理方式,即任一时刻都从中读取未单位分配赔偿损失中最小值直到等于容量上限为止的潜在赔偿损失总和,为从计算机处理所得的赔偿中被交换出来的单位赔偿存失为的数量,为从计算机处理所得赔偿后交换进去的单位赔偿存失为的数量。对原先任意一单位的赔偿损失,由于其都是那一时刻未分配赔偿中的最小值,故任一均小于任一交换进的新单位赔偿中,又由于交换的单位赔偿数量相等,即,故,因此,假设不成立
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 商品 配送 问题 论文
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【a199****6536】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【a199****6536】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。