Published on Wed Apr 14 2021

A Novel Generalised Meta-Heuristic Framework for Dynamic Capacitated Arc Routing Problems

Hao Tong, Leandro L. Minku, Stefan Menzel, Bernhard Sendhoff, Xin Yao
0
0
0
Abstract

The capacitated arc routing problem (CARP) is a challenging combinatorial optimisation problem abstracted from typical real-world applications, like waste collection and mail delivery. However, few studies considered dynamic changes during the vehicles' service, which can make the original schedule infeasible or obsolete. The few existing studies are limited by dynamic scenarios that can suffer single types of dynamic events, and by algorithms that rely on special operators or representations, being unable to benefit from the wealth of contributions provided by the static CARP literature. Here, we provide the first mathematical formulation for dynamic CARP (DCARP) and design a simulation system to execute the CARP solutions and generate DCARP instances with several common dynamic events. We then propose a novel framework able to generalise all existing static CARP optimisation algorithms so that they can cope with DCARP instances. The framework has the option to enhance optimisation performance for DCARP instances based on a restart strategy that makes no use of past history, and a sequence transfer strategy that benefits from past optimisation experience. Empirical studies are conducted on a wide range of DCARP instances. The results highlight the need for tackling dynamic changes and show that the proposed framework significantly improves over existing algorithms.

Thu May 28 2020
Neural Networks
Towards Decision Support in Dynamic Bi-Objective Vehicle Routing
We consider a dynamic bi-objective vehicle routing problem. Therein, the distance traveled by a single vehicle and the number of unserved dynamic requests is minimized. A decision is made at each era by a decision-maker, thus any decision depends on irreversible decisions made in foregoing eras.
0
0
0
Sat Apr 25 2020
Neural Networks
The Dynamic Travelling Thief Problem: Benchmarks and Performance of Evolutionary Algorithms
Many real-world optimisation problems involve dynamic and stochastic components. Most research on dynamic problems focuses on single- component problems. We define a number of scenarios based on the Travelling Thief Problem.
0
0
0
Thu May 28 2020
Neural Networks
Dynamic Bi-Objective Routing of Multiple Vehicles
Vehicle-Routing-Problems (VRPs) often imply repeated decision making on dynamic customer requests. We adopt a recently proposed Dynamic Evolutionary Multi-Objective Algorithm for a related VRP problem and extend it to the more realistic scenario of multiple vehicles. We empirically show
0
0
0
Thu Apr 06 2017
Neural Networks
Tackling Dynamic Vehicle Routing Problem with Time Windows by means of Ant Colony System
The Dynamic Vehicle Routing Problem with Time Windows (DVRPTW) is an extension of the well-known Vehicle Routed Problem (VRP) DVRPTw takes into account the dynamic nature of the problem. The experiments indicate that the proposedgorithm is competitive and effective.
0
0
0
Fri Feb 07 2020
Neural Networks
Dynamic Multi-objective Optimization of the Travelling Thief Problem
0
0
0
Tue Dec 31 2019
Artificial Intelligence
C. H. Robinson Uses Heuristics to Solve Rich Vehicle Routing Problems
We consider a wide family of vehicle routing problem variants. The proposed algorithms have outperformed the existing technologies at CHR on 10 benchmark instances.
0
0
0