不确定因素下车辆路径问题建模及优化方法研究

发布时间：2020-09-03 07:31

　　车辆路径问题(Vehicle Routing Problem,VRP)作为物流运输研究的一个重要问题,在现实中具有广泛的应用基础。人类需求的日益多样化和现实世界存在的大量不确定因素,都加大了车辆调度管理的难度。尽管不确定因素下的VRP问题已有了一系列研究成果,但缺乏探讨车辆配送中的动态管理策略和处理异常信息的快速反应机制。本文重点研究了不确定因素下VRP的建模和优化方法,主要研究内容和创新性工作如下: 针对标准的带时间窗VRP的多目标数学模型,研究了三种基于混合搜索策略的启发式算法。离散差分进化混合算法采用线性加权的方法来处理多目标模型,并发展了新的变异和交叉算子,对精英个体运用局部禁忌搜索以提高算法的寻优能力。提出了一种构造多样性初始解的随机车辆配载方法,以及插入可行邻域和2-Opt可行邻域两种搜索可行解的邻域结构。文化基因算法和多目标文化基因算法分别采用线性加权法和Pareto方法来处理多目标模型,种群搜索采用遗传算法,局部搜索采用禁忌搜索。仿真对比实验验证了三种算法的有效性。针对具有模糊需求量的VRP,提出了一种动态管理方法。采取一种事前预测的策略,在初始计划执行中实时进行动态调整。设计了一种嵌入模糊模拟的NSGA-Ⅱ混合算法,分析了决策者主观偏好值对决策目标的影响,然后与传统车辆调度方法进行了对比分析,验证了本文提出的动态管理策略的有效性。针对具有模糊预约时间的VRP,应用模糊事件给出了车队服务满意度的一个新的度量方法和求最大满意度的计算方法。进而提出了一种基于Pareto优化的多目标禁忌搜索算法,通过与NSGA-Ⅱ算法进行仿真对比实验,证明了多目标禁忌搜索算法是求解多目标组合优化问题的一种有效的方法。考虑顾客的主观偏好影响,研究了模糊时间窗VRP的集成优化方法。在多目标禁忌搜索算法中嵌入优化顾客满意度的动态规划方法,来求解以物流配送成本和顾客平均满意度为目标的模型。对模糊时间窗为线性分段函数形式和非线性凹函数形式的隶属度函数,分别提出了有限枚举算法和次梯度二分迭代算法来优化顾客的最优开始服务时间。进一步,研究了带随机时间和模糊时间窗的VRP。为了处理随机因素,提出了预先安排车辆行驶计划,然后在车辆行驶过程中根据时间调度规则随时调整开始服务时间的策略,动态优化顾客的满意度水平。对带时间窗的动态VRP进行了研究,提出了一种新的紧急顾客插入和分批驱动调度策略,该策略只需实时插入紧急顾客。与新顾客插入后的重复优化策略和批处理策略进行了对比,并分析了分批优化间隔长度对调度性能的影响。
【学位单位】：天津大学
【学位级别】：博士
【学位年份】：2012
【中图分类】：F224;F252
【部分图文】：

示意图,指标,最优解,公式计算

如果最优解在 Par；如果大多数解都集中在的解的数量较少，那么表明公式计算： 2111BiiS d dB 1 1 2minji j x Bf x f x f i 。该指标取值越小，表明指标包括 S-metric、Error可以参考 Knowles 和 Co

操作示意图,顾客,多目标准则,车辆路径问题

第二章多目标准则下的带时间窗车辆路径问题把移除的顾客点依次按照最优目标值法插入到染色体 P1’和 P2’中。以 P1’’为例，根据插入可行邻域查找顾客 1 的可行插入点，然后比较在各个位置插入顾客1 后的目标函数值（即适应度），选择最优位置插入。依次类推，依次插入 98，得到最终的子染色体 C1。同样 P2’插入 3175 后得到 C2。3 1 7 5 0 2 4 6 0 8 9 0 6 7 3 0 2 4 5 0 1 9 8 0

示意图,调机,种群,存储池

图 2-9 精英解的存储和协调机制示意图算法是基于种群的全局搜索和基于个体的局部搜索的结是如何协调种群搜索和局部搜索得到的 Pareto 非占优解的示，对父代种群经过交叉操作得到的每个新个体进行局部最优解作为子代的个体。采用一个容量足够大的存储池结的 Pareto 非占优解。比较存储池中的解集，如果在局部搜areto 非占优解，那么就用其更新存储池中的一个劣解。局种群、子代种群和存储池中的所有解采用基于 Pareto 排序Deb 等(2002)[183]）进行选择操作，得到新的父代种群，然程。度函数群搜索和局部搜索的机制不同，所以在同时考虑个体的两种不同的适应度函数，分别应用于对种群的选择操作和对

【参考文献】