Cíle diplomové práce jsou popsat procesy probíhající v kontejnerovém přístavním terminálu, vytvořit přehled rozhodovacích problémů vznikajících v kontejnerovém přístavním terminálu z hlediska úrovně jejich typu řízení a plánování (strategické, taktické a operativní) a formulovat vybrané rozhodovací problémy a matematicky je analyzovat.

[pt] Esta dissertação tem como objetivo contribuir para o gerenciamento de frotas de grande porte, buscando uma maior rapidez e eficiência na distribuição de veículos ao longo do tempo/espaço, visando maximizar o lucro total da empresa. Problemas de gerenciamento de frotas dinâmicas são normalmente formulados como uma rede dinâmica, mas há uma grande dificuldade ao se trabalhar com problemas desse tipo, especialmente quando se busca uma solução sobre um horizonte de planejamento longo. Visando contornar essa dificuldade, Powell & Carvalho (1998) desenvolveram uma nova abordagem para problemas desse tipo: a Logistics Queuing Network (LQN). A utilização do algoritmo LQN na prática (através de um software) permitiria uma tomada de decisão mais rápida e eficiente, sendo bastante útil, em especial para empresas de transportes. Assim, implementou-se o algoritmo LQN, através do desenvolvimento de um software para o gerenciamento de frotas de grande porte, por meio do qual podese constatar o potencial de aplicação desse algoritmo. / [en] The objective of this dissertation is to contribute to the large-scale fleet management, looking for a greater efficiency and speed in vehicle distribution over time and space, while maximizing total profit. Dynamic fleet management problems are normally formulated as a dynamic network, but it`s really difficult to work with problems of this class, especially when we look for a solution over a large planning horizon. In order to overcome this problem, Powell & Carvalho (1998) developed a new formulation for these problems: the Logistics Queuing Network. The use of its algorithm in real problems (using a software) would allow quickly and more efficient decisions in transports, being really useful especially for transports enterprises. For this reason, the algorithm LQN was implemented, through the development of a software for the large-scale fleet management, so we could verify the potential application of this algorithm.

SJ AB is the leading railway operating company in Sweden and is owned by the Swedish government. In Hagalund train depot (HGL) SJ AB, as well as some of SJ AB:s competitors, run their operational maintenance. The HGL property is owned by Jernhusen but some of the infrastructure is owned by Trafikverket; the Swedish transport administration. The number of depot tracks available for SJ AB have been reduced over time, as competition is increasing. SJ AB constructs their own track plans, i.e. decide the arrival and departure track for each train turnaround in the depot. These track plans are currently made by a so called production planner in the planning system RPS. In RPS the planners base their decisions on common sence, as there is no optimising function in the system. The mathematical problem associated with this task is called the Track Assignment Problem (TAP), which is a well-known problem within railway related research. This report presents an optimisation program - TAP Solver (TAPS) - that takes information from RPS and then generates an optimised solution visualised as a track plan. The user is given the opportunity to direct the solution through parameters in a weight matrix in Excel. TAPS is created to make the process of constructing a track plan both faster and easier. Our results show that TAPS is able to find the optimal 24 hour track plan within a few minutes.

京都大学 / 0048 / 新制・課程博士 / 博士(情報学) / 甲第18530号 / 情博第534号 / 新制||情||95(附属図書館) / 31416 / 京都大学大学院情報学研究科知能情報学専攻 / (主査)教授 岡部 寿男, 教授 松山 隆司, 教授 阿久津 達也 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

No description available.

Redundancy Allocation Problem (RAP) is a well known mathematical problem for modeling series-parallel systems. It is a combinatorial optimization problem which focuses on determining an optimal assignment of components in a system design. Due to the diverse possible selection of components, the RAP is proved to be NP-hard. Therefore, many algorithms, especially heuristic algorithms were proposed and implemented in the past several decades, committed to provide innovative methods or better solutions. In recent years, multi-agent system (MAS) is proposed for modeling complex systems and solving large scale problems. It is a relatively new programming concept with the ability of self-organizing, self-adaptive, autonomous administrating, etc. These features of MAS inspire us to look at the RAP from another point of view. An RAP can be divided into multiple smaller problems that are solved by multiple agents. The agents can collaboratively solve optimal RAP solutions quickly and efficiently. In this research, we proposed to solve RAP using MAS. This novel approach, to the best of our knowledge, has not been proposed before, although multi-agent approaches have been widely used for solving other large and complex nonlinear problems. To demonstrate that, we analyzed and evaluated four benchmark RAP problems in the literature. From the results, the MAS approach is shown as an effective and extendable method for solving the RAP problems. / Electrical and Computer Engineering

Motivated by problems in logistics, image recognition, and statistics, we consider the server allocation problem. In this problem, we are given $k$ servers (with capacities) and $n$ requests, which are points in a metric space. A server serves a request by moving to the request location, and the goal is to serve all requests while minimizing the total movement of servers, subject to the constraint that the number of requests served by a server cannot exceed its capacity. When the server capacity is $1$, and for the Euclidean metric, the problem reduces to the Euclidean bipartite matching problem. When the capacity is $infty$, suppose we are also provided with the order in which requests are to be served, the problem is the $k$-first come first served routing problem. We also consider a generalization of the $k$-first come first served routing problem to the taxi allocation problem, where each request is associated with a pickup location, dropoff location, and pickup time, and the server's velocity is also given as input. We present new algorithms for the Euclidean bipartite matching problem, showing improvements over existing algorithms. In particular, for two point sets $A, B subset mathbb{R}^d$ with $|A| = |B| = n$ and dimension $d > 1$ being constant, we developed: begin{itemize} item A faster algorithm that computes an $varepsilon$-approximate minimum-cost perfect matching in $O(n(varepsilon^{-O(d^3)}loglog n + varepsilon^{-O(d)}log^4 nlog^5log n))$ time. This is an improvement over previous algorithms, which took $n(varepsilon^{-1}log n)^{Omega(d)}$ time. item An algorithm that boosts the accuracy of any $varepsilon$-additive approximation algorithm, achieving an expected additive error of $min{varepsilon, (dloglog n)w^*}$ from the optimal matching cost $w^*$ in $O(T(n, varepsilon/d)loglog n)$ time, where $T(n, varepsilon)$ is the time complexity of any given $eps$-additive approximation algorithm. end{itemize} For the $k$-first come first served routing problem, we present the following results. begin{itemize} item The online version of the $k$-first come first served routing problem is the celebrated $k$-server problem. The best-known online algorithm for this problem is the Work Function algorithm. We present a new implementation of the work function algorithm, where processing the $i$th request takes $O((i+k)^2)$ time, improving on the previous methods that take $Omega(k(i+k)^2)$ time. item For the offline setting, we show that the $k$-first come first served routing problem and the taxi allocation problem can be reduced to the minimum-cost bipartite matching problem. Using this reduction, begin{itemize} item we develop a time-based divide-and-conquer algorithm to obtain an optimal solution in $tilde{O}(kn^2)$ time, which can be further improved to $tilde{O}(kn)$ when the requests and servers are in two-dimensional Euclidean space, and, item we apply a recently presented geometric divide-and-conquer algorithm to obtain an optimal solution for the taxi routing problem in a two-dimensional Euclidean space. As a result, we obtain significant empirical performance improvements for the taxi allocation problem in a two-dimensional space where the cost of moving from one location to another is lower bounded by the Euclidean cost. end{itemize} end{itemize} / Doctor of Philosophy / In the server allocation problem, we are given n requests and k servers, both as points in a space. A server can serve a request by moving to the request location, and each request can be served by exactly one server. The objective is to optimize the allocation of servers to requests such that the total distance traveled by the servers is minimized. In this thesis, we present efficient algorithms for three specific problems in the server allocation problem framework. First, we consider the case when the servers are restricted to serving up to one request each. This problem reduces to the well-known minimum cost maximum cardinality bipartite matching problem. When the underlying distance is Euclidean, this problem is called the Euclidean bipartite matching problem. We present two efficient algorithms that improve the state-of-the-art for the Euclidean bipartite matching problem. Second, we consider the case when the servers can handle multiple requests. Assuming the requests are given as ordered sequences, a server can serve a subsequence of the request sequence. We devise two efficient algorithms for this problem and show empirical performance improvements on the New York Taxi data set. Third, we consider the scenario when the requests appear in an online fashion such that on the arrival of each request, a server must be allocated to it immediately and irrevocably. This problem is the celebrated k-server problem. The work function algorithm is an online algorithm that solves the k-server problem with the best-known competitive ratio. We present a new, faster implementation of the work function algorithm.

The research is a study of the efficiency and robustness of genetic algorithm to instances of both discrete and continuous global optimization problems. We developed genetic algorithm based heuristics to find the global minimum to problem instances considered. In the discrete category, we considered two instances of real-world space allocation problems that arose from an academic environment in a developing country. These are the university timetabling problem and hostel space allocation problem. University timetabling represents a difficult optimization problem and finding a high quality solution is a challenging task. Many approaches, based on instances from developed countries, have been reported in the literature. However, most developing countries are yet to appreciate the deployment of heuristics and metaheuristics in handling the timetabling problem. We therefore worked on an instance from a university in Nigeria to show the feasibility and efficiency of heuristic method to the timetabling problem. We adopt a simplified bottom up approach in which timetable are build around departments. Thus a small portion of real data was used for experimental testing purposes. As with similar baseline studies in literature, we employ genetic algorithm to solve this instance and show that efficient solutions that meet stated constraints can be obtained with the metaheuristics. This thesis further focuses on an instance of university space allocation problem, namely the hostel space allocation problem. This is a new instance of the space allocation problems that has not been studied by metaheuristic researchers to the best of our knowledge. The problem aims at the allocation of categories of students into available hostel space. This must be done without violating any hard constraints but satisfying as many soft constraints as possible and ensuring optimum space utilization. We identified some issues in the problem that helped to adapt metaheuristic approach to solve it. The problem is multi-stage and highly constrained. We first highlight an initial investigation based on genetic algorithm adapted to find a good solution within the search space of the hostel space allocation problem. Some ideas are introduced to increase the overall performance of initial results based on instance of the problem from our case study. Computational results obtained are reported to demonstrate the effectiveness of the solution approaches employed. Sensitivity analysis was conducted on the genetic algorithm for the two SAPs considered to determine the best parameter values that consistently give good solutions. We noted that the genetic algorithms perform well specially, when repair strategies are incorporated. This thesis pioneers the application of metaheuristics to solve the hostel space allocation problem. It provides a baseline study of the problem based on genetic algorithms with associated test data sets. We report the best known results for the test instances. It is a known fact that many real-life problems are formulated as global optimization problems with continuous variables. On the continuous global optimization category therefore, we focus on improving the efficiency and reliability of real coded genetic algorithm for solving unconstrained global optimization, mainly through hybridization with exploratory features. Hybridization has widely been recognized as one of the most attractive approach to solving unconstrained global optimization. Literatures have shown that hybridization helps component heuristics to taking advantage of their individual strengths while avoiding their weaknesses. We therefore derived three modified forms of real coded genetic algorithm by hybridizing the standard real-coded genetic algorithm with pattern search and vector projection. These are combined to form three new algorithms namely, RCGA-PS, RCGA-P, and RCGA-PS-P. The hybridization strategy used and results obtained are reported and compared with the standard real-coded genetic algorithm. Experimental studies show that all the modified algorithms perform better than the original algorithm.

The p-median problem is often used to locate p service centers by minimizing their distances to a geographically distributed demand (n). The optimal locations are sensitive to geographical context such as road network and demand points especially when they are asymmetrically distributed in the plane. Most studies focus on evaluating performances of the p-median model when p and n vary. To our knowledge this is not a very well-studied problem when the road network is alternated especially when it is applied in a real world context. The aim in this study is to analyze how the optimal location solutions vary, using the p-median model, when the density in the road network is alternated. The investigation is conducted by the means of a case study in a region in Sweden with an asymmetrically distributed population (15,000 weighted demand points), Dalecarlia. To locate 5 to 50 service centers we use the national transport administrations official road network (NVDB). The road network consists of 1.5 million nodes. To find the optimal location we start with 500 candidate nodes in the network and increase the number of candidate nodes in steps up to 67,000. To find the optimal solution we use a simulated annealing algorithm with adaptive tuning of the temperature. The results show that there is a limited improvement in the optimal solutions when nodes in the road network increase and p is low. When p is high the improvements are larger. The results also show that choice of the best network depends on p. The larger p the larger density of the network is needed.

In this study we have conducted research on how to optimize inventory management within logistics. The focus in this study is to examine the picking rounds, the reason for this is because it is the most time consuming and expensive part within a warehouse. Is it possible to minimize the handling time to create efficient picking rounds? As a part of the research project AI has been investigated as well. If it is possible with help of AI, create a streamlining of current warehouse logistics. The purpose of this report is to investigate how to minimize the distance in picking rounds for efficient warehouse management. To be able to fulfil the purpose of the report research questions where conducted. The methodology that was chosen at first was traditional data collection. With the help of other studies conducted in this area we started to collect information. To be able to compare this information to the chosen company Care of Carl a case study was performed. A case study on the current situation at Care of Carl, and what the current optimization is based on. With the help of these two methods a result emerged. The result that was conducted by this study is that placement and categorization of products as well as route planning has a significant role when streamlining the picking process and minimizing the picking process. To store items in a warehouse the most suitable option is to use a free item placement, or storage out of sale frequency. But important to acknowledge is that it requires support systems to make this storage possible. When categorizing articles, it is crucial to combine this with a suiting picking method. In the case study, combining ABC categorization with zone picking was a possible solution. In general, it might be a good idea to invest in AI to use the picking position principle. With AI it is possible to analyse more complex data such as customer patterns and if this implementation succeeds it can lead to great advantages within a warehouse and the picking processes. The traveling distance constitutes most of the total picking time, it is important to have a route method that works with how you have chosen to place the items. This study shows that the optimal routing method is the one to use. This study showed that there are a lot of different strategies and methods on the current market. According to the case study Care of Carl can make big savings by changing strategies and methods. The reason why is because they have been reactive when investing in IT support systems. But in general, if a company wants to meet the current increasing requirements according to the globalization and the continuous changes within logistics operations, AI is the next step. The methods that are currently used are not sufficient, with the help of AI there is room for improvements within product allocation and route planning. / I denna studie har det undersökts hur man kan optimera lagerhanteringen inom logistik. Fokus har varit att undersöka plockrundorna, då det är den mest tidskrävande och kostsamma delen inom ett lager. Är det möjligt att minimera hanteringstiden och därmed effektivisera plockrundorna? Studien har även varit en del av ett forskningsprojekt där man har undersökt om det med hjälp av AI är möjligt att skapa en effektivisering av lagerhantering. Syftet med denna rapport är att undersöka hur man minimerar avståndet i plockrundorna för att effektivisera lagerhanteringen. För att kunna uppfylla syftet med rapporten utformades det forskningsfrågor kopplat till syftet. Traditionell datainsamling var den metod som användes för att komma i gång med studien. Den teoretiska referensramen som skapades i denna rapport var utifrån andra studier som genomförts inom detta område, men även utifrån att kunna besvara de forskningsfrågor som skapats. Det genomfördes även en fallstudie på företaget Care of Carl, med en nulägesbeskrivning samt en förklaring gällande hur deras nuvarande optimering tagits fram. För att kunna besvara syftet med rapporten och forskningsfrågorna jämfördes den teoretiska referensramen med den fallstudien som genomförts i samband med denna studie. Resultatet som framkom under studien var att placering och kategorisering av produkter såväl som ruttplanering har en avgörande roll gällande effektivisering av plockprocessen i ett lager. Gällande inlagringsmetod är det lämpligast att använda sig av flytande artikelplacering alternativt lagring utifrån försäljningsfrekvens. Vad som är viktigt att nämna är att båda metoder kräver ett stödsystem för att kunna implementeras. Gällande kategorisering av artiklar är det viktigt att kombinera detta med en passande plockmetod. I fallstudien var en möjlig lösning att kombinera ABC-kategorisering med zonplockning. Generellt sätt är AI en framtida värd investering då man kan använda sig av plockpositionsprincipen. AI möjliggör analysering av mer komplexa data som kundmönster och om denna implementering lyckas kan det leda till stora fördelar inom ett lager och för plockprocessen. Det är även viktigt att ha en ruttmetod som fungerar ihop med den placeringsmetod man använt sig av, då gångtiden och gångavståndet är det som utgör det mesta av den totala plocktiden. Denna studie visar att den optimala ruttmetoden är den som bör användas, och detta kräver en investering i ett stödsystem. Denna studie visade att det för tillfället finns många olika strategier och metoder på marknaden idag. Enligt fallstudien kan Care of Carl göra stora besparingar bara genom att ändra sina strategier och metoder. Orsaken är att de har varit reaktiva vid investeringav IT-stödsystem. Generellt sätt, om ett företag vill uppfylla de ökande kraven som finns till följd av globaliseringen och de kontinuerliga förändringarna inom logistikverksamheten, är AI nästa steg att ta. Metoderna som för närvarande används är inte tillräckliga och med hjälp av AI finns det möjlighet för förbättringar inom produktallokering och ruttplanering.