Título: | INTEGER PROGRAMMING TECHNIQUES AND APPLICATIONS TO VEHICLE ROUTING PROBLEMS | |||||||
Autor: |
HUMBERTO JOSE LONGO |
|||||||
Colaborador(es): |
MARCUS VINICIUS SOLEDADE POGGI DE ARAGAO - Orientador EDUARDO UCHOA BARBOZA - Coorientador |
|||||||
Catalogação: | 09/MAR/2005 | Língua(s): | PORTUGUESE - BRAZIL |
|||||
Tipo: | TEXT | Subtipo: | THESIS | |||||
Notas: |
[pt] Todos os dados constantes dos documentos são de inteira responsabilidade de seus autores. Os dados utilizados nas descrições dos documentos estão em conformidade com os sistemas da administração da PUC-Rio. [en] All data contained in the documents are the sole responsibility of the authors. The data used in the descriptions of the documents are in conformity with the systems of the administration of PUC-Rio. |
|||||||
Referência(s): |
[pt] https://www.maxwell.vrac.puc-rio.br/projetosEspeciais/ETDs/consultas/conteudo.php?strSecao=resultado&nrSeq=6029&idi=1 [en] https://www.maxwell.vrac.puc-rio.br/projetosEspeciais/ETDs/consultas/conteudo.php?strSecao=resultado&nrSeq=6029&idi=2 |
|||||||
DOI: | https://doi.org/10.17771/PUCRio.acad.6029 | |||||||
Resumo: | ||||||||
Optimization techniques have an important role in
Transportation Logistics.
The combinatorial nature of the problems related to this
area suggests
integer programming as a natural approach to their
resolution. Nevertheless
there are many cases where even instances of reasonable
size still beyond
the resolution capability of the current known algorithms.
The success of
the known algorithms have therefore been limited. This can
be justified by
the fact the most of them leave important recent advances
in the combinatorial
optimization field unexplored. Some of these new techniques
and
their applications are the main subject of this thesis. In
the first part, the
basic decomposition techniques for linear and integer
programming problems
as well as the related column generation approach is
addressed. This
is followed by the presentation of a reformulation
technique for linear and
integer programming which is alternative to the well known
Dantzig-Wolfe
master program. The new possibilities coming from this
approach are explored
and the resulting consequences to the standard branch-and-
bound
algorithm and its variations branch-and-cut, branch-and-
price and branchand-
cut-and-price are presented. The second part of this text
addresses the
application of the metodologies described in part one to
routing problems
where capacity constraints are considered. First, a
techinque named Projected
Column Generation is described in the context of the
Capacitated
Vehicle Routing Problem. Then, it is presented a new
transformation from
the Capacitated Arc Routing Problem to the Capacitated
Vehicle Routing
Problem as well as a tailored branch-and-cut-and-price to
solve this problem.
Finally, a new problem in vehicle redistrubution is
described together
with a column generation approach for its resolution.
Computational results
for all applications are presented.
|
||||||||