Modelos para o problema de roteamento de veículos com restrições de empacotamento bidimensional
Carregando...
Data
2017-06-28
Autores
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Goiás
Resumo
Three different integer linear programming models for the Vehicle Routing Problem with
Two-dimensional Loading Constraints are developed in this work. The version of the problem
studied considers that the unloading of the rectangular items can respect or not the
sequence of the clients visited on the route, that is, we solve the sequential and unrestricted
versions of the problem. The first model deals with the problem completely, that is, with
all constraints inserted at once. The second and third models are based, respectively, on
a three- and two-index formulation. Separation routines are considered to detect violated
inequalities related with packing on the second and third models, while the third model also
considers cuts on connectivity and capacity. Computational experiments were carried out
over instances of the literature with the quantity of customers ranging from 15 to 36 and
items from 15 to 114, besides to consider the cases in which the cost of traversing an edge
is integer and real. The models with cuts on demand were better in relation to the first model,
besides being competitive when comparing with the results fromthe literature. The first
model solved 4 of the 80 instances, the three-index model solved 7 and, the two-index model
solved 53. On the sequential version, the adopted model solved 33 instances for the case
with integer costs (and 37 for the case with real costs). In comparing with a recent heuristic
from the literature, the best model was capable of tying in 48 instances in the unrestricted
version and 24 in the sequential version.
Descrição
Palavras-chave
Problema integrado, Problema de roteamento de veículos, Problema de empacotamento ortogonal bidimensional, Programação linear inteira, Planos de corte, Integrated problem, Vehicle routing problem, Two-dimensional orthogonal packing problem, Integer linear programmig
Citação
SILVA, Lorrany Cristina da. Modelos para o problema de roteamento de veículos com restrições de empacotamento bidimensional. 2017. 89 f. Dissertação (Mestrado em Modelagem e Otimização) - Universidade Federal de Goiás, Catalão, 2017.