Trabalhos

INTRODUÇÃO
Problemas de entrega estão presentes tem diversas aplicações. Quando vamos ao supermercado nos deparamos com diversos produtos oriundos de diferentes cidades, estados até países. Desde hortifrutigranjeiros até computadores e automóveis, somos inundados com mercadorias de diferentes marcas, tipos e fabricantes. Cada um destes fabricantes produz estes produtos em diferentes lugares, sendo obrigados a ter um custo de transporte para que cada um alcance os consumidores. Uma boa parte do custo destas mercadorias está inserido neste transporte e uma redução do mesmo é muito importante, pois beneficia tanto as empresas produtoras, que não precisam gerar tantos gastos, como os consumidores que podem comprar estes produtos com um custo mais razoável. Muito se tem estudado na literatura a respeito de otimizar rotas economizando tempo e combustível. Um dos problemas clássicos e mais estudados a este respeito é o Problema do Caixeiro Viajante. Ele consiste em, dado um conjunto de distâncias, ou tempos de viagem, entre diversas localidades, achar um circuito de comprimento mínimo que, saindo de uma origem, percorra todas as localidades, passando exatamente uma vez em cada localidade e depois voltando para a origem. Este problema, por si só, é muito interessante e tem muitas aplicações teóricas e práticas, mas só leva em consideração as distâncias a serem percorridas. Se quisermos modelar um problema de entrega de mercadorias, onde o tipo e a quantidade destas mercadorias é, além das distâncias, importante para o cálculo total do custo, o Problema do Caixeiro Viajante não é a melhor opção. Existe também, na literatura, um outro problema chamado de Problema de Mínima Latência. Ele consiste em, dado um conjunto de tempos entre diversas cidades (tarefas) calcular o atraso entre o nó origem e o nó atual e seu objetivo, no final, é minimizar o somatório dos atrasos entre todas as localidades envolvidas e a origem. Este problema também é muito interessante e foi