基于划分的蚁群算法求解货物权重车辆路径问题

An ant colony optimization algorithm for vehicle routing problem with cargo coefficient

考虑单产品分销网络中的车辆路径问题(VRP:vehicle routing problem).与以往诸多研究不同的是,建立了一种带货物载重量的VRP模型(weighted VRP),即车辆在两个顾客之间行驶时的载重量也作为影响运输费用的一个因素考虑.因此,需求量较大的顾客拥有较高的车辆运输优先权.在分析了问题性质的基础上,提出一种基于划分策略的蚁群算法PMMAS求解货物权重车辆路径问题,并与其他常用的启发式算法进行比较分析,表明了算法的有效性.

A distribution network between one warehouse and multiple retailers is considered. A model named weighted vehicle routing problem（VRP） is built. Being contrary to many other VRP models, the weight loaded in a vehicle through a route between two customers is considered as an important factor of system cost when a routing decision is made. With this method, the retailers with larger demands will have priority to be visited earlier. Finally, an ant colony optimization algorithm named PMMAS （partition based max-rain ant system） combined with a special partition method is proposed to solve this model. Some illustrative examples are introduced to test the efficiency of the PMMAS, and comparison analysis is conducted with commonly used heuristic algorithms for vehicle routing problem.