Multi-Objective Genetic Algorithms for the Single Allocation Hub Location Problem

Hub Location Problems play vital economic roles in transportation and telecommunication networks where goods or people must be efficiently transferred from an origin to a destination point whilst direct origin-destination links are impractical. This work investigates the single allocation hub location problem, and proposes a genetic algorithm (GA) approach for it. The effectiveness of using a single-objective criterion measure for the problem is first explored. Next, a multi-objective GA employing various fitness evaluation strategies such as Pareto ranking, sum of ranks, and weighted sum strategies is presented. The effectiveness of the multi-objective GA is shown by comparison with an Integer Programming strategy, the only other multi-objective approach found in the literature for this problem. Lastly, two new crossover operators are proposed and an empirical study is done using small to large problem instances of the Civil Aeronautics Board (CAB) and Australian Post (AP) data sets.

Le financement des municipalités par le gouvernement fédéral au Canada et aux États-Unis: transferts et facteurs d'allocation.

Rapport de recherche

Fair Production and Allocation of an Excludable Nonrival Good

We study fairness in economies with one private good and one partially excludable nonrival good. A social ordering function determines for each profile of preferences an ordering of all conceivable allocations. We propose the following Free Lunch Aversion condition: if the private good contributions of two agents consuming the same quantity of the nonrival good have opposite signs, reducing that gap improves social welfare. This condition, combined with the more standard requirements of Unanimous Indifference and Responsiveness, delivers a form of welfare egalitarianism in which an agent's welfare at an allocation is measured by the quantity of the nonrival good that, consumed at no cost, would leave her indifferent to the bundle she is assigned.

Efficient Strategy-Proof Allocation Functions in Linear Production Economies

In a linear production model, we characterize the class of efficient and strategy-proof allocation functions, and the class of efficient and coalition strategy-proof allocation functions. In the former class, requiring equal treatment of equals allows us to identify a unique allocation function. This function is also the unique member of the latter class which satisfies uniform treatment of uniforms.

Resource-Monotonicity for House Allocation Problems

We study a simple model of assigning indivisible objects (e.g., houses, jobs, offices, etc.) to agents. Each agent receives at most one object and monetary compensations are not possible. We completely describe all rules satisfying efficiency and resource-monotonicity. The characterized rules assign the objects in a sequence of steps such that at each step there is either a dictator or two agents who “trade” objects from their hierarchically specified “endowments.”

Consistent House Allocation

In practice we often face the problem of assigning indivisible objects (e.g., schools, housing, jobs, offices) to agents (e.g., students, homeless, workers, professors) when monetary compensations are not possible. We show that a rule that satisfies consistency, strategy-proofness, and efficiency must be an efficient generalized priority rule; i.e. it must adapt to an acyclic priority structure, except -maybe- for up to three agents in each object's priority ordering.

Fair Allocation of Production Externalities: Recent Results

We survey recent axiomatic results in the theory of cost-sharing. In this litterature, a method computes the individual cost shares assigned to the users of a facility for any profile of demands and any monotonic cost function. We discuss two theories taking radically different views of the asymmetries of the cost function. In the full responsibility theory, each agent is accountable for the part of the costs that can be unambiguously separated and attributed to her own demand. In the partial responsibility theory, the asymmetries of the cost function have no bearing on individual cost shares, only the differences in demand levels matter. We describe several invariance and monotonicity properties that reflect both normative and strategic concerns. We uncover a number of logical trade-offs between our axioms, and derive axiomatic characterizations of a handful of intuitive methods: in the full responsibility approach, the Shapley-Shubik, Aumann-Shapley, and subsidyfree serial methods, and in the partial responsibility approach, the cross-subsidizing serial method and the family of quasi-proportional methods.

Pour une allocation équitable des ressources en GMF

Objectif : Évaluer la « lourdeur » de la prise en charge clinique des personnes vivant avec le VIH/SIDA (PVVIH) afin d’ajuster l’allocation des ressources en GMF. Méthodologie : Analyse comparative entre le GMF de la Clinique médicale l’Actuel, les GMF montréalais et de l’ensemble du Québec, en identifiant les différences dans les profils de consommation de soins pour les années civiles 2006 à 2008 et les coûts d’utilisation des services pour l’année 2005. Résultats : En 2008, 78% de la clientèle inscrite au GMF de la Clinique médicale l’Actuel est vulnérable comparativement à 28% pour les autres GMF montréalais, une tendance observée pour l’ensemble du Québec. Le nombre moyen de visites par individu inscrit et vulnérable est de 7,57 au GMF l’Actuel alors que la moyenne montréalaise est de 3,37 et celle du Québec de 3,47. Enfin, le coût moyen des visites médicales au GMF l’Actuel en 2005 est de 203,93 $ comparativement à des coûts variant entre 132,14 et 149,53 $ pour les unités de comparaison. Conclusion : L’intensité de l’utilisation des ressources au GMF de la Clinique médicale l’Actuel (nombre d’individus vulnérables, nombre de visites et coûts) suggère que la prise en charge clinique des personnes vivant avec le VIH/SIDA est beaucoup plus lourde qu’un citoyen tout venant ou même de la majorité des autres catégories de vulnérabilité. Afin d’offrir un traitement juste et équitable aux GMF, l’inscription devrait être ajustée afin de tenir compte de la « lourdeur » de cette clientèle et valoriser la prise en charge des personnes qui présentent des tableaux cliniques complexes.

Redundancy gain : manifestations, causes and predictions

Les temps de réponse dans une tache de reconnaissance d’objets visuels diminuent de façon significative lorsque les cibles peuvent être distinguées à partir de deux attributs redondants. Le gain de redondance pour deux attributs est un résultat commun dans la littérature, mais un gain causé par trois attributs redondants n’a été observé que lorsque ces trois attributs venaient de trois modalités différentes (tactile, auditive et visuelle). La présente étude démontre que le gain de redondance pour trois attributs de la même modalité est effectivement possible. Elle inclut aussi une investigation plus détaillée des caractéristiques du gain de redondance. Celles-ci incluent, outre la diminution des temps de réponse, une diminution des temps de réponses minimaux particulièrement et une augmentation de la symétrie de la distribution des temps de réponse. Cette étude présente des indices que ni les modèles de course, ni les modèles de coactivation ne sont en mesure d’expliquer l’ensemble des caractéristiques du gain de redondance. Dans ce contexte, nous introduisons une nouvelle méthode pour évaluer le triple gain de redondance basée sur la performance des cibles doublement redondantes. Le modèle de cascade est présenté afin d’expliquer les résultats de cette étude. Ce modèle comporte plusieurs voies de traitement qui sont déclenchées par une cascade d’activations avant de satisfaire un seul critère de décision. Il offre une approche homogène aux recherches antérieures sur le gain de redondance. L’analyse des caractéristiques des distributions de temps de réponse, soit leur moyenne, leur symétrie, leur décalage ou leur étendue, est un outil essentiel pour cette étude. Il était important de trouver un test statistique capable de refléter les différences au niveau de toutes ces caractéristiques. Nous abordons la problématique d’analyser les temps de réponse sans perte d’information, ainsi que l’insuffisance des méthodes d’analyse communes dans ce contexte, comme grouper les temps de réponses de plusieurs participants (e. g. Vincentizing). Les tests de distributions, le plus connu étant le test de Kolmogorov- Smirnoff, constituent une meilleure alternative pour comparer des distributions, celles des temps de réponse en particulier. Un test encore inconnu en psychologie est introduit : le test d’Anderson-Darling à deux échantillons. Les deux tests sont comparés, et puis nous présentons des indices concluants démontrant la puissance du test d’Anderson-Darling : en comparant des distributions qui varient seulement au niveau de (1) leur décalage, (2) leur étendue, (3) leur symétrie, ou (4) leurs extrémités, nous pouvons affirmer que le test d’Anderson-Darling reconnait mieux les différences. De plus, le test d’Anderson-Darling a un taux d’erreur de type I qui correspond exactement à l’alpha tandis que le test de Kolmogorov-Smirnoff est trop conservateur. En conséquence, le test d’Anderson-Darling nécessite moins de données pour atteindre une puissance statistique suffisante.

Planification de la récolte et allocation des produits aux usines

L’industrie forestière est un secteur qui, même s’il est en déclin, se trouve au cœur du débat sur la mondialisation et le développement durable. Pour de nombreux pays tels que le Canada, la Suède et le Chili, les objectifs sont de maintenir un secteur florissant sans nuire à l’environnement et en réalisant le caractère fini des ressources. Il devient important d’être compétitif et d’exploiter de manière efficace les territoires forestiers, de la récolte jusqu’à la fabrication des produits aux usines, en passant par le transport, dont les coûts augmentent rapidement. L’objectif de ce mémoire est de développer un modèle de planification tactique/opérationnelle qui permet d’ordonnancer les activités pour une année de récolte de façon à satisfaire les demandes des usines, sans perdre de vue le transport des quantités récoltées et la gestion des inventaires en usine. L’année se divise en 26 périodes de deux semaines. Nous cherchons à obtenir les horaires et l’affectation des équipes de récolte aux blocs de coupe pour une année. Le modèle mathématique développé est un problème linéaire mixte en nombres entiers dont la structure est basée sur chaque étape de la chaine d’approvisionnement forestière. Nous choisissons de le résoudre par une méthode exacte, le branch-and-bound. Nous avons pu évaluer combien la résolution directe de notre problème de planification était difficile pour les instances avec un grand nombre de périodes. Cependant l’approche des horizons roulants s’est avérée fructueuse. Grâce à elle en une journée, il est possible de planifier les activités de récolte des blocs pour l’année entière (26 périodes).

Allocation via Deferred-Acceptance under Responsive Priorities

In many economic environments - such as college admissions, student placements at public schools, and university housing allocation - indivisible objects with capacity constraints are assigned to a set of agents when each agent receives at most one object and monetary compensations are not allowed. In these important applications the agent-proposing deferred-acceptance algorithm with responsive priorities (called responsive DA-rule) performs well and economists have successfully implemented responsive DA-rules or slight variants thereof. First, for house allocation problems we characterize the class of responsive DA-rules by a set of basic and intuitive properties, namely, unavailable type invariance, individual rationality, weak non-wastefulness, resource-monotonicity, truncation invariance, and strategy-proofness. We extend this characterization to the full class of allocation problems with capacity constraints by replacing resource- monotonicity with two-agent consistent con ict resolution. An alternative characterization of responsive DA-rules is obtained using unassigned objects invariance, individual rationality, weak non-wastefulness, weak consistency, and strategy-proofness. Various characterizations of the class of "acyclic" responsive DA-rules are obtained by using the properties efficiency, group strategy-proofness, and consistency.

Allocation optimale des ressources pour les applications et services de grille de calcul

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

House allocation via deferred-acceptance

We study the simple model of assigning indivisible and heterogenous objects (e.g., houses, jobs, offi ces, etc.) to agents. Each agent receives at most one object and monetary compensations are not possible. For this model, known as the house allocation model, we characterize the class of rules satisfying unavailable object invariance, individual rationality, weak non-wastefulness, resource-monotonicity, truncation invariance, and strategy-proofness: any rule with these properties must allocate objects based on (implicitly induced) objects' priorities over agents and the agent-proposing deferred-acceptance-algorithm.