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 Profits</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 enn 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 Prots, 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 Profits :</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 prot 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 flotte 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> |
Partager