Penerapan algoritma genetika dalam penyelesaian Travelling Salesman Problem with Precedence Constraints (TSPPC) / Yayun Hardianti
| Main Author: | Hardianti, Yayun |
|---|---|
| Format: | Thesis NonPeerReviewed |
| Terbitan: |
, 2013
|
| Subjects: | |
| Online Access: |
http://repository.um.ac.id/17332/ |
Daftar Isi:
- HardiantiYayun.2013.PenerapanAlgoritmaGenetikadalamPenyelesaianTravellingSalesmanProblemwithPrecedenceConstraints(TSPPC).SkripsiJurusanMatematikaFakultasMatematikadanIlmuPengetahuanAlamUniversitasNegeriMalang.PembimbingProf.Drs.PurwantoPh.D.KataKunciAlgoritmaGenetikaTravellingSalesmaProblemWithPrecedenceConstraints(TSPPC)TravellingSalesamProblem(TSP)merupakanpermasalahanseorangsalesyangharusmengunjungibeberapakotadanharusmelaluisetiapkotatersebuttepatsatukalidankembalilagikekotaawaldenganjaraktempuhdanbiayaminimal.PermasalahnTSPselamainihanyamelihatjarakantaradepotdenganpelangganatauantarpelanggansajapadahalpadakenyataanyapermasalahandistribusitidakhanyapadajaraktetapijugaadanyaurutantitikyangharusdikunjungiterlebihdahulusebelumtitikyanglain.UntukmemecahkanmasalahtersebutTSPdikembangkanmenjadiTSPPCatauTravellingSalesmanProblemwithPrecedenceConstraints.TSPPCmerupakanpermasalahanuntukmencariperjalananterpendekmelaluisemuatitikdantiaptitikdilewatitepatsatukalidengantambahankendalayaituadanyaurutantitikyangharusdikunjungiterlebihdahulu(precedenceconstraints).TSPPCdapatdimodelkandalambentukgraphnetwork.Dengantitiksebagaikotadansisiberarahsebagaiprecedencerelation.SalahsatumetodeyangdigunakandalammenyelesaiakanTSPPCadalahdenganmenggunakanalgoritmagenetika.Algoritmagenetikaadalahalgoritmapencarianheuristikyangdidasarkanatasmekanismeevolusibiologis.TahapanpenyelesaianTSPPCdenganalgoritmagenetikayaitutahapinisialisasi(pembentukanpopulasiawal)tahapperhitungannilaifitnestahappemilihan(seleksi)denganRoulleteWheeltahappindahsilangdenganmooncrossoverdantahapmutasi(swappingmutation).Untukmengatasiprecedenceconstraintsalgoritmagenetikadigabungkandengankonseptopologicalsortdalammenentukanlintasanyangfisibel.Topologicalsortadalahteknikmengurutkantitik-titikpadagraphberarahsedemikiansehinggajikaterdapatlintasandarivikevjmakavjdilaluisetelahvi.UntukmemudahkandalammencaripenyelesaianTSPPCterutamasaatharusmengunjungibanyakkotaalgoritmagenetikadiimplementasikandalambahasapemrogramanBorlandDelphi7.DarihasilanalisisdidapatbahwaalgoritmagenetikayangdigabungkandengankonseptopologicalsortmampumanghasilkanlebihdarisatualternativesolusiuntukTSPPC.PerhitungansecaramanualmenunjukkanalgoritmagenetikamampumenyelesaikanpermasalahanTSPPCdengan6dan10titik.PerhitungandenganmenggunakanprogramGA-TSPPCmampumenyelesaikanpermasalahanTSPPC50titikdan20generasi