Pendanaan: Pekerjaan ini didukung oleh Institut Manajemen India Ahmedabad.

ABSTRAK

Kami mempelajari masalah desain optimal jaringan akses optik fiber-to-the-home (FTTH). Dengan adanya jaringan simpul dan tepi yang berakar pada titik distribusi optik (ODP) dengan permintaan serat optik tertentu pada sebagian simpul tersebut, masalahnya adalah menemukan penempatan pemisah yang optimal, yang memungkinkan beberapa titik permintaan untuk berbagi serat umum antara ODP dan pemisah, sehingga jumlah biaya kabel serat dan pemisah diminimalkan. Selain itu, perlu diputuskan pemilihan jenis kabel yang optimal dengan kapasitas yang sesuai pada setiap tepi jaringan untuk membawa lalu lintas yang diperlukan. Literatur yang ada tentang desain jaringan akses FTTH biasanya mengasumsikan jumlah tahap pemisahan yang sama untuk semua titik permintaan—khususnya, satu dalam kasus masalah pemisahan tunggal (SSP) atau dua dalam kasus masalah pemisahan ganda (DSP). Kami menyediakan formulasi pemrograman integer campuran (MIP) dari masalah pemisahan campuran (MSP), di mana beberapa titik permintaan dapat dilayani melalui satu tahap pemisahan, sedangkan yang lain dapat dilayani melalui dua tahap pemisahan. Kami selanjutnya mengusulkan beberapa ketidaksetaraan (VI) yang valid, dengan atau tanpa templat yang telah ditentukan sebelumnya, untuk memperkuat formulasi. Melalui eksperimen komputasional kami pada contoh besar, kami menunjukkan kemanjuran VI yang kami usulkan, yang membantu meningkatkan batas bawah masalah dari 79% menjadi 86,9% dari biaya optimal MIP, secara rata-rata. Untuk kasus khusus SSP dan DSP, kami menunjukkan bahwa formulasi kami menghasilkan batas bawah yang jauh lebih ketat dibandingkan dengan formulasi yang ada dalam literatur. Selain itu, VI yang kami usulkan secara komparatif jauh lebih efektif dalam memperketat batasan. Secara khusus, formulasi yang kami usulkan dengan VI kami secara konsisten mengungguli yang tersedia dalam literatur, menjadi sebanyak 500 kali lebih cepat dalam beberapa contoh.