随机配送时间车辆路径优化模型及算法研究

发布时间：2018-02-28 20:48

本文关键词： 车辆路径优化问题随机配送时间客户满意度机会约束自适应遗传算法　出处：《兰州交通大学》2014年硕士论文　论文类型：学位论文

【摘要】：物流配送中的车辆路径优化问题(Vehicle Routing Problem,VRP)是当今物流配送优化的关键环节，一直是现代物流领域研究的热点问题。有效地安排车辆行驶路径，不仅可以加快对客户需求的响应速度，提高服务质量，还可以降低物流服务商运作成本。目前对于VRP的研究多把VRP的约束条件如行驶时间、服务时间等都看成是固定不变的静态VRP，且对模型的目标函数的设定多从配送企业出发，设定为车辆行驶距离最短、配送成本最低等单目标函数，对于综合考虑客户满意度、配送成本多目标的VRP优化研究还不多见。事实上，实际的物流配送系统中由于交通、车辆和自然条件等因素的影响，使得物流配送系统具有一定的随机性和复杂性，因此对带有随机性VRP的研究更能贴近实际的配送情况。本论文研究的重点是围绕随机配送时间车辆路径问题进行的。通过分析了国内外VRP研究现状，指出了国内在VRP模型上研究还不够深入的问题，确定了本文所要解决的问题。设计了新的适合实际情况的物流配送路径优化模型，，并进行了实例验证。首先，在分析了目前VRP模型的基础上，本文在综合考虑了企业运输成本的最小化以及顾客满意度约束等多方面因素，通过对物流配送时间的随机性和顾客的满意度进行相关的研究；采用随机机会约束规划理论构建了VRP的随机机会约束规划模型，并将顾客满意度函数作为首要的约束条件体现在模型当中，在模型寻优的过程中直接起作用，从而将配送中心以往不能量化的信誉损失间接的予以量化，这在很大程度上强化了配送中心的长远利益，也提高了顾客服务水平，即准时化、高效率化等。其次，在对模型的求解过程中采用了遗传算法，由于标准遗传算法在求解车辆路径问题时易早熟收敛。本文根据求解VRP模型的特点，对标准的遗传算法的遗传操作进行了改进，设计了新的自适应遗传算法，算法的运行参数交叉率和变异率不是固定的数值，而是能够根据适应度值在进化的不同阶段进行自适应调节。最后，通过算例验证了模型和算法的可行性及有效性，对选用的算例建立了随机VRP模型，采用改进的遗传算法对建立的模型进行了求解，讨论了不同的置信度和满意度取值对于模型解的影响。研究的结果不仅对于车辆路径问题的实际应用具有指导意义，而且还能为物流配送调度系统提供决策支持。
[Abstract]:Vehicle Routing problem (VRP) is the key link of logistics distribution optimization and has been a hot issue in the field of modern logistics. It can not only speed up the response to customer demand, improve the quality of service, but also reduce the operating cost of logistics service providers. At present, the research on VRP mostly focuses on the constraints of VRP, such as travel time. The service time is regarded as the static VRP, and the objective function of the model is set from the distribution enterprise, which is the single objective function, such as the shortest vehicle travel distance, the lowest distribution cost, and the comprehensive consideration of customer satisfaction. Research on multi-objective VRP optimization of distribution cost is rare. In fact, due to the influence of traffic, vehicle and natural conditions, the logistics distribution system has a certain randomness and complexity in the actual logistics distribution system. Therefore, the research with random VRP can be more close to the actual distribution situation. This paper focuses on the problem of random distribution time vehicle routing. By analyzing the current research situation of VRP at home and abroad, this paper points out that the domestic research on VRP model is not enough. The problems to be solved in this paper are determined. A new logistics distribution route optimization model suitable for the actual situation is designed and verified by an example. First of all, based on the analysis of the current VRP model, this paper comprehensively considers the minimum transportation cost and the constraints of customer satisfaction, and so on. Through the research on the randomness of logistics distribution time and customer satisfaction, the stochastic chance constrained programming model of VRP is constructed by using stochastic opportunity constraint programming theory. And the customer satisfaction function is embodied in the model as the first constraint condition, and plays a direct role in the process of model optimization, thus indirectly quantifying the loss of reputation that the distribution center could not quantify in the past. To a great extent, it strengthens the long-term benefit of distribution center and improves the level of customer service, that is, punctuality, high efficiency and so on. Secondly, the genetic algorithm is used in the process of solving the model. Because the standard genetic algorithm is easy to converge in solving the vehicle routing problem, according to the characteristics of solving the VRP model, The genetic operation of the standard genetic algorithm is improved, and a new adaptive genetic algorithm is designed. The crossover rate and mutation rate of the running parameters of the algorithm are not fixed values. It is possible to adjust adaptively at different stages of evolution according to fitness. Finally, the feasibility and validity of the model and algorithm are verified by an example. The random VRP model is established for the selected example, and the improved genetic algorithm is used to solve the established model. The influence of different confidence and satisfaction values on the solution of the model is discussed. The results not only have guiding significance for the practical application of the vehicle routing problem, but also provide decision support for the logistics distribution scheduling system.
【学位授予单位】：兰州交通大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：F252;F224

【参考文献】