[pt] Problemas de transporte de cargas fracionadas são grandes
candidatos para
a aplicação de técnicas de otimização como forma de obter
um melhor
aproveitamento de recursos. Nesta dissertação, são
apresentados modelos
de programação inteira e os algoritmos desenvolvidos para
a
resolução adequada
dos problemas estudados neste contexto. O foco é o
planejamento
da movimentação dos veículos para o atendimento das
demandas ao longo
de um período pré-definido. Diferentes formas de
contratação dos veículos
são consideradas, demandas possuem janelas de tempo para
serem atendidas
e podem compartilhar um mesmo veículo em um ou mais
trechos
do seu caminho até o destino. Conexões são permitidas, ou
seja, uma demanda
pode utilizar mais de um veículo para o seu atendimento,
respeitando
as capacidades operacionais dos centros de distribuição e
coleta. Os
objetivos abrangem o dimensionamento da frota, que possui
um custo fixo,
e o planejamento da operação ao longo do período. Este
deve
determinar
quais demandas são transportadas por quais veículos em
que
instantes e
em que trechos. O método de resolução proposto utiliza
algoritmos para a
construção e pré-processamento de grafos que representam
o
problema e permitem
que a formulação como programa inteiro tenha uma
resolução
mais efciente. Além disso, o algoritmo correspondente
resolve uma sequência de
programas inteiros para obter soluções viáveis de
qualidade
para as diferentes
versões do problema aqui considerado. Melhorias nos
limites
inferiores
obtidos também são propostas. O código resultante foi
testado em um conjunto
de instâncias baseadas na operação de uma transportadora
brasileira
de grande porte. Resultados foram obtidos tanto para
condições de utilização reais, isto é, com o tempo de
execução limitado, como para testar
os limites do método proposto. Em ambos os casos pôde-se
obter soluções
de alta qualidade comprovada. / [en] Less-than-truckload transportation problems are great
candidates for the application of optimization techniques
as a form to obtain a better exploitation
of resources. This thesis introduces integer programming
models and the developed algorithms for the proper
resolution of the studied problems in this context. The
focal point is the vehicle's dislocation planning for the
ideal attendance of the demands during a certain time
period. Different forms of vehicle contract are considered.
There are time windows for the attendances and demands can
share a same vehicle in one or more parts of
its route until his destination. Connections are allowed,
that is, demands can use more than one vehicle for its
attendance, respecting the operational capacities of the
centers (collection and distribution stations). The
goals embraces the sizing of the proper fleet which has a
fixed cost, and the operation's planning during the period.
This one should determine which demands are transported by
which vehicles in what instants and where on routes. The
resolution's method proposed uses algorithms for the graph's
construction and pre-processing which represents the
problem and allows that the formulation, as an integer
program, to have a resolution more efficient. Furthermore,
the corresponding algorithm solves a sequence of integer
programs to obtain feasible quality solutions for the
differents versions of the considered problem. Improvements
on the lower bounds gotten are also proposed.
The resulting code was tested in a set of proposed
instances that were based on the operation of an important
brazilian trucking company . Results were acquired such for
conditions of real utilization, in other words, with a
limited time of execution, as to test the limits of the
proposed method. In both cases, solutions of comproved high
quality were obtained.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:12334 |
| Date | 10 October 2008 |
| Creators | PEDRO DE MOURA E CUNHA |
| Contributors | MARCUS VINICIUS SOLEDADE POGGI DE ARAGAO |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | TEXTO |
Page generated in 0.0025 seconds