O problema do caixeiro viajante com múltiplos passageiros e quota / The problem of the traveling boxer with multiple passengers and quota

Allan Vilar de Carvalho, Marco César Goldbarg, Elizabeth Ferreira Gouvêa Goldbarg

Abstract


Este trabalho apresenta o Problema do Caixeiro Viajante com Múltiplos Passageiros e Quota, uma variante do Problema do Caixeiro Viajante com Quota relacionada com outros modelos de roteamento enriquecido. O problema consiste em desenvolver uma solução do problema do Caixeiro Viajante com Quota considerando que o caixeiro é o motorista de carro que deseja compartilhar os custos de viagem com passageiros que podem ser embarcados e desembarcados em cidades da sua rota. Cada passageiro cuja solicitação de transporte é atendida compartilha os custos da viagem no caminho entre sua origem e seu destino com o caixeiro e outros passageiros no carro. Um modelo de programação matemática e um banco de instâncias são propostos para o problema. As soluções exatas para instâncias com até 10 vértices são apresentadas. Uma heurística ad hoc e duas heurísticas baseadas na meta-heurística colônia de formigas são propostas. Os resultados de um experimento computacional são relatados

Keywords


Caixeiro Viajante. Problemas de Ridesharing. Meta-heurísticas. Tópicos (MH – Meta-heurísticas. OT – Otimização)

References


Amey, A., Attanucci, J. & Mishalani, R. (2011). Real-time ridesharing–the opportunities and challenges of utilizing mobile phone technology to improve rideshare services. In TRB Annual Meeting, 1–17.

Ausiello, G., Demange, M., Laura, L. & Paschos, V. (2004). Algorithms for the on-line quota traveling salesman problem. In International Computing and Combinatorics Conference, 290–299.

Awerbuch, B., Azar, Y., Blum, A. & Vempala, S. (1998). New approximation guarantees for minimum-weight k-trees and prize-collecting salesman. SIAM Journal on Computing 28(1), 254–262.

Balas, E. (1989). The prize collecting traveling salesman problem. Networks 19(6), 621–636.

Berbeglia, G., Cordeau, J.-F. & Laporte, G. (2010). Dynamic pickup and delivery problems. European Journal of Operational Research 202(1), 8–15.

Calheiros, Z. S. A. (2017). O Problema do Caixeiro Viajante Com Passageiros. Dissertação de mestrado, Pós-graduação em Sistemas e Computação, Universidade Federal do Rio Grande do Norte.

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

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

Deakin, E., Frick, K. & Shively, K. (2010). Markets for dynamic ridesharing? case of berkeley, california. Transportation Research Record: Journal of the Transportation Research Board 2187, 131–137.

Doerner, K. F. & Salazar-González, J.-J. (2014). Chapter 7: Pickup-and-delivery problems for people transportation. In Vehicle Routing: Problems, Methods, and Applications, Second Edition, 193–212. SIAM.

Dorigo, M. & Di Caro, G. (1999). Ant colony optimization: a new meta-heuristic. In IEEE CEC99 Congress on Evolutionary Computation 2, 1470–1477.

Goldbarg, M. C. & Goldbarg, E. (2012). Grafos: Conceitos, Algoritmos e Aplicações. Elsevier.

Goldbarg, M. C., Goldbarg, E. F. G. & Luna, H. P. L. (2016). Otimização Combinatória e Meta-heurísticas: Algoritmos e Aplicações. Elsevier.

Gruebele, P. (2008). Interactive system for real time dynamic multi-hop carpooling. Global Transport Knowledge Partnership, 1-17. Disponível em http://www.dynamicridesharing.org/resources/Multi_hop_social_carpool_routing_System.pdf, último acesso em 4 de junho de 2018.

Kleiner, A., Nebel, B. & Ziparo, V. A. (2011). A mechanism for dynamic ride sharing based on parallel auctions. In International Joint Conference on Artificial Intelligence 11, 266–272.

Lin, S. & Kernighan, B. W. (1973). An effective heuristic algorithm for the traveling-salesman problem. Operations Research 21(2), 498–516.

López-Ibánez, M., Dubois-Lacoste, J., Stützle, T. & Birattari, M. (2011). The IRACE Package, Iterated Race for Automatic Algorithm Configuration. Technical Report TR/IRIDIA/2011- 004, IRIDIA, Université Libre de Bruxelles, Belgium.

Miller, C. E., Tucker, A. W. & Zemlin, R. A. (1960). Integer programming formulation of traveling salesman problems. Journal of the ACM 7(4), 326–329.

Mladenović, N. e Hansen, P. (1997). Variable neighborhood search. Computers & Operations Research 24(11), 1097–1100.

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

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

Parragh, S. N., Doerner, K. F. & Hartl, R. F. (2008). A survey on pickup and delivery models part ii: Transportation between pickup and delivery locations. Journal für Betriebswirtschaft 58(2), 81–117.

Yu, W., Liu, Z. & Bao, X. (2014). Optimal deterministic algorithms for some variants of online quota traveling salesman problem. European Journal of Operational Research 238(3), 735–740.




DOI: https://doi.org/10.34117/bjdv6n5-283

Refbacks

  • There are currently no refbacks.