基于服务区域划分优化的配送路径规划问题研究

张 睿（无锡职业技术学院，江苏 无锡 214073）

0 引 言

流通领域中，许多物流配送企业借助外部经济的发展，实现了规模扩张与快速发展，但对如何控制成本，提高运营效率的迫切性并不强。现在随着经营环境的变化，物流需求量更大，客户、网络更复杂，对服务的要求更多样化。但面临的竞争更加激烈，不管是从事跨区域配送还是城市配送，首先需要考虑顾客服务水平，赢得客户的认可，然后考虑配送运营的成本问题，因而如何创新物流服务，提高运营效率和控制日常运营成本成为每个配送企业需要时刻思考的问题。

传统的基于经验的方法，在企业规模有限，客户数量不是非常多，配送网络相对简单的情况下，只要员工和管理者技能过关，执行力好，都应该能够较好地完成配送任务，获得企业的发展。但是随着销售区域扩大，客户数量的不断增加，客户需求持续增长，配送业务量大增，配送周期缩短，配送线路更复杂，并且需求的随机性、变动性加大，光凭经验和手工安排，已无法做到配送计划的优化，必须借助于统计分析、利用数学模型和智能算法，才能获得较好的配送计划，节省时间，提高效率。本文就是针对这些问题，从企业应用的角度，提出先合理划分配送区域，再优化配送路线的方法，从而达到降低成本，提高竞争力的目标。

1 论文总体思路综述

排单和车辆调度是整个配送计划和作业实施的核心，是配送任务和客户服务按时完成的有力保证。

传统的订单排单和车辆调度、路线安排都是由公司里业务能手来完成，送货区域大了，客户多了，这项工作的效率和完成工作的成本控制都会不理想，现在常用的智能优化方法，把它作为一个典型的VSP问题，建立数学模型，利用智能化的算法，求解可行的配送路径规划，作为理论研究，这样的做法是有意义的。但是有两个问题：（1）这个模型数据的收集整理工作量特别大，计算过程也较长，因而成本不会低。（2）模型本身一定要适合实际的作业过程，这就需要有一个不断测试和优化的过程，并且还要适应每天的动态变化，否则反而会影响到日常的作业过程。许多研究理论完备、精深，但是在适应产业化运营时，工程上的可实现性还有待提高和完善。因而影响了这些很有价值的研究在企业实际中的运用。

本文的研究并不针对配送路径规划做理论上的深究，而是立足实际应用，在可接受的范围内，利用较简易实用的智能优化方法，在较短的时间内，以较低的成本获得相对优化的配送路径规划方案。不求最佳，但求有效。为今后电子排单和送货线路优化软件的开发和应用作必要的铺垫。

具体设想：第一步，利用聚类分析法对配送区域进行合理分区，先把复杂问题简单化。第二步，每个分区内就是个典型的TSP问题，有很成熟的解决办法。在平衡好各分区工作时间安排后，就能很快获得较理想的配送方案。

重点是第一步，分区时一定要考虑到客户位置、需求量、车辆载重、作业时间均衡限制等因素，需要花费好多功夫。

2 配送区域动态优化及其方法

2.1 配送区域的初始划分方法。配送区域优化方法对最终优化的结果有很大的影响，因而合理的划分方法的选择十分重要，目前常用的划分方法有扫描法和聚类算法，在配送客户有限、区域较小时运用扫描法就可以了，但是当客户数量很多，区域较大，又要考虑约束条件时，聚类算法就是我们必然的选择了，聚类算法中K-means比较成熟，操作简单，原理是：把大量d维（二维）数据对象n个聚集成k个聚类（k＜n），使同一聚类内的对象相似性最大，不同聚类内的对象相似性尽量的小。利用聚类算法分区可以使配送区域的划分比较紧密并且实用。

在运用聚类分析法时有几个问题要注意：第一，k的选择，以一天送货总量/单车载重量，也可以放宽一些，到：一天送货总量/单车载重量+1。第二，k个聚类内的密度，分区密度大，效率高，成本低。第三，每个分区内工作时间大体相当，这样便于运行的稳定，进行成本控制和人员、车辆的考核。第四，每个聚类间不重合。做到这样分区效果会比较好。

传统的K-means聚类法，k个聚类区内，初始点是随机产生的，运行时间长，收敛效果差。基于均衡化考虑，在配送对象分布不均匀时，用密度法效果较好，初始中心点以密度来定义，运用两点间欧氏距离方法，求解所有对象间的相互距离，并求平均数，用mean（D）表示，确定领域半径n是对象数目，coefR是半径调节系数，0＜coefR＜1，经验表明，coefR=0.13时，效果最好。如果使用平均欧氏距离还不理想，可增加距离长度，甚至用最大距离选择法，收敛速度比较快。

在配送对象分布较均匀时，可考虑用网格法，效果较好，整个配送区域划分用k=Q/q，k为初始点个数，假设k=mn，将地图划分成m行n列，以每格中心点为初始点，通过网格内的反复聚类运算，达到收敛，获得网格稳定的聚类中心。

2.2 分区内配送工作量的均衡。这样就完成了配送区域的初步划分，但是没有考虑各个分区内工作量的均衡问题，如果工作量不均衡，对于客户服务水平的保证，成本的控制，作业的安排，人员、车辆的考核都存在问题。

在实际的物流企业配送作业过程中，一般一辆车一天也就送货10多家或20来家，多余的时间要用于收款，与公司财务部门交账，核算出车相关费用，所以不考虑同一车同一天出车多次的情况，多次出车待以后深入探讨。那么就意味着每个分区就是一辆车一条线路，把问题大大简化了，需要说明的是：这种方法对于配送规模不是特别大的单个城市配送是适用的，也具有广泛性。

各分区内的每日配送工作量是以配送作业耗用时间来衡量的，耗用时间有两部分构成：（1）车辆行驶时间；（2）客户服务时间。由于配送分区有限，每个分区内的客户数量不是很多，可以采用实地测时的方式，把每条线路的配送时间统计出来，这是一种手工办法，但比较符合实际，各线路时间分别为T1,T2,T3,T4,…,Tk，从中选出最大值Tmax，最小值Tmin，用经验法确定允许的差值，然后来调整超过差值的分区内的客户，从而使得各区作业时间基本均衡。

如果客户数量众多，分区也较复杂，就需要借助统计学方法，通过对样本线路车辆行驶时间以及服务时间，拟合出分区作业时间函数，然后，计算出所有线路作业时间，即使分区重新调整，线路重新组合，仍可以很快计算出线路作业时间。本文不在这个方面进行深入探讨。

2.3 重新组合客户，确定最终区域划分。观察各线路作业时间超过允许差值的部分，由大到小来调整，将离聚类中心最远的数据点弹出，使本区T值下降，直至在差值以内，将弹出点加入到临近的不足均衡作业时间的分区内，如果临近分区作业时间超过允许差值，这个点就不能弹出，只能弹出另外的次远数据点，以此类推，任何一个数据点只能弹出一次，直到所有数据点和分区调整完毕。

这样最终确定的分区，既能做到区域划分紧密，效率、成本更低，又能做到各区作业时间均衡，便于工作指派，车辆、人员核算。

以上是本文的第一部分工作，也是最有意义的工作，确定好合理的区域划分，不仅是配送作业合理化的重要步骤，也是业务人员访销工作和客户服务的重要依据。

3 基于改进蚁群算法的分区线路优化方法

分区内线路安排，就是一辆送货车由DC出发，依次经过分区内每一个客户点，完成送货后返回DC，求出近似最优的行车顺序，这是个典型的旅行商问题（Traveling Salesman Problem，TSP），TSP是NP完全问题，解法很多，有精确算法，也有启发式算法，目前许多智能算法就属于启发式算法，可以解决较复杂的线路优化问题，对于一般线路优化也能做得更准确，这里介绍蚁群算法解决实际问题。原因是蚁群算法与其他启发式算法相比，在求解性能上，具有较强的鲁棒性和搜索较好解的能力，是一种分布式的并行算法，一种正反馈算法，易于与其它方法结合。克服基本算法缺点，改善算法性能。

3.1 蚁群算法简介。蚁群算法（Ant Colony Algorithm,ACA）是由意大利学者M.Dorigo等人于20世纪90年代初提出的一种新的模拟进化算法，其真实地模拟了自然界蚂蚁群体的觅食行为。M.Dorigo等人将其用于解决旅行商问题TSP，并取得了较好的实验结果。

蚁群算法用于解决优化问题的基本思路是：用蚂蚁的行走路径表示待优化问题的可行解，整个蚂蚁群体的所有路径构成待优化问题的解空间。路径较短的蚂蚁释放的信息素数量较多，随时间推移，较短路径上积累的信息素浓度逐步增高，选择该路线的蚂蚁数量也越来越多，最终整个蚂蚁会在正反馈的作用下集中到最佳线路上，这个路线就是最有解。

3.2 用蚁群算法解决分区线路优化问题。以下用数学语言描述蚁群算法的整个过程：设蚂蚁数量为m，分区内客户数量为n，m≤n，客户点i与客户点j之间距离用dij（i,j=1,2,3,…,n）表示，t时刻i与j连接路径上的信息素浓度为τij（t）。初始时刻各路径上的信息素浓度相同。

位于客户点i的第k只蚂蚁选择客户点j的概率为：

其中：

τ（i,j）表示边（i,j）上的信息素浓度；

η（i,j）是启发信息，d是客户点i和j之间的距离；α和β反映了信息素与启发信息的相对重要性；

tabuk表示蚂蚁k已经访问过的城市列表。

当所有蚂蚁完成周游后，按以下公式进行信息素更新。

其中：ρ为小于1的常数，表示信息的持久性。

其中：Q为常数；lk表示第k只蚂蚁在本次迭代中走过的路径，Lk为路径长度。

蚁群算法解决TSP问题具体步骤：（1）基本参数设置：包括蚂蚁数m，信息素重要程度因子0≤α≤5，启发函数重要因子1≤β≤5，信息素消逝参数0.1≤ρ≤0.99，信息素释放总量10≤Q≤10 000，最大迭代次数iter_max，迭代次数初值iter=1。用试验方法确定α、β、ρ、Q值，以获得较优的组合，有助于改进基本蚁群算法，提高整体优化效果，并缩短运算时间。（2）初始解的求解：利用最近邻算法，以缩短算法运算时间，并以此算法产生初始解的路径长度作为产生初始信息素的基础。（3）构建解空间：将各个蚂蚁随机地置于不同出发点，对每个蚂蚁，按公式（1）计算其下一个待访问的网点，直到所有蚂蚁访问完区域内所有网点。（4）更新信息素：计算各个蚂蚁经过的路径长度Lk（k=1,2,…,m），记录当前迭代次数中的最优解。同时，根据（2）式和（3）式对各个网点连接路径上的信息素浓度进行更新。（5）判断是否终止：若iter＜iter_max，则令iter=iter+1，清空蚂蚁经过路径的记录表，并返回步骤2，否则终止计算，输出最优解。

蚁群算法如结合其他启发式算法，建立混合算法，能够解决许多现实问题，达到较好运算效果，结合具体问题，可以深入研究。

4 本文的局限与进一步研究的方向

本文的研究更多地从实际运用和操作的便利角度出发，因而力求方法简便，运算效率较高，然而实际问题远比设想复杂，物流系统的优化应该是整体性的优化。本文只是做了配送区域的合理划分，在此基础上，对区域内配送路径进行优化，只是送货过程的优化，完整的过程还包括客户服务水平，合理的库存水平，以及配送中心选址，服务地点（卸货点）的设置等，只有这些因素都考虑到了，才能真正实现配送系统的优化。另外，还有静态分析和动态分析的区别，大区域划分保持相对静态，区域间根据每日具体的业务需求做必要的动态调整，这部分可借助人工安排，也可参考软件，保持一定的灵活性。整个配送系统的研究千头万绪，在进一步的研究中，首先需要把销售系统的优化结合进来，客户前端的需求和库存决定着后面的订单以及配送，业务员对零售网点的访销，一方面对接客户服务，体现公司的客户服务水平，另一方面，对接订单的处理以及最终的配送工作，业务人员访销作业的系统性安排，以及客户、配送中心信息的一体化都有赖于业务访销与配送作业的综合优化。

因而，配送区域合理划分、送货线路优化以至于整个物流系统，销售系统、供应系统的不断优化，对于物流企业、社会物流以及整个经济运行系统是非常有意义的，对于众多转型中，缺乏专业知识和技术的中小物流企业，有着普遍意义，值得重视。

[1] 陈子侠,等.杭烟物流与送货路线优化[J].物流技术，2003(8):38-40.

[2] 王勇，池吉.物流配送路线及配送时间的优化分析[J].重庆交通大学学报，2008(4):647-650.

[3] 杨弋，顾幸生.物流车辆优化调度的综述[J].东南大学学报，2003（增刊）:105-111.

[4] 陈文，郑少锋.基于蚁群算法的配送路径规划研究[J].物流科技，2013(7):45-47.