基于遗传算法的物流云服务平台任务调度研究

（重庆邮电大学 经济管理学院，重庆 400065）

0 引言

随着“大数据（Big data）”时代的到来，各行各业的业务数据如海量洪流般的产生，数据以及数据处理对企业的发展和创新有着至关重要的作用。物流业作为我国的战略性基础性产业，必然也会受“大数据”时代的影响，人们对物流服务的需求更加多样化和复杂化，物流运单信息呈现海量增长趋势（尤其是在“双11”、“购物狂欢节”等节假日时期，各大电商平台促销活动激烈，导致人们的消费行为高度集中），更要求物流调度对市场变化具有更高的灵敏性和适应性，而物流调度的主要难点在于如何用更少的时间对需求不同、运单量极大的物流服务进行快速合理的分配。

近年来，在云计算、物联网和供应链管理的综合模式下，产生了一种新型物流服务模式，即物流云服务（Logistics Cloud Service，LCS）。物流云服务是一种在网络技术支持下，通过物流云服务平台整合物流资源和客户资源从而形成对应的物流资源云，并根据客户需求智能管理和调配物流资源，为客户提供便捷、优质的个性化物流服务。与以往的物流服务模式相比，物流云服务更加注重服务的专业化和个性化，通过构建按需供应、资源高度共享的物流云服务平台来实现对全社会物流资源的分配和调度。基于这种模式，客户可以快捷地享受到最适合的物流服务，而作为物流服务提供方也能以最少的时间对物流资源进行调度分配来满足客户的个性化需求。但是，由于我国物流行业起步较晚，物流云服务模式尚在发展初期，针对如何快速地实现物流资源与需求任务的动态组合、智能匹配和优化调度的相关研究就尤为重要。

关于物流云服务以及物流云服务模式下的任务调度研究，国内外学者取得了一定的成果。林云等人认为物流服务具有云计算的技术特征，提出了面向供应链的物流云服务模式；陈典斌探讨了物流云服务的设计与运行措施；徐骁勇等人以任务执行时间与能耗作为优化目标，建立了一个节能调度模型，并将非支配排序遗传算法（NSGA-II）应用于云计算的节能调度问题；郑小强等人提出了一种云遗传算法来解决复杂维修物流任务的组织和调度；李振汕等人针对系统处理大规模物流调度信息能力不足的情况，提出了一种基于云计算环境下的物流资源调度优化模型对问题进行求解；孙大为等从理论上对云资源调度模型进行了系统的建模分析，提出了一种基于免疫克隆的偏好多维QoS的云资源调度优化算法；张卫等人结合云模型和蚁群算法对制造服务调度问题制定了一种求解策略，以实现制造服务资源的优化配置。

遗传算法（Genetic Algorithms，GA）是一种模拟自然进化的仿真算法，它将问题表示成“染色体”的适者生存过程，通过“染色体”群的一代代不断进化，经过复制、交叉和变异等操作，最终收敛到“最适应环境”的个体，从而求得问题的最优解或者近似最优解。因为遗传算法直接以目标函数作为搜索信息，不需要梯度等高等价值信息，并且采用自适应随机搜索技术，使用多个搜索点的搜索信息，因而它具有高度的灵活性、并行性和很强的通用性。本文基于物流云服务平台强大的信息整合能力，采用遗传算法对物流云服务平台中的物流任务进行调度优化，最后进行仿真实验，证明了遗传算法对实现物流云服务平台任务调度的有效性和可行性，实现了兼顾最大化资源利用率、最小化调度时间以及最低运营成本三方面目标的物流云服务平台任务调度优化。

1 物流云服务平台概述

1.1 内涵作用

物流云服务平台（Cloud Service Platform,CSP）是面向各类物流企业、物流枢纽中心及各类综合型企业的物流部门等的完整解决方案，依靠大规模的云计算处理能力、标准的作业流程、灵活的业务覆盖、精确的环节控制、智能的决策支持及深入的信息共享来完成物流行业各个环节所需要的信息化要求。它是传统物流信息服务平台的完善与升级，为解决当前物流资源共享困难、资源利用率不高、信息不对称等问题提供了新的解决思路。

1.2 体系架构

物流云服务模式主要由三个部分构成，即：物流服务需求方（Logistics Cloud Service Demander,LCSD）即用户层、物流服务提供方（Logistics Cloud Service Provider,LCSP）即资源层、云服务平台（CSP）即云端服务层。CSP主要由个性化物流服务推荐中心、物流云调度中心和服务质量监控管理中心三个部分构成，它是连接LCSD和CSP的桥梁和枢纽，负责建立完整的供需服务链。LCSD通过CSP发布自己的个性化物流需求，LCSP通过CSP发布自己已有的物流资源和服务，CSP通过对LCSD的物流需求进行分析，然后对LCSP所提供的物流资源和服务进行整合、检索和匹配，建立起满足LCSD个性化需求的物流服务解决方案并进行相应的资源调度。物流云服务平台体系架构如图1所示。

图1 物流云服务平台体系架构

1.3 任务调度

物流云服务平台下的任务调度主要包括以下两个方面：

（1）物流硬件资源调度。主要是为了解决当企业拿到一批物流任务之后，应当如何调度现有的车辆、人工资源以及车辆的路径优化等问题；这个方面是传统物流企业最为关心的问题，随着物流行业的发展，此类问题的解决方案已经较为成熟，故本文不再具体讨论此类资源调度问题。

（2）物流管理服务资源调度。主要是解决当物流云平台面临多批次的任务申请时，应当如何合理地分配云端的服务器、存储资源以及任务实施者，以达到高效的平台运行效率和较低的运营成本。这也是当下物流云服务平台最为关心的问题，也是本文的研究重点。

2 物流云服务平台下的任务调度模型

2.1 问题描述

本文要解决的问题是同一类物流服务需求方（LCSD）向云服务平台（CSP）提出物流需求，CSP对提交上来的物流任务进行批处理，然后整合物流云服务提供方（LCSP）已有的物流资源和服务，将物流任务和物流资源和服务进行检索匹配，并进行相应的物流云调度。为了提高云平台的服务质量，本文建立了一个兼顾资源利用率、调度时间与运营成本的多目标优化模型，来指导物流云服务平台下的物流任务调度分配。

2.2 假设条件

由于物流云服务环境下的任务调度非常复杂，包含了各种不确定因素，因此，为使物流云服务平台下的任务调度模型化，需假设以下前提条件：

（1）LCSD的性质相同或相近，需要接受服务的时间差别较小；

（2）各个LCSD都是互相独立的，且互不干扰；

（3）LCSD的数量远远大于LCSP的数量；

（4）CSP对批量物流任务的处理具有顺序性，本批任务完成以后才可以进行下一批物流任务的分配和调度；

（5）每个LCSP工作能力相同，即对于同一个物流任务的完成时间相同；

（6）不考虑LCSP具体如何处理任务，当一个任务分配给某个LCSP，本模型只关心其完成该任务的时长，不考虑LCSP如何调配人员和车辆等具体问题；

（7）物流云服务任务调度成本仅考虑物流云服务平台的运营成本。

2.3 模型建立

基于以上前提，可以对物流云服务平台下的任务调度做出如下描述：用Q表示LCSD的数量，P表示LCSP的数量，调度工作是将Q个需求通过CSP分配给P个LCSP完成。设第i个LCSP分配到Ki个任务，Ci为每次使用云平台的开销（包括带宽、存储容量等费用），Bi为每个LCSP单位时间内最大任务承载量，Ki/Bi则为每个LCSP的使用率，本文将其定义为该LCSP的资源利用率，这样，物流云服务平台下的任务调度的多目标优化模型表示如下：

其需要满足以下约束条件：

其中：tij为第j个任务使用第i个资源的时间；Ti为第i个LCSP完成所分配到的任务所需要的时间；）表示完成该批任务所需要的时间；表示完成该批任务LCSP的平均资源使用率；表示完成该批任务的成本。本模型是一个多目标的优化问题，其优化目标综合考虑了调度时间，资源利用率以及调度成本，即使得完成任务的所用的时间最少，资源利用率最高，同时相应的调度运营成本最低。

2.4 模型分析

本模型是一个多目标整数规划问题，为了简化求解，引入偏好向量λ=（x,y,）z将问题转化成单目标整数规划问题：

这样，只要定义好偏好向量λ=（x,y,）z，问题便可以通过遗传算法等启发式算法进行求解了。

3 物流云服务平台下的任务调度遗传算法设计

3.1 编码与种群初始化

编码机制是遗传算法的必要步骤，对于应用于不同问题的编码，目前还没有统一的方法。DeJong提出了两条操作性强的实用编码原则：（1）有意义的积木块编码原则：应使用能够易于产生与所求问题相关的且具有低阶、短定义长度模式的编码方案；（2）最小字符串编码原则：应使用能使问题得到自然表示或者描述的具有最小编码字符集的编码方案。

常用的编码方案有二进制编码、Gray编码等。从本质上看Gray编码是二进制编码的一种转换，本文采取Gray编码的方式来对上文中提出模型中的自变量进行编码。Gray码是依靠二进制码进行转换的，转换规则如下：

（1）对n位二进制的码字，从右到左，以0到n-1编号；

（2）如果二进制码字的第i位和i+1位相同，则对应的格雷码的第i位为0，否则为1（当i+1=n时，二进制码字的第n位被认为是0，即第n-1位不变）。

3.2 适应度函数与选择

在遗传算法中，适应度函数即为本文的目标函数，且具有非负性，任何情况下都大于等于0，其值越大越好。

物流云服务平台面向不同的企业和用户，不同的物流服务需求者对于目标函数的追求也存在较大差异，比如：快消或季节性产品（例如时装），物流速度也就是物流任务的完成时间是其核心指标，则相对的偏好向量λ=（x,y,）z中的y值就会大一些。企业用户可以根据自身的物流需求定位以及订单的特性，参考物流云服务平台的相关调度参数的历史数据，进行偏好向量的设置。

问题模型所涉及的目标函数包含三个部分：资源利用率、调度时间以及运营成本。考虑到本文给定的物流云服务模式下资源服务的分布性，在建模过程中考虑了物流云的相关信息。通过对服务选择链进行解码，就可以得到服务质量参数和服务的执行成本。而物流成本和交货期，需要结合两条链进行解码。本文选用主动调度的解码方式来实现编码串到参数的映射，根据子任务顺序链中各子任务的排列顺序，结合服务选择链，确定每个子任务所选服务的执行开始和结束时间，通过该子任务所选的服务，所属企业以及子任务的所属企业等相关信息，确定物流时间和物流成本。

4 实验仿真及结果分析

4.1 实验仿真

为了验证本文提出的基于遗传算法的物流云任务调度模型的合理性和算法的有效性，进行了仿真实验。其中为了仿真的可实施性，本文对模型进行了简化，将复杂的多目标优化问题通过偏好向量转化成单一目标的优化问题。遗传算法的适应度函数值（Fitness）即为上一章所阐述的目标函数。利用MATLAB上谢菲尔德大学开发的遗传算法工具箱以及Python上的遗传算法开源算法对本文提出的模型进行仿真。

本文算例是根据参考文献[11]给出的问题修改而得。假设现有10个LCSP，其服务申请的响应时间如表1所示。

表1 LCSP服务申请响应时间 单位：m

与此同时，有100个LCSD，其业务完成时间如表2所示。

表2 LCSD业务完成时间 单位：m

每个服务器的使用成本如表3所示：

4.2 仿真结果

表3 每台服务器的使用成本 单位：元

设置每个LSCP每天最大提供服务时间为12小时。通过MATLAB仿真得到最优调度方案如表4、图2至图4所示：

表4

图2 目标函数值变化曲线

图3 调度成本变化曲线

图4 适应度函数变化趋势图

4.3 结果分析

从上一节中可以看出，利用文中所阐述的遗传算法，经过100代迭代计算，适应度函数可以收敛。算法完成了将100个LCSD任务分配给10个LCSP的任务，并且当偏好向量λ=（0.4,0.4,0.2）的情况下，其中的一个最优解为176.3，在此情况下服务成本为80.0元，服务所需时间为507.3分钟。

5 结束语

本文综合考虑资源利用率、任务调度时间以及调度运营成本三方面指标，与以往研究相比考虑更加全面，建立的物流云服务平台下的任务调度模型通过遗传算法求解并通过仿真验证，仿真结果显示，目标函数值随着迭代次数的增多逐渐呈现上升趋势，适应度函数逐渐减小，调度成本也逐渐减小，证明了本研究的实际有效性，为物流云服务模式下的任务调度问题提供了新的解决思路。

但本文的研究还有需要改进的地方，比如本文考虑的物流云服务平台的调度运营成本，并未考虑物流云服务提供商的服务成本以及物流云服务需求者的消费成本，这一点对于提高综合服务质量缺乏一定的说服力，需要在以后的研究中得到解决，从而为物流云服务模式的发展和推广提供更有效的解决方案和理论技术支持。

参考文献：

[1]陈典斌.物流云服务——供应链下的物流服务新模式探析[J].农村经济与科技，2017,28(14):65-66.

[2]占天异，丁一，姚锦元,等.物流云服务下动态设施选址问题研究[J].河北工业科技，2014(3):193-198.

[3]许波，赵超，祝衍军,等.云计算中虚拟机资源调度多目标优化[J].系统仿真学报，2014(3):592-595,620.

[4]邰英英.物流云服务的物流服务新模式[J].科技经济市场，2016(11):176-177.

[5]梁红波.云物流和大数据对物流模式的变革[J].中国流通经济，2014(5):41-45.

[6]姜妍旭.基于双边资源整合的云物流服务平台研究与开发[D].哈尔滨：哈尔滨工业大学（硕士学位论文），2015.

[7]林云，田帅辉.物流云服务——面向供应链的物流服务新模式[J].计算机应用研究，2012(1):224-228.

[8]崔涛.基于云服务优选的最节能物流运输调度系统的设计[J].现代电子技术，2016,39(20):138-141,145.

[9]张晓磊，马从安，申晨.物流云服务下基于改进蝙蝠算法的任务调度[J].计算机应用研究，2015(6):1676-1679,1697.

[10]李振汕.云计算环境下的物流资源调度算法研究[J].物流技术，2013(9):339-341,386.

[11]梁庆中.混合云平台上多目标任务调度算法研究[D].北京：中国地质大学（博士学位论文），2015.

[12]熊永华，王静，吴敏,等.面向多目标优化的云制造虚拟资源调度方法[J].计算机集成制造系统，2015(11):3079-3087.

[13]Mengke Yang,Movahedipour Mahmood,Xiaoguang Zhou,et al.Design and Implementation of Cloud Platform for Intelligent Logistics in the Trend of Intellectualization[J].中国通信，2017,14(10):180-191.