Identifying the most distinctive characteristics of a good solution for non-Euclidean CVRP using statistical learning model

Abstract

A capacitated vehicle routing problem (CVRP) is a well-known NP-hard combinatorial optimization. Therefore, heuristics are the common methods used to search for a good solution. The algorithms will perform better if characteristics of good solutions of the problem are known. There was a research study in the characteristics of Euclidean CVRP solutions and the knowledge was later applied in a metaheuristic. That study becomes our motivation to study the characteristics of non-Euclidean CVRP solutions. To that end, we considered the solutions of non-Euclidean CVRP in the new Euclidean space with the same or higher dimensions using multi-dimensional scaling in which the characteristics of the solutions can be defined under Euclidean properties. In addition, the statistical learning models were employed to identify the most distinctive characteristic which yields the highest accuracy of prediction of a good solution in the new space. Moreover, decision rules were also determined for interpreting characteristics of good and bad solutions of non-Euclidean CVRP.