Production
https://prod.org.br/article/doi/10.1590/S0103-65132009000100004
Production
Article

Uma nova abordagem para o problema dial-a-ride

Mauri, Geraldo Regis; Lorena, Luiz Antonio N.

Downloads: 1
Views: 849

Abstract

Este trabalho descreve um modelo matemático geral e multiobjetivo para o problema dial-a-ride e uma aplicação do simulated annealing para resolvê-lo. O modelo trata a forma estática do problema e abrange vários casos distintos dos modelos mais comuns, tais como frota homogênea e heterogênea, garagens múltiplas ou únicas, e uma função de minimização multiobjetivo que trata os custos de transporte e a inconveniência dos clientes por meio de penalizações. A aplicação do simulated annealing é simples, porém, para a geração de novas soluções vizinhas, são utilizados três movimentos de troca selecionados de forma aleatória e uniformemente distribuída, e as rotas são roteirizadas e programadas separadamente por outros métodos heurísticos. Os resultados computacionais são obtidos com o uso de instâncias públicas disponíveis e comparados com outros métodos que apresentam o atual estado da arte em que o problema se encontra.

Keywords

Dial-a-ride, simulated annealing, modelo multiobjetivo

References

 

 

 


10.BAUGH, J. W.; KAKIVAYA, D. K. R.; STONE, J. R. Intractability of the dial-a-ride problem and a multiobjective solution using simulated annealing. Engineering Optimization, v. 30, n. 2, p. 91-123, 1998.

BERGVINSDOTTIR, K. B. The genetic algorithm for solving the dial-a-ride problem. 2004. 140 p. (IMM 2004-37). Dissertação (Master of Science in Engineering). Technical University of Denmark (DTU), Lyngby, 2004.

CALVO, R. W.; COLORNI, A. An effective and fast heuristic for the dial-a-ride problem. 4OR: A Quarterly Journal of Operations Research, v. 5, n. 1, 61-73, 2007.

CORDEAU, J. F. A branch-and-cut algorithm for the dial-a-ride problem. Operations Research, v. 54, n. 3, p. 573-586, 2006.

CORDEAU, J. F.; LAPORTE, G. A tabu search heuristic for the static multi-vehicle dial-a-ride problem. Transportation Research Part B: Methodological, v. 37, n. 6, p. 579-594, 2003.

______. The dial-a-ride problem: models and algorithms. Annals of Operations Research, v. 153, n. 1, 29-46, 2007.

ILOG. Ilog CPLEX 9.0: user's manual. France, 2003. 564 p.

JORGENSEN, R. M.; LARSEN, J.; BERGVINSDOTTIR, K. B. Solving the dial-a-ride problem using genetic algorithms. Journal of the Operational Research Society, v. 58, n. 10, p. 1321-1331, 2007.

KIRKPATRICK, S.; GELLAT, D. C.; VECCHI, M. P. Optimization by simulated annealing. Science, v. 220, n. 4598, p. 671-680, 1983.

MADSEN, O. B. G.; RAVN, H. F.; RYGAARD, J. M. A heuristic algorithm for a dial-a-ride problem with time windows, multiple capacities, and multiple objectives. Annals of Operations Research, v. 60, n. 1, p. 193-208, 1995.

ROPKE, S.; CORDEAU, J. F.; LAPORTE, G. Models and branch-and-cut algorithms for pickup and delivery problems with time windows. Networks, v. 49, n. 4, 258-272, 2007.

SAVELSBERGH, M. W. P. The vehicle routing problem with time windows: minimizing route duration. ORSA Journal on Computing, v. 4, n. 2, p. 146-154, 1992.

TOTH, P.; VIGO, D. Fast local search algorithms for the handicapped persons transportation problem. In: OSMAN, I. H.; KELLY, J. P. (Ed.). Meta-heuristics: theory and applications. Berlin: Springer, 1996. p. 677-690.

______. Heuristic algorithms for the handicapped persons transportation problem. Transportation Science, v. 31, n. 1, p. 60-71, 1997.

XIANG, Z.; CHU, C.; CHEN, H. A fast heuristic for solving a large-scale static dial-a-ride problem under complex constraints. European Journal of Operational Research, v. 174, n. 2, 1117-1139, 2006.

ZNAMENSKY, A.; CUNHA, C. B. Um modelo para o problema de roteirização e programação do transporte de deficientes. In: CONGRESSO DE PESQUISA E ENSINO EM TRANSPORTES, 13., 1999, São Carlos. Anais... São Carlos: ANPET, 1999, p. 59-62.



1590/S0103-65132009000100004

 

 

 

5883a3de7f8c9da00c8b4697 1574685864 Articles
Links & Downloads

Production

Share this page
Page Sections