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

带时间窗快递车辆路径问题模型及算法研究随着电子商务的飞速崛起,快递企业如何合理安排运输车辆以降低运输成本成为一个迫切需要解决的问题。快递车辆路径问题是经典的车辆路径问题(VehicleRoutingProblem,VRP)的变种,也是一个NP难问题。
因此,快速的启发式求解算法及解好坏的评估是研究中的难点和关键。该问题的研究及应用,可以显著地降低快递行业的运输成本,同时也减少车辆的二氧化碳排放量,对经济和环境产生积极影响。
给定分拨中心的网络结构及其服务时间窗口约束和各个分拨中心之间的货物流量结构及其时效约束的快递车辆路径规划,是实际中最为常见的一类问题。本文主要研究了带时间窗的快递车辆路径问题的建模及求解,具体工作包括以下两项内容：1.固定时间窗快递车辆路径问题建模及求解固定时间窗快递车辆路径问题就是研究在收件时间窗和派件时间窗固定的情况下,如何安排班车路由使得班车花费的总成本最小。
本文首先建立了此问题的数学模型,然后设计了基于贪心启发式方法的快速求解算法,并提出了一种新的班车安排方法：环线班车+单边车,以此代替原有的效果较差的对称班车安排方法,最后还给出了评估该问题解的一个下界模型。通过在不同规模的真实数据集上进行计算实验,将提出算法的求解结果与下界模型得到的下界进行比较,从而表明了求解算法的精确程度。
还将两种班车安排方法得到的结果进行对比,说明了本文提出的新班车安排方法优于原有班车安排方法。此外,对于9城市数据和21城市数据,求解算法总的计算时间分别为1秒和54秒。
2.可变时间窗快递车辆路径问题建模及求解通过分析发现时间窗对于班车运输成本影响较大,为此需要将时间窗作为可变参数纳入到模型中,我们将该问题称之为可变时间窗快递车辆路径问题。本文在固定时间窗问题的基础上,采用环线班车+单边车的班车安排方法,建立了该问题的数学模型。
为了评价算法求解结果的优劣,对该问题建立了时间约束松弛的下界模型并加以证明,再采用Lingo软件求出其一个下界。最后,设计了一种两阶段的求解算法,该算法包括时间窗求解和固定时间窗问题求解两个阶段,并且在时间窗求解阶段设计了时间窗口好坏的一个评价函数。
在9城市数据集和21城市数据集上分别进行了求解,计算结果表明,时间窗口的好坏对最终班车安排花费有较大的影响,一组良好的时间窗口安排可以有效的降低班车运输成本。