Heurística de Clarke e Wright

A heurística de Clarke e Wright (1964) surge, no campo da logística, como factor de simplicidade e flexibilidade na formulação da programação de rotas, no âmbito da gestão de transporte. Existem vários estudos que demonstram diferentes formas possíveis de programação de rotas. Para a sua implementação, são necessários conhecimentos matemáticos bastante complexos, restringindo deste modo, a sua utilização em algumas empresas (Carvalho, 2002, p. 206).

Esta heurística baseia-se na troca de conjuntos de rotas em cada ponto de chegada, caso seja possível ou desejável, por forma a melhorar o desempenho global. Por conseguinte, uma das designações atribuída à formulação é a heurística de poupança de Clarke e Wright (Carvalho, 2002, p. 207).

A formulação supracitada demonstra grande utilidade para frotas homogéneas, uma vez que admite a minimização da frota e da distância percorrida. No entanto, a heurística não possui a capacidade de manipulação de dados referentes a frotas heterogéneas, por não considerar os custos fixos e directos associados à variabilidade dos veículos e das distâncias percorridas (Teixeira, 2002, p. 4).

Desenvolvimento do método

Primeiramente, são definidas as restrições básicas do problema, como por exemplo: por cada rota apenas é atendido um cliente. Com base nestas restrições, deve-se garantir a menor distância possível no atendimento de todos os clientes. Por conseguinte, elabora-se uma lista com as rotas (de ida e volta) desde o armazém até cada dois clientes, e calculam-se os custos inerentes às respectivas deslocações ( S i j {\displaystyle S_{ij}} ). 

                                                            
  
    
      
        
          S
          
            i
            j
          
        
        =
        
          d
          
            0
            i
          
        
        +
        
          d
          
            0
            j
          
        
        −
        
          d
          
            i
            j
          
        
      
    
    {\displaystyle S_{ij}=d_{0i}+d_{0j}-d_{ij}}

Sendo, d 0 i {\displaystyle d_{0i}} e d 0 j {\displaystyle d_{0j}} representantes da distância entre o armazém e os clientes i e j, respectivamente, e dij a distância entre os dois clientes.

Em suma, esta lista é organizada de forma decrescente de custos, sendo que a solução óptima corresponde ao custo total mínimo (Miura, 2008, p. 15-18) e (Teixeira, 2002, p. 5-6).

Referências

  • CARVALHO, José Mexia Crespo de – Logística. 3ª ed. Lisboa: Sílabo, 2002. ISBN 978-9-726-18279-5
  • MIURA, Marcos - Modelagem heurística no problema de distribuição de cargas fraccionadas de cimento [Em linha]. São Paulo: [s.n.], 2008. [Consult. em 24 Mar. 2009]. 84 p. Dissertação apresentada à Escola Politécnica da Universidade de São Paulo para obtenção do título de mestre em engenharia. Disponível em WWW: <URL:http://www.teses.usp.br/teses/disponiveis/3/3148/tde-17112008-115017/>
  • TEIXEIRA, Roberto Gomes; CUNHA, Claudio Barbieri da - Heurísticas para o problema de dimensionamento e roteirização de uma frota heterogénea utilizando o algoritmo out-of-kilter [Em linha]. São Paulo: Escola Politécnica da Universidade de São Paulo, 2002. [Consult. em 24 Mar. 2009]. Disponível em WWW: <URL:http://www.ptr.poli.usp.br/ptr/docentes/cbcunha/files/heuristicas_dimens_roteir_OOK_CBC.pdf>

Ver também

Ícone de esboço Este artigo sobre Logística é um esboço. Você pode ajudar a Wikipédia expandindo-o.
  • v
  • d
  • e