Major Projects
Due to NDA, some of my recent projects are excluded from the list below.
Ferry Scheduling and Fleet Optimisation
Role Principle investigator (2014–2015), co-investigator (2012–2013), contributor (2011–2012).
Description We have been running several projects with British Columbia Ferry Services Ltd. (BC Ferries) to find optimal fleet configurations and improved service strategies in the region of Vancouver, BC, Canada.
Media release In 2014, BC Ferries announced a $252 million vessel replacement programme involving three Intermediate Class Ferries (link to BC Ferries' media release). This decision was supported by independent research projects by Abraham Punnen and Daniel Karapetyan conducted in 2011–2013 (media release). The researchers validated the efficiency of the proposed fleet configurations in terms of the potential operational cost and level of service relative to the current vessels in service.
CORS Practice Prize Abraham Punnen and Daniel Karapetyan recently won the second Practice Prize at the Canadian Operational Research Society conference for their work with BC Ferries.
TV Commercials Scheduling
Description Our ASAP team is working with Channel 4 (a national TV company) in order to investigate the application of optimisation techniques to the scheduling of commercials during advertising breaks. The objective is to provide schedules that increase advertising effectiveness and lead to greater advertiser satisfaction.
Airport Pre-Departure Sequencer
Description Airport departure sequencing is a complicated dynamic optimisation problem with many contradicting objectives. Improved predictions of the departure sequence notably reduce the departure delays, fuel burn and air and noise pollution at the airport. Our team, in collaboration with Ultra Electronics Ltd., designed a pre-departure sequencer for a European international airport with plans to install it in more airports.
Satellite Mission Planning
DescriptionIn the first part of this project, we addressed the satellite downlink scheduling problem. The data downlinking can be the bottleneck of a satellite's performance. In this project, we formulated the satellite downlink scheduling problem as a constrained parallel machine scheduling problem and proposed an efficient heuristic algorithm to solve this class of problems. In our case study, computational experiments showed that the proposed heuristic clearly outperforms currently implemented algorithms and reaches near-optimal solutions (this was proven by means of a mixed integer program) in less than a minute for any of our benchmark instances.
In the second part of the project, we focused on image acquisition scheduling for a satellite constellation. The existing literature on the subject cannot be applied to our case study problem and, thus, we develop new models and solution techniques to produce near-optimal schedules in a limited time.
Generalised Travelling Salesman Problem
Description The Generalised Travelling Salesman Problem (GTSP) is a natural generalisation of the well-known Travelling Salesman Problem (TSP). Over the years, we have developed a number of efficient algorithms including a memetic algorithm (Gregory Gutin and Daniel Karapetyan, A memetic algorithm for the generalized traveling salesman problem, Natural Computing 9, 47–60, 2009) that still holds the title of the state-of-the-art GTSP solver.
Instances library I am maintaining the GTSP Instances Library which is a collection of de facto standard test instances used in computational experiments in many GTSP related publications. The library aims at providing the instances in a convenient form and to keep track of the best solutions found for each of these problems.
Bipartite Unconstrained 0-1 Quadratic Programming Problem
Description The Bipartite Unconstrained 0-1 Quadratic Programming Problem is a generalization of the well-known Unconstrained 0-1 Quadratic Programming Problem. It has numerous applications in graph theory, matrix factorization, etc. Although the problem is widely mentioning in literature, neither polynomially solvable cases nor heuristic approaches were thoroughly investigated before. We addressed these two subjects and achieved significant results in both cases.
Multidimensional Assignment Problem
Description The Multidimensional Assignment Problem is a generalization of the well-known Assignment Problem. It has applications in multiple targets tracking, matching noisy data from multiple sensors, image recognition, solving systems of polynomial equations and others.