ارائه روشی برای انتخاب کوتاه ترین مسیر مقید با استفاده از برش های منطقی

نوع مقاله: مقاله پژوهشی

نویسندگان

دانشکده علوم پایه، گروه ریاضی کاربردی، دانشگاه علوم و فنون هوایی شهید ستاری، مهرآباد جنوبی، تهران، ایران.

چکیده

مسئله‌ی کوتاه­ترین مسیر یکی از مسائل کلاسیک و پرکاربرد بهینه‌سازی است که الگوریتم­های کارآمدی برای آن ارائه شده است. در این مسئله شبکه­ای شامل مجموعه­ای از نقاط و کمان­های بین آن­ها در‌نظر گرفته شده و به هر کمان پارامتری مانند طول، هزینه یا زمان طی مسیر نسبت داده می­شود. هدف اصلی مسئله، یافتن کوتاه­ترین یا کم­هزینه­ترین مسیر بین دو نقطه‌ی مشخص است. با در‌نظر گرفتن پارامتر دیگری برای هریک از کمان­ها و اضافه‌کردن یک محدودیت دیگر، به­صورت قید ظرفیت، مسئله به شرایط واقعی نزدیک­تر خواهد شد. این مسئله توسعه داده‌شده به مسئله‌ی کوتاه‌ترین مسیر مقید معروف است که پیچیدگی بالاتری دارد و برای حل آن به الگوریتم‌های کارآمدی نیاز است. در این مطالعه، یک روش حل برای این مسئله ارائه شده است که قادر است در مدت زمان کوتاهی به جواب بهین برسد. در این روش از یک الگوی تکراری حل مدل آزاد‌شده و اضافه‌کردن برش­های منطقی در هر تکرار استفاده می­شود. نتایج پیاده­سازی الگوریتم ارائه‌شده بر روی شبکه­های مختلف، کارایی آن را  به‌خوبی نشان می­دهد.

کلیدواژه‌ها

موضوعات


عنوان مقاله [English]

Providing a method for selecting the constrained shortest path problem using logical cuts

نویسندگان [English]

  • Sajad Moradi
  • Gholamreza Karamali
Faculty of Basic Sciences, Department of Applied Mathematics, Shahid Sattari Aeronautical University of Sciences and Technology, South Mehrabad, Tehran, Iran.
چکیده [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.

کلیدواژه‌ها [English]

  • network
  • Constrained routing
  • Relaxed model
  • Solution Algorithm
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.