عنوان مقاله [English]
Shortest path problem is one of the practical issues in optimization, and there are many efficient algorithms in this area. In this issue, a network of some nodes and arcs is considered in which, each arc has a specific parameter such as distance or cost. The main objective is to find the shortest or least costly route between two distinct points. By considering an additional parameter and adding a new limitation, as a capacity constraint, the problem will be closer to the real world condition. This extended issue is known as the constrained shortest path problem and has a higher complexity order and practical algorithms are needed to solve it. In this study, an effective algorithm is presented that obtains the optimal solution within a short time. In this method, a repetitive pattern is used so that, in each iteration, the relaxed model, after adding a logical cut, is solved. The results of the implementation of the proposed algorithm on different networks show its efficiency.
Ahuja, R. K., Magnanti, T. L., Orlin, J. B., & Weihe, K. (1995). Network flows: theory, algorithms and applications. ZOR-methods and models of operations research, 41(3), 252-254.
Cherkassky, B. V., Goldberg, A. V., & Radzik, T. (1996). Shortest paths algorithms: Theory and experimental evaluation. Mathematical programming, 73(2), 129-174.
Zhan, F. B., & Noon, C. E. (1998). Shortest path algorithms: an evaluation using real road networks. Transportation science, 32(1), 65-73.
Sedeño-Noda, A., & González-Martín, C. (2010). Shortest path simplex algorithm with a multiple pivot rule: a comparative study. Asia-pacific journal of operational research, 27(06), 677-691.
Lozano, L., & Medaglia, A. L. (2013). On an exact method for the constrained shortest path problem. Computers & operations research, 40(1), 378-384.
Garey, M. R. (1979). Computers and intractability: A guide to the theory of np-completeness. Revista Da Escola De Enfermagem Da USP, 44(2), 340.
Tarapata, Z. (2003). Military route planning in battlefield simulation: effectiveness problems and potential solutions. Journal of telecommunications and information technology, 47-56.
Mora, A. M., Merelo, J. J., Laredo, J. L. J., Millán, C., & Torrecillas, J. (2009). CHAC, A MOACO algorithm for computation of bi‐criteria military unit path in the battlefield: Presentation and first results. International journal of intelligent systems, 24(7), 818-843.
MirHassani, S. A., Moradi, S., & Taghinezhad, N. (2011). Algorithm for long-term scheduling of multiproduct pipelines. Industrial & engineering chemistry research, 50(24), 13899-13910.
Avella, P., Boccia, M., & Sforza, A. (2004). Resource constrained shortest path problems in path planning for fleet management. Journal of mathematical modelling and algorithms, 3(1), 1-17.
Eppstein, D. (1998). Finding the k shortest paths. SIAM journal on computing, 28(2), 652-673.
Pugliese, L. D. P., & Guerriero, F. (2013). A survey of resource constrained shortest path problems: Exact solution approaches. Networks, 62(3), 183-200.
Handler, G. Y., & Zang, I. (1980). A dual algorithm for the constrained shortest path problem. Networks, 10(4), 293-309.
Santos, L., Coutinho-Rodrigues, J., & Current, J. R. (2007). An improved solution algorithm for the constrained shortest path problem. Transportation research part B: methodological, 41(7), 756-771.
Carlyle, W. M., Royset, J. O., & Kevin Wood, R. (2008). Lagrangian relaxation and enumeration for solving constrained shortest‐path problems. Networks: an international journal, 52(4), 256-270.
Verstichel, J., Kinable, J., De Causmaecker, P., & Berghe, G. V. (2015). A Combinatorial Benders׳ decomposition for the lock scheduling problem. Computers & operations research, 54, 117-128.
Gendron, B., Garroppo, R. G., Nencioni, G., Scutellà, M. G., & Tavanti, L. (2013). Benders decomposition for a location-design problem in green wireless local area networks. Electronic notes in discrete mathematics, 41, 367-374.