【作者】 吴斌；

【导师】 王万良； 赵燕伟；

【作者基本信息】 浙江工业大学 ， 控制理论与控制工程， 2008， 博士

【摘要】 物流被称为“第三利润源泉”,越来越受到人们的关注,日益成为国民经济的基础产业。运输是物流中的重要环节,占物流成本的60%以上。车辆路径问题主要研究物流配送中车辆线路优化以降低运输成本。该问题是运筹学和组合优化领域中的著名NP问题,在航班调度、列车编组等众多领域都有应用。由于NP问题求解的复杂性,目前车辆路径问题的求解方法主要使用各种智能优化算法。本文主要研究了以下四种模型的车辆路径问题:有能力约束的车辆路径问题,开放式车辆路径问题,基于客户满意度的开放式车辆路径问题,开放式动态网络车辆路径问题。研究了粒子群及其改进算法对上述模型的求解。具体的研究内容如下:(1)首先介绍了论文的研究背景及意义,给出了车辆路径问题的定义,分析了车辆路径问题的组成要素。然后在对国内外大量文献总结提炼的基础上,从车辆路径问题的模型和求解算法两方面,深入分析了车辆路径问题的国内外研究现状。(2)系统研究了基于粒子群算法的有能力约束车辆路径问题(CapacityVehicle Routing Problem,CVRP)。提出了整数编码、实数编码两种求解CVRP的方法。在整数编码中,以交换数为基础,对粒子的速度重新定义,并对速度的加、减等操作进行了定义,提出了“换位减”算子作为整数编码的速度计算方法;针对整数编码算法存在的问题,提出了一种实数编码方法求解CVRP,用实数的整数部分表示客户所在的车辆,小数部分表示在该车辆中配送的次序,融合遗传算法的思想,引入交叉算子以增加种群的多样性,详细讨论了粒子群算法的各个参数对算法结果的影响。为了与其他智能优化算法比较,研究了遗传算法、人工鱼群算法在CVRP中的应用。将双种群遗传算法用于CVRP的求解;提出了人工鱼群算法在CVRP中的应用,针对车辆路径问题的特点,定义了鱼群的距离、领域等概念,提出了人工鱼根据自身在鱼群中的排序,自适应选择移动算子的策略。(3)通过引入虚拟配送中心的概念,建立了开放式车辆路径问题的三下标数学模型。提出了开放式车辆路径问题的粒子群求解方法,将最邻近插入、最远插入、2-Opt、3-Opt等启发式算法作为再优化过程引入粒子群算法,通过这些启发式算法调整线路内和线路间的客户来改进解,从理论上分析了这些算法的计算复杂度。通过实验分析,找出合适的启发式算子,并和其他的算法进行了比较。(4)以客户满意度为首要优化目标,建立了基于客户满意度的开放式车辆路径问题的数学模型,使用梯形模糊数表示客户满意度。综合考虑距离、等待时间、客户的满意度等因素,定义了广义的距离和节约费用的概念,提出了改进的最邻近法和最廉价插入法,将这两个算法作为初始化和改进算子结合粒子群算法进行优化求解。分析了算法的复杂度,对算法的各个参数进行了讨论,通过实验仿真对这几种方法进行了分析比较。(5)动态网络车辆路径问题目前研究的热点和难点问题,将动态网络与开放式两个因素结合起来研究车辆路径问题还未见报道。本文针建立了开放式动态网络车辆路径问题的数学模型,提出了一种连续时间依赖函数模型。提出了自适应惯性权重调整的粒子群算法,定义了粒子的“位置比”概念,充分利用粒子的已有知识,动态的调整惯性权重。在算法中,引入公告板策略,根据粒子适应度的高低分类更新粒子状态,对于优秀粒子使用一种新的状态更新公式,以使其跳出局部极值点。对于适应度低的粒子,通过统计其在公告板中出现的频率,用新的粒子替换以保持种群的多样性。通过实验讨论了算法的参数设置,对几种惯性权重方案进行了分析比较,实验结果证明了算法的有效性。(6)在上述理论工作的基础上,针对第三方物流在国内的迅速发展,而相应的车辆调度软件功能不够完善,开发了智能车辆调度系统。该系统包括智能车辆调度、承运单的管理、电子地图的显示等功能。该系统可以处理有时间窗、有能力约束等多种情况的车辆调度问题,提供遗传算法、粒子群算法等多种优化算法供用户使用。系统在杭州某物流公司应用,取得了良好的效果。最后,对全文研究工作进行了总结,展望了车辆路径问题的模型和算法研究的前景。更多还原

【Abstract】 Logistics, which is regarded as "the third profit source", has obvious impact on economic activity of the world day by day, and cause people’s more and more attention too. Transportation and delivery is the key part in the logistics, 60% of all the logistics cost. Vehicle routing problem (VRP), which is research on how to plan the vehicles routes in order to save the transportation cost, is the well known NP problem in the field of operation research and combination optimization. It has been applied to many fields, such as flight scheduling, train organizing. VPR have many models because of its many constraints, such as custom, network and vehicle type. For NP complexity, the polynomial method has not been found now, so most researchers concentrate on the research of heuristic method.The dissertation mainly studied four VRP models: capacity vehicle routing Problem (CVRP), Open Vehicle Routing Problem (OVRP), the Customer Satisfaction Vehicle Routing Problem (CSVRP) and the Time Dependent Vehicle Routing Problem (TDVRP). The main contributions of the paper are as follows:(1) First the research background and significance of the thesis is introduced, and the definition of vehicle routing problem is given. The composition elements of Vehicle routing problem is analyzed. Then based on summing up a large number of domestic and foreign literatures, survey the status of vehicle routing problem deeply from the model and algorithms. Open vehicle routing problem and time dependent vehicle routing problem as hot issues are discussed detailedly.(2) The CVRP is deeply and systematically studied based on Particle Swarm Optimization. Two encoding methods: integer encoding and real number encoding are presented. In the integer number encoding, based on the "exchange number", the velocity of the particles is redefined, and various operator of velocity is defined. "Exchange minus operator" is constructed to compute particle’s velocity. In the real number encoding, the vehicle is mapped into the integer part of the real number; and the sequence of customers in the vehicle is mapped into the decimal fraction of the real number. The crossover operator is inducted to improve the diversity of the population. The impact of various parameters for the result is discussed detailedly. For the sake of comparing with other intelligent algorithms, Genetic Algorithm and Artificial Fish School Algorithm are studied. Double Genetic Algorithm is presented for CVRP, and two populations is initialization, each has its probability of crossover and mutation, and the two populations exchange the better chromosome. It can break the balance of inter-population in the local minimization, increase the diversity of the population, escape the local minimization. For Artificial Fish School Algorithm, some definitions and rules when the AFS A algorithm is applied into combination optimization problem is presented. The operation rules of AFSA for VRP are presented, method of encoding, behavior evaluation and so on. The computational complexity of these algorihtms are analyzed and the parameters of algorithms are discussed through experiments.(3) The mathematical model of Open Vehicle Routing Problem is founded, and Particle Swarm Optimization combined the global search and local search algorithms are presented. Several heurist methods are applied into the post-optimization procedure,such as 2-Opt,3-Opt, Nearest Insertion Algortihm. They are used to optimize the inner or outer routes and modify illegal solutions. The computational complexity of these algorihtms are analyzed . In the experiments, the performance of the proposed post-optimization algorithm is analyzed and the particle swarm optimization algorithm is compared with other heuristic methods.(4) The multi-objective vehicle routing problem to optimize both customer satisfaction and the transportation cost is proposed. The customer satisfaction is denoted by trapezia fuzzy number. The improvement Nearest Neighbor Algorithm and Cheapest Insertion Algorithm are presented. The general cost is defined, which is included customer satisfaction, distance, waiting time and other factors. The two algorithms hybrid PSO is proposed to solve the problem. The complexity of the algorithm and the algorithm’s parameters are discussed. Finally, in the experiments, these algorithms are analyzed and compared.(5) Time dependent vehicle routing problem is more complex than other VRPs, because its travel cost changed with the time. In the paper, the mathematic model of the problem is founded, and a continuous function is presented for the time dependent network model. The auto-adapt parameter of PSO is presented. Each particle’s parameterωcan auto-adapt regulate according to the fitness changing. At the same time, call-board policy is introduced in the algorithm, and the particle update its position according to the fitness. For the better particle, a new updating fomula is applied,and for the inactivity particle, they are displaced by the new particles. In the experiment, the parameters of the algorithm are discussed detailedly, and the result show the algorithm is efficiency.(6)Based on the above the academic research, an intelligent vehicle routing system based on the 3rd party logistics industry is developed. The system include the following functions, such as vehicle scheduling, route planning, delivering order building, electronic map display, and basic information manager. The system supports the models of CVRP, VRPTW, and provides the genetic algorithm, particle swarm optimization and so on. The system has been applied in a 3rd party logistics company, and have favourable economic benefit.更多还原