Um algoritmo para roteirização com restrições de tempos de viagens e de trabalho

Abstract

O uso de restrições de tempo em problemas de Cobertura de Arcos ou Nós representa, para todos os modelos que agregam a roteirização, uma enorme dificuldade na obtenção de seus resultados. A motivação para este estudo surgiu, por meio de uma empresa gaúcha, de um caso específico de determinação de um roteiro mínimo realizado por um veículo para visitar determinados lugares que estão restritos ao tempo, correspondente a jornada de trabalho, gasto não só para se chegar a eles como também o da visita. Este trabalho apresenta um modelo baseado no interessante método de Clarke-Wright que desenvolve um processo iterativo do qual permite a rápida seleção de uma rota ótima ou proxima à òtima respeitando as restrições de tempo. A estruturação do modelo está baseada: - na criação de dois arquivos: o das viagens (representado pelas arestas) e o das visitas (pelos nós); - na determinação da rota mais curta entre cada par de nós que compõe uma aresta - para esse sistema foi utilizado o Algoritmo de Floyd. Ao longo do trabalho são descritos as caracterizações que norteiam esse problema e como foram introduzidas no modelo. Os arquivos e os programas elaborados estão em linguagem Pascal. Á medida que caracterizarmos e tivermos bem definidos outros casos de roteirização, esse modelo será passível de aplicação, podendo ser utilizado em microcomputadores do tipo PC/AT ou compatível.