【作者】 陆琳；

【导师】 谭清美；

【作者基本信息】 南京航空航天大学 ， 管理科学与工程， 2007， 博士

【摘要】 随着全球市场分工的进一步细化,世界范围内贸易的频度与数量都呈现出显著的增长,物流效率成为甄别一个企业乃至一个国家经济运行效率的重要指标之一。车辆路径问题是物流运输系统的核心组件,并且由于其研究方法及成果可直接应用于组合优化领域,因而自诞生之日起就得到了理论与实务界的广泛关注,取得了大量的成果。但是,受于时代经济与信息处理技术的限制,这些研究大多是确定型模型,即假设在安排车辆路径之前所有的相关信息都已经知道并且确定。现今,社会经济运行的环境较之从前发生了巨大的变化,一方面,经济活动频率大大增加,并且伴随着大量的不确定信息;另一方面,通信及计算机技术的飞速发展不仅使社会经济秩序避免了因不确定信息的泛滥而可能引发的混乱,而且进一步促使人们利用这些不确定信息创造更多的财富。可以说,对不确定信息的处理策略及技术手段直接决定了经济实体的效率、盈利水平。针对这一新情况的产生、发展,本文对不确定信息车辆路径进行研究,开展了以下工作:首先,对不确定信息车辆路径问题的进行了一般概述。阐述了车辆路径问题的定义、构成、分类、模型以及求解车辆路径问题的经典算法;在此基础上,将不确定信息车辆路径问题划分为非实时信息处理的不确定信息车辆路径问题和实时信息处理的不确定信息车辆路径问题两大类,分析了不确定信息车辆路径问题的内涵、特点、研究现状及相应的各种数学模型、优化方法,指出研究中存在的问题。其次,对求解车辆路径问题的各类启发式算法的研究现状进行了较为详细的综述和归纳,阐述它们诞生的源泉思想、运作流程,并详尽分析了它们在车辆路径问题中的应用进展。在此基础上提出了新的改良算法,即最大熵分布估计算法、自感应蚁群算法和混合粒子群算法,进行了相应的理论分析与证明,为处理复杂的不确定信息车辆路径问题提供必要的数学求解工具。第三,逐次递进研究了2类随机车辆路径问题。首先,研究仅有供(取)货任务的车辆路径问题,即随机需求车辆路径问题。对此,结合现实生活中长期顾客服务记录所隐含的统计性知识构建了新的统计学模型,设计了求解该模型的混合粒子群算法,并通过大量的仿真试验比较分析了新算法与其他智能算法的优劣。其次,进一步研究具有供货和取货双重任务的车辆路径问题,即同时供货和取货的随机车辆路径问题。应用上节的统计学思想,构建了该类问题的整数规划模型,提出期望程度因子、距离性比因子等概念,设计了针对该问题的自感应蚁群算法,并与其他优化算法进行了数据测试与比较,验证了算法的有效性。第四,分析了模糊车辆路径问题,综合选择车辆行驶时间以及顾客预约时间为模糊信息参量,克服了现有研究仅局限于某种单模糊变量而未能系统考虑复合模糊变量的缺陷,并采用细分顾客类别以吸收配送者知识系统的方法,分别以物流企业效用最大化和顾客效用最大化两种决策目标构建了2类模糊车辆调度优化模型,给出了求解该类问题的最大熵分布估计算法,并结合仿真试验分析了决策参数的变化对2类模型计算结果的影响,给出了相关参数制定的依据。第五,渐进深入研究了2类实时动态车辆路径问题。首先,研究了非满载动态车辆路径问题,即动态旅行商问题,阐述了动态车辆路径问题实现的技术支持单元以及动态信息数据生成的方法,并利用仿真试验考察了实时不确定信息车辆路径问题各现场一次性优化方法的性能。其次,研究了更具现实意义的满载有时间窗动态车辆路径问题,在服务中心处理新信息的机制以及动态规划行驶中车辆行驶路径的策略方面提出了新的见解,阐明物流企业对新信息的处理方法,提出动态车辆路径问题优化的分置策略,设计了针对该问题的改进蚁群算法以及相应的分段计算启用规则,并结合仿真试验与各现场一次性优化方法及基本蚁群算法进行了性能比较,验证新策略及新算法的有效性。最后,在上述理论的基础上,以VB为开发语言,开发出了具有Windows图形界面的动态车辆路径规划系统,该系统可在电子地图上动态显示出车辆的行驶路线及当前位置,并可根据动态信息的变化确定最优路径并显示输出。更多还原

【Abstract】 Along with the further division of labor in global market, trade frequency and quantity in the worldwide scale have grown remarkably, and the logistics efficiency has become one of important indicators in judging economy operating efficiency for an enterprise and even a state. Vehicle routing problem is the main problem in the field of logistics transportation system, for its research methodology and the achievement can apply directly to the combination optimization domain, thus it has obtained the widespread attention and made a great achievement in theoretical and the practical realm since it was born. However, restrained by the time economical background and the information processing technology, these researches are mostly confined in certainty models, namely supposing all related information has known and determined before planning vehicles routing. Nowadays, the environment of social economy operating has changed greatly comparing with the past. On the one hand, economic activity frequency increases considerably, and also following the massive indefinite information; on the other hand, the rapid development of correspondence and computer technology not only causes the social economy order to avoid the confusion resulting from the flood of indefinite information, but also further urges the people to use these indefinite information to create more wealth. It can be said that the processing strategy and the technical method to indefinite information directly decides efficiency and profit level of a economic entity. In view of this new situation, this article studies the uncertain information vehicle routing problem, and the work are as follows:First, this article gives the general outline to uncertain information vehicle routing problem, including the definition, the constitution, the classification, the model as well as the classical algorithms to solve the vehicle routing problem. On this basis, this article puts the uncertain information vehicle routing problem into two parts----the problems of the non-real-time information processing and the real-time information processing according to the advancement of time development. And this article also analyzes the connotation, the characteristic, the research present situation of uncertain information vehicle routing problem and the corresponding mathematical model and the optimized method, and then points out the problems in the process of research.Second, this article makes a throughout overview and summary of the present situation of all kinds of heuristic algorithms to solve vehicle routing problem, elaborates the source thinking and the operation flow of these algorithms and then gives a detailed analysis of application progress into vehicle routing problem. On this basis, this article has proposed new algorithms----maximum entropy distribution algorithm, self-telepathy ant colony algorithm and hybrid particle swarm optimization, and carried on the corresponding theoretical analysis and the proofs, which provide the essential mathematics solution tool to deal with the complex indefinite information vehicle routing problem. Third, this article gradually researches on tow kinds of stochastic vehicle routing problems. The work studies from vehicle routing problem with only supplying or carrying assignment. To this, combining with the long-term customer record in the real life, this article constructs the new statistics model, designs hybrid particle swarm optimization to solve this model, and comparatively analyzes advantage and weakness between the new algorithm and other algorithms. Then, this article further studies on the vehicle routing problem with simultaneous selivery and pick-up.By application the statistics method in previous section, this article constructs integer programming model for this kind of question, proposes concepts of the expectation degree factor, the distance compares factor and so on, designs self- telepathy ant colony algorithm to solve this question, compares dates with other optimized algorithms which finally validates this algorithm.Forth, this article analyzes the fuzzy vehicle routing problem. Taking vehicle’s fuzzy travel time and customer’s fuzzy due time as fuzzy information parameter, using the method of subdivides the customer class to absorb the allocation knowledge system and using the method of subdividing the customer’s class to absorb the carriers’knowledge system, this article converts two deciding-making goals of logistic enterprises’utility maximization and customers’s utility maximization to two kinds of fuzzy information vehicle scheduling model and gives maximum entropy distribution algorithm to solve this kind of problem, analyzes the influence of the computed results of these two kinds of models with the change of policy-making parameters and suggests the frame basis of correlation parameters of the formulation.Fifth, this article gradually lucubrates two kinds of dynamic vehicle routing problem. The research starts from dynamic vehicle routing problem of non-full loads, namely dynamic traveling repairman problem, elaborates technical support for the realization of dynamic vehicle routing problem as well as the production method of dynamic information datas, and inspects the performance of various one-off optimization strategies in various scenes of real-time uncertain information vehicle routing problem by the simulation experiment.Then, this article makes study on dynamic vehicle routing problem of full loads with time windows, which is a more practical significance problem. This article also proposes new notions about the mechanism of deal with new information and the strategy of the dynamic programming of travel routing of the traveling vehicles, which expounds the methods of logistic enterprise to deal with new information, proposes separated-gang strategy to optimize dynamic vehicle routing problem,designs modified ant colony optimization to improve this problem and the corresponding using regulation of replicate computation, and compares the performance of various one-off optimization strategies and ant colony algorithm based on artificial test which confirms the validity of the new strategy and the new algorithm.At last, on the basis of the above theory, taking VB as the development language, this article develops dynamic vehicle routing plan system that has Windows graphical interface. And this system can dynamically demonstrate the vehicles’traveling routing and the current position on the electronic map, choose the optimal routing according to the dynamic information change, and then demonstrate the output.更多还原