### Diclehan Tezcaner Ozturk (University of Strathclyde)

#### Heuristic and exact approaches for bi-objective routing

*Wednesday 18 Febrary 2015 at 15.30, JCMB 6206*

##### 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 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 compare the results for discretized and continuous terrains.

### Seminars by year

*Current*
*2016*
*2015*
*2014*
*2013*
*2012*
*2011*
*2010*
*2009*
*2008*
*2007*
*2006*
*2005*
*2004*
*2003*
*2002*
*2001*
*2000*
*1999*
*1998*
*1997*
*1996*