Algoritma Variable Nighborhood Descent (VND) pada Vehicle Routing Problem with Time Windows (VRPTW) dan implementasinya / Vivi Ratnasari
| Main Author: | Ratnasari, Vivi |
|---|---|
| Format: | Thesis NonPeerReviewed |
| Terbitan: |
, 2018
|
| Subjects: | |
| Online Access: |
http://repository.um.ac.id/17257/ |
Daftar Isi:
- RatnasariVivi.2018.AlgoritmaVariableNeighborhoodDescent(VND)padaVehicleRoutingProblemwithTimeWindows(VRPTW)danImplementasinyaSkripsiJurusanMatematikaFakultasMatematikadanIlmuPengetahuanAlamUniversitasNegeriMalang.Pembimbing(I)Dra.SaptiWahyuningsihM.Si.(II)DarmawanSatyanandaS.TM.T.KataKuncidistribusigraphvehicleroutingproblemwithtimewindows(VRPTW)variableneighborhooddescent(VND).Pemilihanrutemerupakansalahsatuaspekpentingdalambidangpendistribusian.PermasalahanpenentuanruteyangditempuholehkendaraandistribusidalamteorigraphdikenaldenganVehicleRoutingProblem(VRP).SalahsatuvarianVRPdengantambahankendalatimewindowsuntuksetiapcustomeradalahVRPTW.PermasalahanVRPTWdapatdiselesaikandenganmenggunakanalgoritmaVariableNeighborhoodDescent(VND).TeknikyangdigunakanalgoritmaVNDuntukmenyelesaikanpermasalahanVRPTWadalahdenganmemberikanhimpunanstrukturneighborhooduntuksuatusolusiawalkemudianmemeriksakeoptimalandarisolusiawalmenggunakanstrukturneighborhoodtersebut.LangkahpertamadalamalgoritmaVNDadalahmembentuksolusiawalmenggunakanalgoritmaNearestNeighbor.Langkahkeduaadalahmengujikeoptimumansolusiawaldengancaramelakukanpertukaranposisicustomerdarisolusiawalmenggunakanenamstrukturneighborhooddiantaranyaswap(1-1)swap(2-1)swap(2-2)insertionexchangedan2-optsecaraberurutan.Solusidariprosespertukarandibandingkandengansolusiawaluntukmengetahuisolusimanayangmemberikanhasilyanglebihbaik.Langkahkeduatersebutdilakukansecaraberulangsampaidiperolehkondisioptimum.Kondisioptimumtercapaisaatsemuastrukturneighborhoodtelahdilewatidanmenghasilkansolusi-solusiyangkonvergenkesuatunilaiyangminimum.ImplementasialgoritmaVNDuntukVRPTWdirancangdalambahasapemrogramanBorlandDelphi7.0.BerdasarkancontohpermasalahanyangtelahdibahaspenyelesaianVRPTWmenggunakanalgoritmaVNDmenghasilkansolusiyanglebihbaikdengantotalwaktutempuhyanglebihpendekdibandingkandenganalgoritmaMultipleAntColonySystem(MACS)danalgoritmaModifiedSavingwithExchangeLocalSearch(MS-ELS).BerdasarkanujicobaprogramyangtelahdilakukanmenggunakandatatitikyangsamadiperolehhasilbahwaaplikasiVND-VRPTWmenghasilkanrutedengantotalwaktulebihpendeksecaraberturut-turutadalah358%264%1215%101%dan675%dibandingkanruteyangdihasilkanolehaplikasiTSP-VRP.AplikasiVND-VRPTWjugamenghasilkanrutedengantotalwaktulebihpendeksecaraberturut-turutadalah2129%185%1153%2271%dan731%dibandingkanruteyangdihasilkanolehaplikasiMACS-MDVRPTW.