Facility Location with Tree Topology and Radial Distance Constraints
المؤلفون المشاركون
Adasme, Pablo
Firoozabadi, Ali Dehghan
المصدر
العدد
المجلد 2019، العدد 2019 (31 ديسمبر/كانون الأول 2019)، ص ص. 1-29، 29ص.
الناشر
Hindawi Publishing Corporation
تاريخ النشر
2019-11-21
دولة النشر
مصر
عدد الصفحات
29
التخصصات الرئيسية
الملخص EN
Let Gd=V,Ed be an input disk graph with a set of facility nodes V and a set of edges Ed connecting facilities in V.
In this paper, we minimize the total connection cost distances between a set of customers and a subset of facility nodes S⊆V and among facilities in S, subject to the condition that nodes in S simultaneously form a spanning tree and an independent set according to graphs G¯d and Gd, respectively, where G¯d is the complement of Gd.
Four compact polynomial formulations are proposed based on classical and set covering p-Median formulations.
However, the tree to be formed with S is modelled with Miller–Tucker–Zemlin (MTZ) and path orienteering constraints.
Example domains where the proposed models can be applied include complex wireless and wired network communications, warehouse facility location, electrical power systems, water supply networks, and transportation networks, to name a few.
The proposed models are further strengthened with clique valid inequalities which can be obtained in polynomial time for disk graphs.
Finally, we propose Kruskal-based heuristics and metaheuristics based on guided local search and simulated annealing strategies.
Our numerical results indicate that only the MTZ constrained models allow obtaining optimal solutions for instances with up to 200 nodes and 1000 users.
In particular, tight lower bounds are obtained with all linear relaxations, e.g., less than 6% for most of the instances compared to the optimal solutions.
In general, the MTZ constrained models outperform path orienteering ones.
However, the proposed heuristics and metaheuristics allow obtaining near-optimal solutions in significantly short CPU time and tight feasible solutions for large instances of the problem.
نمط استشهاد جمعية علماء النفس الأمريكية (APA)
Adasme, Pablo& Firoozabadi, Ali Dehghan. 2019. Facility Location with Tree Topology and Radial Distance Constraints. Complexity،Vol. 2019, no. 2019, pp.1-29.
https://search.emarefa.net/detail/BIM-1133343
نمط استشهاد الجمعية الأمريكية للغات الحديثة (MLA)
Adasme, Pablo& Firoozabadi, Ali Dehghan. Facility Location with Tree Topology and Radial Distance Constraints. Complexity No. 2019 (2019), pp.1-29.
https://search.emarefa.net/detail/BIM-1133343
نمط استشهاد الجمعية الطبية الأمريكية (AMA)
Adasme, Pablo& Firoozabadi, Ali Dehghan. Facility Location with Tree Topology and Radial Distance Constraints. Complexity. 2019. Vol. 2019, no. 2019, pp.1-29.
https://search.emarefa.net/detail/BIM-1133343
نوع البيانات
مقالات
لغة النص
الإنجليزية
الملاحظات
Includes bibliographical references
رقم السجل
BIM-1133343
قاعدة معامل التأثير والاستشهادات المرجعية العربي "ارسيف Arcif"
أضخم قاعدة بيانات عربية للاستشهادات المرجعية للمجلات العلمية المحكمة الصادرة في العالم العربي
تقوم هذه الخدمة بالتحقق من التشابه أو الانتحال في الأبحاث والمقالات العلمية والأطروحات الجامعية والكتب والأبحاث باللغة العربية، وتحديد درجة التشابه أو أصالة الأعمال البحثية وحماية ملكيتها الفكرية. تعرف اكثر