Heuristics for a facility location problem with a quadratic objective function

Facility location problems are an important set of problems within the field of optimisation. These problems consider which facilities to open out of a set of possible facilities and how to assign users to the open facilities. Most of the facility location problems studied have a linear objective. In this thesis, we consider a facility location...

Algorithms for partially robust team formation

In one of its simplest forms, Team Formation involves deploying the least expensive team of agents while covering a set of skills. While current algorithms are reasonably successful in computing the best teams, the resilience to change of such solutions remains an important concern: Once a team has been formed, some of the agents considered...

Bi-sided facility location problems: an efficient algorithm for k-centre, k-median, and travelling salesman problems

This study introduces a general framework, called Bi-sided facility location, for a wide range of problems in the area of combined facility location and routing problems such as locating test centres and designing the network of supermarkets. It is based on a multi-objective optimisation model to enhance the service quality which the clients...

A facility location model for uncrewed surface vessels in the maritime survey industry: The impact of remote and autonomous operations on logistical decision-making regarding harbor facility locations

The maritime industry is preparing for a future where human presence is no longer required on board of ships. This will revolutionize the global execution of maritime operations and consequentially introduce unprecedented challenges to the corresponding logistics. This paper presents a non-standard facility location problem (FLP) that arises in...

Finding the optimal set of parking locations for maintenance trains in the Dutch railway network: An optimisation approach using a combination of discrete-event simulation and simulated annealing

The Dutch railway system is subject to maintenance, which is carried out by a group of rail contractors who need parking space to park and prepare trains in between projects. The objective of this study is to minimise the total costs as a result of the distance travelled by maintenance trains and the preservation of the included parking...

Exploring the transport efficiency for different types of logistics facilities

The synergic effect between the spatial organisation and freight transport is crucial for transport planners to understand. It will help in improving freight transport planning. The absence of freight data has made such a study difficult. This research aims to understand the relation between spatial organisation and freight transportation by...

Waste Collection in Amsterdam Centrum Using Autonomous Vessels: Optimization of container type selection and location for household waste collection in Amsterdam Centrum with Autonomous Vessels (Roboats)

This research strives to contribute to the solution of the Amsterdam waste problem by improving the location determination of the various container types within the Centrum area. One of the modalities is an autonomous surface vehicle (ASV), and in this case, a Roboat. Since it is not possible to assign all demand to one modality, also trucks and...

Informed decision-making on healthcare facility locations in expanding refugee camps: Researching the interplay between healthcare facility locations and refugee settlement behavior

In 2018, the number of forcibly displaced people all over the world was higher than ever before. More than a third of this group are refugees, often living in refugee camps.  NGOs try to deliver all necessary aid to these camps, while facing limited access and resources. Therefore, they want to optimize the results of the aid they deliver. The...

Supporting group decision makers to locate temporary relief distribution centres after sudden-onset disasters: A case study of the 2015 Nepal earthquake

In the humanitarian response, multiple decision-makers (DMs) need to collaborate in various problems, such as locating temporary relief distribution centres (RDCs). Several studies have argued that maximising demand coverage, reducing logistics costs and minimising response time are among the critical objectives when locating RDCs after a...

Bioethanol facility location selection using best-worst method

One of the major factors in the success of renewable energy is finding a proper location for production facilities. At a national level, different parts of a country (e.g. provinces) can be seen as alternatives that can be assessed based on a set of criteria, and ranking them to identify the best location. The focus in this paper is on...

Forecast-driven facility location model for pre-positioning relief goods in preparation for strong typhoons

Weather forecast agencies periodically provide information on potential typhoon behavior from its formation to dissipation. This information can be used to pre-position relief goods in areas that are potentially affected by a strong incoming typhoon. The uncertainty of the typhoon behavior with respect to a point location decreases over time,...

Comparing population and incident data for optimal air ambulance base locations in Norway

Background: Helicopter emergency medical services are important in many health care systems. Norway has a nationwide physician manned air ambulance service servicing a country with large geographical variations in population density and incident frequencies. The aim of the study was to compare optimal air ambulance base locations using both...

Strengthening the integrality gap for the capacitated facility location problem with LP-based rounding algorithms

This thesis studies the capacitated facility location problem, in which all clients have unit demand and all facilities have integral capacity. A linear relaxation is researched, with corresponding integrality gap bounded by a constant. Recently, such a linear relaxation has been found and proven using an LP-bounding algorithm. The formulation...

Improved Approximation Algorithm for k-level Uncapacitated Facility Location Problem (with Penalties)

We study the k-level uncapacitated facility location problem (k-level UFL) in which clients need to be connected with paths crossing open facilities of k types (levels). In this paper we first propose an approximation algorithm that for any constant k, in polynomial time, delivers solutions of cost at most α_k times OPT, where α<sub...

Adapting the Chudak-Shmoys approximation algorithm to the k-level uncapacitated facility location problem

An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem

We obtain a 1.5-approximation algorithm for the metric uncapacitated facility location (UFL) problem, which improves on the previously best known 1.52-approximation algorithm by Mahdian, Ye, and Zhang. Note that the approximability lower bound by Guha and Khuller is 1.463 . . . . An algorithm is a (?f ,?c)-approximation algorithm if the solution...

"Capacitated Facility Location": De kracht van de surrogaat-knapzakrelaxatie (The Strength of the SUrrogate Knapsack Relaxation)

Deze scriptie laat het onderzoek zien naar de kracht van de surrogaat-knapzakrelaxatie. Deze relaxatie kan gebruikt worden bij het oplossen van het Capacitated Facility Location probleem en blijkt zeer informatief te zijn t.o.v. de LP-relaxatie.