This thesis aims to find an optimal route taken by workers reading gas-meters. The text consists of three parts: the collection of necessary data, the selection and subsequent modification of the heuristic method and the calculation itself. Two techniques of data collection are applied: purchase from a specialised company and calculation based on geographical coordinates. These techniques are compared in the end. The method of the nearest neighbour is used for calculation, after being modified for this particular case. The calculation itself is done by the program named Gas-meters, which was created for the purpose of this thesis. The route potentially used by the gas company workers is then the result of the thesis. Furthermore, the thesis presents specific corporate savings possibly brought by using the presented program.

The thesis describes the principles of dynamic programming and it's application to concrete problems. (The travelling salesman problem, the knapsack problem, the shortest path priblem,the set covering problem.)

The traveling salesman problem (TSP) has become a classic in the field of combinatorial optimization. Attracting computer scientists and mathematicians, the problem involves finding a minimum cost Hamiltonian cycle in a weighted graph.

The diploma thesis focuses on the use of genetic algorithms for tasks related to the travelling salesman problem. Based on theoretical knowledge and problem analysis a proposal of the solution is provided. This creates a daily route plan for service technicians with regard to constraints. The case study shows that the proposed solution in comparison with manual scheduling by experience enables to reduce transportation costs.

This work deals with traveling salesman problem (TSP) and examines it’s possibilities to use in business. It is about the optimization of the travel cost, saving time and unnecessary mileage. Part of the work is a program with a GUI written in program MATLAB. Program uses neural networks to calculate the most effective path between places, where the trader has to reach. It’s possible to use the algorithm for many purposes, e.g. distribution of goods, store management, planning of PCBs or rescue services. Program communicates with the Google Maps API server, which provides the actual information of the path.

<p> In this thesis, we investigate and characterize policies for task allocation to teams of agents in settings with heterogeneity and risk. We first consider a scenario consisting of a set of heterogeneous mobile agents located at a base (or depot), and a set of tasks dispersed over a geographic area. The agents are partitioned into different types. The tasks are partitioned into specialized tasks that can only be done by agents of a certain type, and generic tasks that can be done by any agent. The distances between every pair of tasks are specified and satisfy the triangle inequality. Given this scenario, we address the problem of allocating these tasks among the available agents (subject to type compatibility constraints) while minimizing the maximum travel cost for any agent. We first look at the Heterogeneous Agent Cycle Problem (HACP) where agents start at a common base (or depot) and need to tour the set of tasks allocated to them before returning to the base. This problem is NP-hard, and we provide a 5-approximation algorithm. We then consider the Heterogeneous Agent Path Problem (HAPP) where agents can start from arbitrary locations and are not constrained to return to their start location. We consider two approaches to solve HAPP and provide a 15-approximation algorithm for HAPP.</p> <p> We then look at the effect of risk on path planning by considering a scenario where a mobile agent is required to collect measurements from a geographically dispersed set of sensors and return them to a base. The agent faces a risk of destruction while traversing the environment to reach the sensors and gets the reward for gathering a sensor measurement only if it successfully returns to base. We call this the Single Agent Risk Aware Task Execution (SARATE) problem. We characterize several properties of the optimal policy for the agent. We provide the optimal policy when the risk of destruction is sufficiently high and evaluate several heuristic policies via simulation. We then extend the analysis to multiple heterogeneous agents. We show that the scoring scheme is submodular when the risk is sufficiently high, and the greedy algorithm gives solutions that provide a utility that is guaranteed to be within 50% of the optimal utility. </p>

京都大学 / 0048 / 新制・課程博士 / 博士(情報学) / 甲第20516号 / 情博第644号 / 新制||情||111(附属図書館) / 京都大学大学院情報学研究科数理工学専攻 / (主査)教授 永持 仁, 教授 太田 快人, 教授 山下 信雄 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

No description available.

The success of construction projects depends on proper use of construction equipment and machinery to a great extent. Thus, appropriate planning and control of the activities that rely on construction equipment could have significant effects on improving the efficiency of project operations. Cranes are the largest and most conspicuous construction equipment, widely used in typical construction sites. They play a major role in relocation of materials in horizontal and vertical directions on construction sites. Given the nature of activities relying on construction cranes in various stages of a project, cranes normally have control over the critical path of the project with the potential to create schedule bottlenecks and delaying the completion of the project. This dissertation intends to improve crane operations efficiency by developing a new framework for optimizing crane service sequence schedule. The crane service sequence problem is mathematically formulated as an NP-complete optimization problem based on the well-known Travel Salesman Problem (TSP) and is solved using different optimization techniques depending on the problem’s size and complexity. The proposed framework sets the basis for developing near-real time decision support tools for on-site optimization of crane operations sequence. To underline the value of the proposed crane sequence optimization methods, these methods are employed to solve several numerical examples. Results show that the proposed method can create a travel time saving of 28% on average in comparison with conventional scheduling methods such as First in First out (FIFO), Shortest Job First (SJF), and Earliest Deadline First (EDF).

No description available.