Com a calibração de cada parâmetro e considerando os diferentes cenários men- cionados para o problema foram realizados os testes para verificar a eficiência da ALNS para resolver os diferentes problemas. Nas Tabelas 20 e 21 é apresentada uma análise quantitativa dos resultados obtidos, em relação ao custo da solução, dado pelo valor da FO, pela ALNS sem a aplicação do ruído e com a aplicação do ruído, respectivamente. Em ambas as tabelas são apresentados, para cada cenário e problema da empresa G00, o valor médio da FO (FO Média), a porcentagem do desvio padrão (Desvio P (%)) e o valor da FO da melhor solução (Melhor FO) obtida dentre as dez execuções. Uma análise qualitativa
das soluções, que leva em consideração o número de jornadas, de duplas pegadas e de horas extras contidas na solução, é apresentada ao realizar as comparações com outros métodos da literatura.
Tabela 20 – FO média, Desvio P (%), valor da FO da melhor solução obtida e seu deta- lhamento para os dias úteis, sábado e domingo da empresa G00 nos quatro cenários distintos considerados, obtidos pela ALNS sem a aplicação do ruído Cenário Dados Segunda Terça Quarta Quinta Sexta Sábado Domingo
1T V600 FO Média 1.220.118 1.172.848 1.400.409 1.523.416 1.442.174 1.063.718 572.884 Desvio P (%) 0,943 0,535 0,747 0,645 0,447 0,919 0,451 Melhor FO 1.204.500 1.162.832 1.385.804 1.505.896 1.433.608 1.050.576 565.812 1T V5.000 FO Média 1.280.396 1.217.594 1.447.686 1.584.688 1.484.026 1.140.896 603.150 Desvio P (%) 0,713 0,601 0,357 0,783 0,402 0,820 0,053 Melhor FO 1.256.628 1.202.692 1.440.876 1.565.016 1.471.920 1.127.876 602.836 2T V600 FO Média 1.224.303 1.161.067 1.395.434 1.520.991 1.436.904 1.065.081 569.930 Desvio P (%) 0,678 0,336 0,409 0,485 0,484 0,602 0,739 Melhor FO 1.210.492 1.152.376 1.389.968 1.510.252 1.425.480 1.055.260 565.608 2T V5.000 FO Média 1.270.998 1.208.713 1.446.612 1.587.650 1.486.715 1.125.628 603.987 Desvio P (%) 0,907 0,500 0,524 0,662 0,624 0,911 0,450 Melhor FO 1.252.288 1.200.932 1.435.604 1.573.848 1.471.984 1.108.708 599.496
Tabela 21 – FO média, Desvio P (%), valor da FO da melhor solução obtida e seu deta- lhamento para os dias úteis, sábado e domingo da empresa G00 nos quatro cenários distintos considerados, obtidos pela ALNS com a aplicação do ruído Cenário Dados Segunda Terça Quarta Quinta Sexta Sábado Domingo
1T V600 FO Média 1.221.488 1.175.690 1.400.736 1.527.848 1.440.438 1.067.940 572.970 Desvio P (%) 0,431 0,426 0,714 0,526 0,449 1,004 0,481 Melhor FO 1.211.836 1.169.944 1.384.688 1.514.668 1.431.040 1.053.000 565.224 1T V5.000 FO Média 1.285.999 1.216.303 1.443.449 1.580.489 1.483.530 1.135.152 602.781 Desvio P (\%) 0,974 0,605 0,565 0,719 0,488 0,802 0,654 Melhor FO 1.261.280 1.201.956 1.431.336 1.564.068 1.475.376 1.126.256 599.212 2T V600 FO Média 1.218.576 1.160.093 1.397.439 1.526.757 1.441.528 1.075.894 569.677 Desvio P (%) 0,759 0,533 0,353 0,618 0,527 0,989 0,763 Melhor FO 1.203.568 1.153.616 1.388.460 1.513.188 1.431.724 1.055.320 564.696 2T V5.000 FO Média 1.269.999 1.211.082 1.448.822 1.582.646 1.481.879 1.132.003 603.574 Desvio P (%) 0,573 0,546 0,344 0,403 0,633 0,908 0,726 Melhor FO 1.257.688 1.197.704 1.439.944 1.575.324 1.469.816 1.117.452 594.592
Ao analisar o desempenho do ALNS para os diferentes cenários, foi realizada uma comparação dos resultados obtidos pela ALNS com os resultados obtidos por diferentes métodos da literatura que utilizaram o mesmo conjunto de dados de entrada e configuração de cenário. Além disso, os resultados dos cenários foram comparados com a escala adotada pela empresa.
Considerando o primeiro Cenário, o 1T V600, os resultados obtidos pela heurística
foram comparados com os resultados obtidos pelos métodos GRASP (SILVA; CUNHA, 2010), VNS-VLNS (REIS; SILVA, 2012), Matheurística (SOUZA, 2014) e GLS (SILVA; SILVA, 2015). Na Tabela 22 são apresentados os resultados obtidos nestes testes. Na última linha da Tabela 22 é apresentado o gap, dado pela diferença (em %) entre o
Capítulo 5. Experimentos Computacionais 80
valor da FO da melhor solução já encontrada e o valor da FO da solução retornada pela ALNS, nas respectivas instâncias e cenários. O gap é obtido pela expressão gap = (salns− smelhor)/smelhor. Um valor negativo para o gap (em verde) significa que a ALNS
superou, em determinada porcentagem, os melhores resultados conhecidos, enquanto um valor positivo (em vermelho) significa que a ALNS gerou resultados, em determinada porcentagem, piores que os melhores conhecidos. Os resultados obtidos pelas duas versões da heurística ALNS não são comparados entre si. Dessa forma, um valor em negrito para o valor da FO representa a melhor solução obtida para o problema. Quando um valor encontra-se em negrito e itálico (aplicável apenas nas versões da ALNS), significa que o método gerou uma solução pior que a ALNS concorrente, mas ainda sim melhor que a melhor solução alcançada por outro método, até então. Um valor em itálico representa a segunda melhor solução alcançada. Todos estes valores destacados encontram-se em cinza. A escolha da melhor versão da heurística ALNS é realizada a partir dos respectivos valores do gap.
Tabela 22 – Comparação dos resultados obtidos pela ALNS com as soluções obtidas pelos métodos GRASP, VNS-VLSN, Matheurística, GLS e com a solução adotada pela empresa, no cenário 1T V600
Dados Segunda Terça Quarta Quinta Sexta Sábado Domingo
ALNS FO 1.204.500 1.162.832 1.385.804 1.505.896 1.433.608 1.050.576 565.812 Jorn. 117 113 135 147 141 101 55 DP 21 16 18 16 14 28 10 HE 91:15 96:48 104:11 109:34 105:02 99:04 40:53 ALNSruído FO 1.211.836 1.169.944 1.384.688 1.514.668 1.431.040 1.053.000 565.224 Jorn. 118 114 135 148 140 102 55 DP 19 14 17 17 9 18 9 HE 85:09 89:46 102:02 101:57 106:50 92:30 40:56 GRASP FO 1.264.836 1.265.880 1.462.384 1.564.420 1.510.520 1.131.272 590.716 Jorn. 124 125 144 154 149 111 58 DP 14 7 11 12 10 15 7 HE 68:29 48:40 65:46 71:45 60:30 51:08 27:09 VNS-VLNS FO 1.223.556 1.191.952 1.380.000 1.517.168 1.435.332 1.089.764 562.444 Jorn. 120 117 135 149 141 107 55 DP 19 14 19 17 14 10 7 HE 50:39 56:28 77:30 70:42 70:33 57:21 34:21 Matheurística FO 1.163.884 1.110.504 1.331.296 1.429.740 1.368.232 996.912 528.308 Jorn. 108 104 124 133 127 92 49 DP 95 74 100 107 106 73 38 HE 112:01 111:16 130:22 148:05 144:18 127:58 64:37 GLS FO 1.253.532 1.222.920 1.417.292 1.557.100 1.474.588 1.104.096 581.468 Jorn. 123 120 139 153 145 108 57 DP 23 23 14 22 19 17 9 HE 40:33 38:00 78:43 57:55 54:57 57:54 74:14 Empresa FO 1.364.404 1.322.420 1.518.460 1.651.256 1.576.564 1.253.100 686.468 Jorn. 134 130 149 162 155 124 68 DP 6 3 5 4 1 0 0 HE 86:41 85:55 106:05 120:14 108:11 54:35 26:57 GAP -1,582% -2,504% +0,421% -0,749% -0,120% -3,730% +0,599% GAPruído -0,967% -1,881% +0,340% -0,165% -0,300% -3,491% +0,494%
Para o Cenário 1T V600 que permite que as tripulações realizem até uma troca de
veículo por jornada e adota o peso 600 para as duplas pegadas, mediante uma análise quantitativa, que observa apenas o valor da FO, o método proposto por Souza (2014)
gerou as melhores soluções para todos os problemas testados. No entanto, ao realizar uma análise qualitativa dos resultados, as melhores soluções são totalmente impraticáveis operacionalmente, uma vez que são desejáveis soluções que possuam, no máximo, 20% de jornadas do tipo dupla pegada na escala. Apesar das soluções geradas possuírem uma redução significativa do número de jornadas em relação aos demais métodos, nota-se um aumento bastante expressivo no número de jornadas de dupla pegada, que atinge cerca de até 88% do total de jornadas para a segunda-feira, por exemplo. Essa limitação da quantidade de duplas pegadas é de extrema importância e deve ser considerada, uma vez que as tripulações que realizam este tipo de jornada devem, obrigatoriamente, folgar aos domingos durante o mês. Esta restrição faz parte da a próxima etapa do planejamento do Sistema de Transporte Público, denominada Rodízio de Tripulações, descrito. Se houver um grande número de duplas folgando aos domingos no mês em planejamento, se faz necessário a contratação de tripulações do tipo folguistas, para realizar as jornadas que ficarem em aberto. A economia gerada na programação diária, com a redução de jornadas, é comprometida na etapa posterior, com a contratação de novas tripulações. Sendo assim, é importante analisar as soluções cujo número de jornadas do tipo dupla pegada é inferior a 20%. Tais soluções são destacadas em negrito e/ou itálico, para o cenário 1T V600. Por
esta análise, a heurística ALNS, em ambas as versões, foi capaz de gerar as melhores soluções para os problemas da segunda-feira, terça-feira, quinta-feira, sexta-feira e sábado. Para a quarta-feira e domingo, as soluções obtidas pela ALNS foram, no máximo, 0,4% e 0,6% piores que as melhores soluções, geradas por Reis e Silva (2012). Também nota-se que as soluções geradas pela ALNS, na maioria dos problemas, são caracterizadas por apresentar um número inferior de jornadas em relação às soluções geradas pelos demais métodos, com exceção daquelas obtidas por Souza (2014). Essa redução é explicada pelo aumento de horas extras na solução, que representa o trade-off do problema: ao diminuir o número de jornadas, é natural que o número de horas extras aumente, uma vez que um número menor de tripulações deve realizar as mesmas tarefas.
No cenário de testes 1T V5.000, caracterizado por permitir até uma troca de veículos
por jornada e peso 5.000 para as duplas pegadas, os resultados gerados pela heurística foram comparados com os resultados obtidos pelos métodos VNS-VLSN (REIS; SILVA, 2012), Matheurística (SOUZA, 2014) e GLS (SILVA; SILVA, 2015), visto que reúnem as mesmas configurações. Os resultados são apresentados na Tabela 23.
Como pode-se notar na Tabela 23, há uma redução no número de jornadas do tipo dupla pegada nas soluções geradas, se comparadas às soluções geradas no cenário anterior. Esta foi a estratégia adotada para que as heurísticas gerassem soluções contendo o número de duplas pegadas próximas à solução da empresa. Analisando as soluções apresentadas, ambas as versões da heurística ALNS geraram os melhores resultados para os problemas da segunda-feira, terça-feira, quarta-feira, quinta-feira e sábado. A ALNS com a aplicação do ruído também alcançou o melhor resultado para o problema do domingo. Para a sexta-feira,
Capítulo 5. Experimentos Computacionais 82
Tabela 23 – Comparação dos resultados obtidos pela ALNS com as soluções obtidas pelos métodos VNS-VLS, Matheurística, GLS e com a solução adotada pela empresa, no cenário 1T V5.000
Dados Segunda Terça Quarta Quinta Sexta Sábado Domingo
ALNS FO 1.256.628 1.202.692 1.440.876 1.565.016 1.471.920 1.127.876 602.836 Jorn. 120 115 138 151 141 105 57 DP 7 6 7 6 7 11 5 HE 90:07 94:33 107:49 104:14 112:10 95:19 32:39 ALNSruído FO 1.261.280 1.201.956 1.431.336 1.564.068 1.475.376 1.126.256 599.212 Jorn. 122 115 137 151 139 106 56 DP 4 6 7 6 11 9 6 HE 88:40 91:29 109:44 100:17 126:34 88:34 38:23 VNS-VLNS FO 1.270.628 1.213.176 1.471.176 1.583.644 1.471.100 1.152.552 601.296 Jorn. 120 114 140 148 139 109 57 DP 11 11 11 17 12 10 5 HE 65:07 75:44 67:24 77:41 87:55 52:18 27:35 Matheurística FO 1.332.316 1.267.380 1.497.240 1.612.644 1.535.660 1.156.484 605.312 Jorn. 118 114 133 146 140 99 54 DP 26 21 28 25 22 28 11 HE 92:59 93:15 113:30 115:11 106:55 110:21 42:58 GLS FO 1.276.280 1.216.340 1.455.988 1.581.920 1.478.832 1.146.440 601.560 Jorn. 120 116 139 150 142 110 57 DP 12 8 10 13 8 7 5 HE 67:50 68:05 66:37 70:30 78:28 47:40 27:20 Empresa FO 1.390.804 1.335.620 1.540.460 1.668.856 1.580.964 1.253.100 686.468 Jorn. 134 130 149 162 155 124 68 DP 6 3 5 4 1 0 0 HE 86:41 85:55 106:05 120:14 108:11 54:35 26:57 GAP -1,102% -0,864% -1,038% -1,069% +0,056% -1,619% +0,256% GAPruído -0,741% -0,933% -1,722% -1,141% +0,291% -1,792% -0,348%
as soluções obtidas pelas versões da ALNS foram, no máximo, 0,3% piores que a melhor solução gerada por Reis e Silva (2012).
Na prática das empresas, é aceitável que as tripulações realizem, no máximo, uma troca de veículos durante a execução de uma jornada. O processo de troca de condutores por veículo é indesejado e, por isso, evitado, uma vez que dificulta o controle e a supervisão dos veículos quanto a danos materiais que podem ser provocados pelo mal uso do veículo pelos condutores. Diante desse fato, poucos trabalhos consideram mais de uma troca de veículos por jornada, visto que a situação é pouco adotada na prática. Entretanto, este cenário foi estudado para verificar se esta forma de operação pode trazer alguma economia significativa para a empresa.
No Cenário 2T V600, que permite até duas trocas de veículos por jornada e utiliza o
peso 600 para as duplas pegadas, os resultados obtidos pela ALNS foram comparados com os resultados obtidos pelos métodos GRASP (SILVA; CUNHA, 2010) e VNS-VLNS (REIS; SILVA, 2012), uma vez que, dentre as diferentes abordagens consideradas, são as únicas testadas com as mesmas configurações e com o mesmo conjuntos de dados. Os resultados são apresentados na Tabela 24.
Ao analisar a Tabela 24, as duas versões da heurística ALNS geraram as melhores soluções para todos os dias úteis e para o sábado neste cenário. Quanto ao domingo, as
Tabela 24 – Comparação dos resultados obtidos pela ALNS com as soluções obtidas pelos métodos GRASP, VNS-VLNS e com a solução adotada pela empresa, no cenário 2T V600
Dados Segunda Terça Quarta Quinta Sexta Sábado Domingo
ALNS FO 1.210.492 1.152.376 1.389.968 1.510.252 1.425.480 1.055.260 565.608 Jorn. 118 112 136 148 139 102 55 DP 17 17 13 13 15 20 10 HE 84:33 92:24 92:22 93:33 110:20 96:55 40:02 ALNSruído FO 1.203.568 1.153.616 1.388.460 1.513.188 1.431.724 1.055.320 564.696 Jorn. 117 112 136 148 140 102 55 DP 19 19 11 14 13 23 8 HE 92:22 92:34 91:05 103:17 99:41 89:40 41:14 GRASP FO 1.264.386 1.265.916 1.457.172 1.563.532 1.508.884 1.131.828 591.060 Jorn. 124 125 143 154 149 111 58 DP 14 7 12 11 9 14 8 HE 66:32 48:49 83:13 70:33 56:11 55:57 26:05 VNS-VLNS FO 1.223.556 1.189.408 1.393.920 1.515.196 1.437.060 1.089.764 562.444 Jorn. 120 117 137 149 141 107 55 DP 19 10 15 17 17 10 7 HE 50:39 55:52 62:10 53:36 56:18 43:12 34:21 Empresa FO 1.364.404 1.322.420 1.518.460 1.651.256 1.576.564 1.253.100 686.468 Jorn. 134 130 149 162 155 124 68 DP 6 3 5 4 1 0 0 HE 86:41 85:55 106:05 120:14 108:11 54:35 26:57 GAP -1,079% -3,214% -0,284% -0,327% -0,812% -3,270% +0,563% GAPruído -1,661% -3,103% -0,393% -0,133% -0,373% -3,264% +0,400%
soluções geradas pelas versões da ALNS foram, no máximo, 0,6% piores que a melhor solução, gerada por Reis e Silva (2012). Igualmente ao cenário 1T V600, a redução no número
de jornadas das soluções geradas pela ALNS, em relação aos demais métodos, é justificada pelo aumento das horas extras em cada solução.
Por fim, no Cenário 2T V5.000, que permite que sejam realizadas até duas trocas de
veículos por jornada e adota o peso 5.000 para as duplas pegadas, os resultados obtidos pela ALNS foram comparados apenas com os resultados obtidos pelo método VNS-VLNS (REIS; SILVA, 2012), uma vez que é a única abordagem que utiliza os mesmos parâmetros. Estes estão apresentados na Tabela 25.
Analisando a Tabela 25, nota-se que ambas as versões da ALNS geraram os melhores resultados para os problemas da segunda-feira, terça-feira, quarta-feira, quinta-feira e sábado, assim como no cenário 1T V5.000, cujos resultados são apresentados na Tabela 23.
Da mesma forma, a ALNS com a aplicação do ruído também alcançou o melhor resultado para o domingo. Para a sexta-feira, as soluções obtidas pelas versões da ALNS foram, no máximo, 0,7% piores que a melhor solução gerada por Reis e Silva (2012).
Ao analisar a qualidade das soluções obtidas pelo ALNS sem e com ruído nos quatro cenários, apenas o problema do sábado, nos Cenários 1T V600 e 2T V600, apresentou
uma quantidade de jornadas do tipo dupla pegada superior aos 20%, indesejável pelas empresas de transporte público. O restante das soluções são compostas por uma quantidade de duplas pegadas inferior a 20% do total de jornadas, ressaltando a aplicabilidade das
Capítulo 5. Experimentos Computacionais 84
Tabela 25 – Comparação dos resultados obtidos pela ALNS com as soluções obtidas pelo método VNS-VLNS e com a solução adotada pela empresa, no cenário 2T V5.000
Dados Segunda Terça Quarta Quinta Sexta Sábado Domingo
ALNS FO 1.252.288 1.200.932 1.435.604 1.573.848 1.471.984 1.108.708 599.496 Jorn. 121 116 138 152 141 104 56 DP 4 4 6 6 7 9 6 HE 92:52 87:13 106:41 99:22 112:26 98:47 39:34 ALNSruído FO 1.257.688 1.197.704 1.439.944 1.575.324 1.469.816 1.117.452 594.592 Jorn. 121 115 138 153 143 106 56 DP 5 5 7 5 3 7 6 HE 94:32 94:36 103:56 102:04 103:24 93:33 39:58 VNS-VLNS FO 1.264.724 1.220.112 1.449.952 1.580.160 1.461.288 1.141.916 597.496 Jorn. 121 118 139 150 139 110 58 DP 12 8 11 14 10 11 6 HE 51:34 58:25 58:19 58:33 66:05 49:39 27:12 Empresa FO 1.390.804 1.335.620 1.540.460 1.668.856 1.580.964 1.253.100 686.468 Jorn. 134 130 149 162 155 124 68 DP 6 3 5 4 1 0 0 HE 86:41 85:55 106:05 120:14 108:11 54:35 26:57 GAP -0,993% -1,597% -0,999% -0,401% +0,736% -2,995% +0,335% GAPruído -0,559% -1,871% -0,695% -0,307% +0,588% -2,189% -0,488%
soluções geradas em ambientes práticos e reais. Um outro fator a ser notado é a pequena porcentagem do desvio padrão em todas as soluções, mostrando a robustez da heurística.
Para escolher qual dentre as duas abordagens da ALNS obteve melhor desempenho ao resolver o primeiro conjunto de dados, foi levado em consideração o desempenho obtido com relação aos valores do gap. Assim, a partir de uma análise quantitativa, a ALNS com a aplicação do ruído foi escolhida como a melhor dentre as duas versões, uma vez que superou a quantidade de melhores soluções obtidas nos cenários 1T V5.000 e 2T V5.000,
e empatou nos cenários restantes. Por este motivo, aos novos dados de entrada foram aplicadas a ALNS que considera o ruído da FO. Os resultados obtidos encontram-se nas Tabelas 30 e 31, para os cenários 1T V600 e 1T V5.000, e 2T V600 e 2T V5.000, respectivamente.
Uma outra característica analisada foi a flexibilidade de permitir, no máximo, apenas uma ou duas trocas de veículo por jornada nos resultados obtidos pela ALNS com a aplicação do ruído. Nas Tabelas 26 e 27 são apresentados os custos (valor da FO) das melhores soluções obtidas ao resolver os problemas considerando os pesos 600 e 5.000 para as jornadas do tipo dupla pegada, nos cenários que permitem, no máximo, uma e duas trocas de veículo por jornada, respectivamente. Os valores em negrito indicam qual dos cenários resultou na solução com menor valor da FO.
Considerando a Tabela 26, que apresenta os resultados obtidos nos cenários que ponderam as jornadas de dupla pegada com o peso wdp = 600, observa-se que a flexibilidade
causada pelas trocas de veículos não levou a um impacto significativo no custo das soluções. Para três dentre os sete problemas, foram obtidas soluções mais baratas ao permitir até uma troca de veículo por jornada, enquanto para os problemas restantes se sobressaíram as soluções que permitem realizar até duas trocas. Este fato pode ser explicado pela
Tabela 26 – Custo das melhores soluções obtidas nos cenários 1T V600 e 2T V600 com a aplicação de ruído 1T V600 2T V600 SEG 1.211.836 1.203.568 TER 1.169.944 1.153.616 QUA 1.384.688 1.388.460 QUI 1.514.668 1.513.188 SEX 1.431.040 1.431.724 SAB 1.053.000 1.055.320 DOM 565.224 564.696
Tabela 27 – Custo das melhores soluções obtidas nos cenários 1T V5.000 e 1T V5.000 com a
aplicação de ruído 1T V5.000 2T V5.000 SEG 1.261.280 1.257.688 TER 1.201.956 1.197.704 QUA 1.431.336 1.439.944 QUI 1.564.068 1.575.324 SEX 1.475.376 1.469.816 SAB 1.126.256 1.117.452 DOM 599.212 594.592
flexibilidade que o menor peso para as duplas pegadas proporciona, uma vez que, dado o baixo valor deste tipo de jornadas, seu número tende a ser maior.
Por outro lado, ao analisar a Tabela 27, que apresenta os resultados obtidos nos cenários que ponderam as duplas pegadas com o peso wdp = 5.000, nota-se a influência que
a possibilidade de realizar mais trocas de veículos durante uma jornada pode ocasionar no valor da FO. Neste caso, apenas dois dos sete problemas apresentaram melhores soluções permitindo-se até uma troca de veículo por jornada, enquanto os seis problemas restantes obtiveram soluções melhores ao considerar até duas trocas. Como o valor das jornadas de dupla pegada é mais elevado neste caso, a busca tende a explorar as situações menos custosas, como aquelas que incorporam mais trocas de veículos nas jornadas.