大型物流车辆配送线路自适应调度方法

(北京物资学院 信息学院，北京 110049)

大型物流车辆配送线路自适应调度方法

郭键

(北京物资学院信息学院，北京110049)

为了有效提高物流配送车辆的利用率，降低配送车辆的空载率及物流运输成本，需要对大型物流车辆配送线路自适应调度方法进行研究；当前方法多是采用通过对物流车辆配送过程中的调度与路径选择进行分析，建立多类型的物流配送车辆调度模型，并构建改进后的遗传算法，对物流调度模型的算法效率以及计算时间和复杂度进行优化，以获取物流车辆配送调度问题的最优解，但该方法存在过程较为繁琐的问题；为此，提出一种大型物流车辆配送线路自适应调度方法；该方法首先建立物流车辆配送线路调度问题的数学模型，为实现自适应调度方法对数学模型进行优化求出最优解，利用蚁群算法对物流车辆配送调度数学模型的最优解进行优化，获取最优路径的适应度初始化蚁群算法的各客户点之间的信息素，从而得出了优化的最优路径；以优化的最优路径完成对大型物流车辆配送线路自适应调度；仿真实验表明，利用蚁群算法不仅加快了物流配送路线调度优化问题求解的速度，降低了物流运输的成本，而且获取了最优解的概率，比其他调度算法具有更明显的优势。

大型物流；车辆配送；自适应调度；蚁群算法

0 引言

随着经济的飞速发展，物流水平的不断提高，物流平台已成为各行业中必不可少的辅助平台[1]。物流配送加快了经济的发展，带动了人们的消费。但进行物流配送时易受到很多因素的影响，例如客户的位置、客户配送要求、以及配送车辆等多方面，导致物流车辆配送的自适应调度问题越来越严峻[2]。在这种情况下，如何利用有限的车辆高效的安排配送，在配送过程中降低配送成本是该领域急需解决的主要问题。对科学物流进行有效地管理是加快物流配送的效率，提高物流配送服务质量的有效途径[3]。科学的物流管理涉及到很多方面，车辆配送为主要环节，配送指按客户要求进行物品的派发和收揽，物流车辆配送是配送过程中最主要的部分[4]。车辆配送自适应调度的主要目标是满足客户要求的条件下，降低物流配送的成本。引起了很多专家的关注与重视，由于物流车辆配送调度方法具有广泛的发展意义，因此成为物流领域人士研究的重点课题。

近年来也取得了一定的成果，李明对物流车辆调度的优化问题的现状进行了总体的探究，分析了当前物流配送调度问题的现状。徐银聪对物流车辆配送调度的优化方法进行了比较，为物流车辆配送调度过程中进行合理的选择方法提供了依据。郭耀提出了基于物流车辆配送的优化理论方法，主要以物流车辆配送调度的基本理论为主，对单车场和多车场车辆配送调度的优化问题、满载和非满载的物流车辆配送优化问题以及物流车辆配送调度算法的实现进行了详细的介绍[5]。袁庆达提出将搜索算法应用到物流车辆配送线路调度优化问题。李军对非满载物流车辆配送调度问题的遗传算法进行了研究，将基于编码的遗传算法应用于物流车辆配送调度优化问题，利用遗传算法解决物流车辆配送调度问题提供了理论支持。陆杰将遗传算法的思想与物流车辆配送调度的程序设计相结合，对遗传算法进行简单的编程[6]。李宁提出了一个调度算法来解决物流车辆配送的问题，在此基础上利用遗传算法给出车辆行驶的最优路径。高伟伦针对遗传算法求解物流车辆配送调度问题进行了研究。文献[8]提出了一种基于改进遗传算法的物流配送调度方法。主要对物流车辆配送过程中的调度与最优路径进行分析，建立多类型的配送车辆调度模型，在此基础上构建改进后的遗传算法，对物流调度模型得算法效率以及减少计算时间和复杂度进行优化，更加高效的获取物流车辆配送调度问题的最优解，但该方法存在过程较为繁琐的问题。文献[9]提出了一种基于神经网络的物流配送调度优化算法。首先对城市物流配送建立数学模型，建立解决非满载车辆优化路线的神经网络模型。利用神经网络对物流车辆调度进行优化，给出解决物流车辆配送优化调度为一体的具体方法，但该方存在成本较高的问题。文献[10]提出一种基于改进粒子群算法的物流配送调度模型。建立物流配送调度模型，将物流车辆与车辆路径进行编码编成粒子，利用粒子间的协作找出最优物流车辆配送调度方案，对粒子算法存在的不足进行了改进，但该方法存在调度结果不理想的问题。

针对上述问题，提出一种物流配送自适应调度的方法。仿真实验表明，结合蚁群算法加快物流配送自适应调度问题求解的速度，降低了物流运输的成本，具有广泛的实用价值。

1 物流车辆配送自适应调度方法

首先对物流车辆配送建立自适应调度模型，采用调度方法对自适应模型进行求最优解，结合蚁群算法对物流车辆自适应调度的数学模型最优解进行优化，获取最优路径对蚁群算法客户间的信息素进行初始化，从而得出了优化的最优路径；以优化的最优路径完成对物流配送自适应调度问题。具体步骤如下：

1.1 建立物流车辆调度问题的数学模型

首先建立物流车辆配送自适应调度的数学模型，自适应调度的问题主要是对有限的车辆在规定时间内完成任务作出相应的安排。本文主要对物流车辆配送自适应调度问题的可用资源与活动以及调度目标进行研究。

活动主要指有物流配送中心为客户进行配送货物，假设有一个物流配送中心，M表示客户的数目，配送货物的客户位置固定，qi(i=1,2,…,M)表示配送货物的重量。

可用资源指配送货物的车辆，K表示配送车的车辆数，Qk(k=1,2,…,K)表示配送车辆的载重量，Dk(k=1,2,…,K)表示物流车辆单次配送的里程数，Ck(k=1,2,…,K)表示配送车辆单次配送的客户数。

物流调度目标是对调度序列尽心优化求解。满足在配送任务约束的条件下，实现配送车辆里程为最短。

综合上述，建立物流配送自适应调度的数学模型为：

(1)

公式(1)表示物流配送的目标函数，要求车辆配送的总里程最短。

(2)

公式(2)表示车辆配送要求，要求每个客户的车辆配送要求都需要满足。

(3)

公式(3)表示为物流车辆配送里程的约束条件，物流车辆进行调度安排配送时，要求物流车辆配送的任务不可超过单次配送车辆里程的上限。

(4)

公式(4)表示物流车辆配送载重量的约束条件，物流自适应调度安排车辆配送时，要求配送车辆不可超载。

0≤nk≤Ck,Ck≤M

(5)

公式(5)表示是物流车辆配送客户数的约束条件，要求车辆配送路线上客户数不可超过物流车辆单次配送客户数上限，客户数目M为限制的上限。

Rk={rki|rki∈{1,2,…,M},i=1,2,…,nk}

(6)

公式(6)表示物流车辆配送路线的安排。

Rk1∩Rk2=φ,∀k1≠k2

(7)

公式(7)表示是车辆配送隐含的约束，要求每个客户仅货物由一台车进行配送。

其中，doj(j=1,2,…,M)表示物流配送中心到每个客户的距离，dij(i,j=1,2,…,M)表示客户i到j的距离，nk表示第k辆车进行配送服务的用户数(nk=0表示不使用第k辆车)。Rk表示第k条配送车辆行驶的路线，其中，rko=0表示配送中心，rki表示路线k中第i个访问的客户。

1.2 基于蚁群算法的物流配送自适应调度方法

蚁群算法是以蚂蚁寻找食物生成的路径模拟的一种算法，当环境发生变化时，蚂蚁依然可以找出新的路径。

将物流配送车辆的数目比喻为蚂蚁的数目，蚂蚁从物流配送中心寻找最优路径，路径上的物流信息素为路径上的适应值，由公式(8)表示：

τij=F(rij)

(8)

随着迭代次数的逐渐增加，第t+1迭代后物流车辆配送路径的信息素在迭代的基础上由公式(9)表示：

(9)

式中，τij(t)max表示物流车辆配送路径信息素的最大值，τij(t)min表示物流车辆配送路径信息素的最小值，当物流路径信息素逐渐加大时，易过早得出局部的最优解，获取不出全局最优解。当物流信路径息素较小时，易导致迭代的次数过多，收敛的速度逐渐变慢。

第k只蚂蚁在物流车连配送的路径(i,j)间进行转移的概率为：

(10)

式中，τij(t)表示物流车辆配送路径(i,j)物流信息素的浓度，wij表示路径(i,j)间的距离，a表示物流路径信息素的主要程序，b表示物流车辆配送路径耗费的时间。r∈R表示蚂蚁在配送路径中连续经过的客户点。

1.3 蚁群优化车辆配送路径算法的描述

算法输入：蚂蚁的总数量(客户的数目)，任意的两个客户点(i,j)间车辆配送的距离wij，任意客户(i,j)的物流路径信息素的浓度τij(t)，a表示物流路径信息素浓度的主要性，b编号物流车辆配送路径的重要性，allowk表示蚂蚁k访问的客户点，ρ表示物流路径信息素的持久性；

蚁群算法的输出：物流车辆自适应调度的最优路径；

步骤1：迭代次数表示为i=0；

步骤2：第k只蚂蚁从物流配送中心开始出发，依据公式(10)从allowk中选择第j个配送客户点，在进行迭代时，所有的蚂蚁共享一个allowk；

步骤3：当蚂蚁选择配送客户点j作为访问的配送客户点，并且ck+qk≤bk时，可满足配送车辆容量的要求，将j从allowk中删除，依据公式(9)对物流路径信息素进行更新；

步骤4：对于蚂蚁的k=1,2,…,M，假设allowk不为空时，转到步骤2继续进行此步骤，假设allowk为空时，转到步骤5继续进行此步骤；

步骤5：计算蚂蚁当前行走的路径，认定为当前的最优解；

步骤6：迭代次数由i=i+1表示，达到最大迭代次数imax；

步骤7：迭代输出的结果表示为当前的最优解；

2 实验结果分析

2.1 实验数据来源

为确定蚁群算法对物流车辆配送线路自适应调度问题求解的有效性，在P42核3.6GHz，内存为4GB，Windows7的仿真的环境下，利用VC++8.0编程进行一次仿真实验。仿真实验对象为：1个配送中心，10个收货点，5台配送车辆，每台配送车的最大载重量为20，每个收货点配送量由表1所示，物流收货点费用如表2所示，物流车辆配送线路的最优调度方案的最少的费用是950元。

表1 各收货点所需配送量

表2 各收货点的配送费用

为了测试迭代数对蚁群算法求大型解物流车辆配送线路自适应调度问题的影响，分别采用进行迭代100与500次仿真实验，分析迭代次数变化对最少费用的影响，最优方案的最少费用的变化曲线由图1与图2表示。

图1 迭代100次的最少费用

图2 迭代500次的最少费用

由图1和图2可知，随着配送迭代次数的增加，蚁群算法不断向最优解靠近，即贴近最少费用950元，图1、图2对比能看出，配送迭代的次数逐渐增多，寻找最优物流车辆配送自适应调度方案的成功率也在逐渐增加，同时蚁群算法的运行时间也在逐渐增加，降低了自适应调度问题求解的效率，由此本文物流配送自适应调度迭代的次数选择为200次。

2.2 与其他算法性能对比

选择标准粒子算法、改进粒子群算法以及动态规划算法与本文算法进行对比实验。对各种算法进行20次实验，找出自适应调度问题最优解的概率与求解的时间，结果由表3所示。将表3的分析结果进行对比，能得出以下结论：

1)相对于动态规划算法，其他算法的最优求解时间逐渐减少，提高了物流车辆配送自适应调度求解的效率，动态规划算法是利用穷举方式对自适应调度最优解进行搜索，自适应调度问题寻优的次数与调度问题的规模表示为指数变化的关系，实际物流自适应调度应用性较差。

2)相对于其他的智能算法，蚁群算法寻找最优解的成功率逐渐在增加，自适应调度问题求解的时间也逐渐减少，蚁群算法减少了寻找最优解的物流配送迭代次数，复杂度逐渐在下降，增强蚁群算法搜寻的能力，获取更优的物流车辆配送自适应的调度方案。

表3不同算法的综合性能对比

仿真实验证明，利用蚁群算法加快了物流配送路线自适应调度求解的速度，降低了物流运输的成本，具有广泛的实用价值。

3 结论

采用通过对物流车辆配送过程中的调度与路径选择进行分析，建立多类型的物流配送车辆调度模型，在此基础上构建改进后的遗传算法，对物流调度模型得算法效率以及减少计算时间和复杂度进行优化，更加高效的获取物流车辆配送调度问题的最优解，但该方法存在过程较为繁琐的问题。为此，提出一种大型物流车辆配送线路自适应调度方法。仿真实验证明，利用蚁群算法利用蚁群算法加快了物流配送路线自适应调度求解的速度，降低了物流运输的成本，具有广泛的实用价值。

[1]吴 聪,杨建辉.基于改进粒子群算法的物流配送车辆调度优化[J].计算机工程与应用,2015,51(13):259-262.

[2]程八一,李 明.面向生产-库存-配送的联合调度问题及蚁群优化算法[J].机械工程学报,2015,51(12):202-212.

[3]田 冉,孙林夫,唐慧佳,等.多车场物流协同运输调度问题研究[J].计算机工程与应用,2015,51(21):230-236.

[4]李 静.一种基于蚁群改进算法的单向物流配送路径优化[J].电子设计工程,2016,24(10):68-70.

[5]李 雪,聂兰顺,齐文艳,等.基于近似动态规划的动态车辆调度算法[J].中国机械工程,2015,26(5):682-688.

[6]张 玉,贾遂民.多资源约束的车辆调度问题的改进遗传算法[J].计算机工程与应用,2016,52(7):253-258.

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

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

[9]王 旭,谢沐男,邓 蕾.基于粗糙集的物流资源分类方法研究[J].计算机工程与应用,2016,52(14):67-71.

[10]柯俊山,胡 凯,朱文奇.基于启发式算法的乘用车物流运输计划问题研究[J].数学的实践与认识,2015,45(15):89-100.

AdaptiveSchedulingMethodforLarge-scaleLogisticsDistributionVehicleLines

Guo Jian

(School of Information, Beijing WUZI University, Beijing 101149, China)

In order to effectively improve the utilization rate of logistics distribution vehicle and reduce the empty loading rate of distribution vehicles and logistics transportation cost, need adaptive scheduling method for large-scale logistics distribution vehicle lines were studied. But the current method is used to in the process of logistics distribution vehicle scheduling and the choice of path analysis, many model in the process of logistics distribution vehicle scheduling model is established, on the basis of constructing the improved genetic algorithm, the efficiency of logistics scheduling model and algorithm to optimize and reduce the computing time and complexity and more efficient to obtain the optimal solution of logistics distribution vehicle scheduling problem, but the process of this method were more complicated problems. For this, put forward a kind of large-scale logistics distribution vehicle line adaptive scheduling method. This method first to establish a logistics distribution line adaptive scheduling, the mathematical model for the realization of the adaptive scheduling method to further optimization of the mathematical model to find the optimal solution, using the mathematical model of ant colony algorithm for logistics distribution vehicle scheduling optimization, the optimal solution to obtain the optimal path of ant colony algorithm to initialize the fitness of each customer information between the point element, thus obtained the further optimization of the optimal path; In order to optimize the optimal path to complete the adaptive scheduling for large logistics vehicle distribution lines. Simulation experiments show that using ant colony algorithm not only speeds up the logistics distribution vehicle route scheduling optimization problem solving speed, reduce the cost of logistics, and obtain the optimal solution of probability, scheduling algorithm has more obvious advantages than others.

large logistics; vehicle distribution; adaptive scheduling; ant colony algorithm

2017-04-22；

2017-05-15。

北京市属高等学校青年拔尖人才培育计划项目(CIT&TCD201504052)。

郭 键(1975-)，女，辽宁锦州人，博士研究生，教授，主要从事智能监控方向的研究。

1671-4598(2017)11-0166-04

10.16526/j.cnki.11-4762/tp.2017.11.042

F224

A