2 研究综述

2。1 VRP问题概述

2。2关于VRP问题的研究

2。3关于C-W节约法的研究

3。建立模型

3。1 模型假设

本次研究针对两类包裹提供最优的快递员配送方案。第一类是电商包裹，快递员需要从网点提取并配送至消费者，第二类是同城O2O包裹，快递员需要在指定时间去商户提取并在指定时间内配送至消费者。

设定每天8点前，所有电商包裹都抵达网点。快递员在8点开始从网点进行派送，快递员需要在晚上8点前将所有的电商包裹送至消费者手中。在配送电商包裹的同时,快递员还要配送同城O2O包裹（如外卖订单等），对于这类包裹，快递员需要在指定时间之前到达商户领取包裹，并在指定时间之前送达消费者手中。

为模型简化和符合实际情景，做如下假设及限制：

（1）快递员把包裹送至消费者手中抽象为快递员把包裹送到离消费者最近的配送点，并在配送点处理完成。

（2）由于每个网点的配送范围两两不重合，所以每个配送点仅会被一个网点服务到。

（3）每个快递员任何时刻携带的包裹量不得大于140件。

（4） 每笔同城O2O订单，有商户的领取时间限制，快递员不得晚于该时间到达商户，如果快递员早于该时间到达，则快递员需要等待至领取时间。同时，每笔订单还有消费者最晚收货时间，即快递员不得晚于该时间送达至配送点，如果快递员早于该时间送达至配送点，快递员不需等待，可直接进行配送。

（5）每个配送点的电商包裹只能一次配送完毕,不能分多次配送。

（6）选取上海较大的O2O商户（含外卖等）598家。这些同城O2O包裹将由快递员到商户取走并送到配送点给消费者。每笔同城O2O订单可能包含若干包裹，从消费者体验考虑，只可在满足总包裹量不大于140件的情况下一次取走，不可分批取走。

（7）快递员的平均时速是15公里／小时。。

（8）快递员在配送点的停留(处理)时间，停留时间和配送地点该次所要配送的包裹量相关。

（9） 快递员数量上限1000个，有配送任务的快递员数量可以少于1000，快递员可以服务多个网点。

（10） 作为起始条件，可以指定快递员8点从任何一个网点出发，快递员如果完成当天的任务，则在最后一个配送点结束。

由此可见，该研究是在有约束条件下的VRP问题，同时，O2O包裹还涉及到时间窗限制。

3。2 C-W节约算法简介文献综述

整个研究涉及两类包裹配送：电商订单和O2O同城包裹，因此，本算法采取“先规划电商订单路线，再解决O2O订单”。先以C-W节约算法为基础，再通过整体优化、改良，初步建立电商订单的路径。然后遍历所有快递员的位置，将派出此时此刻最优的快递员去配送O2O订单（O2O同城订单产生的时间不固定）。

节约法(the Clarke-Wright algorithm)是一种常见易用的启发式算法，由Clarke和Wright于1964年提出。C-W节约法思路基本如下：假设每个配送员从配送中心出发，直接抵达某一配送点，处理完包裹后直接返回配送中心，即构成了n条“O – i - O”（i=1，2，3，……，n）的初始路线，第i条路线的里程可记为：

初始情况下，配送员从配送网店出发，到配送点1、配送点2分别进行配送并返程，即“配送中心—配送点1—配送中心—配送点2—配送中心”的路径，这样该路径运输距离为：

现假设将两条路径合并在同一条配送路线中（前提为配送员配送包裹不超重），此时，配送员数量减少一人，同时运输总距离减少。此时的运输总距离为：