Meta-learning to the Vehicle Routing Problem

• Grant number: 22/16276-4
• Support Opportunities: Scholarships in Brazil - Post-Doctoral
• Start date: October 01, 2023
• End date: September 30, 2025
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Computing Methodologies and Techniques
• Principal Investigator: Mariá Cristina Vasconcelos Nascimento Rosset
• Grantee: Alessandra Marli Maria Morais Gouvêa
• Host Institution: Divisão de Ciência da Computação (IEC). Instituto Tecnológico de Aeronáutica (ITA). Ministério da Defesa (Brasil). São José dos Campos , SP, Brazil
• Associated research grant: 13/07375-0 - CeMEAI - Center for Mathematical Sciences Applied to Industry, AP.CEPID

Abstract

The Vehicle Routing Problem (VRP) is a widely studied problem in Operations Research. Over the years, many techniques have been proposed to solve different instances of this problem. Among the techniques, the meta-heuristics (MHs) stand out to provide reasonable solutions in a timely manner as expected by most practical applications. In practice, given the instance of the problem, one always has to choose which MH, from a set of options, is the most appropriate to solve it. Such a choice is a challenging task and common to several optimization problems. Meta-learning, a sub-area of machine learning, holds the needed concepts to deal with this task and has been widely used to recommend the best MH for instances of optimization problems of different domains. However, the literature lacks efforts to apply meta-learning to benefit VRP. To enjoy the meta-learning concepts one need to select instances to compose a data set, map each instance to a vector of characteristic, find the solutions for each instance of the data set, measure the performances of MHs, and then learn which instance characteristics influence the performance of MHs to recommend the best, or a ranking of, MH from the characteristic of a new instance without executing any MH. Steps like the selection of instances and their mapping to a set of characteristics are crucial to the recommendation process. This research project is the first endeavor in sense of applying the meta-learning in benefit of VRP.The project is designed to deal with the challenge of selecting an unbiased set of instances in addition to analyzing different techniques for extracting characteristics from instances in order to identify patterns that influence the performance of MHs, to finally build a model (meta-knowledge) for recommendations of MHs.