Technische Universiteit Delft
Faculteit Werktuigbouwkunde, Maritieme Techniek en Technische Materiaalwetenschappen
Transporttechnologie /
Logistieke Techniek
G.C. van der Vlist
Een heuristische tabu search methode voor het transportprobleem met vaste
kosten.
Computeropdracht,
Rapport 98.3.LT.5100, Transporttechnologie, Logistieke Techniek.
Voor de meeste transportproblemen geldt in werkelijkheid vaak dat naast de
variabele kosten ook vaste kosten een rol spelen. Dit transportprobleem
met vaste kosten kan op twee manieren opgelost worden. Door een exact
algoritme of door een benadering met een heuristische methode. Nadeel van
een exact algoritme is dat grotere problemen niet meer te behandelen zijn.
Nadeel van een heuristische zoekmethode is daarentegen dat soms als
oplossing een lokaal minimum wordt gevonden dat niet gelijk is aan het
globale minimum. Sun ea. (M.Sun, J.E. Aronson, P.G. McKeown, D. Drinka, "A tabu
search heuristic procedure for the fixed charge transportation problem",
European Journal of Operational Research, Vol.106 nr.2-3 (1998) pp.441-456)
ontwikkelden een heuristische tabu search methode die vergeleken met andere
heuristische methoden veel sneller een betere oplossing genereert.
Om een zo goed mogelijk resultaat te krijgen moet er voor worden gezorgd
dat zo veel mogelijk verschillende oplossingen worden bekeken. Hiervoor
wordt met behulp van een flexibel werkgeheugen bepaalde oplossingen een
voorkeursbehandeling gegeven en andere ontmoedigd of verboden. Het
verbieden van een stap gebeurt door te bepalen of een stap taboe is. Deze
taboe status wordt bepaald door te eisen dat een tak minimaal
Nin stappen achtereenvolgens tot de oplossing moet behoren
of Nout stappen achtereenvolgens buiten de oplossing moet blijven.
De heuristische tabu search methode bestaat uit drie onderdelen. Deze
zorgen er op verschillende wijze voor dat de oplossing in een ander
zoekgebied terecht komt. De drie onderdelen zijn achtereenvolgens korte
termijn, middellange termijn en lange termijn. In vergelijking met
het korte termijn onderdeel worden in middellange termijn onderdeel takken
die relatief vaak tot de oplossing behoren aantrekkelijker gemaakt. In het
lange termijn onderdeel worden echter de takken die relatief weinig tot de
oplossing behoren aantrekkelijker gemaakt.
Van de heuristische tabu search methode is in Matlab een implementatie
gemaakt. Uitvoeren hiervan leert dat voor grotere vraagstukken een
vertaalslag richting C++, Fortran of Pascal moet worden gemaakt want
Matlab is relatief langzaam.
Rapporten studenten Logistieke Techniek
Gewijzigd: 1998.12.02;
logistics@3mE.tudelft.nl
, TU Delft
/ 3mE
/ TT
/ LT.