Uma nova abordagem para o problema dial-a-ride
Mauri, Geraldo Regis; Lorena, Luiz Antonio N.
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
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
Facebook
Google+
Twitter
LinkedIn
Mendeley
StumbleUpon
CiteULike
Reddit
Email