Greedy Random Abstract
Capacitated Vehicle Routing with Time Windows (CVRTW) is the routing of vehicles that each carry a specific capacity of product to different customers with varying availabilities (time windows) and varying demanded amounts of product. CVRTW is a NP-Hard problem and is especially difficult since the number of possible solutions grows exponentially with the size of the problem. By taking into account capacity and time windows, CVRTW generates solutions that have real-life applications.
This study creates and analyzes a novel technique for optimizing CVRTW. This new approach created and programmed ten artificial intelligence algorithms in C++. Each algorithm independently drove a generic CVRTW engine. An initial experiment compared them against each other on a set of standardized benchmarks. One algorithm, Greedy Random (GR), emerged with the best performance, significantly better than the other nine at p = 0.025.
Four more experiments elucidated the reasons for GR's performance. Each experiment tested a hypothesis about GR’s performance by programming new variants of GR and comparing them on a set of standardized benchmarks.
Analysis of the experimental results found that GR derived its performance from its use of a single catalytic initial random move to modify and reoptimize the solution, allowing it to escape from a non-optimal local minimum and approach the optimal solution. GR provides a high level of portability because it is separate from an optimization engine. It is the first successful problem-independent optimization algorithm. Thus, industry can apply GR to other areas of optimization such as manufacturing planning and chip layout.