【作者】 张念志；

【导师】 吴耀华；

【作者基本信息】 山东大学 ， 物流工程， 2010， 硕士

【摘要】 近年来,随着可利用自然资源的日趋减少以及人们环保意识的增强,能源的回收利用越来越受到人们的重视。在政府构建集约型社会政策指引下,正向物流和逆向物流相结合成为时代的要求,由此衍生的集送货一体化车辆路径问题已成为当前国内外物流领域的一个研究热点。对于集送货一体化车辆路径问题,目前的研究尚不够深入,并且,实际的车辆路径问题往往规模较大,这就需要一种耗费时间较少、求解质量较优的算法来满足实际工作的需要。本文针对这一要求,提出了“先预分派,后优化”的启发式算法。首先,借鉴扫描算法的思想对客户进行预分派。根据实际中距离相对较近的客户由同一辆车提供服务的特点,把在一定扫描范围内的客户分派给同一辆车；然后,运用改进的粒子群算法分派并优化配送线路。在优化过程中,为保证粒子所代表的配送线路是可行的,对于配送线路不可行的粒子,及时进行调整。这种基于客户预分派的粒子群算法,优化效果优于客户车辆随机分派的基本粒子群算法,从而能够保证粒子在飞行中快速收敛,有利于在较短的时间内找到较优的解决方案。为验证该算法的有效性,本文进行了大量的仿真实验。实验主要包括两部分：对车辆路径问题和集送货一体化的车辆路径问题的数据集分别进行了测试。实验结果表明,这种基于客户预分派的改进粒子群算法具有较高的计算效率,能够在合理的时间内得到较优解,这为解决实际生活中客户规模较大的车辆路径问题提供了一种很好的解决思路。最后,本文对于改进粒子群算法的应用前景进行了展望,并给出了进一步的研究方向。更多还原

【Abstract】 In recent years, with the reduction of renewable resources and the growing awareness of environmental protection, people increasingly pay attention to the energy recovery and utilization. Besides, the "Saving Society" policy supported by the government makes the combination of forward logistics together with reverse logistics become a requirement of the times. Therefore, a great many of research interests have been shown on vehicle routing problem with simultaneous pickup and delivery (VRPSPD).Current research on VRPSPD is still not deep enough. Moreover, due to the large scalability in current practical problem, algorithms with less running time and relative acceptable problem-solving ability are needed in practice. With the aim of the difficulties in solving them, a customer pre-assigned two-phase heuristic algorithm is developed. We first deploy different vehicles, with algorithm used to assign customer groups to delivery vehicles, so customers are assigned to the same vehicle, the angle of which with the datum mark is only slightly different. Secondly we propose a modified particle swarm optimization to arrange customers visiting sequences for every vehicle. In process of optimization, the infeasible routes which violate the capability constraint are not abjured but adjusted before the next iteration. So the number of infeasible routes decreases through this adjustment, and it can help the particle to move forward to a more feasible solution.In order to verify the effectiveness and efficiency of the proposed algorithm, a large number of simulation experiments have been carried out. They can be divided into two parts:experiments on vehicle routing problem and vehicle routing problem with simultaneous pickup and delivery. The experimental results prove the feasibility and validity of the proposed method which can obtain the efficient solution within short time. Therefore, it can be used to solve the real-life large-scale vehicle routing problem. At last, the thesis predicts the application prospect of the improved particle swarm optimization and gives some directions of future research.更多还原