基于改进贪心算法的动态车辆路径问题分析

摘要：针对移动电子商务下的动态车辆路径问题，在贪心算法的基础上，结合K-d tree方法和Held-Karp模型对贪心算法进行改进，对移动电子商务环境下的动态车辆路径问题进行案例分析，并验证该算法的有效性。

关键词：移动电子商务；动态车辆路径问题；改进贪心算法；案例分析

中图分类号：O22 文献识别码：A 文章编号：1001-828X（2017）001-000-01

一、引言

移动电子商务环境下取货车辆调度问题的实质就是动态车辆路径问题（DVRP）。目前对于DVRP问题的解决方法主要包括两类，一是采用判断准则将新出现的顾客添加到已经制定的路线中。二是采用优化算法从全局最优角度出发。但是目前上述算法不能实现全局系统最优，且实时性不强。

二、理论概述

1.贪心算法

贪心算法求解DVRP的过程是将任意两节点构成的边按边长升序排列有（Cn2=n（n-1）/2条边），从最短边开始依次添加合法边至当前路径中，直到添加完所有合法边，形成每条路径的两端点都与配送中心节点O连接形成Hamilton回路为止

2. K-d tree方法

K-d tree方法即k维空间二叉搜寻树，是一种分割k（本文k=2）维数据空间的数据结构，主要应用于多维空间关键数据的搜索（如：范围搜索和最近邻搜索）。其原理是将系统中n个点所在k维空间进行分割，将分割后的区域视为二叉树的节点，将整个区域用二叉树表示。

3.Held-Karp模型

Held和Karp在1970年提出了经典的Held-Karp模型，用于求解旅行商问题的最优解下界。该模型的原理是使用一个实数向量η=（η1，η2，…ηn）改造距离矩阵的模型。

4.改進贪心算法的步骤

对改进贪心算法的整个过程分步骤说明：（1）读取DVRP问题和第i个新出现的顾客；（2）设置t和α两个参数；（3）根据顾客和配送中心的坐标信息、t建立K-d tree；（4）根据坐标信息和α计算向量η；（5）根据K-d tree和Held-Karp 模型改造后距离矩阵，计算每个节点i对应的最邻近节点j，并将边（i，j）和对应长度rij+ηi+ηj存至Heap，且按边长升序排列；（6）提取Heap中的第一条最短边，假设为（x，y）；（7）判断添加边（x，y）至当前路径是否满足判断合法边的4条规则，满足执行（9）否则执行（8）；（8）更新Heap数组，保证每个可连接节点与最邻近节点形成的边均在Heap中，然后执行（6）；（9）添加边（x，y）至当前路径中；（10）确定是否还有合法边存在，如果有则执行（8）；否则将形成的m条路径的端点分别与配送中心连接得到最终解，结束程序。

三、算例说明与求解

本文以Li等人在2005年提出了12个n为560～1200的算例为数据基础，算例名称最后的数量表示顾客数量，动态程度φ分别为0.25、0.50、0.75、1.00。求解质量与求解时间如表1。

改进贪心算法在求解质量方面优于已知最优解，求解时间较短。求解最大的算例DVRP-1200，φ=1.00时，顾客出现的平均时间间隔为24.00s，计算耗时仅为10.35s，能满足对于算法时间的要求。

四、结语

本文结合K-d tree法和Held-Karp模型提高求解质量策略，提出了移动电子商务环境下动态车辆路径问题的改进贪心算法，对12个标准算例求解验证了该模型和算法能在合理的时间内求解DVRP问题。

参考文献：

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

[2]Li FY， Golden B， Wasil Edward. Very large-scale vehicle routing：new test problems， algorithms， and results [J]. Computers and Operations Research，2005， 32 （5）：1165-1179.

作者简介：李珊珊（1991-），女，汉族，山东德州人，山东科技大学矿业与安全工程学院硕士研究生，系统理论专业。