Problema de passeio rentável com passageiros e restrições de tempo e custo/ Profitable Tour Problem with Passengers and Time and Cost Restrictions

Authors

  • Vinicius Araujo Petch Brazilian Journals Publicações de Periódicos, São José dos Pinhais, Paraná
  • Marco Cesar Goldbarg
  • Elizabeth Ferreira Gouvea Goldbarg
  • Jose Gomes Lopes Filho

DOI:

https://doi.org/10.34117/bjdv5n10-267

Keywords:

Problema do Passeio Lucrativo, Programação matemática, Busca em Vizinhança Variável, GRASP

Abstract

 

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.

References

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.

Published

2019-10-21

How to Cite

Petch, V. A., Goldbarg, M. C., Goldbarg, E. F. G., & Filho, J. G. L. (2019). Problema de passeio rentável com passageiros e restrições de tempo e custo/ Profitable Tour Problem with Passengers and Time and Cost Restrictions. Brazilian Journal of Development, 5(10), 21003–21019. https://doi.org/10.34117/bjdv5n10-267

Issue

Section

Original Papers