带时间窗快递车辆路径问题模型及算法研究

发布时间：2019-01-11 18:19

【摘要】：随着电子商务的飞速崛起,快递企业如何合理安排运输车辆以降低运输成本成为一个迫切需要解决的问题。快递车辆路径问题是经典的车辆路径问题(Vehicle Routing Problem, VRP)的变种,也是一个NP难问题。因此,快速的启发式求解算法及解好坏的评估是研究中的难点和关键。该问题的研究及应用,可以显著地降低快递行业的运输成本,同时也减少车辆的二氧化碳排放量,对经济和环境产生积极影响。给定分拨中心的网络结构及其服务时间窗口约束和各个分拨中心之间的货物流量结构及其时效约束的快递车辆路径规划,是实际中最为常见的一类问题。本文主要研究了带时间窗的快递车辆路径问题的建模及求解,具体工作包括以下两项内容：1.固定时间窗快递车辆路径问题建模及求解固定时间窗快递车辆路径问题就是研究在收件时间窗和派件时间窗固定的情况下,如何安排班车路由使得班车花费的总成本最小。本文首先建立了此问题的数学模型,然后设计了基于贪心启发式方法的快速求解算法,并提出了一种新的班车安排方法：环线班车+单边车,以此代替原有的效果较差的对称班车安排方法,最后还给出了评估该问题解的一个下界模型。通过在不同规模的真实数据集上进行计算实验,将提出算法的求解结果与下界模型得到的下界进行比较,从而表明了求解算法的精确程度。还将两种班车安排方法得到的结果进行对比,说明了本文提出的新班车安排方法优于原有班车安排方法。此外,对于9城市数据和21城市数据,求解算法总的计算时间分别为1秒和54秒。2.可变时间窗快递车辆路径问题建模及求解通过分析发现时间窗对于班车运输成本影响较大,为此需要将时间窗作为可变参数纳入到模型中,我们将该问题称之为可变时间窗快递车辆路径问题。本文在固定时间窗问题的基础上,采用环线班车+单边车的班车安排方法,建立了该问题的数学模型。为了评价算法求解结果的优劣,对该问题建立了时间约束松弛的下界模型并加以证明,再采用Lingo软件求出其一个下界。最后,设计了一种两阶段的求解算法,该算法包括时间窗求解和固定时间窗问题求解两个阶段,并且在时间窗求解阶段设计了时间窗口好坏的一个评价函数。在9城市数据集和21城市数据集上分别进行了求解,计算结果表明,时间窗口的好坏对最终班车安排花费有较大的影响,一组良好的时间窗口安排可以有效的降低班车运输成本。
[Abstract]:With the rapid rise of electronic commerce, how to arrange the transportation vehicle reasonably to reduce the transportation cost becomes an urgent problem to be solved by express delivery enterprises. Express vehicle routing problem is a variant of the classic vehicle routing problem (Vehicle Routing Problem, VRP), and is also a difficult NP problem. Therefore, the fast heuristic algorithm and the evaluation of the solution are the difficulties and key points in the research. The research and application of this problem can significantly reduce the transport cost of the express delivery industry, but also reduce the carbon dioxide emissions of vehicles, and have a positive impact on the economy and the environment. It is the most common problem in practice that the network structure of the distribution center and its service time window constraints, the cargo flow structure between the distribution centers and its time-limited express vehicle routing planning are the most common problems in practice. This paper mainly studies the modeling and solution of express vehicle routing problem with time window. The specific work includes the following two parts: 1. Modeling and solving the fixed time window Express vehicle routing problem is to study how to arrange the routing of the shuttle bus to minimize the total cost of the shuttle bus when the pickup time window and the distribution time window are fixed. This paper first establishes the mathematical model of the problem, then designs a fast solution algorithm based on greedy heuristic method, and proposes a new method of arranging the bus: the one-sided car of the loop line bus. A lower bound model for evaluating the solution of the problem is given. Through the calculation experiments on real data sets of different scales, the results of the proposed algorithm are compared with the lower bound obtained by the lower bound model, which shows the accuracy of the algorithm. The results obtained from the two methods are compared and the results show that the new method is superior to the original one. In addition, for 9 city data and 21 city data, the total computation time of the algorithm is 1 second and 54. 2 seconds, respectively. Modeling and solving of variable time window Express vehicle routing problem through analysis, it is found that time window has a great influence on the transportation cost of shuttle bus, so it is necessary to incorporate time window into the model as a variable parameter. We call this problem a variable time window express vehicle routing problem. On the basis of the fixed time window problem, the mathematical model of the problem is established by using the method of arranging the single side car of the circular line bus. In order to evaluate the advantages and disadvantages of the algorithm, a lower bound model of time-constrained relaxation is established and proved, and a lower bound is obtained by using Lingo software. Finally, a two-stage algorithm is designed. The algorithm consists of two stages: time window solution and fixed time window solution, and an evaluation function of time window is designed in the time window solution phase. The results on 9 city data sets and 21 city data sets show that the time window has a great influence on the cost of the final schedule. A good time window arrangement can effectively reduce the transportation costs.
【学位授予单位】：中国科学技术大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP301.6

【相似文献】