Resolução de um caso real do problema dial-a-ride multicritério via clustering search
Solving a real case of the multicriteria dial-a-ride problem via a clustering search
Rodrigues, Patricia Perretto; Rosa, Rodrigo de Alvarenga; Resendo, Leandro Colombi; Mauri, Geraldo Regis; Ribeiro, Glaydston Mattos
http://dx.doi.org/10.1590/S0103-65132013005000044
Production, vol.24, n3, p.572-582, 2014
Resumo
Este artigo apresenta um clustering search (CS) para o problema dial-a-ride (DARP) multicritério presente na cidade de Vitória (ES). Em Vitória, os usuários especificam requisições de transporte entre origens e destinos com janelas de tempo para os horários de embarque e desembarque; o transporte é realizado por uma frota homogênea de veículos localizados inicialmente em uma mesma garagem; busca-se assim definir um conjunto de rotas de atendimento que minimize o custo de transporte(normalmente, tempo ou distância), o número de veículos utilizados e o tempo total de espera dos usuários, respeitando restrições como as de capacidade dos veículos e de precedência (o embarque de um usuário deve preceder o seu destino em uma rota). Dessa forma, o CS aqui proposto foi capaz de tratar as particularidades do caso de Vitória, ES. Bons resultados computacionais são apresentados considerando instâncias reais obtidas na Secretaria de Transportes, Trânsito e Infraestrutura Urbana de Vitória, ES.
Palavras-chave
Dial-a-ride. Clustering search. Multicritério
Abstract
This paper presents a clustering search (CS) algorithm for the multicriteria dial-a-ride problem (DARP) from Vitória, Espírito Santo State, Brazil. In Vitória, users submit pickup and delivery requests for transportation between various origins and destinations with time windows for the pickup and delivery; these requests are serviced by a homogeneous fleet of vehicles based at the same depot. The aim is to plan a set of vehicle routes to service all requests while minimizing the transportation cost (commonly length or travel times), the number of vehicles used and the total waiting time inside the vehicles, under constraints such as vehicle capacities and precedence (the origin of a user must precede his/her destination on the route). Our CS was able to handle the particularities present in Vitória. Good computational results are reported for practical instances provided by the Department of Transportation, Traffic and Urban Infrastructure of Vitória.
Keywords
Dial-a-ride. Clustering search. Multicriteria
References
ARMSTRONG, G. R.; GARFINKEL, R. S. Dynamic programming solution of the single and multiple vehicle pickup and delivery problem with application to dial-a-ride. Universidade do Tennessee, 1982. Working paper n. 162.
BEKTAS, T. The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega, v. 34, p. 209-219, 2006. http://dx.doi.org/10.1016/j.omega.2004.10.004
BERBEGLIA, G.; CORDEAU, J. F.; LAPORTE, G. Dynamic pickup and delivery problems. European Journal of Operational Research, v. 202, p. 8-15, 2010. http://dx.doi.org/10.1016/j.ejor.2009.04.024
BERGVINSDOTTIR, K. B. The genetic algorithm for solving the dial-a-ride problem. 2004. 150 f. Dissertation (Master of Science in Engineering)-Technical University of Denmar, Lyngby, 2004.
CHAVES, A. A.; LORENA, L. A. N. Clustering search algorithm for the capacitated centered clustering problem. Computers & Operations Research, v. 37, p. 552-558, 2010. http://dx.doi.org/10.1016/j.cor.2008.09.011
CORDEAU, J.-F.; LAPORTE, G. A tabu search heuristic for the static multi-vehicle dial-a-ride problem. Transportation Research Part B, v. 37, p. 579-594, 2003. http://dx.doi.org/10.1016/S0191-2615(02)00045-0
CORDEAU, J.-F. A branch-and-cut algorithm for the dial-a-ride problem. Operations Research, v. 54, p. 573-586, 2006. http://dx.doi.org/10.1287/opre.1060.0283
COSLOVICH, L.; PESENTI, R.; UKOVICH, W. A two-phase insertion technique of unexpected customers for a dynamic dial-a-ride problem. European Journal of Operational Research, v. 175, p. 1605-1615, 2006. http://dx.doi.org/10.1016/j.ejor.2005.02.038
CUNHA, C. B. Aspectos práticos da aplicação de modelos de roteirização de veículos a problemas reais. Transportes, v. 8, p. 51-74, 2000.
GLOVER, F. Tabu search and adaptive memory programming: advances, applications and challenges. In: BARR, R.; HELGASON, R.; KENNINGTON, J. (Eds.). Interfaces in Computer Science and Operations Research. Boston: Kluwer, 1996. p. 1-75. PMid:8842811.
HAMMING, R. W. Error detecting and error correcting codes. Bell System Technical Journal, v. 26, p. 147-160, 1950.
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, p. 1321-1331, 2007. http://dx.doi.org/10.1057/palgrave.jors.2602287
KAISER, M. S. Aplicação de metaheurística híbrida na resolução do problema dial-a-ride. 2009. 83 f. Dissertação (Mestrado em Engenharia de Transportes)-Universidade Federal do Rio de Janeiro, Rio de Janeiro, 2009.
KARABUK, S. A nested decomposition approach for solving the paratransit vehicle scheduling problem. Transportation Research Part B, v. 43, p. 448-465, 2009. http://dx.doi.org/10.1016/j.trb.2008.08.002
MADSON, O. B. G.; RAVN, H. F.; RYGAARD, J. M. A heuristic algorithm for the dial-a-ride problem with time windows, multiple capacities and multiplie objectives. Annals of Operations Research, v. 60, p. 193-208, 1995. http://dx.doi.org/10.1007/BF02031946
MAURI, G. R.; LORENA, L. A. N. Uma nova abordagem para o problema dial-a-ride. Produção, v. 19, p. 41-54, 2009. http://dx.doi.org/10.1590/S0103-65132009000100004
OLIVEIRA, A. C. M.; LORENA, L. A. N. Detecting promising areas by evolutionary clustering search. In: BAZZAN, A. L. C.; LABIDI, S. Advances in Artificial Intelligence SBIA 2004. Lecture Notes in Computer Science, v. 3171, p. 318-323, 2004.
OLIVEIRA, A. C. M.; LORENA, L. A. N. Hybrid evolutionary algorithms and clustering search. Hybrid Evolutionary Algorithms, Studies in Computational Intelligence, v. 75, p. 77-99, 2007. http://dx.doi.org/10.1007/978-3-540-73297-6_4
PAQUETTE, J. et al. Measuring quality of service in dial-a-ride operations: the case of a Canadian city. Transportation, p. 1-26, 2012a. http://dx.doi.org/10.1007/s11116-011-9375-4
PAQUETTE, J. et al. Combining multicriteria analysis and tabu search for dial-a-ride problems. Transportation Research Part B, 2012b. Submetido.
PARRAGH, S. N.; DOERNER, K. F.; HARTL, R. F. A survey on pickup and delivery problems Part II: transportation between pickup and delivery locations. Journal für Betriebswirtschaft, v. 58, p. 81-117, 2008. http://dx.doi.org/10.1007/s11301-008-0036-4
PARRAGH, S. N. et al. A heuristic two-phase solution approach for the multi-objective dial-a-ride problem. Networks, v. 54, p. 227-242, 2009. http://dx.doi.org/10.1002/net.20335
RIBEIRO, G. M.; LAPORTE, G.; MAURI, G. R. A comparison of three metaheuristics for the workover rig routing problem. European Journal of Operational Research, v. 220, n. 1, p. 28-36, 2012. http://dx.doi.org/10.1016/j.ejor.2012.01.031
RODRIGUES, P. P. Proposta de um modelo matemático para o problema dial-a-ride aplicado ao transporte de cadeirantes. 2011. 148 f. Dissertação (Mestrado em Engenharia Civil - Transportes)-Universidade Federal do Espírito Santo, Vitória, 2011.
ROPKE, S.; PISINGER, D. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation Science, v. 40, p. 455-472, 2006. http://dx.doi.org/10.1287/trsc.1050.0135
SAVELSBERGH, M. W. P. The vehicle routing problem with time windows: minimizing route duration. ORSA Journal on Computing, v. 4, p. 146-154, 1992. http://dx.doi.org/10.1287/ijoc.4.2.146
TOTH, P.; VIGO, D. Fast local search algorithms for the handicapped persons transportation problem. In: OSMAN, I. H.; KELLY, J. P. (Eds.). Meta-heuristics: Theory and Applications. Boston: Kluwer, 2006. p. 60-71.
TOTH, P.; VIGO, D. Heuristic algorithms for the handicapped persons transportation problem. Transportation Science, v. 31, p. 60-71, 1997. http://dx.doi.org/10.1287/trsc.31.1.60
VITÓRIA (Município). Secretaria de Transportes, Trânsito e Infraestrutura Urbana - SETRAN. Cadeirantes contam com transporte porta a porta. Disponível em:
WOLFLER-CALVO, R.; COLORNI, A. An effective and fast heuristic for the dial-a-ride problem. 4OR: A Quarterly Journal of Operations Research, v. 5, p. 61-73, 2007.
Facebook
Google+
Twitter
LinkedIn
Mendeley
StumbleUpon
CiteULike
Reddit
Email