Problèmes de tournées de véhicules et application industrielle pour PDF

26 mars 2014 for the Vehicle Routing Problem with Time Windows. ... Le VRP implique la planification de routes de livraison `a moindre coût afin.

Problèmes de tournées de véhicules et application industrielle pour

Problem with Time Windows. [6] R-N. Guibadj S. Afifi and A. Moukrim. New lower bounds and exact algorithm for the Vehicle Routing Problem with Time Windows

A dynamic programming operator for metaheuristics to solve vehicle

19 juin 2017 2.4 Classical Heuristics in Vehicle Routing . ... to minimise some objective such as the total distance travelled. The objective function.

Towards a smart prediction and optimization model in the context of

22 sept. 2021 inventory management and transportation routing. Physical Internet (PI) is ... total distribution costs of the feasible routes in each area.

T H E S E

3 sept. 2007 1.6 ´Evolution des victimes de la route et objectifs `a 2010 de l'Europe des 15 ... culation continue d'augmenter même si le nombre total de ...

Proceedings MOSIM 2018 - 12e Conference Internationale de

22 janv. 2019 2 – A continuous time inventory routing problem with energy minimization by ... that aims to minimize the total cost and the tardiness of.

Conception et réalisation dun système de gestion de véhicules

26 févr. 2013 le nombre total de véhicules disponibles pour servir la route ... de voitures en circulation au kilomètre la minimisation du taux ...

Création et utilisation datlas anatomiques numériques pour la

total de transport soit minimisé. Dans un LCP le véhicule ne peut transporter qu'une seule demande à la fois (full truckload) ce qui oblige le point de

ORBIS: The Stanford Geospatial Network Model of the Roman World

2 mai 2012 For each route the model generates two discrete outcomes for time and four for expense in any given month. Figure 1 - Sea routes in July with ...

Optimisation combinée des coûts de transport et de stockage dans

7 mai 2012 order to minimize logistics costs incurred in a logistics network multi-product multi-level ... Optimisation du coût logistique total .

Par Rym Nesrine GUIBADJ

Thèse présentée

Problèmes de tournées de véhicules et application

écologique

Soutenue le 16 avril 2013

D2074 par Rym Nesrine GUIBADJ

Problèmes de tournées de véhicules et

application industrielle pour la réduction de l"empreinte écologiqueThèse présentée pour l"obtention du grade de Docteur de l"UTCSoutenue le : 16 avril 2013 Spécialité : Technologies de l"Information et des Systèmes

Problèmes de tournées de véhicules

et application industrielle pour la réduction de l"empreinte écologique Thèse soutenue le 16 avril 2013 devant le jury composé de : Gilles GONCALVES Professeur des Universités (ARTOIS) Rapporteur Nacima LABADIE Maître de Conférences, HDR (UTT) Rapporteur Jacques CARLIER Professeur des Universités (UTC) Examinateur Philippe BOTTE Chef de projet (VEOLIATRASNDEV) Examinateur Aziz MOUKRIM Professeur des Universités (UTC) Directeur iii iv

Remerciements

Je souhaite adresser mes plus sinceres remerciements aux personnes qui ont cru en moi et qui m'ont permis d'arriver au bout de cette these. En premier lieu, je tiens a exprimer mes plus vifs remerciements a Aziz Moukrim qui fut pour moi un directeur de these attentif et disponible. Sa competence, sa rigueur scientique et sa clairvoyance m'ont beaucoup appris. Ils ont ete et resteront des moteurs de mon travail de chercheur. Je voudrais egalement remercier M. Phillipe Botte de m'avoir donne l'opportunite de travailler sur un projet de recherche et de developpement consequent et ambitieux. Je remercie cordialement M. Gilles Goncalves et Mme. Nacima Labadie d'avoir accepte d'^etre rapporteurs de cette these ainsi que M. Jacques Carlier d'avoir fait l'honneur d'examiner mon travail. J'adresse mes plus profondes reconnaissances a tous les membres de l'equipe MERCUR et l'equipe HEUDIASYC pour tous les echanges techniques, scientiques et pour leur sympathie et leur accueil chaleureux pendant ces trois ans de these. Enn, je tiens a remercier mes amis et mes proches en particulier mon conjoint pour son soutien sans faille et ses encouragements. Un grand merci du fond du coeur a ma mere qui m'a toujours soutenue inconditionnellement dans mon parcours universitaire, comme dans la vie. v

Publications

Revue internationale

[1] Duc-Cuong Dang,Rym Nesrine Guibadjand Aziz Moukrim. An eective PSO-inspired algorithm for the team orienteering problem. European Journal of

Operational Research, accepted, 2013.

Conferences internationales avec comite de lecture [2] D-C. Dang,R-N. Guibadjand A. Moukrim. A PSO-based memetic algorithm for the team orienteering problem. EvoApplications 2011 (Turin, Italy). Lecture Notes In Computer Science, 2011, vol. 6625, p. 471-480.

Conferences nationales

[3]R-N. Guibadj, D-C. Dang et A. Moukrim. Optimisation par essaim particulaire pour le probleme de m-tournees selectives. ROADEF 2011 (Saint-Etienne, France). [4]R-N. Guibadjet A. Moukrim. Un algorithme memetique pour resoudre le probleme de m-tournees selectives avec fen^etres de temps. ROADEF 2013 (Troyes,

France).

En preparation

[5]R-N. Guibadjand A. Moukrim. Memetic algorithm for the Team Orienteering

Problem with Time Windows.

[6]R-N. Guibadj, S. A and A. Moukrim. New lower bounds and exact algorithm for the Vehicle Routing Problem with Time Windows. vii

Table des matieres

Remerciements v

Publications vii

Table des matieres ix

Liste des algorithmes xiii

Liste des tableaux xv

Liste des gures xvii

Introduction 1

1 Contexte et expression industrielle 5

1.1 Resume . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2 Contexte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.3 Problematique de la mobilite . . . . . . . . . . . . . . . . . . . . . . .

1.3.1 Transport des personnes . . . . . . . . . . . . . . . . . . . . .

1.3.2 Transport des marchandises . . . . . . . . . . . . . . . . . . .

1.3.3 Positionnement du cas industriel . . . . . . . . . . . . . . . .

1 0

1.4 Problematique de l'habitat . . . . . . . . . . . . . . . . . . . . . . . .

1.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2 Domaine de l'etude 13

2.1 Problemes d'optimisation combinatoire . . . . . . . . . . . . . . . . .

2.2 Theorie de la complexite . . . . . . . . . . . . . . . . . . . . . . . . .

2.3 Methodes de resolution . . . . . . . . . . . . . . . . . . . . . . . . . .

2.3.1 Methodes exactes . . . . . . . . . . . . . . . . . . . . . . . . .

14 ix

2.3.2 Methodes approchees . . . . . . . . . . . . . . . . . . . . . . .16

2.4 Problemes de tournees de vehicules . . . . . . . . . . . . . . . . . . .

2.4.1 Presentation generale des problemes de Tournees de Vehicules

2.4.2 Diverses variantes des problemes de tournees . . . . . . . . . .

2.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 Optimisation par Essaim Particulaire 25

3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.2 Formulation of the problem . . . . . . . . . . . . . . . . . . . . . . .

3.3 A PSO-inspired algorithm . . . . . . . . . . . . . . . . . . . . . . . .

3.3.1 Basic algorithm . . . . . . . . . . . . . . . . . . . . . . . . . .

3.3.2 Position representation and evaluation . . . . . . . . . . . . .

3.3.3 Randomized heuristics . . . . . . . . . . . . . . . . . . . . . .

3 2

3.3.4 Improvement of positions through local search . . . . . . . . .

3.3.5 Genetic crossover operator to update position . . . . . . . . .

3.3.6 Swarm local best update . . . . . . . . . . . . . . . . . . . . .

3.4 Numerical results on the standard benchmark . . . . . . . . . . . . .

3.4.1 Protocol and performance metrics . . . . . . . . . . . . . . . .

3.4.2 Parameter setting . . . . . . . . . . . . . . . . . . . . . . . . .

3.4.3 Comparison with the literature . . . . . . . . . . . . . . . . .

3.5 A set of larger instances for the team orienteering problem . . . . . .

3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4 Algorithme memetique pour le TOPTW 51

4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.2 Literature review . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.3 Formulation of the problem . . . . . . . . . . . . . . . . . . . . . . .

4.4 Memetic algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.4.1 Chromosome and evaluation . . . . . . . . . . . . . . . . . . .

4.4.2 Population . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.4.3 Selection and crossover . . . . . . . . . . . . . . . . . . . . . .

4.4.4 Local search engine . . . . . . . . . . . . . . . . . . . . . . . .

4.4.5 Population update . . . . . . . . . . . . . . . . . . . . . . . .

4.4.6 Basic algorithm . . . . . . . . . . . . . . . . . . . . . . . . . .

60
x

4.5 Numerical results . . . . . . . . . . . . . . . . . . . . . . . . . . . . .61

4.5.1 Parameter setting . . . . . . . . . . . . . . . . . . . . . . . . .

4.5.2 Performance comparison . . . . . . . . . . . . . . . . . . . . .

4.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5 Nouvelles bornes inferieures pour le VRPTW 75

5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.2 Literature review . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.3 Problem formulation . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.4 Lower bounding techniques . . . . . . . . . . . . . . . . . . . . . . . .

5.4.1 Incompatibilities between customers . . . . . . . . . . . . . . .

5.4.2 Vehicle capacity constraints . . . . . . . . . . . . . . . . . . .

5.4.3 New lower bounds inspired from Energetic Reasoning . . . . .

7 9

5.4.4 Using bin-packing lower bounds into Energetic Reasoning . . .

5.5 Numerical results . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Conclusion 91

A Portail du Moteur d'Adaptation 95

A.1 Cadre general . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
A.2 Description du portail . . . . . . . . . . . . . . . . . . . . . . . . . . 97

Bibliographie 103

Liste des algorithmes

3.1 Basic algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.1 IDCH algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.2 Basic algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.1 Energetic Reasoning : satisability test and time bound adjustment . .

82
xiii

Liste des tableaux

3.1 Performance comparison based on RPE average for each data set of the

relevant instances. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

3.2 Robustness comparison based on ARPE average for each data set of

the relevant instances. . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

3.3 Average CPU time for each data set of the standard benchmark. . . . .

3.4 Maximal CPU time for each data set of the standard benchmark. . . .

3.5 Stability comparison based on the number of instances having zero APRE.

4 1

3.6 In

uence of prot generations on the stability of PSOiA . . . . . . . . . 43

3.7 Results for set 4 of the benchmark. . . . . . . . . . . . . . . . . . . . .

3.8 Results for set 5 of the benchmark. . . . . . . . . . . . . . . . . . . . .

3.9 Results for set 6 of the benchmark. . . . . . . . . . . . . . . . . . . . .

3.10 Results for set 7 of the benchmark. . . . . . . . . . . . . . . . . . . . .

3.11 Results of the new instances. . . . . . . . . . . . . . . . . . . . . . . . .

4.1 Parameter values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.2 Performance on a small subset of instances with various parameters

settings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

4.3 Performance comparison based on RPE average for each data set of the

standard benchmark. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

4.4 Strict improvements . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.5 Results for Solomon's instances with m = 1. . . . . . . . . . . . . . . .

4.6 Results for Solomon's instances with m = 2. . . . . . . . . . . . . . . .

4.7 Results for Solomon's instances with m = 3. . . . . . . . . . . . . . . .

4.8 Results for Solomon's instances with m = 4. . . . . . . . . . . . . . . .

4.9 Results for Cordeau's instances with m = 1. . . . . . . . . . . . . . . .

4.10 Results for Cordeau's instances with m = 2. . . . . . . . . . . . . . . .

4.11 Results for Cordeau's instances with m = 3. . . . . . . . . . . . . . . .

4.12 Results for Cordeau's instances with m = 4. . . . . . . . . . . . . . . .

4.13 Results for new Solomon's instances. . . . . . . . . . . . . . . . . . . .

73
xv

4.14 Results for new Cordeau's instances. . . . . . . . . . . . . . . . . . . .73

5.1 Lower bound results and CPU times . . . . . . . . . . . . . . . . . . .

89
xvi

Liste des gures

3.1 The new evaluation process for the same split problem described in [25]

with 8 customers,m= 2 andL= 70. . . . . . . . . . . . . . . . . . . .3 0

3.2 An example of position update for an arbitrary instance of ten

customers. Black dots represent random generated locationsrand shaded boxes represent marked customers fromMduring Phase 1. . . .34

3.3 Performance of PSOiA in terms of the stopping conditionk. . . . . . .37

3.4 Performance of PSOiA in terms of the probabilityphof a particle to

be moved out of its current position. . . . . . . . . . . . . . . . . . . . 38

4.1 An example of splitting problem. . . . . . . . . . . . . . . . . . . . . .

4.2 Illustration of the LOX crossover operator. . . . . . . . . . . . . . . . .

59
quotesdbs_dbs17.pdfusesText_23

[PDF] Heurs et malheurs de l`hôtel de la Croix d`Or - France

[PDF] HEURS ET MALHEURS DU RITE ECOSSAIS

[PDF] HEURTEY PETROCHEM FAIR VALUE: 15,2€

[PDF] Heurtey Petrochem Services Brochure

[PDF] Heurts et malheurs du tacot de CUY - Anciens Et Réunions

[PDF] Heut heirat die Liebe meines Lebens

[PDF] Heute - Wolfschlugen

[PDF] Heute auf Seite 3: Guernka, Guernica Elf Aquitaine

[PDF] Heute kennen lernen, was morgen die Welt bewegt Le monde de - Réseau Social

[PDF] Heute mit: Thomas „Iker Casillas“ Ostermeier

[PDF] Heute Online

[PDF] HEUTTE, J. (2011) La part du collectif dans la motivation et son

[PDF] Heva Advanced Coloured Cleaning Products - France

[PDF] Hevi-Sand® est produit à partir de chromite de fonderie à haute - Anciens Et Réunions

[PDF] HewIett-Packard Iimited warranty statement

[PDF] Problèmes de tournées de véhicules et application industrielle pour