众包车辆路径问题

万勇平 （江西财经大学，江西 南昌 330013）

WAN Yongping (Jiangxi University of Finance and Economics,Nanchang 330013,China)

0 引 言

物流“最后一公里”问题促使许多公司寻找创新性的解决方案，以此来降低总体配送成本。零售巨头沃尔玛计划通过商场购物的顾客顺路配送在线购物的包裹，这样就不需要专门的配送公司或者车辆进行包裹配送，通过这种方式来达到降低配送成本的目的[1]。沃尔玛于2017年开始该计划的小规模试点，尝试让员工在下班途中兼职快递员，为客户投送包裹。同样为了提升配送效率，亚马逊英国在2016年开始测试使用无人机进行终端配送，预计30分钟才能完成的第一次配送测试任务仅仅用了13分钟。无人机配送也可以看作是一种物流众包，与有人驾驶的车辆一样，会产生配送成本问题，都要考虑如何优化配送路径，降低配送成本。因此，研究VRPOD问题有着重要的经济意义，有助于降低物流终端配送成本，提高配送效率。

1 问题描述及算法介绍

1.1 问题描述

车辆路线问题（Vehicle Routing Problem,VRP）由Dantzig和Ramser[2]在1959年首次提出，它是指一定数量的客户，各自有不同数量的货物需求，配送中心向客户提供货物，由一个车队负责分送货物，组织适当的行车路线，目标是使得客户的需求得到满足，并能在一定的约束条件（如配送供需、配送时间、车辆负载、车辆行驶里程等）下，达到如路程最短、成本最小、耗费时间最少等规划目标。由于VRP具有广泛的现实运用和巨大的经济价值，VRP问题自1959年被提出以来，该问题一直是网络优化问题中最基本的问题之一，受到国内外学者的长期关注。

众包车辆路径问题（The Vehicle Routing Problem with Occasional Drivers,VRPOD）是VRP的一个变种问题，在基本VRP问题基础上引入了众包的概念。在众包模式下物流配送公司不仅自身拥有运输车辆进行配送，同时以一定报酬为前提，将一部分的包裹众包给有配送愿意的顺路的司机，相比于传统的配送模式这种模式的好处在于自身需要维持的运输车辆更少，这样能降低固定资产的比例。同时由于招募的司机更少，人员成本更低。物流配送公司需要考虑的是，如何安排自有车辆和众包车辆的配送路线以降低总的配送成本。

本文假设存在一个配送中心，中心自身维持一定数量的配送车辆，向顾客点配送包裹。自有运输车队配送能力不够，需要将一部分包裹外包，私人车主顺路接受配送请求并完成配送任务以获得报酬。为了将问题简化，我们并没有考虑所有的符合现实中的条件，例如本文限制每位司机每次只能服务一个客户点，实际上众包司机可以服务多个客户点。但是，这并不妨碍我们从经济的角度考察众包模式对于物流配送带来的效益。

1.2 算法介绍

为了验证模型是可行的，使用扫描法求解VRPOD问题并将其与在VRP问题下的解进行比较。扫描法是一种传统的启发式求解算法，扫描法最早由Gillett和Miller提出。基本思想是：以配送中心为原点建立极坐标表示各客户点的位置。给每个客户点编号，客户点的角度越大编号越大。从配送点沿着任意方向画一条直线，按照顺时针或者逆时针方向，把客户点按从小到大的顺序排入车辆配送路线中，路线安排要满足车辆负载的约束条件，当约束条件达到上限时返回配送中心，形成一条配送路线。重复以上步骤，继续向下扫描，直到所有客户点都被安排到一个分组当中，此时操作结束。

2 建立数学模型

VRPOD的基本变量定义如下所示：G=N,（）A 表示完全有向图，N是图上各点的集合，A是图上各条边的集合；点集合N由两部分构成：配送中心0，客户点集合C；车辆集合V包含两部分：自有车辆集合S，每辆车的最大载荷为Q，配送到成本为c；雇佣车辆集合K，为了将问题简化，假定雇佣车辆配额获得的报酬与其目的地无关，只与配送中心到客户点的距离doi有关，并且对于同一个配送点，所有司机获得的报酬是一样的。这种做法符合实际情况，因为，雇佣车辆的公司并不会关心雇佣车辆的目的地。实际上，司机接受配送的意愿受配送点到目的地的距离的影响，越近意愿会越高，但是这种情况下，问题将更加复杂。作为对雇佣司机车的补偿，提高配送意愿，司机获得的报酬p=ξc0k，同时ξ＞1。假设众包配送成本与车辆初始位置无关，只与配送点到目的地的距离有关，且车辆负载满足单个客户点的需求。建立如下所示的线性规划模型：

上述模型中：式（1）为目标函数，xij为二进制变量（0或者1），表示自有车辆是否访问边（i,j）；cij表示自有车辆访问边（i,j）时付出的成本；pik表示众包车辆k访问客户i所得的报酬；wik是一个二进制变量，表示众包车辆k是否访问客户点i。式（2）和式（3）为流约束，表示同一个客户点只能被访问一次。si表示客户点i被自有车辆访问过，是一个二进制变量。式（4）中，qi表示客户点i的包裹重量，自有车辆的载货量不能超过车辆的最大负载。式（5）表示一位雇佣车辆最多只能服务1个客户点。式（6）表示每位客户分配到1辆雇佣车辆。式（7）表示每个客户点只能被1辆车访问。

3 算例分析

设定算例各点的位置信息格式为 （序号、X坐标、Y坐标、需求量），其中序号0表示配送中心，1到11表示客户点，需求量（单位：吨） 为各点需要配送货物重量，各点具体信息如下： （0,50,50,0），（1,48,85,0.2），（2,45,70,0.3）， （3,35,75,0.2）， （4,33,58,0.15）， （5,39,40,0.2）， （6,45,30,0.1）， （7,58,34,0.2）， （8,70,30,0.25），（9,70,56,0.2），（10,70,66,0.2），（11,75,88,0.15）。根据各点的坐标使用Excel计算各点之间的距离（欧式距离），获得距离矩阵表1：

3.1 经典VRP问题分析

在经典VRP问题当中，所有的客户点需要配送中心的车辆进行服务，这样就需要拥有足够的车辆来满足配送任务。但是，由于配送任务的需求是不确定的，有时高有时低，配送中心要拥有的运力高于平均运送需求，这样就会造成运力浪费，间接提高配送成本。在本例当中，配送中心需要有3辆车才能完成服务所有客户点的任务。

表1 各点距离矩阵

图1 经典VRP问题配送路线

通过使用扫描法得到如图1的配送路线图，车辆1的路线为：0→1→2→3→4→0；车辆2的线路为：0→5→6→7→8→9→0；车辆 3 的线路为：0→10→11→0。

根据表2的距离矩阵和图1的配送线路，得到车辆1行驶里程mileage1=d01+d12+d23+d34+d40=97.5km。车辆2行驶里程mileage2=d05+d56+d67+d78+d89+d90=99.7km，车辆3行驶里程mileage3=d0,10+d10,11+d11,0=93.7km。根据得到数据计算每条路线的配送成本，得到经典VRP问题路径及成本如表2所示：

表2 经典VRP问题路径及成本

3.2 VRPOD问题分析

在众包模式下，配送中心不再需要维持3辆配送车，在这里设定为2辆，其配送路线如图2所示。此时，总共需要4辆车才能完成派送任务，其中车辆1和2为自有车辆，车辆3和4为众包车辆。

图2 VRPOD问题配送路径

根据表3的距离矩阵和图2的配送路径，车辆1和车辆2行驶里程不变仍然分别为97.5和99.7km，车辆3的总路程d0,10=25.6km，车辆4的总里程d0,11=45.5km，计算得到总配送成本为 （968+355.5ξ）元。

表3 配送路线及成本

为了检验ξ值对成本节约的影响，计算不同参数情况下，节约成本及节约率大小，如表4。在本例中ξ值越小，成本节约的越多。但是ξ值越低，司机参与众包的意愿会随着降低，影响他们的积极性，所以ξ值不是越小越好。本例当中ξ的取值范围在1到1.3之间。为了维护双方的利益，1.2是一个比较合适的值。当然，在实际情况下，不仅存在直接配送成本，还有间接配送成本，如车辆购置、维护和人员工资支付等。在众包模式下，由于需要维持的车辆和司机更少，间接成本更低，物流企业可以承受的ξ值可以更高。

表4 效益表

4 结束语

本文在经典VRP问题的基础上引入了物流众包，同时建立了VRPOD的线性规划模型，运用了扫描法求解了VRP问题下和VRPOD问题下的解，通过两种问题解的对比，从而验证在物流“最后一公里”配送中引入众包模式能在一定程度上降低终端配送成本。