3
Archived Theses
0
DOIs Assigned
0%
DOI Rate
Discipline
Minimum ağırlıklı mükemmel komşuluk kümesi problemi
Given an undirected simple graph G = (V,E), the open neighborhood of a vertex j ∈ V, denoted by δ(j), is defined as the set of all vertices that are adjacent to j , i.e., δ(j) = {i|{i,j} ∈ E}. The closed neighborhood of a vertex j, denoted by Δ(j), is defined as Δ(j) = δ(j)∪{j}. For a set S ⊆ V, a vertex j is said to be perfect with respect to S, i.e., S-perfect, if |Δ(j)∩S|=1. The set S is said to be a perfect neighborhood set if the set of S-perfect vertices dominate G. Hedetniemi et al. (1997) proposed a linear-time algorithm for the minimum cardinality perfect neighborhood set problem when G is a tree. We observe some flaws in the proposed algorithm and correct them. Moreover, we consider the weighted version of the problem, where the weight of a perfect neighborhood set S is defined as ∑j∈V (wjyj + vjxj). Here yj and xj are binary parameters taking the value 1 if and only if j is in S and j is S-perfect, respectively, and wj and vj are the weights associated with vertex j. We extend the algorithm proposed by Hedetniemi et al. for trees to the weighted case and check its correctness by comparing its solutions with the solutions of an integer programming formulation that we propose for arbitrary graphs. Additionally, we provide some valid inequalities for the integer programming formulation to make it stronger, and characterize the perfect neighborhood set polytope for star graphs and complete graphs by the help of these valid inequalities. Finally, we conduct computational experiments to see the effects of these valid inequalities.
Enerji verimliliği esaslı zaman kısıtlı ve çok konumlu robot buluşma problemi
We study the energy efficient multi-place robot rendezvous problem. In this problem, we aim to find a set of rendezvous places where a tanker robot meets with mobile worker robots for a recharging task by preserving a meeting order. The problem is examined under two different objective functions. The first objective function is to minimize the total time spent, i.e., campaign time to recharge all the robots. The second objective function is to minimize the total energy consumption of all the robots by taking a predetermined campaign time as a restriction. The energy consumption functions of both the mobile worker robots and the tanker robot used in this study are nonlinear and distances between locations are calculated by the Euclidean distances. This problem is NP-hard when we aim to find the optimal rendezvous places and the optimal meeting order simultaneously. In our solution approach, we first fix the meeting order and determine the optimal rendezvous places based on a given meeting order. To do so, we provide a second order cone programming formulation. Then, we utilize improvement heuristics to find a better meeting order to improve the objective function value. Mainly we work on 2-opt and 3-opt edge exchange improvement heuristics as well as their combination to search for a better meeting order. Furthermore, we implement speed-up techniques to decrease the solution times of the improvement heuristics. Finally, extensive computational experiments are conducted to compare the suggested improvement heuristic algorithms and speed-up techniques.
Tercih edilen hizmet başlangıç zamanlı ve çoklu müşteri sınıflı kuyruk sistemleri
Motivated by the operational problems in curbside pickup systems, in this thesis, a capacity allocation problem in a queuing system, where arriving customers have preferred service delivery times, is studied. In the illustrated system, customers may have different priorities. All requests are assumed to be served before or during their requested time period. In order to increase the generality of the model, actions of early service, rejecting a customer request, and outsourcing (or equivalently working overtime) are allowed for the service provider. We model this problem as a Markov Decision Process. We analyze the structural properties to identify a set of suboptimal solutions and use these results to develop efficient solution methods. We develop state space aggregation methods to solve problem instances of larger size.