一种新的同时取送货车辆路径问题方法研究

刘玲　栗雅清　王蕴默

摘 要：随着国家的富强，社会经济实力的持续增长，我国人民群众的日常生活水平也越来越高，所以人们的网购热情也随之提高。由此以来，随着人们网购的种类和数量不断增多，网购时的取货和送货问题也浮出水面，成为了一种被广大学者重点研究的问题。本文针对同时取送货车路径的问题，基于用户画像相关方法建立了双目标模型，随后设计了蚁群算法对静态和动态问题进行相关解析，实验结果可得，该方法在具体问题中的求解速度以及对外界环境不良因素的抗干扰能力较强，为以后的相关研究奠定了理论基础。

关键词：同时取送货 车辆路径 双目标 蚁群算法

1 引言

同时送货的时效性、客户的满意程度以及各种具有不确定因素的相关问题正随着国家及社会高速发展慢慢的浮出水面[1]。而如今，随着计算机以及相关技术的快速普及，国家为了应对各场景下精确满足客户需求，完善相关配送规范和配送能力。

末端配送的主要問题是VRPSPD问题，以配送网络为应用场景，结合用户画像理论对取送货问题进行研究，具有现实意义。当前结合用户画像对同时取送货问题研究的文献相对较少，研究具有高复杂度的NP-hard问题，具有重要学术价值[2-3]，研究成果应用于各个领域，车辆路径问题的求解方法框架及技术路线示意如图1-2

所示。

2 末端配送概念的相关概述

我国末端配送以不同的配送需求主体与配送客体划分，可以将配送服务分为三大类，分别是B2B、B2C、C2C。

3 用户画像流程及方法

构架逻辑，其中用户平时在配送服务中的行为数据如：评论参与情况，平台浏览量，进行用户画像。

4 取送货需求用户画像体系构建

取送货用户画像标签体系，其中标签获取及处理步骤如下：

（1）标签获取，根据相关问卷调查，获得了150份相关数据资料。对最底层事实标签数据进行定量处理和归一化处理，即可进行下一步数据的收集和分析。

（2）对问卷数据的处理步骤共有三步：

①分析各个标签，构建指标评价矩阵Xij。

②归一化处理，消除不同量纲之间的影响得到X'ij。归一化式子[4]如（1）所示，其中Z'是标准化后的数值，Z表示初始值，Zmin该指标极小值，Zmax该指标的最大值：

（1）

③熵值法求解高级标签下各个指标的影响权重。

5 双目标蚁群算法要点及流程

蚁群算法是受自然界蚂蚁群体的觅食行为启发而发展起来的进化算法，蚁群算法最初被应用于旅行商问题（travelling salesman problem，TSP），取得了很好的实验结果。近年来蚁群优化（antcolony optimization， ACO）方法被广泛应用于车辆路径问题。

本文提出的基于用户画像的同时取送货模型为路径最小和客户满意度惩罚最小的双目标模型，并不存在绝对最优解。双目标蚁群算法[5]流程结合用户基本数据及用户画像得到的四组客户进行仿真验证，蚁群算法参数设置如表1所示。列出基于时空聚类的区域划分客户点的数据。对每一个区域内的客户进行求解，分析每一区域非劣解偏向不同目标函数的解及是否采用时空距离对配送区域进行划分，可以得出如下结论：

（1）对比有画像下有无聚类的求解结果，可见有画像有聚类的计算效率约为有画像无聚类的两倍。（2）对比有画像有聚类是区域分别求解还是一起求解的结果可见，一起求解的无惩罚客户占比要高于分别求解。（3）对比无聚类下是否画像对结果影响，无聚类下有画像的结果求解时间明显缩短。（4）对比有聚类下有无用户画像对结果的影响。

6 结语

本文在用户画像及配送区域划分的基础上，进行路径优化。建立VRPSPD基本模型，提出基于用户画像的VRPSPD双目标问题， 模型考虑车辆容量和最大行驶距离限制的同时， 构建了最小化总行驶距离和最小化不同车辆行驶距离最大差以平衡各车辆的工作负荷的双目标模型，并且考虑了需求点客户用户价值和用户时间敏感度对时间窗下满意度惩罚的影响。最后通过算例验证了算法的有效性，从是否双目标、有无聚类等角度，对比分析算法优化效果，为以后的实际应用提供了夯实的理论研究基础。

参考文献：

[1]孔源.基于海量浮动车数据和社交网络兴趣点的时空轨迹挖掘[D].北京：清华大学，2017.

[2]Li J，Pardalos P M，Sun H.adaptive neighborhood selection approach for the multi-depot vehicle routing problem with simultaneous deliveries and pickups[J].Iterated local search embedded Expert systems with applications an international journal，2015，42（7）：3551-3561.

[3]Wang J，Ying z，Wang w.Multiobjective vehicle routing problems with simultaneous delivery and pickup and time windows：formulation，instances and algorithms[J]. IEEE Transactions on Cy bernetics，2016，46（3）：582-594.

[4]Branke J，Middendorf M，Noeth G.Waiting strategies for dynamic vehicle routing[J].Transportation science，2005，39（3）：298-312.

[5]Reed M，Yiannakou A，Evering R. An ant colony algorithm for the multi-compartment vehicle routing problem[J].Applied Soft Computing，2014，15：169-176.