基于软计算的救灾物资多配送中心调度问题研究.docx

基于软计算的救灾物资多配送中心调度问题研究 摘要自然灾害的发生不可避免，但灾难发生后对应急物资的合理调度可以有效降低灾难造成的生命和财产损失。基于对救灾物资调配特点的分析，建立救灾物资多配送中心调度问题的数学模型，给出基于软计算的求解方法，得出可在灾难发生后根据每种物资需求的紧急程度确定配送线路和配送时间，同时引入多配送中心更符合灾后物资调运实际情况的结论，希望能为应急物资调度问题的相关研究提供一定借鉴。 下载 关键词软计算；救灾物资；配送中心；调度 中图分类号F259.21文献标识码A文章编号 2095-3283（2015）12-0119-03 我国地域广阔，地质构造复杂，各种自然灾害频发，如2002年蔓延全国的“非典”、2008年南方极端寒冷天气、2008年5月12日汶川大地震、2010年4月14日玉树地震，2013年4月20日庐山地震等重大自然灾害时有发生。一些重大灾难的发生都是随机和不可预见的，会造成大量的人员伤亡和财产损失。在灾害发生后，如何有效降低灾难造成的人员伤亡和财产损失攸关重要，特别是如何将医药用品、粮食和帐篷等必要的应急物资及时调配到位是避免灾难进一步扩大的重要保证。 一、救灾物资调配的特点 救灾物资调配与传统物资调配比较存在很大差异，在灾难发生和发展的不同阶段，对于不同救灾物资的需求也是各不相同。总体来看，救灾物资的调配具有以下特点： 1.突发性。灾难的发生往往都是突发事件，其发生时间和发生地点大多不可预测，这决定了救灾物资调配最主要的特点就是突发性。 2.不确定性。灾难发生的突发性导致短时间内灾区情况不能确定，从而使救灾物资的需求地点、需求数量和需求种类等具有不确定性。 3.时限性。在灾难发生的不同时期，对物资配送的时限要求也完全不同。例如，灾难发生前期对应急医疗用品需求最大，中后期对粮食和日用品的需求增大，所以救灾物资的配送就必须在一定时间内到达，才能使物资的效用达到最大，有些物资需要快速运到，而有些物资的配送要求既不能提前也不能推后。 4.弱经济性。灾难发生后，救灾物资配送的主要目标是以最快速度把灾区需要的物资运送到需要的地点，尽可能地减少人员伤亡和损失，而物资配送的经济性不是主要考虑的目标。 5.复杂性。灾难发生后往往会对灾区的道路桥梁等造成破坏，同时通信设施也可能遭到破坏，这就使救灾物资配送面临的情况更加复杂。 6.协调性。救灾物资配送往往需要多部门和多方式协调完成，这就需要相关部门之间加强合作与协调，才能使高效完成救灾物资的配送任务。 由此可见，救灾物资的运输调度问题是一个NP问题（Non-deterministic Polynomial，即多项式复杂程度的非确定性问题），传统方法难以有效解决，因此本文采用软计算方法对此问题进行建模并求解。 二、救灾物资多配送中心调度问题的数学模型 救灾物资多配送中心物流调度问题，是在经典多配送中心物流调度问题的基础上，考虑了配送服务需求点对服务时间的要求，即配送服务必须在客户要求的时间窗内完成。其数学模型定义在图G=（V，E）上，其中V=v1，vn，vn+1，vn+m，E=（vi，vj）；v1，vn表示有N（n=1，N）个待服务的客户点；vn+1，vn+m表示有M（m=1，M）个配送中心，每个配送中心拥有Km（m=1，M）辆载重量均为Q的车辆（相同车型），每辆车一次配送的最大行驶距离为D。每个客户点的需求量分别为qi（i=1，N）。Cij是弧，表示线路（vi，vj）E的费用，或距离，或其他定义。（ETi，LTi）表示客户要求的服务时间窗，Si表示车辆到达用户i的时间，TEi表示在ETi之前到达客户i时需要等待的时间（TEi=ETi-Si），提前到达的单位惩罚因子是PE，TLi表示在LTi之后到达客户i的延迟时间（TLi= Si-LTi），延迟到达的单位惩罚因子是PL，tij表示配送车辆由客户i行驶到客户j的时间，Ti表示在客户点i卸货的时间。为了合理求解，模型假设如下：（1）车辆载重量应能够满足配送路径上各客户的需求量之和；（2）车辆的最大行驶距离应能满足每条配送路径的长度；（3）每个客户的需求必须满足，且只能由一台车辆送货；（4）要求在规定时间内完成配送服务，否则将根据违反时间窗的程度给予一定的惩罚。 若以配送总里程最短为目标函数，则可建立数学模型如下： 变量定义：Xijkm= 1 配送中心 m 的车辆 k 从客户 i 行驶到客户 j ；0 否则. Yikm=1 客户 i由配送中心 m的第 k辆完成；0 否则. Min Z=Mm=1Kmk=1n+mi=1n+mj=1（Cij+max（0，PETEj）+ max（0，PLTLj）Xijkm（1） S.T.iqiYikmQ（2） ijCijXijkm=D（3） mkYikm=1（4） ikmXijkm=1（5） ETiSk（i-1）+T（i-1）+t（i-1）iLTi（6） Xijkm=1 or 0（7） Yikm=1 or 0（8） 上述模型中，目标函数式（1）即要求配送总里程最短（各条配送路径之和最短）。同时对于违反时间约束的路径，按照设定的惩罚因子，适当增大目标函数，这将把违约成本考虑到目标函数中；式（2）保证车辆的载重量大于等于每条路径上各客户的货物需求量之和；式（3）保证车辆一次配送的最大行驶距离应大于等于每条配送路径的长度；式（4）保证每个客户都得到配送服务，不会遗漏；式（5）保证限制每个客户仅能由一台车辆提供服务；式（6）是时间约束，车辆到达客户i的时间=车辆到达路径排列中位于i之前的客户的时间+在前一客户的卸货时间+从前一客户到客户i的运行时间，到达客户i的时间满足客户i的配送时间约束，如果违反时间约束，将增大目标函数值；式（7）和式（8）是变量取值约束。 三、基于软计算的救灾物资多配送中心调度问题求解 1.构建虚拟配送中心 首先确定一个可以包含所有配送中心的圆，然后再随机取得圆的一个内点作为虚拟配送中心的坐标。事实上，虚拟配送中心所处的位置并没有太多的实际意义，只是从方便分析问题进而构建完整的配送网络图而言，最好将虚拟配送中心确定在多个配送中心所形成的网络图的中心。 各配送中心之间、各客户点之间、各配送中心与客户点之间的距离（或成本，或其它度量标准）仍采用公式D（Ci，Dj）=（Xci-XDj）2+（Yci-YDj）2进行计算。 由于采用虚拟配送中心的求解思路，就将问题转换成虚拟配送中心0向（N+M）个客户配送的问题。设多个配送中心和客户点编号为（1，2，N，N+1，N+M；其中N+1，N+M为实际配送中心，虚拟配送中心编号为0）。各个客户点的配送量是qi（1，2，N，N+1，N+M），其中实际配送中心的需求量qi为0。虚拟配送中心的车辆总数为K0（各实际配送中心车辆的总和）。客户点i到j的运距为Cij（i，j=1，2，N，N+1，N+M）；虚拟配送中心到实际配送中心的运距为d0j=dj0=0（j= N+1，N+M），表示没有距离，但其与各客户点的距离d0j=dj0=（j=1，N），表示没有通路。t0j=tj0=0表示虚拟配送中心到实际配送中心的时间为0，Ti=0（i=N+1，N+M）表示在实际配送中心的服务时间为0。 2.遗传算法的设计 （1）染色体编码。由于多配送中心物流调度问题的特殊性，即采用不同的车辆数，个体的长度会有所变化，因此本文采用的个体（染色体）编码为可变长度的十进制实数编码。 （2）初始化种群。在设定个体数量即种群规模（Num）的情况下，可以进行种群初始化。首先，通过随机方式产生互不重复的N个由1xN之间的随机整数组成的串，作为客户排列基因串，构成一个个体，重复Num次就能得到整个种群的客户排列基因串。但此时只是客户点的全排列，而没有实际配送中心。假定各个实际配送中心有足够的货物和车辆可以满足配送需求，则车辆从虚拟配送中心出发选择第一个可选客户（即各个实际配送中心）的概率是相同的，均是1/（可作为车辆第一个配送客户的实际配送中心的数量）。这时可以通过常用的轮盘赌法来选择此车辆的第一个配送客户，再在已产生的多个客户基因串中随机选择一个串，将选定的第一个配送客户插入到客户串的最前端，然后根据车辆载重限制及客户需求时间窗约束，为此车辆分配将要服务的客户，当达到载重限制或时间约束时，就将第一个配送客户插入，就能完成第一辆车的配送路径初始化。重复轮盘赌法产生新的子路径的第一个客户，再按上面的方法构造第二台车的配送路径，直到将全部客户都分配到相应的路径中。重复上面的步骤Num次，就可以将种群初始化完成。需要说明的是，实际配送中心的编号在基因串中必须成对出现，构成一个循环的运行路径。 （3）适应度函数。给定一个个体x，该个体对应一个配送方案，即对应着数学模型的一个解Z（x）。由于目标函数是求极小值，因此使Z（x）越小的个体，其适应性越强。目标函数值不会出现负值，因此可以用Z（x）的倒数形式作为对应的适应度函数，即Z（x）=1/Z（x）。当Z（x）越小时，Z（x）越大，则个体的适应值越大。对于违反约束的个体，可以在其适应值基础上增加一个合适的为负值的惩罚函数M（x），这样就能减小相应个体的适应值，最终影响个体进入下一代的机会，同时适应值越大的个体越能在遗传操作中进入下一代种群。 （4）选择算子。使用最佳保留策略进行优胜劣汰操作，即找出当前群体中适应度最高的个体不参与交叉和变异操作，而用它替换掉本代群体中经过交叉、变异等操作后所产生的适应度最低的个体。 （5）交叉算子。对新产生的子个体需要进行插入配送中心操作，以产生完整的子代。首先，随机选择一个配送中心将其插入C1的第一位基因前面，然后根据车辆容量约束将此配送中心标识插入满足约束的最后一位基因的后面，这样就形成了一条路径，即某配送中心某辆车的运行路线。再随机选择一个配送中心重复上面的操作，直到完成对C1的划分。在此特别指出的是，对于车辆满载率不足的某条路径，在时间约束上可以适当放宽，因为时间约束已在目标函数中进行了转换处理，违反时间约束越严重的子代个体，其适应值越低，越容易被淘汰。此时考虑车辆运行的满载率，将更好地降低车辆的运行成本，提高规模效益。对子代个体C2也采取同样的方法进行调整。 （6）变异算子。变异操作是在群体中随机选择一个个体，对其以一定的概率随机改变个体中某位或某几位基因的值或排列顺序。本文采用局部搜索机制来完成个体变异操作。对当前选中的个体随机选择S个基因对（i，j； 其中i，j=1，s），对每一对基因进行换位操作，检查基因换位后个体的适应值是否提高。如果个体的适应值有所提高，则保存基因换位操作后的个体，并退出局部搜索。如果在对S个基因进行检查后，个体的适应值都没有提高，则根据Metropolis准则选择一对基因进行交换后替换父个体而生成新的个体。 四、结论 自然灾害的发生不可避免，但灾难发生后对应急物资进行合理调配，可以有效降低灾难造成的生命和财产损失。根据救灾物资多配送中心调度问题的数学模型及基于软计算的求解方法，得出结论：有效解决突发性自然灾害导致物质需求的不确定性与物资需求的紧急性之间的矛盾，可以在灾难发生后根据每种物资需求的紧急程度确定配送线路和配送时间；同时，引入多配送中心更符合灾后物资调运的实际情况。 参考文献 郎茂祥.多配送中心车辆调度问题的模型与算法研究J.交通运输系统工程与信息，2006，10（5）：65-39. 钟石泉，贺国光.多车场车辆调度智能优化研究J.华东交通大学学报，20