Indonesia adalah negara kepulauan dengan lebih dari 17 ribu pulau. Makadari itu, laut memegang peran penting bagi transportasi. Program Toll Laut sudah di implementasikan untuk mendukung konektivitas transportasi pada negara kepulauan ini. Namun, beberapa masalah masih terlihat pada kabupaten kepulauan, sebagai contoh, Kabupaten Sumenep. Kabupaten Sumenep berlokasi di Jawa Timur dengan total 126 pulau. Terdapat 6 pulau besar di Kabupaten Sumenep, yaitu, Pulau Madura, Pulau Poteran, Pulau Masalembu, Pulau Sapudi, Pulau Ra`as, dan Pulau Kangean. Jenis kapal yang beroperasi di wilayah Kabupated Sumenep bervariasi dengan kapasitas dan ukuran yang berbeda beda. Hal ini mengakibatkan faktor muat penumpang dan pendapatan kapal yang tidak seimbang. Tujuan dari penelitian ini berhubungan dengan skema kapal penumpang di wilayah Kabupaten Sumenep dengan mengoptimalisasi sistem and mendesain skema yang paling efisien. Data akan di proses dan di kalkulasi menggunakan linear programmingdengan Excel Data Solver. Fungsi objektif dari persamaan linear adalah untuk memaksimalkan pendapatan bersih setiap tahunnya, dengan jumlah penumpang per kapal dan frekuensi per tahun sebagai konstrain. Ukuran dan kapasitas kapal di asumsikan sama untuk semua rute, ukuran kapal yaitu 258 GWT dengan 2 mesin utama dna kapasitas 180 penumpang. Setelah menganalisa data, rute dari Pelabuhan Kalianget menuju Pelabuhan Masalembu dan Pelabuhan Kalianget menuju Pelabuhan Talango tidak berubah, dikarenakan jarak Masalembu yang terlalu jauh dan jarak Poteran yang terlalu dekat. Menurut hasil kalkulasi, rute yang menghasilkan pendapat bersih paling tinggi adalah Model 2, dengan rute Pelabuhan Kalianget-Pelabuhan Sapudi-Pelabuhan Brakas-Pelabuhan Batu Gulok-Pelabuhan Sapeken. Model 2 akan dikombinasikan dengan rute menuju Pulau Masalembu dan Pulau Poteran. Sebagai hasil total dari pendapatan bersih adalah Rp. 6,323,084,797,-.

Indonesia is an archipelagic country with more than 17 thousand islands. Hence, sea holds an essential part for transportation. Maritime Highway Program is already implemented to connect this archipelagic nation. However, some problems are still seen in some regencies, for example, Sumenep Regency. Sumenep Regency is located in East Java and the total of 126 islands. There are 6 main islands in Sumenep Regency, which are Main Island of Sumenep, Poteran Island, Masalembu Island, Sapudi Island, Raas Island, and Kangean Island. The type of vessels operated on Sumenep are heterogeneous, means that the capacity and size are different between one route and another. This leads to unbalance load factor and revenue between each vessels. The objective of this research are mainly related to passenger ship transportation scheme in Sumenep Regency by optimizing the system and designing the most efficient passenger sea transportation scheme in Sumenep Regency. In which, will be processed and calculated using linear programming in Excel Data Solver. The objective function of the linear equation is to maximize the net revenue obtained per year, with number of passenger and the frequency per year as its constrains.  The size and capacity of the vessel are assumed to be homogeneous for all routes, which are 258 GWT vessel with two main engine and capacity of 180 passenger. After analysing the data, the routes from Kalianget Port to Port of Masalembu and Kalianget Port to Talango Port will not be changed since the distance is either too far or too close to the main port which makes it not feasible to be included in the same group as the other islands. Based on the calculation, the route that gives the biggest revenue is Model 2, where the route is from Kalianget Port-Port of Sapudi-Brakas Port-Batu Gulok Port-Port of Sapeken. Model 2 Routing Scheme is then combined with the route to Masalembu Island and Poteran Island. As a result the total revenue obtained from this optimization is Rp. 6,323,084,797,-.