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

[EN] Since its birth in the fifties, the maritime container has revolutionised freight international transport providing support to a global production system, marked by the industry offshoring looking for competitive advantages and the configuration of increasingly complex and global supply chains. Within this context, the container has gained a great importance becoming a basic logistic element in supply chains where it plays the role of a transport, production and distribution unit. The success of container is evident if we analyse the evolution of container port traffic, which has been growing at a pace of over 10 % surpassing 600 million TEU of traffic since 2012. The container is, therefore, a key element in global supply chains and container logistics is a field of work and study of enormous interest due to its impact in the efficiency of these supply chains, due to the cost incurred for the operating account of shipping companies and operators (cost which is transferred to the final user and has an impact in the price of the goods being transported), and due to the social and environmental cost associated to the externalities of transport derived from the management of the container fleet. Container logistics has to do with the efficient management of the container fleet, minimising the transport, warehousing and maintenance costs, and maximising the use of the equipment. In container logistics it is possible to categorise, generally, two different categories or levels depending on the geographical scope and the transport modes involved: The international level and the local or regional level. This thesis addresses container logistics at a local or regional level, insofar as in relation to the management of stock, transport and internal movements, trying to react and identify solutions to some of the problems currently facing the port-logistics sector. The research result allows, firstly, knowing in an integral and structured manner the complexity of maritime container logistics. Secondly, specific real problems are identified and addressed for its modelling and analysis that allows for contributing to the improvement of the current logistics system. The following specific problems are addressed: -Modal choice problems for the configuration of internal logistics corridors or chains for maritime container transport. -Problems locating networks of nodal infrastructures facilitating the logistics needs of maritime containers. -Problems related to the movements and management of empty maritime containers. The interest and the academic contribution of this thesis lies as much in the definition and modelling of the specific problems with a significant theoretical discussion, as the empirical application to a real environment and real situations. This has been possible due to the direct contact of the author with the port-logistics sector and the participation in many consultancy and research projects in the cluster of the port of Valencia and also at European and international level. The thesis is outlined as a collection of six scientific articles. The articles have been presented in the thesis in such a way as to follow a logical sequence and not in relation with the chronological order of their publication. / [ES] Desde su aparición en los años 50, el contenedor marítimo ha revoluciona-do el transporte internacional de mercancías dando soporte a un sistema global de producción, marcado por la multilocalización de las industrias en busca de ventajas competitivas y la configuración de cadenas de suministro cada vez más complejas y globales. En este contexto, el contenedor ha adquirido un gran protagonismo convirtiéndose en un elemento logístico básico en las cadenas de suministro en las que actúa como unidad de transporte, producción y distribución. El éxito del contenedor queda puesto de manifiesto al analizar la evolución del tráfico portuario de contenedores, que ha estado creciendo a ritmos superiores al 10 %, superando los 600 millones TEU desde 2012. El contenedor es, por tanto, un elemento clave de las cadenas de suministro globales y la logística del contenedor es un área de estudio y trabajo de enorme interés por el impacto que tiene en la eficiencia de dichas cadenas, por el coste que supone a navieras y operadores en sus cuentas de explotación (coste que se traslada al usuario final y repercute en el precio de las mercancías transportadas) y por el coste social y ambiental asociado a las externalidades del transporte derivadas de esta gestión de la flota de contenedores. La logística del contenedor tiene que ver con la gestión eficiente del parque de contenedores, minimizando los costes de transporte, almacenamiento y mantenimiento, y maximizando la utilización del equipo. En la logística del contenedor se pueden identificar, por lo general, dos categorías o niveles diferenciados en función del ámbito geográfico y de los modos de transporte implicados: El nivel internacional y el nivel local o regional. Este trabajo aborda la logística del contenedor a nivel regional o local, es decir, en lo relativo a la gestión del stock, transporte y movimientos interiores, tratando de dar respuesta y plantear soluciones a algunos de los problemas con los que se encuentra el sector logístico-portuario en la actualidad. El resultado de la investigación permite, en primer lugar, conocer de una forma integral y estructurada la complejidad de la logística del contenedor marítimo. En segundo lugar, se identifican y abordan problemas específicos reales para su modelización y análisis, que permiten contribuir a la mejora del sistema logístico actual. En concreto se abordan los siguientes problemas: -Problemas de elección modal en la configuración de las cadenas o corredores logísticos interiores en el transporte de contenedores marítimos. -Problemas de localización o vertebración de una red de infraestructuras nodales para atender las necesidades logísticas de los contenedores marítimos. -Problemas asociados a los movimientos en vacío y gestión de contenedores marítimos. El interés y contribución académica de este trabajo reside tanto en la definición y modelización de los problemas específicos con una profunda discusión teórica, como en la aplicación empírica a situaciones y entornos reales, cosa que ha sido posible gracias al contacto directo del autor con el sector logístico-portuario y su participación en numerosos proyectos de consulto-ría e investigación tanto en el clúster del Puerto de Valencia como a nivel europeo e internacional. El trabajo se plantea como una colección de seis artículos científicos. El orden en que están situados los artículos en la tesis permite mantener una secuencia lógica construida a posteriori y no según el orden cronológico en el que fueron publicados. / [CAT] Des del seu naixement als anys 50, el contenidor marítim ha revolucionat el transport internacional de mercaderies donant suport a un sistema global de producció, marcat per la multilocalització de les indústries en busca d'avantatges competitives i la configuració de cadenes de subministrament cada vegada més complexes i globals. En aquest context, el contenidor ha adquirit un gran protagonisme convertintse en un element logístic bàsic en les cadenes de subministrament en les quals actua com a unitat de transport, producció i distribució. L'èxit del contenidor s'evidencia en analitzar l'evolució del tràfic portuari de contenidors, que ha estat creixent a ritmes superiors al 10 % superant els 600 milions TEU des de 2012. El contenidor és, per tant, un element clau de les cadenes subministrament globals i la logística del contenidor és un àrea d'estudi i treball d'enorme interès per l'impacte que té en l'eficiència d'aquestes cadenes, pel cost que suposa a navilieres i operadors en els seus comptes d'explotació (cost que es trasllada a l'usuari final i repercuteix en el preu de les mercaderies transportades) i pel cost social i ambiental associat a les externalitats del transport derivades d'aquesta gestió de la flota de contenidors. La logística del contenidor té a veure amb la gestió eficient del parc de contenidors, minimitzant els costos de transport, emmagatzematge i manteniment, i maximitzant la utilització de l'equip. En la logística del contenidor es poden identificar, en general, dues categories o nivells diferenciats en funció de l'àmbit geogràfic i de les modalitats de transport implicats: el nivell internacional i el nivell local o regional. Aquest treball aborda la logística del contenidor a nivell regional o local, és a dir, quant a la gestió de l'estoc, transport i moviments interiors, tractant de donar resposta i plantejar solucions a alguns dels problemes amb els quals es troba el sector logístic-portuari en l'actualitat. El resultat de la recerca permet, en primer lloc, conèixer d'una forma integral i estructurada la complexitat de la logística del contenidor marítim. En segon lloc, s'identifiquen i aborden problemes específics reals per a la seua modelització i anàlisi, que permeten contribuir a la millora del sistema logístic actual. En concret s'aborden els següents problemes: -Problemes d'elecció modal en la configuració de les cadenes o corredors logístics interiors en el transport de contenidors marítims. -Problemes de localització o vertebració d'una xarxa d'infraestructures nodals per a atendre les necessitats logístiques dels contenidors marítims. -Problemes associats als moviments en buit i gestió de contenidors marítims. L'interès i contribució acadèmica d'aquest treball resideix tant en la definició i modelització dels problemes específics amb una profunda discussió teòrica, com en l'aplicació empírica a situacions i entorns reals, cosa que ha sigut possible gràcies al contacte directe de l'autor amb el sector logístic-portuari i la seua participació en nombrosos projectes de consultoria i recerca tant en el clúster del Port de València com a nivell europeu i internacional. El treball es planteja com una col·lecció de sis articles científics. L'ordre en què estan situats els articles en la tesi permet mantenir una seqüència lògica construïda a posteriori i no segons l'ordre cronològic en el qual van ser publicats. / Furió Pruñonosa, S. (2016). Modelos y métodos avanzados para la logística del contenedor. Aplicación al Puerto de Valencia [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/63248 / TESIS