APLIKASI SIMULATED ANNEALING HEURISTIK PADA HETEROGENEOUS FLEET POLLUTION ROUTING PROBLEM

ARTYA LATHIFAH, Nur Aini Masruroh, ST., M.Sc., Ph.D.

2015 | Tesis | S2 Teknik Industri

Kesadaran lingkungan telah meningkat selama beberapa dekade terakhir. Akibatnya, semakin banyak perusahaan yang mempertimbangkan polusi dalam perencanaan kegiatan logistik. Pollution Routing Problem merupakan lanjutan dari Vehicle Routing Problem dengan Time Windows. Pollution Routing Problem menyelesaikan penentuan satu set rute kendaraan dengan kecepatan yang optimal pada setiap segmen rute untuk setiap kendaraan dalam melayani satu set pelanggan dalam Time Windows tertentu. Dalam prakteknya, banyak masalah routing kendaraan ditangani oleh armada kendaraan yang heterogen yang memiliki perbedaan kapasitas dan biaya variabel untuk tiap jenisnya. Tingkat emisi juga bervariasi menurut jenis kendaraan karena perbedaan kapasitas dan curb weight masing-masing jenis kendaraan. Oleh karena itu, pada penelitian ini diusulkan armada yang heterogen pada Pollution Routing Problem yang merupakan kelanjutan dari Pollution Routing Problem dengan constraints yang lebih komprehensif dengan mempertimbangkan beberapa jenis kendaraan. Tujuannya adalah untuk meminimalkan biaya total dari bahan bakar, greenhouse gas, dan biaya variabel kendaraan. Sebuah model matematika dikembangkan dan juga diaplikasikan metode heuristik bernama Simulated Annealing diusulkan untuk Heterogeneous Fleet Pollution Routing Problem. Simulated Annealing heuristik pertama diverifikasi menggunakan data benchmark dari Pollution Routing Problem. Hasil verifikasi menunjukkan bahwa Simulated Annealing dapat menghasilkan cost lebih kecil untuk 7 kasus bila dibandingkan dengan metode sebelumnya dan bisa mendapatkan perbedaan 0.493%. Selanjutnya, Simulated Annealing digunakan untuk menyelesaikan Heterogeneous Fleet Pollution Routing Problem dan hasilnya dibandingkan dengan CPLEX. Dapat disimpulkan bahwa pertimbangan armada kendaraan yag heterogen dapat mengurangi biaya total polusi untuk semua kasus.

The consciousness for the environment has been increasing for the last decades. As a result, more and more companies are taking pollution into account in planning their logistic activities. Pollution Routing Problem is an extension of the classical Vehicle Routing Problem with Time Windows. Pollution Routing Problem determines a set of optimal route and vehicle speeds on each route segment for a fleet of vehicles to serve a set of customers within specific time windows. In practice, many vehicle routing problems are addressed by a fleet of heterogeneous vehicles with different capacities and travel costs. Emission levels vary by vehicle type because of differences in curb weight and capacity. Therefore, this study proposed Heterogeneous Fleet Pollution Routing Problem which is an extension of Pollution Routing Problem with a richer and more practical set of constraints and multiple vehicle types. The goal is to minimize total costs of fuel, greenhouse gas emissions, and vehicle variable cost put together in a more comprehensive objective function. A mathematical model is developed and a Simulated Annealing heuristic is proposed for Heterogeneous Fleet Pollution Routing Problem. The performance of the proposed Simulated Annealing heuristic is first verified using benchmark data of the Pollution Routing Problem. The result shows that Simulated Annealing performs better for 7 instances than the previous method and can get difference of 0,493% in average. Then, Simulated Annealing is used to solve Heterogeneous Fleet Pollution Routing Problem and the results are compared to those obtained by CPLEX. Then, it is found that the consideration of heterogeneous fleet reduces total pollution costs for all instances.

Kata Kunci : pollution routing problem, heterogeneous fleet, time windows, greenhouse gas, simulated annealing