基于Voronoi划分的同城即时配送优化策略研究

2022-11-10徐贤浩沈夏婵任欣欣

运筹与管理 2022年10期

徐贤浩, 沈夏婵, 任欣欣

(华中科技大学管理学院,湖北武汉 430074)

0 引言

随着移动互联网技术更新迭代和新零售业强势崛起，人们对物流服务时间的要求越来越高，2021年中国同城快递业务量超140亿件，较上年增加19亿件，同比增长15.99%，占当年快递业务总量近13%。

即时配送包括距离短、时效性强、地点分散等特点，用户在下单时会附带对商品种类、数量、送达期望时间等要求，平台或商家需及时响应，从用户提出需求至商品送达，整个过程持续时间通常不超过一小时。在实际配送中，如何对众多配送订单进行合理规划及如何对车辆进行合理运力调度从而达到既提高配送服务质量，同时又能控制配送总成本已成为当前重要问题。

近年来越来越多的学者在研究即时配送车辆路径问题会引入时间窗、道路交通状况等实际因素。在对车辆路径问题的数学模型研究上，陈萍等[1]建立了基于餐饮O2O配送的取送货车辆路径优化模型；王帅等[2]研究了O2O平台上食品提供商的车辆路径问题；王征等[3]建立了基于即时响应状态下的配送订单数学问题模型；柴获等[4]设计了多重图求解运输网络的带时间窗车辆路径问题；慕静等[5]将众包配送运力调度模型中的目标函数改变为配送人员收益激励最大化；Huang et al.[6]研究了众包配送交付中最后一公里问题；李桃迎等[7]引入了时间惩罚成本和K-means聚类算法来解决同时取送货的VRP问题。

除此之外，还有许多研究聚焦在对求解算法的改进上，孙小军[8]设计了单亲遗传-布谷鸟搜索混合算法求解带时间窗的配送问题。胡俊桥[9]使用遗传-蚁群混合算法求解车辆路径问题。孙小军等[10]设计了一种基于交通拥堵和挥发因子两个变量的改进蚁群算法。Abidi et al.[11]使用改进遗传算法解决具有不确定性的RVRP问题。Kumar et al.[12]提出了基于Dijkstra的fast-clusiVAT算法。Ticha et al.[13]设计了一种基于多图模型的自适应大邻域搜索启发式方法。Lu et al.[14]使用分支定价切分算法研究具有不确定性需求的带有时间窗的VRP问题。

上述研究为本文奠定了基础，但仍然有进一步研究的空间，具体体现如下：

第一，针对大规模即时配送的车辆路径优化问题仍有大量研究空间。在数据规模较大的条件下，现有数学模型无法较好解决，例如存在多门店、多客户的“多对多”的情况。

第二，针对大规模车辆路径问题求解使用的启发式算法的路径选择策略仍需不断改进。当前求解VRP问题所采用的单一或混合启发式算法仅考虑了配送路径长短对路径选择的影响，且均使用欧式距离即直线距离代表配送路径的长度，与现实情况存在一定偏差，而在当下“分钟级”配送中，两地点的实际距离(由于电动车体积较小，本文使用步行路线近似代替电动车行驶路线)与欧式距离的差值对路径选择和车辆行驶时间的影响较大。

1 模型构建

1.1 带时间窗的车辆路径问题模型建立

1.1.1 问题描述与模型假设

同城即时配送作为新颖的第三方配送方式不具备配送中心，呈现出送货点多分散和面广的特点，且客户有严格的时间窗要求，配送车辆完成后无需返回。模型基本假设为：

(1)整个配送网络存在多配送中心，即为平台商户；

(2)所有配送任务均由多个同型号车辆完成；

(3)配送车辆从当前位置出发，先取完所有商品后再开始配送，所有商品送货完成才可视为当前车辆全部配送任务完成，此时车辆无需返回初始位置；

(4)客户均有假定的配送服务需求时间窗；

(5)单个客户需求有且仅由单台车辆满足；

(6)本假设条件下配送商品的特点是体积小且不规则、车载容量灵活不固定等，因此暂不考虑配送配送车辆的商品数量约束；

(7)假定配送车辆均为小型电动车，实际续航里程较短，因此需考虑配送车辆的最大里程限制；

(8)不考虑配送车辆到达客户需求点的服务时间，即配送车辆到达客户点便视为完成当前客户的配送任务；

(9)假定配送车辆全程匀速行驶，暂不考虑交通状况变化、天气或其他突发状况等现实情况的影响。

1.1.2 模型建立

(1)符号说明

根据上述九个基本假设，本数学模型的各个参数、决策变量及函数定义如下：

①参数：

②决策变量：

(1)

(2)

③函数：

在实际的即时配送中，若配送商品晚于客户要求时间送达便会极大影响客户满意度，最终会对企业造成一定损失。为简化问题，假定时间惩罚成本随时间呈线性变化，函数表达式如下:

(3)

(2)数学模型

通过上述描述与假设，建立带用户需求软时间窗的车辆路径问题数学模型，并将配送产生的总成本最小为目标函数，具体如下:

(4)

(12)

对上述建立的数学模型中各表达式说明如下：

表达式(4)表示以配送产生的总成本最小为目标函数，分别由车辆行驶成本、车辆固定成本、车辆取货等待成本及车辆延误的时间惩罚成本四项组成。

表达式(5)、(6)、(7)表示单个用户的单个商品取送货仅由一台配送车辆完成；

表达式(8)表示单个车辆完成其全部配送任务的总耗时，分别由取货等待时间、行驶时间两部分组成；

表达式(9)表示单个车辆总行驶里程不得超过车辆最大行驶里程约束；

表达式(10)表示客户理论等待时间须早于其能接受的最晚送达时间，否则因此产生的超时惩罚成本为无穷大；

表达式(12)表示各个参数、变量均大于零；

表达式(11)表示整数化约束，即xijk,yjk只能取0或1。

1.2 配送区域划分研究

此前研究大规模车辆路径问题时，考虑的是整个配送网络中只存在单一门店的情况，此时只有客户间的相对距离会影响配送区域划分的结果。而配送网络中存在多个门店时，门店距客户的距离同样也会影响配送区域划分。将整个配送区域按照门店、车辆及客户等地理位置数据划分为若干个独立子区域，各个独立子区域分别寻找自己的最优路径，以此缩小优化搜索范围，提高算法求解效率。

本研究使用Voronoi划分方法处理众多客户因地理位置不同而产生的分类问题，其主要思想是为多个门店点划分独立子区域，使其区域中的点只受离其最近的核心点影响。本研究中，多个客户需求点中穿插分布着门店位置点，由车辆、客户及门店组成的点均位于同一平面上，门店位置即是该平面上多个不重合节点，这些门店点将配送网络分成了多个独立子区域，每个独立子区域内包含的客户点离该区域的门店点最近就由该门店负责配送。Voronoi算法具体实现如下：

(1)每个门店节点两两相连形成若干三角形；

(2)找出所有三角形外接圆圆心；

(3)遍历三角形链表，寻找与三角形pT三边共边的相邻三角形A、B、C；

(4)如果找到A、B和C，则连接其外心与pT外心，存入Voronoi边链表中，否则寻找最外边中垂线，也存入Voronoi边链表中；

(5)遍历结束，画出Voronoi图。

Voronoi划分图形成过程如图1所示，本文选择调用Python中的Voronoi函数。

图1 Voronoi划分示意图

1.3 基础蚁群算法的概述与改进

1.3.1 基础蚁群算法的概述

蚁群算法(Ant Colony Algorithm, ACA)诞生于1992年，算法模拟了蚁群协作觅食的过程，蚂蚁较大概率会选择信息素浓度高的路径，并且路径上的信息素浓度会随时间推移而逐渐降低，最终蚂蚁能够找到一条距离食物的最佳路径，即距离最短路径。

(13)

其中，allowk为蚂蚁k待访问城市集合，α和β分别为信息素浓度和启发函数的权重。

τij(t+1)=(1-ρ),τij(t)+Δτij(t)

(14)

(15)

(16)

其中，ρ为信息素挥发系数，Q为常数，Lk为蚂蚁k所走的路径长度。

1.3.2 蚁群算法的三步改进

(1)状态转移概率公式的优化

传统蚁群算法是使用状态转移概率公式计算出下一时刻待访的最短路径，即只考虑了距离长短因素对路径选择的影响。本文在此基础上还考虑了超时惩罚成本，即添加时间窗因素到状态转移概率公式中，客户期望商品送达时间窗为[0,tij]，tij越小表示客户对商品送达的时间要求越严格，即优先配送tij较小的客户。时间窗因素φij表达式为:

(17)

加入时间窗因素φij后，改进蚁群算法的状态转移概率计算公式如下:

(18)

(2)使用实际距离替代欧式距离

以往启发式算法求解车辆路径问题多使用欧氏距离度量两点距离，但现实道路往往是不规则的曲线，因此欧式距离并不能反映车辆实际行驶距离，所求得的解也存在较大误差。文中改进蚁群算法所使用的实际距离是由百度地图开发平台JavaScript API v2.0求得。随机选择一组点(114.414694,30.51839)和(114.416259,30.521761)的经纬度来说明欧式距离与实际距离的差别，计算得到两点之间欧式距离为404米，实际距离为570米，差值为166米。

(3)改进路径选择

为保证蚂蚁在选择下一步路径时具有一定随机性，即算法有一定概率选择信息素剩余量少的路径，此种做法在一定程度避免了局部最优解。

本文改进的蚁群算法将轮盘赌加入路径选择。将每条路径的选择概率看作轮盘扇面之一，指针停止时所在的扇面就选择对应概率的路径，通过添加0-1之间的随机数模拟指针停止时指向的扇面，以此增加蚂蚁在选择路径时的多样性。根据上述描述，本文改进的蚁群算法求解步骤如下：

Step1iter→1(iter为迭代次数)，将各参数初始化。

Step2构建解空间将m只蚂蚁随机置于不同起点，对每只蚂蚁按照公式(18)使用轮盘赌方法计算其下一个待访问城市，直到所有蚂蚁将所有城市访问完成。

Step3计算每只蚂蚁所走的路径长度Lk，记录当前迭代次数的最优解，同时根据公式(14)～(16)对各城市连接路径上的信息素浓度进行更新。

Step4判断是否终止，若iter

2 算例验证及结果分析

2.1 背景描述

假设有如下场景：较短时间内，门店收到了平台一百个不同客户的商品配送需求，平台有十台配送车辆位于该配送区域中。门店将任务分别分配给配送车辆，车辆在收到任务后先到门店取货，门店优先为先到达、客户多的车辆准备商品，车辆将需求商品全部取完后开始配送。

本文使用百度地图选取了一百二十个实际地点，其中包括十台配送车辆、十个门店及一百个客户需求点。首先使用通过百度地图开发者平台提供的API接口获取上述一百二十个真实地点的经纬度数据，并对客户点进行Voronoi划分，将一百个客户分配给多个子配送区域；其次对划分出的子配送区域，在已有各地址经纬度数据的基础上，计算各地点间的实际距离；最后进行基础蚁群算法和改进蚁群算法算例对比实验。各点地理位置如图2所示，其中蓝点代表客户所在点，红点代表配送车辆所在点，白点代表门店所在点。

图2 各点地理位置分布图

为方便计算，假设配送车辆以V=300m/min匀速行驶，车辆最大里程约束L=50000m，门店出货时间ti=0.1min/个，单台车辆固定成本c1=5/台，单位距离成本c2=0.001/m，单位时间占用成本c3=3/min，超时惩罚成本为λm=6/min、λn=3/min。从一百个客户中随机选择七十个为普通客户，理论等待时间窗为[0,20]，其余三十个为期望配送时间较短客户，理论等待时间窗为[0,10]，所有客户能接受的最晚配送时间均为60min。

实验仿真环境为操作系统Windows 10，处理器lntel(R)Core(TM) i5-7200U CPU @2.50GHz 2.71 GHz，使用MATLAB R2012a软件实施编程，蚁群算法各参数设置如表1所示。

表1 蚁群算法的参数设置

2.2 数据收集

使用百度地图开发者平台处理包括门店、配送车辆、客户在内共一百二十个地点数据后，得到经纬度数据，并对门店、配送车辆及客户进行单独编号。

2.3 算例分析

以十个门店为核心点，Voronoi划分结果如表2所示：

表2 Voronoi划分结果

绘制Voronoi划分效果图如图3所示，蓝色点代表门店点，红色×代表客户点。

图3 Voronoi划分效果图

使用基础蚁群算法的求解结果如表3、4所示。

表3 基础蚁群算法求解车辆路径表

表4 基础蚁群算法求解成本表

使用上述经改进后的蚁群算法求解结果如表5、6所示。

表5 改进蚁群算法求解车辆路径表

表6 改进蚁群算法求解成本表

对比表4、6可以看出：(1)时间占用成本相同，原因是门店及客户位置不变的情况下，Voronoi划分结果是相同的，因此改进蚁群算法不能减少占用时间和时间占用成本；(2)改进蚁群算法相较基础蚁群算法而言，六号配送车辆产生的超时惩罚成本占总超时惩罚成本的比例较大，分别为76%、92%，原因是六号配送车辆离门店距离最远。

两种路径规划方案的行驶距离、各项时间以及各项成本如表7、8。

表7 两种路径规划方案的行驶距离以及时间表

表8 改进蚁群算法求解的成本表

对比表7和表8可以看出：(1)改进蚁群算法求解的总超时时间(11分钟)比基础蚁群算法的总超时时间(17.1分钟)低36%；改进蚁群算法求解的超时惩罚成本比基础蚁群算法低17%，是导致其总成本比基础蚁群算法低17%的重要原因，说明使用改进蚁群算法在降低总成本上更具优势。(2)改进蚁群算法求解的车辆行驶总距离(35460米)比基础蚁群算法的车辆行驶总距离(31410米)高13%，改进蚁群算法求解的每辆车平均耗时(11.96分钟)比基础蚁群算法的每辆车平均耗时(10.6分钟)长13%，原因是改进蚁群算法的状态转移概率公式中加入了时间窗这一因素，使路径寻优搜索时需同时考虑客户需求时间和行驶距离长短，这会牺牲了期望时间较长的用户时间。