随机车辆路径问题模型及算法研究

【作者】 刘贵英；

【导师】 胡大伟；

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

【摘要】 随着市场经济发展步伐的加快，作为“第三利润源泉”的物流对经济活动的影响日益明显，越来越引起人们的重视。处于末端的物流配送，具有提高物流经济效益，优化、完善物流系统，改善服务，降低成本等功能，在物流系统中占有重要的地位，因此逐渐成为挖掘利润源泉的突破口，也越发显示出它的重要性。 本文系统介绍了配送的概念和特点，物流与配送的关系，配送的基本环节和流程，配送系统的功能和目标，并分析了路径优化在配送中的作用。配送的核心是送货，合理的安排配送路径对于到达配送系统目标，即提高客户服务水平，提高配送效率，提高配送质量，降低配送成本有十分重要的作用。因此车辆路径问题成为近年来的研究热点。 本文阐述了车辆路径问题的概念和分类，并重点研究了随机车辆路径问题，如介绍了随机车辆路径问题的概念、分类、数学模型及求解方法以及对随机因素的处理方式等。针对随机顾客的车辆路径问题和随机需求的车辆路径问题两类问题，给出了相应公式定义和符号，以及在不同策略下计算先验序列期望长度的表达式，并采用空间填充曲线(spacefilling curve，简称SFc)和or—opt搜索相结合的方法设计了算法，运用C语言编制了相应的求解程序，最后通过实例验证了本文提出的模型的正确性和算法的有效性。更多还原

【Abstract】 With the development of market economy, logistics, as "the third headspring of profits" has a great influence on the action of the economy, which caused people much thoughtful of. Distribution has the important role in the system of logistics, which has a great influence on efficiency, cost , and benefit. So it became the breakthrough of the headspring of the profit, which displayed an important role.The paper introduced the concept and the characteristics of the distribution, the relationship between logistics and distribution, the basic process, the function and target of the distribution. It analyzed the importance of the optimization of the path in the distribution. The core of distribution is delivering goods. For achieving the target of distribution system that increases the service level, the efficiency and the quality of distribution, and lowers the cost of the distribution, the reasonable arrangement the distribution path is necessary. So vehicle routing problem became the hotspot of research in the recent years.This paper expatiate the concept of the vehicle routing problem, and divide it into different sort.It laid special stress on the stochastic vehicle routing problem. The paper introduced the concept, classify, mathematical model and the solved method and the handling of the stochastic factor. The paper studied two kinds of the problem, the vehicle routing problem with the stochastic customer(VRPSC), and the vehicle routing problem with the stochastic demands(VRPSD). We give the definition of the formula and the denotation, and the expression of the expected length of the priori sequence under different strategies. We designed the arithmetic based on the spacefilling curve(SFC) and or-opt method, and used C programming to compile the solved program. Finally we proved correctness of the model and the validity of the arithmetic by the numerical example.更多还原