303 research outputs found
Cyclic Orders
No full textA family F of triplets of a set X is a cyclic order if the following axioms are satisfied: (a, b, c) ∈ F ⇒ (b, c, a) and (c, a, b) ∈ F(cyclicity);(a, b, c) ∈ F ⇒ (b, a, c) ∉ F(antisymmetry);(a, b, c) and (c, d, a) ∈ F ⇒ (b, c, d) and (d, a, b) ∈ F(transitivity).Such a concept aims to formalize some problems related to points or intervals drawn on a circle or on the plane, or with geometric representations of finite groups ((a, b, c) ∈ F is to be read as ‘b is located between a and c’). We move into the context of the so defined ternary relation some classical questions arising in the theory of partially ordered subsets, and deal, for instance, with extendability problem and with the problem of the minimal partition of a cyclic order into complete cyclic suborders. We also present several applications to such questions as the characterization of cyclic graphs or circular-arc graphs
Une extension du problème du point fixe pour des graphes simples
No full textRésuméNous disons qu'un graphe possède la propriété du k-point fixe (k est un entier) si pour tout homomorphisme f d'un produit Gk dans G, il existe un sommet x de Gk dont l'image f(x) est adjacente ou égale à une de ses coordonnées.L'introduction de ce concept se justifie par le lien qui le connecte au problème du jeu de poursuite à k poursuivants: plus spécifiquement, il est indispensable qu'un graphe G possède cette propriété du k-point fixe pour que k poursuivants puissent attraper un joueur poursuivi sur G.Nous étudions ici quelques applications de cette propriété, et prouvons que tout graphe planaire posséde la propriété du 2-point fixe.AbstractWe say that a graph G satisfies the k-fixed point property (k is an integer) if, for every homomorphism f from a product Gk into G, there exists a vertex x in Gk whose image through f is adjacent or identical to one of its coordinates.The justification of this concept comes from its relationship with the classical pursuit game with k pursuers and 1 evader: namely, we check here that if a graph G=(X,E) does not satisfy this property, then a strategy exists which allows the evader to escape the k pursuers in this pursuit game played on G.We study some applications of this concept and prove that any planar graph satisfies the 2-fixed point property
An extended approach for manufacturing strategy process base on organization performance through Fuzzy QFD
No full textOn the problem of minimizing the cost with optical devices in Wavelength Division Multiplexing optical networks: complexity analysis, mathematical formulation and improved heuristics
No full text
A new robust possibilistic programming model for reliable supply chain network design: A case study of lead-acid battery supply chain
No full textModeling and solving difficult DARP and Lot-Sizing problems
No full textLe principal objet de cet thèse réside dans la modélisation et l’optimisation de services de transport à la demande aussi différents soient-ils (ou seront-ils). Les techniques de supervision doivent alors pouvoir supporter différents objectifs et différentes contraintes pour s’adapter aux services actuels et futurs. Ainsi, ce rapport de thèse développe différentes variantes du DARP - ang. Dial-a-Ride Problem -, le problème de Recherche Opérationnelle modélisant et optimisant un service classique de transport à la demande. Le DARP standard a été étendu de façon à prendre en compte des hypothèses de fonctionnement prometteuses, comme le fait de séparer les composants d’une même requête pour les dispatcher sur des véhicules différents ou encore la présence de mécanismes d’intermodalité. Cette thèse permet également d’inscrire les véhicules autonomes tels que les VIPA dans de nouvelles problématiques de la Recherche Opérationnelle tout en restant dans le domaine du transport à la demande. La modélisation puis l’optimisation de ces systèmes permet de créer les plannings de ces nouveaux véhicules. A long terme, l’évolution technologique devrait permettre de ne plus se soucier du fait qu’ils sont automatiques. Ces travaux tentent de fournir un cadre suffisamment générique permettant à la fois de fournir une solution exploitable aujourd’hui et qui soit adaptable demain.The main objective of the thesis is modeling and optimization of several on-demand transportation services. Supervision techniques must be able to handle numerous criteria and numerous constraints to adapt to the current and future services. Thus, this research develops several types of DARP - Dial-a-Ride Problem -, the operation research problem modeling and optimizing an on-demand transportation system. The standard DARP has been adapted to promising systems, such as those allowing to split the components of the same request and the possibility to dispatch them on different vehicles or the presence of intermodal mechanisms. This thesis also formulates new Operations Research problems in order to integrate autonomous vehicles such as the VIPA in an optimized on-demand transportation system. Modeling and optimizing these systems create schedules of these new vehicles. In the future, technological evolutions are expected and the automatic feature of the vehicles will not be taken into account anymore. These studies attempt to provide a generic framework in order to provide a usable tool for today and an adaptable tool for tomorrow
Algorithms for on-demand touring problems
No full textDans le cadre de cette thèse, nous nous intéressons au problème du transport à la demande. Nous proposons des heuristiques pour résoudre ce problème de manière rapide et efficace. Dans cette thèse, nous traitons trois problèmes : le premier est le Dial-a-ride (DARP standard). Pour ce problème, nous proposons des heuristiques basées sur la technique d’insertion et une technique de propagation de contrainte. Nous proposons aussi la procédure SPLIT et des opérateurs classiques de recherche locale pour résoudre ce problème. Le second est le DARP multicritères pour laquelle nous proposons un schéma de type ELS. Le troisième est un problème de transport à la demande avec contraintes financières (DARPF), qui est une extension de DARP. Nous résolvons ce problème grâce à une heuristique d’insertion et une technique de propagation de contraintes. La fonction objectif détermine les caractéristiques des tournées. Des résultats expérimentaux montrent que nos (méta-) heuristiques donnent des résultats plus favorables aux clients (meilleure qualité de service)As part of this thesis, we investigate the vehicle routing problem. We propose heuristics to solve this problem quickly and efficiently. In this thesis, we deal with three problems: the first is the Dial-a-ride problem. For this problem, we propose heuristics based on the technique of insertion and a constraint propagation technique. We propose also the procedure SPLIT and some operators of local research to solve this problem. The second is the multi-criteria DARP for which we propose an ELS framework. The third is a DARP problem with financial constraints (DARPF), which is an extension of DARP. We solve this problem thanks to insertion heuristics using a constraint propagation technique. The objective function determines the characteristics of the tour. Experimental results show that our (meta-) heuristics give results more favorable to customers (better quality of service
- …
