Optimization Model

Alhamdulillah… saya bisa menepati janji saya ke Dr. Ahmad (dan ke diri saya sendiri juga sebenarnya) untuk menyelesaikan optimization model tesis ini dalam seminggu. Tapi saya baru menemui Dr. Ahmad hari jumat, 21 September, sebab hari kamisnya saya dateng ke ITMA, beliau nggak ada. Ya sudah, besok paginya aja saya temui beliau di fakulti. Rupanya hari kamis itu beliau ada rapat di fakulti. Karena saya nggak nge-SMS, dia kira saya nggak jadi dateng, jadi dia nggak ke ITMA lagi. Salah saya juga sih, nggak confirm lagi mau dateng. Udah tau sekarang Dr. Ahmad tuh mobilitasnya tinggi sekali semenjak jadi pengetua ITMA.

Emang sih, saya juga udah ngira, bagian optimization model ini nggak sesusah bagian menentukan candidate site. Udah kebayang yg perlu dikerjain seperti apa (iya lah, tinggal ngoding doang, kok ), cuma yg susah mungkin ngedesain algoritmanya.
Sebagaimana yg sudah saya rencanakan sebelumnya, data² dari DBF yg diperlukan untuk keperluan running optimization model ini saya export dulu ke MySQL, sebab query yg bisa dilakukan oleh Perl terhadap DBF amat sangat terbatas, bahkan sekedar select join pun nggak bisa.
Saya bikin dulu script Perl untuk convert data² itu. Total ada 6 tabel di MySQL yg terlibat dalam model buatan saya, 3 tabel berisi entities untuk facility, hi-risk zone, dan mod-risk zone; 1 tabel berisi matrix OD antar facilities, dan 2 tabel lagi berisi informasi mengenai coverage facilities terhadap hi-risk zone dan mod-risk zone.

Mula-mula saya bikin algoritmanya simpel aja. Saya cari satu facility yg punya service area paling luas sebagai initial point. Lalu dari initial point ini, saya cek candidate point² lainnya. Yg jaraknya terlalu dekat dengan initial point, akan langsung dianggap tidak optimum, dan tidak akan disertakan lagi dalam iterasi berikut. Kecuali kalo sudah tidak ada lagi candidate point yg tersedia, sementara jumlah facility belum mencapai target, maka point² yg sudah dianggap tidak optimum tadi akan di-observe kembali, dan dicari mana yg memiliki nearest distance paling jauh (maximin) terhadap facility² yg sudah terpilih.
Dari suatu facility terpilih, untuk mendapatkan facility berikutnya saya akan mencari candidate point² yg berada pada jarak lebih jauh dari jarak minimum terhadap facility² terpilih, kemudian cari mana yg bisa mengcover fire-risk zone. Dari situ diambil satu point yg memiliki service area paling luas untuk dijadikan sebagai facility terpilih. Kalau nggak ada point yg bisa mengcover fire-risk zone, ya langsung aja diambil yg memiliki service area paling luas.

Pas udah selesai coding, baru saya dapet ide untuk memisahkan point² yg berada pada jarak lebih jauh dari jarak minimum itu ke dalam 2 bagian, yaitu point² yg berada pada jarak lebih dekat dari jarak maksimum (local range), dan point² yg berada pada jarak lebih jauh dari jarak maksimum (global range). Kenapa saya bedakan ini? Karena, dari satu facility ke facility terdekatnya, lebih ideal kalo jarak mereka itu pas, nggak terlalu jauh supaya nggak ada gap, juga nggak terlalu dekat supaya nggak overlap. Kalau nggak dipisahin begini, maka dari satu facility terpilih, bisa jadi facility terpilih berikutnya memiliki jarak yg “tanggung” dengan facility yg sedang diobservasi. “Tanggung” dalam arti, service area antar mereka menciptakan gap, tapi kalo di antara mereka disisipkan satu facility lagi, service area facility tsb akan overlap cukup luas dengan service area mereka. So, saya buat algoritma ke-2, yg memisahkan jarak antara local range dan global range. Prioritas pencarian point akan dilakukan di local range dulu. Kalo di situ nggak ada point sama sekali, baru deh cari ke global range.

Setelah selesai ngoding algoritma ke-2, saya terpikir ide lain lagi. Dalam kedua algoritma yg sudah saya buat, untuk point² yg sudah masuk dalam unreasonable distance, ketika diambil lagi karena sudah tidak tersedia candidate point dalam reasonable distance, point² ini nggak dicek lagi apakah mereka mampu mengcover fire-risk zone atau nggak. Mereka juga bukan diambil dari yg service areanya paling besar, melainkan cuma dicari yg nearest distancenya paling jauh terhadap facility² terpilih. Nah, untuk algoritma ke-3, saya coba untuk point² dari unreasonable distance ini juga dicek lagi apakah ada yg mampu mengcover fire-risk zone, sama seperti pengecekan yg dilakukan pada point² di reasonable distance. Hanya saja, final decisionnya tetap dicari yg memiliki nearest distance paling jauh, bukan yg memiliki service area paling luas seperti pada point² di reasonable distance. Ternyata pas di-run, algoritma ke-3 ini memiliki run time yg cukup lama, mencapai belasan detik. Ya, karena point² di unreasonable distance jumlahnya jauh lebih banyak.

Tapi yg bikin saya kecewa, ternyata tak satu pun dari algoritma yg saya buat ini mampu menghasilkan coverage lebih luas dari existing coverage. Saya dah coba pake candidate points yg didapat dari quadrat subdivision maupun hexagon subdivision, tetap coveragenya lebih kecil. Tapi saya tau alasannya. Untuk candidate points dari hexagon subdivision, coverage total dari seluruh candidate pun memang sudah terlihat tidak optimum. Jelas lah coverage dari facility² terpilih yg dihasilkan dari optimization model juga nggak bakalan lebih memuaskan. Candidate points dari quadrat subdivision lebih bagus, karena memang jumlahnya lebih banyak. Tapi faktor utama yg saya duga sangat mempengaruhi buruknya coverage area hasil optimization model saya adalah: banyak candidat points yg letaknya terlalu ke pinggir dalam study area. Ini semua karena saya mendesak point² tsb sebaiknya mendekati centroid hexagon. Padahal untuk hexagon² yg berada di bagian tepi study area, hanya sebagian kecil saja yg terisi oleh polygon study area. Sepertinya niat saya untuk menggunakan hexagon yg lebih kecil benar² perlu dilaksanakan, supaya hexagon² yg cuma keisi sedikit study area bisa dikurangi, sehingga candidate points yg dihasilkan pun nggak bakalan jatuh terlalu ke pinggir lagi.

Belakangan saat diskusi dengan Dr. Ahmad, saya dapet ide lain juga, yaitu saya akan membuat buffer dari batas study area ke arah dalam, dan menjadikan wilayah buffer tsb sebagai restricted area. Dengan demikian candidate points dijamin tidak akan terletak terlalu ke pinggir. Dr. Ahmad juga sempet ngasih masukan, untuk hexagon² di bagian pinggir yg hanya terisi oleh sebagian kecil polygon study area, ya ambil intersection study area tsb dengan hexagonnya aja, kemudian tentukan centroid dari intersectionnya itu, jadi bukan dari full hexagon. Tapi cara ini pun masih memungkinkan output candidate point akan jatuh di pinggir. Cara saya lebih baik.

Karena bisa dibilang tesis saya ini sudah selesai, dah tinggal writing aja, Dr. Ahmad pun berniat memasukkan penelitian saya untuk pembuatan poster. Kebetulan hari jumat itu hari terakhir submit borang untuk mengajukan poster, maka Dr. Ahmad menyuruh saya untuk ngisi borang itu hari itu juga. Kita memang nggak harus langsung submit posternya, cuma perlu submit judul penelitian, isi penelitian, kegunaan penelitian, abstrak penelitian, dsb. Nanti kalo di-approve, baru bikin posternya.

Hari sabtu, baru saya bisa ketemu lagi dengan Dr. Noordin. Ternyata selama 2 minggu ini beliau pergi umrah, baru nyampe hari jumat, makanya email saya nggak dibales². Tapi kelihatannya dia udah baca email saya. Pas ketemu ini ya saya konsultasi langsung aja. Pertamanya sih Dr. Noordin nggak langsung nerima cara saya make hexagon untuk nyari candidate points, tapi ternyata itu karena dia salah paham. Dikiranya metode hexagon itu untuk langsung nentuin lokasi fire station yg baru. Dikiranya output dari metode itu udah final output. Dia nggak ngeh kalo setelah dapet candidate points, saya masih akan melakukan optimization model lagi untuk mendapatkan selected points yg akan memberikan coverage maksimum. Setelah dia ngerti bahwa output metode hexagon itu baru intermediate output, baru deh dia OK. Alhamdulillah… saya udah takut aja kalo dia bilang metode saya ini aneh lah, atau unacceptable. Tapi nggak kok, malah pas saya bilang ada metode lain yg udah dikenal, yaitu K-Mean cluster, dia bilang metode saya ini lebih baik. Dia pun nyaranin saya bikin paper tentang ini. Fiuhh… lega deh. Kalo Dr. Noordin udah setuju juga, berarti selesai deh tesis saya. Bener² tinggal writing aja.

Tapi saya masih sangsi bisa selesai akhir semester ini. Masalahnya saya mesti menyediakan waktu juga untuk para supervisor memeriksa draft tesis saya. Normalnya sih sebulan. Iya kalo semua oke, kalo banyak koreksi? Lagipula saya masih harus melakukan beberapa eksperimen. Saya masih harus mengganti bentuk² hexagon itu dengan ukuran yg lebih kecil. Saya juga masih harus mencari literatur untuk memperkuat alasan saya menetapkan angka² pembobotan dalam multi criteria analysis. Jadi, siapa bilang tinggal writing? Masih banyak aktivitas² lab yg perlu dituntaskan nih.

Masalah lain, rumus matematika dalam optimization model yg saya buat, itu SALAH. Sejak awal pun saya sudah merasakan keganjilan dalam rumus matematika tsb. Tapi kebetulan baik Dr. Ahmad maupun Dr. Noordin pun sepertinya nggak paham juga, jadi nggak ada yg ngasih komentar.
Jadi begini, objective dari optimization model saya adalah: memaksimalkan service area dari serangkaian fire station yg jumlahnya ditentukan. Dalam hal ini, jumlah yg ditentukan itu sama dengan jumlah existing fire station. Model ini memiliki 2 constraints, yaitu pertama, jarak antar fire station harus memenuhi reasonable distance untuk mencegah terlalu banyak overlapping service area. Kedua, fire station harus diletakkan sedemikian rupa sehingga hi-risk zone akan tercover oleh minimal 2 fire station, dan mod-risk zone oleh minimal 1 fire station. Nah, di sini nih letak ganjilnya. Kalau jumlah fire stationnya ditentukan (berarti terbatas), tidak mungkin saya bisa menetapkan constraint seperti itu. Kondisi tsb tak akan terjamin, yg berarti, rumus matematik ini tidak akan ada solusinya. Kalau saya menerapkan constraint seperti itu, maka mestinya objective model tsb bukan memaksimalkan service area dari serangkaian fire station dengan jumlah tertentu, melainkan mencari jumlah minimum fire station yg diperlukan untuk bisa mengcover hi-risk zone dan mod-risk seperti yg disyaratkan dalam constraint tsb. Mestinya, constraint bahwa serangkaian fire station harus bisa mengcover fire-risk zone itu dijadikan sebagai objective lain selain objective utama memaksimalkan service area. Statement objective-nya yaitu, memaksimalkan jumlah hi-risk zone yg bisa tercover oleh 2 fire station dan memaksimalkan jumlah mod-risk zone yg bisa tercover oleh 1 fire station. Jadi sebenarnya, model saya ini multi objectives, bukan single objective. Maka, saya nggak bisa pake rumus matematik sederhana seperti yg saya buat untuk single objective itu. Untungnya ada sih artikel jurnal yg pernah saya baca, yg merumuskan multi-objectives model ke dalam persamaan matematika. Saya bisa cek lagi di situ.

Satu hal lagi yg saya rasakan janggal dan membuat model buatan saya tidak bisa menjamin optimal solution adalah, menghitung coverage area dari serangkaian fire station itu nggak bisa simpel tinggal menjumlahkan service area dari masing² fire station. Kenapa? karena service area total ini TIDAK SAMA DENGAN coverage total dari rangkaian fire stations tsb, sebab service area dari fire station² tsb ada yg overlap, dan kita tidak bisa memastikan berapa persen area yg overlap. Tidak ada cara untuk menghitung itu. Semula saya pikir, dengan menetapkan constraint harus memenuhi reasonable distance itu udah bisa mengatasi problem ini. Tapi setelah saya pikir² lagi, itu pun nggak bisa menjamin juga. Nggak bisa dipastikan bahwa kalo jarak fire station sekian, overlapping areanya sekian. Semua tergantung dari bentuk geometri road network di sekitar fire station yg bersangkutan. Jadi, tetaplah rumus matematik ini tidak akan ada solusinya.

Waktu diskusi dengan Dr. Noordin, saya sempet ngebahas tentang gimana caranya merepresentasi polygon dengan point. Sebab fire-risk zone yg saya punya itu merupakan polygon, sementara untuk mengetahui apakah sebuah fire-risk zone tercover oleh sebuah fire station, lebih mudah jika zone itu berbentuk point, jadi kita tinggal mengecek apakah point zone tsb jatuh di dalam polygon service area si fire station. Kalo iya berarti tercover, kalo nggak ya nggak tercover. Untuk hi-risk zone, kebetulan polygon-nya kecil², jadi andai mau direpresentasi dengan point pun, saya bisa make tehnik centroid untuk nentuin point-nya. Tapi untuk mod-risk zone, polygonnya lumayan gede. Nggak bisa saya pake tehnik centroid untuk nentuin point yg merepresentasi polygon² zone ini. Lagipula, ukuran polygon tsb beda², ada yg gede, ada yg kecil. Kalau polygon dengan ukuran yg berbeda² itu direpresentasi oleh point yg sama, jelaslah tehnik representasi tsb nggak tepat.

Dr. Noordin pun pusing juga mikirin solusi masalah itu. Dia sempet nyaranin, untuk polygon² tertentu saya bagi secara manual jadi beberapa polygon, baru ambil centroidnya. Tapi saya nggak mau cara manual, sebab menurut saya cara manual itu nggak profesional. Kalo data kita sedikit, mungkin bisa pake cara manual. Tapi kalo banyak?
Saya pun mengajukan usul lain, yaitu dengan menempatkan random points dalam masing² polygon mod-risk zone tsb, yg jumlahnya proporsional dengan luas polygon. Sebenarnya lebih bagus kalo bisa menempatkan regular points, tapi kayaknya nggak tersedia tool semacam itu di ArcGIS. Tapi seenggaknya cara ini otomatis. Dr. Noordin bilang sih, boleh² aja saya make cara itu. Kata dia, sebenarnya dalam research, kita bisa make tehnik apa pun, asal jelaskan seberapa akurat tehnik tsb, dan seberapa cocok dengan kasus dan kondisi dalam research kita. Lebih bagus kalo kita bisa kasih rekomendasi mana tehnik yg paling cocok digunakan.

Balik lagi ke masalah rumus matematik tadi, belakangan saya nemu ide lain (pembuatan tesis kali ini memang betul² proses pemerasan ide ). Dalam facility location model konvensional, selalu terdapat supply point dan demand point. Sementara dalam model buatan saya, demand itu bukan direpresentasi oleh point, melainkan oleh area. Terbukti saya mendapatkan banyak kesulitan karena itu. Mulai dari gimana menentukan point untuk merepresentasi fire-risk zone, sampai menghitung total coverage area dari serangkaian fire station. Ide saya untuk menggenerate random points yg jumlahnya proporsional dengan luas polygon itu, batal saya niatkan. Sekarang saya ingin mengubah sedikit optimization model saya. Saya akan mengconvert demand area dalam model buatan saya, dari “continuous space” menjadi “continuous points”. Mudah melakukan ini, tinggal convert data asal ke raster dengan ukuran cell tertentu, lalu convert lagi ke point, maka setiap cell akan menjadi satu point. Kalau kita pengen jarak antar demand pointnya 200 m, ya set ukuran cell untuk data rasternya 200 m juga.

So, nanti bukan service area dalam satuan meter persegi lagi yg datanya akan saya simpan dalam tabel MySQL, melainkan data coverage fire station² terhadap demand point² (yg mengandung data turunan berapa banyak point yg dicover oleh sebuah fire station). Kalo demand direpresentasi dalam bentuk point gini, optimalisasi bisa dihitung dari berapa banyak jumlah point yg tercover oleh serangkaian fire station. Rumus matematik sebelumnya jelas perlu disesuaikan, yg sebelumnya ingin memaksimalkan service area dari serangkaian fire stations dengan jumlah tertentu, menjadi memaksimalkan jumlah demand point yg bisa tercover oleh serangkaian fire stations dengan jumlah tertentu, barulah rumus matematik ini bisa didapatkan solusinya.

Terus, kalo semua demand direpresentasi oleh point gitu, saya juga bisa menggunakan Greedy Algorithm seperti yg digunakan Church dalam tesisnya (eh, tesis dia itu tesis PhD, lho… ). Greedy Algorithm-nya si Church itu begini: pertama, cari facility yg bisa mengcover the most population. Kemudian untuk facility ke-2, cari yg bisa mengcover the most population yg belum tercover oleh facility pertama. Untuk facility ke-3, cari yg bisa mengcover the most population yg belum tercover oleh facility pertama dan ke-2. Begitu seterusnya sampai seluruh populasi tercover atau jumlah facility sudah mencapai target yg ditentukan. Saya pun bisa menggunakan proses serupa. Pertama, cari facility yg bisa mengcover demand point paling banyak. Untuk facility ke-2, cari lagi yg bisa mengcover demand point terbanyak yg belum tercover oleh facility pertama, dst. Tapi karena model saya ini multi objectives, nggak bisa sesederhana gitu aja, karena demand point dalam model buatan saya itu terbagi dalam 3 kelas, yaitu hi-risk, mod-risk, dan biasa. Demand point hi-risk dan mod-risk harus dapet prioritas lebih dibanding demand point biasa. Jadi pertimbangan pilihan dipengaruhi oleh seberapa banyak fire-risk zone yg bisa tercover, dan seberapa banyak total point yg bisa tercover. Kalau ada sebuah facility bisa mengcover hi-risk zone misalnya, tapi secara keseluruhan dia cuma bisa mengcover sedikit demand point, sementara ada facility lain yg nggak bisa mengcover hi-risk zone, tapi secara keseluruhan dia bisa mengcover banyak demand point, maka pilihan mungkin akan jatuh ke facility yg terakhir ini. Makanya, saya perlu belajar lagi gimana membuat rumus matematik untuk optimization model dengan multi-objectives.

Saya suka sekali dengan tesis saya ini. Nggak nyangka, lingkup analisis tesis saya jadi meluas dan menjangkau semua bidang² yg saya sukai:
When computing service area, it is a network analysis problem.
When finding suitable land, it is a spatial analysis problem.
When finding potential site, it is a geostatistic problem.
When finding optimal site, it is a combinatorial problem.
Untuk optimization model, dibutuhkan pengetahuan dan pemahaman yg mendalam tentang analisa algoritma, dan keahlian programming dan manajemen database. Jadi, tesis saya ini merupakan integrasi antara GIS, Geostatistic, Matematika, dan Programming.

Dr. Ahmad pun bilang, tesis saya ini sangat lengkap, semuanya ada, mulai dari spatial analysis sampai programming. Dia bahkan menyarankan saya untuk convert ke PhD aja, kalo merasa bahwa substansi tesis ini terlalu berat untuk diselesaikan sebagai tesis Master. Wuah… nggak pernah saya berpikir tesis saya bisa mencapai level tesis PhD. Padahal target saya cuma pengen selesai kuliah master dalam waktu setahun aja, sekarang malah ditawarin untuk convert ke PhD .

Leave a Reply