This research project will consider the computational problem of determining routes of a fixed length in real-world street maps. This problem has various practical applications in everyday life, such as planning jogging routes and determining walks to complete our daily steps target. During the Covid-19 pandemic, it is also desirable to be able to create routes that obey government guidelines by “staying local” and avoiding areas of high virus transmission.
The computational problem of quickly determining attractive routes of a target length is highly applicable in the real world; however, very little research has been carried out in this area. One known characteristic is that this problem is NP-hard, and therefore requires the use of heuristic and approximate methods in most cases.*
This project will focus on designing, implementing, and testing a range of algorithms for this problem. In doing this, we will seek to deepen our understanding of this computational problem and, where appropriate, make connections to other graph-theoretical problems and results.
During this PhD the student will learn about different methods for tackling combinatorial optimisation problems, including integer programming, heuristics, and metaheuristics. Such techniques will then be implemented for this problem. There will also be opportunities to learn how to interrogate online mapping services to collect and exploit real-world data. There will be a significant element of coding in these projects (most likely C++ and Python) and the student will become experienced in running large scale experiments and statistically analysing results. A strong background in operational research, mathematics, and/or computer science is therefore required.
Upon completion, the desired aim is for the student to have achieved at least one journal publication in addition to their thesis. Opportunities to teach in tutorial sessions will also be provided. The student will follow the series of NATCOR advanced courses as part of their doctoral training, which will involve making short visits to other universities in the UK. The student is also encouraged to link with colleagues at Cardiff University’s Data Innovation Research Institute (DIRI). They will also attend international conferences, where they will present their work to their peers.
* Lewis, R. (2020) 'A
Heuristic Algorithm for Finding Attractive Fixed-Length Circuits in Street
Maps'. In Computational Logistics (LNCS 12433), pp. 384-395.
http://rhydlewis.eu/papers/kcircuit.pdf
The proposed studentship involves a combination of both theoretical and experimental work. Theoretical results will be derived via a thorough review of the literature, mathematical thought, and supervisory discussions. Significant results will be documented through publication with the student named as first author, helping to develop their research portfolio.
The student will learn about various algorithms for tackling combinatorial optimisation problems. There will be a heavy element of coding in these projects (most likely C++ and Python) and the student will become experienced in running large scale experiments and statistically analysing results. More generally, the student will become experienced in critical thinking, complex problem solving, and correct decision-making. They will develop the research skills needed to dig deeply into the literature to find credible information. All of these skills are highly transferrable inside and outside of academia, particularly in areas of analytics and data science. Opportunities to teach in UG and PGT tutorial sessions will also be provided by the School of Mathematics.
A compulsory taught element of the programme will also be provided by NATCOR, a series of week-long courses taught at different UK universities. These courses will be used to introduce the student to important research skills and methods and will help to advance and broaden their knowledge in the field.
The student will also be encouraged to seek publications during their PhD. This will aid the improvement of their writing skills, and allow them to gain experience in revising and defending work.
HOW TO APPLY
Applicants should apply through the Cardiff University online application portal, for a Doctor of Philosophy in Mathematics with an entry point of October 2021
In the research proposal section of your application, please specify the project title and supervisors of this project.
There is no requirement to submit a research proposal
In the funding section, please select "I will be applying for a scholarship / grant" and specify that you are applying for advertised funding from EPRSC Maths DTP
Continue with Facebook
