云计算下物流配送调度的算法研究

包琼雪

（温州职业技术学院，浙江 温州 325035）

云计算下物流配送调度的算法研究

包琼雪

（温州职业技术学院，浙江 温州 325035）

在分析影响资源调度因素的基础上，建立了云计算环境下的物流资源调度模型，在云计算框架下完成订单信息和物流配送车辆的信息处理，从而得出最合理的物流配送方案。针对物流配送中的车辆调配问题，建立了配送路径算法模型和最小配送成本算法模型，为物流配送方案提供最佳的策略。通过仿真实验表明，该算法具备可行性和优越性。

云计算；物流配送；优化算法；资源调度

一、引言

目前物流企业的货物配送以及订单的分类处理都是通过相关人员的随意的分配。该方式简单易行，然而随着物流业的极速的发展，大量订单的增加使得该种方式效率变得十分低下。云技术是一种虚拟化的技术，用该技术可以实现优势资源的共享，利用优势的资源就可以较好的完成物流业资源分配以及调度的问题。物流企业中的物流配送以及业务调度算法运算过程中不仅要顾及到及时响应的问题，还要对该算法实现的成本进行估计，如果成本耗费过高或者对于客户的响应不及时该方式都是没有意义的。在研究的过程中采取了多约束条件以及遗传学算法方面的知识来解决这些实际的问题[1]。

二、物流资源调度

（一）影响物流调度的因素

物流企业的配送是分段式的,配送过程中有很多不同配送单位协同来完成货物的配送，一般来说,物流企业接到订单之后会对订单进行简单分割，然后由配送车辆将订单中的物品按照事先设定好的路线对货物进行配送。这个过程也就是物流配送的过程占据物流业成本的绝大部分。如何对订单进行合理的分割，确定配送车辆的数量以及配送路线的指定都直接影响了物流配送成本。具体来讲影响物流企业配送成本的主要方面有车辆数量的确定，配送人员的分配，订单的分割，配送路线的合理规划，对于客户需求响应的时间等。物流业的物流配送首先应该优先考虑的是企业的大订单，然后采集零散的较小的订单[2]。接着划分责任配送区域，确定相应的配送时间，在配送的过程中同时要考虑到物流配送的远近以及车辆路线安排的事宜针对配送距离比较远的订单可以采取专门的车辆配送。

图1 配送路线以及配送方案示意图

图1为配送路线方案示意图，图中1-6为配送的地点，中间为配送中心。将1-3点划分为一个配送区域，将4-6点作为另一个配送区域。根据两个区域的订单情况分别设定一定数量的车辆，然后对每次配送的时间进行规定以满足客户对于配送时间的需求。

（二）云计算下的物流调度

由于云计算具有海量数据处理的能力，响应速度比较快，价格低廉而被很多的行业所广泛的使用。由于物流业中物流配送的过程涉及到的车辆数量问题，配送时间问题，配送路线问题都要涉及比较复杂的算法，复杂的算法就对计算机的硬件及运算方式提出了更高要求。传统的计算方式由于时间响应慢，往往达不到物流企业对于实时性的要求，采取云计算的方式来对物流配送的过程中海量的数据进行处理，然后得到物流配送实时性的最小成本同时又满足客户需求的配送方式[3]。

图2 云计算方式下模型的计算方式

三、改进遗传算法下的配送车辆调度

（一）问题提出

一般的物流企业来讲物流配送的环节可以简单的划分为：客户下单，物品分配，配送过程，物品签收，交易完成。影响配送主要成本的还是车辆数据的确定以及配送路线的确定，如果二者设置合理则能够在最小成本下来满足客户的需求[4]。由于在配送的过程中需要满足客户以及最小成本的原则，所以该模型要满足以下的几条规则。

（1）路线划分完成之后，车辆的行走必须要严格按照该路线进行行驶，不得更改。

（2）路径的分支是由多个配送节点之间的相互连接组成的。

（3）规划路径时，不同的路径不能够出现重复的节点。

（4）分支路径的选取要满足上述约束条件。

（5）配送车辆不能出现超载，如果一次配送不能够完全配送完毕，可以考虑多次或多个车辆，但是要在满足客户的基本时间响应需求下，以最小的成本来实现该配送。

（6）每条配送路线都有一个规定的时间阈值，一般来讲配送的时间应该小于该阈值以满足客户对于配送时间的要求。

（二）车辆调度模型

车辆调度模型的建立要遵循上述约定的条件，本文中假设配送点的个数为N个，可以承接配送任务的车辆的数目为M。d（x，y）为点x与点y之间的距离一般来说就是配送距离，R（x）为配送到某个地点x所有的配送物品的数量，Q为配送车辆的最大的载重。D为配送车辆行驶的距离。配送路径的选择以满足尽量多的订单为原则，但是配送路径的选择应该在车辆能够行驶的最大的距离限度之内。则配送方案模型如公式（1）所示。

公式1的含义为采取某种配送方案下物流配送总的路径的长度，也就是第一个配送点x0与第二个配送点x1之间的距离加上第二个配送点 x1与第三个配送点x2之间的距离……加上 xN+M-2与xN+M-1之间的距离最后再加上最后一个点到第一个出发点之间的距离就得到了公式1也就是采取某种配送方案时配送车辆所走过的总的路径。通过约束条件，建立目标函数为满足该约束的成本最低的模型：

在公式2中cij为运输车辆从需求点i运输到需求点j所需要的运输成本，yijK为运输车辆K是否会由i点到达j点，如果运输车辆会经过i到j点之间的路径那么该值就为1否则该值就为0，Pi为在节点i处停留单位时间的成本消耗，Ti为车辆在节点i停留的时间。令F为配送这些点所需的最小的成本。上式就是配送成本最小化模型。根据可支配车辆的出发满足下列条件：

根据载重量的最大载重量的约束要求要满足下列条件：

在公式4中，k为运输车辆，当车辆k经过节点i时xik的值为1，当车辆k不经过节点i时，xik值为0，Qi为应该为节点i所应该配送货物的重量，公式4的含义就是运输车辆k为所有其配送节点配送货物的总重量不应该超过车辆k的最大的载重Qk。配送车辆k在配送节点i与配送节点j之间的配送节点关系满足下列式子：

在公式5与公式6中描述的意义为假设运输车辆k经过i点到达j，那么车辆k一定既经过又经过节点i又经过节点j。根据配送模型对于配送时间的约束条件，要满足下列式子：

公式8的含义为到达节点j所花费的时间与在节点i停留的时间之和再加上运输车辆由节点i到节点j所花费的时间减去M，如果运输车辆经过i到达j那么取值为0否则取值为M，最后要小于或者等于到达j点所花费的时间。在上述模型中物流配送可支配的车辆的集合为（K={1，2，…，m}）。配送过程中节点的集合为（G={1，2，…，n}）。配送中心表示为{0}。Gk为车辆k所配送的所有节点的集合。Ti为货物配送到相应的地点i所耗费的时间。Cij为物流配送到节点i所耗费的成本。Tij为从节点i配送到节点j所耗费的时间。Qi为节点i的配送货物的总量。Qk为配送车辆最大的货运量。Si为在节点i所装卸货物所耗费的时间。为配送车辆出发的时刻。为系统要求的最长配送时间。Xik为物流配送车辆的划分。如果配送车辆经过节点i那么该值为1否则该值为0。Yijk为配送路线规划，如果车辆经由i到j那么该值为1否则为0。

（三）模型算法分析

建立车辆调度模型的目的就是为了以最小的成本F来得到相应的配送方案以及确定配送路线。如果没有上述约束规定那么存在（Pn1+Pn2+…+Pnn）中配送的方式。相应的计算量为（Pn1+Pn2+…+Pnn）m。如果加上上述条件，可支配车辆要满足 ΣQi·xik≤Qk极大值为 IK，符合 Tj+Si+Tij-M（1-yijk）≤Tj极大值节点为Jk，符合T0k+ΣΣyijk（Tij+Si）极大值节点为 Hk，令 Lk=min（Ik，Jk，Hk），那么车辆K的配送选择有ΣPLku种，相应的信息处理量为mk=1（Lku=1ΣPLku），从上述方案可以推出随着N与M的变大，计算量也会随着极速变大。

（四）云计算环境下的算法流程

首先通过模型得出物流配送的车辆调度信息之后就要确定配送调度的优先级次序，并在云计算方式下完成相应配送方案以及配送路线的确定，其算法实现的流程如图3所示。

图3 云计算方式算法流程图

四、仿真实验

仿真试验中采用CloudSim软件来计算得到物流配送的方案，设定相应的仿真情景，相应的配送业务与车辆以及配送地点信息来对该算法进行评估。假设可支配车辆为24，工作人员数量为48，配送车辆最大载货数量为110，配送时间为每个工作日8小时，单件物品的每小时成本为0.6元，一共有5个配送中心，每个配送中心到配送节点之间的成本可以认为是和两点之间的距离成正比，采用不同的运输方案的时候可以确定车辆是否会经历两个点之间的路径，在某个点停留的单位时间成本为5，在每个点停留的时间假设都为5min。仿真的模型为多点的配送模型也就是在某个城市中有多个配送的中心，每个客户端都可能是通过不同的配送中心来送货的，配送中心的位置、数量以及配送点的位置和数量分布如图4所示：

图4 多配送中心实际仿真问题

通过对不同配送方式的计算可以得到表2结果。通过公式2可以计算每种配送方式下物流成本，在本仿真实验中一共有48个配送点，每个配送点可以有5种配送的选择方式，一共有5的48次方种配送方式，通过计算这些配送方式的最小的成本就可以得到如表1所示的配送结果。表1中的结果是通过人工的计算得到的。

表1 人工计算方式配送成本与配送时间

表2为所采取云计算方式下，计算配送方案与配送模型所花费时间，仿真验证结果如下：

表2 云计算方式下配送成本与配送时间

衡量配送调度算法的本文所基于的一个很重要的标准就是公式2中所描述的成本指标，通过云计算方式下和人工配送调度方式下配送成本之间的对比，在订单数分别为 190，200，210，220，230，240，250，260的时候配送的成本原来为9 502，9 703，…，11 824；而采用云计算方式下物流配送方案配送的成本为8 231，8 403，…，9 206；也就是云计算方式下配送的成本都降低了。通过将人工求取的计算结果的时间与云计算方式下的计算的时间进行对比分析可以发现云计算模式下的配送调度算法的实现的时间要比人工快速的多，也相对精确的多。通过云计算技术的运用，能够大大缩短配送方案确定的时间提高配送的效率。

五、结语

通过将云计算技术应用于物流配送过程中物流配送方案的确定以及配送路线确定，在模型的建立过程中通过问题的分解提高的模型的现实意义也加快了模型的运算的速度。通过相应的实验验证云计算模式下的计算相应的配送方案与路线大大减少了相应的求解的时间提高了求解的效率，为物流配送方案的实时性确定提供了理论与现实的可行性。

[1]钮亮，张宝友，2015.基于云计算求解城市物流配送最短路径研究[J].科技通报（5）：184-188，213.

[2]丰佳栋，2015.云计算视角下的第三方物流服务质量创新模型[J].中国流通经济（2）：33-38.

[3]刘章逵，2016.云计算在海上运输物流电子管理系统中的应用[J].舰船科学技术（18）：103-105.

[4]李翔，叶欧，张鹏伟，2016.基于云计算的印刷企业供应物流信息系统[J].包装工程（21）：211-216.

（责任编辑：C 校对：T）

F062.3；F252.5

A

1004-2768（2017）04-0114-04

2017-01-17

包琼雪（1976-），女，浙江温州人，经济师，温州职业技术学院工商管理系讲师，研究方向：企业管理、物流管理。