Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

N o d’ordre: 3 2 4 CENTRALE LILLE THÈSE présentée en vue d’obtenir le grade de

N o d’ordre: 3 2 4 CENTRALE LILLE THÈSE présentée en vue d’obtenir le grade de DOCTEUR en Spécialité : Automatique, Génie Informatique, Traitement du Signal et des Images par Yihan LIU Master of Science of Beihang University (BUAA) Doctorat délivré par Centrale Lille Titre de la thèse : Optimisation de Problème de Tournées de Véhicules de Service à Domicile Soutenue le 27 Juin 2017 devant le jury d’examen : M. Pierre BORNE École Centrale de Lille Président M. Khaled MELLOULI IHEC Carthage, Tunisie Rapporteur Mme. Shaoping WANG Beihang University (BUAA) Rapporteur M. Abdelkader EL KAMEL École Centrale de Lille Directeur de thèse M. Khaled MESGHOUNI École Centrale de Lille Examinateur M. Dumitru POPESCU Université Polytechnique de Bucarest Examinateur Mme. Zhuoyue SONG Beijing Institute of Technology (BIT) Examinateur Mme. Liming ZHANG University of Macau Examinateur Thèse préparée dans le Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL), UMR CNRS 9189 - École Centrale de Lille École Doctorale Sciences pour l’Ingénieur - 072 Serial No : 3 2 4 CENTRALE LILLE THESIS Presented to obtain the degree of Doctor of Philosophy in Topic : Automatic Control, Computer Science, Signal and Image Processing by Yihan LIU Master of Engineering of Beihang University (BUAA) Ph.D. awarded by Centrale Lille Title of the thesis : Optimization of Vehicle Routing Problem for Field Service Defended on June 27, 2017 in presence of the committee : Mr. Pierre BORNE École Centrale de Lille President Mr. Khaled MELLOULI IHEC Carthage, Tunisie Reviewer Mrs. Shaoping WANG Beihang University (BUAA) Reviewer Mr. Abdelkader EL KAMEL École Centrale de Lille Supervisor Mr. Khaled MESGHOUNI École Centrale de Lille Examiner Mr. Dumitru POPESCU Université Polytechnique de Bucarest Examiner Mrs. Zhuoyue SONG Beijing Institute of Technology (BIT) Examiner Mrs. Liming ZHANG University of Macau Examiner Thesis prepared within the Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL), UMR CNRS 9189 - École Centrale de Lille École Doctorale Sciences pour l’Ingénieur - 072 To my parents, to all my family, to my professors, and to my friends. Acknowledgements This research work has been realized in École Centrale de Lille, in “Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL)”, with the research group “Optimisation : Modèles et Applications (OPTIMA)”, from Febru- ary 2014 to June 2017. This work is ﬁnancially supported by China Scholarship Council (CSC). First and foremost, I oﬀer my sincerest gratitude to my supervisor, Prof. Abdelkader El Kamel, for his continuous support of my Ph.D. experience and research, for his patience, motivation, enthusiasm, and immense knowledge. His guidance helped me in all the time of research and writing of this dissertation. I could not have imagined having a better tutor and mentor for my Ph.D. study. He has provided his supervision, valuable guidance, continuous encouragement as well as given me extraordinary experiences through out the work. Besides my supervisor, I would like to thank Prof. Pierre BORNE for his kind acceptance to be the president of my Ph.D. Committee, as well as Prof. Khaled MELLOULI and Prof. Shaoping WANG, who have kindly accepted the invitation to be reviewers of my Ph.D. thesis, for their encouragement, insightful comments and hard questions. My gratitude to Prof. Khaled MESGHOUNI, Prof. Dumitru POPESCU, Prof Zhuoyue SONG and Prof. Liming ZHANG, for being the examiner of my thesis and for their kind acceptance to take part in the jury of the Ph.D. defense. I am also very grateful to the staﬀin École Centrale de Lille. Vanessa Fleury, Christine Yvoz, and Brigitte Foncez have helped me in the administrative work. Many thanks go also to Patrick Gallais, Gilles Marguerite, Jacques Lasue, for their kind help and hospitality. Special thanks go to Christine Vion, Martine Mouvaux for their support in my lodgment life at the dormitory “Léonard de Vinci”. i ACKNOWLEDGEMENTS I would like to take the opportunity to express my gratitude and to thank my fellow workmates in CRIStAL: Bing Liu„ Qi Sun, Jian Zhang, Ben Li for the stimulating discussions for the hard teamwork. Also I wish to thank my friends and colleagues: Daji Tian, Chen Xia, Hongchang Zhang, Yu Du, Lijie Bai, Qi Guo, Lijuan Zhang, etc., for all the fun we have had in the last three years. All of them have given me support and encouragement in my thesis work. My Ph.D. program was supported by the cooperation between China and Scholarship Council (CSC) and Ecoles-Centrales Intergroup. So I would like to thank all of the people who have built this relationship and contributed to select candidates for interesting research projects. I am extremely grateful to CSC who ﬁnanced me. So as to the rest of my family for their love and support. Their encouragement and understanding during the course of my dissertation make me pursue the advanced academic degree. Villeneuve d’Ascq, France LIU 2017 ii Abstract The logistics performance of the enterprises and the optimization of transporta- tion have become a great issue in recent years. Field force planning and optimiza- tion is a new challenge for the service sector especially for utility companies in the energy, telecommunications and water distribution areas. It generates new varia- tions of combinatorial optimization problems in the ﬁelds of manpower scheduling and vehicle routing. The challenges are many: to increase productivity and re- duce costs, by increasing the number of visited clients, while reducing the time and cost of transportation and to achieve an eﬃcient internal organization and appropriate human resources planning. In the literature, most of the work deals with problems involving deliveries of goods. In this thesis, we focus on the service tours, which constitute a less studied problem. We address the problem of the planning and routing of technician visits to customers in the ﬁeld, for maintenance or service logistics activities undertaken by utilities. The plan must be designed over a multi-period horizon. This dissertation focuses on the optimization of ﬁeld service routing problem with meta-heuristics. The addressed problem is abstracted from the realistic problem. This problem can be assimilated to a multi-depot and multi-period routing problem with time window. Various constraints were taken into consider to simulate the real problem. First, we consider the local search heuristics for solving the problem. Initial feasible solutions are obtained by a constructive heuristic. Several heuristics of local search are adapted to improve the solutions which permit us to obtain a fea- sible solution in a very short computing time. Second, we consider using genetic algorithm to ﬁnd the near-optimum solution. The genetic algorithm is applied with new representation of chromosome and new genetic operators to adapt the force constraints of the real-world problem. Third, we consider a genetic algo- iii ABSTRACT rithm with diversity control to deal with large scale problems. Infeasible solutions are taken account in the population and the diversity contribution is part of the evaluation to avoid the premature of search. Experiments are done to a series of instances which come from the actual production activity. Results showed that these methods’ performance meets the demand of real world situation. iv Contents Acknowledgements i Abstract iii Table of Contents v List of Figures viii List of Tables xi List of Algorithms xii Abbreviations xv 1 Introduction 1 1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Vehicle Routing Problem . . . . . . . . . . . . . . . . . . . . . . . 4 1.3 Presentation of Problem Studied . . . . . . . . . . . . . . . . . . . 8 1.4 Contributions of the Dissertation . . . . . . . . . . . . . . . . . . 9 1.5 Organization of the Dissertation . . . . . . . . . . . . . . . . . . . 10 2 State of the Art 13 2.1 Classiﬁcation of Vehicle Routing Problem . . . . . . . . . . . . . . 14 2.1.1 Constituent Elements of Vehicle Routing Problem . . . . . 14 2.1.2 VRP Extended Criteria . . . . . . . . . . . . . . . . . . . 16 2.1.3 Vehicle Routing Problem Extensions . . . . . . . . . . . . 19 2.2 Solution Methodologies . . . . . . . . . . . . . . . . . . . . . . . . 25 2.2.1 Exact Algorithms . . . . . . . . . . . . . . . . . . . . . . . 25 2.2.2 Heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 v CONTENTS 2.2.3 Meta-heuristics uploads/Science et Technologie/ liu-yihan-dle.pdf