The emphasis on minimizing the logistics costs to decrease overall system costs has led the researchers to consider the interdependencies between the decisions of locating facilities and planning the routes from those facilities. The location-routing problems considering this issue are the subject of this thesis study. A two-level hierarchical distribution system is considered in which goods are delivered from the sources (plants) to the facilities (depots) and then from the facilities to the customers. The facilities are uncapacitated and operate within the shift times defined. The goods are to be delivered to the customers within their time windows by the vehicles that are capacitated. Both a mathematical model and a genetic algorithm based heuristic solution approach are proposed for this problem. We discuss the problem specific issues integrated with the general framework of the genetic algorithm applications. The computational studies are realized on a number of test problems. The results indicate that the genetic algorithm based heuristic gives satisfactory results compared with a sequential solution methodology.

This study deals with a municipal solid waste management system in which the strategic and tactical decisions are addressed simultaneously. In the system, the number and locations of the transfer facilities which serve to the particular solid waste pick-up points and the landfill are determined. Additionally, routing plans are constructed for the vehicles which collect the solid waste from the pick-up points by regarding the load capacity of the vehicles and shift time restrictions. We formulate this reverse logistics system as a location-routing problem with two facility layers. Mathematical models of the problem are presented, and an iterative capacitated-k-medoids clustering-based heuristic method is proposed for the solution of the problem. Also, a sequential clustering-based heuristic method is presented as a benchmark to the iterative method. Computational studies are performed for both methods on the problem instances including up to 1000 pick-up points, 5 alternative transfer facility sites, and 25 vehicles. The results obtained show that the iterative clustering-based method developed achieves considerable improvement over the sequential clustering-based method.

In this study, our aim is to determine the locations of bottle banks used in collecting recycled glass. The collection of recycled glass is done by a fleet of vehicles that visit some predetermined collection points, like restaurants and hospitals. The location of bottle banks depends on the closeness of the banks to the population zones where the recycled class is generated, and to the closeness of the banks to the predetermined collection points. A mathematical model, which combines the maximal covering problem in the presence of partial coverage and vehicle routing problem with profits, is presented. Heuristic procedures are proposed for the solution of the problem. Computational results based on generated test problems are provided. We also discuss a case study, where bottle banks are located in Yenimahalle, a district of Ankara

In this study, a metaheuristic procedure, particularly a variable neighborhood search procedure, is proposed to solve the combined location and selective traveling salesman problem in glass recycling. The collection of used glass is done by a collecting vehicle that visits a number of predefined collection centers, like restaurants and hospitals that are going to be referred to as compulsory points. Meanwhile, it is desired to locate a predetermined number of bottle banks to residential areas. The aim is to determine the location of these bottle banks and the route of the collecting vehicle so that all compulsory points and all bottle banks are visited and the maximum profit is obtained. Population zones are defined in residential areas and it is assumed that the people in a particular population zone will recycle their used glass to the closest bottle bank that fully or partially covers their zone. A Variable Neighborhood Search algorithm and its variant have been utilized for the solution of the problem. Computational experiments have been made on small and medium scale test problems, randomly generated and adapted from the literature.

Transportations are paramount for a well-functioning society and necessary to secure essential products and maintain our standard of living. These are operations and activities related to distributing packages and goods and providing services by society such as waste collection, postal services, health care, or emergency response. Transports thus affect all of us – companies, the public sector, and individuals – in our daily lives. However, the transportation sector is also one of the most polluting sectors, and in recent years the number distributed goods has increased significantly. Based on the importance of transportation and logistics services and their impact on the economy, environment, and people’s lives, it is in everyone’s interest that these transports are as efficient as possible. The supply chain's underlying infrastructure affects the efficiency and design of distribution routes. As such infrastructure is associated with substantial capital investments, it is crucial to consider the network design and the location of various facilities. The supply chain network design in this context encompasses two major problem classes; the vehicle routing problem aiming to find optimal routes to serve a set of customers by a fleet of vehicles from a central facility, and the facility location problem aiming to find the optimal location for various facilities. Moreover, these problems are interconnected as the facilities affect the demand fulfillment and the vehicle routing. Such problems are often solved with optimization techniques within the field of Operations Research, which is concerned with the mathematical modeling and algorithmic solution of decision-making problems. The objective of this thesis is to contribute to the advancement of the field of supply chain network design, by;       I.  exploring and identifying opportunities and needs for modeling and solution approaches that cope with the increased complexity of real-life industrial applications in facility location and distribution systems of goods, and     II.  to propose new modeling approaches and solution methods that cope with such opportunities and needs.  The thesis is based on three appended papers. Paper A presents a network design modeling approach for a reverse supply chain of a newly introduced product with difficulties in demand estimations. Paper B is a literature review covering multi-objective location-routing problems; these are strategic models aiming to determine the location of facilities considering aspects of tour planning and multi-stop routes. An annotated review is presented based on the application area of the various models, and an analysis of objectives and solution approaches used. Paper C introduces the Hierarchical Multi-Switch Multi-Echelon VRP, which is a new variant of the vehicle routing problem based on a real-life operational problem originating from the policies of a Nordic distribution company. A mixed-integer formulation of the problem is proposed, and its relations to other previously stated VRP variants are analyzed and discussed.

This thesis deals with stochastic location routing problem. Multiple stochas- tic and deterministic models are formulated and it is discussed that it is difficult to solve these problems via exact integer programming methods. It is necessary to develop heuristic methods to find a solution of these problems. Multiple ver- sions of these problems are formulated and their properties and possibilities how to solve them are discussed. Therefore, the brand new Blockchain metaheuristic is developed and later used for solving stochastic location routing problem ap- plied on a waste collection problem. As a part of Blockchain metaheuristic we develop the new application of Greedy algorihtm that is used for finding initial solution. The quality of the heuristic algorithm developed by us is presented in a numerical study. 1

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

Le problème de localisation-routage avec capacités (PLRC) apparaît comme un problème clé dans la conception de réseaux de distribution de marchandises. Il généralisele problème de localisation avec capacités (PLC) ainsi que le problème de tournées de véhicules à multiples dépôts (PTVMD), le premier en ajoutant des décisions liées au routage et le deuxième en ajoutant des décisions liées à la localisation des dépôts. Dans cette thèse on dévelope des outils pour résoudre le PLRC à l’aide de la programmation mathématique. Dans le chapitre 3, on introduit trois nouveaux modèles pour le PLRC basés sur des flots de véhicules et des flots de commodités, et on montre comment ceux-ci dominent, en termes de la qualité de la borne inférieure, la formulation originale à deux indices [19]. Des nouvelles inégalités valides ont été dévelopées et ajoutées aux modèles, de même que des inégalités connues. De nouveaux algorithmes de séparation ont aussi été dévelopés qui dans la plupart de cas généralisent ceux trouvés dans la litterature. Les résultats numériques montrent que ces modèles de flot sont en fait utiles pour résoudre des instances de petite à moyenne taille. Dans le chapitre 4, on présente une nouvelle méthode de génération de colonnes basée sur une formulation de partition d’ensemble. Le sous-problème consiste en un problème de plus court chemin avec capacités (PCCC). En particulier, on utilise une relaxation de ce problème dans laquelle il est possible de produire des routes avec des cycles de longueur trois ou plus. Ceci est complété par des nouvelles coupes qui permettent de réduire encore davantage le saut d’intégralité en même temps que de défavoriser l’apparition de cycles dans les routes. Ces résultats suggèrent que cette méthode fournit la meilleure méthode exacte pour le PLRC. Dans le chapitre 5, on introduit une nouvelle méthode heuristique pour le PLRC. Premièrement, on démarre une méthode randomisée de type GRASP pour trouver un premier ensemble de solutions de bonne qualité. Les solutions de cet ensemble sont alors combinées de façon à les améliorer. Finalement, on démarre une méthode de type détruir et réparer basée sur la résolution d’un nouveau modèle de localisation et réaffectation qui généralise le problème de réaffectaction [48]. / The capacitated location-routing problem (CLRP) arises as a key problem in the design of distribution networks. It generalizes both the capacitated facility location problem (CFLP) and the multiple depot vehicle routing problem (MDVRP), the first by considering additional routing decisions and the second by adding the location decision variables. In this thesis we use different mathematical programming tools to develop and specialize new models and algorithms for solving the CLRP. In Chapter 3, three new models are presented for the CLRP based on vehicle-flow and commodity-flow formulations, all of which are shown to dominate, in terms of the linear relaxation lower bound, the original two-index vehicle-flow formulation [19]. Known valid inequalities are complemented with some new ones and included using separation algorithms that in many cases generalize extisting ones found in the literature. Computational experiments suggest that flow models can be efficient for dealing with small or medium size instances of the CLRP (50 customers or less). In Chapter 4, a new branch-and-cut-and-price exact algorithm is introduced for the CLRP based on a set-partitioning formulation. The pricing problem is a shortest path problem with resource constraints (SPPRC). In particular, we consider a relaxation of such problem in which routes are allowed to contain cycles of length three or more. This is complemented with the development of new valid inequalities that are shown to be effective for closing the optimality gap as well as to restrict the appearance of cycles. Computational experience supports the fact that this method is now the best exact method for the CLRP. In Chapter 5, we introduce a new metaheuristic with the aim of finding good quality solutions in short or moderate computing times. First, a bundle of good solutions is generated with the help of a greedy randomized adaptive search procedure (GRASP). Following this, a blending procedure is applied with the aim of producing a better upper bound as a combination of all the others in the bundle. An iterative destroy-and-repair method is then applied using a location-reallocation model that generalizes the reallocation model due to de Franceschi et al. [48].

Dans les problèmes de localisation-routage classiques (LRP), il s'agit de combiner des décisions stratégiques liées aux choix des sites à ouvrir (centres de traitement) avec des décisions tactiques et opérationnelles liées à l'affectation des clients aux sites sélectionnés et a la confection des tournées associées. Cette thèse propose de nouveaux modèles de localisation-routage permettant de résoudre des problématiques issues de réseaux logistiques, devenus aujourd'hui de plus en plus complexes vu la nécessité de mutualisation de ressources pour intégrer des contraintes de développement durable et des prix de carburants qui semblent augmenter de manière irrémédiable. Plus précisément, trois aspects ont été intégrés pour généraliser les modèles LRP classiques de la littérature : 1) l'aspect pickup and delivery, 2) l'aspect multi-produits, et 3) la possibilité de visiter un ou plusieurs centres de traitement dans une tournée donnée. Nous avons étudié deux schémas logistiques, qui ont donné lieu à deux nouveaux modèles de localisation et de routage, le MPLRP-PD (LRP with multi-product and pickup and delivery), qui peut être vu comme une extension des problèmes de tournées de véhicules avec collecte et livraison, intégrant une décision tactique liée à la localisation des centres de traitement (noeud avec collecte et livraison) dans un réseau de distribution à un seul échelon, et le 2E-MPLRP-PD (Two-echelon LRP with multi-product and pickup and delivery) qui est une généralisation du LRP à deux échelons avec les contraintes citées plus-haut. Ces deux modèles ont été formalisés par des programmes linéaires en variables mixtes (MIP). Des techniques de résolution, basées sur des méthodes de type heuristique, clustering, métaheuristique, ont été proposées pour résoudre le MPLRP-PD et le 2E-MPLRP-PD. Les jeux d'essais de la littérature ont été généralisés pour tester et valider les algorithmes proposés / In the framework of Location-Routing Problem (LRP), the main idea is to combine strategic decisions related to the choice of processing centers with tactical and operational decisions related to the allocation of customers to selected processing centers and computing the associated routes. This thesis proposes a new location-routing model to solve problems which are coming from logistics networks, that became nowadays increasingly complex due to the need of resources sharing, in order to integrate the constraints of sustainable development and fuels price, which is increasing irreversibly. More precisely, three aspects have been integrated to generalize the classical LRP models already existed in the literature: 1) pickup and delivery aspect, 2) multi-product aspect, and 3) the possibility to use the processing centers as intermediate facilities in routes. We studied two logistics schemes gives us two new location-routing models: (i) MPLRP-PD (Multi-product LRP with pickup and delivery), which can be viewed as an extension of the vehicle routing problem with pick-up and delivery, including a tactical decision related to the location of processing centers (node with pick-up and delivery), and (ii) 2E-MPLRP-PD (Two-echelon multi-product LRP with pickup and delivery), which is a generalization of the two-echelon LRP. Both models were formalized by mixed integer linear programming (MIP). Solving techniques, based on heuristic methods, clustering approach and meta-heuristic techniques have been proposed to solve the MPLRP-PD and the 2E-MPLRP-PD. The benchmarks from the literature were generalized to test and to validate the proposed algorithms

In this thesis, we study the energy efficient coverage and connectivity problem in wireless sensor networks (WSNs). We try to locate heterogeneous sensors and route data generated to a base station under two conflicting objectives: minimization of network cost and maximization of network lifetime. We aim at satisfying connectivity and coverage requirements as well as sensor node and link capacity constraints. We propose mathematical formulations and use an exact solution approach to find Pareto optimal solutions for the problem. We also develop a multiobjective genetic algorithm to approximate the efficient frontier, as the exact solution approach requires long computation times. We experiment with our genetic algorithm on randomly generated problems to test how well the heuristic procedure approximates the efficient frontier. Our results show that our genetic algorithm approximates the efficient frontier well in reasonable computation times.