algoritma general variable neighborhood search (gvns) pada vehicle routing problem with simultaneous delivery and pick-up (vrpsdp) dan implementasinya / dyah ayu retno widiari lintang manggali putri
| Main Author: | Putri, Dyah Ayu Retno Widiari Lintang Manggali Putri |
|---|---|
| Format: | Thesis NonPeerReviewed |
| Terbitan: |
, 2021
|
| Online Access: |
http://repository.um.ac.id/148516/ |
Daftar Isi:
- Matematikamerupakansalahsatuilmupengetahuanyangpenerapannyadapatdigunakanuntukmenyelesaikanpermasalahandalamkehidupansehari-harisepertimenentukanrutependistribusian.PermasalahantersebuttermasukdapatdiselesaikandengansalahsatucabangilmumatematikayaituteorigrafkhususnyapadamateriVehicleRoutingProblem(VRP).VehicleRoutingProblemwithSimultaneousDeliveryandPickup(VRPSDP)merupakanperluasandariVRPyangmemilikikendalakhususyaitupermintaandanpengembaliandilakukansecarabersamaan.PadapenelitianiniAlgoritmayangdigunakandalammenyelesaikanVRPSDPadalahAlgoritmaGeneralVariableNeighborhoodSearch(GVNS)yangterdiridaribeberapatahapanyaitupembentukansolusiawaldenganAlgoritmaInsertionHeuristictahapperturbasidantahapanperbaikansolusidenganAlgoritmaRVND.ImplementasidarialgoritmatersebuttelahdibuatdenganmenggunakanaplikasiBorlandDelphi7sebagaialatbantuperhitungan.Programtersebuttelahdiujicobakandenganmenggunakan6customer10customer30customer75customer100customerserta4dataset.Outputyangdihasilkanprogramadalahberuparuteyangterbentukbesertajaraktempuhnyadanvisualisasidarirutetersebut.Hasilyangdiperolehdaripermasalahan6customeradalahsebesar266kmyangkemudiandibandingkandenganAlgoritmaReactiveGreedyRandomizedAdaptiveSearch(RGRASP)yangmenghasilkansolusi361km.HaltersebutmenyatakanbahwaAlgoritmaGVNSmenghasilkansolusiyanglebihbaikdibandingkandenganAlgoritmaRGRASP.KemudianberdasarkanhasilujicobadatasetmenggunakanperbandinganantaraAlgoritmaGVNSdenganAlgoritmaTabuSearchdiketahuibahwadatasetc101yangdiselesaikandenganmenggunakanAlgoritmaGVNSmemilikisolusi1296126dengannilaigapyaitu0029%darisolusiAlgoritmaTabuSearchuntukujicobadatasetr101menghasilkansolusi1090529dengannilaigapyaitu0046%.Begitujugadengandatasetc1_2_1yangdiselesaikandenganAlgoritmaGVNSmenghasilkansolusi4060651memilikigap070%dandatasetr1_2_1yangmenghasilkansolusi3715843dengannilaigapyaitu0078%.SehinggaberdasarkandatatersebutdapatdiketahuibahwasolusiyangdihasilkandatasetmelaluiujicobadenganAlgoritmaGVNSmemilikisolusitotaljarakyangsedikitlebihjauhjikadibandingkandenganAlgoritmaTabuSearchdannilairata-ratagapdarikeduaalgoritmaadalah005%.ArtinyaselisihhasilyangdihasilkanAlgoritmaGVNSsangatkompetitifdenganrentangnilaipersentasegapantara0029%sampai0078%.