多商品配送问题的数学模型及快速算法.doc

多商品配送问题的数学模型及快速算法摘要:多商品的配送问题日益成为现实社会的热点。本文描述了商品价格，需求以及销售网络已定的前提下，一个多货栈多商品多客户的供货商如何制定商品配送计划，以实现供应成本的最小化。在考虑了运输成本与时间的关系以及提前/推迟供货带来的惩罚之后，以实现运输成本与惩罚之和最小为目标，进行了系统建模。首先建立了原始模型，分析模型结构后，讨论了几种可行的算法。然后在运输时间小于一个订货时段，惩罚与误期的时段成正比的假定下，将模型转化为可求解的线性规划模型，并由最简单的情况开始逐级深化讨论模型。对各个简化模型，给出相应的具体算例，用lingo进行求解，结果分析表明了模型的正确性和有效性。当深化为多货栈多商品多零售商模型时，通过深入分析模型，提出一种快速算法，并由lingo编程实现，极大地减少了线性规划的变量个数（由O（）减少为O（），降低了线性规划的复杂度。通过两种算法对带有个变量的大规模销售网络的计算比较，验证了快速算法的优越性。最后根据一种更符合实际情况的假设，进一步优化，建立了更加有效，更加节省成本的供销模型。关键词：多商品配送 提前/推迟供货惩罚 运输成本 二次规划 线性规划 快速算法 优化模型一、问题的重述：考虑供货商的多种商品配送问题假设该供货商在某地区有多个仓储的货栈，它们位于该地区的不同地点供货商的目标是按照不同零售商的需求将商品及时发送给零售商，使总成本尽可能小这里的总成本主要由以下几部分组成（1）运输成本，它与运输的时间和运输的商品相关（2）由于货栈可以以不同价格将同一种商品供给不同的零售商，且同一种商品在不同货栈的售价也可以不同，这样零售商会按照价格优先的原则选择发货的货栈另一方面，每一时段每个商品在货栈中的存储量有一个上限当一个货栈被指派为一个特定的零售商提供规定数量的商品的时候，可能会出现零售商的需求和货栈储量不平衡的情况当某时段容量不足的时候，货栈通过提前或推迟供货给零售商的方式来补偿需求如果提前供应，将会导致零售商的商品持有成本上升, 因此零售商会向供货商索要赔偿；若推迟, 则会降低货栈的信誉，且零售商也会向供货商索要赔偿所以，提前和推迟所带来的赔偿都是供应成本的一部分，而赔偿费用与商品的价格和提前、推迟的时间有关现假设在一个周期（例如一年）开始时，每个零售商对所有商品在不同时间(时段)的需求已知，以及商品的价格已知，问题是供货商如何安排不同时间(时段)的供货，使得一个周期的总成本尽可能小1对此问题，并针对你所理解的实际中的多商品配送问题，建立数学模型, 讨论求解算法的设计2分析当运输成本和运输的时间是什么关系, 提前、推迟惩罚与商品的价格以及提前、推迟的时间是什么关系时，或在其他你认为合理的假设下，该问题可以有快速算法求解这里，你对这些关系的假设应与实际背景较吻合3举一个和几个实际算例来说明你的算法或模型二、问题的分析 考虑某地区的一个供货商，有J个货栈，分布在该地区的不同地方。该供货商可提供K种商品，每一个货栈可拥有全部的商品也可以是其中的一部分，每一个货栈又给多个零售商供货。假设供货商给I个零售商供货。在一个周期T（例如一年，并分为T个时段）开始时，每个零售商对所有商品在不同时段的需求已知，每种商品的价格已知，且这一价格在一个周期内保持不变。零售商选择价格最低的一个货栈给它供货（如果存在多个最低价格时，由零售商任意选择其中的一个），因此一个周期内货栈与零售商间的销售网络已经确定。我们认为根据所给价格既定的销售网络是健康的，不存在极度不平衡的供需关系。该问题考虑的供应成本由两部分组成：运输成本和由于提前或延误供货造成的赔偿：（1）、运输成本。该供货商在不同的地方设有多个货栈，而该地区的零售商也位于不同的地方，因此存在运输问题，即运输时间、运输费用。设运输成本为G，它与运输时间，运输商品的种类k及运输量有关。 （2）、由于提前或延误供货造成的赔偿，称为惩罚函数，表示x单位价格的商品提前或延误时段对零售商的赔偿。当0或x0时，F0；当0时表示推迟供货。三、基本假设1、零售商以时段为时间间隔向零售商订货，且每一时段至多订一次货。2、 货栈以时段为时间间隔给零售商发货，且每一时段至多发一次货。3、 当某货栈某时段容量不足时，供货商只通过由零售商按价格最低原则选定的 货栈提前或推迟供货的方式来补偿需求，而不考虑货栈之间的相互调货，或者由其它货栈给该零售商供货。4、 供货商有充足的运输能力，运输成本只与时间与运输商品以及运输量有关， 而不考虑具体的运输细节。5、 当配送区域比较大的时候，运输的时间可能比较长，货物经过几个时段才能送到零售商处。这时，供货商为了协调供货以达到总成本的最小，可以选择不同的方式，改变运输时间，从而改变运输成本。1当配送区域比较小的时候，运输时间比较短，与一个时段相比可忽略，即当期发货当期可到。6、 每一时段每个商品在货栈中的存储量有一个上限。供货商货源充足，且每一时段初给货栈补一次货，每次补货都可达到货栈的存储上限。不考虑补货的运输成本。7、 不考虑商品在货栈中的存储成本。四、变量及符号的说明j : 表示第j个货栈i：表示第i个零售商k：表示第k种商品：j货栈给i零售商提供k商品的价格：对i零售商t时段的订货，j货栈在t时段的发货量：j货栈在t时段运输k商品到i零售商的运输时间：i零售商t时段对商品k的需求量：j货栈存储量的上限：单位的k商品运输时间产生的运输成本。：惩罚函数，表示单位价格的商品提前或延误时段对零售商的赔偿。当0或0时，F0；当0时表示推迟供货。 五、模型的建立1、 目标函数的建立根据题目要求，将模型的目标值考虑为两部分：运输成本和供货提前/延期的惩罚费用。由假设条件（4），在一个周期内，一个零售商对一种商品的需求只由一个货栈满足，不存在货栈之间的相互调整，各个货栈的供货是独立的，因此，在下面的最优化讨论中，我们只讨论一个货栈供货的最优化情况，整个供货商的最优化供货可通过J个货栈的线性叠加得到。为了不失一般性，我们考虑第j个货栈供货情况（j1，2， ，J）。（1） 、运输成本前面已经假设第k种商品的运输成本与运输时间、商品数量的关系，很容易写出j货栈在一个周期之内所承担的所有运输成本： （2） 、提前/推迟供货的惩罚费用由前面假设的提前/延迟供货与惩罚费用的函数关系，且tt，代入惩罚函数，通过线性叠加易得j货栈在一个周期内的所有惩罚费用： 因此，一个周期内，j货栈的供应成本之和可表示为： 2、 约束条件： （1）、货栈应当满足零售商在不同时段t的需求量，表达式如下： t1，2， ，T；i 1，2， I； k1，2， ，K 其中表示i货栈t时段对k商品的需求量，为已知。 （2）、根据实际情况，j货栈所有商品的储存量之和有上限，列出表达式为： j1，2， ，J其中为j货栈的最大存储量，为已知量。原始模型如下： s.t. i 1，2， ，I; k1，2， ，K；t1，2， ，T; j1，2， ，J t1，2， ，T; t1，2， ，T ; i 1，2， ，I;j1，2， ，J; k1，2， ，K3. 模型的初步分析及算法设计：在上述数量决策的的数学规划模型中，已知条件为各个零售商的需求，各个货栈的容量上限以及供货价格。在目标函数中我们假设某种商品的惩罚函数与延误时间成正比，与延误货品的数量成正比，而其运输费用与运输时间成正比，与运输的货量成正比。由于实际发货量与实际发货采用的运输时间均是待求解的未知量，从而它们的乘积将使目标函数的维数达到二维，该决策模型转化为二次规划问题。对二次规划问题，传统的算法有直接消去法、广义消去法、有效集法等。这些算法虽然能算得问题的精确解，但其计算的复杂性随着求解规模的增大而迅速增大，所以这些算法对于大规模问题都不具有实际可行性。Mcarthy和Liu102认为经典的生产规划理论及其最优算法只具有学术价值，在实际应用中运用很少。为使算法更加使用，我们建议采用以下几种近似算法：1、 规则方法： 这是一种在生产计划和调度问题研究中，运用最广泛的启发式方法。其优点在于，计算时间较少，便与生产中的实时生产与调度。2、 仿真方法： 其主要是通过计算机模拟现实生产环境，对可能的生产计划和调度方案进行计算机上虚拟实施，比较计算结果，寻求最优方案。这种利用近似枚举的方法在缺乏有效的理论支持的情况下是一种最直观也最有效的方法。3、 智能化方法： 智能化生产计划的方法主要有：遗传算法（GA）、设禁搜索（TS）、模拟退火（SA）和人工智能网络等智能化算法。这些智能算法的优点是能跳出局部最优，搜索全局最优解，但解的准确性还有待考证。所列算法各有优缺点，具体实施中我们可以根据问题的规模及限制条件的复杂程度选择合适的算法。比如我们可以采用遗传算法（CP-GA）与模糊逻辑（CP-HA）相结合的智能混合算法（CP-FL），由于过程过于繁杂，此处不做详细说明，具体过程可参见文献116，124，125。 事实上，现实生活当中运输函数和成本函数有一些特殊的性质，这样便可以大大简化模型和算法。为此，下一部分，我们将根据实际情况以及生产实践，对运输函数和惩罚函数做进一步的假设，再根据这些假设，从易到难，从单货栈单商品单零售商模型，到多货栈多商品多零售商模型，一步一步接近实际情况，给出快速的算法，并对各种模型举出具体算例，以验证模型的合理性。六、模型的简化：（一） 假设：1、运输函数：。考虑商品k的运输费用为运输时间，商品数量的线性函数。假设为从j货栈到i零售商的平均运输时间，我们假设小于一个时段，即当期发货当期即可到达。它与时段和商品种类无关，只与货栈与零售商的距离有关，我们大胆地做假设，为了达到最低成本的目的，商家必定会选择一种最优的运输方式以及相应的最佳运输时间。设为单位商品k从货栈运输到零售商的单位时间的运费成本因子，则可以得到所有商品的运输费用： 在一个周期开始时，零售商的需求已知，因此已经确定，所以一个周期内内的总运输成本也是一个定值，不能通过供货安排来改变，因此在下列简化模型中，要实现供应成本的最小化，只考虑惩罚的最小即可，2、惩罚函数 ：如果因为核算方式的不同而算出不同的延误赔偿额，供货商与零售商必将产生争议。为了避免在清算时发生争议，我们大胆假设惩罚函数对与延误时间应该是线性形的，以下我们给出简单的数学证明：考虑某货栈只有一个零售商购买一种货品的情况，假设货栈上限不随时间变化。设惩罚函数可简单表示为F（x , t）,x为延误货量，t为延误时间。设货栈上限为C。现只考虑推迟的情况。设某期的定单为货栈上限的两倍，则当期只能发出定单一半的货量，然后设之后连续N期的定单都为货栈的上限，第N+1期无定单，则拖欠的货物只能在第N+1期发出，可认为应赔F（ C ，N ）。但也可以认为是当期拖欠的货物在第一期发出，而第一期的货物在第二期发出，以次类推，直到第N期的货物在第N+1期发出从而补完拖欠。在这种情况下，其赔偿额为N*F（ C ，1 ）。如果F（ C ，N ） N*F（ C ，1 ）则零售商会要求按照二者中赔偿额高的那项索取赔偿，而供货商则会认为其调整方式是按二者中赔偿额低的那项实施的，从而双方产生争议。为使不产生争议，必须使 F（ C ，N ）= N*F（ C ，1 ）提前的情况可同样证明。所以惩罚函数是延误时间的线性函数，证毕。从现有的有关生产计划与调度问题文献6来看，产品的交货期的描述方式有三种：精确交货期、交货期窗口和模糊交货期。通常，提前与推迟的惩罚与订单的价值成正比，且与提前、推迟时间成正比，设单位时间单位价值的提前与推迟供货的惩罚因子为，一般来说,推迟供货会引起信誉度的降低，因此假定，以使供货商在供货不足的情况下尽量采用提前供货代替推迟供货，则商品k的单位时间的提前与推迟供货惩罚因子为，（k1，2， ，K）。设应交货时间为t，供货时间为t。精确交货期：交货时间为固定的时间点，如图4-1所示. 图4-1 精确交货期地隶属函数（用来描述客户的满意程度）可以表示为 （式6.1） 精确交货期的提前/推迟供货的惩罚函数可以描述为： （式6.2） 交货期窗口：交货时间为一段时间，例如零售商要求在，这一区间内交货都可。为最早交货期，为最晚交货期。如图6-2所示。 图6-2 交货期窗口的隶属函数可以表示为： （式6.3） 交货期窗口的提前/推迟供货的惩罚函数可以描述为： (式6.4) 模糊交货期：交货时间为一段时间，并且反映了客户对偏离这一时间的不同主观满意程度。如图6-3所示， ，其中，分别是商品k的最早交货期和最晚交货期，分别是客户的最满意交货期的上限和下限，且满足10时，变量超过100000，计算量非常庞大，但考虑到这些变量当中大部分都是0，为此，我们设计了快速算法，由程序实现。模型的改进：根据题意，每个零售商都根据价格最优的原则选定发货货栈。实际上我们可以认为，零售商选定的只是最低的那个价格而不是货栈。如果在具体配送的过程中，供货商愿意在商品出售价格保持不变的基础上选择从其他货栈发货，供应商自己补足差价，则收货的零售商应该没有异议，因以为这么做对零售商的利益丝毫没有影响，在惩罚因子较大的情况下甚至可以避免不必要的延误。此时我们将各个货栈对某零售商提供某种商品所提供的价格减去其中的最低价格，从而产生差价，将这些差价加到相应的运费中去，产生虚拟运费（不低于原运费）或是折合成虚拟的运输时间（不少于原运输时间），在这种模型下各个货栈对某个零售商提供某种商品的价格均是最低价格，零售商对供货商指定的任何货栈均无异议。此时，在定单不超过当期货栈上限的情况下（即不需推迟或提前），供货商只要选择虚拟运费最低的那个货栈发货即可实现成本最低。基于这种假设下建立的深化模型如下：s.t. t1，2， ，T; ; i 1，2， ，I; k1，2， ，K j1，2， ，J;其中 是虚拟运输时间采用这种可根据具体定单情况以及客户对象选派货栈供货的配送方式，比起自始至终由指派的货栈对确定的客户供货的配送方式，要更加灵活，也更节省成本。 八、参考文献1.张曙，分布式网络化的全球制造，中国机械工程，19982.McCarthy B L and Liu J,Addressing the gap in scheduling research:a review of optimization and heuristic methods in production schedualing.International Joural Production Research 1994,32(4),903-915.3.D,Wang,S-C. Fang and H.L.Nuttle, Fussy rule quantification and its application in fussy due-date bargaining,Proceeding of IFSA Congress 19994.Wang, Dingwei, Fang, S.C. and T.J. Hodgson,A fussy due-date bargainer for make-to-order manufacturing systems, IEEE Trans. on SMC Part-C,1999,29,566-575.5.