Algoritma Variable Neighborhood Descent (VND) pada Multiple Trip Vehicle Routing Problem (MTVRP) dan implementasinya / Pratiwi Ratih Dewi
| Main Author: | Dewi, Pratiwi Ratih |
|---|---|
| Format: | Thesis NonPeerReviewed |
| Terbitan: |
, 2017
|
| Subjects: | |
| Online Access: |
http://repository.um.ac.id/17250/ |
Daftar Isi:
- ABSTRAKDewiPratiwiRatih.2017.AlgoritmaVariableNeigborhoodDescent(VND)padaMultipleTripVehicleRoutingProblem(MTVRP)danImplementasinyaJurusanMatematikaFakultasMatematikadanIlmuPengetahuanAlamUniversitasNegeriMalang.Pembimbing(1)Dra.SaptiWahyuningsihM.Si.(II)DarmawanSatyanandaS.TM.T.KataKuncigraphvehicleroutingproblem(VRP)MultipleTripVehicleRoutingProblem(MTVRP)SequentialInsertionVariableNeighborhoodDescent(VND)localsearchdistribusi.Prosespendistribusianberkaitaneratdenganpemilihanrutedistribusisehinggadiperolehruteyangoptimumdenganbiayapendistribusianminimum.Modelpendistribusianbervariasisesuaidenganbatasanyangharusdipenuhisalahsatunyaadalahbataswaktuoperasi.VarianVehicleRoutingProblem(VRP)yangdibatasiolehwaktuoperasiadalahMultipleTripVehicleRoutingProblem(MTVRP)dimanakendaraandapatmenempuhbeberaparuteselamaperiodewaktutertentu.PencarianruteterpendekpadaMTVRPmelibatkansolusiawalyangkemudiandiperbaikandenganlocalsearch.VariableNeighborhoodDescent(VND)merupakanvarianpalingsederhanadariVariableNeighborhoodSearch(VNS)yangmenampilkanbeberapaturunandenganneighborhoodberbeda.LangkahpertamaalgoritmaVNDyaitumembentuksolusiawalmenggunakanalgoritmaSequentialInsertion.LangkahkeduaadalahtahapperbaikanlocalsearchmenggunakanprosedurVNDdenganenamstrukturneighborhoodyangdilakukansecaraberurutan(1-insertionintraroute(N_1)1-insertioninter-route(N_2)1-1swap(N_3)2-0shift(N_4)2-2swap(N_5)2-1swap(N_6))darineighborhood1sampaineighborhood6hinggadiperolehkondisioptimum.Kondisioptimumtercapaisaatstrukturneighborhoodtelahdilewatisemuadantidakdapatdilakukanperbaikanlagi.SecaraumumsolusiawalyangdiperolehdarialgoritmaSequentialInsertionsetelahdiperbaikidenganVNDmenghasilkansolusibaruyanglebihbaikyaituwaktutempuhyanglebihpendekdariwaktutempuhawal.ImplementasidarialgoritmaVNDuntukMTVRPdalambahasapemrogramanBorlandDelphi7.0berhasildirancangsecaraterstruktur.Aplikasidiujicobauntukkasus10titik13titik21titikdan31titik.