Solution Methods
The Vehicle Routing Scheduler Library currently contains the following 16 optimizing schedulers for vehicle routing problem:
- Clark & Wright Saving Algorithm: A constructive algorithm published by Clark & Wright that often yield a relatively good solution which deviates little from the optimal solution.
- Random Constructive Algorithm: A simple heuristic to create feasible vehicle routes from a randomly generated integer permutation.
- Sweeping Algorithm: A constructive algorithm which generates vehicle routes by sweeping clockwise or anti-clockwise a line centred at the depot and collecting the swept customers into routes sequentially.
- Single Route Improvement: A sequential two-step optimizer that combines a constructive algorithm (for initial solution) with a single route-based refinement algorithm or local search algorithm (for solution improvement).
- Multi Route Improvement: Same as Single Route Improvement heuristic except that the refinement local search is based on inter-route edge exchange.
- Hybrid Route Improvement: Same as Single Route Improvement heuristic except that the refinement local search is a hybrid combining both single route and inter-route edge exchange methods.
- GVR-based Canonical Memetic Algorithm (MA): Canonical memetic algorithm in which the solution has a multi-route graph-based solution representation similar to genetic vehicle route representation, but with each route representing a TSP circuit whose depot may or may not be the same as another route (so that it can represent solution in problem variant such as MDVRP).
- CMMA: Cooperating memes-based MA in which memes in the form of local searchers are combined in a collaborating manner to form a large neighbourhood specifically for solving vehicle routing problem efficiently and effectively.
- SIM: Adaptive MA that uses the simple inheritance mechanism for adaptive selecting memes (i.e. local searchers) during the lifetime learning process of the MA.
- SGMA: Adaptive MA that uses self-generating mechanisms (e.g. innovation, imitation, etc.) for adaptively generating memes during the lifetime learning process of the MA.
- Meta-Lamarckian MA (S1): Adaptive MA that uses meta-Lamarckian learning mechanism in the form of solution distance-based similarity measure.
- Meta-Lamarckian MA (S2): Adaptive MA that uses meta-Lamarckian learning mechanism in the form of fitness reward and roulette wheel selection method.
- CAMA: Memeplex-based adaptive MA that makes use of conceptual modelling of co-adapted meme complexes or memeplexes to effectively solve optimization problems.
- SAM: Self-adaptive memeplex based MA in which memeplexes are self-adaptive and undergoing learning during lifetime learning phase and evolution phase of MA.
- Choice Function Hyperheuristic (Choice Function): A high-level heuristic which adaptively controls the combination of several low-level knowledge poor heuristics so that while using only cheap and easy-to-implement low-level heuristics, the choice-function hyperheuristic makes an effective and realistic combination of the low level heuristics at hand.
- Simulated Annealing (SA): A generic probabilistic metaheuristic for the global optimization problem of locating a good approximation to the global optimum of a given function in a large search space. Different from traditional SA, SA implemented in this library is VRP domain-driven with a portfolio-based perturbation mechanism to make it more efficient for solving VRP.
The solution methods introduced above are heuristics and meta-heuristics.
Heuristic refers to experience-based techniques for problem solving, learning, and discovery that give a solution which is not guaranteed to be optimal. Where the exhaustive search is impractical, heuristic methods are used to speed up the process of finding a satisfactory solution via mental shortcuts to ease the cognitive load of making a decision.
Meta-Heuristic is a higher-level procedure or heuristic designed to find, generate, or select a lower-level procedure or heuristic (partial search algorithm) that may provide a sufficiently good solution to an optimization problem, especially with incomplete or imperfect information or limited computation capacity.
Figure below illustrates classification of VRP schedulers in the library, the green leave nodes represent the schedulers currently implemented in the Vehicle Routing Scheduler Library.
