Het kwadratisch kortste pad probleem (KKPP) is een NP-hard probleem dat een pad zoekt tussen twee knopen in een gerichte graaf zodat de som van alle interactiekosten tussen de samenstellende bogen van het pad minimaal is. Voorgaande auteurs hebben algoritmen verkregen voor het oplossen van een KKPP, al zijn die vaak beperkt tot specifieke gevallen en voor verbetering vatbaar. Dit onderzoek oogt een algoritme te ontwikkelen dat algemene instanties van het KKPP kan oplossen op een efficiëntere manier dan andere auteurs.
De prestatie van het ontwikkelde algoritme zal grondig geanalyseerd worden. We zullen de resultaten vergelijken met die van andere auteurs. Een eerlijke vergelijking vereist een implementatie van hun algoritmen en een relevante testset van grafen. Een vergelijking zal ook gemaakt worden met de prestatie van algemene oplossers, zoals Integer Linear Programming software, toegepast op het KKPP.
In een tweede deel van het onderzoek zullen we problemen identificeren die gerelateerd zijn aan het KKPP. Een voorbeeld is de uitbreiding naar meerdere tak-disjuncte kortste paden. We zullen onderzoeken hoe goed het KKPP algoritme presteert wanneer het rechtstreeks wordt toegepast op deze gerelateerde problemen. We zullen ook focussen op het ontwikkelen van nieuwe algoritmen, elk geoptimaliseerd voor een specifiek gerelateerd probleem. Die zullen een basisprestatie geven, die toekomstige auteurs kunnen verbeteren, want veel verwante problemen zijn nog niet eerder onderzocht.