HAL-Ecole des Ponts ParisTech
Not a member yet
42743 research outputs found
Sort by
Linear Lexicographic Optimization and Preferential Bidding System
No full textInternational audienceSome airlines use the preferential bidding system to construct the schedules of their pilots. In this system, the pilots bid on the different activities and the schedules that lexicographically maximize the scores of the pilots according to their seniority are selected. A sequential approach to solve this maximization problem is natural: The problem is first solved with the bids of the most senior pilot, and then it is solved with those of the second most senior without decreasing the score of the most senior, and so on. The literature admits that the structure of the problem somehow imposes such an approach. The problem can be modeled as an integer linear lexicographic program. We propose a new efficient method, which relies on column generation for solving its continuous relaxation and returns proven optimality gaps. To design this column generation, we prove that bounded linear lexicographic programs admit “primal-dual” feasible bases, and we show how to compute such bases efficiently. Another contribution on which our method relies is the extension of standard tools for resource-constrained longest path problems to their lexicographic versions. This is useful in our context because the generation of new columns is modeled as a lexicographic resource-constrained longest path problem. Numerical experiments show that this new method is already able to solve to proven optimality industrial instances provided by Air France, with up to 150 pilots. By adding a last ingredient in the resolution of the longest path problems, which exploits the specificity of the preferential bidding system, the method achieves for these instances computational times that are compatible with operational constraints. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2022.0372
De nouveaux chantiers pour l’histoire de la protection sociale ?
No full textInternational audiencePour compléter ce dossier de la RFAS consacré à l’histoire de la protection sociale, il a été jugé utile de proposer un regard prospectif sur trois champs de recherche aujourd’hui en plein essor et encore peu développés dans le domaine de la protection sociale mais appelés sans nul doute à renouveler les problématiques et à enrichir nos connaissances en la matière. Ont été retenus le « genre », les « générations » et la « question coloniale ». Dans ce but, Bruno Valat a interrogé trois spécialistes de ces questions, respectivement une politiste (Sandrine Dauphin), un économiste (André Masson) et un historien (Antoine Perrier)
L’antisémitisme et la réforme de la Bourse de Paris (1893-1898)
No full textInternational audienceThe reforms of the Paris Stock Exchange between 1893 and 1898 gave rise to manifestations of antisemitism that were very much of their time. Supporters of the stockbrokers’ monopoly branded their opponents who participated in the free market (known as coulissiers ) as Jews. Beyond the conservative defense of a privileged guild and its liberal contestation, this episode illuminates two conceptions of the financial market that are still current today. The coulissiers favored liquidity and speed of execution, professional financiers, and international exchanges, potentially at the cost of trading security and equality, and to the detriment of small traders and market stability. The official brokers ( agents de change ) had opposite priorities. The debate was complexified by the emergence of a third, socialist position that rejected both liberal and conservative visions, proposing a public-service stock exchange that would favor transparency and security without benefiting a privileged group. Although this position did not win out, it nevertheless heralded new conceptions of the market economy.Les réformes de la Bourse de Paris entre 1893 et 1898 sont l’occasion de manifestations d’antisémitisme qui peuvent ne guère surprendre dans le contexte de l’époque. Les partisans du monopole des agents de change traitent de juifs les membres du marché libre (les coulissiers) qui le remettent en cause. Au-delà de la défense conservatrice d’une corporation privilégiée et de sa contestation libérale, cet épisode permet de mieux comprendre que ce sont deux conceptions du marché financier toujours actuelles qui sont en cause. Les coulissiers privilégient la liquidité, la rapidité d’exécution, les financiers professionnels et les échanges internationaux, au prix éventuellement d’une moindre sécurité et d’une moindre égalité dans l’échange, au détriment sans doute des petits boursicoteurs et de la stabilité du marché. Les agents de change avaient des priorités inverses. Le débat s’enrichit de l’émergence d’une tierce position socialiste qui renvoie dos à dos libéraux et conservateurs pour proposer une Bourse service public privilégiant transparence et sécurité sans que ce soit au profit d’un groupe privilégié, position qui, sans prévaloir, annonce de nouvelles conceptions de l’économie de marché
Une Seule Santé comme axe de construction d'un Système Intersectoriel d'Innovation (S.I.I.) au Cameroun
No full textSource Agritrop Cirad (https://agritrop.cirad.fr/608653/)International audienceThe Innovation Systems (IS) approach has been widely used since the end of the 1980s and has seen a plethora of terminologies appropriate to the areas visited. This approach has both made it possible to understand the nature of inter-institutional interactions between stakeholders in a system and has influenced public innovation policies in terms of relevant instruments. The approach in terms of IS has been duplicated on numerous territorial scales (regional, local, national) or even sectoral. However, no inter-sectoral proposal has been made within this approach. We thus challenge the concept of One Health in order to be able to propose an Intersectoral Innovation System within the framework of Cameroon. One Health represents an integrated analysis framework connecting animals, plants and their environment. One Health can thus represent a potential axis for building a new Intersectoral Innovation System through better interministerial and intersectoral coordination. In this, we will see how it can be integrated as an intersectoral public policy tool, as well as inserted into this new innovation system in Cameroon. The Innovation Systems (IS) approach has been widely used since the end of the 1980s and has seen a plethora of terminologies appropriate to the areas visited. This approach has both made it possible to understand the nature of inter-institutional interactions between stakeholders in a system and has influenced public innovation policies in terms of relevant instruments. The approach in terms of IS has been duplicated on numerous territorial scales (regional, local, national) or even sectoral. However, no inter-sectoral proposal has been made within this approach. We thus challenge the concept of One Health in order to be able to propose an Intersectoral Innovation System within the framework of Cameroon. One Health represents an integrated analysis framework connecting animals, plants and their environment. One Health can thus represent a potential axis for building a new Intersectoral Innovation System through better interministerial and intersectoral coordination. In this, we will see how it can be integrated as an intersectoral public policy tool, as well as inserted into this new innovation system in Cameroon.L'approche par les Systèmes d'Innovation (S.I) a été largement mobilisée depuis la fin des années 1980 et a connu pléthores terminologies appropriées aux terrains visités. Cette approche a, à la fois permis de saisir la nature des interactions inter-institutionnelles entre parties prenantes d'un système et a influencé les politiques publiques d'innovation en termes d'instruments pertinents. L'approche en termes de S.I est dupliquée sur de nombreuses échelles territoriales (régionales, locales, nationales) ou encore sectorielles. Néanmoins, aucune proposition intersectorielle n'a été réalisée au sein de cette approche. Nous interpellons ainsi le concept d'une Seule Santé pour pouvoir proposer un Système Intersectoriel d'Innovation dans le cadre du Cameroun. Une Seule Santé représente un cadre d'analyse intégrée connectant les animaux, les plantes et leur environnement. Une Seule Santé peut ainsi représenter un axe potentiel de construction d'un nouveau Système Intersectoriel d'Innovation par une meilleure coordination interministérielle et intersectorielle. En cela, nous verrons comment il peut être intégré comme outil de politique publique intersectorielle, tout comme inséré dans ce nouveau système d'innovation au Cameroun
Estimations et prédictions solaires
No full textE-magazine of the University of French Guiana Foundation and the Ecological Transition Agency (Agency for Ecological Transition) in accordance with ADEME/UG agreement 20GYC0082E-magazine de la Fondation de l’Université de Guyane et de l’Agence de la transition écologique selon convention ADEME/UG 20GYC008
Résistance au flambement de panneaux CLT avec imperfections. Caractérisation expérimentale et critères de dimensionnement
No full textCross-laminated timber (CLT) is a panel made of several layers of wood lamellas. The orientation of the lamellas alternates by 90° from one layer to another. CLT is used in timber buildings, for example, as load-bearing walls. The buckling resistance of CLT panels must be verified while being designed. The standards governing timber construction were developed in the 1990s, when the use of CLT panels was still uncommon. Therefore, they do not specifically cover the use of CLT, but rather glued laminated timber (GLT) or solid wood. This is the case with Eurocode 5, which will be examined in this study. However, CLT has different structural properties from those of GLT or solid wood. Indeed, its crossed layers can be subjected to rolling shear. Since the rigidity of wood in rolling shear is much lower than its axial rigidity, CLT exhibits flexibility in shear. In addition to this shear flexibility, wood is a heterogeneous material with variable properties. Thus, it seems necessary to evaluate the quality of predictions of buckling strengths using failure criteria for CLT panels subjected to axial compression and moments.To this end, we present in this study the criteria found in the standards, explaining their assumptions. A nonlinear criterion taking into account second-order effects caused by all types of imperfections and moments is also presented. The aim of this study is to compare the buckling strengths predicted by these criteria with those obtained experimentally.To perform this comparison of criteria, we first determine the stiffness and strengths necessary to use the criteria, through experimental characterization. Two experimental four-point bending campaigns on panels of different dimensions, as well as an experimental compression campaign on small CLT samples were conducted for this purpose. Then, the buckling strengths of CLT panels are measured through two experimental buckling campaigns. Nineteen CLT panels were tested, with different heights and load eccentricities. These tests also allow for an experimental estimation of the critical buckling load, as well as a total eccentricity taking into account backlash in the experimental setup and imperfections. We observe a wide variability in the strengths obtained by the different criteria. The direct measurement of the critical load significantly reduces this variability, and the nonlinear criterion then appears to be the most relevant for predicting the buckling strengths of CLT panels.Le bois lamellé croisé (ou CLT) est un empilement de plusieurs couches constituées de lamelles de bois. L'orientation des lamelles alterne de 90° d'une couche à l'autre. Le CLT est utilisé dans la construction de bâtiments en bois, par exemple en murs porteurs. La tenue en flambement des panneaux de CLT doit donc faire l'objet d'une vérification lors de leur dimensionnement. Les normes régissant la construction en bois ont été développées dans les années 1990, alors que l'utilisation de panneaux de CLT était encore peu courante. Elles ne couvrent donc pas spécifiquement l'utilisation du CLT, mais plutôt du bois lamellé collé (GLT) ou du bois massif. C'est le cas de l'Eurocode 5 qui sera étudié dans ce travail. Le CLT a pourtant des propriétés structurelles différentes de celles du GLT ou du bois massif. En effet, ses couches croisées peuvent être sollicitées en cisaillement roulant. La rigidité du bois en cisaillement roulant étant très faible devant sa rigidité axiale, cela confère au CLT une souplesse en cisaillement. En plus de cette souplesse en cisaillement, le bois est un matériau hétérogène dont les propriétés sont variables. Il parait ainsi nécessaire d'évaluer la qualité des prédictions des résistances en flambement par les critères de rupture pour des panneaux de CLT soumis à une compression axiale et à des moments. Pour cela, nous présentons dans ce travail les critères présents dans les normes en explicitant leurs hypothèses. Un critère non-linéaire prenant en compte les effets de second ordre causés par tous les types d'imperfections et de moments est également présenté. L'objectif est de comparer les résistances en flambement prédites par ces critères avec celles obtenues expérimentalement. Pour effectuer cette comparaison des critères, nous déterminons d'abord les raideurs et résistances sur lesquelles ils se basent, au moyen d'essais de caractérisation. Deux campagnes expérimentales de flexion quatre-points sur des panneaux de dimensions différentes, ainsi qu'une campagne expérimentale de compression sur des petits échantillons de CLT ont été réalisées en ce sens. Ensuite, les résistances en flambement de panneaux de CLT sont mesurées au moyen de deux campagnes expérimentales de flambement. Dix-neuf panneaux de CLT ont ainsi été testés, présentant des hauteurs et des excentrements de charge différents. Ces essais permettent également de faire une estimation expérimentale de l'effort critique de flambement, ainsi que d'un excentrement total prenant en compte les jeux présents dans le dispositif expérimental et les imperfections. Nous observons une grande variabilité des résistances obtenues par les différents critères. La mesure directe de l'effort critique permet de réduire significativement cette variabilité, et le critère non-linéaire semble alors être le plus pertinent pour prédire les résistances en flambement des panneaux de CLT
Optimisation intégrée des décisions de logistique des entrepôts avec prise en compte de facteurs humains
No full textThis thesis is structured in two main parts that explore different research directions related to warehousing logistics and human factors. As a first objective, this thesis studies the integration of planning problems in manual picker-to-parts warehouses. The work achieved during the preparation of this thesis advances the state-of-the-art on the topic in several dimensions. First, we study the tractability of the Picker Routing Problem (PRP) in conventional warehouses. Moving forward, we explore the integration of the storage and routing decisions, motivated by modern industrial practices due to the development of e-commerce, where storage decisions are becoming increasingly dynamic. We propose a generic Branch-Cut-and-Price algorithm able to solve a large class of variants of the problem. Finally, we propose efficient move evaluation and neighborhood exploration routines for integrated OP problems. These results are based on the introduction of a novel PRP heuristic based on lower and upper bounds for the problem. As a secondary objective, this thesis studies the integration of human factors and ergonomics in optimization problems, with a focus on logistics and manufacturing systems. Human-aware optimization is becoming an important research stream with the advent of Industry 5.0, placing the human operator at the core of the process design. Our main contribution to the topic is an extensive review of the literature. In this work, we present a holistic picture of human-aware optimization of logistics and manufacturing systems.Cette thèse est divisée en deux parties principales qui explorent différentes thématiques de recherche liées à la logistique des entrepôts et aux facteurs humains. Comme premier objectif, cette thèse étudie l'intégration de problèmes de planification dans les entrepôts où la préparation de commandes est effectuée par des opérateurs humains. Le travail effectué au cours de cette thèse permet de faire progresser l'état de l'art sur le sujet à plusieurs niveaux. Tout d'abord, nous étudions la complexité computationnelle du problème de routage des préparateurs dans les entrepôts conventionnels. Nous étudions ensuite l'intégration des décisions de stockage et de routage. Nous proposons un algorithme générique de Branch-Cut-and-Price capable de résoudre une large classe de variantes du problème. Enfin, nous développons des méthodes efficaces pour l'évaluation des déplacements et l'exploration de voisinages pour les problèmes de planification intégrée de logistique des entrepôts. Ces résultats reposent sur l'introduction d'une nouvelle heuristique pour le problème de routage des préparateurs, fournissant des bornes inférieures et supérieures pour le problème.Dans un second temps, cette thèse étudie l'intégration des facteurs humains et de l'ergonomie dans les problèmes d'optimisation liés aux systèmes logistiques et manufacturiers. Notre principale contribution à ce domaine est une revue approfondie de la littérature, où nous proposons une vision holistique de la prise en compte de facteurs humains dans les algorithmes d'optimisation pour les systèmes logistiques et manufacturiers
Arbres, décompositions, et théorie des Nœuds
No full textGraph theory and knot theory are two well established mathematical fields which present profound interactions. This thesis focuses on investigating some knot theory problems from a computational point of view and drawing inspiration from results and methods stemming from graph theory.The first problem we address concerns the decidability of a knot invariant. The genus of a knot is a classical knot invariant: it is the minimal genus of an embedded orientable surface in the 3-dimensional space admitting the knot as its boundary. It is now fairly well understood from a computational perspective. On the contrary, no algorithm is known for its four-dimensional variants, both in the smooth and in the topological locally flat category.We investigate a class of knots and links called Hopf arborescent links, which are obtained as the boundaries of surfaces constructed by iterated plumbings of Hopf bands. We show that for such links, computing the genus defects, which measure how much the four-dimensional genera differ from the classical genus, is decidable. Our proof is non-constructive and is obtained by proving that a containment relation on surfaces associated to Hopf arborescent links forms a well-quasi-order.The second problem we tackle is motivated by the existence of efficient algorithms to compute many knot invariants and properties on diagrams of low treewidth. It was recently proved that there exist knots which do not admit any diagram of low treewidth, and the proof relied on intricate low-dimensional topology techniques. We initiate here a thorough investigation of tree decompositions of knot diagrams (or more generally, diagrams of spatial graphs) using ideas from structural graph theory. We define an obstruction on spatial embeddings that forbids low treewidth diagrams, and we prove that it is optimal with respect to a related width invariant. We then show the existence of this obstruction whenever an embedding into a surface with high compression-representativity exists, which is the case for torus knots. Thus, we provide a new and self-contained proof that those do not admit diagrams of low treewidth.Finally, we shift our focus toward the complexity of knot diagrams throughout the action of Reidemeister moves. Recognising the trivial knot is a fundamental question of knot theory. A natural way to attack this problem is by applying Reidemeister moves on a diagram in a brute force or random manner until the diagram corresponds to a circle. It turns out that the number of crossings of some unknot diagrams must increase during the execution of this algorithm. No super constant lower bound is known on how many such crossings need to be added during the execution of similar algorithms. The problem of deciding whether two links are split, i.e. can be separated by a sphere, is approachable in the same way and presents the same issue. We prove that there exist link diagrams which require an arbitrarily large number of added crossings to be split via this methodLa théorie des graphes et la théorie des nœuds sont deux célèbres domaines mathématiques qui présentent de profondes interactions. Cette thèse se concentre sur l'étude de certains problèmes de théorie des nœuds d'un point de vue informatique et en s'inspirant de résultats et méthodes issus de la théorie des graphes.Le premier problème que nous abordons concerne la décidabilité d'un invariant de nœud. Le genre d'un nœud est un invariant classique : c'est le genre minimal d'une surface orientable plongée dans l'espace de dimension 3 qui est bordée par le nœud. De nos jours, il est assez bien compris d'un point de vue informatique. En revanche, aucun algorithme n'est connu pour ses variantes en dimension 4, à la fois dans la catégorie des variétés lisses et dans celle des variétés localement plates. Nous étudions une classe de nœuds et d'entrelacs appelés entrelacs arborescents de Hopf, qui sont obtenus comme bords de surfaces construites par des plombages itérés de bandes de Hopf. Nous montrons que sur ces entrelacs, le calcul des défauts de genre, qui mesurent à quel point les genres quadridimensionnels diffèrent du genre classique, est décidable. Notre preuve est non-constructive et est obtenue en prouvant qu'une relation d'inclusion sur les surfaces associées aux entrelacs arborescents de Hopf forme un bel ordre.Le deuxième problème que nous attaquons est motivé par l'existence d'algorithmes efficaces pour calculer de nombreux invariants et propriétés de nœuds sur des diagrammes de faible largeur arborescente (treewidth). Il a été récemment prouvé, par de complexes résultats de topologie en basse dimension, qu'il existe des nœuds qui n'admettent pas de diagrammes de faible largeur arborescente. Nous entamons ici une étude approfondie des décompositions arborescentes des diagrammes de nœuds (ou plus généralement, des diagrammes de graphes spatiaux) en utilisant des idées de la théorie structurelle des graphes. Nous définissons une obstruction sur les plongements dans l'espace qui s'oppose à des diagrammes de faible largeur arborescente. Nous prouvons de plus que cette obstruction est optimale vis-à-vis d'un invariant de largeur que nous définissons. Nous montrons ensuite l'existence d'une telle obstruction dès qu'il existe un plongement dans une surface avec haute représentativité. Cette dernière partie est toujours vérifiée sur les nœuds toriques: nous fournissons ainsi une nouvelle preuve que ces nœuds n'admettent aucun diagramme de faible largeur arborescente. Pour finir, nous nous concentrons sur la complexité des diagrammes de nœuds sous l'action de mouvements de Reidemeister. Reconnaître le nœud trivial est un problème fondamental de théorie des nœuds. Une façon naturelle de l'attaquer est d'appliquer des mouvements de Reidemeister sur un diagramme du nœud de manière exhaustive ou aléatoire jusqu'à ce que le diagramme corresponde à un cercle. Il s'avère que le nombre de croisements de certains diagrammes du nœud trivial doit nécessairement augmenter pendant l'exécution de cet algorithme. De plus, on ne connaît pas de borne inférieure meilleure que constante sur le nombre de croisements qui doivent être ajoutés pendant l'exécution d'algorithmes similaires. Cet algorithme peut aussi être appliqué au problème de décider si un entrelacs est séparé, c'est-à-dire, s'il existe une sphère qui sépare deux de ses composantes. Il présente le même problème de devoir ajouter des croisements à un diagramme pendant son exécution. Nous prouvons qu'il existe des diagrammes d'entrelacs qui nécessitent un nombre arbitrairement grand de croisements à ajouter pour être séparés en utilisant cet algorithm
