A Symmetry-breaking method for The Unit Stop Number Problem

Favoritar este trabalho
Como citar esse trabalho?
Detalhes
  • Tipo de apresentação: Trabalho completo (oral)
  • Eixo temático: 14. OC – Otimização Combinatória
  • Palavras chaves: Orbitopal Fixing; Integer Programming; Symmetry-breaking methods;
  • 1 Universidade Federal de Ouro Preto
  • 2 Université Clermont Auvergne

A Symmetry-breaking method for The Unit Stop Number Problem

Estefânia de Sá Moura

Universidade Federal de Ouro Preto

Resumo

The resolution of Integer Linear Programming formulations generally requires exponential computational time. One of the factors that can contribute to time explosion is the presence of symmetry. Fortunately, symmetry can usually be spotted and treated efficiently. When addressing combinatorial optimization problems with identical allocating resources (i. e., identical machines on Lot Sizing problems), one simple permutation between them can generate symmetric solutions. Such issue appears within the Unit Stop Number Problem, a dial-a-ride transport problem appearing from the deployment of autonomous electric vehicles. In such problem, identical vehicles travels along a predefined circuit where clients request for rides between stations. The goal is to minimize the number of performed pick-up and delivering operations. In this paper we show how symmetry is spotted in such problem and propose to efficiently treat it by adapting and applying the well known Orbitopal Fixing method. Computational results convincingly show the efficiency of our approach.

Compartilhe suas ideias ou dúvidas com os autores!

Sabia que o maior estímulo no desenvolvimento científico e cultural é a curiosidade? Deixe seus questionamentos ou sugestões para o autor!

Faça login para interagir

Tem uma dúvida ou sugestão? Compartilhe seu feedback com os autores!