Production
https://prod.org.br/doi/10.1590/S0103-65132013005000044?lang=en
Production
Article

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

Downloads: 1
Views: 137

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: . Acesso em: 07 abril 2010.

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.
5883a4447f8c9da00c8b4866 production Articles
Links & Downloads

Production

Share this page
Page Sections