配送和集货一体化下的车辆路线问题研究

【作者】 陈诚；

【导师】 胡大伟；

【作者基本信息】 长安大学 ， 载运工具运用工程， 2006， 硕士

【摘要】 随着物流业在我国的不断发展以及物流专业化水平的不断提高，我国物流配送业近年来也得到了迅速的发展。在物流配送活动中，配送车辆的路线问题是配送合理化的核心问题，对于企业提高服务水平、降低物流成本、增加经济效益的影响也最大。为实现成本最小化和效益最大化的根本目的，配送和集货一体化将是现代物流配送的发展方向，因此对配送和集货一体化下的车辆路线问题进行研究是具有一定的理论价值和现实意义的。 本文对配送和集货一体化下多站点车辆路线问题以及配送和集货一体化下带硬时间窗的车辆路线问题进行了研究。本文首先建立了配送和集货一体下多站点车辆路线问题的数学模型，并针对问题特点设计了综合运用多种启发式算法的多阶段求解方法对模型进行了求解，计算结果表明集成配送和集货时的车辆总行驶路线比分别配送和集货时节约近一半。 考虑到现代物流的时效性因素，本文建立了配送和集货一体化下带硬时间窗的车辆路线问题的数学模型，针对问题的复杂性，设计了适合求解该问题的混合遗传禁忌算法。采用改进节约法构造和随机产生相结合的方法为遗传算法产生初始解群体，并对遗传算法中较优的一部分染色体进行禁忌搜索以加快收敛速度。用计算机编程实现了该算法，通过与有关文献中的实例进行比较，所求解的质量提高了2.1％，说明本文设计算法对该问题的适应性，以及在遗传算法中采用构造初始群体中部分解及对进化中的较优解进行禁忌搜索的方法更容易得到更好的解。最后，通过对三组标准测试数据，包括宽时间窗、紧时间窗和混合时间窗，进行大量的试验证明本文设计算法的科学可行性和有效性。更多还原

【Abstract】 With the continuous development of logistics industry and the constantly improvement of the specialization level of logistics in our country, logistics distribution industry has also been developed quickly. Of all the activities in distribution, the vehicle routing problem is the key problem. In addition, it has great much effect on enterprise to upgrade the level of service, to reduce the logistics cost and to increase economic benefits. To achieve the basic aim of minimum cost and maximum benefits, unitizing the activities of delivery and pickup will be the trend. So, it is of theoretical and practical senses to some extents to study the vehicle routing problem under the environment of unitizing the activities of delivery and pickup for this paper.The objects of this paper are the multi-depot vehicle routing problem with pickups and deliveries and the pickups and deliveries vehicle routing problem with hard-windows. Firstly, this paper sets up the mathematic model of the multi-depot vehicle routing problem with pickups and deliveries then solve it by using multi-phases composite heuristics algorithm. The result shows that the total distance traveling by vehicles when integrating pickups and deliveries is about the half of it when separate the two.This paper sets up the mathematic model of the pickups and deliveries vehicle routing problem with hard-windows, design a hybrid genetic/tabu search algorithm to solving this problem. Combine the two methods of structuring by improved C-W algorithm and producing randomly to produce starting group for genetic algorithm and using tabu search for a proportion of better chromosomes. The computing result is 2.1% better Compare with the related literature, which show the suitability of designed algorithm and that structuring a proportion chromosomes for the starting group and using tabu search in the genetic algorithm can help to get better solution fast. At last, the designed algorithm proved to be practicable, scientific and effective by using it to test three suits of standard testing dates which contain the small time-windows, big time-windows and normal time-windows.更多还原