This thesis examines exact and heuristic approaches to solve the Ship Routing and Scheduling Problem (SRSP). The method was developed to address the problem of loading cargos for many customers using heterogeneous vessels. Constraints relate to delivery time windows imposed by customers, the time horizon by which all deliveries must be made and vessel capacities. The objective is to minimise the overall operation cost, where all customers are satisfied. Two types of routing and scheduling are considered, one called single-cargo problem, where only one cargo can be loaded into a ship, and the second type called multi-cargo problem, where multiple products can be carried on a ship to be delivered to different customers. The exact approach comprises two stages. In the first stage, a number of candidate feasible schedules is generated for each ship in the fleet. The second stage is to model the problem as a set partitioning problem (SPP) where the columns are the candidate feasible schedules obtained in the first stage. The heuristic approach uses Tabu Search (TS). Most of the TS operations, such as insert and swap moves, tenure, tabu list, intensification, and diversification are used. The results of a computational investigation are presented. Solution quality and execution time are explored with respect to problem size and parameters controlling the tabu search such as tenure and neighbourhood size. The results showed that the average of the solution gap between TS solution and SPP solution is up to 28% (for small problems) and up to 18% for large problems. However, obtaining an optimal solution requires a large amount of computer time to produce the solution compared to obtaining approximate solutions using the TS approach. The use of Tabu Search for SRSP is novel and the results indicate that it is viable approach for large problems.

In this thesis the capacitated vehicle routing problem with time windows (VRPTW) is studied, where the objective is to serve a set of geographically dispersed customers with known demands and predefined time windows at the minimum cost. It is hard to find an optimal solution for the VRPTW even if the problem size is small. Therefore, many heuristic methods are developed to obtain near optimal solutions. In this study a local search algorithm is proposed for solving the VRPTW, which consist of route construction and route improvement phases. Computational experiments are conducted with Solomon (1987)&rsquo / s and Homberger and Gehring (1999)&rsquo / s problem sets in order to test the performance of the proposed algorithm. From the computational results encouraging results are obtained in terms of solution quality.

This thesis is aimed on time frame distribution task. In the theoretical part is described the mathematical model of this task and introduced in detail two concrete heuristics: greedy look-ahead and AKRed. In the practical part of the thesis has been a real situation solved with using of sophisticated optimalization software and through own implemented heuristic. These two solution are then compared each other and applicability of each heuristics for the given real problem is evaluated.

This thesis deals with the Travelling salesman problem with time windows. The problem is that the travelling salesman must pass through each defined location exactly once and finally return to the original place for the lowest possible price. The time windows in this problem are that each place can only be visited in a given time range, or it can happen that in a certain period of time there will be no path between some places. The thesis deals with an overview of this problem and problems similar to it. It also deals with the description of various methods by which this problem can be solved. As part of this thesis, an application in the Python programming language was also created, which is used to test selected methods for finding solutions. Finally, the given experiments are evaluated and the effectiveness of the given strategies is compared.

In this thesis, the vehicle routing problem with stochastic, and time dependent, travel times is studied. The stochastic travel times are estimated from historical drive data. The variation of the drive times, as well as that of the variance, during the day was modeled.   The purpose of the thesis was to propose a method of handling the congestion related traffic impediments in an urban setting. Since the majority of times of delivery in the empirical test cases studied correlate with the time period of high traffic load, an efficient and robust handling of such traffic scenarios is of high importance.  It is shown that the stochastic models will shift the estimated arrivals to customers from the more volatile early and late extremes to more central regions of the time window. Previously delivered routes were evaluated both with the standard algorithm and the proposed stochastic algorithm. The difference between the actual drive times and the calculated drive times were analyzed by studying the correlation of the drive times between each customer in the route. It was shown that the routes of the proposed stochastic method increased this correlation. The drive times between nodes where also perturbed with a Gamma distributed noise. The results from the stochastic algorithm showed higher resilience to this disturbance than did the deterministic models. / I detta examensarbete har fordonsruttningsproblemet, VRP, med stokastiska och tidsberonds körtider behandlöats. De stokastiska körtiderna har estimerats från tidigare insamlad hasighetsdata. Modeller för körtidernas och variansernas förändring under dagen har tagits fram.   Syftet med examensarbetet var att föreslå en metod för hur påverkan på körtider av förutsägbar trafikträngsel i en urban trafikmiljö kan hanteras. Eftersom huvuddelen av alla leveranser sammanfaller med de tider på dygnet då trafikbelastning är som högst, ar är en effektiv och robust metod för att hantera sådana störningar av stor vikt. Det visas att den stokastiska modellen kommer att förflyttar ankomster från början och slutet av tidsfönstret till den mer okänsliga mittregionen. Tidigare, utförda leveranser studerades både med den ursprungliga deterministiska modellen och här framtagna stokastiska modellen. Skillnaden mellan de två analyserades genom att studera korrelationen mellan körtiderna som de beräknats av de två modellerna och de upmätta tiderna som de loggats av leveransfordonen. Det visas att korrelationen mellan körtiderna mellan de stokastiska körtiderna och de verkliga körtiderna är högre än korrelationen mellan de deterministiska körtiderna och de verkliga. Rutterna som föreslagits av den stokastiska modellen var också mer tlig mot störningar.

京都大学 / 0048 / 新制・課程博士 / 博士(工学) / 甲第19287号 / 工博第4084号 / 新制||工||1630(附属図書館) / 32289 / 京都大学大学院工学研究科都市社会工学専攻 / (主査)教授 谷口 栄一, 教授 藤井 聡, 准教授 宇野 伸宏 / 学位規則第4条第1項該当 / Doctor of Philosophy (Engineering) / Kyoto University / DFAM

京都大学 / 0048 / 新制・課程博士 / 博士(工学) / 甲第19290号 / 工博第4087号 / 新制||工||1630(附属図書館) / 32292 / 京都大学大学院工学研究科都市社会工学専攻 / (主査)教授 谷口 栄一, 准教授 宇野 伸宏, 准教授 QURESHI,Ali Gul / 学位規則第4条第1項該当 / Doctor of Philosophy (Engineering) / Kyoto University / DFAM

[pt] Este trabalho apresenta uma aplicação prática do roteamento de navios com coleta-e-entrega e janelas de tempo para o alívio de plataformas de petróleos para exportação. Especificamente para este caso, os navios aliviadores fazem o transporte do petróleo de plataformas offshore diretamente para um terminal de transbordo, onde a carga será transferida para outro navio para ser exportado. Foram propostas adaptações a um modelo de programação linear inteira mista já existente, buscando descrever as peculiaridades deste processo e facilitar a sua resolução pelo método exato. O modelo foi testado com dados realísticos de uma empresa petrolífera e pode fornecer soluções de alta qualidade para testes com períodos de até 30 dias em um tempo de processamento computacional inferior a 10 minutos, estando assim adequado ao uso na rotina do programador de navios desta empresa. / [en] This study presents a practical application of ship routing with pickup-anddelivery and time windows for offloading operations in offshore oil platforms. Specifically in this case, the shuttle tankers transport crude oil from the offshore platforms directly to an onshore terminal, where the cargo will be transferred to another vessel to be exported. Adaptations to an existing mixed-integer linear programming model are proposed to better represent this process and facilitate its resolution by the exact method. The model was tested with realistic data from an oil and gas company and it can provide high-quality solutions for tests with periods up to 30 days, in a processing time of less than 10 minutes, thus being suitable for use in the routine of the company s ship programmer.

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 thesis considers the disk scheduling problem. The problem is investigated in two types of settings: offline and online. We first adopt the traveling salesman problem with time windows in the scheduling literature for solving the offline problem. Then we develop a decision epoch scheme in which offline problems are iteratively used in solving the online problem. We perform an experimental study for our approach and two well-known disk scheduling algorithms, and compare them according to several performance criteria.