In this paper, we introduce two algorithms to address the two-echelon capacitated location-routing problem (2E-CLRP). We introduce a branch-and-cut algorithm based on the solution of a new two-index vehicle-flow formulation, which is strengthened with several families of valid inequalities. We also propose an adaptive large-neighbourhood search (ALNS) meta-heuristic with the objective of finding good-quality solutions quickly. The computational results on a large set of instances from the literature show that the ALNS outperforms existing heuristics. Furthermore, the branch-and-cut method provides tight lower bounds and is able to solve small- and medium-size instances to optimality within reasonable computing times.

Workforce scheduling is widely used within most industries. A well-outlined and efficient schedule gives cost savings, such as reduced number of overtime hours, increases overall utilization, and facilitates meeting demands. A large and complex schedule, for example, scheduling of a health care workforce, needs to consider many parameters when constructed; it is essential to account for all critical constraints regarding who can dispense a particular medicine, laws restricting the health care system, etcetera. This thesis evaluates two different methods for implementing a workforce scheduling system for one of Linköping’s most well-known restaurants and bars for students, using mixed integer programming and heuristics. Flamman Pub & Disco recruits new employees prior to every semester. Usually, the workforce consists of around 100 employees, and the vast majority of them work either in the bar or in the kitchen. Historically, the scheduling process has been handled manually using Excel. This does, however, take up much time for the operations manager, something considered frowned upon. Therefore, this thesis suggests an automated scheme for future scheduling processes. Because Flamman is a student organization, they do not hold the capital to invest in expensive licensed optimization software. However, literature studies have shown that heuristics such as large neighborhood search can generate sufficient performance, and therefore the investigation of free-of-charge software using a heuristic approach is conducted. The constructed framework uses a mixed integer programming model, which also lays the cornerstone for the two heuristics: a reverse constructive heuristic and a large neighborhood search. The results retrieved from the analysis prove that a heuristic can be a helpful tool for upcoming recruitment periods. There are, however, recommended areas for improvement regarding the current state of the heuristic.

This thesis aims to implement a combination of Linear Programming Column Generation and a Large Neighbourhood Search heuristic to solve scheduling problems. The resulting method is named Integer Programming Column Search (IPCS). For computational evaluation, the IPCS method is applied to the problem Prize-Collecting Job Sequencing with One Common and Multiple Secondary Resources generalised to parallel identical machines. The interest of combining exact procedures with heuristic approaches is quickly growing since scheduling problems have many and complex real-world applications. Most of these problems are NP-hard and therefore very challenging to solve. By using a combination of heuristic strategies and exact procedures, it can be possible to find high-quality solutions to such problems within an acceptable time horizon. The IPCS method uses a greedy integer programming column generating problem introduced in a previous work. This problem is designed to generate columns that are useful in near-optimal integer solutions. A difference to previously introduced method is that we here build a master problem, an Integer Programming Column Search Master (IPCS-Master). This is used to update the dual solution that is provided to the greedy integer programming column generating problem. The computational performance of the IPCS method is evaluated on instances with 60, 70, 80, 90 and 100 jobs. The result shows that the combined design encourage the generation of columns that benefit the search of near-optimal integer solutions. The introduction of an IPCS-Master, which is used to update the dual variable values, generally leads to fewer pricing problem iterations than when no master problem is used.

In this paper, we study a rich vehicle routing problem incorporating various complexities found in real-life applications. The General Vehicle Routing Problem (GVRP) is a combined load acceptance and generalised vehicle routing problem. Among the real-life requirements are time window restrictions, a heterogeneous vehicle fleet with different travel times, travel costs and capacity, multi-dimensional capacity constraints, order/vehicle compatibility constraints, orders with multiple pickup, delivery and service locations, different start and end locations for vehicles, and route restrictions for vehicles. The GVRP is highly constrained and the search space is likely to contain many solutions such that it is impossible to go from one solution to another using a single neighbourhood structure. Therefore, we propose iterative improvement approaches based on the idea of changing the neighbourhood structure during the search.

The objective of this thesis is to model and solve the problem of placing thermal imaging camera for monitoring piles of combustible bio-fuels. The cameras, of different models, can be mounted at discrete heights on poles at fixed positions and at discrete angles, and one seeks camera model and mounting combinations that monitor as much of the piles as possible to as low cost as possible. Since monitoring all piles may not be possible or desired, due to budget or customer constrains, the solution to the problem is a set of compromises between coverage and cost. We denote such a set of compromises a frontier. In the first part of the thesis a way of modelling the problem is presented. The model uses a discrete formulation where the area to monitor is partitioned into a grid of cells. Further, a pool of candidate camera placements is formed, containing all combinations of camera models and mounting positions. For each camera in this pool, all cells monitored are deduced using ray-casting. Finally, an optimization model is formulated, based on the pool of candidate cameras and their monitoring of the grid. The optimization model has the two objectives of minimizing the cost while maximizing the number of covered cells. In the second part, a number of heuristic optimization algorithms to solve the problem is presented: Greedy Search, Random Greedy Search, Fear Search, Unique Search, Meta-RaPS and Weighted Linear Neighbourhood Search. The performance of these heuristics is evaluated on a couple of test cases from existing real world depots and a few artificial test instances. Evaluation is made by comparing the solution frontiers using various result metrics and graphs. Whenever practically possible, frontiers containing all optimal cost and coverage combinations are calculated using a state-of-the-art solver. Our findings indicate that for the artificial test instances, the state-of-the-art solver is unmatched in solution quality and uses similar execution time as the heuristics. Among the heuristics, Fear Search and Greedy Search were the strongest performing. For the smaller real world instances, the state-of-the-art solver was still unmatched in terms of solution quality, but generating the frontiers in this way was fairly time consuming. By generating the frontiers using Greedy Search or Random Greedy Search we obtained solutions of similar quality as the state-of-the-art solver up to 70-80% coverage using one hundredth and one tenth of the time, respectively. For the larger real world problem instances, generating the frontier using the state-of-the-art solver was extremely time consuming and thus sometimes impracticable. Hence the use of heuristics is often necessary. As for the smaller instances, Greedy Search and Random Greedy Search generated the frontiers with the best quality. Often even better full coverage solutions could be found by the more time consuming Fear Search or Unique Search. / Syftet med detta examensarbete är att modellera och lösa kameraplaceringsproblemet då IR-kameror ska användas för brandövervakning av fastbränslehögar. Problemet består i att givet ett antal kamera modeller och monteringsstolpar bestämma de kombinationer av placeringar och modeller sådana att övervakningen av högarna är maximal, för alla möjliga kostnadsnivåer. I den första delen av examensarbetet presenteras en modell för detta kameraplaceringsproblem. Modellen använder sig av en diskret formulering, där området om ska övervaras är representerad av ett rutnät. De möjliga kameravalen beskrivas med en diskret mängd av möjliga kameraplaceringar. För att utröna vilka celler inom rutnätet som en kameraplacering övervakar används metoden ray-casting. Utifrån mängden av möjliga kameraplaceringar kan en optimeringsmodell med två målfunktioner formuleras. Målet i den första målfunktionen är att minimera kostnaden för övervakningen och i den andra att maximera storleken på det övervakade området. Utgående från denna modell presenteras därefter ett antal algoritmer för att lösa modellen. Dessa är: Greedy Search, Random Greedy Search, Fear Search, Unique Search, Meta-RaPS och Weighted Linear Neighbourhood Search. Algoritmerna utvärderas på två konstgjorda testproblem och ett antal problem från verkliga fastbränslelager. Utvärderingen baseras på lösningsfronter (grafer över de icke-dominerade lösningarna med de bästa kombinationerna av kostnad och täckning) samt ett antal resultatmått som tid, lägsta kostnad för lösning med full täckning, etc... Vid utvärderingen av resultaten framkom att för de konstgjorda testinstanserna presterade ingen av heuristikerna jämförbart med en standardlösare, varken i termer av kvalitén på lösningarna eller med hänsyn tagen till tidsåtgången. De heuristiker som presterade bäst på dessa problem var framförallt Fear Search och Greedy Search. Även på de mindre probleminstanserna från existerande fastbränslelager hittade standardlösaren optimala lösningsfronter och en lösning med full täckning, men tidsåtgången var här flera gånger större jämfört med vissa av heuristikerna. På en hundra- respektive en tiondel av tiden kan Greedy Search eller Random Greedy Search heuristikerna finna en lösningsfront som är jämförbar med standardlösare, upp till 70-80% täckning. För de största probleminstanserna är tidsåtgången vid användning av standardlösare så pass stor att det i många fall är praktiskt svårt att lösa problemen, både för att generera fronten och att hitta en lösning med full täckning. I dessa fall är heuristiker oftast de enda möjliga alternativen. Vi fann att Greedy Search och Random Greedy Search var de heuristiker som, liksom för de mindre probleminstanserna, genererade de bästa lösningsfronterna. Ofta kunde dock en bättre lösning för full täckning hittas med hjälp av Fear Search eller Unique Search.

La logistique collaborative est récemment devenue un élément important pour beaucoup d'entreprises afin d'améliorer l'efficacité de leur chaîne logistique. Dans cette thèse, nous étudions les possibilités offertes par les problèmes de collectes et livraisons pour améliorer les performances des chaînes logistiques grâce au transport collaboratif. La thèse est inscrite dans un projet européen nommé SCALE (Step Change in Agri-food Logistics Ecosystem). Dans un premier temps, deux métaheuristiques sont proposées et étudiées pour résoudre le problème de collectes et livraisons avec transbordements. Celles-ci sont comparées aux travaux de la littérature et permettent d’améliorer les résultats sur certaines instances. Dans un deuxième temps, un modèle pour un problème de collectes et livraisons (PDVRP) est proposé. Celui-ci est utilisé pour étudier les bénéfices de la collaboration sur le transport. Il est appliqué sur des données générées aléatoirement et sur des données réelles issues du projet SCALE. Enfin troisièmement, un modèle pour un PDVRP particulier est présenté. Dans ce modèle, les marchandises doivent passer par exactement deux points de transbordement entre les points de collecte et les points de livraison. Ce problème est inspiré d'une seconde étude de cas réalisée dans le cadre du projet SCALE. Ceci permet de mettre en évidence l’intérêt de la collaboration et du transbordement dans le domaine du transport de marchandises. / Collaborative logistics have become recently an important element for many companies to improve their supply chains efficiency. In this thesis, we study pickup and delivery problems to improve supply chains efficiency thanks to collaborative transportation. The thesis was part of the European project SCALE (Step Change in Agri-food Logistics Ecosystem). Firstly, two metaheuristics are proposed and studied to solve the Pickup and Delivery Problem with Transshipments. These metaheuristics are compared with literature works and the results of several instances are improved. Secondly, a mathematical model for a pickup and delivery problem (PDVRP) is proposed. This model is used to study the benefits of collaboration on transportation. It is applied on random data and on a case study from SCALE with real data. Finally, a model for a particular PDVRP is presented. In this model, the shipments have to cross exactly two transshipments nodes between their pickup and delivery points. This problem is inspired by a second case study made during the project SCALE. This allows to highlight the importance of collaboration and transshipment in the field of goods transportations.

There are different transportations in the city logistics (e.g., passengers, freights, and wastes), which are handled respectively by single-purpose vehicles (SVs) of the corresponding type. The multi-purpose vehicle (MV) is a future concept whose load modules can be changed for different urban transportations. MVs enable the sequential sharing of different mobilities, thus theoretically improving the efficacy of the city logistics by higher utilization of vehicles. A variant model of the Pick-up and Delivery Problem with Time Windows is established to describe the sequential sharing problem considering both MVs and SVs with the features of multiple depots, partial recharging strategies, and fleet sizing. In the problem, MVs can change their load modules for all types of objects carried by SVs. An adaptive large neighborhood algorithm (ALNS) is developed with new mechanisms for MVs. The proposed ALNS is tested by 15 artificial data cases and compared with the MIP solver. The results show the proposed ALNS is time-effective and validated to find good solutions. / Det finns olika transporter i stadslogistiken (t.ex. passagerare, gods och avfall), som hanteras av enskilda fordon (SV) av motsvarande typ. Multifunktionsfordonet (MV) är ett framtida koncept vars lastmoduler kan ändras för olika stadstransporter. MV möjliggör sekventiell delning av olika mobiliteter, vilket på ett teoretiskt sätt förbättrar stadslogistikens effektivitet genom högre användning av fordon. En variantmodell av Pick-up and Delivery Problem with Time Windows är etablerad för att beskriva det sekventiella delningsproblemet med beaktande av både MV och SV med funktionerna i flera depåer, partiella laddningsstrategier och flottans storlek. I problemet kan MV: er ändra sina belastningsmoduler för alla typer av objekt som bärs av SV: er. En adaptiv stor stadsdelalgoritm (ALNS) har utvecklats med nya mekanismer för MV. Den föreslagna ALNS testas av 15 artificiella datafall och jämförs med MIP-lösaren. Resultaten visar att det föreslagna ALNS är tidseffektivt och validerat för att hitta bra lösningar.