Detalhes

Nome da Disciplina: MODELAGEM E IMPLEMENTAÇÃO DE ALGORITMOS BRANCH-CUT-AND-PRICE COM VRPSOLVER/META-SOLVER

Carga Horária: 60

Créditos: 3

Obrigatória: Não

PROGRAMA DE DISCIPLINA ÁREA DE CONCENTRAÇÃO: Pesquisa Operacional LINHA DE PESQUISA: Otimização SEMESTRE/ANO DE CRIAÇÃO: 02/2026 SEMESTRE/ANO DE REVISÃO: DOCENTES RESPONSÁVEIS: Marcos Costa Roboredo Currículo aprovado através de Resolução Conselho de Ensino e Pesquisa nº 172/99 DISCIPLINA CÓDIGO: TCE11679 NOME: Modelagem e Implementação de Algoritmos Branch-Cut-and-Price com VRPSolver/Meta-Solver IDIOMA MINISTRADO: PORTUGUÊS TIPO DE OFERECIMENTO DA DISCIPLINA: PRESENCIAL CARGA HORÁRIA SEMANAL CARGA HORÁRIA TOTAL Nº DE CREDITOS TEÓRICA 02 60 03 PRÁTICA 02 OBJETIVOS Objetivo geral Capacitar o aluno a formular variantes de problemas de roteamento de veículos como modelos VRPSolver e a implementar novos recursos no Meta-Solver, resolvendo-os de forma exata via Branch-Cut-and-Price, incluindo o desenvolvimento de modelos inéditos. Objetivos específicos Ao final da disciplina, o aluno deverá ser capaz de: • Compreender os fundamentos de geração de colunas e Branch-Cut-and-Price, e o modelo genérico do VRPSolver baseado em pricing por caminho mínimo com restrições de recursos (RCSP). • Modelar variantes clássicas (CVRP, VRPTW, HFVRP) na interface em Julia e resolvê-las à otimalidade. • Desenvolver modelos VRPSolver inéditos para variantes não tratadas na literatura, definindo os recursos necessários. • Implementar novos recursos no Meta-Solver, garantindo sua corretude, e integrá-los ao solver. • Conduzir e interpretar experimentos computacionais, comparando os resultados com a literatura. JUSTIFICATIVA Os problemas de roteamento de veículos estão entre os mais relevantes da otimização combinatória, com ampla aplicação em transporte, logística e serviços. Na última década, algoritmos Branch-Cut-and-Price (BCP) passaram a obter os melhores resultados na resolução exata de muitas de suas variantes, mas cada variante exigia uma implementação dedicada, distanciando a teoria da aplicação prática. O VRPSolver reduziu esse distanciamento ao oferecer um algoritmo BCP genérico, no qual o usuário modela sua variante em poucas linhas de código. O Meta-Solver amplia essa capacidade ao permitir que novos recursos de viabilidade e custo sejam definidos pelo próprio usuário, viabilizando o tratamento de variantes antes intratáveis com desempenho de estado da arte. A disciplina aproveita esse cenário para levar o aluno do uso da ferramenta ao domínio de seus fundamentos, capacitando-o a modelar variantes, desenvolver modelos inéditos e implementar os recursos correspondentes RESULTADOS DE APRENDIZAGEM / COMPETÊNCIAS Ao concluir a disciplina, o aluno será capaz de: • Explicar os fundamentos de geração de colunas e Branch-Cut-and-Price e o modelo genérico do VRPSolver baseado em pricing por RCSP. • Modelar variantes de roteamento na interface em Julia e resolvê-las à otimalidade. • Desenvolver modelos inéditos e implementar os recursos correspondentes no Meta-Solver, justificando sua corretude. • Avaliar o desempenho computacional dos modelos, comparando os resultados com a literatura. EMENTA Machine Learning; Análise Exploratória de Dados; Dados Tabulares e Árvore de Decisão; Modelos Lineares Problemas de roteamento de veículos e suas variantes. Formulações de particionamento de conjuntos. Geração de colunas e decomposição de Dantzig-Wolfe. Algoritmos Branch-Cut-and-Price. Subproblema de pricing como caminho mínimo com restrições de recursos (RCSP). Modelo genérico do VRPSolver: conjuntos elementares e de empacotamento, mapeamento de variáveis e recursos. Modelagem de variantes clássicas na interface em Julia. Labeling bidirecional sobre o grafo de buckets: estados, extensão, dominância, concatenação e fixação por custo reduzido. Desenvolvimento de modelos inéditos. Implementação de novos recursos no Meta-Solver e sua corretude. Experimentos computacionais e comparação com a literatura. PROGRAMA (CONTEÚDO) Unidade 1 — Fundamentos 1.1 Problemas de roteamento de veículos e suas variantes 1.2 Formulações de particionamento de conjuntos 1.3 Geração de colunas e decomposição de Dantzig-Wolfe 1.4 Separação de cortes e o algoritmo Branch-Cut-and-Price Unidade 2 — O modelo VRPSolver 2.1 Subproblema de pricing como caminho mínimo com restrições de recursos (RCSP) 2.2 Modelo genérico: conjuntos elementares e de empacotamento, mapeamento de variáveis 2.3 Recursos: de viabilidade e de custo 2.4 Cortes de Rank-1 com memória limitada e ng-paths Unidade 3 — Modelagem de variantes 3.1 A interface em Julia (e o VRPSolverEasy) 3.2 Modelagem de variantes clássicas: CVRP, VRPTW, HFVRP 3.3 Configuração, resolução à otimalidade e leitura de resultados 3.4 Desenvolvimento de modelos inéditos Unidade 4 — O Meta-Solver 4.1 Labeling bidirecional sobre o grafo de buckets 4.2 Estados, extensão de rótulos, dominância e concatenação 4.3 Fixação por custo reduzido e exploração de simetria 4.4 A interface do Meta-Solver: symmetric, initState, extendAlongArc/extendToVertex, dominationCost, concatenationCost Unidade 5 — Implementação de recursos 5.1 Definição de um novo recurso e prova de corretude da dominância 5.2 Estudo de caso: recurso de custo cumulativo (CCVRP) 5.3 Estudo de caso: recurso de coleta e entrega simultâneas (VRPSPD) 5.4 Compilação, integração ao solver e construção do modelo Unidade 6 — Experimentação 6.1 Instâncias e métricas: limites, gaps, nós e tempos 6.2 Condução de experimentos computacionais 6.3 Comparação com a literatura 6.4 Apresentação dos projetos METODOLOGÍA / ESTRATÉGIAS DIDÁTICAS (incluir Processo Híbrido de Ensino e Aprendizagem, quando aplicável) A disciplina combina aulas expositivas dialogadas, para os fundamentos teóricos (geração de colunas, Branch-Cut-and-Price, modelo VRPSolver e algoritmo de labeling), com atividades práticas em laboratório, nas quais os alunos modelam variantes e implementam recursos no Meta-Solver. Os conceitos são introduzidos a partir de problemas concretos de roteamento, articulando teoria e aplicação. O estudo dos artigos de referência sobre o VRPSolver e o Meta-Solver é feito por leitura dirigida e discussão em sala, e os estudos de caso (recurso de custo cumulativo e de coleta e entrega simultâneas) são desenvolvidos de forma guiada, da formulação à execução computacional. As atividades práticas evoluem de exercícios de modelagem na interface em Julia até a implementação e integração de recursos novos ao solver. A disciplina culmina em um projeto, no qual cada aluno desenvolve um modelo inédito para uma variante de sua escolha, implementa os recursos correspondentes, conduz os experimentos computacionais e compara os resultados com a literatura, consolidando as competências trabalhadas ao longo do curso. FORMA DE AVALIAÇÃO A avaliação é contínua e combina atividades ao longo do curso com um projeto final, distribuídos da seguinte forma: • Listas e exercícios teóricos e práticos — atividades de modelagem na interface em Julia e exercícios sobre os fundamentos teóricos, acompanhando as unidades. • Projeto final — desenvolvimento de um modelo inédito para uma variante de roteamento, com implementação dos recursos correspondentes no Meta-Solver, experimentos computacionais e comparação com a literatura. Avaliado por relatório escrito e apresentação. ,

BIBLIOGRAFIA BÁSICA UCHOA, E.; PESSOA, A.; MORENO, L. Optimizing with Column Generation: Advanced Branch-Cut-and-Price Algorithms (Part I). Cadernos do LOGIS-UFF, Universidade Federal Fluminense, Engenharia de Produção, n. L-2024-3, ago. 2024. Disponível em: https://optimizingwithcolumngeneration.github.io. PESSOA, A.; SADYKOV, R.; UCHOA, E.; VANDERBECK, F. A generic exact solver for vehicle routing and related problems. Mathematical Programming, v. 183, n. 1, p. 483–523, 2020. SADYKOV, R.; UCHOA, E.; PESSOA, A. A bucket graph-based labeling algorithm with application to vehicle routing. Transportation Science, v. 55, n. 1, p. 4–28, 2021. SADYKOV, R.; FROGER, A.; UCHOA, E.; PESSOA, A.; BULHÕES, T.; DE ARAUJO, D. Bucket Graph Meta-Solver for the Resource Constrained Shortest Path Problem. Preprint hal-05486295, Inria, 2026. ERRAMI, N.; QUEIROGA, E.; SADYKOV, R.; UCHOA, E. VRPSolverEasy: A Python library for the exact solution of a rich vehicle routing problem. INFORMS Journal on Computing, 2024. TOTH, P.; VIGO, D. (Eds.). Vehicle Routing: Problems, Methods, and Applications. 2. ed. Philadelphia: SIAM, 2014. (MOS-SIAM Series on Optimization). BIBLIOGRAFIA COMPLEMENTAR BALDACCI, R.; MINGOZZI, A.; ROBERTI, R. New route relaxation and pricing strategies for the vehicle routing problem. Operations Research, v. 59, n. 5, p. 1269–1283, 2011. PECIN, D.; PESSOA, A.; POGGI, M.; UCHOA, E. Improved branch-cut-and-price for capacitated vehicle routing. Mathematical Programming Computation, v. 9, n. 1, p. 61–100, 2017. PECIN, D.; PESSOA, A.; POGGI, M.; UCHOA, E.; SANTOS, H. Limited memory rank-1 cuts for vehicle routing problems. Operations Research Letters, v. 45, n. 3, p. 206–209, 2017. RIGHINI, G.; SALANI, M. Symmetry helps: bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints. Discrete Optimization, v. 3, n. 3, p. 255–273, 2006. IRNICH, S.; DESAULNIERS, G. Shortest path problems with resource constraints. In: Column Generation. Boston: Springer, 2005. p. 33–65. COSTA, L.; CONTARDO, C.; DESAULNIERS, G. Exact branch-price-and-cut algorithms for vehicle routing. Transportation Science, v. 53, n. 4, p. 946–985, 2019. PESSOA, A.; SADYKOV, R.; UCHOA, E.; VANDERBECK, F. Automation and combination of linear-programming based stabilization techniques in column generation. INFORMS Journal on Computing, v. 30, n. 2, p. 339–360, 2018. SADYKOV, R.; VANDERBECK, F.; PESSOA, A.; TAHIRI, I.; UCHOA, E. Primal heuristics for branch and price: the assets of diving methods. INFORMS Journal on Computing, v. 31, n. 2, p. 251–267, 2019. DAMIÃO, C. M.; SILVA, J. M. P.; UCHOA, E. A branch-cut-and-price algorithm for the cumulative capacitated vehicle routing problem. 4OR, v. 21, p. 41–71, 2023. PRAXEDES, R.; BULHÕES, T.; SUBRAMANIAN, A.; UCHOA, E. A unified exact approach for a broad class of vehicle routing problems with simultaneous pickup and delivery. Computers & Operations Research, v. 162, p. 106467, 2024. DELL'AMICO, M.; RIGHINI, G.; SALANI, M. A branch-and-price algorithm for the vehicle routing problem with simultaneous pickup and delivery. Transportation Science, v. 40, n. 2, p. 235–247, 2006. ROBOREDO, M. C.; SADYKOV, R.; UCHOA, E. Solving vehicle routing problems with intermediate stops using VRPSolver models. Networks, v. 81, n. 3, p. 399–416, 2023.