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
MLA