============================================================
   Seminário de Teoria da Computação e Combinatória (TCC)

============================================================

Título:      The Vehicle Positioning Problem
            
Palestrante: Carlos Henrique Cardonha
             IBM Research-Brazil

Hora e Data: 14h, sexta-feira, 23 de março de 2012

Local:       Sala Multi-usos do Numec

Resumo: 

This talk addresses the Vehicle Positioning Problem (VPP), a
classical  combinatorial   optimization  problem  in  public
transport in  which vehicles  should be assigned  to parking
positions in a  depot in such a way  that shunting moves are
minimized.  We  investigate   several  models  and  solution
methods  to solve  the VPP  and the  VPPP,  a multi-periodic
extension of the problem which was not previously studied.

We  start with  an introduction  to the  problem and  with a
discussion about  some of its theoretical  properties and IP
formulations (both  linear and quadratic).   For large-scale
scenarios, we propose two  advanced solution methods. In the
first approach, a set  partitioning formulation is solved by
a   branch-and-price   framework.   We   present   efficient
algorithms for the pricing  problem and, in order to improve
the  performance of the  framework, we  introduce heuristics
and  discuss  strategies  to  reduce symmetry.   The  second
approach consists of an  iterative technique in which we try
to optimize an ILP by solving some of its projections, which
are smaller and therefore easier to compute. Both techniques
are able  to produce satisfactory  solutions for large-scale
instances of the VPPP .

Finally,  if we have  enough time,  advanced aspects  of the
problem will be discussed.  Namely, we will present solution
methods  for the  VPP+ and  for  the VPPP+,  which are  more
challenging   versions  of   the  VPP   and  of   the  VPPP,
respectively, and talk about  the role of uncertainty in the
problem.