Complexe varianten van het klassieke rittenplanningsprobleem

Abstract

Voor bedrijven wordt het steeds belangrijker om goederen efficiënt te vervoeren naar klanten en rittenplanningen spelen hierbij een grote rol. Bij rittenplanningen worden immers routes geconstrueerd en toegewezen aan voertuigen. Methoden die een optimale oplossing voorzien voor dit probleem zijn vaak onbestaand, complex en/of tijdrovend. In de praktijk is echter op zeer korte termijn nood aan rittenplanningen en dus moeten er heuristieken gevonden worden die realistische en dus complexe rittenplanningsproblemen kunnen oplossen. Heuristieken zijn algoritmes die op een snelle manier een goede benadering van de optimale oplossing geven.

Deze thesis start met een beschrijving van de verschillende complexe beperkingen die in rekening worden gebracht bij rittenplanningsproblemen. Daarna wordt gefocust op rittenplanningen met een heterogene vloot en meerdere depots. Definities en oplossingsmethodes omtrent deze beperkingen worden grondig beschreven. Eerst worden de twee beperkingen afzonderlijk bekeken zodat een voldoende begrip van beide subproblemen verkregen wordt. Vervolgens zal het rittenplanningsprobleem bekeken worden waarbij beide beperkingen gecombineerd zijn. Uiteindelijk wordt de theorie toegepast op een praktijkprobleem. Drie verschillende heuristieken worden toegepast op numerieke voorbeelden en deze heuristieken worden vervolgens met elkaar vergeleken. De gebruikte heuristieken zijn de efficiëntieratiomethode, de methode waarbij de goedkoopste combinatie van voertuigen gekozen wordt en de besparingsmethode.