Heuristic and exact approaches for multi-objective routing

Download

index.pdf

Date

2013

Author

Tezcaner Öztürk, Diclehan

Metadata

Show full item record

Item Usage Stats

150
views

83
downloads

In this thesis, we consider the bi-objective routing problem. This problem is a combination of the bi-objective shortest path problem (finding the efficient arcs between nodes) and the bi-objective traveling salesperson problem (finding the efficient tours composed of efficient arcs). We develop solution procedures to find efficient tours. We consider two different terrain structures; discretized terrain and continuous terrain. In the discretized terrain, the terrain is approximated with grids and we allow the vehicle to move between adjacent grid points. In the continuous terrain, we consider a two dimensional plane and there are no restrictions on the movement of the vehicle. To find the most preferred solution, we first develop a general interactive algorithm for a decision maker whose preferences are consistent with an underlying quasiconvex function to be minimized for any bi-criteria integer program. We then apply our algorithm to the bi-objective routing problem. In each iteration of the algorithm, we find a number of efficient tours made up of the efficient arcs. For this, we initially find all efficient arcs between all pairs of nodes and introduce these arcs to the interactive algorithm. We establish some rules that decrease the number of efficient arcs required for finding an efficient tour that satisfies some constraints. We demonstrate the approach on the routing problem of unmanned air vehicles (UAVs) which are assumed to travel on a discretized terrain. We also study the routing problem in continuous terrain, specifically for the UAV routing problem. We develop methods to find the approximate efficient frontier of the shortest path problem between each node pair. We then find the efficient tours that use a subset of the efficient arcs using a mixed integer nonlinear program. We also discuss the implementation of the interactive algorithm for the routing problem in the continuous terrain.

Subject Keywords

Drone aircraft., Vehicles, Remotely piloted., Heuristic algorithms., Navigation (Aeronautics).

URI

http://etd.lib.metu.edu.tr/upload/12616680/index.pdf
https://hdl.handle.net/11511/23189

Collections

Graduate School of Natural and Applied Sciences, Thesis

Suggestions

OpenMETU
Core

Intelligent design objects applied to the spatial allocation problem Zaratiegui Fernandez, Javier Ignacio; Sorguç, Arzu; Computational Design and Fabrication Technologies in Department of Architecture (2014) This thesis approaches the spatial allocation problem as a multi-objective optimization problem. It proposes the use of Intelligent Design Objects (IDO) model to help designers with this task. Solutions are generated and evaluated, according the user defined criteria. Iterative improvement is proposed as a help to visualize candidate solutions and conceive the desired spatial relations. By defining the criteria and rating it numerically, both designer and client are able compare the solutions obtained. The ...
Approaches for multiobjective combinatorial optimization problems Özpeynirci, Nail Özgür; Köksalan, Murat; Department of Industrial Engineering (2008) In this thesis, we consider multiobjective combinatorial optimization problems. We address two main topics. We first address the polynomially solvable cases of the Traveling Salesperson Problem and the Bottleneck Traveling Salesperson Problem. We consider multiobjective versions of these problems with different combinations of objective functions, analyze their computational complexities and develop exact algorithms where possible. We next consider generating extreme supported nondominated points of multiob...
On the balanced k-chinese postmen problems Limon, Yasemin; Azizoğlu, Meral; Department of Industrial Engineering (2015) In this thesis, we consider a k-Chinese Postmen Problem with the objective of minimizing total squared workloads. Our aim is to balance the workloads of the postmen, while maintaining low total workload. We develop an efficient subtour elimination constraint and incorporate it to our integer program. We develop exact and approximate solution procedures that run in exponential and polynomial time respectively. The results of our computational experiment reveal the satisfactory behaviors of our algorithms in ...
Nonlinear Seismic Dam and Foundation Analysis Using Explicit Newmark Integration Method with Static Condensation Albostan, Utku; Bahcecioglu, Tunc; Arıcı, Yalın; Kurç, Özgür (Elsevier BV; 2017-09-13) Engineers use the explicit Newmark integration method to analyze nonlinear dynamic problems. Instead of using computationally expensive global matrix assembly and factorization, the explicit integration method performs computations at element level which is computationally efficient, easily parallelizable, and does not require equilibrium iterations in case of nonlinear analysis. On the other hand, the explicit schema might require much smaller time steps compared to implicit integration alternative especia...
Effective optimization with weighted automata on decomposable trees Ravve, E. V.; Volkovich, Z.; Weber, Gerhard Wilhelm (Informa UK Limited, 2014-01-02) In this paper, we consider quantitative optimization problems on decomposable discrete systems. We restrict ourselves to labeled trees as the description of the systems and we use weighted automata on them as our computational model. We introduce a new kind of labeled decomposable trees, sum-like weighted labeled trees, and propose a method, which allows us to reduce the solution of an optimization problem, defined in a fragment of Weighted Monadic Second Order Logic, on such a tree to the solution of effec...

Citation Formats

D. Tezcaner Öztürk, “Heuristic and exact approaches for multi-objective routing,” Ph.D. - Doctoral Program, Middle East Technical University, 2013.