Informations
Directeur de thèse :
Année de début :
Fin 2009
Université :
Université Constantine 2
Soutenance
Date de soutenance :
12 Juin 2016
Membres de Jury :
Benmohammed Mohamed
Atmani Baghdad
Khelfi Med Fayçal
Mostefai Sihem
Manuscrit
Téléchargement :
Détails
Titre :
Optimization Methods for Logistics Routing

Résumé :

Les défis logistiques abondent dans de nombreux domaines ; bonnes solutions ne sont pas si bondante, et sont donc à la fois intérêt commercial et théorique. Les problèmes de tournées des véhicules (VRP) est l’un des plus difficiles des problèmes d’optimisation combinatoire qui modélise les problèmes du monde rencontrés dans la distribution physique des marchandises. Il consiste à servir les demandes de plusieurs clients au coût de voyage minimal en respectant des contraintes spécifiques. L’établissement des méthodes de résolution pour les problèmes de tournées de véhiculesdoitélaborerdesapprochesadaptéesrépondantauxcontraintes. Par conséquent, l’objectif de cette thèse est de développer des méthodes efficaces qui produisent des bonnes solutions de qualité aux problèmes VRP dans un temps de calcul raisonnable.

Afin de développer des méta-heuristiques efficaces, cette thèse présente tout d’abord deux nouvelles heuristiques développées, à savoir un algorithme évolutionnaire hybride et un Algorithme GRASP basé sur une heuristique randomisée pour résoudre la petite/ moyenne échelle du VRP. En second lieu, elle propose une nouvelle stratégie parallèle coopérative qui résout les grandes instances du VRP, en tenant compte du temps et de la complexité de l’approche proposée.

Les méthodes sont testées sur les problèmes de VRP de référence bien connus, petits et grands ensembles de données. La complexité de calcul des méthodes de résolution sont analysés et les résultats expérimentaux ont été rapportés.


Mots clés :
Problèmes de tournées de véhicules Heuristiques Algorithmes évolutionnaires Le coût logistique Des approches coopératives parallèles.
Title:
Optimization Methods for Logistics Routing

Abstract:

Logistical challenges abound in many fields; good solutions are not so abundant, and so are of both commercial and theoretical interest. The subset of routing problems has received particular attention. In fact, Vehicle Routing Problem (VRP) is one of the most challenging combinatorial optimization problems that models real-world problems encountered in the physical distribution of goods. It consists in serving the request of locations at minimal travel cost respecting specific constraints. Established Vehicle Routing Problem solution methods must be adapted to find solutions fulfilling these requirements. Therefore, the goal of this thesis is developing efficient methods that produce good quality solutions to VRP in a reasonable computing time.

In order to develop effective metaheuristics, this thesis presents firstly two novel heuristics developed, namely Hybrid Evolutionary Algorithm and AGRASP Algorithm Based on New Randomized Heuristic for solving the small/medium scale of the VRP. Secondly, it proposes a new parallel cooperative strategy that solves the large-scale instances of the VRP, taking into account the time and the complexity of the proposed approach.

The methods are tested on the well-known VRP benchmark problems, small and large data sets. The computational complexity of the solution methods are analyzed and experimental results have been reported.


Keywords:
Vehicle Routing Problems Heuristic methods Evolutionary algorithms Logistics cost Parallel cooperative approaches.


الملخص:

تكثر التحديات الوجستية في العديد من المجالات. لكن الحلول الجيدة ليست جد وفيرة كما أنها ذات فائدة تجارية، ونظرية. يعتبر مشكل توجيه السيارات من أكثر مشاكل التحسين الاندماجية صعوبة وتحديا حيث أنه يمثل مشاكل العالم الحقيقي التي تواجه في مجال توزيع السلع. يهدف هذا المشكل الى خدمة طلبات مجموعة من المواقع بأقل تكلفة ممكنة مع احترام جميع الخصائص المحددة. ويجب أن تتميز الوسائل المبتكرة لحل هذا النوع من المشاكل بالقدرة على التكيف مع هذه الخصائص. من أ جل هذا، يهدف هذا البحث الى ايجاد وسائل وتقنيات فعالة التي تنتج حلولا ذات نوعية جيدة لمشكل توجيه السيارات مع احترام الوقت اللازم لإصدارها.

من أ جل تطوير تقنيات استدلالية عامة، تقدم هذه الاطروحة بداية تقنيتين جديدتين، وهما: التقنية الجينية المهجنة والتقنية (-) القائمة على طريقة عشوائية من أجل معالجة مشكل توجيه السيارات ذات الكم الصغير والمتوسط. وثانيا، تقدم هذه الاطروحة تقنية تعاونية متوازية لحل الحالات ذات الكم الكبير من نفس المشكل، مع الاخذ بعين الاعتبار الوقت وتعقيد الخوارزميات المقترحة.

تم اختبار التقنيات المقترحة على مشاكل توجيه السيارات المعروفة، من مجموعات صغيرة متوسطة وكبيرة. كما تم رصد التعقيد الحسابي اضافة الى المجموعات البيانية وتحليل الاساليب والنتائج التجريبية كلها تم تقييدها.


الكلمات المفتاحية:
السيارة مشاكل التوجيه الخوارزمية التطورية طرق الكشف عن مجريات الامور النقل تكلفة النقل والإمداد.