PT.Pos Logistik Indonesia merupakan perusahaan distribusi pihak ketiga (3PL) yang memaksimalkan peluang bisnis logistik di Indonesia dengan mengoptimalkan jaringan PT.Pos Indonesia. Proses pickup and delivery problem (PDP) pada PT.Pos Logistik Indonesia menggunakan KBM yang beragam (heterogeneous) , time window berdasarkan shift, dan permintaan muatan yang fluktuatif. Berdasarkan observasi dan wawancara dengan pihak perusahaan, penulis menemukan permasalahan yaitu utilitas KBM yang tidak optimal pada trayek sekunder. Berdasarkan target rata-rata utilitas PT.Pos Logistik pada trayek sekunder adalah sebesar 40% sedangkan persentase rata-rata utilitas kapasitas KBM yang dibandingkan dengan muatan masing-masing pada outgoing dan incoming adalah sebesar 18,702% dan 18,704%. Berangkat dari permasalahan tersebut, PT.Pos Logistik Indonesia membutuhkan perancangan rute yang dapat meningkatkan utilitas tiap KBM dengan mengunjungi lebih dari satu trayek yang akan selaras dengan tujuan meminimasi biaya operasional. Solusi yang diusulkan adalah perancangan rute menggunakan algoritma multi start adaptive large neighborhood search (MSALNS) yang didasari oleh dua fase, yaitu: fase I, mengelompokkan trayek berdasarkan jarak menggunakan algoritma nearest neighbors dan fase II menggunakan algoritma adaptive large neighborhood search (ALNS) sebagai solusi akhir dengan prosedur removal dan insertion heuristic. Dengan menugaskan kembali KBM pada tanggal 22-28 Desember 2019 berdasarkan rute eksisting dan membandingkan dengan solusi, peningkatan utilitas KBM sebesar 20% hingga 30%
Kata kunci : Vehicle Routing Problem(VRP), Pickup and Delivery Problem (PDP), Heterogeneous, Time Window, Multi Start Adaptive Large Neighborhood Search (MSALNS)