有时间窗车辆路径问题指的是什么意思（什么是有时间窗车辆路径问题)

有时间窗车辆路径问题指的是什么意思（什么是有时间窗车辆路径问题)

你真的知道有时间窗车辆路径问题吗？你知道多少？以下是爱68为您整理有时间窗车辆路径问题的相关知识，让您更深入地了解什么是有时间窗车辆路径问题。那么，在公路运输行业，有时间窗车辆路径问题代表什么呢？让我们一起看看。

有时路径有时间问题（vehicle routing problems with time windows，VRPTW）

车辆路线问题（VRP）最早是由Dantzig和Ramser1959年首次提出，是指一定数量的客户，各有不同数量的货物需求，配送中心向客户提供货物，由团队负责配送货物，组织适当的驾驶路线，目标是满足客户的需求，在一定的限制下，如最短的距离、最低的成本、最少的时间等。

成本函数还包括早到客户所需的等待时间和服务时间。成本函数还要包括由于早到某个客户而引起的等待时间和客户需要的服务时间。

在VRPTW除了满意之外，车辆还需要满意VRP除了问题的限制外，还必须满足需求点的时窗限制，需求点的时窗限制可分为两种，一种是硬时窗（Hard Time Window），硬时窗要求车辆在时窗内到达，早到时等待，迟到时拒绝；另一种是软时窗（Soft Time Window），窗户不一定要到，但在时窗外到达时，必须进行处罚，而不是等待和拒绝是软时窗和硬时窗之间最大的区别。

Bodin和Solomon分别对VRP及其变形问题和VRPTW详细总结了问题。实际生产中的许多问题可以归结为VRPTW例如，钢铁厂制定热轧带钢轧制计划的问题实际上是一个问题VRPTW问题。邮政投递、飞机、火车、公共汽车调度等一些服务行业也存在这样的问题。Savelsbergh证明了VRPTW是一个NP难题之后，对其算法的研究主要集中在各种启发式算法上。智能启发式算法的出现，如遗传算法、禁忌搜索法和模拟退火法，以求解VRPTW问题提供了新的工具。Thangiah和Joe都用遗传算法求解VRPTW问题是，前者的目标是降低总服务成本，而后者有两个目标，一是使用最少的车辆，二是在使用最少车辆的前提下降低总成本。

含时窗限制车辆行程问题（VRPTW）相对于车辆相比（VRP），运输时间和时间窗口必须额外考虑。主要原因是客户有服务时间的最后期限和最早开始服务时间的限制。因此，在这种限制下，最初VRP除了空间的路径（Routing）除了考虑，还必须在时间上添加排程（Sche***ng）考虑，同时，由于场地站也有时间窗的限制，也间接造成了路径长度的限制，可见VRPTW总巡逻成本不仅包括运输成本，还包括时间成本和未在时间窗口限制内交付的处罚成本。因此，如果你想得到一个好的答案，时间和空间（Temporal andSpatial）问题的探讨是非常重要的。

由于VRPTW比VRP问题多考虑同一时窗的因素，所以在解决方案上比较VRP问题更复杂，根据Taillard(1997)等人的分类，求解VRPTW可分为六种方法，分述如下。

1.精确解决分枝界限法（Exact Algorithm Based on Branch-and-BoundTechniques）：Kolen(1987)这样才能得到准确的解决，但只能解决六到十五个节点的问题，所以解决的范围太小，只适用于小问题。

2.途程建构启发式算法（Route Construction Heuristics）：在一个问题中，需求点以节点选择原则或路线安排原则逐一纳入途程路线。Soloman(1987)循序建构法（Sequential Insertion Heuristics）。

3.途程改进启发式算法（Route Improvement Heuristics）：首先决定一个可行的旅程，即一个起始解，然后改进起始解，直到无法改进。常见的是节线交换方法（Edge Exchange Procedure），如Lin(1965)提出K-Optimal，以及Potvin与Rousseau(1993)提出了考虑旅行方向的交换算法。

4.合成启发式算法（Composite Heuristics）：该解决方案将途程构建启发算法与途程改进启发算法相结合Russell(1995)提出Hybrid Heuristics便是混合了Potvin与Rousseau(1993)提出的平行插入法，并加入路线改进法的合成启发算法；Roberto(2000)也提出了平行插入法和内部交换改进法的合成启发性解决方案VRPTW的问题。

5.根据最佳启发式算法（Optimization-Based Heuristics）：如Koskosidis（1992）等人利用混合整数规划模块，再透过启发式算法，将原始问题分解成指派/分群的子问题的一系列的巡行以及排程问题。

6.通用启发算法（Metaheuristics）：能有效解决局部最佳化问题。Potvin（1996）等人、Taillard(1997)人均利用Tabu Search的方式来求解VRPTW的问题。可以有效解决局部最佳化的困扰。如Potvin（1996）等人、Taillard（1997）等人均利用Tabu Search的方式来求解VRPTW的问题。

有时间窗车辆路径问题指的是什么意思（什么是有时间窗车辆路径问题)

有时间窗车辆路径问题指的是什么意思（什么是有时间窗车辆路径问题)发表于2023-03-20，由周林编辑，文章《有时间窗车辆路径问题指的是什么意思（什么是有时间窗车辆路径问题)》由admin于2023年03月20日发布于本网，共3172个字，共5701人围观，目录为公路运输，如果您还要了解相关内容敬请点击下方标签，便可快捷查找与文章《有时间窗车辆路径问题指的是什么意思（什么是有时间窗车辆路径问题)》相关的内容。

版权声明：

文章:(有时间窗车辆路径问题指的是什么意思（什么是有时间窗车辆路径问题))，来源：，阅读原文。

有时间窗车辆路径问题指的是什么意思（什么是有时间窗车辆路径问题)若有[原创]标注，均为本站原创文章，任何内容仅供学习参考，未经允许不得转载，任何内容不得引用，文章若为转载文章，请注明作者来源，本站仅为分享知识，不参与商业活动，若有侵权请联系管理删除