Criação de Algoritmo para Octave e Explicação

Solução Matemática para Otimização de Rotas em Logística May 8 2024 1 Modelagem Matemática Vamos começar representando os pontos de entrega como vetores no plano cartesiano Suponha que tenhamos três pontos de entrega P1x1 y1 P2x2 y2 e P3x3 y3 Podemos escrever esses pontos como vetores P1 x1 y1 P2 x2 y2 P3x3 y3 Agora vamos calcular a matriz de distâncias entre cada par de pontos de entrega A distância entre dois pontos Pi e Pj é dada pela fórmula da distância euclidiana dij sqrtxj xi2 yj yi2 Vamos calcular as distâncias d12 d13 e d23 d12 sqrtx2 x12 y2 y12 d13 sqrtx3 x12 y3 y12 d23 sqrtx3 x22 y3 y22 Substituindo os valores conhecidos dos pontos podemos calcular as distâncias d12 sqrt212 4 32 sqrt12 12 sqrt2 d13 sqrt512 132 sqrt42 22 sqrt16 4 sqrt20 d23 sqrt522 142 sqrt32 32 sqrt9 9 sqrt18 Portanto a matriz de distâncias D será D 0 sqrt2 sqrt20 sqrt2 0 sqrt18 sqrt20 sqrt18 0 2 Análise de Rotas Agora para analisar as rotas podemos calcular as direções e distâncias entre os pontos de entrega usando produtos de vetores e conceitos de geometria analítica Suponha que queremos calcular a rota do veículo que parte do ponto P1 e segue para P2 Podemos representar essa rota como o vetor diferença entre P2 e P1 overrightarrowP1P2 x2 x1 y2 y1 Substituindo os valores conhecidos dos pontos obtemos overrightarrowP1P2 21 43 1 1 Agora podemos calcular a magnitude deste vetor para obter a distância entre os pontos P1 e P2 overrightarrowP1P2 sqrt12 12 sqrt1 1 sqrt2 Portanto a distância entre os pontos P1 e P2 é sqrt2 Podemos seguir o mesmo procedimento para calcular as distâncias e direções entre outros pares de pontos de entrega utilizando vetores correspondentes Este processo nos permite determinar as distâncias e direções entre os pontos de entrega o que é essencial para identificar as rotas mais eficientes para cada veículo de transporte 3 Otimização da Alocação Para otimizar a alocação de veículos de transporte usaremos combinações lineares e transformações lineares Suponha que tenhamos m veículos de transporte e n pontos de entrega Podemos representar a alocação de veículos como um vetor v de tamanho n onde cada componente vi representa a quantidade de veículos alocados para o ponto de entrega Pi Por exemplo se v 2 1 3 isso significa que dois veículos estão alocados para o ponto P1 um veículo para o ponto P2 e três veículos para o ponto P3 Agora vamos considerar a matriz de distâncias D onde dij representa a distância entre os pontos Pi e Pj D 0 sqrt2 sqrt20 sqrt2 0 sqrt18 sqrt20 sqrt18 0 Para calcular a distância total percorrida pela frota de veículos usaremos o produto escalar entre o vetor de alocação v e a matriz de distâncias D Distância Total v cdot D v1 cdot D1 v2 cdot D2 vn cdot Dn Onde Di representa a iésima coluna da matriz de distâncias Vamos usar como exemplo o vetor de alocação v 2 1 3 que significa que temos 2 veículos alocados para P1 1 veículo para P2 e 3 veículos para P3 Distância Total 2 cdot 0 sqrt2 sqrt20 1 cdot sqrt2 0 sqrt18 3 cdot sqrt20 sqrt18 0 Calculando cada produto escalar e somandoos obtemos a distância total percorrida pela frota de veículos Após calcular a distância total podemos ajustar o vetor de alocação v de forma a minimizar essa distância sujeita a restrições de capacidade e tempo 4 Implementação de Algoritmos Para encontrar a alocação ideal de veículos de transporte implementaremos algoritmos de otimização baseados nos conceitos de álgebra linear e geometria analítica Uma abordagem comum é usar algoritmos de otimização linear ou programação inteira Neste caso usaremos a programação inteira para resolver o problema de alocação de veículos Suponha que queremos minimizar a distância total percorrida pela frota de veículos sujeita a restrições de capacidade e tempo Podemos formular o problema como um problema de programação inteira da seguinte forma Minimizar Distância Total sumi1n sumj1n vi cdot dij Sujeito a sumi1n vi m vi geq 0 Onde vi é o número de veículos alocados para o ponto de entrega Pi dij é a distância entre os pontos de entrega Pi e Pj m é o número total de veículos disponíveis Este problema pode ser resolvido usando bibliotecas de otimização como PuLP em Python que permite formular e resolver problemas de programação inteira Agora vamos considerar um exemplo simples com três pontos de entrega e dois veículos disponíveis Suponha que tenhamos a seguinte matriz de distâncias D 0 2 4 2 0 3 4 3 0 Nosso objetivo e minimizar a distˆancia total percorrida pela frota de veıculos sujeita a restricao de que cada ponto de entrega deve ser atendido por pelo menos um veıculo Podemos implementar esse problema de alocacao de veıculos em Python usando a biblioteca PuLP da seguinte maneira Vou enviar um arquivo separado em Python com um exemplo disso Os graficos e tabelas serao enviados a parte 4