Um Modelo de Programaçao Inteira Mista para uma ... · foi modelado como um problema de programação inteira mista e resolvido pelo CPLEX. O modelo proposto foi testado usando

Um Modelo de Programacao Inteira Mista para umaEspecializacao do Problema de Empacotamento Tridimensional

Paulo de Tarso Gomide Castro Silva1

1Departamento de InformaticaPontifıcia Universidade Catolica do Rio de Janeiro (PUC-Rio)

Rua Marques de Sao Vicente, 225, 22453-900, Rio de Janeiro, RJ, [email protected]

Geraldo Robson Mateus2

2Departamento de Ciencia da ComputacaoUniversidade Federal de Minas Gerais (UFMG)

Av. Antonio Carlos, 6627, 31270-010, Belo Horizonte, MG, [email protected]

RESUMO

Nesse trabalho, e estudada uma especializacao do Problema de Empacotamento Tridimensional.Dado uma certa quantidade de produtos de dimensoes e pesos variaveis e uma frota com determinadostipos de veıculos, o problema consiste em alocar os produtos na frota de modo a minimizar a carga mortanesses veıculos. Cada produto apresenta ainda um status que varia conforme a urgencia de sua entrega,ganhando uma prioridade maior no momento de alocacao, aqueles cuja entrega e mais urgente. O problemafoi modelado como um problema de programacao inteira mista e resolvido pelo CPLEX. O modelo propostofoi testado usando dados reais de uma grande empresa brasileira que, interessada no trabalho, concordouem ceder algumas informacoes de seu funcionamento. Os resultados desses testes sao aqui apresentados ecomparados a uma heurıstica que simula a alocacao manual de produtos, atualmente realizada nas empresasque nao possuem um software adequado para a realizacao dessa tarefa.

PALAVRAS CHAVE. Problema de Empacotamento. Programacao Inteira Mista. Otimizacao Combi-natoria. AL - Aplicacoes a Logıstica e Transportes.

ABSTRACT

In this paper we study a Three-Dimensional Bin Packing Problem specialization. Given a certainamount of goods with variable dimensions and weights and a fleet of trucks of different types, the problemconsist of allocating the goods in the fleet so as to minimize the empty space. Each good also has a statuswich varies according to the urgency of its delivery, the higher being this urgency, the higher being thepriority of such delivery. The problem was modeled as a Mixed Integer Programming Problem and solvedby CPLEX. We have tested the proposed model using data from a big brazilian company wich, interestedin the project, has agreed to provide us with information about its operation. The results for these testsare reported here and compared to an heuristic that simulates the manual allocation of the goods, currentlyemployed by companies with no specific software for this task.

KEYWORDS. Bin Packing Problem. Mixed Integer Programming. Combinatorial Optimization. AL -Applications for Logistics and Transport.

1O presente trabalho e parte do projeto final de graduacao desenvolvido na Universidade Federal de Minas Gerais

XLI SBPO 2009 - Pesquisa Operacional na Gestão do Conhecimento Pág. 1302

1. IntroducaoCada vez mais, aumenta, por parte das empresas, a preocupacao em minimizar os gastos empregados

no escoamento de seus produtos. Isso acontece devido ao fato de os custos relacionados ao transporte demercadorias representar uma parcela significativa no custo final dessas e dos servicos de uma industria.

A exemplo do Brasil, em muitos paıses o transporte de cargas e, basicamente, rodoviario e os gastoscom esse meio de transporte sao muito elevados por inumeras razoes como o alto preco do combustıvel, acobranca de pedagios e os elevados custos com a manutencao de veıculos, muitas vezes agravados pelo mauestado de conservacao das vias.

Com tantas despesas, os custos com transporte de uma mercadoria chegam a representar 10% a15% do valor dessa. No Brasil, o gasto com transporte de cargas corresponde a 10,8% do PIB (ProdutoInterno Bruto) [Alvarenga 2005]. Portanto, o transporte e uma das atividades que mais contribuem nos custoslogısticos de uma empresa, de modo que qualquer reducao em seus custos pode trazer uma significativareducao no valor final das mercadorias.

E nesse contexto que surgem varias ideias a fim de minimizar os custos envolvidos no tratamentodessas mercadorias. Sao analisados os custos desde o momento de envio ate sua estocagem no destino final,onde aparecem classicos problemas da area de logıstica como o Problema de Corte (PC), o Problema deEmpacotamento (PE) e o Problema de Roteamento de Veıculos (PRV).

Nesse trabalho, por iniciativa de uma empresa interessada no trabalho, foi estudado uma especia-lizacao do Problema de Empacotamento (PE) considerando aspectos reais de grandes grupos do cenarionacional. Um desafio que esses grupos e seus parceiros enfrentam diariamente se refere a maneira de alocarsuas mercadorias nos caminhoes certos de modo a minimizar os espacos perdidos. Esse tipo de problema econhecido como o Problema de Empacotamento Tridimensional (PET), ou Problema de Empacotamento 3Ddo ingles Three-Dimensional Bin Packing Problem (3DBPP). O objetivo principal desse classico problema edeterminar padroes eficientes de utilizacao de objetos grandes por objetos menores, de dimensoes e quanti-dades conhecidas. Em outras palavras, pretende-se saber como colocar caixas (objetos pequenos) no interiorde contentores ou de caminhoes de forma a obter, nomeadamente, um bom aproveitamento do espaco [Silvaand Soma 2003]. Por tratar-se de um problema NP-difıcil, o PET apresenta alta complexidade de resolucao,oferecendo assim um estımulo a mais para os grandes pesquisadores.

O Problema de Empacotamento Tridimensional, em geral, e amplamente estudado na area de otimi-zacao combinatoria. A natureza intrinsecamente combinatorial desse problema sugere que ele possa serformulado e resolvido como um problema de programacao inteira [Longo 2004]. E foi justamente apoiando-se nesse aspecto do problema, que o presente trabalho concentrou-se para modela-lo dessa forma.

Para a resolucao da especializacao do PET aqui tratada, foi alvitrado nesse trabalho a elaboracaode um algoritmo exato que o modela como um problema de programacao inteira mista, visando sempre aminimizacao da carga morta nos caminhoes, seja por peso, volume ou area (diferenca entre a capacidade totaldo veıculo e a quantidade realmente utilizada). Apesar de, em geral, os algoritmos exatos nao suportarembem os problemas NP-difıceis, no caso aqui analisado, a modelagem mostrou-se suficiente para o porte dasgrandes empresas do cenario nacional, uma vez que nessas os tipos de embalagens e caminhoes utilizadosnao apresentam grandes variacoes.

As principais particularidades das mercadorias a serem transportadas, assim como as caracterısticasdos caminhoes disponıveis, serao mostradas na definicao do problema.

A motivacao para esse trabalho, foi a demanda por uma maior automatizacao do processo de monta-gem de cargas, por parte de varias empresas, considerando diversas condicoes e regras de trabalho, para queseja possıvel dessa forma fazer um melhor planejamento a medio e curto prazo e a programacao diaria.

A ideia central do trabalho foi implementar um algoritmo que atenda qualquer empresa que precise,em um tempo habil, definir uma boa forma de alocar suas mercadorias a serem entregues. Para tanto, buscou-


se modelar o problema de forma mais generica possıvel para que o mesmo possa ser utilizado em diversoscenarios.

Para dar uma melhor visibilidade da economia que a aplicacao do algoritmo elaborado pode gerar,e apresentada, para algumas instancias fornecidas por uma grande empresa interessada no trabalho, umacomparacao entre a solucao do problema obtida pela modelagem apresentada e por uma heurıstica que simulao processo manual de empacotamento utilizado hoje nessa empresa.

Portanto, a proposicao do trabalho foi criar um algoritmo que otimizasse o modo como, rotinei-ramente, sao alocadas as mercadorias enviadas aos clientes de grandes empresas, fazendo com que essaspossam diminuir os custos com as transportadoras, na medida que minimizam os espacos desperdicados noscaminhoes. Buscou-se a sistematizacao do processo de montagem de carga dos caminhoes de forma a oti-mizar a carga morta transportada, uma vez que o valor do transporte e calculado com base na capacidade,em toneladas, metros cubicos ou metros quadrados dos veıculos, multiplicada pela distancia percorrida pelosmesmos. Maiores detalhes do problema serao apresentados na proxima secao.

Este artigo esta organizado da seguinte forma. Na proxima secao, o problema e definido de formadetalhada e objetiva. A secao 3 apresenta todo o referencial teorico citando os principais trabalhos relaci-onados. O modelo implementado e explicado na secao 4. A secao 5 traz os resultados atingidos para asinstancias fornecidas pela empresa interessada. E, por fim, sao mostrados os trabalhos futuros, bem como aconclusao na secao 6.

2. Definicao do ProblemaO Problema de Empacotamento Tridimensional surge normalmente no setor de expedicoes de gran-

des empresas. Diariamente este setor e responsavel pela montagem das cargas, conforme pedidos, e envioaos clientes. Essas cargas sao, em geral, enviadas utilizando caminhoes como meio de transporte, sendo namaioria dos casos de responsabilidade da propria empresa.

Para o envio dessas mercadorias, transportadoras sao contratadas a todo tempo. A forma de operacaodestas empresas nao e considerada no trabalho, uma vez que, a princıpio, nao se pretende modificar suasformas de atuacao.

No contexto atual brasileiro, as grandes empresas organizam os pedidos atraves de programas. Cadaprograma identifica um ou mais produtos para um unico cliente. Esses programas sao gerados em decorrenciade datas estabelecidas por contrato ou atraves de residentes das empresas atuando junto ao cliente. Umavez estabelecidos os programas, a transportadora e informada sobre os pedidos a serem entregues para umcliente e quais veıculos serao usados. Cabe as proprias empresas definir os caminhoes e montar as cargasnos mesmos.

A transportadora envia o(s) caminhao(oes) para cada entrega, podendo existir uma diferenca negativaentre a quantidade a ser transportada e a capacidade do(s) caminhao(oes). Quando o caminhao chega aempresa, o veıculo e seu motorista ja sabem o seu destino, por este motivo o caminhao nao pode ser alocadoa outro cliente. Com o caminhao alocado, o setor de expedicao e o responsavel por identificar os produtos aserem carregados e como sera montada a carga naquele caminhao.

Tratando-se de grandes empresas brasileiras, pode-se imaginar um escoamento bem grande de mer-cadorias atingindo o valor de mil toneladas por dia e demandando dezenas de caminhoes de suas transpor-tadoras. Apesar de boa parte das empresas de grande porte apresentarem mercadorias de diversas formasdiferentes, normalmente as embalagens dessas nao sofrem tantas variacoes. Nesse trabalho e na empresanele interessada e considerado apenas o empilhamento de embalagens do mesmo tipo e o empilhamentomaximo permitido e informado para cada tipo.

No Brasil, as transportadoras dispoem basicamente de quatro categorias de caminhoes. Essas foramexatamente as categorias consideradas nos testes cujos resultados ainda serao mostrados. Sao elas:


1. Caminhao trucado: capacidade de 14t e area util de 2,40m x 7,60m x 4,00m;2. Caminhao trator + semi-reboque: capacidade de 27t e area util de 2,40m x 13,10m x 3,00m;3. Caminhao trator trucado + semi-reboque: capacidade de 31t e area util de 2,40m x 12,30m x

4,00m;4. Bitrem: capacidade de 41t e area util de cada carreta de 2,40m x 7,40m x 3,00m.

Como dito, o objetivo maior na montagem da carga e minimizar a carga morta. E exatamente aıque o estudo desse problema ganha importancia, uma vez que a carga morta e, em geral, decorrente douso ineficiente das capacidades disponıveis. As causas dessa ineficiencia pode ser atribuıda a incorretamontagem da carga, ou a alocacao de caminhao que nao atende idealmente, em termos de sua capacidade,a carga a ser montada, ou ainda a inadaptabilidade dos produtos a serem transportados com a capacidadeou caracterıstica dos caminhoes disponıveis. No primeiro caso, a montagem otimizada dos produtos podereduzir a carga morta. No segundo, um melhor criterio no processo de alocacao dos caminhoes. E no terceiro,um replanejamento do formato e tamanho dos produtos a serem transportados. Nesse trabalho, sao ofertadassolucoes para os dois primeiros casos, ignorando apenas a ultima situacao citada onde o proprio processo deproducao deve ser repensado, extrapolando a abrangencia do Problema de Empacotamento.

A fim de se atingir um planejamento mais coerente no atendimento a todos os clientes, os pedidos,ou programas, sao classificados em uma de tres categorias, recebendo prioridade diferente em cada umadelas. Sao elas:

1. Atrasado: pedido em atraso;2. Obrigatorio: pedido que deve ser atendido, impreterivelmente, no presente dia;3. Antecipado: pedido com data de entrega futura ou mesmo que nao foi feito atraves de um programa

mas sua entrega pode ser adiantada.

Normalmente o onus maior assumido pela empresa, provem do atraso em si, tendo acrescimos di-minutos em relacao aos dias a mais de demora. Por essa razao a prioridade maxima de entrega encontra-senos produtos com status obrigatorio.

Um aspecto importante e que deve ser reforcado e o fato de que nao deve haver o compartilhamentode carga entre clientes. Tambem por isso, uma boa escolha dos caminhoes que irao transportar uma certamercadoria e fundamental.

Entre os aspectos gerais, mostrou-se ideal considerar a significancia do peso dos produtos, bem comoo empilhamento e o espacamento desses na montagem da carga. Dependendo do produto e/ou cliente e/ouempresa que faz o atendimento, certos produtos podem ser alocados considerando apenas suas dimensoes jaque o seu peso e simbolico comparado a capacidade dos caminhoes ou mesmo ao peso das demais pecas aserem alocadas, produtos identicos podem ser empilhados ou nao, e alguns espacamentos mınimos sao ounao pre-fixados. Alem disso considerou-se a limitacao da quantidade de produtos pelo estoque e o respeitoa um numero maximo de veıculos disponıveis que podem ser alocados da transportadora. Um outro aspectorelevante e o posicionamento dos produtos no caminhao, mais precisamente o fato das cargas mais pesadasdeverem ser necessariamente posicionadas entre os eixos do caminhao ou nao. Em busca da maxima ge-neralidade, todos os aspectos acima mencionados podem ser ou nao ser considerados, dependendo apenasdos valores dos parametros do problema ou, no caso do ultimo aspecto tratado, da presenca ou ausencia dealgumas restricoes.

3. Trabalhos RelacionadosO Problema de Empacotamento Tridimensional e um classico problema da computacao e ha muito

tempo vem sendo estudado por pesquisadores de todo o mundo. Muitos trabalhos ja foram publicadosapresentando solucoes para o problema, que usam desde algoritmos exatos ate heurısticas e meta-heurısticas.


Por tratar-se de um problema da classe dos problemas NP-difıceis, a natureza e complexidade doPET levam a uma explosao combinatoria de possibilidades para avaliacao de todas as solucoes possıveis demodo que, na pratica, na maioria dos casos, os algoritmos exatos sao potencialmente incapazes de resolvero problema. Algumas tentativas foram feitas ao longo do tempo e, dentre os metodos exatos, so aqueles queconsideram algumas simplificacoes na definicao do problema apresentam resultados mais efetivos, como[Martello et al. 2000].

Entretanto, o acrescimo dessas simplificacoes nao invalida o que ja foi afirmado anteriormente.Mesmo com elas, os algoritmos exatos so funcionam bem para instancias de tamanho reduzido, restrin-gindo a sua aplicabilidade a casos especıficos. Assim, a tendencia natural e que para solucao do PET sejamimplementados algoritmos aproximados (heurısticas e meta-heurısticas) que nao garantem a solucao otima,mas que geram boas solucoes em tempos aceitaveis.

No campo dos algoritmos de aproximacao, Li e Cheng [Li and Cheng 1990a] foram os primeiros aestudar o Problema de Empacotamento Tridimensional, apresentando diversos algoritmos para o mesmo em1990 [Li and Cheng 1990b, Li and Cheng 1990c, Li and Cheng 1992]. A partir daı, varios pesquisadores seinteressaram por essa linha e diversas heurısticas e meta-heurısticas foram testadas usando as mais diversasestrategias. Dentre esses pesquisadores destacaram-se, alem de Li e Cheng, Miyazawa [Miyazawa 1993,Miyazawa 1997a], Wakabayashi [Miyazawa and Wakabayashi 1998, Miyazawa and Wakabayashi 1994,Miyazawa and Wakabayashi 1997b], Silva [Silva and Soma 2003], Feo [Feo and Resende 1995], entre outros.No trabalho [Miyazawa 1997a], e introduzida uma subdivisao ao problema de empacotamento tratando-ode forma diferente quando se trata da alocacao de produtos “pequenos”. Tal definicao e aqui aproveitadaconsiderando a alocacao de produtos pequenos, aquela em que a viabilidade da montagem dos produtosdepende apenas do respeito as restricoes de peso, volume e area do veıculo, uma vez que as dimensoes dosprodutos sao bem pequenas em relacao ao compartimento de alocacao.

Entretanto, apesar de tantos estudos nessa area, no melhor do conhecimento dos autores, nao hamencao na literatura de nenhum estudo que combine, como proposto nesse trabalho, o problema de empa-cotamento lidado no momento de expedicao com um planejamento a longo prazo, com o intuito de que aempresa fornecedora e a transportadora possam estar melhores preparadas para possıveis imprevistos e maisimunes a problemas como falta de embalagens ou veıculos disponıveis.

4. AlgoritmosComo o trabalho em questao trata um problema da classe NP-difıcil, inicialmente era esperada a

necessidade da implementacao de algoritmos aproximados, uma vez que era prevista uma insuficiencia porparte de um algoritmo exato para instancias de porte razoavel. No decorrer do trabalho, porem, causandocerta surpresa, a execucao do modelo elaborado no resolvedor CPLEX mostrou-se sim, viavel para instanciasde porte real como as da empresa interessada no trabalho. As razoes disso, que em um primeiro momentonao foram percebidas, sao os fatos de boa parte das grandes empresas do cenario nacional, que precisam deum software como o desenvolvido, apresentarem poucas variacoes nas embalagens usadas, das principaistransportadoras disponibilizarem poucas categorias diferentes de veıculos para esse tipo de transporte e,principalmente, das embalagens a serem transportadas apresentarem tamanhos bem pequenos em relacaoaos veıculos, minimizando a importancia das suas dimensoes em si.

Assim sendo, a implementacao de algoritmos aproximados mostrou-se desnecessaria e foi imple-mentado apenas uma heurıstica simples que busca simular o processo manual de alocacao de produtos quee utilizado hoje por muitas das grandes empresas do paıs. O intuito dessa heurıstica e gerar uma base decomparacao para os resultados do algoritmo exato proposto, de modo que se possa assim, estimar a econo-mia que a implantacao de um sistema com tal algoritmo poderia proporcionar a uma empresa.

A seguir e apresentado o modelo de programacao inteira mista formulado para a resolucao do pro-blema estudado. Como mencionado no capıtulo anterior, o problema apresenta uma complexidade menor


quando se trata da alocacao de objetos pequenos, ocasiao em que a viabilidade da montagem das cargasindepende das dimensoes dessas. A diferenca pratica e que nesse caso ja na alocacao dos produtos na frota,se tem a garantia que a montagem dos mesmos e viavel.

A fim de facilitar a compreensao do leitor, cuidadosos comentarios sao tecidos a respeito da funcaoobjetivo e de cada uma das restricoes definidas no modelo. Em seguida ao modelo, e mostrada a heurısticade simulacao criada.

4.1. Modelo de Programacao Inteira Mista

Para uma melhor vizualizacao dos modelos, modularizamos a apresentacao dos mesmos de modoque sao observadas cinco partes distintas quais sejam os conjuntos considerados no problema, os parametrosdesse, as variaveis do modelo, a funcao objetivo e, por fim, as restricoes definidas.

Esse modelo tem como finalidade a alocacao dos produtos na frota. O seu intuito e de servir comoferramenta aos profissionais responsaveis pela alocacao dos produtos nos veıculos, nao importando a essescomo sera feita a montagem ou mesmo as dimensoes dos produtos em si.

4.1.1. Conjuntos Considerados no Problema

• Conjunto dos tipos de produto a serem alocadosP = {p1, p2, p3 . . .};

• Subconjunto de P com os tipos de produto em que o peso e consideradoPP = {p1, p2, p3 . . .};• Conjunto de status possıveis para um produto

S = { “obrigatorio”, “atrasado”, “antecipado” };• Conjunto dos veıculos disponıveis na transportadora

T = {t1, t2, t3 . . .};• Conjunto de particionamentos da cacamba dos veıculos

B = { “sobre o eixo dianteiro”, “entre os eixos”, “sobre o eixo traseiro” };

4.1.2. Parametros do Problema

• lp → largura dos produtos do tipo p ∈ P• cp → comprimento dos produtos do tipo p ∈ P• hp → altura dos produtos do tipo p ∈ P• wp → peso dos produtos do tipo p ∈ P• mp → empilhamento maximo permitido para produtos do tipo p ∈ P• obp → quantidade de produtos do tipo p ∈ P com status obrigatorio• atp → quantidade de produtos do tipo p ∈ P com status atrasado• anp → quantidade de produtos do tipo p ∈ P com status antecipado• stp → quantidade em estoque de produtos do tipo p ∈ P• spc→ espacamento mınimo exigido entre os produtos a serem alocados• Lt → largura do veıculo t ∈ T• Ct → comprimento do veıculo t ∈ T• Ht → altura do veıculo t ∈ T• Wt → peso maximo suportado pelo veıculo t ∈ T

Sem perda de generalidade, todos os parametros do problema sao definidos como inteiros nao ne-gativos. Para uma descricao mais compacta do modelo, definimos mais alguns parametros que auxiliam nacompreensao do mesmo. Sao eles:


• vp → volume dos produtos do tipo p ∈ P = lp.cp.hp

• ap → area dos produtos do tipo p ∈ P = lp.cp

• npt → empilhamento maximo para produtos do tipo p ∈ P no veıculo t ∈ T = min(mp,

⌊Hthp

⌋)• Wtb → peso maximo suportado pela particao b ∈ B do veıculo t ∈ T = Wt

3

• Vtb → volume da particao b ∈ B do veıculo t ∈ T = Lt.Ct3 .Ht

• Atb → area da particao b ∈ B do veıculo t ∈ T = Lt.Ct3

4.1.3. Variaveis do Modelo

• xpstb ∈ Z+ → quantidade de produtos do tipo p ∈ P com status s ∈ S na particao b ∈ B do veıculot ∈ T

• yt ∈ B→ igual a 1, se o veıculo t ∈ T e usado na alocacao dos produtos e 0, caso contrario• zptb ∈ Z+ → quantidade de pilhas necessarias para acomodar todos os produtos do tipo p ∈ P

alocados para a particao b ∈ B do veıculo t ∈ T• CMPtb ∈ R+ → carga morta em relacao ao peso na particao b ∈ B do veıculo t ∈ T• CMVtb ∈ R+ → carga morta em relacao ao volume na particao b ∈ B do veıculo t ∈ T• CMAtb ∈ R+ → carga morta em relacao a area na particao b ∈ B do veıculo t ∈ T

4.1.4. Funcao Objetivo

Sempre buscando ampliar a generalidade e aplicabilidade do algoritmo, a funcao objetivo do pro-blema (1) tambem esta condicionada ao interesse do usuario. Dessa forma, pode ser minimizada a cargamorta em relacao ao peso, volume ou area, ou ainda qualquer combinacao desses fatores, permitindo assimao usuario buscar um bom aproveitamento dos veıculos em relacao ao(s) fator(es) que mais lhe interesse(m).Para os testes, como foi sugerido pela empresa interessada, minimizamos a soma das cargas mortas emrelacao ao peso e ao volume.

min∑t∈T

∑b∈B

[CMPtb, CMVtb, CMAtb] (1)

4.1.5. Restricoes

As restricoes definidas para o problema cuidam para que todos os limites e particularidades especi-ficados sejam respeitados. Com essa finalidade sao necessarias restricoes tratando diversos aspectos comoos limites de peso, volume e area dos veıculos, a necessidade de envio dos produtos classificados como obri-gatorio, a correspondencia dos tipos de produtos disponıveis em estoque com aqueles alocados na frota, etc.Todas essas restricoes impostas sao apresentadas e explicadas a seguir:

∑p∈PP

∑s∈S

xpstbwp + CMPtb = ytWtb, ∀ t ∈ T, ∀ b ∈ B (2)

∑p∈P

∑s∈S

xpstbvp + CMVtb = ytVtb, ∀ t ∈ T, ∀ b ∈ B (3)

∑p∈P

zptb(ap + 2spc(cp + lp + 2spc)) + CMAtb = ytAtb, ∀ t ∈ T, ∀ b ∈ B (4)


As restricoes (2), (3) e (4) verificam, respectivamente, o respeito aos limites de carga, volume e area,ja definindo as cargas mortas presentes em todas as particoes de todos os veıculos onde os produtos seraoalocados. Vale observar que as restricoes (4) consideram a area total ocupada pelas pilhas onde os produtosserao alocados em uma dada particao de um veıculo, ja considerando o espacamento mınimo exigido entreesses.

∑s∈S

xpstb > (zptb − 1)npt, ∀ p ∈ P,∀ t ∈ T, ∀ b ∈ B (5)

∑s∈S

xpstb ≤ zptbnpt, ∀ p ∈ P,∀ t ∈ T, ∀ b ∈ B (6)

As restricoes (5) e (6) lidam com o empilhamento dos produtos. Sao elas que definem o numero depilhas necessarias para alocar todos os produtos de um determinado tipo na particao de um veıculo. Para essadefinicao, e considerado o maior empilhamento possıvel para produtos do tipo p ∈ P no veıculo t ∈ T , ouseja, e analisado o empilhamento maximo permitido para o tipo de produto e a viabilidade do empilhamentoem relacao a altura do veıculo.

∑t∈T

∑b∈B

xpstb = obp, ∀ p ∈ P, s = 1 (7)

∑t∈T

∑b∈B

xpstb ≤ atp, ∀ p ∈ P, s = 2 (8)

∑t∈T

∑b∈B

xpstb ≤ anp, ∀ p ∈ P, s = 3 (9)

Tratados todos os limites em relacao ao peso, volume e area das particoes dos veıculos com osprodutos a serem ali alocados, as restricoes (7), (8) e (9) garantem a alocacao de todos os produtos comstatus obrigatorio e a flexibilidade para alocar ou nao os demais produtos, conforme seja mais interessantepara a empresa.

∑s∈S

∑t∈T

∑b∈B

xpstb ≤ stp, ∀ p ∈ P (10)

Para respeitar a capacidade de oferta de produtos da empresa em questao, as restricoes (10) fazemcom que possam ser alocados nos veıculos uma quantidade maxima de produtos correspondente aqueladisponıvel em estoque.

∑p∈P

∑s∈S

xpstb′wp ≤∑p∈P

∑s∈S

xpstb′′wp, ∀ t ∈ T, b′ = 1, b′′ = 2 (11)

∑p∈P

∑s∈S

xpstb′wp ≤∑p∈P

∑s∈S

xpstb′′wp, ∀ t ∈ T, b′ = 3, b′′ = 2 (12)

Por fim, as restricoes (11) e (12) fazem com que as cargas estejam bem distribuıdas pelo veıculoconcentrando uma maior carga entre seus eixos, ja que e a particao mais resistente e menos instavel domesmo.


5. Heurıstica de Simulacao do Empacotamento ManualConforme mencionado, com o intuito de simular a alocacao manual de produtos atualmente realizada

nas empresas que nao possuem um software adequado para a realizacao de tal tarefa, foi implementada umaheurıstica bem simples para que se possa ter um parametro de comparacao e com isso, estimar a economiaque a implantacao de um software como o proposto pode gerar. A ideia dessa heurıstica e mostrada noalgoritmo abaixo e o mesmo e explicado logo a seguir.

Algoritmo 1 : Heurıstica de Simulacao de uma Alocacao Manual de MercadoriasEntrada : Produtos a serem alocados e veıculos disponıveis

1: Ordene em ordem decrescente todos os produtos que se deseja alocar em relacao ao peso, volume ou area, conformeo que se deseja minimizar;

2: Inicialize uma solucao inicial vazia, isto e, ainda sem nenhum produto alocado nos veıculos;3: enquanto (houver algum produto que nao esta alocado em nenhum veıculo) faca4: Selecione, segundo a ordenacao realizada, o proximo produto a ser alocado;5: Percorra todos os veıculos que ja possuem alguma carga alocada verificando a possibilidade de alocar ali o

produto selecionado;6: Caso encontre algum, o produto em questao e alocado no primeiro veıculo com capacidade e espaco suficiente

para ele;7: Caso nao exista nenhum veıculo capacitado ou caso se trate do primeiro produto, um novo veıculo qualquer que

esteja disponıvel entra na solucao e comeca a receber cargas.8: fim enquanto

O algoritmo implementado ordena, de modo decrescente, as mercadorias em relacao a metrica deinteresse do usuario (1). Esta e exatamente a definicao da ordem em que as mercadorias serao alocadas (4).Definida esta ordem, o algoritmo tenta alocar os produtos nos veıculos que ja receberam alguma carga (5).Caso seja possıvel, o produto e alocado no primeiro veıculo que suporte seu peso, volume e area (6). Casocontrario, e dado inıcio ao processo de alocacao de mercadorias em um novo veıculo qualquer da frota (7).O processo e repetido ate que todos os produtos tenham sido alocados (3).

A heurıstica em questao foi, intencionalmente, implementada de um modo pouco inteligente. Issofoi feito justamente para tentar chegar a solucoes proximas daquelas encontradas nas empresas onde a res-ponsabilidade de alocacao dos produtos e dos proprios carregadores que, sem planejamento e organizacao,acabam nao chegando a boas solucoes.

Apesar de bem ineficiente, esta estrategia gulosa implementada nao esta distante das alocacoes feitasmanualmente, sem nenhum tipo de planejamento. E para que se possa ter uma ideia de como essa naomuito rara situacao pode representar um desperdıcio significante, foram selecionadas algumas instancias daempresa interessada no trabalho e alguns resultados comparando o modelo proposto e essa heurıstica seraoapresentados no capıtulo a seguir.

6. Resultados ComputacionaisPara confirmar a corretude dos algoritmos apresentados e viabilizar o calculo de uma estimativa da

economia atingida com a implementacao do modelo criado, algumas instancias da empresa interessada foramtestadas. Essas instancias, como a maioria das empresas de grande porte, nao apresentam grandes variacoesnas dimensoes dos produtos, estando estas sempre entre 0,50 e 2,00 metros. As dimensoes e capacidades dosveıculos disponıveis, ja descritas na secao (2), sao identicas aquelas encontradas nas grandes transportadorasdo paıs. Foi considerada uma quantidade padrao de 30 produtos de cada tipo por programa, ja que clientesfrequentes raramente fazem pedidos demasiadamente grandes, ate porque normalmente o onus da entregarecai sobre a empresa. Os parametros que variam nas instancias testadas e os valores que elas assumem saoos seguintes:

• Tipos de produtos diferentes: 3 tipos nas instancias pequenas e 5 nas grandes.


• Dimensoes e pesos dos produtos: variam para cada tipo de produto. Para facilitar a exposicao dosresultados, esses produtos recebem aqui tres classificacoes em relacao ao seu porte:

– Pequeno: dimensoes entre 0.50 e 1.00 metros e peso ate 5 toneladas;– Medio: dimensoes entre 1.00 e 1.50 metros e peso entre 5 e 10 toneladas;– Grande: dimensoes entre 1.50 e 2.00 metros e peso entre 10 e 15 toneladas.

• Quantidade total de produtos: 90 unidades quando sao considerados 3 tipos diferentes de produtose 150 unidades quando sao considerados 5.

Os testes foram executados considerando todas as restricoes possıveis, entretanto as instancias foramcriadas de modo a evitar problemas como a falta de produtos em estoque ou a falta de determinado tipo deveıculo na transportadora. Os produtos foram considerados com status obrigatorio para que se garanta aalocacao de todos eles e haja justica na comparacao dos resultados. Quanto a funcao objetivo, buscou-seminimizar sempre a soma das cargas mortas em relacao ao peso e ao volume, ja que essa e a situacao maiscomum entre as grandes empresas brasileiras, inclusive a empresa interessada no trabalho.

A tabela a seguir apresenta uma comparacao entre os resultados atingidos pelos algoritmos imple-mentados para as instancias testadas e, adiante, o significado de cada uma de suas colunas e explicado.

Produtos Heurıstica Modelo

# |P | Porte WT VT CMP CMV WT VT CMP CMV

90 3 Pequeno 291 73.87 21 68.51 282 69.91 12 64.55

90 3 Medio 774 221.14 54 199.86 733 209.20 13 187.92

90 3 Grande 1274 395.71 104 340.74 1209 358.53 29 303.56

150 5 Pequeno 486 129.79 36 121.39 462 122.91 12 114.50

150 5 Medio 1329 408.34 129 374.21 1224 361.83 24 327.71

150 5 Grande 2123 642.60 173 553.50 1966 559.33 16 470.23

Tabela 1. Resultados Encontrados pela Heurıstica e pelo Algoritmo Exato Implementados

Na tabela exposta sao informados inicialmente os parametros dos produtos a serem alocados quesao o numero total de produtos, a quantidade de tipos de produtos diferentes e a classificacao em que eles seencontram. E entao sao apresentadas, em relacao ao peso e ao volume, a capacidade total e a carga morta dafrota utilizada em ambos os algoritmos.

Mostrados os resultados alcancados pelos algoritmos, nas tabelas abaixo pode ser vista a economiaque seria gerada pela aplicacao do modelo apresentado na alocacao dos produtos das instancias testadas.

Instancias 1 2 3 4 5 6Heurıstica 291 774 1274 486 1329 2123

Modelo 282 733 1209 462 1224 1966

Economia 3.09% 5.29% 5.10% 4.94% 7.90% 7.39%

Instancias 1 2 3 4 5 6Heurıstica 73.87 221.14 395.71 129.79 408.34 642.60

Modelo 69.91 209.20 358.53 122.91 361.83 559.33

Economia 5.36%% 5.40% 9.40% 5.30% 11.39% 12.96%

Tabela 2. Economia Gerada pelo Modelo em Relacao ao Peso e ao Volume


A economia apresentada foi calculada comparando a capacidade total dos caminhoes fretados nosdois algoritmos. O calculo foi realizado dessa forma pelo fato do valor pago a transportadora ser, na maioriadas vezes, referente somente a capacidade dos caminhoes utilizados e a distancia por esses percorrida.

Com os testes realizados, pode ser percebido que quanto maior os parametros envolvidos no pro-blema, maior e tambem a economia proporcionada pelo algoritmo implementado. Em outras palavras pode-se dizer que com o aumento das instancias, isto e, o aumento da quantidade e tipos de produtos e veıculos,cresce tambem a necessidade de um software como esse.

Foi visto que com a utilizacao do modelo ora apresentado, a economia por parte das empresas contra-tantes podera atingir valores significantes. Vale mencionar ainda, que alem da economia direta mostrada nosresultados acima, pode-se esperar tambem uma diminuicao nos gastos com danos nos produtos e veıculos,ja que no modelo implementado o espacamento mınimo e o empilhamento maximo dos produtos sao respei-tados, alem de se buscar sempre a distribuicao equilibrada dos produtos ao longo dos veıculos.

Para a empresa interessada no trabalho, estima-se uma alta economia, uma vez que atualmente aalocacao dos seus produtos na frota transportadora e feita manualmente e a melhor alocacao dos produtosfatalmente implicara em uma reducao dos custos dessa.

As instancias testadas juntamente com os resultados detalhados para ambos os algoritmos estaraodisponıveis, na ocasiao do XLI SBPO, no sıtio do primeiro autor (www.dcc.ufmg.br/∼gomide/pet).

7. Conclusao e Trabalhos FuturosO desenvolvimento do trabalho e os bons resultados apresentados tornou visıvel que, por se tratar

de um problema tao complexo (NP-difıcil), em empresas de medio e grande porte, e indispensavel o usode um software para a alocacao dos produtos na frota transportadora, tamanha e a economia que o mesmopode proporcionar. Isso pode ser visto com clareza nos resultados apresentados em que o modelo propostosuperou em ate 10% a heurıstica que simula o processo empregado atualmente nessas empresas.

Contrariando as expectativas iniciais, o algoritmo exato implementado como um problema de pro-gramacao inteira mista se mostrou suficiente para atender as solicitacoes das grandes empresas do paıs. Issoporque essas empresas, em geral, apresentam poucas variacoes nas dimensoes dos produtos a serem aloca-dos, as embalagens usadas sao de tamanhos bem pequenos comparados aos compartimentos de alocacao eainda, porque as principais transportadoras disponibilizam poucos tipos diferentes de veıculos para esse tipode transporte. Desse modo abandonou-se a ideia da elaboracao de algoritmos aproximados, ja que com aeficiencia apresentada pelo algoritmo exato, a implementacao desses nao faria mais sentido.

Dando continuidade ao projeto, dois trabalhos futuros sao almejados:1. Pretende-se implementar um algoritmo de montagem de modo que, alem da alocacao dos produtos

na frota, o software possa precisar o posicionamento exato dos produtos nos veıculos;2. E, a fim de tornar o modelo mais generico, e pretendido ainda uma remodelagem do problema

de modo que possa ser considerado tambem o empilhamento de produtos diferentes, caso seja deinteresse da empresa solicitante.

Referencias

Alvarenga, G. B. (2005). Um algoritmo hıbrido para os problemas de roteamento de veıculos estatico edinamico com janela de tempo. Tese de Doutorado, Departamento de Ciencia da Computacao, Universi-dade Federal de Minas Gerais, Belo Horizonte-MG, Brasil.

Bard, J. F., Kontoravdis, G., Yu, G. (2002). A branch-and-cut procedure for the vehicle routing problem withtime windows. Transportation Science, 36(2), p. 250-269.

Feo, T. A., Resende, M. G. C. (1995). Greedy randomized adaptive search procedures. Journal of GlobalOptimization, n. 6, p. 109-133.


Li, K., Cheng, K. H. (1990). A generalized harmonic algorithm for on-line multi-dimensional bin packing.TR UH-CS-90-2, University of Houston.

Li, K., Cheng, K. H. (1990). On three-dimensional packing. SIAM Journal on Computing, 19, p. 847-867.

Li, K., Cheng, K. H. (1990). Static job scheduling in partitionable mesh connected systems. Journal ofParallel and Distributed Computing, 10, p. 152-159.

Li, K., Cheng, K. H. (1992). Heuristic algorithms for on-line packing in three dimensions. Journal ofAlgorithms, 13, p. 589-605.

Longo, H. J. (2004). Tecnicas para Programacao Inteira e Aplicacoes em Problemas de Roteamento deVeıculos. Departamento de Informatica, PUC-Rio, Rio de Janeiro-RJ, Brasil.

Martello, S., Pisinger, D., Vigo, D. (2000). The three-dimensional bin packing problem. Operations Rese-arch, Mar/Apr, v. 48, p. 256-267.

Miyazawa, F. K. (1993). Algoritmos de empacotamento tridimensional: novas estrategias e analises dedesempenho. Dissertacao de Mestrado. Universidade de Sao Paulo IME-USP, Sao Paulo-SP, Brasil.

Miyazawa, F. K. (1997). Algoritmos de aproximacao para problemas de empacotamento. Tese de Douto-rado, Universidade de Sao Paulo IME-USP, Sao Paulo-SP, Brasil.

Miyazawa, F. K., Wakabayashi, Y. (1998). Approximation algorithms for the orthogonal z-oriented 3-Dpacking problem. SIAM Journal on Computing.

Miyazawa, F. K., Wakabayashi, Y. (1994). Three-dimensional packing algorithms with asymptotic perfor-mance analysis (abstract). XV International Symposium on Mathematical Programming, Ann Arbor,Michigan, EUA, p. 213.

Miyazawa, F. K., Wakabayashi, Y. (1997). An algorithm for the three-dimensional packing problem withasymptotic performance analysis. Algorithmica, 18, p. 122-144.

Silva, J. L. C., Soma, N. Y. (2003). Um algoritmo polinomial para o problema de empacotamento de binstridimensionais com estabilidade estatica da carga. Pesquisa Operacional, Brasil, v. 23, p. 79-98.


Documents

Um Modelo de Programaçao Inteira Mista para uma ... · foi modelado como um problema de programação inteira mista e resolvido pelo CPLEX. O modelo proposto foi testado usando