Implementação em C++ do algoritmo proposto por Martins e Pascoal (2003)[1] para obtenção dos k-caminhos mais curtos entre um par origem-destino Adaptado a partir da implementação disponível em https://github.com/yan-qi/k-shortest-paths-cpp-version
As adaptações feitas permitem que seja analisado mais de um par OD de cada vez. Por preferência pessoal, também alterei o programa para funcionar a partir de um executável que lê um arquivo de entrada e gera um arquivo de saída para processamento posterior por outros programas.
Um problema conhecido e que está sendo analisado é que o programa apresenta um memory leak, que pode tornar inviável as análises de problemas muito grandes.
A pasta 'others' contém os programas desenvolvidos por mim para meu Projeto Final de Graduação, para utilização nas etapas anteriores e posteriores à obtenção dos k-caminhos. O Projeto utilizou estes programas para aplicar o modelo proposto por Markovic et al. (2015)[2] para o Problema de Captura de Fluxo Evasivo (PCFE - Evasive Flow-Capturing Problem).
1 - GetLinks: recebe os dados do TransCAD e a lista com todas as vias da rede e gera a instância de entrada para o YenKfFull
2 - CplexOut: recebe o arquivo de saída do YenKfFull e a instância de entrada e gera o modelo expandido do PCFE para otimização no CPLEX.
3 - Facility Links: a partir dos nós de origem e destino monitorados na solução ótima, definidos pelo CPLEX e da lista com todas as vias da rede, gera uma lista com o ID das vias monitoradas para visualização no TransCAD.
[1] MARTINS, E. Q. V., PASCOAL, M. M. B, 2003, A new implementation of Yen’s ranking loopless paths algorithm, Quarterly Journal of the Belgian, French and Italian Operations Research Societies, vol 1(2), p. 121-133.
[2]MARKOVIĆ, N., RYZHOV, I. O., SCHONFELD, P., 2015, Evasive Flow Capture: Optimal location of Weigh-in-Motion Systems, Tollbooths, and Security Checkpoints, Networks, vol. 65(1), p. 22-44.