مجلة اقتصاديات شمال افريقيا
Volume 20, Numéro 1, Pages 231-248
2024-03-03
Application Of Minimal Spanning Tree Search Algorithms To The Resolution Of Graph Problems: Case Of Salting And Snow Removal Of The Road Network Of The City Of Tiaret
Authors : Setti Hamid . Beladjine Khaldia . Berradia Slimane .
Abstract
The main objective of this study is to treat a primordial subject of the optimization of graph and network problems, namely the problem of finding the spanning tree of minimum weight, which consists of identifying and determining the tree which connects all vertices of a graph using a set of edges whose cost is minimal. Through this research study we address the problem of salting and snow removal from the road network of the city of Tiaret during winter by the municipal authorities and services. Our mission is to determine a partial road network (sub-network) from the initial road network of the town of Tiaret, which will have to be salted and cleared of snow by these authorities and services. The application of graph theory techniques for modeling the problem, and the use of the main search algorithms for the minimum weight spanning tree, allowed the study to propose the optimal subnetwork which contains the main roads of the road network of the city of Tiaret, to salt and clear snow at the lowest possible cost. الهدف الرئيسي من هذه الدراسة هو معالجة موضوع أساسي يتعلق بأمثلية مسائل نظرية البيان والشبكات، وهي مشكلة البحث عن الشجرة الممتدة ذات الوزن الأدنى، التي تقوم على تحديد الشجرة التي تربط جميع قمم بيان باستخدام مجموعة من الاحرف بأقل تكلفة. من خلال هذه الدراسة البحثية نتناول مشكلة التمليح وإزالة الثلوج من شبكة الطرق لمدينة تيارت خلال فترة الشتاء من قبل السلطات و المصالح البلدية. مهمتنا هو تحديد شبكة طرق جزئية و فرعية من شبكة الطرق الأولية لمدينة تيارت، و التي سيتعين تمليحها و إزالة الثلوج منها . إن تطبيق كل من تقنيات نظرية البيان لنمذجة المشكلة، و استخدام الخوارزميات الرئيسية للبحث عن الشجرة الممتدة ذات الوزن الأدنى، أتاح للدراسة اقتراح الشبكة الفرعية و الجزئية المثلى التي تتضمن الطرق الاساسية لشبكة طرق مدينة تيارت، الواجب على السلطات و المصالح البلدية تمليحها وإزالة الثلوج منها بأقل تكلفة ممكنة.
Keywords
graph theory ; minimal spanning tree ; road salting ; snow removal ; deicing ; نظرية البيان ; الشجرة المثلى ; تمليح الطرق ; ازالة الثلج ; ازالة الجليد
Les articles similaires
بوسالم أحلام
.
عابد يوسف
.
ص 117-132.
Yahia Zeghoudi
.
pages 74-88.
Mohammed Dib
.
pages 63-85.
Said Houari Amel
.
pages 257-268.
Zoubeidi Malika
.
Dahane Azedine
.
Kouadria Mustapha
.
pages 654-664.
