Séparation des Contraintes de Coupe-Capacité Arrondies du CVRP : Complexité et Applications aux Contraintes de Partition Routées
Identifieur interne : 000286 ( Main/Curation ); précédent : 000285; suivant : 000287Séparation des Contraintes de Coupe-Capacité Arrondies du CVRP : Complexité et Applications aux Contraintes de Partition Routées
Auteurs : Ibrahima Diarrassouba [France]Source :
Descripteurs français
- mix :
Abstract
Dans ce papier, nous nous intéressons au problème de séparation des contraintes dites de Coupe-Capacité Arrondies qui sont valides pour le polytope du CVRP (Capacitated Vehicle Routing Problem). Ces contraintes, ainsi que leur problème de séparation, présentent un intérêt particulier dans la résolution du CVRP, surtout dans le cadre d'algorithmes de Coupes et Branchements. A notre connaissance, la complexité du problème de séparation associé à ces contraintes n'est pas connu dans la litérature, et plusieurs auteurs ont proposé des algorithmes heuristiques pour les séparer. Dans ce travail, nous étudions une généralisation des Contraintes de Coupe-Capacité Arrondies et montrons que ces contraintes peuvent être séparées en temps polynomial. Nous donnons aussi un algorithme de séparation en (n-1)E(n,m+n) où E(n,m+n) peut être borné par O(n4) (ici n et m désigne respectivement le nombre de sommets et d'arêtes du graphe support du CVRP). Comme conséquence, nous répondons à la question de la complexité du problème de séparation des Contraintes de Coupe-Capacité Arrondies.
Puis, nous nous intéressons aux applications du résultat précédent au problème de séparation des contraintes dites de Partitions Routées. Ces contraintes sont valides pour le polytope du problème de Conception de Réseau Fiables avec Chemin de Longueur Bornée. Nous montrons que, dans un cas particulier où elles définissent des facettes, les Contraintes de Partitions Routées peuvent être séparées en temps polynomial. Enfin, nous discutons d'autres applications des Contraintes de Coupe-Capacité Arrondies.
Url:
Links toward previous steps (curation, corpus...)
- to stream Hal, to step Corpus: Pour aller vers cette notice dans l'étape Curation :000758
- to stream Hal, to step Curation: Pour aller vers cette notice dans l'étape Curation :000758
- to stream Hal, to step Checkpoint: Pour aller vers cette notice dans l'étape Curation :000162
- to stream Main, to step Merge: Pour aller vers cette notice dans l'étape Curation :000287
Links to Exploration step
Hal:hal-00946288Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="fr">Séparation des Contraintes de Coupe-Capacité Arrondies du CVRP : Complexité et Applications aux Contraintes de Partition Routées</title>
<author><name sortKey="Diarrassouba, Ibrahima" sort="Diarrassouba, Ibrahima" uniqKey="Diarrassouba I" first="Ibrahima" last="Diarrassouba">Ibrahima Diarrassouba</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-244433" status="INCOMING"><orgName>Laboratoire de Mathématiques Appliquées du Havre</orgName>
<orgName type="acronym">LMAH</orgName>
<desc><address><addrLine>25 Rue Philippe Lebon, 76063, Le Havre, France</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://lmah.univ-lehavre.fr/</ref>
</desc>
<listRelation><relation active="#struct-300317" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-300317" type="direct"><org type="institution" xml:id="struct-300317" status="VALID"><orgName>Université du Havre</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName><settlement type="city">Le Havre</settlement>
<region type="region" nuts="2">Région Normandie</region>
<region type="old region" nuts="2">Haute-Normandie</region>
</placeName>
<orgName type="university">Université du Havre</orgName>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:hal-00946288</idno>
<idno type="halId">hal-00946288</idno>
<idno type="halUri">https://hal.archives-ouvertes.fr/hal-00946288</idno>
<idno type="url">https://hal.archives-ouvertes.fr/hal-00946288</idno>
<date when="2014-02-26">2014-02-26</date>
<idno type="wicri:Area/Hal/Corpus">000758</idno>
<idno type="wicri:Area/Hal/Curation">000758</idno>
<idno type="wicri:Area/Hal/Checkpoint">000162</idno>
<idno type="wicri:Area/Main/Merge">000287</idno>
<idno type="wicri:Area/Main/Curation">000286</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="fr">Séparation des Contraintes de Coupe-Capacité Arrondies du CVRP : Complexité et Applications aux Contraintes de Partition Routées</title>
<author><name sortKey="Diarrassouba, Ibrahima" sort="Diarrassouba, Ibrahima" uniqKey="Diarrassouba I" first="Ibrahima" last="Diarrassouba">Ibrahima Diarrassouba</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-244433" status="INCOMING"><orgName>Laboratoire de Mathématiques Appliquées du Havre</orgName>
<orgName type="acronym">LMAH</orgName>
<desc><address><addrLine>25 Rue Philippe Lebon, 76063, Le Havre, France</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://lmah.univ-lehavre.fr/</ref>
</desc>
<listRelation><relation active="#struct-300317" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-300317" type="direct"><org type="institution" xml:id="struct-300317" status="VALID"><orgName>Université du Havre</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName><settlement type="city">Le Havre</settlement>
<region type="region" nuts="2">Région Normandie</region>
<region type="old region" nuts="2">Haute-Normandie</region>
</placeName>
<orgName type="university">Université du Havre</orgName>
</affiliation>
</author>
</analytic>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass><keywords scheme="mix" xml:lang="fr"><term>Algorithme de Séparation</term>
<term>Capacitated Vehicle Routing Problem</term>
<term>Capacité</term>
<term>Contraintes de Coupe</term>
<term>Contraintes de Partition Rootée</term>
<term>Fonctions Sous</term>
<term>modulaires</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="fr">Dans ce papier, nous nous intéressons au problème de séparation des contraintes dites de Coupe-Capacité Arrondies qui sont valides pour le polytope du CVRP (Capacitated Vehicle Routing Problem). Ces contraintes, ainsi que leur problème de séparation, présentent un intérêt particulier dans la résolution du CVRP, surtout dans le cadre d'algorithmes de Coupes et Branchements. A notre connaissance, la complexité du problème de séparation associé à ces contraintes n'est pas connu dans la litérature, et plusieurs auteurs ont proposé des algorithmes heuristiques pour les séparer. Dans ce travail, nous étudions une généralisation des Contraintes de Coupe-Capacité Arrondies et montrons que ces contraintes peuvent être séparées en temps polynomial. Nous donnons aussi un algorithme de séparation en (n-1)E(n,m+n) où E(n,m+n) peut être borné par O(n4) (ici n et m désigne respectivement le nombre de sommets et d'arêtes du graphe support du CVRP). Comme conséquence, nous répondons à la question de la complexité du problème de séparation des Contraintes de Coupe-Capacité Arrondies.
Puis, nous nous intéressons aux applications du résultat précédent au problème de séparation des contraintes dites de Partitions Routées. Ces contraintes sont valides pour le polytope du problème de Conception de Réseau Fiables avec Chemin de Longueur Bornée. Nous montrons que, dans un cas particulier où elles définissent des facettes, les Contraintes de Partitions Routées peuvent être séparées en temps polynomial. Enfin, nous discutons d'autres applications des Contraintes de Coupe-Capacité Arrondies.
</div>
</front>
</TEI>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/France/explor/LeHavreV1/Data/Main/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000286 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Curation/biblio.hfd -nk 000286 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Wicri/France |area= LeHavreV1 |flux= Main |étape= Curation |type= RBID |clé= Hal:hal-00946288 |texte= Séparation des Contraintes de Coupe-Capacité Arrondies du CVRP : Complexité et Applications aux Contraintes de Partition Routées }}
![]() | This area was generated with Dilib version V0.6.25. | ![]() |