A LAGRANGEAN RELAXATION-BASED SOLUTION APPROACH FOR MULTICOMMODITY NETWORK DESIGN PROBLEM WITH CAPACITY VIOLATIONS

Abstract

In this study, we formulate and compare two different Lagrangean relaxation-based decompositions for multicommodity network problems with penalized constraints. These problems are different versions of capacitated multicommodity network problems where capacity constraints can be violated for additional penalty costs. These costs are reflected as nonlinear terms in the objective function; hence, these problems turn out to be nonlinear mixed integer optimization problems. To the best of our knowledge, there is no exact solution algorithm for this type of problem. We propose two kinds of Lagrangean relaxation-based decompositions and solve these problems with the subgradient algorithm. The resulting subproblems are easy to solve and the proposed algorithms can reach reasonable solutions where CPLEX solver cannot even find a solution. In the study, we also conduct a computational analysis where we compare two relaxations over various performance measures. Even though two relaxations present similar performances in terms of computation times and the number of iterations, we observed that Relaxation 1 statistically outperforms Relaxation 2.

Keywords

• Multicommodity Network Design Problem
• Lagrangean Relaxation
• Subgradient Algorithm
• Decomposition

KAPASİTE İHLALLİ ÇOKLU MAL ŞEBEKE DİZAYN PROBLEMİ İÇİN LAGRANGEAN GEVŞETMESİ TABANLI BİR ÇÖZÜM YAKLAŞIMI

Abstract

Bu çalışmada, cezalandırıcı kısıtlara sahip çoklu mal şebeke problemi için Lagrangean gevşetmesi tabanlı iki farklı ayrıştırma yaklaşımı formüle edilmekte ve karşılaştırılmaktadır. Bu problemler kapasite kısıtlarının ilave bir ceza maliyeti ile ihlal edilebilediği kapasite kısıtlı çoklu mal şebeke problemlerinin farklı versiyonlarıdır. Bu maliyetler amaç fonksiyonuna doğrusal olmayan terimler olarak yansıtılmakta, bu kapsamda bu problemler doğrusal olmayan karışık tam sayılı eniyileme problemlerine dönüşmektedir. Bilgimiz dahilinde, bu tip problemlerin çözümü için herhangi bir kesin çözüm algoritması bulunmamaktadır. Bu problemler için iki farklı Lagrangean gevşetmesi tabanlı ayrıştırma teklif etmekte ve gradyant altı algoritması ile çözmekteyiz. Ortaya çıkan alt-problemler kolaylıkla çözülebilmekte ve önerilen algoritmalar CPLEX çözücünün herhangi bir çözüm bile bulamadığı durumlar için makul sonuçlar elde etmektedir. Çalışmada ayrıca bu iki gevşetmenin farklı performans metrikleri bazında karşılaştırmasının yapıldığı bir hesaplamalı analiz de yapmaktayız. Her ne kadar iki gevşetme de çözüm süresi ve iterasyon adedi açısından benzer performanslar gösterse de Gevşetme 1’nin istatistiksel olarak Gevşetme 2’den daha üstün olduğunu gözlemledik.

Keywords

• Çoklu Mal Şebeke Dizayn Problemi
• Lagrangean Gevşetmesi
• Gradyan Altı Algoritması
• Ayrıştırma

References

1. Ahuja, R. K., Magnanti, T. L. and Orlin, J. B. (1993). Network Flows: Theory, Algorithms, and Applications, New Jersey, Prentice Hall.
2. Anisi, M., and Fathabadi, H. S. (2019). "Survivable multi-commodity network flow design: case of node capacities and arc failure". International Journal of Operational Research, 35(3), 355–365. doi:10.1504/IJOR.2019.10022713.
3. Bektaş, T., Chouman, M. and Crainic, T. G. (2010). "Lagrangean-based decomposition algorithms for multicommodity network design problems with penalized constraints". Networks, 55(3), 171–180.
4. Belotti, P., Malucelli, F., and Brunetta, L. (2007). "Multicommodity network design with discrete node costs". Networks, 49(1), 90–99.
5. Chouman, M., Crainic, T. G., and Gendron, B. (2018). "The Iimpact of filtering in a branch-and-cut algorithm for multicommodity capacitated fixed charge network design". EURO Journal on Computational Optimization, Vol. 6, 143–184.
6. Costa, A. M. (2005). "A survey on benders decomposition applied to fixed-charge network design problems". Computers & Operations Research, 32(6), 1429–1450. doi:10.1016/j.cor.2003.11.012.
7. Costa, A. M., Cordeau, J.-F. and Gendron, B. (2009). "Benders, metric and cutset inequalities for multicommodity capacitated network design". Computational Optimization and Applications, Vol. 42, 371–392. doi:10.1007/s10589-007-9122-0.
8. Crainic, T. G., and Rousseau, J.-M. (1986). "Multicommodity, multimode freight transportation: A general modeling and algorithmic framework for the service network design problem". Transportation Research Part B: Methodological, 20(3), 225–242. doi:10.1016/0191-2615(86)90019-6.

9. Crainic, T. G, Frangioni, A., and Gendron, B. (2001). "Bundle-based relaxation methods for multicommodity capacitated fixed charge network design". Discrete Applied Mathematics, Vol. 112, Issues 1–3, 73–99. doi:10.1016/S0166-218X(00)00310-3.
10. Gendron, B., and Gouveia, L. (2016). "Reformulations by discretization for piecewise linear integer multicommodity network flow problems". Transportation Science, 51(2), 629–649.
11. Ghaffarinasab, N., Zare Andaryan, A., and Ebadi Torkayesh, A. (2020). "Robust single allocation p-hub median problem under hose and hybrid demand uncertainties: models and algorithms". International Journal of Management Science and Engineering Management, 15(3), 184-195.
12. Guimarães, L. R., de Sousa, J. P., and Prata, B. D. A. (2020). "Variable fixing heuristics for the capacitated multicommodity network flow problem with multiple transport lines, a heterogeneous fleet and time windows". Transportation Letters, 1-10.
13. Holmberg, K., and Yuan, D. (2000). "A Lagrangian heuristic based branch-and-bound approach for the capacitated network design problem". Operations Research, 48(3), 461–481.
14. Karsten, C. V., Pisinger, D., Røpke, S., and Brouer, B. D. (2015). "The time constrained multi-commodity network flow problem and its application to liner shipping network design". Transportation Research Part E: Logistics and Transportation Review, Vol. 76, 122–138. doi:10.1016/j.tre.2015.01.005.
15. Katayama, N., Chen, M., and Kubo, M. (2009). "A capacity scaling heuristic for the multicommodity capacitated network design problem". Journal of Computational and Applied Mathematics, 232(1), 90–101. doi:10.1016/j.cam.2008.10.055.
16. Kazemzadeh, M. R. A., Bektaş, T., Crainic, T. G., Frangioni, A., Gendron, B., and Gorgone, E. (2021). "Node-based Lagrangian relaxations for multicommodity capacitated fixed-charge network design". Discrete Applied Mathematics. doi:10.1016/j.dam.2020.12.024.
17. Moradi, S., Raith, A., and Ehrgott, M. (2015). "A bi-objective column generation algorithm for the multi-commodity minimum cost flow problem". European Journal of Operational Research, 244(2), 369–378. doi:10.1016/j.ejor.2015.01.021.
18. Oğuz, M., Bektaş, T., and Bennell, J. A. (2018). "Multicommodity flows and Benders decomposition for restricted continuous location problems". European Journal of Operational Research, 266(3), 851–863. doi:10.1016/j.ejor.2017.11.033.
19. Paraskevopoulos, D. C., Gürel, S., and Bektaş, T. (2016). "The congested multicommodity network design problem". Transportation Research Part E: Logistics and Transportation Review, Vol. 85, 166–187. doi:10.1016/j.tre.2015.10.007.
20. Salimifard, K., and Bigharaz, S. (2020). "The multicommodity network flow problem: State of the art classification, applications, and solution methods". Operational Research, 1-47. doi:10.1007/s12351-020-00564-8.
21. Trivella, A., Corman, F., Koza, D. F., and Pisinger, D. (2021). "The multi-commodity network flow problem with soft transit time constraints: Application to liner shipping". Transportation Research Part E: Logistics and Transportation Review, 150, 102342.
22. Yousefi Nejad Attari, M., Ebadi Torkayesh, A., Malmir, B., and Neyshabouri Jami, E. (2020). "Robust possibilistic programming for joint order batching and picker routing problem in warehouse management". International Journal of Production Research, 59(2), 1-19.
23. Wang, I.-L. (2018a). "Multicommodity Network Flows : A Survey , Part I : Applications and Formulations". International Journal of Operational Research, 15(4), 145–153. doi:10.6886/IJOR.201812.
24. Wang, I.-L. (2018b). "Multicommodity Network Flows : A Survey, Part II : Solution Methods". International Journal of Operational Research, 15(4), 155–173.
25. Wolsey, L. A. (1998). Integer Programming. New York, John Wiley & Sons.