Schoobrary رجوع
العودة إلى البحث
رسائل ماجيستير الفرنسية 2011 f9233c24-209a-4b66-b746-3878bc176b1a

Sur une relation entre la coloration de graphes et le problème du voyageur de commerce multiple

Hacene Ait Haddadene , Mouaouia Cherif Bouzid

كلية الرياضيات-جامعة العلوم والتكنولوجيا هواري بومدين - الجزائر · الجزائر

الموضوعات

علوم بحتة وطبيعية

الملخص

Le problème du voyageur de commerce multiple (m-TSP) consiste en l'optimisation de la visite d'un ensemble de villes par une flotte de véhicules basés à un dépôt. Ce problème qui est NP-difficile a mené à la conception de méthodes de résolution exactes et approchées. Les heuristiques de routage s'inscrivent généralement dans la classe des méthodes à deux phases: chercher une tournée globale puis la séparer en m tournées \emph{ou} partitionner les villes à visiter puis chercher une tournée pour chacun des véhicules. En nous inscrivant dans cette dernière approche, nous présentons l'application inédite au m-TSP d'une méthode de clustering basée sur la b-coloration. Cette application a pour but de développer une heuristique efficace pour le m-TSP ou l'une de ses variantes en générant un clustering intéressant des villes à visiter. Nous reprenons les principaux travaux effectués dans les domaines du m-TSP et de la méthode et nous révélons une manière de dénombrer le nombre de routages possibles dans un m-TSP asymétrique. Nous présentons ensuite notre approche, nous la testons et nous l'évaluons sur des instances connues dans la littérature. Enfin, nous dévoilons une perspective intéressante pour la résolution d'une variante du m-TSP par notre application

التعريف والنوع

رقم الوثيقة
f9233c24-209a-4b66-b746-3878bc176b1a
رقم العقد
0
نوع الوسائط
Crawler
نوع المحتوى
الرسائل العلمية
صيغة المصدر
رسائل ماجيستير
نوع الملف
word
أسماء الملفات
1377316_1.doc, 1377316_2.pdf

بيانات النشر

ألقاب المؤلفين
[{"name_ar":"Hacene Ait Haddadene ","title_ar":"اشراف","title_en":"Supervision"},{"name_ar":"Mouaouia Cherif Bouzid","title_ar":"اعداد","title_en":"Preparation"}]
اللغة
French

المصدر والدورية

اسم المصدر
Sur une relation entre la coloration de graphes et le problème du voyageur de commerce multiple

المحتوى والصفحات

عدد الصفحات
0
ترجمة الملخص
The multiple traveling salesman problem (m-TSP) consists in optimizingthe visit of a set of cities by a fleet of vehicles based at a depot. This problem, whichis NP-hard, has led to the design of several exact and heuristic methods. Most ofthe routing heuristics fall into the class of two phases methods : find one globalroute then split it intomroutesorfind a partition of the cities then a route forevery vehicle. According to the latter approach, we present a new application to them-TSP of a b-coloring based clustering method. Our goal is to design an efficientheuristic for them-TSP or a variation by generating an interesting clustering of thecities that are to be visited. We review the main results in the fields of them-TSP andthe b-coloring clustering method and we present a way for counting the number ofpossible routings in the asymmetricm-TSP. Our approach is then presented, testedand evaluated against benchmarks. Finally, we reveal an interesting perspective forsolving a variation of them-TSP by our approach
كلمات الباحثين
b-coloring based clustering, clustering par la b-coloration, combinatoire énumérative, enu-merative combinatorics, Multiple traveling salesman problem, Problème du voyageur de commerce multiple

إشراف وإعداد

الإشراف
Hacene Ait Haddadene
الإعداد
Mouaouia Cherif Bouzid

الاقتباسات الببليوغرافية

APA

Hacene Ait Haddadene و Mouaouia Cherif Bouzid. (2011). Sur une relation entre la coloration de graphes et le problème du voyageur de commerce multiple. أطروحة(رسائل ماجيستير). كلية الرياضيات-جامعة العلوم والتكنولوجيا هواري بومدين - الجزائر. الجزائر.

MLA

Hacene Ait Haddadene و Mouaouia Cherif Bouzid. Sur une relation entre la coloration de graphes et le problème du voyageur de commerce multiple. 2011. كلية الرياضيات-جامعة العلوم والتكنولوجيا هواري بومدين - الجزائر، رسائل ماجيستير.