Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
Ruin-and-recreate heuristics for the fixed charge transportation problem
Thesis (PhD)--Stellenbosch University, 2025.
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | English |
| Published: |
Stellenbosch : Stellenbosch University
2025
|
| Subjects: | |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1867613763510730752 |
|---|---|
| access_status_str | Open Access |
| author | Le Roux, Gavin James |
| author2 | Visagie, S. E. |
| author_browse | Le Roux, Gavin James Visagie, S. E. |
| author_facet | Visagie, S. E. Le Roux, Gavin James |
| author_sort | Le Roux, Gavin James |
| collection | Thesis |
| dc_rights_str_mv | Stellenbosch University |
| description | Thesis (PhD)--Stellenbosch University, 2025. |
| format | Thesis |
| id | oai:scholar.sun.ac.za:10019.1/134671 |
| institution | Stellenbosch University (South Africa) |
| language | English |
| last_indexed | 2026-06-10T12:41:19.170Z |
| license_str | Other — see source repository |
| provenance_str_mv | Harvested via OAI-PMH from SUNScholar — Stellenbosch University Repository |
| publishDate | 2025 |
| publishDateRange | 2025 |
| publishDateSort | 2025 |
| publisher | Stellenbosch : Stellenbosch University |
| publisherStr | Stellenbosch : Stellenbosch University |
| record_format | dspace |
| source_str | SUNScholar — Stellenbosch University Repository |
| spelling | oai:scholar.sun.ac.za:10019.1/134671 Ruin-and-recreate heuristics for the fixed charge transportation problem Le Roux, Gavin James Visagie, S. E. Stellenbosch University. Faculty of Economic and Management Sciences. Dept. of Logistics. Transportation problems (Programming) Combinatorial optimization Linear programming Metaheuristics Heuristic algorithms UCTD Thesis (PhD)--Stellenbosch University, 2025. Le Roux, G. J. 2025. Ruin-and-recreate heuristics for the fixed charge transportation problem. Unpublished doctoral dissertation. Stellenbosch: Stellenbosch University [online]. Available: https://scholar.sun.ac.za/items/15294dd1-191f-46e1-9c19-5d709552ab4a ENGLISH SUMMARY: The fixed charge transportation problem (FCTP) is an extension of the classical transportation problem and the fixed charge problem. It involves determining an optimal allocation of units along arcs from a set of origins (or supply points) to a set of destinations (or demand points). The network is therefore represented as a directed bipartite graph. Every arc is associated with a variable cost as well as a fixed charge that is incurred if the arc is activated. The objective is to minimise the total cost while ensuring that all supplied units leave the origins and all demand is met at the destinations. In this dissertation, various ruin-and-recreate (R&R) heuristics are developed for the FCTP. Constructive heuristics are initially introduced, laying the groundwork for their integration into the recreate phase of R&R heuristics. The least cost method (LCM), Vogel’s approximation method and Russell’s approximation method are modified to use metric values as opposed to the variable costs. Six new metrics to determine the arcs in which units of flow should be increased, are developed. The R&R heuristic incorporating a local improvement method (in the form of the simplex algorithm) and threshold acceptance as a means to accept or reject a solution in each iteration, is then developed. Four ruin methods, namely arcs removal, vertices removal, multipath removal and subtree removal, are proposed to subtract units of flow from randomly selected arcs during the ruin phase. The heuristics are then expanded to embody memory. The ruin methods are modified so that arcs that have a higher cost per unit have a greater chance of being ruined. Metropolis ac-ceptance is then tested as a stochastic alternative to threshold acceptance. This is followed by learning and forgetting curves that are formulated for FCTPs and optimisation problems in general. Finally, all the developed heuristics are combined into variable R&R heuristics. In each iteration, a random heuristic is selected to be executed on the current solution, similar to variable neighbourhood search. Variants that integrate adaptiveness, incorporate memory and vary the recreate method, are designed. These are then extended to heuristics that combine multiple variants. The heuristics were tested on 50 instances known from literature and 75 newly generated in-stances. Computational results demonstrate that the R&R heuristic employing subtree removal as the ruin method, LCM as the recreate method and the simplex algorithm as the local im-provement method, achieved some of the most favourable outcomes. On average, its solutions are 8.7% better than those attained by CPLEX for instances larger than 75 × 75 (challenging problems). Memory-based R&R heuristics show an improvement, beating CPLEX by 10.2% for challenging instances. Variable R&R heuristics are competitive with memory-based R&R heuristics, returning solutions that are 2.2% better than those by CPLEX across all instances and displaying an improvement of 9.8% over CPLEX for challenging instances. AFRIKAANSE OPSOMMING: Die vastekoste-vervoerprobleem (VKVP) is ’n uitbreiding van die klassieke vervoerprobleem en die vastekoste-probleem. Dit behels die bepaling van ’n optimale toekenning van eenhede langs boevanaf ’n stel oorspronge (of aanbodpunte) na ’n stel bestemmings (of aanvraagpunte). Die netwerk word dus as ’n gerigte tweeledige grafiek voorgestel. Elke boog word geassosieer met ’n veranderlikekoste sowel as ’n vastekoste wat aangegaan word as die boog geaktiveer word. Die doelwit is om die totale koste te minimeer, terwyl verseker word dat alle verskafde eenhede die oorsprong verlaat en alle aanvraag by die bestemmings voldoen word. In hierdie proefskrif word verskeie ruıneer-en-herskep (R&H) heuristieke vir die VKVP ontwikkel. Konstruktiewe heuristieke word aanvanklik bekendgestel, wat die grondslag le vir hul integrasie in die herskepfase van R&H heuristieke. Die minstekostemetode (MKM), Vogel se benaderingsmetode en Russell se benaderingsmetode word aangepas om metriekwaardes te gebruik in teenstelling met die veranderlikekostes. Ses nuwe metrieke om die boe te bepaal waarin eenhede van vloei verhoog moet word, word ontwikkel. Die R&H heuristiek wat ’n plaaslike verbeteringsmetode (in die vorm van die simpleksalgoritme) en drempelaanvaarding as ’n manier om ’n oplossing in elke iterasie te aanvaar of te verwerp, word dan ontwikkel. Vier ruıneringsmetodes, naamlik boe-verwydering, nodusse-verwydering, multipad-verwydering en subboom-verwydering, is voorgestel om eenhede van vloei van lukraak geselekteerde boe tydens die ruıneringsfase af te trek. Die heuristiek word dan uitgebrei om geheue te beliggaam. Die ruıneringsmetodes word aangepas sodat boe wat ’n hoer koste per eenheid het, ’n groter kans het om geruıneer te word. Metropolisaanvaarding word dan getoets as ’n stogastiese alternatief vir drempelaanvaarding. Hierdie word gevolg deur leer- en vergeetkurwes wat vir VKVP’s en optimeringsprobleme in die algemeen geformuleer word. Ten slotte word al die ontwikkelde heuristieke gekombineer in veranderlike R&H heuristieke. In elke iterasie word ’n heuristiek lukraak gekies om op die huidige oplossing uitgevoer te word, soortgelyk aan veranderlike buurtsoektog. Variante wat aanpasbaarheid integreer, geheue inkorporeer en die herskeppingsmetode afwissel, word ontwerp. Dit word dan uitgebrei na heuristieke wat verskeie variante kombineer. Die heuristieke is op 50 gevalle wat uit die literatuur bekend is en 75 nuutgegenereerde gevalle getoets. Berekeningsresultate toon dat die R&H heuristiek wat subboom-verwydering as die ruıneringsmetode, MKM as die herskeppingsmetode en die simpleksalgoritme as die plaaslike verbeteringsmetode gebruik, van die gunstigste uitkomste behaal het. Sy oplossings is gemiddeld 8.7% beter as die wat deur CPLEX behaal word vir gevalle groter as 75 × 75 (uitdagende probleme). Geheue-gebaseerde R&H heuristieke toon ’n beduidende verbetering en klop CPLEX met 10.2% vir uitdagende gevalle. Veranderlike R&H heuristieke is mededingend met geheuegebaseerde R&H heuristieke. Dit gee oplossings wat 2.2% beter as die deur CPLEX oor alle gevalle is en toon ’n verbetering van 9.8% bo CPLEX vir uitdagende gevalle. Doctoral 2025-12-23T06:25:42Z 2025-12-23T06:25:42Z 2025-12 Thesis https://scholar.sun.ac.za/handle/10019.1/134671 en Stellenbosch University xl, 354 pages : illustrations, includes annexures application/pdf Stellenbosch : Stellenbosch University |
| spellingShingle | Transportation problems (Programming) Combinatorial optimization Linear programming Metaheuristics Heuristic algorithms UCTD Le Roux, Gavin James Ruin-and-recreate heuristics for the fixed charge transportation problem |
| title | Ruin-and-recreate heuristics for the fixed charge transportation problem |
| title_full | Ruin-and-recreate heuristics for the fixed charge transportation problem |
| title_fullStr | Ruin-and-recreate heuristics for the fixed charge transportation problem |
| title_full_unstemmed | Ruin-and-recreate heuristics for the fixed charge transportation problem |
| title_short | Ruin-and-recreate heuristics for the fixed charge transportation problem |
| title_sort | ruin and recreate heuristics for the fixed charge transportation problem |
| topic | Transportation problems (Programming) Combinatorial optimization Linear programming Metaheuristics Heuristic algorithms UCTD |
| url | https://scholar.sun.ac.za/handle/10019.1/134671 |
| work_keys_str_mv | AT lerouxgavinjames ruinandrecreateheuristicsforthefixedchargetransportationproblem |