# Operations Research

Listed on this page are current research projects being offered for the Vacation Scholarship Program.

## Floods, fires and explosions: how to design survivable networks in the modern age

Much of society’s critical infrastructure takes the form of large-scale networks. Think of examples such as the power grid, the NBN, gas and water pipelines, and transportation networks. All such networks are potentially vulnerable to natural disasters, or even terrorist attacks. Significant interruption to these networks can wreak havoc. So the question is: how do we design these networks to be robust against local, regional destruction, without blowing the national budget?

In this project we will use planar geometric graph models for this problem and analyse survivability when the destruction region is modelled as a circular disk. In particular, we would like to find algorithms for optimally designing networks that are survivable against failures of a given maximum radius. The project will use mathematical tools from graph theory, optimisation, computer science and just a little bit of Euclidean geometry.

Contact Charl Ras: cjras@unimelb.edu.au

## Performance of a sensor network

(Also listed in Stochastic Processes, posted for 2018-2019)

Wireless networks known as (ad hoc) sensor networks consist of sensing devices known as sensor nodes or sensors. Each sensor node collects information, which is then relayed back to a main station known as a base station or sink. Due to a limited transmission range, each node may need to relay the information through other nodes, resulting in multi-hop relaying. In other words, the collected information is relayed via a pathway of sensors rather than from each sensor directly to the sink. Furthermore, sensors may only operate for a limited time before becoming inoperative, thus needing to be repaired.

In this project we consider a mathematical model for a sensor network in which sensors communicate with the sink via a pathway or route, which is constructed with some simple routing rule, such as choosing the nearest neighbour. We will assume that sensors are operational for an exponentially distributed length of time with parameter λ, before being repaired in an exponentially distributed length of time with parameter μ.

We are interested in calculating performance measures such as the expected length of time until the network becomes disconnected (that is, at least one sensor cannot communicate with the base station), and the expected proportion of time the network is fully connected.

For this project, some familiarity with MATLAB or some other programming language (for example, R, Python, Julia etc) is desirable as initially the model will be simulated, before deriving some analytical results.

Contact: Mark Fackrell fackrell@unimelb.edu.au and Paul Keeler h.keeler@unimelb.edu.au

## Improving the health of patients with chronic conditions using better resource allocation

(Posted for 2017/2018)

MonashWatch is an out of the hospital support service for patients with chronic conditions who have had repeated hospitalisations (click here to find out more). Patients recruited to the program are contacted by phone and asked a series of questions in order to determine their health condition, and whether they need to be admitted to hospital or require some other medical intervention. The primary objective here is to maximise the health outcomes for the patients enrolled in the program. Having healthier patients will lead to a reduction in the number of unplanned hospital admissions, which is the secondary objective here.

Operationally, healthcare practitioners involved in MonashWatch need to decide, each day, which patients to contact. There are many factors that determine which patients to ring. These include: the current health condition of the patient, their health history, their time availability, the last time they were contacted, and their previous responses to the program.

We have modelled this problem as a partially observable Markov decision process, or more specifically, as a restless multi-armed bandit processes (see here). Then Whittle indices (see here) are used to determine which patients to ring each day, and in which order.

The goal of this project is to implement the algorithm using simulated data, and compare the outcomes to other existing algorithms. A probability background and experience in coding in C or Matlab are required.

## Predicting pedestrian flows in Melbourne

(Posted for 2017/2018)

Recently there are increased risks associated with exposure of persons in central city areas due to terrorism. A number of sensors have been installed in Melbourne’s Central Business District (CBD) that measure the number of persons moving at particular sites. This project will involve analysing this data to identify patterns associated with the numbers of persons walking in public areas. Variations relating to location (nearby land use), time of day, day of week, seasonality and special events will be investigated. A model for predicting the number of pedestrians at specific locations in Melbourne will be developed.

Contact: Joyce Zhang Lele.zhang@unimelb.edu.au and Russell Thompson rgthom@unimelb.edu.au

## Perfect codes in Cayley graphs

(Also listed in Discrete Mathematics and Algebraic Combinatorics, posted for 2016-2017)

Perfect codes have been important objects of study ever since the dawn of coding theory in the late 1940s, and after more than six decades they still receive much attention today. The aim of this project is to study perfect codes in Cayley graphs, which are generalizations of perfect codes in the classical setting.

Contact: Sanming Zhou sanming@unimelb.edu.au

## Arc-transitive graphs

(Also listed in Discrete Mathematics and Algebraic Combinatorics, posted for 2016-2017)

A finite graph is a finite set together with a family of 2-element subsets of the set; each element in the set is called a vertex and each 2-element subset in the family is called an edge. An oriented edge is called an arc. If all vertices have the “same status” in the graph and all arcs have the “same status” as well, then the graph is said to be arc-transitive. Examples of arc-transitive graphs include the 1-skeletons of the five Platonic polyhedral. The study of arc-transitive graphs has long been an important area in algebraic graph theory with strong links to group theory. The goal of this project is to study some families of arc-transitive graphs whose automorphism groups contain a subgroup acting imprimitively on the vertex set.

Contact: Sanming Zhou sanming@unimelb.edu.au

## Cores of graphs

(Also listed in Discrete Mathematics and Algebraic Combinatorics, posted for 2016-2017)

A homomorphism from a graph X to a graph Y is a mapping from the vertex set of X to the vertex set of Y that preserves the adjacency relation. Two graphs X, Y are said to be homomorphically equivalent if there is a homomorphism from X to Y and also there is a homomorphism from Y to X. The smallest induced subgraph of X that is homomorphically equivalent to X is called the core of X. This notion plays an important role in understanding structure and colouring of graphs. It is also closely related to several application domains, including synchronization. The purpose of this project is to understand the cores of some families of graphs, especially Cayley graphs of some finite groups.

Contact: Sanming Zhou sanming@unimelb.edu.au

## Enhancing traffic flows at continuous flow intersections

(Posted for 2016-2017)

Melbourne is going to have a new type of intersections along one of its busiest corridors (see here). The basic idea behind continuous flow intersections is to move right-turning cars to the other side of the road and so they won’t affect opposing traffic when crossing the intersection. The traffic signal control strategy plays a key role in determining the capacity of the intersection. We shall model vehicular traffic and study cooperative traffic signals in order to improve traffic flows and reduce congestion.

Contact:: Dr. Joyce Zhang lele.zhang@unimelb.edu.au

## Happy blood donor program

(Posted for 2016-2017)

Recruiting and retaining blood donors is key challenges for blood agencies. The donor service level depends on appropriate appointment strategies. In this mini-project, we shall study a scheduling problem for the appointment reservation that accounts for both booked donors and walk-in donors. It consists of offline scheduling strategies for preallocating time slots to blood donors and online scheduling algorithms for assigning time slots to donors without reservation. The aim is to improve the experience of donors at blood service centers (e.g. reducing their waiting time) and reduce candidate donor abandonment.

Contact:: Dr. Joyce Zhang lele.zhang@unimelb.edu.au

## β-skeletons in the algorithmic closet: computing Relative Neighbourhood Graphs at the drop of a hat

(Posted for 2016-2017, reposted for 2017-2018)

Relative neighbourhood graphs (RNGs) are geometric graphs that capture the essence of “closeness” between points in the plane. Intuitively, these graphs provide a picture of the shape of a set of points, which explains their ubiquitous use in computer graphics and computational geometry. It can be shown that the minimum spanning tree of any set of points in the Euclidean plane is a subgraph of the RNG, which makes this class of graphs of fundamental importance to the field of optimal network design.

The RNG is defined as follows: let A be a set of points in the Euclidean plane. For any pair of points x,y in A, the lens associated with x,y is the intersection of two discs of equal radius |xy| centred at x and y respectively. Edge xy is in the RNG if and only if there are no points of A in the interior of the lens associated with x,y.

In this project we seek to better understand the structure of RNGs and their generalisations, such as β-skeletons. The ultimate aim is to produce lightning-fast algorithms for constructing RNGs. A breakthrough in this area will lead to new algorithms for a multitude of important network-design problems.

Contact: Dr. Charl Ras cjras@unimelb.edu.au

## Survivable spanners: short, simple and sparse

(Posted for 2016-2017, reposted for 2017-2018)

Suppose you would like to design a graph so that the distance between any pair of nodes is as short as possible. It is tempting to simply take the complete graph, because then every pair of nodes is separated by just a single edge. As an added bonus, the complete graph has very high connectivity, which means if we remove some of its edges then the remaining graph will still be connected. But here’s the problem: complete graphs actually have too many edges, which makes working with them quite inefficient. Plus, if we are designing a network in the plane then a complete graph just won’t do, because complete graphs cannot be embedded in the plane without crossing some edges!

The above graph is a Delaunay triangulation, which is not a bad candidate.

We therefore present the following challenge: is it possible to design a graph that maintains the desirable properties of complete graphs, yet is also sparse enough to be planar? In this project we will study (and try to improve) a powerful contender: the famous t-spanner graph.

Contact: Dr. Charl Ras cjras@unimelb.edu.au

## Squeezing the life out of wireless sensor networks

(Posted for 2014-2015, reposted for 2017-2018)

Wireless sensor networks (WSNs) are an exciting new technology that lies at the intersection of communication networks and smart monitoring. It is easy to imagine the benefits of a system consisting of hundreds or even thousands of sensors distributed over a region or an object and able to measure any of a multitude of aspects of their environment, before passing the information to a central base station for intelligent processing. The applications are countless: early detection of bushfires, smart-home systems, battlefield surveillance, animal population tracking, and environmental pollution monitoring – to name just a few.

Although WSNs are already extensively utilised in the real world, their full potential remains largely untapped. In contrast to other types of communication networks, sensor network technology is fundamentally constrained by existing battery technology and energy conservation protocols. This is because WSNs are required to be autonomous for as long as possible, as they are often deployed in remote, harsh, or even hostile environments.

The topology of a WSN (which is the overall pattern formed by the communication links between pairs of sensors) and the relative locations of sensors within the sensing field, play a large role in the efficiency of the network. This project therefore aims to optimise the topological design and sensor location phase of deploying or repairing (augmenting) a WSN. In working on this project students will employ a variety of fascinating mathematical tools from graph theory and network optimisation.

Contact: Dr. Charl Ras cjras@unimelb.edu.au