modelización de una versión del algoritmo estándar para el problema del vendedor viajero
el caso de un centro de ambulancias
Palabras clave:
Areas urbanas, Toma de decisiones, Problema del viajante de comercio, Elección de rutaResumen
La eficiencia del servicio de transporte de pacientes es fundamental no solo para consultas, sino que también puede salvar vidas, considerando las condiciones actuales del tráfico urbano brasileño. En este servicio, las ambulancias han sido un recurso escaso en el contexto brasileño, aunque de gran importancia. Así, nos planteamos una situación que necesita soluciones que ayuden a la toma de decisiones desde un Centro de Ambulancias, utilizando el Problema del Vendedor Viajero para encontrar la ruta ideal. Los experimentos revelaron que el enfoque y la heurística utilizada producen soluciones relevantes, que pueden emplearse en un tiempo de respuesta corto.
Descargas
Citas
AKHAND, M. A. H.; AYON, S. I.; SHAHRIYAR, S. A.; SIDDIQUE, N.; ADELI, H. Discrete spider monkey optimization for travelling salesman problem. Applied Soft Computing, v. 86, p. 105887, 2020. Disponível em: <https://www.sciencedirect.com/science/article/abs/pii/S1568494619306684>. Acesso em: 16 ago. 2022.
ARINGHIERI, R.; BIGHARAZ, S.; DUMA, D.; GUASTALLA, A. Fairness in ambulance routing for post disaster management. Central European journal of operations research, v. 30, n. 1, p. 189-211, 2022. Disponível em: <https://link.springer.com/article/10.1007/s10100-021-00785-y>. Acesso em: 18ago. 2022.
BARRENA, E.; CANCA, D.; COELHO, L. C.; LAPORTE, G. Analysis of the selective traveling salesman problem with time-dependent profits. TOP, p. 1-29, 2022. Disponível em: <https://link.springer.com/article/10.1007/s11750-022-00632-6>. Acesso em: 18 ago. 2022.
BARVINOK, A.; FEKETE, S. P.; JOHNSON, D. S.; TAMIR, A.; WOEGINGER, G. J.; WOODROOFE, R. The geometric maximum traveling salesman problem. Journal of the ACM, v. 50, n. 5, p. 641-664, 2003. Disponível em: <https://dl.acm.org/doi/abs/10.1145/876638.876640>. Acesso em: 21 ago. 2022.
BERTOLINI, L. From “streets for traffic” to “streets for people”: can street experiments transform urban mobility? Transport reviews, v. 40, n. 6, p. 734-753, 2020. Disponível em: <https://www.tandfonline.com/doi/full/10.1080/01441647.2020.1761907>. Acesso em: 16 ago. 2022.
BOCCIA, M.; MASONE, A.; SFORZA, A.; STERLE, C. A column-and-row generation approach for the flying sidekick travelling salesman problem. Transportation Research Part C: Emerging Technologies, v. 124, p. 102913, 2021. Disponível em: <https://www.sciencedirect.com/science/article/abs/pii/S0968090X20308123>. Acesso em: 16 ago. 2022.
CLARKE, G.; WRIGHT, J. W. Scheduling of vehicles from a central depot to a number of delivery points. Operations research, v. 12, n. 4, p. 568-581, 1964. Disponível em: <https://pubsonline.informs.org/doi/epdf/10.1287/opre.12.4.568>. Acesso em: 01 set. 2023.
DANTZIG, G. B.; RAMSER, J. H. The truck dispatching problem. Management science, v. 6, n. 1, p. 80-91, 1759. Disponível em: <https://pubsonline.informs.org/doi/abs/10.1287/mnsc.6.1.80>. Acesso em: 03 set. 2022.
DEINEKO, V. G.; VAN DAL, R.; ROTE, G. The convex-hull-and-line traveling salesman problem: A solvable case. Information Processing Letters, v. 51, n. 3, p. 141-148, 1994. Disponível em: <https://www.sciencedirect.com/science/article/abs/pii/0020019094000719>. Acesso em: 16 ago. 2022.
DUMITRESCU, I.; ROPKE, S.; CORDEAU, J. F.; LAPORTE, G. The traveling salesman problem with pickup and delivery: polyhedral results and a branch-and-cut algorithm. Mathematical Programming, v. 121, p. 269-305, 2010. Disponível em: <https://link.springer.com/article/10.1007/s10107-008-0234-9>. Acesso em: 26 set. 2022.
ECHCHAKOUI, S. Why and how to merge Scopus and Web of Science during bibliometric analysis: the case of sales force literature from 1912 to 2019. Journal of Marketing Analytics, v. 8, p. 165-184, 2020. Disponível em: <https://link.springer.com/article/10.1057/s41270-020-00081-9>. Acesso em: 4 out. 2022.
EULER, L. Solution d’une question curieuse qui ne paraît soumise à aucune analyse. Mémoires de l'Académie Royale des Sciences et Belles Lettres, v. 15, p. 310-337, 1759. Disponível em: <https://scholarlycommons.pacific.edu/cgi/viewcontent.cgi?article=1308&context=euler-works>. Acesso em: 18 ago. 2022.
GIGANTE, R. L.; AZEVEDO, A. T. Study of the impact of the start time of work shift on the efficiency of an emergency system through a simulation model of discrete events. Gestão & Produção, v. 29, e4421 2022. Disponível em: <https://www.scielo.br/j/gp/a/pxMV8s6Qzcgg7z93D53fCkm/abstract/?lang=en>. Acesso em: 16 ago. 2022.
GONÇALVES, W.; OLIVEIRA, M. S.; ROCHA, A. R. Algoritmo genético aplicado ao problema de roteamento de veículos: problema do caixeiro viajante no setor varejista. Cadernos UniFOA, v. 15, n. 43, p. 11-23, 2020. Disponível em: <https://revistas.unifoa.edu.br/cadernos/article/view/3273>. Acesso em: 19 ago. 2022.
GUTIN, G.; KARAPETYAN, D. A memetic algorithm for the generalized traveling salesman problem. Natural Computing, v. 9, n. 1, p. 47-60, 2010. Disponível em: <https://link.springer.com/article/10.1007/s11047-009-9111-6>. Acesso em: 7 out. 2022.
HERNÁNDEZ-PÉREZ, H.; SALAZAR-GONZÁLEZ, J. J. A branch-and-cut algorithm for the split-demand one-commodity pickup-and-delivery travelling salesman problem. European Journal of Operational Research, v. 297, n. 2, p. 467-483, 2022. Disponível em: <https://www.sciencedirect.com/science/article/pii/S0377221721004689>. Acesso em: 4 out. 2022.
JACOBSEN, J. L.; READ, N.; SALEUR, H. Traveling salesman problem, conformal invariance, and dense polymers. Physical review letters, v. 93, n. 3, p. 038701, 2004. Disponível em: <https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.93.038701>. Acesso em: 16 ago. 2022.
SARQUIS JÚNIOR, M. C.; SOUZA, R. P.; LIRA LIMA, V. M. Construção jurídica do sistema orçamentário nacional: do orçamento público e seus princípios formadores. Brazilian Journal of Development, v. 8, n. 3, p. 19289-19306, 2022. Disponível em: <https://scholar.archive.org/work/vuxrioyjrjgatmbhaa6el4zhdu/access/wayback/https://brazilianjournals.com/index.php/BRJD/article/download/45374/pdf>. Acesso em: 19 ago. 2022.
LETCHFORD, A. N.; NASIRI, S. D.; THEIS, D. O. Compact formulations of the Steiner traveling salesman problem and related problems. European Journal of Operational Research, v. 228, n. 1, p. 83-92, 2013. Disponível em: <https://www.sciencedirect.com/science/article/pii/S037722171300091X>. Acesso em: 16 ago. 2022.
LI, W.; WANG, C.; HUANG, Y.; CHEUNG, Y. M. Heuristic smoothing ant colony optimization with differential information for the traveling salesman problem. Applied Soft Computing, v. 133, p. 109943, 2023. Disponível em: <https://www.sciencedirect.com/science/article/pii/S1568494622009929>. Acesso em: 27 set. 2022.
MIKCHAILOVITCH, A. S. Local search metaheuristics for capacitated vehicle routing problem: a comparative study. Trudy ISP RAN/Proc. ISP RAS, v. 31, n. 4, p. 121-138, 2019.
MOSAYEBI, M.; SODHI, M.; WETTERGREN, T. A. The traveling salesman problem with job-times (tspj). Computers & Operations Research, v. 129, p. 105226, 2021. Disponível em: <https://www.sciencedirect.com/science/article/pii/S0305054821000186>. Acesso em: 13 set. 2022.
OLIVEIRA CHAGAS, U.; SALTON, R. A. B.; SANTOS ARENAS, M. V.; SOUZA, V. B. P. Efetividade do princípio da economicidade na contratação de serviço de aluguel de veículos pela administração pública, realidade ou ficção? Conjecturas, v. 22, n. 2, p. 381-400, 2022. Disponível em: <http://www.conjecturas.org/index.php/edicoes/article/view/678>. Acesso em: 7 nov. 2022.
OUENNICHE, J.; RAMASWAMY, P. K.; GENDREAU, M. A dual local search framework for combinatorial optimization problems with TSP application. Journal of the Operational Research Society, v. 68, n. 11, p. 1377-1398, 2017. Disponível em: <https://www.tandfonline.com/doi/abs/10.1057/s41274-016-0173-4>. Acesso em: 17 set. 2022.
PERSYN, D.; DÍAZ-LANCHAS, J.; BARBERO, J. Estimating road transport costs between and within European Union regions. Transport Policy, v. 124, p. 33-42, 2022. Disponível em: <https://www.sciencedirect.com/science/article/pii/S0967070X20301827>. Acesso em: 29 ago. 2022.
RICHTER, M. A.; HAGENMAIER, M.; BANDTE, O.; PARIDA, V.; WINCENT, J. Smart cities, urban mobility and autonomous vehicles: How different cities needs different sustainable investment strategies. Technological Forecasting and Social Change, v. 184, p. 121857, 2022. Disponível em: <https://www.sciencedirect.com/science/article/pii/S004016252200381X>. Acesso em: 18 ago. 2022.
SAMARAKKODY, T.; ALAGALLA, H. Optimizing the multiple trip vehicle routing plan for a licensee green tea dealer in Sri Lanka. Modern Supply Chain Research and Applications, v. 3, n. 4, p. 246-261, 2021. Disponível em: <https://www.emerald.com/insight/content/doi/10.1108/MSCRA-10-2020-0027/full/html>. Acesso em: 21 ago. 2022.
SPETH, D.; SAUTER, V.; PLÖTZ, P.; SIGNER, T. Synthetic European road freight transport flow data. Data in brief, v. 40, p. 107786-107786, 2022. Disponível em: <https://www.sciencedirect.com/science/article/pii/S235234092101060X>. Acesso em: 21 ago. 2022.
ULTSCH, A.; LÖTSCH, J. Euclidean distance-optimized data transformation for cluster analysis in biomedical data (EDOtrans). BMC bioinformatics, v. 23, n. 1, p. 1-18, 2022. Disponível em: <https://bmcbioinformatics.biomedcentral.com/articles/10.1186/s12859-022-04769-w>. Acesso em: 21 ago. 2022.
WANG, Z.; GUO, J.; ZHENG, M.; WANG, Y. Uncertain multiobjective traveling salesman problem. European Journal of Operational Research, v. 241, n. 2, p. 478-489, 2015. Disponível em: <https://www.sciencedirect.com/science/article/pii/S0377221714007334>. Acesso em: 21 set. 2022.
ZHANG, Z.; HAN, Y. Discrete sparrow search algorithm for symmetric traveling salesman problem. Applied Soft Computing, v. 118, p. 108469, 2022. Disponível em: <https://www.sciencedirect.com/science/article/abs/pii/S1568494622000321>. Acesso em: 16 ago. 2022.
Archivos adicionales
Publicado
Cómo citar
Número
Sección
Licencia
Derechos de autor 2023 Revista Brasileira de Iniciação Científica
Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial-CompartirIgual 4.0.
