Dynamic programming approaches for the traveling salesman problem with drone

Bouman, P., Agatz, N., & Schmidt, M. · 2018

full-text

Los van het heuristische artikel van dezelfde auteurs pakt dit artikel het TSP-D exact aan met dynamisch programmeren. Het paar wordt geciteerd wanneer men bespreekt hoe grote instanties exact opgelost kunnen worden. Het algoritme is niet opnieuw geïmplementeerd.

Het presenteert exacte methoden met dynamisch programmeren en meldt dat ze grotere problemen oplosten dan de benaderingen met wiskundig programmeren die toen in de literatuur stonden. Door te beperken hoeveel locaties de vrachtwagen mag bezoeken terwijl de drone weg is, daalt de oplostijd naar verluidt aanzienlijk, met een relatief klein effect op de kwaliteit van de oplossing.

“Groter” is relatief ten opzichte van exacte methoden van die tijd, niet ten opzichte van de omvang van een dagelijkse operationele VRP. Het toevoegen van de beperking geeft over het algemeen een garantie van optimaliteit op. Lees dat punt als de experimentele waarneming van het artikel.