A Symmetry-breaking method for The Unit Stop Number Problem

Favorite this paper
How to cite this paper?
Details
  • Presentation type: Trabalho completo (oral)
  • Track: 14. OC – Otimização Combinatória
  • Keywords: 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

Abstract

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.

Share your ideas or questions with the authors!

Did you know that the greatest stimulus in scientific and cultural development is curiosity? Leave your questions or suggestions to the author!

Sign in to interact

Have a question or suggestion? Share your feedback with the authors!