M.A. Davids
Ontwikkeling van een Pascal-programma voor het Traveling Purchaser Probleem.
Computeropdracht,
Rapport 97.3.LT.4906, Transporttechnologie, Logistieke Techniek.
"Implementeer de methode voor de behandeling van het Traveling Purchaser
Probleem (TPP) in K.N. Singh en D.L. van Oudheusden "A branch and bound
algorithm for the traveling purchaser problem" (European Journal of
Operational Research, vol.97 (1997) pp.571-579)" was de opdracht
Logistieke Informatica waarvan dit rapport verslag doet.
Bij het Traveling Purchaser Probleem moet
een inkoper n gegeven artikelen kopen in een deelverzameling van m gegeven
plaatsen. Ook gegeven zijn de kosten van een artikel in een plaats en
de reiskosten van een plaats naar een andere plaats. Het probleem is het
vinden van een rondreis voor de inkoper zodanig dat de
som van reis- en artikelkosten minimaal is.
Het TPP is een abstractie van het Traveling Salesman
Probleem (TSP, bepaal een optimale rondreis langs een aantal plaatsen)
en heeft een aspect (selecteer een deelverzameling uit de verzameling
van m plaatsen voor de rondreis) dat overeenkomt met een Simple
Plant Location Probleem (SPLP). Singh en Van Oudheusden combineren
bestaande algorithmes voor het TSP en SPLP tot een Branch-and-Bound
algorithme dat een exacte oplossing voor het TPP vindt.
Na het ontwikkelen van Pascalalgorithmes in pseudocode
is het Pascalprogramma PASTPP geschreven dat een TPP tot een omvang van
6 plaatsen en 100 artikelen in maximaal enkele seconden oplost.
Hierbij wordt het SPLP door PASTPP op algemene wijze opgelost.
Singh en Van Oudheusden gebruiken een specifiek SPLP-algorithme
waarmee zij een TPP met 25 plaatsen en 100 artikelen in
een aanvaardbare tijd oplossen. Van dit algorithme is wel een
FORTRAN-versie maar geen Pascalversie beschikbaar. De aanbeveling is
dan ook deze te ontwikkelen, waarmee de prestatie van PASTPP sterk toe
zal nemen.
Rapporten studenten Logistieke Techniek
Gewijzigd: 1997.09.16;
logistics@3mE.tudelft.nl
, TU Delft
/ 3mE
/ TT
/ LT.