Tarih:
Konum: B241
“Heuristic and Exact Approaches for Bi-Objective Routing”
by
Dr. Diclehan Tezcaner Ozturk – Department of Management Science, University of Strathclyde
Date: October 31, 2014, Friday
Time: 10:00
Place: B241
Heuristic and Exact Approaches for Bi-Objective Routing
Diclehan Tezcaner Ozturk
Department of Management Science, University of Strathclyde
Abstract
In this study, 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 biobjective 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.
Biographical Sketch
Diclehan Tezcaner Öztürk is a postdoctoral research associate in the Department of Management Science, University of Strathclyde. She received her B.S., M.S. and Ph.D. degrees from the Department of Industrial Engineering, METU in 2007, 2009 and 2013, respectively. She worked as a research assistant in the same department between 2007 and 2013. Her main research interests are multi-objective decision making, combinatorial optimization, evolutionary algorithms, multi-criteria ranking and robust scheduling and routing.