【作者】 陈宝文；

【导师】 陈兴林；

【作者基本信息】 哈尔滨工业大学 ， 控制科学与工程， 2009， 博士

【摘要】 车辆路径问题是物流管理领域关注的热点问题,因为车辆路径问题的复杂性和多样性,如何合理安排车辆路径以最低成本收送货物,是一个富有挑战性的问题。本文受教育部归国留学人员基金资助,以车辆调度及管理系统为背景,针对目前车辆路径问题的现状,对蚁群算法进行改进并在时间窗、需求和旅行时间三方面扩展的车辆路径问题上进行求解、对运输网络仿真和优化支持向量机参数并在道路行程时间预测等问题展开了深入的研究,其研究内容主要包括以下几个方面:在分析蚁群算法基本参数的基础上,从两个方向改进基本蚁群算法。其一是通过将蚁群算法的基本参数随优化过程变化以及采用多个蚂蚁群共同优化目标的方式改进算法;另一种是将蚁群算法与邻域搜索算法结合的混合蚁群算法,采用两阶段优化对算法进行改进。分析改进后算法的复杂度和收敛性。将提出的变参数多蚁群系统和混合蚁群算法用来求解静态带时间窗口车辆路径问题,提高算法的收敛性,避免局部最优和早期收敛现象。采用前一章得到的改进蚁群算法求解两类不确定需求车辆路径问题随机需求和模糊需求车辆路径问题。不确定需求车辆路径问题是标准车辆路径问题的一个从需求方面扩展的问题。对不确定需求的规律进行统计分析,根据优化的标准,构建了随机需求车辆路径问题的机会约束和二元可能性理论模型,借鉴处理随机需求车辆路径问题的处理方式,采用模糊逻辑推理和模糊数比较两种方式得到模糊需求车辆路径问题的机会约束评价模型。通过建立的优化标准模型,使得不确定需求车辆路径问题转化为改进蚁群算法求解的一般性车辆路径问题。提出了能有效处理动态需求的插入法和蚁群算法结合对动态需求车辆路径问题进行求解。动态需求车辆路径问题是需求没有统计规律的一类车辆路径问题。首先分析城市中的派送问题,给出基于网络拓扑结构的可描述交通管制和路口延误的路网模型与动态需求车辆路径问题的抽象关系,给出动态车辆路径问题路网模型的产生机制。通过对Solomon题库的设定和模拟城市派送任务两方面得到动态车辆路径问题,为动态车辆问题的仿真环境提供检验方法。将变化的道路通行时间作为启发式信息的新的蚁群算法用来求解依赖通行时间的车辆路径问题,此问题是标准车辆路径问题的一个从旅行时间方面扩展的问题。在已知路段旅行时间分布函数的条件下,算法能够在保证车辆能够先出发先到达的一般规律下,求解动态路网条件下的最优路径。采用一种新的利用蚁群算法优化包括组合核函数参数的支持向量机参数的方法。道路的行程时间是求解各类车辆路径问题所需的关键数据。提出的一个基于组合核函数的支持向量回归机预测模型,用蚁群算法优化后的模型预测道路的行程时间。更多还原

【Abstract】 Vehicle routing problems is one of the key issues in the field of logistic management. Since its complexity and diversity,how to deliver right goods to right customers timely with the least cost by means of rationally dispatching vehicles and arranging time and routes is a challenging problem. This dissertation sponsored by the scientific research foundation for the returned overseas chinese scholars, State Education Ministry, considering the status of vehicle routing problems, improving ant colony system to solve the vehicle routing problems are described in time window, demand and travel time. Simulation road network and optimal parameters of support vector machine for travel time prediction are discussed .The detailed contents studied in the paper are as follows:Based on analysis of parameters in ant colony system,two improved ant colony systems are proposed. One is the multi-ant colony optimization using dynamic parameters (M-ACO). The other is combination of ant colony system and large neighborhood algorithm. Complexity and convergence analysis of improved algorithems are presented. Vehicle routing problem with time window (VRPTW) is solved by M-ACO and the hybrid algorithm. Simulation results show that the proposed approach is very effective in preventing the premature convergence and avoiding the local optimum problem.Ant colony optimization algorithm is applied to solve two uncertainty vehicle routing problems--vehicle routing problem with stochastic demand and vehicle routing problem with fuzzy demand (VRPFD). Stochastic vehicle routing problems is the expansion of the standard vehicle routing problem. According to optimization standard,the chance constrained model and confidence model for vehicle routing problems with stochastic demand are proposed afer introducing the statistical law for stochastic demand. The models for fuzzy demand are presented by using experience of handling stochastic demand for reference. The demand data set was handled by the theory of probability and fuzzy mathematics which make VRPFD become a general vehicle routing problems.Algorithm combined with M-ACO and local optimization is proposed for dynamic vehicle routing problem (DVRP). DVRP is researched when statistical work cannot get the law for stochastic demand. Based on analysis the relationship between logistics delivering and DVRP,road network model which can describe road network topology and intersection delay and stochastic customer demand generation are presented. DVRP generator is designed by modifying Solomon dataset and simulating urban road network.The model in accord with urban transport system can be used to test algorithm efficiency of dynamic vehicle routing problem.ACO heuristic factor was modified by travel time is presented for time dependent vehicle routing problem (TDVRP). TDVRP is another expansion of standard Vehicle Routing Problems. Based on known travel time-distance function of the road network,under the prerequisite for satisfying the First-in-First-out rule,time dependent vehicle routing problem is solved in optimization of routing and departing time. The results show that two-stage optimization strategy can get the optimal route under dynamic road net work.A hybrid kernel of support vector regression is presented using the ant colony system to optimize the parameters to improve performance.Travel time of road is important factor in path searching. The improved model is used to predict travel time. The results show that the proposed model improves computability and achieve a better forecasting accuracy than neural network.更多还原