Nature of real-world multi-objective vehicle routing with evolutionary algorithms
Nature of real-world multi-objective vehicle routing with evolutionary algorithms
复制标题
DOI：
10.1109/icsmc.2011.6083675
复制
发表时间：
2011-11
期刊：
影响因子：
--
通讯作者：
J. Gutiérrez;Dario Landa Silva;J. Moreno-Pérez
中科院分区：
文献类型：
--
作者：
J. Gutiérrez;Dario Landa Silva;J. Moreno-Pérez
带时间窗的车辆路径问题（VRPTW）是一个重要的物流问题，在现实世界中表现为多目标。这一领域的大多数研究都是使用为单目标情况设计的经典数据集进行的，如著名的所罗门问题实例。在多目标情况下使用这些数据集时，通常会做出一些不切实际的假设（例如，假设一个单位的行驶时间对应于一个单位的行驶距离）。此外，有没有共同的VRPTW多目标导向的框架来比较算法的性能，因为在文献中的不同实现解决不同的目标集。在这项工作中，我们调查的冲突（或不）的性质，各种目标的VRPTW，并表明，一些经典的测试实例是不适合进行适当的多目标研究。这项研究的见解使我们使用来自真实世界分销公司的数据生成一些问题实例。使用标准进化算法（NSGA-II）在这些新数据集上的实验显示出更强的多目标特征证据。我们的贡献集中在实现更好地了解VRPTW的多目标性质，特别是5个目标之间的冲突关系：车辆数量，总行程距离，最大完工时间，总等待时间，总延误时间。
The Vehicle Routing Problem with Time Windows (VRPTW) is an important logistics problem which in the real-world appears to be multi-objective. Most research in this area has been carried out using classic datasets designed for the single-objective case, like the well-known Solomon's problem instances. Some unrealistic assumptions are usually made when using these datasets in the multi-objective case (e.g. assuming that one unit of travel time corresponds to one unit of travel distance). Additionally, there is no common VRPTW multi-objective oriented framework to compare the performance of algorithms because different implementations in the literature tackle different sets of objectives. In this work, we investigate the conflicting (or not) nature of various objectives in the VRPTW and show that some of the classic test instances are not suitable for conducting a proper multi-objective study. The insights of this study have led us to generate some problem instances using data from a real-world distribution company. Experiments in these new dataset using a standard evolutionary algorithm (NSGA-II) show stronger evidence of multi-objective features. Our contribution focuses on achieving a better understanding about the multi-objective nature of the VRPTW, in particular the conflicting relationships between 5 objectives: number of vehicles, total travel distance, makespan, total waiting time, and total delay time.