Aula Formulação Logística-2023 1

Logística PPrroobblleem maass ddee rrootteeaam meennttoo ddee vveeííccuullooss--VVRRPP M Mooddeellooss m maatteem mááttiiccooss Uma grande variedade de derivações VRPs podem ser classificados de acordo com suas propriedades no que diz respeito aos pedidos a serem cumpridos, a frota disponível, a estrutura de rota, os objetivos e o planejamento considerado. Uma visão geral destas dimensões é dada na seguinte figura, retirada de Drexl, Michael. "Rich vehicle routing in theory and practice." Logistics Research 5.1-2 (2012): 47-63. https://vehicle-routing-problem.github.io/ https://core.ac.uk/download/pdf/34605432.pdf https://www.researchgate.net/publication/287796502_The_Vehicle_Routing_Problem_State_of_the_Art_Classification_and _Review https://www.youtube.com/watch?v=RabVJKQ_w1g https://www.youtube.com/watch?v=Sb2kz8rI1D4 https://repositorio.ufmg.br/bitstream/1843/NVEA-7GSNPB/1/nari_louise_tenkleytese_corrigida.pdf VVRRPP M Mooddeell –– ddeerriivvaaddoo ddoo m mooddeelloo TTSSPP ddee DDAANNTTZZIIGG Variáveis: para todo veículo k e todo arco ,  se o veículo k percorre a aresta Função objetivo: Restrições: i. O veículo k deve partir do depósito ii. O cliente j é designado a um único veículo k iii. Se o veículo k sai do nó i entçao ele entrou nesse nó iv. A demanda total da rota do veículo k não excede a sua capacidade Q v. Eliminação de sub-rotas isoladas da origem K k 2 , n S C, 2 S ,1 S x S j ijk S i               Exemplo: Seja n = 9, Q = 50, K = 3. As coordenadas geográficas dos 9 clientes são: CLIENTE 1 2 3 4 5 6 7 8 9 0 x 16 23 40 9 97 78 20 71 64 50 y 32 1 65 77 71 24 26 98 55 50 CLIENTE 1 2 3 4 5 6 7 8 9 Demanda 11 35 2 9 3 18 8 10 11 Distâncias/custos entre as cidades: Custo 0 2 3 4 5 6 7 8 9 10 0 0 38 52 18 49 51 38 38 52 14 2 38 0 34 40 45 89 62 7 85 53 3 52 34 0 64 79 95 51 27 104 62 4 18 40 64 0 33 57 55 43 45 26 5 49 45 79 33 0 88 87 52 65 59 6 51 89 95 57 88 0 50 89 37 36 7 38 62 51 55 87 50 0 58 74 34 8 38 7 27 43 52 89 58 0 88 52 9 52 85 104 45 65 37 74 88 0 43 10 14 53 62 26 59 36 34 52 43 0 Veículo 1: x(1,7,1)=x(7,6,1)=x(6,9,1)=x(9,10,1)=x(10,1,1)=1 Veículo 2: x(1,3,2)=x(3,1,2)=1 Veículo 3: x(1,4,3)=x(4,5,3)=x(5,2,3)=x(2,8,3)=x(8,1,3)=1 Custo total: 427 VVRRPP M Mooddeell -- ddeerriivvaaddoo ddoo m mooddeelloo TTSSPP ddee M MTTZZ Variáveis: para todo veículo k e todo arco ,  se o veículo k percorre a aresta é a demanda acumulada no nó i Função bjetivo: Restrições: i. O veículo k deve partir do depósito ii. O cliente j é designado a um único veículo k iii. Se o veículo k sai do nó i então ele entrou nesse nó iv. A demanda total da rota do veículo k não excede a sua capacidade Q i. Eliminação de sub-rotas Algoritmos heurísticos para resolver o VRP:  ALGORITMOS: Christofides, Clarke e Wright PPrroobblleem maass ddee llooccaalliizzaaççããoo ddee ffaacciilliiddaaddeess ((FFaacciilliittyy llooccaattiioonn pprroobblleem m)) ii -- M Mooddeelloo m maatteem mááttiiccoo ddee pp--m meeddiiaannaass ((m miinniissuum m pprroobblleem m)) Objetivo: Localização de p facilidades e a designação de clientes às facilidades de modo a minimizar a soma das distâncias (distância total) às facilidades. Variáveis:  se a facilidade é instalada no local i  se o cliente j for designado à facilidade i Função objetivo Restrições i. O cliente j só é atendido pela facilidade i ii. o cliente j não pode ser designado à facilidade i se ela não for instalada iii. p facilidades deverão ser instaladas 4 medianas i x[2, 1] 1 0,00616410 ii x[2, 2] 1 0,00000000 iii x[2, 3] 1 0,002718250 iv x[2, 4] 1 0,009979750 i x[7, 5] 1 0,008037840 ii x[7, 6] 1 0,003436280 iii x[7, 7] 1 0,000000000 iv x[12, 8] 1 0,007639290 i x[12, 9] 1 0,009630400 ii x[12, 10] 1 0,011177200 iii x[12, 11] 1 0,013445200 iv x[12, 12] 1 0,000000000 i x[12, 13] 1 0,007915180 ii x[12, 14] 1 0,003442780 iii x[12, 15] 1 0,003876600 iv x[17, 16] 1 0,002175890 i x[17, 17] 1 0,000000000 ii x[17, 18] 1 0,011617900 iii x[17, 19] 1 0,008367940 iv x[17, 20] 1 0,015744700 Distância Total 0,126159680 Distância Máxima 0,015744700 iiii -- M Mooddeelloo m maatteem mááttiiccoo ddee pp--cceennttrrooss ((m miinniim maaxx pprroobblleem m)) Objetivo: Localização de p facilidades e a designação de clientes às facilidades de modo a minimizar a máxima distância de clientes às facilidades. Variáveis:  se a facilidade é instalada no local i  se o cliente j for designado à facilidade i r  distância máxima permitida de um cliente a uma facilidade Função objetivo Restrições i. O cliente j só é atendido pela facilidade i ii. o cliente j não pode ser designado à facilidade i se ela não for instalada iii. p facilidades deverão ser instaladas iv. que a distância seja menor que r 4 centros i x[4, 1] 1 0,00786360 ii x[4, 2] 1 0,00997975 iii x[4, 3] 1 0,01229110 iv x[4, 4] 1 0,00000000 i x[4, 5] 1 0,01150310 ii x[4, 7] 1 0,01213030 i x[8, 6] 1 0,01417850 ii x[8, 8] 1 0,00000000 iii x[8, 9] 1 0,00512550 iv x[8, 10] 1 0,00525304 i x[8, 11] 1 0,01395230 ii x[8, 12] 1 0,00763929 iii x[8, 13] 1 0,01094810 iv x[8, 14] 1 0,01074940 i x[8, 15] 1 0,01139440 ii x[18, 18] 1 0,00000000 i x[19, 16] 1 0,00942221 ii x[19, 17] 1 0,00836794 iii x[19, 19] 1 0,00000000 iv x[19, 20] 1 0,01019790 Distância Total 0,16099733 Distância Máxima 0,01417850 4 medianas 4 centros i x[2, 1] 1 0,006016410 y[ 2] 1 i x[ 4, 1] 1 0,00786360 y[ 4] 1 i x[2, 2] 1 0,000000000 y[ 7] 1 i x[ 4, 2] 1 0,00997975 y[ 8] 1 i x[2, 3] 1 0,002718250 y[12] 1 i x[ 4, 3] 1 0,01229110 y[18] 1 i x[2, 4] 1 0,009979750 y[17] 1 i x[ 4, 4] 1 0,00000000 y[19] 1 ii x[7, 5] 1 0,008073840 i x[ 4, 5] 1 0,01150310 ii x[7, 6] 1 0,003436280 i x[ 4, 7] 1 0,01213030 ii x[7, 7] 1 0,000000000 ii x[ 8, 6] 1 0,01417850 iii x[12, 8] 1 0,007639290 ii x[ 8, 8] 1 0,00000000 iii x[12, 9] 1 0,009630040 ii x[ 8, 9] 1 0,00512550 iii x[12, 10] 1 0,011177200 ii x[ 8, 10] 1 0,00525304 iii x[12, 11] 1 0,013445200 ii x[ 8, 11] 1 0,01395320 iii x[12, 12] 1 0,000000000 ii x[ 8, 12] 1 0,00763929 iii x[12, 13] 1 0,007915810 ii x[ 8, 13] 1 0,01094810 iii x[12, 14] 1 0,004342780 ii x[ 8, 14] 1 0,01074940 iii x[12, 15] 1 0,003876600 ii x[ 8, 15] 1 0,01139440 iv x[17, 16] 1 0,002175890 iii x[18, 18] 1 0,00000000 iv x[17, 17] 1 0,000000000 iv x[19, 16] 1 0,00942221 iv x[17, 18] 1 0,011619700 iv x[19, 17] 1 0,00836794 iv x[17, 19] 1 0,008367940 iv x[19, 19] 1 0,00000000 iv x[17, 20] 1 0,015744700 iv x[19, 20] 1 0,01019790 Distância Total 0,126159680 Distância Total 0,16099733 Distância Máxima 0,015744700 Distância Máxima 0,01417850