论文标题
随机鲤鱼的双目标随机方法
A bi-objective stochastic approach for the stochastic CARP
论文作者
论文摘要
电容弧路由问题（CARP）发生在城市废物收集或冬季磨损等应用中。通常在无向图上的文献中定义它，并带有一组节点和一组边缘。同一能力车辆的车队基于一个仓位节点。每个边缘都有成本（长度）和需求（例如浪费量），并且可能会遍历多次。具有非零要求或任务的边缘需要车辆服务。目标是确定一组最低总成本的车辆旅行（路线），以便每次旅行在仓库开始和结束，每次任务都通过一次旅行服务，任何车辆处理的总需求都不会超过。据我们所知，最佳发表的方法是2001年首次推出的模因算法。本文提供了NSGA II（非主导分类遗传算法）模板的新扩展，以符合鲤鱼的随机视图。主要贡献是： - 引入数学表达来评估最长行程的成本和持续时间以及这两个标准的标准偏差。 - 使用NGA-II模板同时优化最长行程的成本和持续时间，包括标准偏差。在TEE众所周知的Dearmon，Belenguer和Benavent和Eglese的基准集上进行了数值实验，证明可以在相当短的计算时间中同时获得四个同时的标准，在相当短的计算时间中获得强大的解决方案。
The Capacitated Arc Routing Problem (CARP) occurs in applications like urban waste collection or winter gritting. It is usually defined in literature on an undirected graph , with a set of nodes and a set of edges. A fleet of identical vehicles of capacity is based at a depot node. Each edge has a cost (length) and a demand (e.g. an amount of waste), and it may be traversed any number of times. The edges with non-zero demands or tasks require service by a vehicle. The goal is to determine a set of vehicle trips (routes) of minimum total cost, such that each trip starts and ends at the depot, each task is serviced by one single trip, and the total demand handled by any vehicle does not exceed . To the best of our knowledge the best published method is a memetic algorithm first introduced in 2001. This article provides a new extension of the NSGA II (Non-dominated Sorting Genetic Algorithm) template to comply with the stochastic sight of the CARP. The main contribution is: - to introduce mathematical expression to evaluate both cost and duration of the longest trip and also standard deviation of these two criteria. - to use a NGA-II template to optimize simultaneously the cost and the duration of the longest trip including standard deviation. The numerical experiments managed on the thee well-known benchmark sets of DeArmon, Belenguer and Benavent and Eglese, prove it is possible to obtain robust solutions in four simultaneous criteria in rather short computation times.
