云物流任务的分配

    本篇论文目录导航：

【题目】云服务在物流行业中的应用探究
【第一章】云物流服务平台架构与运作流程研究绪论
【第二章】云物流运作模式相关理论基础
【3.1 3.2】云物流运作模式的内容
【3.3 - 3.5】云物流平台的运作流程
【第四章】云物流任务的分配
【5.1 - 5.3】临沂市小商品云物流运作模式的构建
【5.4 5.5】临沂市小商品云物流任务的分配
【结论/参考文献】物流行业中云计算的应用研究结论与参考文献

　　第 4 章 云物流任务的分配

　　4.1 云平台分配物流任务的必要性。

　　云物流是信息共享的平台，云平台统一管理物流资源信息、分配物流任务，比如车辆完成运输后，回程时再次登陆云平台，发布车辆的运输路线、时间和车容量等资源信息，云平台根据整合资源信息向车辆分配任务。

　　所有物流资源的信息由云平台统一分类、管理，云平台按照完成总任务的成本最低、时间最短为目标，因此涉及合理任务分配，云计算按照本文构建的物流任务分配过程和分配模型规则和逻辑进行编程，云物流任务分配为云计算的开发奠定基础。

　　4.2 云物流任务分配方式的确定。

　　4.2.1 云物流任务分配的目标。

　　云平台上物流任务是动态的，用户不断在云平台上发布物流任务信息，云平台每隔一段时间刷新一次任务池，而云物流企业在云平台上发布的物流资源信息要经过云平台管理人员实地考察和审核，在一定时间内，物流资源信息的审核所需的时间比任务发布的时间长，所以云物流平台中物流资源是相对固定的，物流任务是动态的。

　　云物流任务分配的目标：云平台上动态物流任务完成的总成本最小、时间最短。

　　4.2.2 云物流任务信息的分配过程。

　　本文根据云物流任务可分割、信息量大、易形成规模的特点，通过管理云平台上的物流任务信息，把物流任务的信息按活动类型进行分解，然后重新组合同类型的物流活动信息，与物流资源信息相匹配，完成云物流任务分配的过程，如图 4-1所示。

　　（1）确定云平台上的物流任务。将云平台上的采购任务、配送任务和回收任务等任务订单信息等发布到云平台上，云平台的物流任务种类繁多，数量庞大，本文认为，发布到云平台上的物流任务大多都是可完成的。

　　（2）分解物流任务信息。云平台上待分配的综合型物流任务信息，内容复杂多样，不便于任务的执行，对复杂、零散的任务订单进行专业化分工，按服务类型分解为运输、装卸、存储、加工等物流活动信息，复杂物流任务信息的分解方法有两种。

　　第一，串联型。串联型物流活动是物流作业有前后的衔接关系的物流任务，作业任务的各个环节紧密相连，前一项活动的完成情况对后一项活动有直接影响。比如装卸和搬运活动的信息，二者作业的对象、地点、数量等信息都相同，时间信息链接紧密，云平台可以将其整合为一项串联物流活动的信息，分配给一项物流资源完成。

　　第二，并联型。并联型物流活动信息是一个任务订单中存在可以同时进行的物流活动信息，每个订单中类似的活动信息可以组合为一项整合任务。如回收物流任务中存在装卸搬运、加工包装和信息传递 3 种物流活动的信息，配送物流任务也有装卸搬运、加工包装和信息传递这 3 种物流活动的信息，云平台就把两项任务中共同的装卸搬运活动信息分别打包为整合的任务信息，在云物流任务池输出两项任务的装卸搬运活动信息共同的装卸对象、数量、时间和地点信息；加工包装活动和信息传递活动信息的整合也是如此。

　　在实际物流任务中，包含以上两种较为复杂的物流活动为混合型，混合型也依照上两种方式拆分为串联型物流活动信息或并联型物流活动信息，分别指派给物流资源完成。

　　（3）整合物流任务信息。将分解后的物流活动重新打包，每一项任务中相同的物流活动合并为运输整合任务信息、装卸整合任务信息、存储整合任务信息和加工整合任务信息，云物流任务池输出打包后的整合任务信息，即图 4-1 中的任务打包环节，这时的物流任务已经形成规模化，在云物流平台等待配置资源。

　　（4）匹配任务和资源。将打包后的整合物流任务，与云物流资源池中经云平台处理、分类过后的物流服务提供商（LSP）发布的物流资源信息类型相匹配，每项物流任务都是有至少一项物流资源可以完成，且每项资源完成任务的时间和成本不尽相同，在任务分配过程中寻找总体成本最低、时间最短的资源-任务组合。

　　4.3 云物流任务分配模型。

　　与非云物流任务分配模型相比，本文构建的云物流任务分配模型有两大特点：

　　一是在成本函数中考虑了云环境下特有的，海量信息在传递过程中由于失真、出错、延误造成的损失和成本，即信息传递成本；二是在时间函数中考虑了云物流任务分配方式下分解物流活动产生的任务衔接时间。

　　云物流平台上任务分配的模型是以总成本最低、时间最短为目标的多目标优化模型。物流的模型中待分配的对象是经过云物流平台打包后的整合物流任务，物流资源是云物流资源池中分类管理的资源。云物任务分配模型中，物流任务至少有一项物流资源可以完成，各物流资源完成任务所付出的时间和费用不完全相同；每一项整合后物流任务只能分配给一项物流资源，有能力的物流服务提供商（LSP），可在云平台发布多项资源信息，在保证任务质量的前提下承担多项物流任务；物流资源相互独立，没有相互约束关系，一项资源的使用不影响其他资源的配置。没有前后衔接关系的两项物流任务，任务衔接时间为零；有衔接关系但已经打包为串联型任务的，分配给同一项物流资源完成，任务衔接时间也为零。

　　4.3.1 符号说明。

　　（1）待分配的云物流任务是经过云平台打包后的整合任务，表示为 i ,令 i = 1,2,……， n;（2） j 表示物流资源，云平台上共有 m 项物流资源，表示为 j =1, 2, ,mL;（3） xi j为决策变量，表示物流任务 i 由资源 j 执行；（4）[ ]ij ijθ θ+?,表示第i项物流资源所提供的服务能力区间；（5）ijc 表示资源 j 完成任务 i 时消耗的单位作业成本；（6） qi j表示资源 j 需要承担的第 i 项物流任务的任务量；（7） ti j表示资源 j 完成任务 i 所需要的单位时间；（8）ijSTx 表示任务的开始时间，ijFTx 表示任务的结束时间；（9）ij ij ijTx = FTx ? STx表示完成第 j 项物流资源完成第 i 项任务所耗费的时间；（10）ijfTx 表示期望该项物流任务被完成所用的时间；（11）ijLFTx 表示有前后关联的紧前任务的最晚结束时间；（12）i（j 1）ESTx+表示有前后关联的紧后任务的最早开始时间；（13）ijζ 表示资源 j 完成任务 i 时产生的货差货损率；（14）iδ 表示物流服务对象的市场价值，即货物的单价；（15）ijv 表示单位物流服务的市场价格，暂不考虑物流中的保价商品；（16） p 表示海量云物流信息在传递过程中出现延迟、损坏和出错的概率，0 ≤ p≤ 1;（17） w 表示信息出错后对物流服务的影响程度， w ∈（0,1），w越靠近 1 说明影响程度越大，造成的损失越大、物流成本越高。

　　4.3.2 模型建立。

　　云物流任务分配的目标函数是总任务完成的成本最低、时间最短，现将成本构成分析如下：

　　（1）基础作业成本。完成云物流平台上运输、仓储、包装加工、装卸搬运等基础的物流任务，其成本为完成该项作业的单位成本与任务量的乘积。

　　（2）货损货差成本。货损货差是衡量物流任务完成质量的重要指标，货损是由于包装任务不达标，装卸搬运过程的不合理操作，仓储管理的失误或突发交通事故等原因造成的货物损失，低货损率是物流安全性的重要指标；货差是指在完成包装、运输、仓储任务时，货物数量与任务要求数量不符的情况，货物种类越多，货差比例越大，货差率是衡量保证物流服务的准确性的标准。

　　式中， qi j表示货物数量，ijζ 表示货差货损率，货差货损率与货物数量和种类呈正相关，任务量越大，种类越多，货损货差率越高；iδ 代表物流服务对像的价值，即货物的市场单价。

　　（3）信息传递成本。云物流平台上信息量庞大，信息传递成本是指在海量的信息传递和搜索过程中，由于信息延迟、失真、出错，而影响任务顺利完成，为货主、物流企业造成的损失。

　　ijv 表示单位物流服务的市场价格，v i j× q表示完成该项物流服务的总价格。p表示物流信息传递过程出现问题的概率，0 ≤ p≤ 1, p 的值由物流服务提供商根据以往一个月内出错的订单占总订单的比重确定，w 的值由管理人员根据经验来确定。

　　（4）作业时间。不同物流资源完成任务所需的时间不同，不同的任务计算时间的量纲也不同，仓储任务以天（d ）为单位，装卸搬运和配送任务以小时（h）为单位，为便于计算，模型中的时间单位都转化为小时（h），任务的计量单位也做无量纲处理，时间分配到任务量中，计算完成每 1 单位任务所用的时间。

　　（5）衔接时间。云平台上的物流任务经过打包整合后，有些任务的执行必须在前一项任务完成的基础上才能进行，有前后关系的两项任务中的衔接、等待时间取决于链接时间较长的部分，在相同环节上所有匹配关系中，取衔接时间的最小值。

　　xi jx i j1（ +）表示第j项任务与第j +1项任务的前后衔接关系，值取 0 表示没有衔接关系，值取 1 时表示有衔接关系。在完成任务链的关键路径上，后一项任务的最早开始时间与前一项任务的最晚结束时间之差中取最大值，保证任务顺利衔接。相同环节上的任务衔接时间取最小值。

　　目标函数式（4-10）表示完成任务的作业成本最小，式（4-11）表示完成任务的时间最短；约束条件式（4-12）表示每项物流任务只能由一项物流资源完成；式（4-13）表示指派给的物流任务的物流资源之和，不得超过云物流平台上的总资源；式（4-14）表示由完成物流任务i完成资源 j时，任务数量必须落在资源 j的服务能力范围之内，即被指派的物流资源可以完成该项物流任务；式（4-15）表示完成物流任务的时间不超过期望完成物流任务的时间，即物流任务必须在规定时间内完成，满足用户需求；式（4-16）表示物流任务 xi （ j1+ ）的开始时间和任务ijx 的开始时间的时间间隔不小于ijx 的作业时间；式（4-17）表示有前后衔接关系的物流活动，后一项物流活动的最早开始时间不得早于后一项活动的最晚结束时间。

　　4.3.3 模型求解。

　　上文所述的云物流任务分配模型，是一个多目标组合的优化问题，由于云平台上物流任务较多，每项物流资源完成不同任务所需的时间和成本均不尽相同，求解过程复杂，根据前人研究结论的比较结果，本文采用搜索速度较快、使用方法简单的遗传算法对云物流任务分配模型进行求解。

　　（1）编码，确定初始种群。云物流任务ix 的数量是庞大的，同样的作业内容由于任务要求的时间、地点不同，会产生不同的任务序号，为避免二进制编码方式产生的染色体长度过长，本文采用自然数编码，随机产生较大的初始种群，防止过早收敛，出现局部最优解。排列顺序表示任务分配结果，如当 （ ）j 1 2n mx = x , x ,… ,  x ,… , x,jx 中的 j ∈ [1, m],上述分配结果表示：1x 完成第 1 项任务，2x 完成第 2 项任务，nx完成第n项任务，n ≤ m.

　　（2）适应度函数设计。一般来说遗传算法只有一个目标函数，而云物流任务分配的模型是成本最低、时间最短两个目标函数，需要将量纲不同的成本、时间两个目标函数做归一化处理，通过定义效用函数分别设定成本和时间权重α 、β ,变为一个目标函数，令 α + β= 1.模型中物流任务完成的成本和时间同等重要，所以 α = 0.5,β = 0.5,对种群个体。

　　maxC 和maxT 为当前迭代结果完成任务耗费的成本和所需的时间，jC 和jT 为由种群jz 执行时，耗费的总成本和时间。当种群中的所有个体都满足约束条件式（4-15）和式（4-17）， μ = 1, （ ）*ijf x 的值越小，适应度越高。

　　（3）选择算子。由于交叉和变异的随机性，优良的基因可能会被淘汰，为保留新产生的越来越多的优良个体，选择算子的过程中采取精英保留策略，把适应度高的父代个体保留下来，不参与交叉和变异操作，直接遗传给子代，防止已经搜索到的最优解遭到破坏，每次随机选取两个个体，适应度较高的一项遗传到下一代。

　　（4）交叉算子。交叉是为了产生新的个体，采用单点交叉，仅交叉父代染色体的编码顺序，随机选取自然数[ i ,j ],交换两组基因。交叉操作频率高，可以尽快收敛到搜索区域，但过早收敛会出现局部最优解，交叉率的取值范围为 0.4-0.99,依据前人的研究经验[56],本文取 0.55.

　　（5）变异算子。在一条染色体上任取两点，将这两点之间的基因实施倒位。如父本个体为（5 1 6 2 3 7 4） ,随机选择从第 2 位到第 5 位之间进行倒位，则产生的子代个体为（5 3 2 6 1 7 4）。当遗传算法通过交叉算子己接近满意解，变异概率越小，可以加速向最优解收敛，一般的取值范围为 0.0001-0.1,本文取变异概率为 0.02.

　　（6）收敛性判定。迭代结果达到 500 次时停止。

　　（7）解码。假设收敛结果为 （ ）j 2 3 1n mx = x , x , x ,… ,  x ,… , x,则表示2x 完成第 1 项任务、3x 完成第 2 项任务、1x 完成第 3 项任务、……、nx 完成第 n 项任务、mx 完成第m 项任务。

　　4.4 本章小结。

　　根据云物流任务信息量大、种类多、可分割的特点，构建了云物流任务的分配过程，按服务类型将订单中的任务信息分解、打包为整合物流任务信息，由云平台根据资源情况，进行统一分配。构建以成本最低、时间最短为目标的云物流任务分配模型，模型中考虑了云物流海量信息的传递成本和任务分解后产生的衔接时间，借助 matlab2014a 的遗传工具箱，求得云物流任务分配模型的解。云物流任务分配为云计算的实现奠定了基础。