Profitable Tour Problem with Passengers and Time and Cost Restrictions

• Vinícius A. Petch UFRN
• Marco Cesar Goldbarg UFRN
• Elizabeth F. G. Goldbarg UFRN
• José G. L. Filho UFRN

DOI: https://doi.org/10.5753/eniac.2018.4458

Resumo

Este artigo tem como objetivo apresentar um novo problema no contexto do transporte colaborativo denominado Problema do Passeio Lucrativo com Passageiros e Restrições de Tempo e Custo. O problema consiste em determinar a melhor rota de um courier que precisa realizar serviços em diversos locais. O courier realiza seu percurso em um veículo. Para reduzir custos, o courier pode levar passageiros que compartilham com ele os custos de viagem. Um modelo matemático é proposto o qual é implementado em um solver e aplicado a instâncias do problema. São apresentados algoritmos heurísticos segundo as meta-heurísticas Variable Neighborhood Search e Greedy Randomized Adaptive Search Procedure. São relatados resultados de um experimento computacional com 36 instâncias com até 150 vértices.

Referências

FEILLET, Dominique; DEJAX, Pierre; GENDREAU, Michel. Traveling Salesman Problems with Profits: an Overview. 2001 DELL'AMICO, Mauro; MAFFIOLI, Francesco; VÄRBRAND, Peter. On prize-collecting tours and the asymmetric travelling salesman problem. International Transactions in Operational Research, v. 2, n. 3, p. 297-308, 1995. CROES, Georges A. A method for solving traveling-salesman problems. Operations research, v. 6, n. 6, p. 791-812, 1958. GLOVER, Fred. Tabu search and adaptive memory programming—advances, applications and challenges. In: Interfaces in computer science and operations research. Springer US, 1997. p. 1-75. MLADENOVIĆ, Nenad; HANSEN, Pierre. Variable neighborhood search. Computers & operations research, v. 24, n. 11, p. 1097-1100, 1997.

BRIMBERG, Jack; HANSEN, Pierre; MLADENOVIć, Nedad; TAILLARD, Eric D. Improvements and comparison of heuristics for solving the uncapacitated multisource Weber problem. Operations Research, v. 48, n. 3, p. 444-460, 2000. FEO, Thomas A.; RESENDE, Mauricio GC. A probabilistic heuristic for a computationally difficult set covering problem. Operations research letters, v. 8, n. 2, p. 67-71, 1989.

LÓPEZ-IBÁNEZ, Manuel; DUBOIS-LACOSTE, Jérémie, STÜTZLE, Thomas; BIRATTARI, Mauro. The irace package, iterated race for automatic algorithm configuration. Technical Report TR/IRIDIA/2011-004, IRIDIA, Université Libre de Bruxelles, Belgium, 2011.

SAVELSBERGH, Martin WP; SOL, Marc. The general pickup and delivery problem. Transportation science, v. 29, n. 1, p. 17-29, 1995.