In this study, we propose a two-phase solution approach for approximating the efficient frontier of a bicriteria hub location problem. We develop an evolutionary algorithm to locate the hubs on the network as the first phase. In the second phase, we develop a bounding procedure based on dominance relations and using the determined bounds, we solve the allocation subproblem for each located hub set. The two-phase approach is tested on the Australian Post data set and it is observed that our approach approximates the entire efficient frontier well. In addition, we suggest an interactive procedure to find the solutions that are in the decision maker&rsquo / s preferred region of the solution space. In this procedure, we progressively incorporate the preferences of the decision maker and direct the search towards the preferred regions. Based on some computational experiments, it is observed that the interactive procedure converges to the preferred regions.

In this study, we consider the Turkish postal delivery system and develop an effective solution approach for the combined hub location and routing problem where the location of hub nodes are determined, the nonhub regional postal offices are allocated to the hubs, and the optimal set of routes are determined for each hub. Since the realized post-routing distances between origin-destination pairs are different from those used in the hub-location model, we develop an algorithm that finds the route-compatible hub configuration and allocation paths. The algorithm is the one that iterates between the hub-location phase and a routing phase. Our strategy consists of updating the distances used in the first phase in order to produce a solution that contains the cognition of routes. Some special structures in the routed network are also identified and used for improving the solution. Computational experience is reported.

In this thesis, we introduce the Partitioning-Hub Location-Routing problem (PHLRP), which can be classied as a variant of the hub location problem. PHLRP consists of partitioning a network into sub-networks, locating at least one hub in each subnetwork and routing the traffic within the network such that all inter-subnetwork traffic is routed through the hubs and all intra-subnetwork traffic stays within the sub-networks all the way from the source to the destination. Obviously, besides the hub location component, PHLRP also involves a graph partitioning component and a routing component. PHLRP finds applications in the strategic planning or deployment of the Intermediate System-Intermediate System (ISIS) Internet Protocol networks and the Less-than-truck load freight distribution systems. First, we introduce three IP formulations for solving PHLRP. The hub location component and the graph partitioning components of PHLRP are modeled in the same way in all three formulations. More precisely, the hub location component is represented by the p-median variables and constraints; and the graph partitioning component is represented by the size-constrained graph partitioning variables and constraints. The formulations differ from each other in the way the peculiar routing requirements of PHLRP are modeled. We then carry out analytical and empirical comparisons of the three IP formulations. Our thorough analysis reveals that one of the formulations is provably the tightest of the three formulations. We also show analytically that the LP relaxations of the other two formulations do not dominate each other. On the other hand, our empirical comparison in a standard branch-and-cut framework that is provided by CPLEX shows that not the tightest but the most compact of the three formulations yield the best performance in terms of solution time. From this point on, based on the insight gained from detailed analysis of the formulations, we focus our attention on a common sub-problem of the three formulations: the so-called size-constrained graph partitioning problem. We carry out a detailed polyhedral analysis of this problem. The main benet from this polyhedral analysis is that the facets we identify for the size-constrained graph partitioning problem constitute strong valid inequalities for PHLRP. And finally, we wrap up our efforts for solving PHLRP. Namely, we present the results of our computational experiments, in which we employ some facets of the size-constrained graph partitioning polytope in a branch-and-cut algorithm for solving PHLRP. Our experiments show that our approach brings signicant improvements to the solution time of PHLRP when compared with the default branch-and-cut solver of XPress. / Dans cette thèse, nous introduisons le problème Partitionnement-Location des Hubs et Acheminement (PLHA), une variante du problème de location de hubs. Le problème PLHA partitionne un réseau afin d'obtenir des sous-réseaux, localise au moins un hub dans chaque sous-réseau et achemine le traffic dans le réseau de la maniére suivante : le traffic entre deux sous-réseaux distincts doit être éxpedié au travers des hubs tandis que le traffic entre deux noeuds d'un même sous-réseau ne doit pas sortir de celui-ci. PLHA possède des applications dans le planning stratégique, ou déploiement, d'un certain protocole de communication utilisé dans l'Internet, Intermediate System - Intermediate System, ainsi que dans la distribution des frets. Premièrement, nous préesentons trois formulations linéaires en variables entières pour résoudre PLHA. Le partitionnement du graphe et la localisation des hubs sont modélisées de la même maniére dans les trois formulations. Ces formulations diffèrent les unes des autres dans la maniére dont l'acheminement du traffic est traité. Deuxièmement, nous présentons des comparaisons analytiques et empiriques des trois formulations. Notre comparaison analytique démontre que l'une des formulations est plus forte que les autres. Néanmoins, la comparaison empirique des formulations, via le solveur CPLEX, montre que la formulation la plus compacte (mais pas la plus forte) obtient les meilleures performances en termes de temps de résolution du problème. Ensuite, nous nous concentrons sur un sous-problème, à savoir, le partitionnement des graphes sous contrainte de taille. Nous étudions le polytope des solutions réalisables de ce sous-problème. Les facettes de ce polytope constituent des inégalités valides fortes pour PLHA et peuvent être utilisées dans un algorithme de branch-and-cut pour résoudre PLHA. Finalement, nous présentons les résultats d'un algorithme de branch-and-cut que nous avons développé pour résoudre PLHA. Les résultats démontrent que la performance de notre méthode est meilleure que celle de l'algorithme branch-and-cut d'Xpress.

In this study, we consider the hub location problem of PTT, first realized by Cetiner (2003), and propose the evaluation of multiple decision criteria while locating hubs. Since the mathematical model for the problem is too large to be solved, we utilize heuristic methods in the solution procedure. While doing this, we first test two algorithms, NSGA-II and SPEA2, on different hub location problems and use the algorithm with better performance while solving the PTT problem.

No description available.

ABSTRACT A GENETIC ALGORITHM FOR p-HUB CENTER PROBLEM WITH STOCHASTIC SERVICE LEVEL CONSTRAINTS Eraslan Demirci, S&uuml / kran M.Sc., Department of Industrial Engineering Supervisor: Asst. Prof. Dr. Sedef Meral December 2010, 170 pages The emphasis on minimizing the costs and travel times in a network of origins and destinations has led the researchers to widely study the hub location problems in the area of location theory in which locating the hub facilities and designing the hub networks are the issues. The p-hub center problem considering these issues is the subject of this study. p-hub center problem with stochastic service level constraints and a limitation on the travel times between the nodes and hubs is addressed, which is an uncapacitated, single allocation problem with a complete hub network. Both a mathematical model and a genetic algorithm are proposed for the problem. We discuss the general framework of the genetic algorithm as well as the problem-specific components of algorithm. The computational studies of the proposed algorithm are realized on a number of problem instances from Civil Aeronautics Board (CAB) data set and Turkish network data set. The computational results indicate that the proposed genetic algorithm gives satisfactory results when compared with the optimum solutions and solutions obtained with other heuristic methods.

京都大学 / 新制・課程博士 / 博士(工学) / 甲第24219号 / 工博第5047号 / 新制||工||1788(附属図書館) / 京都大学大学院工学研究科都市社会工学専攻 / (主査)教授 藤井 聡, 教授 山田 忠史, 准教授 QURESHI Ali Gul / 学位規則第4条第1項該当 / Doctor of Philosophy (Engineering) / Kyoto University / DGAM

Cette thèse, présente des contributions à la résolution (sur les GPUs) de problèmes d'optimisations réels de grandes tailles. Les problèmes de tournées de véhicules (VRP) et ceux de localisation des hubs (HLP) sont traités. Diverses approches et leur implémentions sur GPU pour résoudre des variantes du VRP sont présentées. Un algorithme génétique (GA) parallèle sur GPU est proposé pour résoudre différentes variantes du HLP. Le GA adapte son codage, sa solution initiale, ses opérateurs génétiques et son implémentation à chacune des variantes traitées. Enfin, nous avons utilisé le GA pour résoudre le HLP avec des incertitudes sur les données.Les tests numériques montrent que les approches proposées exploitent efficacement la puissance de calcul du GPU et ont permis de résoudre de larges instances jusqu'à 6000 nœuds. / This thesis presents contributions to the resolution (on GPUs) of real optimization problems of large sizes. The vehicle routing problems (VRP) and the hub location problems (HLP) are treated. Various approaches implemented on GPU to solve variants of the VRP. A parallel genetic algorithm (GA) on GPU is proposed to solve different variants of the HLP. The proposed GA adapts its encoding, initial solution, genetic operators and its implementation to each of the variants treated. Finally, we used the GA to solve the HLP with uncertainties on the data.The numerical tests show that the proposed approaches effectively exploit the computing power of the GPU and have made it possible to resolve large instances up to 6000 nodes.

In this thesis, we introduce the Partitioning-Hub Location-Routing problem (PHLRP), which can be classified as a variant of the hub location problem.<p>PHLRP consists of partitioning a network into sub-networks, locating at least one hub in each subnetwork and routing the traffic within the network such that all inter-subnetwork traffic is routed through the hubs and all intra-subnetwork traffic stays within the sub-networks all the way from the source to the destination. Obviously, besides the hub location component, PHLRP also involves a graph partitioning component and a routing component. PHLRP finds applications in the strategic planning or deployment of the Intermediate System-Intermediate System (ISIS) Internet Protocol networks and the Less-than-truck load freight distribution systems.<p><p>First, we introduce three IP formulations for solving PHLRP. The hub location component and the graph partitioning components of PHLRP are<p>modeled in the same way in all three formulations. More precisely, the hub location component is represented by the p-median variables and constraints; and the graph partitioning component is represented by the size-constrained graph partitioning variables and constraints. The formulations differ from each other in the way the peculiar routing requirements of PHLRP are modeled.<p><p>We then carry out analytical and empirical comparisons of the three IP<p>formulations. Our thorough analysis reveals that one of the formulations is<p>provably the tightest of the three formulations. We also show analytically that the LP relaxations of the other two formulations do not dominate each other. On the other hand, our empirical comparison in a standard branch-and-cut framework that is provided by CPLEX shows that not the tightest but the most compact of the three formulations yield the best performance in terms of solution time. <p><p>From this point on, based on the insight gained from detailed analysis of the formulations, we focus our attention on a common sub-problem of the three formulations: the so-called size-constrained graph partitioning problem. We carry out a detailed polyhedral analysis of this problem. The main benefit from this polyhedral analysis is that the facets we identify for the size-constrained graph partitioning problem constitute strong valid inequalities for PHLRP.<p><p>And finally, we wrap up our efforts for solving PHLRP. Namely, we present<p>the results of our computational experiments, in which we employ some facets<p>of the size-constrained graph partitioning polytope in a branch-and-cut algorithm for solving PHLRP. Our experiments show that our approach brings<p>significant improvements to the solution time of PHLRP when compared with<p>the default branch-and-cut solver of XPress. <p><p>/<p><p>Dans cette thèse, nous introduisons le problème Partitionnement-Location des Hubs et Acheminement (PLHA), une variante du problème de location de hubs. Le problème PLHA partitionne un réseau afin d'obtenir des sous-réseaux, localise au moins un hub dans chaque sous-réseau et achemine le traffic dans le réseau de la maniére suivante :le traffic entre deux<p>sous-réseaux distincts doit être éxpedié au travers des hubs tandis que le traffic entre deux noeuds d'un même sous-réseau ne doit pas sortir de celui-ci. PLHA possède des applications dans le planning stratégique, ou déploiement, d'un certain protocole de communication utilisé<p>dans l'Internet, Intermediate System - Intermediate System, ainsi que dans la distribution des frets.<p><p>Premièrement, nous préesentons trois formulations linéaires en variables entières pour résoudre PLHA. Le partitionnement du graphe et la localisation des hubs sont modélisées de la même maniére dans les trois formulations. Ces formulations diffèrent les unes des autres dans la maniére dont l'acheminement du traffic est traité.<p><p>Deuxièmement, nous présentons des comparaisons analytiques et empiriques des trois formulations. Notre comparaison analytique démontre que l'une des formulations est plus forte que les autres. Néanmoins, la comparaison empirique des formulations, via le solveur CPLEX, montre que la formulation la plus compacte (mais pas la plus forte) obtient les meilleures performances en termes de temps de résolution du problème.<p><p>Ensuite, nous nous concentrons sur un sous-problème, à savoir, le partitionnement des graphes sous contrainte de taille. Nous étudions le polytope des solutions réalisables de ce sous-problème. Les facettes de ce polytope constituent des inégalités valides fortes pour<p>PLHA et peuvent être utilisées dans un algorithme de branch-and-cut pour résoudre PLHA.<p><p>Finalement, nous présentons les résultats d'un algorithme de branch-and-cut que nous avons développé pour résoudre PLHA. Les résultats démontrent que la performance de notre méthode est meilleure que celle de l'algorithme branch-and-cut d'Xpress.<p> / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Rising concerns related to the effects of traffic congestion have led to the search for alternative transportation solutions. Advances in battery technology have resulted in an increase of electric vehicles (EVs), which serve to reduce the impact of many of the negative consequences of congestion, including pollution and the cost of wasted fuel. Furthermore, the energy-efficiency and quiet operation of electric motors have made feasible concepts such as Urban Air Mobility (UAM), in which electric aircraft transport passengers in dense urban areas prone to severe traffic slowdowns. Electrified transportation may be the solution needed to combat urban gridlock, but many logistical questions related to the design and operation of the resultant transportation networks remain to be answered. This research begins by examining the near-term effects of EV charging networks. Stationary plug-in methods have been the traditional approach to recharge electric ground vehicles; however, dynamic charging technologies that can charge vehicles while they are in motion have recently been introduced that have the potential to eliminate the inconvenience of long charging wait times and the high cost of large batteries. Using an agent-based model verified with traffic data, different network designs incorporating these dynamic chargers are evaluated based on the predicted benefit to EV drivers. A genetic optimization is designed to optimally locate the chargers. Heavily-used highways are found to be much more effective than arterial roads as locations for these chargers, even when installation cost is taken into consideration. This work also explores the potential long-term effects of electrified transportation on urban congestion by examining the implementation of a UAM system. Interdependencies between potential electric air vehicle ranges and speeds are explored in conjunction with desired network structure and size in three different regions of the United States. A method is developed to take all these considerations into account, thus allowing for the creation of a network optimized for UAM operations when vehicle or topological constraints are present. Because the optimization problem is NP-hard, five heuristic algorithms are developed to find potential solutions with acceptable computation times, and are found to be within 10% of the optimal value for the test cases explored. The results from this exploration are used in a second agent-based transportation model that analyzes operational parameters associated with UAM networks, such as service strategy and dispatch frequency, in addition to the considerations associated with network design. General trends between the effectiveness of UAM networks and the various factors explored are identified and presented.