物流配送TSP问题的研究

发布时间：2018-04-12 19:42

本文选题：TSP问题 + 遗传算法　；参考：《哈尔滨工业大学》2017年硕士论文

【摘要】：2016年,斯坦福大学价值链创新倡议研究中心与美国邮政服务局督察长办公室联合发布了《最后一英里快递技术颠覆与创新白皮书》。白皮书中指出,四项新型的技术可能支撑物流行业带来新的发展,即优化商品配送流程的高级算法,参与配送系统的无人机技术,参与机械分拣的机器人技术,以及把人工从物流系统中解放出来的无人驾驶汽车技术。本文即针对优化商品配送流程的高级算法,基于GA算法,结合实际解决配送过程中的TSP问题。物流行业中,物流的成本的问题一直是最重要的问题之一,过高的物流成本也是限制其行业发展的最大问题之一。要有效减少运输成本与配送成本,可以进行配送渠道的优化,配送人员的优化,配送效率的提高等等方面来进行。其中最容易实现的,不需要高成本的就是配送车辆的运输线路的优化。由此,本文建立了基于实际配送问题中的TSP问题的配送路径优化模型,并通过用改进的遗传算法结合该实际问题来解决。本文利用遗传算法解决实际配送过程中带有限制条件的多目标TSP问题,并针对实际问题提出改良算法与解决方案,保证可实现最优解的前提下提高算法效率与收敛速度。论文主要研究内容如下:1.对TSP问题与遗传算法进行研究。研究遗传算法与TSP问题的历史和研究现状,介绍TSP问题的数学模型和遗传算法的基本算例,对遗传算法和改进的遗传算法进行一定的归纳和分析,为后续工作提供前提条件。以遗传算法理论为基础建模并完成课题工作。2.建立基于路径长度和时间为目标的多目标实际配送TSP问题数学模型,并实现实际物流配送问题的求取,得到最优路径。研究实际道路路径的实现方案,解决实际道路地图中道路路径与消耗时间的建模,在遍历道路和小区内不同路段时,车辆具有不同速度。在多目标TSP问题上,加入容积的限定,当容积到达阈值时返回,即容积限定的车辆TSP问题,在该限制条件下做出相应解决方案并实现最优路径的计算。仿真红绿灯等待,路况拥堵等可变因素,两点间的时间结合实际问题计算得出。同时保证算法不进行过多计算,保证算法的效率和收敛性。在仿真中根据实际应用计算中出现的问题进行算法的改进,保证仿真路径和仿真时间与真实路径真实时间的贴合,减小误差。3.结合实际问题进行算法的改进。解决跨道路间难于通过变异得到最优序列的问题,研究适应于实际配送问题的适应度函数与选择算子,在实际问题中更优质地产生子代,同时更高效地选择出优秀子代。研究适用于城区道路的初始路径解,提高基于道路路径的初始解的质量。研究适用于实际配送中的编码方案,在订单,路径,区域,目标等多个信息中确定最优的编码方案。本文提出了实际配送过程中的TSP问题解决方案,本文最终完成程序的编写并进行了仿真,验证了文中方法的可行性和实际效果,相对于无序的随机配送和传统的分区块配送方法,在配送时间和配送总路径上有一个较大的提升。
[Abstract]:In 2016, the Stanford University value chain innovation initiative research center and the U.S. Postal Service Inspector General Office jointly issued the "last mile delivery technology of subversion and innovation. The white paper pointed out in the white paper, four new technology may bring new development support of logistics industry, namely commodity distribution process optimization advanced algorithm, UAV technology in distribution system the participation of mechanical sorting robot technology, artificial and liberated from the logistics system of unmanned vehicle technology. In this paper, advanced algorithm optimization of commodity distribution process, based on the GA algorithm, to solve the TSP problem in the process of delivery. Combined with the actual logistics industry, the logistics cost is always one of the most important one of the biggest problems, the high cost of logistics is also limit the development of the industry. In order to effectively reduce the cost of transportation and distribution costs, can Optimization of distribution channels, optimize the distribution of personnel, improve the efficiency of distribution and so on. The most easy to realize the optimization of transport routes do not need high cost is the delivery vehicle. Thus, this paper establishes a model of routing optimization problem of TSP based on the actual distribution problems, and by combining the actual the problem with improved genetic algorithm to solve the multi-objective problem. TSP constraint based genetic algorithm to solve the actual distribution process, and puts forward the improved algorithm and the solution to the practical problems, which improve the efficiency of the algorithm and the convergence speed of the premise can realize the optimal solution. The main contents of this thesis are as follows: 1. the TSP problem and the genetic algorithm are studied. Research history and research status of genetic algorithm and TSP problem, introduces the mathematical model of TSP problem and genetic algorithm the basic example of genetic The genetic algorithm and the improved algorithm are summarized and analyzed, to provide a prerequisite for subsequent work. The genetic algorithm is based on the theory of modeling and complete the project work.2. a multi-objective mathematical model of the actual distribution of the TSP problem of path length and time based on the target, and realize the actual logistics distribution problem is obtained, the optimal path study on the practical realization scheme of the road path, road road map modeling to solve actual path and time consuming, in the area of different sections and traverse roads, vehicles with different speed. In the multi-objective TSP problem, adding volume limit, return when the volume reached the threshold, i.e. vehicle TSP problem limited volume and make the corresponding solutions in the restricted conditions and realize the calculation of the optimal path. The simulation of traffic lights for traffic congestion and other variable factors, between the two time combined with practical problems The calculated. At the same time to ensure the algorithm without too much calculation, to ensure the efficiency of the algorithm and the convergence of the algorithm. The improvement in the simulation according to the practical application problems in calculation, guarantee the simulation path and the simulation time and the true path of real time fitting algorithm is improved to reduce the error of.3. combined with the practical problems. To solve the cross it is difficult to get through the road between the variation of the optimal sequence problem, fitness function and selection operator adapted to the actual distribution problems in practical problems, more high-quality real estate and more efficient offspring, select excellent offspring. The initial path suitable for urban road solutions, improve the quality of the initial solution path based on the encoding scheme, which is suitable for the actual distribution in the study area, in order to determine the path encoding scheme of optimal target and other information in the actual distribution is put forward in this paper. The solution to the TSP problem in the process, the final completion of the program and the simulation verifies the feasibility of the method and the actual results, compared with the random distribution and disorder of the traditional block distribution method, there is a larger increase in the delivery time and delivery route.

【学位授予单位】：哈尔滨工业大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：F252;TP18

【参考文献】