摘 要：针对移动电子商务环境下的动态车辆路径问题，本文将动态车辆路径问题转化为静态车辆路径问题，建立问题模型，并利用贪心算法进行求解。

关键词：移动电子商务；车辆调度；模型；贪心算法

DOI：10.16640/j.cnki.37-1222/t.2017.04.134

1 引言

移动电子商务的位置选择具有随机性、便利性、区域性以及个性化等特点，使得顾客的需求呈现出多样化、个性化、批量小、次数多等特征，给物流快递企业的取货过程增加了一定难度。顾客通过移动电子商务平台下订单、取消或改变订单等信息可能会使原定制的取货路径方案变的次优甚至不可行，因此物流快递企业调度中心应根据平台上出现的新信息不断的与原信息进行合并，对顾客需求的变化作出及时响应，快速调整车辆路径，满足顾客需求。因此，鉴于上述背景，本文主要针对移动电子商务下的动态车辆路径问题，将动态车辆路径问题转化一系列静态车辆路径问题问题，建立問题模型后利用贪心算法进行求解。

2 问题描述及建模

2.1 问题描述

移动电子商务环境下动态车辆路径问题的运作流程：移动电子商务获取顾客需求量和顾客位置信息，智能交通系统实时获取交通信息，全球定位系统实时定位取货车辆，基于位置服务获取任意两个顾客之间的距离。调度中心根据移动电子商务平台将新信息与原信息结合生成新的车辆路径调度方案，并将指令通过全球移动通讯系统传达给取货车辆司机，及时改变路线，提高企业服务质量。

2.2 问题模型

本文仅考虑出现新顾客的情况，解决思路是将不在配送中心的取货车辆虚拟为一个顾客，且需求量为当前已经装载量，并将该虚拟点设置为第一个服务的顾客，从而将动态车辆路径问题转变为静态车辆路径问题。

移动电子商务环境下动态车辆路径问题可以描述为：存在图其中节点集合表示1个配送中心和个顾客，边集合表示任意两节点的边，边长用表示。物流配送中心有辆车，每辆车的装载能力为，每辆车的最大行驶距离为，整个取货过程中出现新信息的次数为，每个顾客的需求量为，且（）；新信息出现的时间为，表示时末服务的顾客数，表示在时方案中的车辆数，表示时正在执行取货任务的车辆数量，表示在时任意两点之间的距离，表示车辆k从顾客i到顾客j，经过则为1，否则为0；v表示车辆平均行驶速度，为保证每辆车均能在周期内完成取货任务，设（T为取货周期），表示动态程度：在取货过程中，出现的新顾客数量与总的顾客数量的比值。

对车辆进行动态调度时，还应满足以下条件：每辆车都是空载从配送中心出发，取货完成后再回到配送中心；顾客只能被一辆车服务一次；每辆车的装载能力不能超过；每辆车的行驶距离不能大于。

3 贪心算法设计

求解移动电子商务环境下的动态车辆路径最大的难点在于取货过程中会不断出现新的信息，所以要求算法的求解速度非常快。本文利进贪心算法求解动态车辆路径问题，能够快速的合并新的信息并从全局最优的角度出发得到最优解。

贪心算法是通过选择来得到一个问题的解，它所做的每一次选择都是当前状态下某种意义的最好选择。贪心算法求解动态车辆路径的过程是将任意两节点构成的边按边长升序排列有（条边），从最短边开始依次添加合法边至当前路径中，直到添加完所有合法边，形成每条路径的两端点都与配送中心节点O连接形成Hamilton回路为止。

贪心算法求解动态车辆路径时判断一条边是否为合法边的4条准则：

（1）添加该边后不会使所有点连接边的数量大于2；

（2）该边不会使图中产生边数小于n的圈；

（3）添加该边生成的单条路径包含的所有顾客需求总量之和不会超过C；

（4）添加该边所在的路径长度与该路径两端点至配送中心的长度之和不会超过D。

4 结论

本文针对移动电子商务环境下的动态车辆路径问题，将动态车辆路径问题转化为静态车辆路径问题，建立了取货车辆调度问题模型并利用贪心算法进行求解。

参考文献：

[1]刘宇熹，蒋艳.中国移动电子商务发展研究及其SWOT分析[C]. 2010.

[2]易云飞，董文永，林晓东等.求解带软时间窗车辆路径问题的改进伊藤算法及其收敛性分析[J].电子学报，2015（04）：658-664.

[3]王旭，葛显龙，代应.基于两阶段求解算法的动态车辆调度问题研究[J].控制与决策，2012（02）：175-181.

[4]熊浩，胡列格.多车型动态车辆调度及其遗传算法[J].系统工程，2009（10）：21-24.

[5]饶卫振.大规模动态车辆路径问题优化方法研究[D].大连理工大学，2012.

作者简介：李珊珊（1991-），女，山东德州人，硕士研究生。