城市物流配送是城市物流活动的一个重要环节。科学有效的城市物流配送体系,一方面有利于城市经济健康发展,另一方面有利于缓解现代城市中环境污染与交通堵塞严重、交通事故频发的问题。物流配送是连接生产与消费的一种中介服务,也是物资供应的重要环节之一。一般意义上的城市物流配送运输,是指配送中心不同客户多频度、小批量的订货要求进行组织配送,在合适的时间,合适的地点,将正确的产品以适当的数量准确地交给客户,并保证服务的质量和合理的成本。由于从事城市配送的货运汽车工作条件复杂,不仅配送点多、货物种类繁多、路况及道路网复杂,而且运输服务地区内运输网点分布也不均匀,因此,设计合理、有效的配送路线方案,控制物流成本,减少车辆数量、配送里程,限制车辆在城市中的运行时间,就成为非常现实的问题。城市物流配送作业的重点将是如何高效的使用车辆并决定最“科学经济”的行驶路线,使商品能够以合理的成本送达顾客手中。本文研究的是如何在城市环境中实现科学有效的配送规划。目前的物流配送规划研究大多放在采用启发式算法逐渐逼近最优解,主要采用的方法是遗传算法、免疫算法、退火算法、禁忌搜索算法及神经网络算法等,如姜大立建立了VRP的遗传算法,WEE-KTI重点研究了禁忌算法和遗传算法混合的启发式算法,1991年,Gendreau等人将禁忌搜索方法应用手VRP。本文中采用的是蚁群算法和聚类算法。蚁群算法是受自然界中真实蚁群觅食行为的启发而提出的一种启发式搜索算法。它具有正反馈、并行计算、较强的鲁棒性等诸多特点。然而,一般蚁群算法在车辆路径问题过程中容易出现过早收敛或停滞现象,而且蚁群算法的搜索时间较长。为了解决这些问题,本文在认真分析国内外VRP研究的基础上,将蚁群算法与聚类算法相结合,提出了一个二阶段启发式车辆路径算法。该算法首先利用空间聚类的方法,对交通网络进行简化。以交通网络中各个结点之间行驶距离作为聚类的度量,以车辆容量为聚类的约束,将所有结点分配到各个簇中,形成有限个簇,再将每个簇抽象为一个新的结点,最终将整个交通网络(或者称为G图)简化成为一个二层结构,大大简化模型的规模。然后在簇结构和簇内两个层次上分别运用蚁群算法,生成以簇为基本需求点的行车路线和簇内点集的行车路线,最后获得最佳路径表。文章除了对算法思想和算法描述做了详细介绍外,还分析了算法的时间复杂度,并通过系统实例验证了算法的有效性。