< Back to previous page

Project

Combinatorial bounds for heuristic neighbourhood search

Most exact combinatorial optimization algorithms provide an optimalityproof or a gap to a lower bound on the optimum, along with a solution fora minimization problem. Unfortunately, many real-world problems are toochallenging for exact algorithms to effectively compute a solution.Heuristics like local search-based methods do not provideoptimality proofs or optimality gaps. Nevertheless, they are often moresuccessful in terms of computing acceptable solutions for difficult problems.This project will improve heuristic search by developing bounding methodsinspired by linear programmingrelaxations and valid inequalities. It involves two parallel research lines: onefocusing on exact methods to produce general heuristic methodologies andanother which addresses heuristic data structures with a view to reducing localsearch neighbourhoods. The new methodologies will be developed whileinvestigating two industrial cases: a vehicle routing problem with loadingrestrictions and a warehouse operator scheduling problem. Targeted academicresults will include new lower bounding methods for heuristic search andmore efficient local search thanks to neighbourhood filtering.The research group develops better search algorithms and considerably expands the industrial applicability of operational decision support.
Date:1 Jan 2021 →  31 Dec 2022
Keywords:Combinatorial optimization
Disciplines:Operations research and mathematical programming