Modelagem do traveling salesman problem com dependência dos tempos de viagem
o caso de uma central de ambulâncias
Palavras-chave:
Áreas urbanas, Tomada de decisão, Problema do caixeiro viajante, Escolha da rotaResumo
A eficiência do serviço de transporte de pacientes é essencial não só para atendimentos, como também, pode salvar vidas, considerando as condições do trânsito urbano brasileiro atual. Neste serviço, as ambulâncias têm sido um recurso escasso, no contexto brasileiro, embora de elevada importância. Assim, consideramos uma situação com necessidade de soluções que auxiliem tomadas de decisões a partir de uma Central de ambulâncias, usando o Traveling Salesman Problem para encontrar a rota ideal. Os experimentos revelaram que a abordagem e heurística utilizadas produzem soluções relevantes, que podem ser empregadas em um tempo de resposta curto.
Downloads
Referências
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.
Arquivos adicionais
Publicado
Como Citar
Edição
Seção
Licença
Copyright (c) 2023 Revista Brasileira de Iniciação Científica
Este trabalho está licenciado sob uma licença Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
