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