彭熙舜，陆安江，贾明俊，卢学敏

（贵州大学 大数据与信息工程学院，贵阳550025）

0 引 言

在当今时代，网购已经成为了一种新的潮流，每年由电商举办的双十一、六一八更是风靡盛行。随着快递数目的剧烈增长，物流的配送工作越来越重要。人们购买的物件也是花样繁多，生鲜快递必须满足时效性，装饰类物品需要避免发生碰撞。物流配送过程中常规应用GPS导航，而高效的物流管理取决于两个关键因素，车辆问题（VRP）与资源配置问题，因此路径规划开始被广泛应用于物流管理中。本文提出了利用Kmeans聚类将客户购买物品按照特性进行分类，再利用蚁群算法进行路径规划。

1 研究背景与意义

路径规划是近代兴起的新型技术，被广泛应用于机器人避障，无人机避障，防空导弹系统中。人们的日常生活也开始利用这种技术，比如城市交通规划，GPS智能导航，物流配送管理系统。通常情况下，按照周围环境信息的布局规划，可以将其分为全局和局部两种路径规划［1］。前者需要在实践之前掌握所有的环境数据，提前作出路径规划判断；后者主要是采取传感器实时得来的局部环境信息，及时的给出路径规划。本文主要研究解决车辆路径问题（VPR），以物流中心为起点，派出车辆向不同位置的客户进行物资配送，配送任务结束后返回起点，而其中的关键在于将配送效率最大化，车辆使用率最大化。

路径规划一般是由环境建模，路径搜索，路径平滑这3步所组成［2］。环境建模是起始环节，搭建一个方便计算机规划具体路径的模型，实质上是将物理信息转为数字信息，在空间上相互映射；……