Heuristic Algorithms for Traveling Salesman and Vehicle Routing Problems

Primary supervisor

Edward Lam

Modern transport and logistics rely on efficient routing to ensure that goods are delivered on time and at minimal cost. Determining the optimal order in which vehicles visit a set of customers is a fundamental challenge in mathematics and computer science. Despite decades of research, this problem remains computationally difficult. To achieve reasonable cost-effectiveness in industry-scale applications, the best-performing methods rely on heuristic and suboptimal solvers. This project will develop new suboptimal algorithms for tackling large instances relevant to practice.

Aim/outline

This project explores constraint-based approaches to designing and implementing heuristic algorithms for traveling salesman and vehicle routing problems. Students will design and implement high-performance solving algorithms to efficiently explore the enormous search spaces associated with these problems. The project will combine ideas from mathematical optimisation, algorithm design and computer programming.

URLs/references

  • https://en.wikipedia.org/wiki/Travelling_salesman_problem
  • https://www.minizinc.org/
  • http://webhotel4.ruc.dk/~keld/research/LKH-3/
  • https://github.com/huub-solver/huub

Required knowledge

This project would suit a mathematics, computer science or software engineering student with an interest in combinatorial optimisation, graph theory and search.

Experience in programming with C, C++ or Rust is required. Familiarity with any kind of optimisation, including mixed integer programming, constraint programming, local search, etc. will be beneficial.