基于智能调度的散点货源动态集散点设置研究

翟江苏，韩宝睿 ZHAI Jiangsu,HAN Baorui

（南京林业大学 汽车与交通工程学院，江苏 南京 210037）

0 引言

传统的寄件过程，一般是由发件人自行寻找附近的快递网点投递，或者是通过电话预约快递员上门取件。随着货源不断增加，能够发现传统揽件模式的效率会逐渐降低、取件成本也会不断增加。此外，如果过多地设置货物揽收点，会导致企业成本大幅提高，而且对于提升系统运行效率的效果也并不明显。在这种情况下，无人取件车网上预约收件模式能够更好地适应揽收快件工作。近年来，随着无人驾驶技术的逐步成熟，快递智能无人收派车的概念也被提出[1]，城市快件智能化收集也将逐步成为现实。智能取件系统的关键技术在于货物动态集散点的设置以及车辆动态路径的规划。其中动态集散点设置实质上也是路径规划中的一个组成部分。当前车辆路径规划问题研究比较成熟，在调度方法以及模型算法上都取得了一些研究成果[2-5]。然而目前的车辆路径规划研究绝大多数集中在静态路径规划，而对于随机动态需求下的散点货源动态集散点设置以及路径规划研究相对较少，虽然一些论文研究可变线路客流的动态集散点设置方法[6]，但是客流集散点主要是以固定站点为主，且客流的时间约束较大，因而通常客流动态集散点的应用情况不是太多，而货源往往随机性更大，需求的时空分布更加广泛，时间约束相对较低，因此对货流的动态集散点设置往往更加具有实际应用意义。

目前，我国城市的住宅主要以“小区式”为主，城市的快件货源一般呈片区分布。此外，相对于客流而言，虽然快件货源的时间分布更加分散，不像客流有明显的高峰时段，但是其对于时间的约束相对较低，因而对散点货源进行动态集散点设置更加具有现实意义。为了适应散点货源的这些特点以及提升系统收件的效率，对货源动态集散点设置进行模型方法研究，是实现快件智能化收集需要解决的重要问题。

1 系统相关概述

1.1 智能取件系统运行流程

智能调度的快递物件收集是依靠互联网以及无人驾驶技术，根据用户的请求，自动规划取送点以及行驶路线，从而使系统高效、快捷的运行。整个系统运行过程分为：网上预约取件—系统取件时间制定—货件集散点规划—车辆路径规划—车辆取件。具体如图1所示：

图1 智能调度下的系统收件流程

通过该流程，能够看出此流程的核心在于合理地设置取件时间、规划散点货物集散点以及设置一条最优取件路径，从而使取件车辆能够迅速到达取件点。相较于定制公交的网上预约模式，智能取件网上预约的需求随机性更强，客户一般都是在取件当天某个时间进行预约，系统只能完全根据即刻的预约来迅速响应。因此，系统为了能够适应需求的随机性，最大化地满足取件需求，系统需要解决两个关键问题，一方面是要将用户已经预约的需求尽量集中，对于动态及时的需求，系统要能够即时将货物位置更新到已有路径中，及时插入集散点，从而使得系统的取件效率达到最大化；另一方面是要规划一条满足有效的取件路径，使得系统用户能够在规定的时间内最大限度地满足揽件需求以及减少运输成本。其中，将用户的需求集中不仅仅是要在时间段上的集中，还要使得相近需求的取件点位置的集中，这也是本文的研究重点。

1.2 智能取件系统集散点设置过程

客户在网上预约取件申请后，系统会按照不同的取件时间段来将各个取件点进行分类。分类完成后，系统首先会寻找位置特殊的需求点（客户指定的取件点），将其位置作为货源集散点，然后系统继续分析其它客户的请求位置，通过距离判断这些需求点是否满足到周边固定集散点或者特殊位置需求点，如果能够满足，系统会直接将其取件位置设置在固定集散点或特殊位置需求点处。如不满足，系统会根据其它在位置上相近的需求点来设置一个或多个临时集散点。临时集散点能够满足客户的随机性需求，弥补固定集散点的缺陷，然而临时集散点也会存在货物安全性以及造成客户等待问题，因此系统要与客户“协商”好取件时间。

1.3 智能取件车辆运行模式

与可变线路式公交类似，智能取件车也是按照客户要求的一种路线可变的智能车辆，当没有临时集散点的时候，车辆一般会沿着固定站点位置所在的基准路线运行，当有临时动态的集散点出现时，车辆会根据时间限制要求进行合理的偏移。具体运行如图2所示：

图2 动态集散点智能取件车服务模式

2 基于层次聚类分析法的动态集散点的设置研究

2.1 层次聚类分析方法

聚类分析的思想是根据对象差异，把不同类的对象区分开。它的目标是把混杂在一起的数据尽可能的分隔开，使同一类对象的相似程度尽可能大，使不同对象的相似程度尽可能小。层次聚类法[7]是对数据对象进行分解，基于距离或者密度或者连通性分层。其原理是：首先将给定的N个对象分为N类；然后计算两个类距离最小并进行合并；其次重新计算类之间的距离，直至所有的聚类完成，形成一个完整的聚类树。

2.2 动态集散点设置方法

设置货源动态集散点的目的是使收件车辆能够在经过尽可能少的服务点的情况下，覆盖所有的客户需求点，提高整个系统的运行效率，达到近似“点到点”的服务，将客户的自行送货距离限制在一定的范围内，建立的集散点设置模型如下：

上述的模型中，i和j分别为货源系统分配的集散点和客户的需求点，P和S分别表示系统设置的集散点集合和客户预约需求点集合，nij为二进制变量，当nij=1时表示需求点j分配至集散点i，否则j在i未获得服务。dij为需求点j与集散点i之间距离，dmax为客户能够接受的最大送件距离，dmax与客户种类、货物种类等有关。式（1）目标函数表示为系统设置的动态集散点数量最少，式（2）控制客户从需求点到达最终集散站点的距离不超过最大送件距离，式（3）表示每个需求都要在某个集散站点的服务范围内。

由集散点设置模型可以看出，当目标函数越小时，系统设置的集散点数目越小，取件车绕行的路程就越小，系统的效率越高。然而集散点数目越少，客户的送件距离就越大，从而会降低系统服务水平，部分用户会无法获得服务。同样，当系统设置的集散点过多时，整个的收件效率就会下降，因此要找到既能够满足系统效率最大，也要能够满足绝大多数客户的需求。此外，对于一般需求点周围存在位置要求的需求点时，一般的需求点应尽可能先往特殊位置需求点去集散，具体算法流程如图3所示。具体过程如下：

图3 动态集散点设置算法流程

步骤1：根据需求点的坐标划分需求点所在固定集散点范围。

步骤2：寻找有特殊位置要求的需求点，并计算其它需求点到其距离，若满足式（2），则优先将其位置更换成特殊位置点。

步骤3：将在同一固定集散点区间内剩下的每个需求点作为一簇，计算两两需求点之间距离，生成距离矩阵。

步骤4：搜索距离矩阵中的最小值，该值对应的两个簇组成新簇，所有新簇中需求点的中心坐标即为新簇的坐标。

步骤5：计算新簇中每个需求点到簇的距离，若满足约束式（2）则返回步骤3，否则该固定集散点区间内的需求点聚类完成，进入步骤6。

步骤6：重复步骤3至步骤5，直到所有固定集散点区间聚类完成。

步骤7：输出结果，包括动态集散点坐标，集散点需求数量，以及集散点的客户平均送件距离等。

3 仿真算例及分析

考虑到固定集散点设置的成本以及使用效率，本文将仿真区域设置为2 000m*2 000m的矩形区域。因为固定集散点的取件几乎不受时间限制，因此本论文重点仿真某时间段内动态的临时集散点设置。区域内的需求点随机生成。本文按照需求点数量以及最大送件距离不同分别进行仿真。以下是以30个普通需求点，2个特殊位置需求点，最大送件距离取300m进行仿真的过程。

随机生成的需求点如图4所示：

去掉特殊需求点及其周边的一般需求点，剩下了22个一般需求点，如图5所示：

图4 随机生成的需求点图

图5 去掉特殊位置及周边需求点后剩下的需求点图

经过聚类算法形成的聚类树如图6所示：

dmax为300时，由图可知，系统将剩下的22个需求点聚类形成了8个集散点，分别为J1～J9，每个集散点包含的需求点变化如下，J1｛2,3,10,17,21 ｝；J2｛7 ｝；J3｛9,22 ｝；J4｛5,6,1 3｝；J5｛12｝；J6｛1,4,8,11,15,16,18,20｝；J7｛14｝；J8｛19｝；如图7所示：

按照不同的需求点以及送件距离进行仿真结果如表1所示。

4 结束语

通过对不同需求数量以及送件距离进行的仿真试验，聚类分析方法能够将全部的需求点进行合理地集散点设置，充分降低取件点数量，减少车辆绕行，能够实现“公平送件距离”。且当需求点数量越大时，集散效果越明显。此外，当系统突然插入需求点时，仍然可以将新的需求点直接聚集到已有的集散点中，这样既可以客户不断变化送件位置，也可以保证车辆到达取件点的准时性，减少拒绝率。

图6 需求点聚类树图

图7 集散点分布情况图

表1 不同需求量及最大送件距离下的集散点数量