Slide - Logística - 2023-2

Logística PPrroobblleem maass ddee rrootteeaam meennttoo ddee vveeííccuullooss--VVRRPP Modelos matemáticos 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 figura acima, 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/ http://www.din.uem.br/sbpo/sbpo2017/pdf/168823.pdf Algoritmos heurísticos para resolver o VRP:  ALGORITMOS: Christofides, Clarke e Wright A SOLUÇÃO do VRP ABAIXO NÃO É ÓTIMA 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: yi ∈ 0,1  yi = 1 se a facilidade é instalada no local i xij ∈ 0,1  xij = 1 se o cliente j for designado à facilidade i Função objetivo: min Z = dijxij J j=1 I i=1 Restrições: i. xij I i=1 = 1, ∀j ∈ J  o cliente j só é atendido pela facilidade i ii. xij ≤ yi ∀i ∈ I, ∀j ∈ J  o cliente j não pode ser designado à facilidade i se ela não for instalada iii. yi I i=1 = p  p facilidades deverão ser instaladas PLI: ... 4 medianas x[2, 1] 1 0,00616410 x[2, 2] 1 0,00000000 x[2, 3] 1 0,00271825 x[2, 4] 1 0,00997950 x[7, 5] 1 0,00807384 x[7, 6] 1 0,00346320 x[7, 7] 1 0,00000000 x[12, 8] 1 0,00763929 x[12, 9] 1 0,00963040 x[12, 10] 1 0,01117720 x[12, 11] 1 0,01344520 x[12, 12] 1 0,00000000 x[12, 13] 1 0,00791518 x[12, 14] 1 0,00434278 x[12, 15] 1 0,00387660 x[17, 16] 1 0,00217589 x[17, 17] 1 0,00000000 x[17, 18] 1 0,01161790 x[17, 19] 1 0,00836794 x[17, 20] 1 0,01574470 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 dos clientes às facilidades. Variáveis: yi ∈ 0,1  yi = 1 se a facilidade é instalada no local i xij ∈ 0,1  xij = 1 se o cliente j for designado à facilidade i r  distância máxima permitida de um cliente a uma facilidade Função objetivo: min Z = r Restrições: i. xij I i=1 = 1, ∀j ∈ J  o cliente j só é atendido pela facilidade i ii. xij ≤ yi ∀i ∈ I, ∀j ∈ J  o cliente j não pode ser designado à facilidade i se ela não for instalada iii. yi I i=1 = p  p facilidades deverão ser instaladas iv. dijxij I i=1 ≤ r, ∀j ∈ J  que a distância seja menor que r PLI: ... 4 centros i x[4, 1] 1 0,00786360 i x[4, 2] 1 0,00997975 i x[4, 3] 1 0,01229110 i x[4, 4] 1 0,00000000 i x[4, 5] 1 0,01150310 i x[4, 7] 1 0,01213030 i x[8, 6] 1 0,01417850 i x[8, 8] 1 0,00000000 ii x[8, 9] 1 0,00512550 ii x[8, 10] 1 0,00253504 ii x[8, 11] 1 0,01395320 ii x[8, 12] 1 0,00763929 ii x[8, 13] 1 0,01094810 ii x[8, 14] 1 0,01074940 ii x[8, 15] 1 0,01139440 iii x[18, 18] 1 0,00000000 iv x[19, 16] 1 0,00942221 iv x[19, 17] 1 0,00836794 iv 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 ii i x[12, 8] 1 0,007639290 ii x[ 8, 8] 1 0,00000000 ii i x[12, 9] 1 0,009630040 ii x[ 8, 9] 1 0,00512550 ii i x[12, 10] 1 0,011177200 ii x[ 8, 10] 1 0,00525304 ii i x[12, 11] 1 0,013445200 ii x[ 8, 11] 1 0,01395320 ii i x[12, 12] 1 0,000000000 ii x[ 8, 12] 1 0,00763929 ii i x[12, 13] 1 0,007915810 ii x[ 8, 13] 1 0,01094810 ii i x[12, 14] 1 0,004342780 ii x[ 8, 14] 1 0,01074940 ii i 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