On Multi-Objective Minimum Spanning Tree Problem under Uncertain Paradigm
Minimum spanning tree problem (MSTP) has allured many researchers and practitioners due to its varied range of applications in real world scenarios. Modelling these applications involves the incorporation of indeterminate phenomena based on their subjective estimations. Such phenomena can be represe...
| Main Authors: | , , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-01-01
|
| Series: | Symmetry |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2073-8994/14/1/106 |
| _version_ | 1797490085370789888 |
|---|---|
| author | Saibal Majumder Partha Sarathi Barma Arindam Biswas Pradip Banerjee Bijoy Kumar Mandal Samarjit Kar Paweł Ziemba |
| author_facet | Saibal Majumder Partha Sarathi Barma Arindam Biswas Pradip Banerjee Bijoy Kumar Mandal Samarjit Kar Paweł Ziemba |
| author_sort | Saibal Majumder |
| collection | DOAJ |
| description | Minimum spanning tree problem (MSTP) has allured many researchers and practitioners due to its varied range of applications in real world scenarios. Modelling these applications involves the incorporation of indeterminate phenomena based on their subjective estimations. Such phenomena can be represented rationally using uncertainty theory. Being a more realistic variant of MSTP, in this article, based on the principles of the uncertainty theory, we have studied a multi-objective minimum spanning tree problem (MMSTP) with indeterminate problem parameters. Subsequently, two uncertain programming models of the proposed uncertain multi-objective minimum spanning tree problem (UMMSTP) are developed and their corresponding crisp equivalence models are investigated, and eventually solved using a classical multi-objective solution technique, the epsilon-constraint method. Additionally, two multi-objective evolutionary algorithms (MOEAs), non-dominated sorting genetic algorithm II (NSGAII) and duplicate elimination non-dominated sorting evolutionary algorithm (DENSEA) are also employed as solution methodologies. With the help of the proposed UMMSTP models, the practical problem of optimizing the distribution of petroleum products was solved, consisting in the search for symmetry (balance) between the transportation cost and the transportation time. Thereafter, the performance of the MOEAs is analyzed on five randomly developed instances of the proposed problem. |
| first_indexed | 2024-03-10T00:26:54Z |
| format | Article |
| id | doaj.art-ac30086ae4ce48df855552ff2689a27c |
| institution | Directory Open Access Journal |
| issn | 2073-8994 |
| language | English |
| last_indexed | 2024-03-10T00:26:54Z |
| publishDate | 2022-01-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Symmetry |
| spelling | doaj.art-ac30086ae4ce48df855552ff2689a27c2023-11-23T15:33:31ZengMDPI AGSymmetry2073-89942022-01-0114110610.3390/sym14010106On Multi-Objective Minimum Spanning Tree Problem under Uncertain ParadigmSaibal Majumder0Partha Sarathi Barma1Arindam Biswas2Pradip Banerjee3Bijoy Kumar Mandal4Samarjit Kar5Paweł Ziemba6Department of Computer Science and Engineering, NSHM Knowledge Campus Durgapur, Durgapur 713212, IndiaCenter for Distance and Online Education, The University of Burdwan, Burdwan 713104, IndiaSchool of Mines and Metallurgy, Kazi Nazrul University (Public University), Asansol 713340, IndiaDepartment of Mathematics, National Institute of Technology Durgapur, Durgapur 713209, IndiaDepartment of Computer Science and Engineering, NSHM Knowledge Campus Durgapur, Durgapur 713212, IndiaDepartment of Mathematics, National Institute of Technology Durgapur, Durgapur 713209, IndiaInstitute of Management, University of Szczecin, 70-453 Szczecin, PolandMinimum spanning tree problem (MSTP) has allured many researchers and practitioners due to its varied range of applications in real world scenarios. Modelling these applications involves the incorporation of indeterminate phenomena based on their subjective estimations. Such phenomena can be represented rationally using uncertainty theory. Being a more realistic variant of MSTP, in this article, based on the principles of the uncertainty theory, we have studied a multi-objective minimum spanning tree problem (MMSTP) with indeterminate problem parameters. Subsequently, two uncertain programming models of the proposed uncertain multi-objective minimum spanning tree problem (UMMSTP) are developed and their corresponding crisp equivalence models are investigated, and eventually solved using a classical multi-objective solution technique, the epsilon-constraint method. Additionally, two multi-objective evolutionary algorithms (MOEAs), non-dominated sorting genetic algorithm II (NSGAII) and duplicate elimination non-dominated sorting evolutionary algorithm (DENSEA) are also employed as solution methodologies. With the help of the proposed UMMSTP models, the practical problem of optimizing the distribution of petroleum products was solved, consisting in the search for symmetry (balance) between the transportation cost and the transportation time. Thereafter, the performance of the MOEAs is analyzed on five randomly developed instances of the proposed problem.https://www.mdpi.com/2073-8994/14/1/106uncertain programmingmulti-objective minimum spanning tree problemepsilon-constraint methodNSGAIIDENSEAdistribution network management |
| spellingShingle | Saibal Majumder Partha Sarathi Barma Arindam Biswas Pradip Banerjee Bijoy Kumar Mandal Samarjit Kar Paweł Ziemba On Multi-Objective Minimum Spanning Tree Problem under Uncertain Paradigm Symmetry uncertain programming multi-objective minimum spanning tree problem epsilon-constraint method NSGAII DENSEA distribution network management |
| title | On Multi-Objective Minimum Spanning Tree Problem under Uncertain Paradigm |
| title_full | On Multi-Objective Minimum Spanning Tree Problem under Uncertain Paradigm |
| title_fullStr | On Multi-Objective Minimum Spanning Tree Problem under Uncertain Paradigm |
| title_full_unstemmed | On Multi-Objective Minimum Spanning Tree Problem under Uncertain Paradigm |
| title_short | On Multi-Objective Minimum Spanning Tree Problem under Uncertain Paradigm |
| title_sort | on multi objective minimum spanning tree problem under uncertain paradigm |
| topic | uncertain programming multi-objective minimum spanning tree problem epsilon-constraint method NSGAII DENSEA distribution network management |
| url | https://www.mdpi.com/2073-8994/14/1/106 |
| work_keys_str_mv | AT saibalmajumder onmultiobjectiveminimumspanningtreeproblemunderuncertainparadigm AT parthasarathibarma onmultiobjectiveminimumspanningtreeproblemunderuncertainparadigm AT arindambiswas onmultiobjectiveminimumspanningtreeproblemunderuncertainparadigm AT pradipbanerjee onmultiobjectiveminimumspanningtreeproblemunderuncertainparadigm AT bijoykumarmandal onmultiobjectiveminimumspanningtreeproblemunderuncertainparadigm AT samarjitkar onmultiobjectiveminimumspanningtreeproblemunderuncertainparadigm AT pawełziemba onmultiobjectiveminimumspanningtreeproblemunderuncertainparadigm |