Heuristic algorithm to solve vehicle routing problem with drones / Assala Litim

Public ISBD Titre : Heuristic algorithm to solve vehicle routing problem with drones Type de document : document électronique Auteurs : Assala Litim ; Ras Elaine Hachem, Auteur ; Ikram Bouras, Directeur de thèse Editeur : Setif:UFA Année de publication : 2025 Importance : 1 vol (49 f .) Format : 29 cm Langues : Anglais (eng) Catégories : Thèses & Mémoires:Informatique Mots-clés : Vehicle Routing Problem Drones Heuristics Integer programming Index. décimale : 004 Informatique Résumé : This thesis focuses on the Vehicle Routing Problem with Drones (VRPD), which is primarily a special case of the classic Vehicle Routing Problem (VRP). The objective is to coordinate the use of trucks and drones to carry out deliveries in order to optimize costs and delivery times. A precise mathematical model is proposed, taking into account transportation constraints, drone endurance, and the demand that must be satisfied within specified time windows. For the solution approach, we presented a two-phase heuristic algorithm. In the first phase, we solve the problem using only trucks in delivery. To find the routes of each truck, we used two methods : the first one is solving a capacitated vehicle routing problem exactly by a branch-and-bound algorithm, and the other one is a route-first cluster-second heuristic. The second phase involved the insertion of drones into each truck route by an heuristic algorithm Note de contenu : Sommaire Abstract ii Résumé iii List of tables vii List of figures vii List of Abbreviations ix Introduction 1 1 General Vehicle Routing problem 3 1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Classical VRP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2.2 Mathematical Formulation of VRP . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3 Applications in logistics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.4 Types of VRP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.5 Optimization approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.5.1 Exact Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.5.2 Approximate Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2 VRP with drones 14 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.2 Problem definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.3 Path-Based Reformulation of the VRPD . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.4 Mathematical Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.5 Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.6 Real-world use cases and application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.7 optimization Approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.7.1 Exact methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.7.2 Heuristics methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.8 Challenges and future directions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.9 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3 Two-Steps heuristic to solve VRPD 24 3.1 Problem definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.2 Mathematical Formulation of the VRP-D . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.3 Resolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.3.1 Exact Method : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.3.2 Heuristic method : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.3.3 Example of Resolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 4 Implementation details and Results 36 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 4.2 Tools and Development Environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 4.3 Implementation details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 4.3.1 Data Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 4.3.2 Implementation of Solving VRPD Using Exact Method . . . . . . . . . . . . . . . 42 4.3.3 Comparative Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 4.3.4 Computed Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 4.3.5 Evaluation Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 4.3.6 Key Observations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 4.4 Global Comparison of Exact and Heuristic Methods for solving Vehicle Routing problems (VRPD) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 4.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 Conclusion 45 References 49 Côte titre : MAI/1048 Heuristic algorithm to solve vehicle routing problem with drones [document électronique] / Assala Litim ; Ras Elaine Hachem, Auteur ; Ikram Bouras, Directeur de thèse . - [S.l.] : Setif:UFA, 2025 . - 1 vol (49 f .) ; 29 cm. Langues : Anglais (eng) Catégories : Thèses & Mémoires:Informatique Mots-clés : Vehicle Routing Problem Drones Heuristics Integer programming Index. décimale : 004 Informatique Résumé : This thesis focuses on the Vehicle Routing Problem with Drones (VRPD), which is primarily a special case of the classic Vehicle Routing Problem (VRP). The objective is to coordinate the use of trucks and drones to carry out deliveries in order to optimize costs and delivery times. A precise mathematical model is proposed, taking into account transportation constraints, drone endurance, and the demand that must be satisfied within specified time windows. For the solution approach, we presented a two-phase heuristic algorithm. In the first phase, we solve the problem using only trucks in delivery. To find the routes of each truck, we used two methods : the first one is solving a capacitated vehicle routing problem exactly by a branch-and-bound algorithm, and the other one is a route-first cluster-second heuristic. The second phase involved the insertion of drones into each truck route by an heuristic algorithm Note de contenu : Sommaire Abstract ii Résumé iii List of tables vii List of figures vii List of Abbreviations ix Introduction 1 1 General Vehicle Routing problem 3 1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Classical VRP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2.2 Mathematical Formulation of VRP . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3 Applications in logistics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.4 Types of VRP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.5 Optimization approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.5.1 Exact Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.5.2 Approximate Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2 VRP with drones 14 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.2 Problem definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.3 Path-Based Reformulation of the VRPD . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.4 Mathematical Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.5 Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.6 Real-world use cases and application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.7 optimization Approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.7.1 Exact methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.7.2 Heuristics methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.8 Challenges and future directions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.9 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3 Two-Steps heuristic to solve VRPD 24 3.1 Problem definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.2 Mathematical Formulation of the VRP-D . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.3 Resolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.3.1 Exact Method : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.3.2 Heuristic method : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.3.3 Example of Resolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 4 Implementation details and Results 36 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 4.2 Tools and Development Environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 4.3 Implementation details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 4.3.1 Data Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 4.3.2 Implementation of Solving VRPD Using Exact Method . . . . . . . . . . . . . . . 42 4.3.3 Comparative Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 4.3.4 Computed Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 4.3.5 Evaluation Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 4.3.6 Key Observations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 4.4 Global Comparison of Exact and Heuristic Methods for solving Vehicle Routing problems (VRPD) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 4.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 Conclusion 45 References 49 Côte titre : MAI/1048

Exemplaires (1)

Code-barres	Cote	Support	Localisation	Section	Disponibilité
MAI/1048	MAI/1048	Mémoire	Bibliothèque des sciences	Anglais	Disponible Disponible

---

1 (1 - 1 / 1)