Improved Meta-RaPS approach with learning concepts for solving capacitated vehicle routing problem

This thesis presents an application of learning concepts incorporated in the construction phase of Meta-heuristic with Randomized Priority Search (Meta-RaPS). This new algorithm is applied for solving capacitated vehicle routing problem (CVRP) with an objective to minimize the total distance travelled in each route while satisfying capacity constraint in forming the routes. This problem is an NP-Hard in nature, so there is no known optimal solution method with polynomial time. This thesis proposes a new method that can solve this problem more efficiently than Meta-RaPS with good quality results. Meta-RaPS learning is implemented and its performance is measured by comparing it against existing heuristics for the same problem. Results from experimentations show Meta-RaPS learning outperformed Meta-RaPS and most of the heuristics for this problem but not as good against some metaheuristics.