具有时间窗约束的累积性车辆路径问题研究
发布时间：2018-10-20 07:32
【摘要】：在当代经济快速发展和科学技术迅速进步的推动下,物流业作为国民经济重要的服务性支柱产业,正在世界各地迅速发展。运用科学的方法对运输运作过程加以指导和优化可以有效的降低物流配送成本进而降低总物流成本,是提高企业竞争力的重要手段。本文在对车辆路径问题的相关基础模型、衍生模型进行探讨总结,以及对解决该类问题的各类算法进行全面综述的基础上,对中国物流运输运作的现实情况进行了深入调查。由于中国高速公路系统融资建设的特殊性,国内高速公路收费的计价收费方式与国外发达国家有所不同,传统的车辆路径问题模型已经不能满足我国物流规划的实际需求。基于对中国实际物流运输中成本计算方法的研究,并考虑到我国高速公路系统计价收费方式的特殊性,提出了以降低中国实际运输中车辆运输成本为目标的具有时间窗约束的累积性车辆路径问题。该问题的目标成本同时与运输路径上的行驶距离和流量有关,符合中国实际的物流运输运作现状。鉴于新问题成本衡量方式的复杂性,本文设计了新型的禁忌搜索算法结构对其进行有效求解:(1)算法中嵌入路径间交叉搜索、可行解路径内邻域搜索和不可行路径内邻域搜索三种邻域搜索方法,形成一套系统的搜索方案,并允许同时在可行和不可行解空间内进行邻域搜索,扩大搜索的范围;(2)提出基于预处理和迭代思想的邻域解运输成本的低复杂度计算方法;同时采用Nagata提出的时间窗违反计算方法对解的时间窗约束违反进行评估,大大降低了计算时间。在对算法涉及的相关参数进行试验的基础上,本文进行了大量的算例实验。对新型问题的数值试验不仅证明了所采用的Nagata时间窗违反计算方法相对传统方法的时间节约性和有效性;同时由于该问题可以覆盖多类已被研究过的车辆路径问题,对相关问题的实际问题的计算不仅验证了模型的全面覆盖性和正确性,更体现了本文算法的高效性和时间节约性。本文的研究旨在为中国实际的物流运输运作提供相关决策支持,同时希望相关研究方法能够运用到实际中,充实车辆路径问题的相关理论体系,为将来相关邻域研究提供一个新的方向。
[Abstract]:With the rapid development of modern economy and the rapid progress of science and technology, logistics industry, as an important service pillar industry of national economy, is developing rapidly all over the world. Using scientific methods to guide and optimize the transportation operation process can effectively reduce the cost of logistics distribution and then reduce the total logistics cost, which is an important means to improve the competitiveness of enterprises. On the basis of discussing and summarizing the basic model and derivative model of vehicle routing problem, and summarizing all kinds of algorithms to solve this kind of problem, this paper makes a thorough investigation on the actual situation of logistics and transportation operation in China. Due to the particularity of the financing construction of expressway system in China, the pricing and charging methods of domestic expressway charges are different from those of developed countries. The traditional vehicle routing problem model can no longer meet the actual demand of logistics planning in China. Based on the study of the cost calculation method in the actual logistics transportation in China, and considering the particularity of the pricing and charging method of the expressway system in China, An accumulative vehicle routing problem with time window constraints is proposed, which aims at reducing the transportation cost of vehicles in actual transportation in China. The target cost of this problem is also related to the distance and flow on the transportation route, which is in line with the current situation of logistics and transportation operation in China. In view of the complexity of the new cost measurement method, this paper designs a new Tabu search algorithm structure to solve it effectively: (1) intersecting search between embedded paths in the algorithm; There are three neighborhood search methods in the feasible solution path and the infeasible path neighborhood search method, which form a set of systematic search schemes, and allow the neighborhood search in the feasible and infeasible solution space at the same time. (2) low complexity computation method of neighborhood solution transportation cost based on preprocessing and iteration is proposed, and the time window violation calculation method proposed by Nagata is used to evaluate the time window constraint violation of the solution. The calculation time is greatly reduced. On the basis of experiments on the related parameters of the algorithm, a large number of numerical examples are carried out in this paper. The numerical test of the new problem not only proves the time saving and effectiveness of the Nagata time window violation calculation method compared with the traditional method, but also covers many kinds of vehicle routing problems that have been studied. The calculation of the practical problems not only verifies the overall coverage and correctness of the model, but also reflects the efficiency and time saving of the algorithm in this paper. The purpose of this paper is to provide relevant decision support for the actual logistics and transportation operation in China, and hope that the relevant research methods can be applied to practice and enrich the relevant theoretical system of the vehicle routing problem. It provides a new direction for the future study of related neighborhood.
【学位授予单位】：上海交通大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：F259.2;F252
本文编号：2282475
[Abstract]:With the rapid development of modern economy and the rapid progress of science and technology, logistics industry, as an important service pillar industry of national economy, is developing rapidly all over the world. Using scientific methods to guide and optimize the transportation operation process can effectively reduce the cost of logistics distribution and then reduce the total logistics cost, which is an important means to improve the competitiveness of enterprises. On the basis of discussing and summarizing the basic model and derivative model of vehicle routing problem, and summarizing all kinds of algorithms to solve this kind of problem, this paper makes a thorough investigation on the actual situation of logistics and transportation operation in China. Due to the particularity of the financing construction of expressway system in China, the pricing and charging methods of domestic expressway charges are different from those of developed countries. The traditional vehicle routing problem model can no longer meet the actual demand of logistics planning in China. Based on the study of the cost calculation method in the actual logistics transportation in China, and considering the particularity of the pricing and charging method of the expressway system in China, An accumulative vehicle routing problem with time window constraints is proposed, which aims at reducing the transportation cost of vehicles in actual transportation in China. The target cost of this problem is also related to the distance and flow on the transportation route, which is in line with the current situation of logistics and transportation operation in China. In view of the complexity of the new cost measurement method, this paper designs a new Tabu search algorithm structure to solve it effectively: (1) intersecting search between embedded paths in the algorithm; There are three neighborhood search methods in the feasible solution path and the infeasible path neighborhood search method, which form a set of systematic search schemes, and allow the neighborhood search in the feasible and infeasible solution space at the same time. (2) low complexity computation method of neighborhood solution transportation cost based on preprocessing and iteration is proposed, and the time window violation calculation method proposed by Nagata is used to evaluate the time window constraint violation of the solution. The calculation time is greatly reduced. On the basis of experiments on the related parameters of the algorithm, a large number of numerical examples are carried out in this paper. The numerical test of the new problem not only proves the time saving and effectiveness of the Nagata time window violation calculation method compared with the traditional method, but also covers many kinds of vehicle routing problems that have been studied. The calculation of the practical problems not only verifies the overall coverage and correctness of the model, but also reflects the efficiency and time saving of the algorithm in this paper. The purpose of this paper is to provide relevant decision support for the actual logistics and transportation operation in China, and hope that the relevant research methods can be applied to practice and enrich the relevant theoretical system of the vehicle routing problem. It provides a new direction for the future study of related neighborhood.
【学位授予单位】：上海交通大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：F259.2;F252
【参考文献】
相关期刊论文 前2条
1 祝崇隽,刘民,吴澄,吴晓冰;针对模糊需求的VRP的两种2-OPT算法[J];电子学报;2001年08期
2 李宁,邹彤,孙德宝;带时间窗车辆路径问题的粒子群算法[J];系统工程理论与实践;2004年04期
相关硕士学位论文 前1条
1 董燕菊;时间约束下的物流配送路线优化研究[D];首都经济贸易大学;2011年
，本文编号：2282475
本文链接：https://www.wllwen.com/guanlilunwen/wuliuguanlilunwen/2282475.html
