Implementasi algoritma branch and bound pada distance constrained capacitated vehicle routing problem (DCVRP) / Reny Magfiroh
| Main Author: | Magfiroh, Reny |
|---|---|
| Format: | Thesis NonPeerReviewed |
| Terbitan: |
, 2015
|
| Subjects: | |
| Online Access: |
http://repository.um.ac.id/17409/ |
Daftar Isi:
- ABSTRAKMaghfirohReny.2015.ImplementasiAlgoritmaBranchandBoundpadaDistanceConstarinedCapacitedVehicleRoutingProblem(DCVRP).SkripsiJurusanMatematikaFMIPAUniversitasNegeriMalang.PembimbingDra.SusyKuspambudiAndainiM.Kom.KataKunciConstarinedCapacitedVehicleRoutingProblem(DCVRP)AlgoritmaBranchandBoundBorlandDelphi7.0.Dalamgraphterdapatberbagaiteoriyangdapatditerapkanpadapermasalahanyangterjadidikehidupansehari-haribeberapadiantaranyaadalahShortestPathTravellingSalesmanProblem(TSP)danVehicleRoutingProblem(VRP).SuatushortestpathyangmelaluisemuatitikdalamsuatugraphdankembaliketitikawaldisebutTSP.SuatuTSPmenghasilkancycletunggal.TSPyangmenghasilkancyclelebihdarisatudisebutVRP.SalahsatuperluasandariVRPadalahDistanceConstarinedCapacitedVehicleRoutingProblem(DCVRP).DCVRPmerupakanpermasalahanpenentuanruteoptimalkendaraandalammelayanicustomerdenganbatasankapasitaskendaraandanditambahsatubatasanlagiyaitujaraktempuhkendaraan.Kendaraantersebutberangkatdankembalipadadepotyangsama.AlgoritmaBranchandBounddariTSPdimodifikasisedemikiansehinggadapatditerapkanpadaDCVRP.DalampenyelesaianDCVRPdenganmenggunakanalgoritmaBranchandBoundterdapat3tahap.Tahappertamaujijarakcustomertahapkeduaujikapasitascustomer.Customeryanglolospadatahapujipertamadankeduaakanmasukpadatahapterakhiryaitupembentukanrute.Ketentuanpadatahapujijarakcustomeradalahduakalijaraksetiapcustomerterhadapdepotkurangdarijarakmaksimal.Sedangkanuntukujikapasitaspermintaansetiapcustomerdisyaratkankurangdarikapasitasmaksimal.Selanjutnyauntukprosesditahappembentukanruteyaitudepotselaludipilihsebagaititikawalrute.Kemudianmemilihduacustomerdenganjarakterdekatkedepotsecaraberurutancustomerterpilihdiujikapasitas.Customeryangmemenuhiujikapasitasdanmemilikijarakterpendekadalahyangdipilihuntukmasukpadarute.Prosesiniberlanjutsampaisalahsatubatasandilanggar.Ketikabatasandilanggarmakadibentukrutebarudenganprosesyangsama.Prosesberhentisaatsemuacustomeryangmasukpadatahappembentukanrutetelahmasukpadarute.ImplementasialgoritmaBranchandBoundterhadapbahasapemrogramanBorlandDelphi07dirancangsecaraterstrukturdalamartianprogramdisusundalambentukprocedure-procedure.Programdiujicobamenggunakan6102052sampai100titik.Eksekusiprogramtanpaadakendala.Jumlahtitiktidakberpengaruhterhadapwaktuprosespencariansolusi.Waktuuntukmenampilkansolusirelatifcepat.Programinijugadifasilitasipenyimpanandatainputanpadafiledanjugafasilitasuntukmembukakembalifile