Red Party (R)

A comparação entre os três algoritmos foi feita utilizando o Teste de Kruskal-Wallis, adequado para comparações entre três ou mais populações.

Tabela 14: Comparação entre os Resultados dos Algoritmos Genético, Memético e Colônia de Formigas

Instância p-valor Bolivia10n3c_S_1 1,11E-16 Bolivia10n3c_S_2 0,00E+00 Bolivia10n3c_S_3 0,00E+00 Argelia15n3c_S_1 9,99E-16 Argelia15n3c_S_2 1,11E-16

Argelia15n3c_S_3 9,21E-15 Bauru50n3c_S_1 8,55E-15 Bauru50n3c_S_2 3,22E-15 Bauru50n3c_S_3 9,55E-15 BrasilCO40n3c_S_1 7,85E-14 BrasilCO40n3c_S_2 1,01E-13 BrasilCO40n3c_S_3 6,66E-16 BrasilMG30n3c_S_1 1,21E-13 BrasilMG30n3c_S_2 1,23E-13 BrasilMG30n3c_S_3 5,95E-14 BrasilPR20n3c_S_1 7,16E-14 BrasilPR20n3c_S_2 3,19E-14 BrasilPR20n3c_S_3 1,90E-14 Bolivia10n3c_N_1 0,00E+00 Bolivia10n3c_N_2 1,11E-16 Bolivia10n3c_N_3 0,00E+00 Argelia15n3c_N_1 7,08E-14 Argelia15n3c_N_2 4,88E-15 Argelia15n3c_N_3 6,66E-16 Bauru50n3c_N_1 0,00E+00 Bauru50n3c_N_2 0,00E+00 Bauru50n3c_N_3 9,99E-16 BrasilCO40n3c_N_1 2,71E-14 BrasilCO40n3c_N_2 2,80E-14 BrasilCO40n3c_N_3 9,99E-16 BrasilMG30n3c_N_1 1,28E-13 BrasilMG30n3c_N_2 1,05E-13 BrasilMG30n3c_N_3 1,29E-13 BrasilPR20n3c_N_1 1,15E-13 BrasilPR20n3c_N_2 6,33E-15 BrasilPR20n3c_N_3 1,78E-15 Bolivia10n4c_S_1 2,66E-15 Bolivia10n4c_S_2 7,00E-03 Bolivia10n4c_S_3 1,92E-13 Argelia15n4c_S_1 8,64E-14 Argelia15n4c_S_2 1,31E-14 Argelia15n4c_S_3 1,22E-13 Bauru50n4c_S_1 8,77E-15 Bauru50n4c_S_2 6,44E-15 Bauru50n4c_S_3 6,88E-15 BrasilCO40n4c_S_1 6,56E-14 BrasilCO40n4c_S_2 4,84E-14 BrasilCO40n4c_S_3 5,00E-15 BrasilMG30n4c_S_1 1,33E-15

BrasilMG30n4c_S_2 1,95E-14 BrasilMG30n4c_S_3 1,38E-14 BrasilPR20n4c_S_1 1,22E-15 BrasilPR20n4c_S_2 1,55E-14 BrasilPR20n4c_S_3 7,88E-15 Bolivia10n4c_N_1 1,55E-15 Bolivia10n4c_N_2 2,10E-14 Bolivia10n4c_N_3 3,44E-15 Argelia15n4c_N_1 1,83E-14 Argelia15n4c_N_2 2,39E-14 Argelia15n4c_N_3 4,44E-16 Bauru50n4c_N_1 8,88E-16 Bauru50n4c_N_2 2,23E-14 Bauru50n4c_N_3 1,39E-14 BrasilCO40n4c_N_1 1,95E-14 BrasilCO40n4c_N_2 5,94E-14 BrasilCO40n4c_N_3 4,25E-14 BrasilMG30n4c_N_1 1,78E-15 BrasilMG30n4c_N_2 4,11E-14 BrasilMG30n4c_N_3 7,77E-16 BrasilPR20n4c_N_1 1,17E-13 BrasilPR20n4c_N_2 7,34E-14 BrasilPR20n4c_N_3 1,11E-13

O teste demonstra que na comparação entre os três algoritmos todos os p-valores encontrados foram menores que 0,05, o que indica que há uma significância maior que 99,5% na comparação entre as populações. Portanto, podemos afirmar que o desempenho do Algoritmo Colônia de Formigas proposto foi consideravelmente pior que os dois anteriores, uma vez que não alcança médias melhores que nenhum dos dois algoritmos em qualquer instância, à exceção de três casos isolados nas instâncias BrasilPR20n4c_S_1, BrasilPR20n4c_S_2 e BrasilPR20n4c_S_3 em comparação com o algoritmo genético.

8 Considerações Finais

Neste trabalho descrevemos o problema do Caixeiro Viajante com Caronas Múltiplas – PCV-MCa – e são propostos alguns algoritmos para resolvê-lo, levando em consideração o contexto de pesquisas anteriores feitas em problemas similares.

Este problema mostra-se de difícil solução por algoritmos exatos, com uma das menores instâncias testadas, Bolivia10n3c_S_2, requerendo um tempo acima de 60 minutos para encontrar uma solução.

O Algoritmo Memético encontrou os melhores resultados dentre as abordagens meta-heurísticas em algumas instâncias, encontrando resultados iguais aos obtidos no algoritmo exato no caso das instâncias menores. O Algoritmo Colônia de Formigas implementado demonstrou que a estratégia abordada não é efetiva para o problema escolhido, portanto é importante que em trabalhos futuros sejam investigadas novas abordagens. Possivelmente isto ocorre pois quando o feromônio leva em consideração o tamanho do percurso entre as arestas, isso não necessariamente leva a uma boa solução. Pode-se, por exemplo, considerar uma instância em que uma solução possua na lista de visita das cidades o ótimo do caixeiro viajante para esta instância. Pode ocorrer de termos quase nenhum passageiro que se interesse em caronas neste percurso, e, portanto, como a ocupação do veículo seria baixa, e o seu valor pode ficar muito longe do ótimo. Esta peculiaridade nos leva a testar novas estratégias de otimização, como a utilizada no Algoritmo Memético, que considera no cruzamento indivíduos com base na sua adequação já preenchidas as caronas, e utilizando um procedimento de busca local que tenta encontrar candidatos com a maior possibilidade de preencher o veículo. Ainda assim, em muitas instâncias, não houve diferença significativa entre os resultados do Algoritmo Memético e o Genético.

A dificuldade em elaborar estratégias para a resolução deste problema está no fato de que qualquer alteração mínima no percurso do motorista pode acarretar grandes mudanças difíceis de prever na quantidade de passageiros que se interessam em embarcar no veículo. Integrar a otimização destes dois

aspectos que compõem a solução requer métodos sofisticados que vão além do que existe na literatura, e dada a possível aplicação prática do problema, um meio de soluciona-lo de maneira ótima e eficiente seria uma grande inovação na área de transportes urbanos, além de outras áreas que venham a ser relacionadas.

Trabalhos futuros envolvendo o PCV-MCa podem propor novas meta- heurísticas e estratégias diferentes de otimização, experimentando novas formas de busca local que permitam uma convergência mais veloz e eficaz da solução em direção a valores menores.

Referências

Agatz, N.A.H., Erera, A., Savelsbergh, M.W.P. & Wang, X. (2011). Dynamic ride-sharing: a simulation study in metro Atlanta. Transportation Reserch Part B, Methodological 45(9):1450-1464.

Agatz, N.A.H., Erera, A., Savelsbergh, M.W.P. & Wang, X. (2012). Optimization for dynamic ride-sharing: A review. European Journal of Operational Research 223(2):29-303.

Amey, A., Attanucci, J. & Mishalani. R. (2011). Real-Time Ridesharing – The Opportunities and Challenges of Utilizing Mobile Phone Technology to Improve Rideshare Services. TRB Annual Meeting: 1-17.

Bellmore, M. & Nemhauser, G. L. (1968). The traveling salesman problem: A survey, Operations Research 16:538-582.

Berbeglia, G., Cordeau, J.-F., Laporte, G., (2010). Dynamic pickup and delivery problems. European Journal of Operational Research 202(1):8-15. Bullnheimer, B., Hartl, R. F., Strauss, C. (1997). A new rank based version of the Ant System— a computational study. Technical report, Institute of Management Science, University of Vienna, 1997.

Burkard, R. E. (1979). Traveling Salesman and Assignment Problems: A Survey, Annals of Discrete Mathematics 4:193-215.

Chan, N. D. & Shaheen, S. A. (2012). Ridesharing in North America: Past, present, and future. Transport Reviews 32(1):93-112.

Coltin, B. & Veloso, M. (2014). Ridesharing with Passenger Transfers, In: Proceedings 014 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2014), 3278-3293.

Dantzig, G. B., Fulkerson, D. R. & Johson. S. M. (1954). Solution of a Large Scale Travelling Salesman Problem, Operations Research 2:393-410.

Dailey, D. J., Lose, D. & Meyers, D. (1999). Seattle smart traveler: dynamic ridematching on the world wide web. Transportation Research Part C 7(1):17- 32.

Deakin, E., Frick, K. T., Shively, K. M. (2010). Markets for dynamic ridesharing? Transportation Research Record: Journal of the Transportation Research Board 2187:131-137.

El-Mihoub, T. A., Hopgood, A. A., Nolle, L. & Battersb, A. (2006). Hybrid Genetic Algorithms: A Review Engineering Letters, 13:2, EL_13_2_11.

Furuhata, M., Dessouky, M., Ordóñez, F., Brunet, M., Wang, X., Koenig, S. (2013). Ridesharing: the state-of-the-art and future directions. Transportation Research Part B: Methodological, 57:28–46.

Garey, M. & Johnson, D. (1979). Computer and Intractibility: A guide to the Theory of NPCompleteness, Freeman, San Francisco.

Ghoseiri, K., Haghani, A. & Hamedi, M. (2011). Real-time rideshare matching problem. University of Maryland, Department of Civil and Environmental Engineering, UMD-2009-05.

Goldbarg, M. C., Luna, H. P. L. & Goldbarg, E. F. G. (2015). Otimização Combinatória: Modelos, Algoritmos e Aplicações. Editora Campus-Elsevier, São Paulo.

Goldbarg, M. C (2015). Modelo de Programação Mamtemática para o Caixeiro Hidersharing. Comunicação interna do Laboratório de algoritmos Experimentais.

Gruebele, P., (2008). Interactive system for real time dynamic multi-hop

carpooling. [http://dynamicridesharing.org/resources/

Multi_hop_social_carpool_routing_System.pdf], Acesso em 20-04-2015.

Gutin, G. & Punnen, A. (2002). The Traveling Salesman Problem and Its Variations, Kluwer Academic Publishers.

Gutin, G., Yeo, A. & Zverovitch, A. (2002). Exponential Neighborhoods and Domination Analysis for the TSP, In: The Traveling Salesman Problem and its Variations, Gutin, G. & Punnen, A. (edt), Kluwer, Dordrecht.

Herbawi, W. & Weber, M. (2012). The ridematching problem with time windows in dynamic ridesharing: A model and a genetic algorithm. In:

Proceedings 41 of ACM Genetic and Evolutionary Computation Conference (GECCO):1-8.

Herbawi, W. & Weber, M. (2011). Ant colony vs. genetic multiobjective route planning in dynamic multi-hop ridesharing. In: Proceedings of the IEEE 23rd International Conference on Tools with Artificial Intelligence (Washington, DC,

USA, 2011), ICTAI '11, IEEE Computer Society, 282-288.

López-Ibáñez, M., Dubois-Lacoste, J., Stützle, T., Birattari, M. (2011). The irace package, Iterated Race for Automatic Algorithm Configuration. In:

Technical Report TR/IRIDIA/2011-004, IRIDIA, Université libre de Bruxelles,

Karp, R. M. (1975). On the Computational Complexity of Combinatorial Problems, Networks 5:45-68.

Kleiner, A., Nebel, B. & Ziparo, V. (2011). A mechanism for dynamic ride sharing based on parallel auctions. In: Proceedings of the 22th International Joint Conference on Artificial Intelligence (IJCAI), Barcelona, Spain, 266-272. ISBN 978-1-57735- 516-8.

Kruskal, W. H., WALLIS, W. A. (1952). Use of ranks in one-criterion variance analysis. J. Am. Stat. Assoc., American Statistical Association, Vol. 47, No. 260 583-621.

Lahyani, R., Khemakhem, M. & Semet, F. (2015). Rich Vehicle Routing Problems: From a taxonomy to a definition, European Journal of Operational Research 241(1):1-14.

Laporte, G., Asef-Vazir, A. & Sriskandarajah, C. (1996). Some Applications of the Generalized Travelling Salesman Problem, Journal of the Operational Research Society 47:1461-1467.

Little, J. D. C., Murty, K. G., Sweeney, D. W., Karel, C. (1963). "An algorithm for the traveling salesman problem" (PDF). Operations Research 11 (6): 972– 989.

Masabumi Furuhata, M., Dessouky, M., Ordóñez, F., Brunet, M-E., Wang, X. & Koenig, S. (2013). Ridesharing: The state-of-the-art and future directions. Transportation Research Part B 57:28-46.

Matai, R., Singh, S. P. & and Mittal, M. L. (2010). An Overview of Applications, Formulations, Traveling Salesman Problem and Solution Approaches. Chapter 1 in Traveling Salesman Problem, Theory and Applications, Davendra, D. (edt) 1-24, Publisher InTech.

Melamed, I. I., Sergeev, S. I., & Kh. Sigal, I. (1990). The Traveling Salesman Problem, Plenum Publishing Corporation 1147-1173.

Morency, C. (2007). The ambivalence of ridesharing. Transportation 34(2):239- 253.

Neri, F. & Cotta, C. (2012). Memetic algorithms and memetic computing optimization: A literature review, Swarm and Evolutionary Computation 2:1- 14.

Nourinejad, M. (2014). Dynamic Optimization Models for Ridesharing and Carsharing, Master Thesis, Department of Civil Engineering, University of

Toronto, Canadá.

[https://tspace.library.utoronto.ca/bitstream/1807/44050/3/Nourinejad_M ehdi_201403_MSc_thesis.pdf]. Acesso em Abril de 2015.

Ong, Y-S. and Keane, A.J. (2004). Meta-lamarckian learning in memetic algorithms.IEEE Transactions on Evolutionary Computation, 8(2):99–110, April 2004.

Reinelt, G. (1994). The Traveling Salesman: Computational Solutions for the Applications, Lectures Notes in Computer Science 840, Spring-Verlag, Berlin.

Papadimitriou, C. H. & Steiglitz. K. (1982). Combinatorial Optimization Algorithms and Complexity, PrenticeHall, New York.

Wang, S. & Chen, L. (2015). Application of Travel Management System Based on Route Inquiry, International Journal of Smart Home, Vol. 9, No. 6 133-140. Wilcoxon, F. (1945). Individual comparisons by ranking methods. Biom. bull., Vol. 1, No. 6 80-83

Winter, S. & Nittel, S. (2006). Ad-hoc shared-ride trip planning by mobile geo- sensor networks. International Journal of Geographic Information Science 00(00):1-21.

Whitley, D. & Sutton, A. M. (2012). Genetic Algorithms – A Survey of Models and Methods, Handbook of Natural Computing, 637-671.

Zhang, W. (1997). A note on the complexity of the asymmetric travelling salesman problem, Operations Research Letters 20:31-38.