APLIKASI METODE BRANCH-AND-PRICE PADA PERMASALAHAN OPEN LOCATION ROUTING PROBLEM WITH TIME WINDOWS

ARLITA NURMAYA ASRI, Bertha Maya Sopha, S.T., M.Sc., Ph.D.

2017 | Tesis | S2 Teknik Industri

Penentuan lokasi pusat distribusi dan rute kendaraan merupakan dua keputusan penting dalam merancang jaringan rantai pasok. Walaupun kedua permasalahan tersebut sering diselesaikan secara terpisah karena perbedaan waktu perencanaan, namun keduanya terbukti saling berhubungan. Sehingga, Location Routing Problem (LRP) digunakan untuk menyelesaikan kedua permasalahan tersebut secara simultan. Permasalahan berkembang ketika perusahaan tidak mempunyai kendaraan sendiri untuk mengantar produk mereka. Selain itu, di dunia nyata, waktu kedatangan kendaraan di pelanggan akan mempengaruhi tingkat kepuasan pelanggan atau penjualan terhadap pelanggan. Setiap pelanggan mempunyai jendela waktu yang spesifik dimana mereka dapat dilayani, dan kendaraan harus datang pada jendela waktu tersebut untuk dapat melayani pelanggan. Sehingga, penelitian ini mengkombinasikan antara Open Location Routing Problem (OLRP) dengan batasan jendela waktu menjadi Open Location Routing Problem with Time Windows (OLRPTW). Penelitian ini mengembangkan algoritma branch-and-price untuk menyelesaikan permasalahan OLRPTW. Instance pada permasalahan ini dimodifikasi dari tiga data set LRP benchmark. Hasil komputasi menunjukkan bahwa hasil algoritma branch-and-price dapat dibandingkan dengan CPLEX pada instance skala kecil hingga sedang dengan jumlah pelanggan mencapai 100. Untuk instance skala besar, algoritma tersebut dapat menyelesaikan hingga 200 pelanggan dengan 10 depot dengan hasil optimal dan menghasilkan lebih banyak instance dengan solusi yang feasible jika dibandingkan dengan CPLEX.

Facility location and vehicle routing problems are two critical decisions in designing a supply chain network. Although they are often solved separately because of the differences in their planning horizon, these two problems have been proven to be interdependent. Therefore, the location routing problem (LRP) is proposed to solve these problems simultaneously. The problem extends from a practical perspective when the companies do not have their own vehicles to deliver their products. Considering in some real-life situations, arrival time at a customer will affect the customer’s satisfaction level or sales to the customer. Each customer may have a specific service time window during which s/he can be serviced, and a service vehicle must arrive within this time window to start its service. Therefore, this study combines the open location routing problem (OLRP) and time windows constraint into the open location routing problem with time windows (OLRPTW). This study proposes a branch-and-price algorithm to solve the OLRPTW problem. The OLRPTW instances are derived from three LRP benchmark data sets. Computational result indicates that the branch-and-price algorithm is comparable for small-medium instances with up to 100 customers. For large instances, it can solve instance with 200 customers and 10 depots to the optimality and provide more instances with feasible solutions compare to CPLEX.

Kata Kunci : open location routing problem, time window, branch-and-price, labeling algorithm