PEMODELAN MASALAH RAILWAY TRAVELING SALESMAN PROBLEM (RTSP) MENGGUNAKAN METODE INTEGER LINEAR PROGRAMMING (ILP)

SOPIA KARTIKA, Dr.rer.nat., Ari Suparwanto, M.Si

2016 | Tesis | S2 Matematika

Dalam tesis ini dibahas mengenai formulasi model permasalahan optimasi rute kereta api yang disebut juga dengan Railway Traveling Salesman Problem (RTSP). Permasalahan RTSP yang akan dibahas dalam penulisan ini merupakan permasalahan dimana seorang salesman melakukan perjalanan dengan menggunakan transportasi kereta api dari stasiun awal, dimana ia memulainya tidak lebih awal dari waktu yang ditentukan menuju ke setiap stasiun di dan akhirnya kembali ke stasiun awal dengan kendala ia harus menghabiskan total waktu yang dibutuhkan di setiap stasiun di untuk menjalankan bisnisnya. Tujuannya adalah meminimalisir keseluruhan waktu perjalanan. Dalam tesis ini akan disajikan model masalah RTSP sebagai sebuah bentuk Integer Linear Program berdasarkan pada graf berarah yang dihasilkan dari informasi jadwal. Dikarenakan graf ini dapat menjadi sedemikian besar, ditunjukkan pula cara untuk mereduksi ukurunnya tanpa mengorbankan kebenarannya. Akhirnya, penyelesaian masalah ini akan menggunakan algoritma branch-and-cut dengan bantuan software ILOG versi CPLEX 12.5 untuk menemukan rute optimal kereta api yang akan meminimalisir keseluruhan waktu perjalanan salesman. Kata kunci: Railway Travelling Salesman Problem, Integer Linear Program, Algoritma Branch-and-cut.

In this thesis we discuss about formulation of railway optimization called Railway Travelling Salesman Problem (RTSP). The RTSP which will be discussed in this paper is a salesman wants to travel from the initial station, starting not earlier than the designated time, to every station in and �nally return back to the initial station, subject to the constraint that she/he spends the necessary amount of time in each station of to carry out his/her business. The goal is to minimize the overall time of the journey. In this paper we present a modelling of RTSP as an integer linear program based on the directed graph resulted from the timeable information. Since in this graph can be very large, we also show how to reduce its size without sacrificing correcness. Finally, solving this problem using the branch-and-cut algorithms with the help ILOG CPLEX version 12.5 software to solved this problem is to find the optimal route a train that the overall time of the salesman journey is minimized. Keywords: Railway Travelling Salesman Problem, Integer Linear Program, Branch-and-cut Algorithm.

Kata Kunci : Railway Travelling Salesman Problem, Integer Linear Program, Branch-and-cut Algorithm.