城市物流配送的二阶段启发式算法  

Two-phase Heuristic Algorithm for City Logistics Distribution

作　　者：冯泉超[1] 许钦泰[1] 杨金梁[1] 樊铭渠[1] 

机构地区：[1]山东科技大学电气信息系,济南250031

出　　处：《科学技术与工程》2009年第7期1782-1786,共5页Science Technology and Engineering

摘　　要：针对城市物流配送的特点,将空间聚类算法与蚁群算法相结合运用到路径规划中,提出了一个基于交通网络的VRP二阶段解法。以带权图描述城市交通路网,利用交通网络中各个结点间的距离关系和结点的需求量,以配送车辆的容量为聚类的约束,通过多次迭代将所有结点聚集成相互独立的多个簇。选择簇间相似性最小的聚类,利用蚁群算法,根据簇之间和簇内结点间的距离关系,分两次规划配送路径,最终得到配送中心到所有结点的配送路径。该算法通过聚类降低系统复杂度,缩短了蚁群搜索时间,具有较快的速度。最后用一个仿真实例验证二阶段算法的有效性。According to the city logistics characteristic,combining application of spatial clustering algorithm and Ant Colony Algorithm,an algorithm based on traffic network is presented.Describing Urban traffic network by weighted graph,using the distance relation of the nodes in the traffic network and nodes＇ demand,the algorithm can aggregate the nodes into several independent clusters.Choosing minimum similarity degree cluster,according to the distance between clusters,the routes are planed in twice by Ant Colony Algorithm,then the distributing routes including all the nodes are got.By using spatial clustering algorithm,system complexity is reduced,ants searching time is shortened,system runs faster.The availability of the algorithm is proved by a simulation in the end.

关 键 词：物流配送 空间聚类 蚁群算法 容量约束 

分 类 号：U121[交通运输工程]