跨区域多配送中心车辆调度智能优化研究

肖正中，谭建，周玉峰，曾俊

1 贵州省烟草公司黔东南州公司，贵州凯里，556000；

2 贵州财经大学，贵州贵阳，550003

跨区域多配送中心车辆调度智能优化研究

肖正中1，谭建2，周玉峰1，曾俊1

1 贵州省烟草公司黔东南州公司，贵州凯里，556000；

2 贵州财经大学，贵州贵阳，550003

跨区域多配送中心车辆调度是一个典型的NP难题，是当前运筹学领域的一个研究热点。本文采用边界分配法将该问题转化为单配送中心车辆调度问题，并结合遗传算法与蚁群算法求解跨区域配送最优调度方案。以贵州省黔东南州烟草公司物流中心卷烟配送为背景进行了仿真分析，结果表明了算法的有效性。

车辆调度；边界分配法；遗传算法；启发式算法

21世纪电子商务的蓬勃发展为物流行业带来了新的机遇和挑战[1]。由于客户数量巨大，货物需求量和配送时间要求的多样性，在车辆载重、车辆最大行驶距离等方面的约束，使得当前物流问题变得非常复杂，亟需对物流问题建模并研究准确高效的求解算法。

现代物流体系建设主要涉及配送中心选址与配送车辆调度[2]。配送车辆调度是物流系统的关键环节，在配送时间、货物需求量、配送中心车辆数目、车辆载重和车辆最长运载里程等限制下，采用某种算法得到最优配送路线[3]。依据配送中心数目的多少，可将配送车辆调度问题划分为单配送和多配送中心车辆调度问题。在一个物流体系中往往存在多个配送中心共同协作配送特定区域内客户。

跨区域多配送中心车辆调度是针对各配送中心所划定的配送区域进行综合车辆调度，是一个NP难题[4]，随着配送中心数目及客户数目的增加，候选的配送方案数量以指数形式增加。因此，寻找合适的算法快速准确找到配送方案问题的全局最优解是该问题的研究重点。目前很多文献对多配送中心车辆调度问题进行了研究[5-6]，研究集中在两个方面，一是采用一定的客户分配方法将多配送中心问题转换为单配送中心问题，二是设计算法解决单配送中心车辆调度问题。王征等（2013）以顾客时间窗偏离程度最小化和配送成本最小化为目标,在Solomon提出的标准算例上建立了问题的数学模型及其求解算法[7]。马宇红等（2013）针对大规模的多配送中心多车型车辆调度问题提出了一种新的多片段染色体混合编码算法[8]。殷脂和叶春明（2014）提出了采用聚类分析最短距离分配法将多配送中心车辆调度问题动态地分解为多个单配送中心车辆调度问题进行求解的策略[9]。孙壮志等（2014）采用中心聚类、禁忌搜索、局部搜索等多种专业算法研究了卷烟配送调度问题[10]。杨珍花等（2015）采用混合模拟退火算法分析了冷藏车多车型混合配送调度优化[11]。

本文针对多配送中心车辆调度问题，首先采用边界分配法将多配送中心车辆调度问题转化为单配送中心车辆调度问题，其次将单配送中心车辆调度问题分解为车辆分配与单车辆路线优划两个互相关联的子问题，并结合遗传算法和蚁群算法求解。边界分配法是将客户分为边界点位置客户和非边界点位置客户，非边界点位置客户根据最近分配原则分配，边界点位置客户的分配由最大节约距离确定。遗传算法是模拟群体的个体按照它们对环境适应度实现优胜劣汰的进化过程。蚁群算法是模拟蚂蚁觅食行为的优化算法，采用分布式正反馈并行计算机制寻找最优路径，易与其他方法结合，且具有较强的鲁棒性。

本文创新点体现在两个方面：（1）提出了配送中心-客户距离关系矩阵，研究了该矩阵的对称性等基本性质，并将路线长度、载重量计算等转换为矩阵运算，使得优化目标和约束条件的表述更加清晰严格；（2）采用边界分配法结合遗传算法、蚁群算法对多配送中心车辆调度问题进行求解，并根据黔东南州烟草公司物流配送中心调动数据进行仿真验证，仿真结果说明了算法的有效性。

1 多配送中心车辆调度问题数学模型

多配送中心车辆调度模型中，配送中心表示为集合P={p1，p2，…，pm}，客户表示为集合Q={q1，q2，…，qn}，且m＞1，n＞1。客户的货物需求量表示为集合R={r1，r2，…，rn}，其中ri表示客户qi的需求量。车辆调度问题中一个重要输入参数是配送中心与客户相对距离，该参数直接影响到最佳调度路线的分配。为准确描述配送中心与客户的相对距离，本文提出距离关系矩阵：

其中，dx,y表示位置x到位置y的实际最短货运距离，dx,y会随道路维修等实际情况变动，因此具有时间相关性，但考虑到这种变动情况很缓慢且离散，单次配送路线规划中假定dx,y是常量。当两地之间最短货运距离不确定时，dx,y也可用球面距离代替。关于距离关系矩阵有如下两个结论：

（1）dx,x=0，即同一位置之间的距离为0；

（2）D=DT，即地点x与地点y的距离等于地点y与地点x之间的距离。单向道路可能会导致dx,y≠dy,x，考虑到这种影响很小，本文假定dx,y=dy,x。

利用矩阵D可计算配送路径的行驶距离。例如某一运输车从配送中心p1出发，先送货到客户q1，再送货到客户q2，然后回到配送中心p1。将其配送路线简记为L=p1→q1→q2→p1，则该路线的总距离为d（L）=dp1,q1+dq1,q2+dq2,p1。由于每辆运输车均是从某一配送中心出发，经过若干客户后回到原配送中心，所以配送路线L在拓扑学上是一个简单环。记QL为路线L上的客户集合，例如Qp1→q1→q2→p1={q1,q2}。在每个客户的货物仅由一个车辆配送的前提下，任两个配送路线QL的交集应为空集。每条配送路线上运输车总载重量G(L)为该路线途径的客户的需求量总和，例如G(p1→q1→q2→p1)=r1+r2。实际问题中，存在车辆载重量和单次最大行驶距离的限制，即d(L)≤dup，G(L)≤Gup，其中，dup表示一次配送最大行驶距离，Gup表示车辆最大载重量。由于配送产品均为卷烟，其体积与重量基本呈正比，因此，本文只考虑车辆最大载重量。

总配送成本包含很多方面，如车辆油耗、车辆损耗、人工成本，时间成本等等。总成本大致与车辆总行驶里程成正比，可假设比例系数为常数k，此时多配送中心车辆调度问题的优化目标即为总配送成本最小。综上得到车辆调度问题的数学模型为：

其中，四个约束条件分别为：（1）最大行驶距离约束；（2）载重约束；（3）每个客户仅由一台车辆送货；（4）所有客户需求全部满足。该优化问题可分为两步求解。步骤一：为每位客户分配一个配送中心负责为其运货；步骤二：每个配送中心选择最优的车辆数以及配货路线完成配货。若采用穷举法则第一步的问题复杂度为O(mn)，第二步是m个相互独立的单配送中心车辆调度问题，该问题具有NP复杂度。鉴于问题的复杂度，每个步骤均需采用一定的算法快速求解。下文分别用边界分配法和遗传算法解决步骤一与步骤二。

2 客户分配方法

2.1 最近距离分配法

步骤一可看做一个聚类问题，聚类中心为配送中心，聚类目的是将每个客户按一定标准分配给某一配送中心。最简单的标准将客户归类到与其距离最近的配送中心，该方法已经在部分文献中使用[6-7]。但该聚类方式在某些情形下不合理，例如某一地区包含两个配送中心和两个客户，坐标分别为p1∶(2，2)，p2∶(6，2)，q1∶(3，5)，q2∶(5，5)，如图1 所示。

图1配送路线比较Fig.1 Distribution route comparison

配送路线一的总运输距离为：dis1=Dp1→q1→p1+Dp2→q2→p2=dp1,q1+dq1,p1+dp2,q2+dq2,p2=12.64

配送路线二的总运输距离为：dis2=Dp1→q2→p1=dp1,q1+dq1,q2+dq2,p1=9.4

当采用最近距离分配法时，得到配送路线一，这种配送方案显然不如配送方案二。最近距离分配法仅考虑了配送中心与客户之间的距离，而未考虑客户之间的距离。

2.2 边界分配法

采用边界分配法分配客户时包含两个过程：首先确定边界点，其次是计算最大节约距离，并将边界点分配给最大节约距离对应的配送中心。取矩阵D的左下子块并记为M，即

将矩阵M的第i行记为Mi，则Mi表示客户qi到各配送中心之间的距离。记min（Mi）为Mi中最小的元素值；记submin（Mi）为Mi中次小的元素值。取一个临界值σ，σ∈[0，1]。当min（Mi）/submin（Mi）＜σ时，将客户i分配给min（Mi）相应的分配中心；当 min（Mi）/submin（Mi）＞=σ时，将客户i标记为边界点。按照下述步骤为边界点分配配送中心，记

则Spi（qk）表示当边界点qk分配给配送中心pi时所能节约的配送距离。则表示分配边界点qk后所能节约的最大配送距离。将边界点qk分配给对应的pi。

临界值σ取值会影响到边界点的分配。当σ=1时，任何客户均按照最近距离分配，边界分配法退化为最近距离分配法；当σ=0时，任何客户均是临界点。边界分配法既考虑到了配送中心与客户之间的距离，又考虑到了客户与客户之间的距离，因此更加合理。

3 车辆选择与线路优化算法

3.1 基于遗传算法的车辆分配方案

边界分配法分配客户之后，多配送中心车辆调度问题转换为单配送中心车辆调度问题。单配送中心车辆调度问题可拆分为车辆选择和路线优化两个相互关联的子问题。车辆选择是单配送中心车辆调度问题的核心，可采用遗传算法解决[12-13]，其流程如图2所示。

图2 遗传算法流程图Fig.2 Flow chart of genetic algorithm

该矩阵表示将五个客户分配给三台车辆的一个方案，其中第一和第三个客户分配给第一辆车；第二和第五个客户分配给第二台车；第四个客户分配给第三台车。

适应度函数定义。适应度函数用于评价遗传算法中每个个体编码的好坏，适应度较高的个体优先遗传到下一代。车辆配送方案的总行驶里程越低，其相应染色体的适应度越高。因此将总行驶里程的倒数作为适应度函数。

生成初始种群。根据车辆数和客户数随机生成N个矩阵C作为初始种群G0={C1,C2,…,CN}，种群中的每个个体必须满足最大行驶距离限制和最大载重量限制，否则将该个体淘汰并随机产生新的个体直到满足限制条件为止。

种群选择与复制。种群中的个体以一定概率进行选择与复制，每个个体的选择概率与其适应度成正比。概率选择机制确保了优秀个体有更大机会遗传到下一代。

交叉操作。种群的选择复制本质上不产生新的个体，即新的车辆分配方案。因此，经种群选择与复制操作后，虽然种群的平均适应度上升了，但其适应度的上限并没有升高。交叉操作以一定概率随机交换种群中两个个体的某些片段，由此产生一些新的个体。交叉操作有利于提升种群适应度上限，从而得到更合理的配送方案。

变异。变异操作随机对个体中的某些基因座的值作变动，即对矩阵C的某些列中1的位置进行变换。遗传算法中，交叉算子具有全局搜索能力，而变异算子具有局部搜索能力，两者相辅相成促进遗传算法得到全局最优解。

终止规则。当两次迭代过程得到的群体适应度上限相差很小或达到迭代次数上限时停止迭代，选择最大适应度对应的分配方案作为最终车辆分配方案。

3.2 基于蚁群算法的车辆路线优化

车辆路线安排问题实质上是一个旅行商问题（TSP），当车辆分配方案确定时，车辆路线优化可用蚁群算法解决[14]。假设车辆所属配送中心的坐标为（0，0），随机生成20个客户。采用的蚁群算法基本参数如表1所示。

蚁群算法是一种进化算法，蚂蚁个数越多，算法搜索的路径越多，得到的解越精确，但是蚁群越大计算复杂度也越大。信息素重要程度体现了已知信息对蚂蚁路径选择的重要程度，该值越大蚁群运动轨迹的随机性也就越弱。启发式因子的重要程度则会影响蚁群寻找路径时的先验性，该值越大蚂蚁越容易选择局部最优路径。信息素蒸发系数对算法收敛速度有很大影响。信息素增加强度系数表示蚂蚁释放信息量的大小，该系数越大算法收敛性越强，同时也更容易陷入局部最优解。

表1 蚁群算法基本参数Tab.1 basic parameters of ant colony algorithm

利用蚁群算法得最短路径为：2-16-9-17-7-1-15-20-10-13-8-14-3-19-12-6-5-11-18-4，最短路径距离为95.0333，路线图以及收敛曲线如图3所示。

图3 基于蚁群算法的路线图及收敛曲线Fig.3 route map and convergence curve based on ant colony algorithm

4 仿真分析

4.1 参数设置

本节以黔东南州烟草公司物流配送为例做仿真分析。该公司共有六个配送站，以东经107度北纬25度为原点，在横坐标[50,250]纵坐标[50,250]的矩形区域内随机产生50个点代表相应客户位置。每个点与最近邻的配送站的距离小于60km。配送中心以及客户位置如图4所示，中小矩形代表配送中心，小圆形代表客户。不同的配送中心以不同颜色区分。模型参数设置如下：每个配送中心的车辆数目为4，每辆车最大载重量dup=8吨，每辆车的最大行驶距离Gup=120km，每个客户的货物需求量在1吨至2吨之间随机生成。

图4 配送中心以及随机产生的客户位置图Fig.4 Distribution center and the random generation of customer location map

4.2 分配客户

分别用最近距离法和边界分配法分配客户，分配结果如图5和图6所示。为清晰地表示分配结果，客户的颜色用分配中心所属的颜色标记。

图5 最近距离法分配客户Fig.5 Nearest distance distribution method

图6 边界分配法Fig.6 Boundary distribution method

对比图5和图6可知，不同的客户分配方法会产生不同的分配结果。最近距离分配法将客户分配给距离最近的配送中心，这种配送方法可能将大量不同方位的客户分配到同一配送中心，而边界分配法倾向于将“成簇”的客户分配到同一配送中心。

4.3 计算最佳配送方案

本文采用遗传算法和蚁群算法对六个配送中心计算其最佳配送方案，限于篇幅仅展示黎平配送中心的配送方案和从江配送中心的配送方案，分别如图6和图7所示。图6中黎平配送中心负责6个客户的货物配送，由两辆车完成，其中一辆车负责西北方向的三个客户，另一辆车负责东南方向的三个客户；图7中从江配送中心负责七个客户的货物配送，同样由两辆车完成，其中一辆车负责西面的4个客户，另外一辆车负责东面的三个客户。

图7 黎平车辆调度路线图Fig.7 Liping vehicle routing map

图8 从江车辆调度路线图Fig.8 Congjiang vehicle routing map

作为对比，本文采用穷举法求解黎平和从江配送中心的配送路线。含有m辆车，n个客户的配送中心，其客户分配方案总共有mn种，每辆车的行驶路线数为k!，其中k为该车辆负责的客户数目。穷取法可以评价所有可能的配送方案从而得到最优解。但当m和n数值较大时，穷举法计算上难以实现。而结合遗传算法及蚁群算法求解黎平和从江配送中心的配送方案，得到与穷举法同样的解（正向与反向的路线配送长度相同，可看作相同方案），但同等计算机配置下耗时仅为穷举法的百分之一。该对比说明结合遗传算法及蚁群算法应用于求解配送方案是一种准确高效的方法。

为研究算法的收敛性与有效性，论文模拟了包含3辆车、12个客户的运输调度问题，结合遗传算法及蚁群算法中随机选取初始种群重复100次实验，在其中85次实验中该算法均得到与穷举法相同的配送方案，即收敛到全局最优解，而在其余15次实验中收敛到局部最优解。这说明遗传算法及蚁群算法的结合有很大概率得到全局最优解，是一种有效的方法。

5 总结与展望

本文采用边界分配法将多分配中心车辆调度问题转化为单分配中心车辆调度问题，并将单分配中心车辆调度问题分解为车辆选择与单车辆路线规划两个互相关联的子问题，分别用遗传算法和蚁群算法求解。问题的转化和分解提高了求解速度，有利于解决大规模跨区域仓储配送问题。客户分配方法对后续的车辆路线规划结果有很大影响，边界分配法相比于最近距离分配法更加合理，然而更有效的客户分配法有待后续研究。

[1]郇青.电子商务物流发展模式研究[D].山东大学, 2012.HUAN Qing.E-commerce logistics development model [D].Shandong University, 2012.

[2]张培林, 魏巧云.物流配送中心选址模型及其启发式算法[J].交通运输工程学报, 2003, 3(02):65-68.ZHANG Peilin, WEI Qiaoyun.Model of logistics distribution center location model and its heuristic algorithm [J].Journal of Traf fi c and Transportation Engineering, 2003, 3 (02): 65-68.

[3]刘云忠, 宣慧玉.车辆路径问题的模型及算法研究综述[J].管理工程学报, 2005, 19(01):124-130.LIU Yunzhong, XUAN Huiyu.Research on model and algorithm of vehicle routing problem [J].Journal of Management Engineering,2005, 19 (01): 124-130.

[4]Bogdanović M.Overview of some solved NP-complete problems in graph theory[J].Advances and Applications in Mathematical Science, 2011, 9(1):35-45.

[5]施朝春, 王旭, 葛显龙.带有时间窗的多配送中心车辆调度问题研究[J].计算机工程与应用, 2009, 45(34):21-24.SHI Zhaochun, WANG Xu, GE Xianlong.Vehicle routing problem with time windows in multiple distribution centers [J].Computer Engineering and Applications, 2009, 45 (34): 21-24.

[6]邢鹏.基于云平台的多配送中心车辆调度问题研究[D].北京交通大学, 2013.XING Peng.Study on vehicle scheduling problem of multi distribution center based on cloud platform [D].Beijing Jiaotong University, 2013.

[7]王征,胡祥培,王旭坪.行驶时间延迟下配送车辆调度的干扰管理模型与算法[J].系统工程理论与实践,2013,33(2):378-387.WANG Zheng, HU Xiangpei, WANG Xuping.Disturbance management model and algorithm for distribution vehicle scheduling with time delay [J].System Engineering Theory and Practice, 2013,33(2):378-387.

[8]马宇红,姚婷婷,张浩庆.基于分区的多配送中心多车型车辆调度问题与遗传算法设计[J].科技导报,2013,(2):61-67.MA Yuhong, YAO Tingting, ZHANG Haoqing.Multi vehicle scheduling problem and genetic algorithm design based on partition of multi distribution centers [J].Technology review, 2013,(2):61-67.

[9]殷脂,叶春明.多配送中心物流配送车辆调度问题的分层算法模型[J].系统管理学报,2014,(4):602-606.YIN Zhi, YE Chunming.Hierarchical algorithm model of logistics distribution vehicle scheduling problem of multi distribution center[J].Journal of Systems Management, 2014,(4):602-606.

[10]孙壮志,鄢烈虎,要学玮.基于线路优化算法的卷烟配送调度系统[J].中国烟草学报,2014,(5):128-133.SUN Zhuangzhi, YAN Liehu, YAO Xuewei.Cigarette distribution scheduling system based on line optimization algorithm[J].Chinese Journal of Tobacco, 2014,(5):128-133.

[11]杨珍花,赖平仲,汤洋等.冷藏车多车型混合配送调度优化[J].系统工程,2015,(10):28-36.Yang Zhenhua, Lai Pingzhong, Tang Yang, et al.Multi vehicle type mixed refrigerated vehicle distribution scheduling optimization [J].System Engineering, 2015,(10):28-36.

[12]Bayley D J, Hart fi eld R J, Burkhalter J E, et al.Design Optimization of a Space Launch Vehicle Using a Genetic Algorithm[J].Journal of Spacecraft & Rockets, 2015, 45(4):733-740.

[13]Gage P J, Kroo I M, Sobieski I P.Variable-complexity genetic algorithm for topological design[J].Aiaa Journal, 2015,33(11):2212-2217.

[14]许争争, 唐加福.基于协作的三阶段启发式算法求解多行程车辆行程问题[J].南开大学学报(自然科学版), 2015,(5):51-59.XU Zhengzheng, TANG Jafu.Three stage heuristic algorithm for solving multi stroke vehicle routing problem [J].Journal of Nankai University (NATURAL SCIENCE EDITION), 2015, (5): 51-59.

Research on intelligent optimization of trans-regional vehicle scheduling among multiple distribution centers

XIAO Zhengzhong1, TAN Jian2*, ZHOU Yufeng1, ZENG Jun1
1 Guizhou Provincial Tobacco Company Qiandongnan Branch, Kaili, Guizhou 556000, China
2 Guizhou University of Finance and Economics, Guiyang 550003, China

Trans-regional vehicle scheduling among multiple distribution centers is a typical NP issue.Boundary distribution method was applied to transform this issue into the issue of vehicle scheduling in single distribution center.An optimal scheduling scheme was then obtained through genetic algorithm combined with ant colony optimization.Simulation analysis was carried out using logistics data of Qiandongnan Tobacco Company in Guizhou province.Results of the analysis proved that the method is valid and ef fi cient.

vehicle scheduling; boundary distribution; genetic algorithm; ant colony optimization

肖正中，谭建，周玉峰，等.跨区域多配送中心车辆调度智能优化研究[J].中国烟草学报，2017, 23（4）

肖正中(1977—)，硕士，经济师，烟草供应链管理，Email：gzxiaozz@163.com

谭 建(1982—)，博士，副教授，烟草供应链管理，Email：tanjian123@126.com

2016-08-23；< class="emphasis_bold">网络出版日期：

日期：2017-03-06

：XIAO Zhengzhong, TAN Jian, ZHOU Yufeng,et al.Research on intelligent optimization of trans-regional vehicle scheduling among multiple distribution centers [J].Acta Tabacaria Sinica, 2017, 23(4)

*Corresponding author.Email：tanjian123@126.com