1
2
| <p><span mce_style="background-color: #ffffff;" style="background-color: rgb(255, 255, 255);"><mce:script type="text/javascript" mce_src="http://latex.codecogs.com/latexit.js"></mce:script>
</span></p><p style="text-align: center;" mce_style="text-align: center;"><span mce_style="background-color: #ffffff;" style="background-color: rgb(255, 255, 255);"><span mce_style="font-size: medium;" style="font-size: medium;"><b><span mce_style="color: #000000;" style="color: rgb(0, 0, 0);">Stage de 3ème année</span></b></span></span></p><p style="text-align: center;" mce_style="text-align: center;"><span mce_style="background-color: #ffffff;" style="background-color: rgb(255, 255, 255);"><span mce_style="color: #ff0000;" style="color: rgb(255, 0, 0);"><span mce_style="font-size: medium;" style="font-size: medium;"><b>Problèmes de tournées de véhicules avec profits dépendants de la période de service.</b></span></span></span></p><p style="text-align: center;" mce_style="text-align: center;"> <span mce_style="background-color: #ffffff;" style="background-color: rgb(255, 255, 255);"><a href="http://ludovic.drugbert.free.fr/site-perso/mesdocs/RapportStage.2013.pdf" mce_href="mesdocs/RapportStage.2013.pdf" target="_blank">rapport-de-stage.2013</a> <a href="http://ludovic.drugbert.free.fr/site-perso/mesdocs/topDrugbertAfsarLabadie.pdf" mce_href="mesdocs/topDrugbertAfsarLabadie.pdf" target="_blank">Article-EA2013</a><br></span></p><p style="text-align: justify;" mce_style="text-align: justify;"><span mce_style="background-color: #ffffff;" style="background-color: rgb(255, 255, 255);"><br></span></p><p style="text-align: justify;" mce_style="text-align: justify;"><span mce_style="background-color: #ffffff;" style="background-color: rgb(255, 255, 255);"><span mce_style="font-size: small;" style="font-size: small;"> Ce stage explore le nouveau problème du <b>Team Orienteering Problem with Time Windows and Period Dependant Profi ts</b> (<i>TOPtwPDP</i>) qui lui-même est une extension du <b>Multi-period Orienteering Problem with Time Windows</b> (<i>MuPOPtw</i>) et du <b>Team Orienteering Problem with Time Windows</b> (<i>TOPtw</i>). Pour résoudre ce nouveau problème de tournées de véhicules, j'ai implémenté plusieurs méta-heuristiques, tel qu'un algorithme Mémétique, un <i><b>GRASP</b></i>, un <i><b>GRASPxELS</b></i> ou encore une <i><b>ILS </b></i>sur des instances modifi ées du <i><b>TOPtw</b></i>.</span></span></p><p style="text-align: justify;" mce_style="text-align: justify;"><span mce_style="background-color: #ffffff;" style="background-color: rgb(255, 255, 255);"><span mce_style="font-size: small;" style="font-size: small;"> Dans un premier temps, j'ai fait un état de l'art sur des problèmes connexes en regroupant les articles les plus pertinents. Ensuite, j'ai conçu de nouvelles instances de tests adaptées à mon problème et basées sur des instances connues du <i><b>TOPtw</b></i>. J'ai tenté de les résoudre grâce à un solveur de programmation linéaire. Les temps d'attentes n'étant pas raisonnables, je suis partie sur un algorithme mémétique constitué d'une procédure de découpage nommée Split et d'une recherche locale basée sur des mouvements fréquemment utilisés dans les problèmes de tournées de véhicules. J'ai aussi implémenté un <i><b>GRASP </b></i>(Greedy randomized adaptive search procedure), dans sa version la plus simple, un <i><b>GRASPxELS</b></i> (<i><b>GRASP </b></i>hybridé par une méthode <b><i>ELS </i></b>ou Evolutionary Local Search) et en n une <i><b>ILS </b></i>(Iterated Local Search), tous constitués de la même recherche locale. Les résultats sont encourageants. Nous utilisons, pour comparer les méta-heuristiques, un système de budget autorisant chacune d'entre elle à un nombre limité de recherche locale. On montre alors un léger avantage pour le Mémétique en terme de fonction objective.</span></span></p><p style="text-align: justify;" mce_style="text-align: justify;"><span mce_style="background-color: #ffffff;" style="background-color: rgb(255, 255, 255);"><span mce_style="font-size: small;" style="font-size: small;"><u><b>Mot-clés :</b></u> Multi Period Team Orienteering, Period Dependent Pro ts, Time Windows, Algorithme Mémétique, GRASP, GRASPxELS, ILS, Variable Neighborhood Descent.</span></span></p><p style="text-align: justify;" mce_style="text-align: justify;"><span mce_style="background-color: #ffffff;" style="background-color: rgb(255, 255, 255);"><br></span></p><p style="text-align: justify;" mce_style="text-align: justify;"><span mce_style="background-color: #ffffff;" style="background-color: rgb(255, 255, 255);"><span mce_style="font-size: small;" style="font-size: small;"><span mce_style="color: #000000;" style="color: rgb(0, 0, 0);"><b><span mce_style="font-size: medium;" style="font-size: medium;"><span mce_style="color: #000000;" style="color: rgb(0, 0, 0);">Team Orienteering Problem with Time Windows and Period Dependant Profi ts :</span></span><br></b></span></span></span></p><p style="text-align: justify;" mce_style="text-align: justify;"><span mce_style="background-color: #ffffff;" style="background-color: rgb(255, 255, 255);"><span mce_style="font-size: small;" style="font-size: small;"><span mce_style="color: #000000;" style="color: rgb(0, 0, 0);"> Le <i><b>TOPtwPDP </b></i>est une extension du <b><i>TOPtw </i></b>et du <b><i>MuPOPtw</i></b>. On considère ici que le pro t apporté par la visite d'un client dépend de la période de service. La figure ci-dessous montre un exemple d'une solution du <b><i>TOPtwPDP </i></b>sur une instance de 100 clients, une fl otte composée de 3 véhicules et un horizon de temps constituté de 4 périodes.</span></span></span></p><p style="text-align: center;" mce_style="text-align: center;"><span mce_style="background-color: #ffffff;" style="background-color: rgb(255, 255, 255);"><span mce_style="font-size: small;" style="font-size: small;"><span mce_style="color: #000000;" style="color: rgb(0, 0, 0);"><img src="mesdocs/exemple_toptwpdp.png" mce_src="mesdocs/exemple_toptwpdp.png" height="599" width="721"><br></span></span></span></p><p style="text-align: justify;" mce_style="text-align: justify;"><span mce_style="background-color: #ffffff;" style="background-color: rgb(255, 255, 255);"><span mce_style="font-size: small;" style="font-size: small;"><span mce_style="color: #000000;" style="color: rgb(0, 0, 0);"> Le but est de proposer des plans de transports tactiques optimisés en sélectionnant un portefeuille de clients, en acceptant chaque client retenu à une période et en construisant les tournées optimales de chaque période. Le <i><b>TOPtwPDP </b></i>peut-être vu comme étant p problèmes de type <b><i>TOPtw</i></b>, ou p est le nombre de période, une fois les clients acceptés aux périodes.</span></span></span></p><p style="text-align: justify;" mce_style="text-align: justify;"><span mce_style="background-color: #ffffff;" style="background-color: rgb(255, 255, 255);"><br></span></p><h2 style="text-align: center;" mce_style="text-align: center;"><span mce_style="background-color: #ffffff;" style="background-color: rgb(255, 255, 255);"><span mce_style="color: #000000;" style="color: rgb(0, 0, 0);"><span mce_style="font-size: medium;" style="font-size: medium;"><b>Modèle mathématique<br></b></span></span></span></h2><p style="text-align: justify;" mce_style="text-align: justify;"><span mce_style="background-color: #ffffff;" style="background-color: rgb(255, 255, 255);"><span mce_style="color: #000000;" style="color: rgb(0, 0, 0);"><b><span mce_style="font-size: small;" style="font-size: small;">1. Données</span></b></span><br></span></p><p style="text-align: justify;" mce_style="text-align: justify;"><span mce_style="background-color: #ffffff;" style="background-color: rgb(255, 255, 255);"><span mce_style="color: #000000;" style="color: rgb(0, 0, 0);"><span mce_style="font-size: small;" style="font-size: small;"><b>2. Programme linéaire en nombre entier</b></span></span></span></p><p style="text-align: justify;" mce_style="text-align: justify;"><span mce_style="background-color: #ffffff;" style="background-color: rgb(255, 255, 255);"><span mce_style="font-size: small;" style="font-size: small;"><span mce_style="color: #000000;" style="color: rgb(0, 0, 0);"><span mce_style="color: #000000;" style="color: rgb(0, 0, 0);"></span></span><span mce_style="color: #000000;" style="color: rgb(0, 0, 0);">Le programme linéaire du TOPtwPDP est donné ci-dessous :</span><b><span mce_style="color: #000000;" style="color: rgb(0, 0, 0);"> </span></b></span></span></p><p style="text-align: center;" mce_style="text-align: center;"><span mce_style="background-color: #ffffff;" style="background-color: rgb(255, 255, 255);"><img src="http://latex.codecogs.com/gif.latex?max \sum \limits_{n = 1}^m \sum \limits_{i\in{C}} \sum \limits_{t\in{\Psi}} p_{i}^{t}y_{i}^{t,n}" mce_src="http://latex.codecogs.com/gif.latex?max \sum \limits_{n = 1}^m \sum \limits_{i\in{C}} \sum \limits_{t\in{\Psi}} p_{i}^{t}y_{i}^{t,n}" border="0"></span></p><p style="text-align: center;" mce_style="text-align: center;"><span mce_style="background-color: #ffffff;" style="background-color: rgb(255, 255, 255);"><br></span></p><p style="text-align: justify;" mce_style="text-align: justify;"><span mce_style="background-color: #ffffff;" style="background-color: rgb(255, 255, 255);"><span mce_style="color: #000000;" style="color: rgb(0, 0, 0);">Sous contraintes :</span></span></p><p style="text-align: center;" mce_style="text-align: center;"><span mce_style="background-color: #ffffff;" style="background-color: rgb(255, 255, 255);"><span mce_style="color: #ffffff;" style="color: rgb(255, 255, 255);"><img src="http://latex.codecogs.com/gif.latex?\sum \limits_{n = 1}^m \sum \limits_{t\in{\Psi}} y_{i}^{t,n} \le 1 \ \ \ \ \forall i\in{C}" mce_src="http://latex.codecogs.com/gif.latex?\sum \limits_{n = 1}^m \sum \limits_{t\in{\Psi}} y_{i}^{t,n} \le 1 \ \ \ \ \forall i\in{C}" border="0"></span></span></p><p style="text-align: center;" mce_style="text-align: center;"><span mce_style="background-color: #ffffff;" style="background-color: rgb(255, 255, 255);"><span mce_style="color: #ffffff;" style="color: rgb(255, 255, 255);"><br></span></span></p><p style="text-align: center;" mce_style="text-align: center;"><span mce_style="background-color: #ffffff;" style="background-color: rgb(255, 255, 255);"><span mce_style="color: #ffffff;" style="color: rgb(255, 255, 255);"><img src="http://latex.codecogs.com/gif.latex?\sum \limits_{(i,j) \in E} x_{ij}^{t,n} = \sum \limits_{(j,i) \in E} x_{ji}^{t,n} = y_{i}^{t,n} \ \ \ \ \forall i\in{C},\ \ \ \ \forall t \in{\Psi}, \ \ \ \ \forall n = 1...m" mce_src="http://latex.codecogs.com/gif.latex?\sum \limits_{(i,j) \in E} x_{ij}^{t,n} = \sum \limits_{(j,i) \in E} x_{ji}^{t,n} = y_{i}^{t,n} \ \ \ \ \forall i\in{C},\ \ \ \ \forall t \in{\Psi}, \ \ \ \ \forall n = 1...m" border="0"></span></span></p><p style="text-align: center;" mce_style="text-align: center;"><span mce_style="background-color: #ffffff;" style="background-color: rgb(255, 255, 255);"><span mce_style="color: #ffffff;" style="color: rgb(255, 255, 255);"><br></span></span></p><p style="text-align: center;" mce_style="text-align: center;"><span mce_style="background-color: #ffffff;" style="background-color: rgb(255, 255, 255);"><span mce_style="color: #ffffff;" style="color: rgb(255, 255, 255);"><img src="http://latex.codecogs.com/gif.latex?\sum \limits_{(d_e,j) \in E} x_{d_ej}^{t,n} =\sum \limits_{(j,d_s) \in E} x_{jd_s}^{t,n} = 1 \ \ \ \ \forall t \in{\Psi}, \ \ \ \ \forall n = 1...m" mce_src="http://latex.codecogs.com/gif.latex?\sum \limits_{(d_e,j) \in E} x_{d_ej}^{t,n} =\sum \limits_{(j,d_s) \in E} x_{jd_s}^{t,n} = 1 \ \ \ \ \forall t \in{\Psi}, \ \ \ \ \forall n = 1...m" border="0"></span></span></p><p style="text-align: center;" mce_style="text-align: center;"><span mce_style="background-color: #ffffff;" style="background-color: rgb(255, 255, 255);"><span mce_style="color: #ffffff;" style="color: rgb(255, 255, 255);"><br></span></span></p><p style="text-align: center;" mce_style="text-align: center;"><span mce_style="background-color: #ffffff;" style="background-color: rgb(255, 255, 255);"><span mce_style="color: #ffffff;" style="color: rgb(255, 255, 255);"><img src="http://latex.codecogs.com/gif.latex?e_{i}y_{i}^{t,n} \le a_{i}^{t,n} \le l_{i}y_{i}^{t,n} \ \ \ \ \forall i \in V, \ \ \ \ \forall t \in{\Psi}, \ \ \ \ \forall n = 1...m" mce_src="http://latex.codecogs.com/gif.latex?e_{i}y_{i}^{t,n} \le a_{i}^{t,n} \le l_{i}y_{i}^{t,n} \ \ \ \ \forall i \in V, \ \ \ \ \forall t \in{\Psi}, \ \ \ \ \forall n = 1...m" border="0"></span></span></p><p style="text-align: center;" mce_style="text-align: center;"><span mce_style="background-color: #ffffff;" style="background-color: rgb(255, 255, 255);"><br></span></p><p style="text-align: center;" mce_style="text-align: center;"><span mce_style="background-color: #ffffff;" style="background-color: rgb(255, 255, 255);"><img src="http://latex.codecogs.com/gif.latex?a_{i}^{t,n}+ds_{ij}+M x_{ij}^{t,n} \le a_{j}^{t,n} + M \ \ \ \forall \left(i,j\right)\in{E}, \ \ \ \forall t \in{\Psi}, \ \ \ \forall n = 1...m" mce_src="http://latex.codecogs.com/gif.latex?a_{i}^{t,n}+ds_{ij}+M x_{ij}^{t,n} \le a_{j}^{t,n} + M \ \ \ \forall \left(i,j\right)\in{E}, \ \ \ \forall t \in{\Psi}, \ \ \ \forall n = 1...m" border="0"></span></p><p style="text-align: center;" mce_style="text-align: center;"><span mce_style="background-color: #ffffff;" style="background-color: rgb(255, 255, 255);"><br></span></p><p style="text-align: center;" mce_style="text-align: center;"><span mce_style="background-color: #ffffff;" style="background-color: rgb(255, 255, 255);"><img src="http://latex.codecogs.com/gif.latex?a_{d_{s}}^{t,n} - a_{d_{e}}^{t,n} \le \lambda \ \ \ \ \forall t \in{\Psi}, \ \ \ \ \forall n = 1...m" mce_src="http://latex.codecogs.com/gif.latex?a_{d_{s}}^{t,n} - a_{d_{e}}^{t,n} \le \lambda \ \ \ \ \forall t \in{\Psi}, \ \ \ \ \forall n = 1...m" border="0"></span></p><p style="text-align: center;" mce_style="text-align: center;"><span mce_style="background-color: #ffffff;" style="background-color: rgb(255, 255, 255);"><br></span></p><p style="text-align: center;" mce_style="text-align: center;"><span mce_style="background-color: #ffffff;" style="background-color: rgb(255, 255, 255);"><img src="http://latex.codecogs.com/gif.latex?x_{ij}^{t,n} \in \left\{0,1\right\} \ \ \ \ \forall \left(i,j\right)\in{E}, \ \ \ \ \forall t \in{\Psi}, \ \ \ \ \forall n = 1...m" mce_src="http://latex.codecogs.com/gif.latex?x_{ij}^{t,n} \in \left\{0,1\right\} \ \ \ \ \forall \left(i,j\right)\in{E}, \ \ \ \ \forall t \in{\Psi}, \ \ \ \ \forall n = 1...m" border="0"></span></p><p style="text-align: center;" mce_style="text-align: center;"><span mce_style="background-color: #ffffff;" style="background-color: rgb(255, 255, 255);"><br></span></p><p style="text-align: center;" mce_style="text-align: center;"><span mce_style="background-color: #ffffff;" style="background-color: rgb(255, 255, 255);"><img src="http://latex.codecogs.com/gif.latex?y_{i}^{t,n} \in \left\{0,1\right\} \ \ \ \ \forall i\in{C}, \ \ \ \ \forall t \in{\Psi}, \ \ \ \ \forall n = 1...m" mce_src="http://latex.codecogs.com/gif.latex?y_{i}^{t,n} \in \left\{0,1\right\} \ \ \ \ \forall i\in{C}, \ \ \ \ \forall t \in{\Psi}, \ \ \ \ \forall n = 1...m" border="0"></span></p><p style="text-align: center;" mce_style="text-align: center;"><span mce_style="background-color: #ffffff;" style="background-color: rgb(255, 255, 255);"><br></span></p><p style="text-align: center;" mce_style="text-align: center;"><span mce_style="background-color: #ffffff;" style="background-color: rgb(255, 255, 255);"><img src="http://latex.codecogs.com/gif.latex?a_{i}^{t,n} \in \mathbf{R}^{+} \ \ \ \ \forall i\in{V}, \ \ \ \ \forall t \in{\Psi}, \ \ \ \ \forall n = 1...m" mce_src="http://latex.codecogs.com/gif.latex?a_{i}^{t,n} \in \mathbf{R}^{+} \ \ \ \ \forall i\in{V}, \ \ \ \ \forall t \in{\Psi}, \ \ \ \ \forall n = 1...m" border="0"></span></p><p style="text-align: center;" mce_style="text-align: center;"><span mce_style="background-color: #ffffff;" style="background-color: rgb(255, 255, 255);"><br></span></p><pre></pre> |
