Penggunaan metode farthest insertion heuristic dan metode arbitrary insertion heuristic dalam menyelesaikan traveling salesman problem / Dian Ayu Anggraeni
| Main Author: | Dian Ayu Anggraeni |
|---|---|
| Format: | Thesis NonPeerReviewed |
| Terbitan: |
, 2009
|
| Subjects: | |
| Online Access: |
http://repository.um.ac.id/16775/ |
Daftar Isi:
- Teorigraphmerupakansalahsatucabangmatematikayangbanyakbermanfaatkerenadenganmenggunakanrumusanataumetodedariteorigraphyangtepatmakakitadapatmenyelesaikansuatumasalahlebihmudah.SalahsatumasalahyangdapatdiselesaikandenganbantuanteorigraphadalahTravelingSalesmanProblem(TSP).TSPmerupakansuatumasalahdalammenemukansikelHamiltondenganjumlahbobotsisiminimum.TerdapatbeberapametodeyangdapatdigunakandalammenyelesaikanmasalahTSP.MetodeyangakandibahasdalammenentukansikelHamiltonadalahmetodeFarthestInsertionHeuristicdanArbitraryInsertionHeuristic.MetodeFarthestInsertionHeuristicinimembangunsuatutourdarisikelkecildenganbobotmaksimaldansecaraberturut-turutditambahdengantitikbaruyangterjauhdarisikel.Titikbarutersebutdisisipkandiantaraduatitikdalamsikelyangmempunyainilaipenyisipanyangminimum.SedangkanMetodeArbitraryInsertionHeuristicmembangunsuatutourdarisikelkecildenganbobotminimumdansecaraberturut-turutditambahdengantitikbaruyangdipilihsecarasembarangdantidakdalamsikel.Titikbarutersebutdisisipkandiantaraduatitikdalamsikelyangmempunyainilaipenyisipanyangminimum.PadaskripsiinikeduametodeakandibandingkandenganmetodeCheapestLinkNearestNeighborHeuristicdanmetodeNearestInsertionHeuristic.Solusiyangdiperolehdenganmenggunakankelimametodetersebutdapatberbedahalinidikarenakanperbedaankonstruksiataulangkah-langkahpadamasing-masingmetodedalammenemukansikelHamiltondenganbobotminimum.DengandemikianmetodeFarthestInsertionHeuristicdanArbitraryInsertionHeuristicdapatdigunakansebagaialternatifuntukmencarisikelHamiltonselainmetodeCheapestLinkNearestNeighborHeuristicdanmetodeNearestInsertionHeuristic.AgarlebihmudahdalammenyelesaikanTSPmetodeFarthestInsertionHeuristicdanArbitraryInsertionHeuristicdapatdirepresentasikandalamprogramkomputeryaitumenggunakanBorlandDelphi.