| Soluções do problema de caminho mínimo são largamente utilizadas por empresas transportadoras para decidir as rotas de entrega dos produtos transportados. Entretanto, o aumento da frota de veículos e principalmente as condições das vias pelas quais trafegam tem aumentado bastante o tempo de deslocamento por entre essas rotas de forma irregular e incerta. Devido a essa variabilidade nos tempos de atraso, transportadoras que trabalham com prazos rígidos de entrega, sendo suscetíveis a multas, ou que transportam produtos perecíveis acabam por acumular grandes prejuízos.
Como esse novo problema tem se tornado frequente, e por sua importância prática, desenvolvemos uma nova abordagem mais precisa que leva em conta o possível risco de descumprimento de um prazo máximo, dentro de uma margem de confiança, na seleção da melhor rota disponível.
Mostramos uma formulação estocástica inteira do problema de caminho mínimo com restrições de atraso máximo. Nesta formulação, nos utilizamos do conceito de “cenários de simulação” para abstrair as diversas configurações de atrasos de uma malha viária gerada sob a forma de um grafo. A cada aresta, para cada cenário, associamos uma variável de Poisson que representa o atraso daquela aresta naquele cenário. Com esses valores, e com a margem de confiança desejada, montamos as restrições de atraso máximo da formulação.
Exibimos ainda os resultados preliminares obtidos com algumas simulações realizadas e indicamos algumas possíveis estratégias de tunning que possam ser aplicadas para acelerar a obtenção das soluções ótimas do problema na formulação proposta.
Apoio: UFC e CNPq. |