Ph.D. Theses

Permanent URI for this collection

https://digitalarchive.library.bogazici.edu.tr/handle/123456789/11650

Browse

Now showing 1 - 13 of 13

Analysis of urban freight distribution and a city logistics model for İstanbul
(Thesis (Ph.D.) - Bogazici University. Institute for Graduate Studies in Science and Engineering, 2023., 2023) Yılmazer, Kadriye Büşra.; Aras, Necati.; Or, İlhan.
Intensive population growth in metropolitan cities brings with it many problems, such as increased demand, traffic congestion, and environmental degradation. This requires more efficient use of resources and faster resolution of issues. With 15.6 million inhabitants, ˙Istanbul is by far the most populated city in Turkey. Due to the problems experienced in the logistics sector and the current situation of ˙Istanbul’s logistics activities, a city logistics plan for ˙Istanbul is required to provide a sustainable and efficient logistics and freight transportation system. The term “city logistics” aims at e↵ectively managing freight transportation, reducing traffic congestion and minimizing the environmental e↵ects of logistics activities in order to increase the quality of life and reduce costs in cities. This thesis aims to analyze the current state of ˙Istanbul’s freight flows and to develop a linear optimization model and solution methodology with the goal of improving the city logistics problems of ˙Istanbul. Initially , based on ˙Istanbul’s urban transportation network and certain criteria, ˙Istanbul is divided into 105 zones, and supply and demand points are determined. Using this network, ˙Istanbul’s city logistics is modeled using mathematical programming by considering ten di↵erent product categories, four di↵erent vehicle categories, and four di↵erent time intervals. The model optimizes the total transportation and CO2 emission costs under various constraints. It is solved using real data of ˙Istanbul. In order to see the e↵ects of possible outcomes (such as insufficient transshipment center capacity, heavy reliance on electric van usage, di↵erent truck utilization rates, traffic density, limitations on emissions, etc.), di↵erent scenarios are prepared. Finally, the results are analyzed.
Collection system design problem with routing under a pıck - up policy
(Thesis (Ph.D.)-Bogazici University. Institute for Graduate Studies in Science and Engineering, 2018., 2018.) Tekin, Mehmet Tuğrul.; Aras, Necati.; Aksen, Deniz.
This thesis is concerned with collection system design for used products obtained from dealers and is an extension of the works by Aras et al. (2008) and Aras and Aksen (2008). The design decisions involve the locations of the collection centers to be opened out of a ﬁnite number of candidates possibly having storage capacity limits, the size of the homogeneous ﬂeet with capacity-limited vehicles to be associated with each collection center, the dealers to be visited, the unit used product acquisition price to be paid and the tour of each vehicle. Not all dealers have to be visited. Instead, the subset that serves the interests of the collecting entity must be identiﬁed where the collecting entity is a proﬁt maximizer. The used products have an inherent value which constitutes the revenue. The dealers have a reservation price associated with their used products and will trade if the oﬀered acquisition price is greater than or equal to the reservation price. The collecting entity must either buy all used products of a dealer or none. Furthermore, it is assumed that horizontal information sharing is in place, hence the oﬀered acquisition price must be the same for all dealers. The collecting entity may choose not to visit a dealer even if the oﬀered acquisition price is greater than or equal to that dealer’s reservation price. Hence, the associated costs of the design problem are related to opening collection centers, used product acquisition, vehicle acquisition and travelling costs. A novel tabu search inspired algorithm incorporating a three level memory mechanism and a hierarchy-free implementation of all neighborhoods is developed. It is adapted to the location routing problem (LRP) and tested on benchmark instances. The overall algorithm is tested on instances derived from LRP benchmarks along with the mathematical programming formulations. Both the LRP adaptation and the overall algorithm exhibit satisfactory performance on test instances.
Coverage, sink location and routing problems in wireless sensor networks
(Thesis (Ph.D.)-Bogazici University. Institute for Graduate Studies in Science and Engineering, 2009., 2009.) Güney, Evren.; Altınel, İ. Kuban.; Aras, Necati.
Recent advances in electronics and telecommunications have enabled the development of low-cost, low-power multifunctional sensor devices that are powered by batteries and communicating through wireless channels over small distances. When a large number of these devices work collaboratively for certain purposes, they form a network which is called a wireless sensor network (WSN). Due to their benefits and inherent characteristics, WSNs give rise to a broad-range of many real-life applications. There are various design issues in the construction of WSNs. In this study, we focus on three important classes of problems, which are Point Coverage, Sink Location and Data Routing Problems. We propose a Binary Integer Programming (BIP) formulation to model the coverage problem and develop various heuristics to solve it. Both the Routing Problem (RP), which involves finding the most energy efficient sensor-tosink routes and Sink Location Problem (SLP), which is determining the optimal sink locations are important design issues to extend the lifetime of a WSN. However, the joint optimization of these two problems results in a more efficient network design, so we develop several Mixed Integer Linear Programming (MILP) formulations and propose optimum solution techniques and heuristics to solve them. Finally, we solve the complete integrated model, which consists of the coverage, sink location and data routing problems simultaneously. We call this hard problem as the Coverage, Location and Routing Problem (CLRP) and develop new mathematical programming formulations. We propose a nested solution procedure, where in the first level of this approach, good sensor locations are sought by using some metaheuristics. In the second level, we solve the remaining sink location and routing problem using efficient heuristics.
Data-driven local search heuristics for bilevel network design problems
(Thesis (Ph.D.) - Bogazici University. Institute for Graduate Studies in Science and Engineering, 2022., 2022) Sevim, İsmail.; Aras, Necati.; Güler,
In the Network Design Problem (NDP), one aims to design the configuration of a network by installing links between a set of given nodes and determine the flow of a set of commodities over these installed links. In this thesis, we work on two bilevel NDPs where the sequential process of decision making approach is inherited. In the first bilevel NDP we model the strategic flight NDP of a small airline carrier as a network interdiction problem to analyse the maximum possible disruption in its flight network in the wake of virtual attacks performed by a competitor. We call this problem the r - Interdiction Network Design Problem with Lost Demand (RI-NDPLD). In the second problem, namely Bilevel Optimization Model for the Reconfiguration of refugee camp network (BOpt-RRC), the readjustment of configurations of refugee camp network are studied under the case of new refugee flows and possible variations in the supply of public service providers. We implement a set of generic local search matheuristics to solve both problems. In the Tabu Search (TS) proposed for the RI- NDPLD, we enhance the generic implementation with bound based pruning and regression based candidate solution set generation procedures to reduce the computational burden of explicit evaluation of all neighboring solutions, and hence, enjoy better diversification. We also implement a generic TS to solve the BOpt-RRC and devise an adaptive neighborhood selection procedure to incorporate into this implementation. In addition to the generic TS, we also implement a Variable Neighborhood Search (VNS) matheuristic and devise an association rule based injection procedure to incorporate good solution components to initial solutions obtained by usual random shaking. Experimental studies reveal promising results for the proposed methods.
Disaster mitigation and humanitarian relief logistics
(Thesis (Ph.D.)-Bogazici University. Institute for Graduate Studies in Science and Engineering, 2012., 2012.) Döyen, Alper.; Aras, Necati.; Barbarosoğlu, Gülay.
In this thesis we are interested in two distinct problems within the disaster management context. These problems are modeled by two-stage stochastic integer programming since stochasticity is inherent in natural disasters. First, we consider a humanitarian relief logistics model which can be used as a pre-disaster planning tool that also considers post-disaster decisions to give an effective response aftermath an earthquake. In this model, decisions are made for location of pre- and post-disaster rescue centers, the amount of relief items to be stocked at the pre-disaster rescue centers, the amount of relief item flows at each echelon, and the amount of relief item shortage. The objective is to minimize the total cost of facility location, inventory holding, transportation and shortage. Since the building and transportation network retrofitting decisions affect the pre-disaster planning of post-disaster response decisions, we propose an integrated model that includes these retrofitting decisions as well. The total mitigation budget is allocated among these mitigation alternatives. The amount of relief item demand is a decision variable that is determined according to the postdisaster damage of buildings. The objective function is defined as the minimization of the total cost of retrofitting, transportation and shortage of relief item demand. The deterministic equivalents of both models are formulated as mixed-integer linear programming models (MILP) and solved by Lagrangean heuristic methods. Results on randomly generated test instances show that the proposed solution methods for both models exhibit good performance under different parameter settings. Also, the value of stochastic solution for both models are high, which validates the incorporation of the uncertainty in the proposed models. In addition, for the integrated model, various analyses are carried out to clearly understand the model behaviour.
Leader-follower games for influence spread in social networks
(Thesis (Ph.D.) - Bogazici University. Institute for Graduate Studies in Science and Engineering, 2020., 2020.) Tanınmış, Kübra.; Aras, Necati.; Altınel, İ. Kuban.
Influence Maximization Problem involves nding a set of individuals in a social network to trigger an in uence/information spread, i.e., a seed set, such that the maximum possible number of individuals are in uenced. In this thesis, two competitive variants of the Influence Maximization Problem where two players make decisions sequentially in the form of a Stackelberg game are introduced. In the Influence Maximization with Deactivation the objectives of the leader and the follower are maximization and minimization of the spread, respectively. While the Misinformation Spread Minimization Problem has a reverse situation, in both problems the leader takes the follower's optimal response into account. Both problems are formulated as mixed-integer bilevel linear programs with a two-stage stochastic program in the lower level, by enumerating the diffusion scenarios due to the well known Linear Threshold model. In the solution phase, firstly several matheuristic methods are proposed where the follower's optimal decisions are approximated via Sample Average Approximation method. For the MSMP, additionally a state-of-the art in uence maximization method is integrated into the developed algorithms. The proposed methods are evaluated on small instances where an optimal solution can be found via complete enumeration as well as larger instances where the algorithms are compared to each other. Then, a branch-and-cut algorithm for mixed-integer bilevel problems is enriched with a variable bound update procedure for the Influence Maximization with Deactivation which is shown to increase the time effciency. An exact algorithm for bilevel interdiction problems is improved substantially, tested on various problem types including the Misinformation Spread Minimization Problem and yields signi cantly better results.
Minimum split coloring
(Thesis (Ph.D.)-Bogazici University. Institute for Graduate Studies in Science and Engineering, 2012., 2012.) Yüzsever, Rıdvan Mert.; Aras, Necati.; Ekim Aşıcı, Tınaz.
Combinatorial optimization is a very important branch of optimization eld. Many problems in the real world such as transportation, scheduling, production, and telecommunication can be modeled as a combinatorial optimization problem. Although a combinatorial optimization problem has a nite set of solutions, examination of this solution space is not easy to accomplish in many problems. Graph theory is one of the most studied elds in optimization for decades. There is a huge literature on this eld with very di erent approaches. One of the most famous problems in this eld is the graph coloring problem. This is due to the fact that it has a wide range of applications but in the same time, it is extremely di cult to nd an e cient way to solve it. Column generation method embedded in a branch-and-bound tree is a success story in dealing with di cult optimization problems. In most of the cases, it is better than the enumeration of the solution space and dynamic programming solution method in combinatorial optimization problems. In this thesis, we consider a generalization of the graph coloring problem called Minimum Split Coloring Problem which covers an even wider application area. We develop a column generation method embedded in a branch-and-bound tree to solve the Minimum Split Coloring Problem exactly in general graphs.
Network flows with conflict constraints
(Thesis (Ph.D.)-Bogazici University. Institute for Graduate Studies in Science and Engineering, 2019., 2019.) Şuvak, Zeynep.; Altınel, İ. Kuban.; Aras, Necati.
It is a commonly used approach to model real life problems as network ﬂow prob lems and they appear in a wide range of areas including telecommunication, wireless networks, transportation, healthcare and scheduling. Our focus in this thesis is on an extension of network ﬂow problems with conﬂict constraints that prevent the simul taneous usage of some arc pairs to send ﬂow. We particularly concentrate on four of them: the minimum cost noncrossing ﬂow problem on layered networks, the minimum cost ﬂow problem with conﬂicts, the maximum ﬂow problem with conﬂicts and the assignment problem with conﬂicts. The minimum cost noncrossing ﬂow problem on layered networks, which emerges from the quay crane scheduling problem in container terminals, is proven to be NP-hard. Further complexity results including the strong NP-hardness and the non-existence of polynomial time approximation algorithm for the the minimum cost ﬂow problem with conﬂicts on general networks are also pro vided. Moreover, polynomially solvable special cases for the minimum cost noncrossing ﬂow problem on layered networks and the assignment problem with conﬂicts, which is known to be NP-hard, are explored. Similarly, the conditions which limit the number of feasible solutions with a polynomial number are indicated for the minimum cost ﬂow problem with conﬂicts and the maximum ﬂow problem with conﬂicts taking ad vantage of the conﬂict graph representation. Alternative mathematical representations for these problems are developed. Pre-optimization procedures to reduce the problem size and to ﬁnd an initial feasible solution are deﬁned. Exact solution algorithms in cluding a branch-and-bound algorithm enriched with the subroutines that exploit the special structure of the considered problem, an improved Russian doll search algorithm and a Benders decomposition with strengthened cuts are proposed. The methods are tested on a large set of test instances and they are shown to be superior than solving the underlying mathematical formulations with a commercial optimization solver.
New neurocomputational approaches for estimating road travel distances and for solving the euclidean traveling salesman problem
(Thesis (Ph.D.) - Bogazici University. Institute for Graduate Studies in Science and Engineering, 1999., 1999.) Aras, Necati.; Altınel, İ. Kuban.
Neural networks are among the most rapidly developing new scientific tools. There are numerous publications reporting their success in estimation and optimization. This work concentrates on both of these aspects and applies neural networks for solving two problems from operations research. One of the problems is the distance estimation problem, which mainly deals with the estimation of the length of the shortest road connecting two points on the earth surface. First, multilayer perceptrons have been adopted. Then, a neural clustering strategy which uses the principle of vector quantization has been utilized prior to the estimation. Thr results are superior than those reported in the literature. The other problem is the well-known Euclidean traveling salesman problem. It tries to determine the shortest tour passing throgh the cities of a given set by visiting aech city exactly once. A new adaptive scheme has been developed in order to solve this problem. The new approach incorporates explicit statistical information obtained from the city coordinates into the adaptation mechanism of Kohonen's self-organizing map. Results obtained for different problems are better than the previous ones. The new approach is then adapted to the solution of the Euclidean Hamiltonian path problem whose combination with the decomposition philosophy resulted in a highly all-neural Eulidean traveling salesman problem algorithm.
Optimal placement, scheduling and routing to maximize lifetime in wireless sensor networks
(Thesis (Ph.D.)-Bogazici University. Institute for Graduate Studies in Science and Engineering, 2010., 2010.) Türkoğulları, Yavuz Boğaç.; Altınel, İ. Kuban.; Aras, Necati.
A wireless sensor network consists of distributed autonomous tiny electronic devices called sensors. They have limited energy and capability for sensing, data processing and communication, but they can collectively behave to provide an effective network that monitors a region, and transmit information to gateway nodes called sinks. In most of the applications, the network must operate for long periods of time, so the available energy resources of the sensors must be managed efficiently. In this thesis we first develop mixed-integer linear programming models to maximize network lifetime by optimally determining locations of sensors and sinks, sensor-to-sink data routes and activity schedules of the deployed sensors over a finite planning horizon subject to coverage, flow conservation, energy consumption and budget constraints. Then, we propose valid inequalities, which we use with a new branch-and-price algorithm to solve the problem exactly. Although they provide stronger linear programming relaxations and thus increase the quality of the formulation, the size of the networks for which the model can be solved exactly is very limited. Hence, we develop approximate solution heuristics using techniques such as the Lagrangean relaxation, column generation and a greedy selection criterion. Based on the computational experiments we can say that they are accurate and efficient. The minimum cost coverage problem, which consists of the deployment of sensors over a sensor field modeled as a set of finite points so that total cost is minimized subject to the coverage requirements, generalizes the famous set covering problem. We provide a polyhedral analysis of this general problem, which has not been studied very much previously. We develope a procedure that generates valid inequalities and a sufficient condition for facet definition, and a cutting plane. Experiments show that the proposed valid inequality cuts of the fractional optimum and improve considerably the linear programming relaxation lowerbound. Finally, we revise the convergence proof of the deflected subgradient algorithm that uses conditional subgradients and suggest some refinements.
Optimal server placement, service deployment, and resource allocation in next-generation computer network
(Thesis (Ph.D.) - Bogazici University. Institute for Graduate Studies in Science and Engineering, 2022., 2022) Ahat, Betül.; Aras, Necati.; Altınel, İ. Kuban.
With the expansion of mobile devices and new trends in mobile communication technologies, there is an increasing demand for diversified services. To accommodate a large number of services on a common network, it becomes crucial for an operator to optimize resource allocation decisions to satisfy the service requirements in an economical way. In this thesis, the computation architecture design problem is considered first where server placement, service deployment, and task assignment decisions are optimized to maximize the revenue of the operator. The problem is modeled as a mixed-integer linear programming (MILP) formulation and a Lagrangian relaxation- based heuristic algorithm is proposed. Then, the concept of network slicing, which partitions a single physical network into multiple isolated slices, is examined. In the deterministic network slicing problem, the capacities of the computational resources are partitioned into slices each of which is customized for a particular service type. An MILP formulation is presented that takes the delay requirements of services into account. Additionally, two algorithms based on Benders decomposition are devised along with some valid inequalities and cut generation techniques. The problem definition is also extended to consider the stochastic behavior of the service requests. A two-stage stochastic integer programming model is constructed which is then converted into a large-scale MILP model by defining a set of scenarios for the random parameters. A similar decomposition approach is also applied to the stochastic network slicing problem. In our computational study on randomly generated test instances, the validity of our models is assessed and the effectiveness of the proposed solution approaches is demonstrated.
Optimally locating facilities with variable characteristics
(Thesis (Ph.D.) - Bogazici University. Institute for Graduate Studies in Science and Engineering, 2011., 2011.) Küçükaydın, Hande.; Altınel, İ. Kuban.; Aras, Necati.
Facility location problems aim at optimally locating facilities like plants, warehouses, convenience stores, shopping malls etc. They can have di erent objectives such as maximizing the pro t gained from the customers or minimizing the costs of locating facilities and serving the customers. In this thesis, we mainly focus on competitive facility location problems which constitute a special family. In a competitive facility location problem, a rm or franchise is concerned with installing new facilities to serve customers in a market where existing facilities with known locations and attractiveness levels compete for increasing their market share and pro t. We can classify these problems into two groups: those with non-reactive competition and those with reactive competition. Three di erent types of competitive facility location models are proposed in order to determine the locations and attractiveness levels of the new facilities to maximize the pro t in this thesis. The rst one belongs to the former class, where the last two models fall into the latter one. We formulate the rst one as a mixed-integer nonlinear programming problem and propose three methods for its solution: a Lagrangean heuristic, a branch-and-bound method with Lagrangean relaxation, and a branch-and-bound method with nonlinear programming relaxation. The computational results obtained on a set of problem instances show that the branch-and-bound method using nonlinear programming relaxation is the most e cient and accurate solution method in order to solve the proposed problem. We consider next an extension of this model by relaxing the assumption that the competitor in the market does not react to the opening of new facilities. In other words, the competitor can react by adjusting the attractiveness levels of its existing facilities with the objective of maximizing its own pro t. To this end, a bilevel mixed-integer nonlinear programming model is formulated. We transform this bilevel model into an equivalent one-level mixed-integer nonlinear program and solve it by a global optimization method. For this problem, we also consider a scenario in which the new entrant rm ignores the reaction of the competitor. The experimental results indicate that anticipating the competitor's reaction by including this into his optimization problem increases the pro t of the new entrant rm, whereas the competitor's pro t is decreased. The last competitive facility location model relaxes the limitation about the competitor's reaction: now the competitor can also open new facilities, close existing ones and/or adjust their attractiveness. This also formulates a bilevel mixed-integer nonlinear programming problem which we try to solve by combining tabu search with global optimization algorithms. We develop three di erent tabu search methods and the computational results on a set of problem instances for comparing the performance of the solution methods show that the third tabu search method is the most accurate one, while the second tabu search method is the most e cient solution procedure. Finally, we consider a di erent facility location problem which takes the customer preferences into account. The facilities are not necessarily identical and customers visit di erent types of facilities according to some given probability distribution and the maximum distance which they are willing to travel. We formulate a binary linear programming problem and solve it by three procedures that include a Lagrangean heuristic whose solution is improved further using a local search method. Based on the experimental results carried out on a set of problem instances the third solution method is the most e cient one. However, a statistical analysis on the quality of the solutions states that there is no signi cant di erence between the three solution procedures.
Quantitative models for decision making in reverse logistics network design
(Thesis (Ph.D.)-Bogazici University. Institute for Graduate Studies in Science and Engineering, 2009., 2009.) Tombuş, Ayşe Cilacı.; Aras, Necati.
In this thesis, we focus on a problem in reverse logistics network design where the aim is locating distribution centers, inspection centers and remanufacturing facilities, determining the acquisition price as well as the amount of returned goods to be collected depending on the unit cost savings and competitor’s acquisition price. The coordination of the forward and reverse flows in the network is also taken into account in order to minimize the transportation costs, fixed costs and used product acquisition costs. A mixed-integer nonlinear programming problem has been formulated and exact algorithms have been suggested to solve it. When the acquisition price is set to a given value, the remaining problem becomes a mixed-integer programming problem which can be solved by Lagrangean relaxation, Benders Decomposition and Cross Decomposition algorithms. The best value of the acquisition price that minimizes the total cost is determined by the Golden Section search and computational results have been reported. Moreover, the effect of fixed cost, capacity as well as unit cost savings on the solution time have been analyzed.

Browse

Browsing Ph.D. Theses by Author "Aras, Necati."

Results Per Page

Sort Options