Model Pemilihan Rute dengan Mempertimbangkan Waktu Sesaat Berdasarkan Kondisi Dynamic User Optimal

Model Pemilihan Rute dengan Mempertimbangkan Waktu Sesaat Berdasarkan Kondisi Dynamic User Optimal Tikah Nur Utami1, Yudi Satria2, Helen Burhan3 Departemen Matematika, FMIPA UI, Kampus UI Depok, 16424, Indonesia E-mail: [email protected], [email protected], [email protected]

Abstrak Tahap pemilihan rute merupakan salah satu tahap dalam perencanaan transportasi, yang bertujuan untuk mendapatkan flow kendaraan pada setiap ruas jalan. Masalah pemilihan rute ini dapat dimodelkan berdasar pada Prinsip Keseimbangan yang dikemukakan oleh Wardrop, di mana waktu tempuh perjalanan untuk setiap rute yang menghubungkan daerah asal dengan daerah tujuan yang sama memiliki waktu tempuh yang minimum dan relatif sama. Lamanya waktu tempuh perjalanan tergantung pada keadaan lalu lintas, di mana pada waktu sebenarnya keadaan lalu lintas setiap waktunya akan mengalami perubahan atau bersifat dinamis. Waktu tempuh perjalanan yang dihitung jika kondisi perjalanan pada setiap ruas jalan tidak berubah dari keadaan pada saat berangkat dari daerah asal sampai tiba di tujuan ketika melalui suatu rute merupakan waktu tempuh sesaat. Pada tulisan dibahas model pemilihan rute berdasarkan kondisi keseimbangan lalu lintas yang dinamis pada waktu sesaat. Langkah awal penyelesaian dari masalah tersebut adalah mendiskretisasi waktu tempuh, selanjutnya membuat pendekatan variational inequality untuk model matematisnya. Pada tahap penyelesaian dibuat model pemrograman nonlinear yang setara dengan model variational inequality tersebut dengan metode relaksasi. Selanjutnya digunakan Algoritma Frank Wolfe dengan menyisipkan metode all or nothing dalam penyelesaian masalah pemrograman nonlinear tersebut.

The Instantaneous Dynamic User Optimal Route Choice Model Abstract Route choice phase is one of the phases in transportation planning, which aims to get a traffic flow on any road. This route choice problem can be modeled based on the equilibrium principle stated by Wardrop, where the travel time for each route that connects the same of the origin to the destination have the minimum travel time and relatively equal. The length of travel time depends on traffic conditions, in real time the traffic conditions will change every time or be dynamic. Calculated travel time if the traffic condition on every link has not changed from the state at the time of departure from origin to arrive at the destination when through the route is an Instantaneous travel time. In this paper, it will be explained about Instantaneous dynamic user optimal route choice models. The first step of solving that problem is formulating the model in discrete time, and then using variational inequality approach. At the stage of completion is made nonlinear programming model that is equivalent to the variational inequality models with relaxation methods. Frank Wolfe algorithm is then used with apply all or nothing method in solving the nonlinear programming problem. Keywords: dynamic user-optimal route choice model; Frank Wolfe algorithm; instantaneous travel time; traffic assignment; variational inequality.

Model pemilihan..., Tikah Nur Utami, FMIPA, 2014

1. PENDAHULUAN Kemacetan lalu lintas di jalan raya merupakan salah satu permasalahan transportasi di beberapa kota besar di Indonesia, contohnya DKI Jakarta. Kemacetan yang setiap saat dijumpai ini, setiap tahun frekuensi serta durasinya semakin bertambah. Jika ditinjau dari rasio antara luas jalan dan jumlah mobil di DKI Jakarta, infrastuktur jalan hanya mampu menampung 1,05 juta mobil, sedangkan jumlah mobil yang ada sekitar 2,3 juta unit. Oleh karena itu, infrastruktur jalan raya di DKI Jakarta menampung kurang lebih dua kali lipat kemampuannya untuk menampung jumlah mobil. Menurut Kepala Bidang Jalan Dinas Pekerjaan Umum DKI Jakarta, rasio jalan yang ada yaitu 7,159% dari luas ibu kota, sedangkan idealnya mencapai 12% dari total luas wilayah. Ketidakmampuan jalan di DKI Jakarta untuk menampung luapan jumlah kendaraan terutama pada jam sibuk ini menyebabkan kemacetan yang dapat menimbulkan biaya tambahan dan tundaan atau waktu tempuh yang lebih lama.

Pemerintah DKI Jakarta telah mengeluarkan upaya untuk membatasi pergerakan jumlah kendaraan yang bertujuan untuk mengurangi kemacetan, antara lain: penerapan 3 in 1, penertiban parkir liar dengan cara gembok ban, dan pemberlakuan jalur bus khusus. Beberapa upaya yang telah dilaksanakan tersebut belum memberikan hasil yang signifikan dalam mengurangi kemacetan karena perencanaan pelaksanaan belum dirancang dengan baik. Perencanaan transportasi yang baik memiliki tujuan untuk memastikan bahwa kebutuhan pada masa yang akan datang terhadap pergerakan manusia, barang, atau kendaraan dapat ditunjang oleh sistem prasarana transportasi yang ada dan harus beroperasi di bawah kapasitasnya.

Perencanaan transportasi yang mempertimbangkan keadaan sebenarnya (real time) ditunjukkan dengan adanya perkembangan teknologi, di mana para pengendara dapat mengetahui informasi lalu lintas melalui media informasi seperti radio, GPS, televisi, Google map, Waze, TMC, dll. Informasi keadaan lalu lintas yang diberikan ke pengguna jalan oleh media informasi tersebut merupakan estimasi waktu tempuh perjalanan berbasis rute berdasarkan waktu sesaat (Instantaneous time). Jadi, saat itu juga pengguna jalan memilih rute berdasarkan waktu sesaat. Waktu tempuh perjalanan berdasarkan waktu sesaat adalah waktu tempuh perjalanan yang terjadi jika kondisi perjalanan pada ruas jalan tidak berubah dari keadaan saat berangkat dari asal sampai tiba di tujuan ketika melalui rute tersebut.


Dalam tulisan ini akan dibahas masalah pemilihan rute berdasarkan waktu sesaat yang memenuhi kondisi Instantaneous Dynamic User Optimal di mana untuk setiap pasang daerah asal dan daerah tujuan, pada waktu sesaat, pengendara memiliki waktu tempuh perjalanan yang sama dan minimum untuk setiap rute. Model pemilihan rute yang memenuhi kondisi Instantaneous Dynamic User Optimal diformulasikan menjadi model Variational Inequality yang biasa digunakan untuk mempelajari masalah keseimbangan yang diperkenalkan oleh Hartman dan Stampacchia (1966). Selanjutnya, akan diselesaikan pemrograman nonlinear yang setara dengan model Variational Inequaliy tersebut menggunakan algoritma Frank Wolfe yang biasa digunakan untuk menyelesaikan program matematika yang bersifat nonlinear.

2. TINJAUAN TEORITIS 2.1 Variational Inequality Variational Inequality adalah metode untuk mempelajari masalah keseimbangan yang diperkenalkan oleh Hartman dan Stampacchia pada tahun 1966. Masalah variational inequality yang telah dirumuskan dan dipelajari meliputi masalah keseimbangan pada jaringan lalu lintas, masalah keseimbangan pada pasar oligopolistik, masalah keseimbangan pada keuangan, masalah keseimbangan pada migrasi, dll.

Dalam matematika, variational inequality adalah sebuah pertidaksamaan yang melibatkan fungsi matematis yang harus diselesaikan untuk semua nilai variabel. Dalam variational inequality berisi kasus tentang masalah-masalah dalam pemrograman matematika yaitu sistem persamaan nonlinear dan masalah optimasi (Nagurney, 2002).

Pada permasalahan variational inequality didefinisikan variabel keputusan dan fungsi tujuan yang merupakan fungsi matematis dari variabel keputusan yang akan di optimisasikan yaitu yang domainnya adalah

di mana

merupakan fungsi kontinu

. Permasalahan Variational Inequality dapat didefinisikan sebagai

berikut


Definisi 2.1 (Ran & Boyce, 1996) kosong, konveks, dan tertutup di

adalah sebuah himpunan bagian dari

yang tidak

, f adalah fungsi kontinu yang terdefinisi di

. Masalah

Variational Inequality adalah menentukan

di mana berlaku

Pada permasalahan variational inequality yang bersifat dinamis akan ditentukan variabel kontrol yang

yang dapat dikendalikan sehingga menghasilkan nilai optimal.

Selain

variabel

kontrol

didefinisikan

pula

variabel

state

yang mempunyai nilai awal, proses dinamik ̇ yang

menyebabkan

terjadinya

perubahan,

persamaan

state

, serta vektor dari fungsi harga atau fungsi tujuan di mana vektor fungsi harga ini adalah fungsi dari variabel state dan kontrol

. Karena variabel state dapat ditentukan dari persamaan

state maka jika variabel kontrol diketahui, vektor dari fungsi harga dapat ditulis . Jika diberikan himpunan konveks

yang tertutup dari variabel kontrol

adalah vektor dari fungsi kontinu yang dipetakan dari

ke

dan

, maka didapat

suatu definisi seperti di bawah.

Definisi 2.2 (Ran & Boyce, 1996) Variational Inequality merupakan penentuan variabel kontrol

sedemikian sehingga ∫

Permasalahan optimasi merupakan masalah yang memaksimumkan atau meminimumkan suatu fungsi objektif yang tergantung pada kendala kendala tertentu. Masalah optimasi yang mempunyai kendala atau pun tidak, dapat diformulasikan sebagai masalah Variational Inequality sebagai berikut.

Teorema 2.1 (Ran & Boyce, 1996) Misalkan

adalah solusi dari masalah optimisasi

dengan syarat di mana Z adalah fungsi kontinu dan terturunkan dan G adalah himpunan konveks, maka juga merupakan solusi dari masalah variational inequality


,

Selain itu, masalah Variational Inequality dapat diformulasikan sebagai masalah optimasi sebagai berikut

Teorema 2.2 (Ran & Boyce, 1996) Jika

maka

adalah fungsi konvek dan

adalah solusi dari

adalah solusi dari

dengan syarat

Masalah variational inequality dapat diformulasikan sebagai masalah konveks ketika fungsi objektif

optimisasi yang

memiliki Jacobian yang simetri dan semidefinit positif.

Teorema 2.3 (Ran & Boyce, 1996) Jika F(x) merupakan vektor dari fungsi yang kontinu dan

terturunkan di G, dan matriks Jacobian

adalah simetri dan [

]

semidefinit positif, maka terdapat fungsi konveks Z(x) yang bernilai riil yang memenuhi di mana variational inequality

adalah vektor gradien dari Z(x) dan

adalah solusi

juga solusi dari Min Z(x) dengan syarat

2.2

Algoritma Relaksasi

Algoritma relaksasi merupakan metode iteratif yang digunakan untuk mencari solusi dari permasalahan variational inequality. Secara umum, algoritma relaksasi memecahkan masalah variational inequality ke dalam beberapa submasalah menjadi bentuk pemrograman nonlinear. (Nagurney, 1993)

Dengan menggunakan permasalahan variational inequality yang telah didefinisikan pada Definisi 2.1, asumsikan

merupakan vektor dari fungsi di


dan

, di mana

untuk setiap

berlaku

, dan untuk setiap

ditentukan, matriks Jacobian variabel keputusan

yang nilainya sudah

adalah simetri dan definit positif. Dengan kata lain,

pada fungsi

dipartisi menjadi dua grup yaitu

dengan

,

dan

atau sesuai

.

simetri dan definit positif, maka integral garis ∮

Karena matriks jacobian menciptakan fungsi

di

dan

, di mana

yang berninilai tetap,

merupakan fungsi yang strictly convex, dan

.

Untuk setiap iterasi n, akan diselesaikan submasalah variational inequality sebagai berikut

Submasalah variational inequality di atas ekivalen dengan masalah pemrograman matematika sebagai berikut

di mana terdapat

yang merupakan solusi unik.

Jika barisan solusi

konvergen atau ketika

bernilai sama dengan

pada saat

menuju tak hingga, maka submasalah variational inequality menghasilkan

Langkah - langkah dalam metode relaksasi diringkas seperti berikut. Langkah 0. Menentukan variabel keputusan yang layak (

). Tetapkan

.

Langkah 1. Menyelesaikan submasalah pemrograman matematika

diperoleh solusi

.

Langkah 2. Jika ‖

‖

, untuk

ditentukan, maka hentikan langkah. Jika ‖

yang bernilai sangat kecil sesuai dengan yang ‖

, tetapkan

lalu

kembali ke langkah 1.

2.3 Metode Frank Wolfe Metode Frank Wolfe yang diusulkan oleh Margurite Frank dan Philip Wolfe pada tahun 1956 merupakan metode yang digunakan untuk menyelesaikan masalah pemrograman kuadratik


dengan kendala linier. Metode ini juga dikenal dengan metode kombinasi konveks. (Ran & Boyce, 1996)

Misalkan terdapat masalah program minimisasi konveks dengan kendala linier sebagai berikut

∑

d.s di mana

merupakan fungsi konveks yang nonlinear, kontinu dan terturunkan, serta

dan

merupakan konstanta.

Secara umum, metode Frank Wolfe mencari nilai mana sejauh

. Nilai pada arah

dari

di

merupakan nilai yang didapat setelah berpindah dari

, di mana

merupakan vektor arah perpindahan, dan

merupakan titik yang berada pada ujung-ujung atau batas dari daerah layak. Secara matematis .

Jadi, dalam metode Frank Wolfe,

didapat dengan mencari vektor arah dengan

kemiringan yang paling curam pada arah menurun dan memiliki perpindahan yang paling besar dari

.

Saat mencari arah selidik

, tentukan

sedemikian sehingga arah dari

menghasilkan penurunan yang maksimum. Arah dari titik terdapat pada daerah layak adalah vektor

ke

ke sembarang titik

atau vektor satuan

‖

yang

. Dengan

‖

menggunakan turunan berarah, maka kemiringan dari

dengan arah vektor satuan ‖

adalah

menurun secara paling cepat pada

‖

. Penurunan yang maksimum atau

‖

arah gradien yang berlawanan

‖

], sehingga penurunan dari fungsi objektif pada arah

didapat dengan mengalikan slope dengan besarnya jarak dari ‖

‖

‖

ke .

‖

Penyelesaian pemrograman matematika di atas sama halnya jika kita mencari minimum dari (-1) dikali fungsi objektifnya sebagai berikut

Karena

konstan, maka program matematis di atas dapat diubah menjadi


Saat menentukan panjang langkah hal yang perlu diperhatikan adalah . Panjang langkah paling besar bernilai 1, karena jika

akan mendapat solusi

yang infisibel. Jadi panjang langkah didapat dengan menyelesaikan

Karena

didapat dari pemrograman matematis yang linier maka secara natural daerah

layaknya terbatas. Oleh karena itu titik baru berada di antara

Setelah didapat

dan .

, maka didapatlah titik baru

. Langkah langkah dari

algoritma Frank Wolfe untuk menyelesaikan masalah pemrograman nonlinear dapat diringkas sebagai berikut Langkah 0 Tetapkan nilai

, kemudian menentukan nilai

yang memenuhi kendala

Langkah 1 Menentukan arah dengan cara mencari nilai Langkah 2 Menentukan panjang langkah dengan cara mencari nilai Langkah 3 Didapat titik baru dengan mensubstitusi nilai

yang didapat pada langkah 1 dan

yang didapat pada langkah 2 ke dalam persamaan Langkah 4 Menguji konvergensi di mana jika jika

tetapkan

hentikan iterasi, namun dan kembali lakukan iterasi dari langkah 1.

3. PEMBAHASAN Pembahasan pada bagian ini mengenai model pemilihan rute dengan mempertimbangkan waktu sesaat berdasarkan kondisi Dynamic User Optimal (DUO).


3.1 Waktu Tempuh Sesaat (Instantaneous Time) Dalam penjelasan waktu tempuh sesaat diberikan ilustrasi pada Gambar 1. Misalkan terdapat empat node dan tiga link yang menyusun jaringan sederhana dengan satu O-D dan satu rute. Tumpukan dari nilai pada Gambar 1 merepresentasikan waktu tempuh perjalanan saat melewati link ketika berangkat dari node asal di waktu yang berbeda. Ketika berangkat pada waktu 1 untuk melewati link

waktu tempuh yang dibutuhkan adalah 1 satuan waktu,

sedangkan waktu tempuh yang dibutuhkan untuk melewati link

saat berangkat pada waktu

4 adalah 6 satuan waktu. Waktu tempuh perjalanan berdasarkan waktu tempuh sesaat

Gambar 1 Ilustrasi waktu tempuh sesaat (Instantaneous time) (Instantaneous time) untuk setiap rute pada setiap waktu keberangkatan yang berbeda dihitung dengan menjumlahkan waktu tempuh perjalanan pada link link yang menyusun rute tersebut dengan waktu keberangkatan yang sama. Sebagai contoh, dengan memperhatikan Gambar 3.1, untuk kendaraan yang berangkat pada waktu 1 memiliki waktu tempuh perjalanan

satuan waktu, sedangkan kendaraan yang berangkat pada waktu 2

memiliki waktu tempuh perjalanan

satuan waktu. Jadi, waktu tempuh

perjalanan berdasarkan waktu tempuh sesaat adalah waktu tempuh perjalanan yang terjadi jika kondisi perjalanan tidak berubah dari keadaan pada saat berangkat ketika melalui rute yang dipilih (Ran & Boyce, 1996). 3.2 Notasi Notasi yang digunakan di dalam model pada penulisan ini dan solusi algoritmanya dapat diringkas sebagai berikut. Dalam semua notasi, superscript ‘rs’ menyatakan pasangan daerah asal -daerah tujuan , di mana daerah digambarkan dengan node pada graf, subscript ‘p’


menyatakan rute

, di mana rute digambarkan dengan path pada graf, dan subscript ‘ ’

menyatakan ruas jalan atau link , di mana digambarkan dengan busur pada graf. : Jumlah kendaraan yang berada pada link

saat waktu

dengan rute

di

mana node asal dan node tujuan : Flow kendaraan yang masuk ke link node asal

saat waktu

dengan rute

di mana

saat waktu

dengan rute

di mana

dan node tujuan

: Flow kendaraan yang keluar dari link node asal

dan node tujuan

: Jumlah kendaraan yang berada pada link : Flow kendaraan yang masuk ke link

selama interval waktu

: Flow kendaraan yang keluar dari link

selama interval waktu selama interval waktu

: Flow kendaraan yang berangkat dari node asal

menuju node tujuan

pada

waktu melalui rute : Flow kendaraan yang tiba di node tujuan dari node asal

pada waktu

: Jumlah kumulatif kendaraan yang sudah tiba di node tujuan

dari node asal

pada waktu : Waktu tempuh perjalanan untuk melalui link ( (

pada waktu sesaat

.

))

: Waktu tempuh perjalanan untuk melalui rute tujuan pada waktu sesaat . (

∑

dengan node asal

dan node

(

))

: Waktu tempuh perjalanan rute yang minimum untuk rute yang dengan node asal

dan node tujuan pada waktu sesaat . (

{

: Waktu tempuh perjalanan yang minimum dari node asal

}

).

sampai ke

sembarang node pada waktu sesaat . : Himpunan dari link yang keluar dari node : Himpunan dari link yang menuju ke node

3.3 Pendefinisian Kendala Selama periode waktu [0,T] jumlah kendaraan yang bergerak pada suatu link harus ditentukan terlebih dahulu. Penentuan jumlah kendaraan yang bergerak pada suatu link harus memenuhi suatu kondisi, di mana kondisi yang harus dipenuhi tersebut merupakan kendala dalam model pemilihan rute pada tulisan ini. Kendala kendala tersebut terdiri dari :


 Kendala yang menyatakan hubungan antara variabel state dan variabel kontrol o o  Kendala konservasi flow kendaraan o

∑

∑

o ∑

∑

o ∑

∑

 Kendala Flow Propagation ∑

̃(

)

(

)

 Kendala secara definisi o ∑ o ∑ o ∑  Kendala kondisi tidak negatif o o o o o  Kendala kondisi batas o o

3.4 Model Pemilihan Rute Berdasarkan Kondisi Instantaneous Dynamic User Optimal Pada model perencanaan transportasi empat tahap pada tahap ke-empat dilakukan pemilihan rute yang terpendek, tercepat, dan termurah sehingga dihasilkan volume lalu lintas pada setiap rute. Wardrop (1952) dalam prinsip User’s Equilibrium menjelaskan bahwa dalam kondisi keseimbangan tidak ada pengguna jalan yang dapat mengubah rutenya untuk mendapatkan biaya perjalanan yang lebih murah atau waktu tempuh yang lebih cepat, karena semua rute


yang tidak digunakan mempunyai biaya perjalanan yang sama atau lebih besar dari pada rute yang dilaluinya sekarang. Kondisi User’s Equilibrium jika dibagi berdasarkan variasi waktu dibedakan menjadi Static User Equilibrium dan Dynamic User Optimal. Pada Static User Equilibrium, kondisi lalu lintas tidak berubah untuk tiap satuan waktu. Padahal pada kenyataannya (real time) setiap satuan waktu keadaan lalu lintas pasti berubah ubah atau bersifat dinamik. Model pemilihan rute yang dibahas pada tulisan ini merupakan model keseimbangan lalu lintas berdasarkan pandangan pengguna dengan mempertimbangkan variasi dari keadaan lalu lintas yang berubah setiap waktunya atau bersifat dinamik pada waktu sesaat atau Instantaneous Dynamic User Optimal (Instantaneous DUO).

Kondisi pemilihan rute dengan mempertimbangkan waktu sesaat (Instantaneous time) berdasarkan keadaan Dynamic User Optimal (DUO) di mana selanjutnya disebut dengan Instantaneous DUO dibedakan menjadi dua, yaitu berdasarkan pada waktu tempuh perjalanan rute dan berdasarkan waktu tempuh perjalanan link. Pembahasan pada tulisan ini yaitu berdasarkan waktu tempuh perjalanan link.

Keadaan Instantaneous DUO berbasis waktu link terjadi jika flow yang masuk dari node asal menuju node keputusan, untuk semua rute yang digunakan yang menuju node keputusan memiliki waktu tempuh perjalanan yang sama dan minimum berdasarkan waktu sesaat.

Gambar 2 Ilustrasi keadaan Instantaneous DUO berbasis waktu link Misalkan link

, maka kondisi pemilihan rute dengan mempertimbangkan waktu

sesaat berdasarkan keadaan Dynamic User Optimal berbasis waktu link terpenuhi jika persamaan di bawah ini berlaku (

) *(

(3.3a) )

+

(3.3b) (3.3c)


Tanda bintang (*) menyatakan bahwa nilai yang dicapai merupakan solusi optimum dalam keadaan Instantaneous DUO berdasarkan waktu tempuh berbasis link.

Persamaan (3.3c) menyatakan bahwa jumlah kendaraan yang masuk ke link negatif, artinya link tersebut digunakan jika

tidak bernilai

atau link tersebut tidak digunakan jika

. Pernyataan (3.3a) menyatakan bahwa selisih antara waktu tempuh perjalanan menuju node

dengan melewati link

dan waktu tempuh perjalanan yang minimum untuk

menuju node tidak bernilai negatif, artinya waktu tempuh perjalanan menuju node dengan melewati link

dapat lebih besar atau sama dengan waktu tempuh perjalanan yang minimum

menuju node . Persamaan (3.3b) dapat terpenuhi jika +

, artinya jika suatu link

menuju node

yang melalui link

lebih besar dari waktu tempuh perjalanan yang minimum

, artinya jika suatu link

yang melalui link

)

tidak digunakan maka waktu tempuh perjalanan untuk

untuk menuju node , atau dapat pula terpenuhi jika +

dan *(

dan *(

)

digunakan maka waktu tempuh perjalanan untuk rute

sama dengan waktu tempuh perjalanan yang minimum untuk menuju

node .

Permasalahan variational inequality yang ekivalen dengan model pemilihan rute Instantaneous DUO berdasarkan waktu tempuh sesaat berbasis link dapat dinyatakan dalam teorema berikut

Teorema 3.2 (Ran & Boyce, 1996) Pola lalu lintas dinamik yang memenuhi kendala ada dalam kondisi Instantaneous DUO berbasis waktu link jika dan hanya jika memenuhi masalah variational inequality

∫ ∑ ∑[

][

]

3.4 Solusi Algoritma Selanjutnya dijelaskan cara menyelesaikan model yang telah diformulasikan ke dalam bentuk variational inequality berbasis link. Dalam algoritma pencarian solusi untuk permasalahan pemilihan rute, model variational inequality untuk kondisi Instantaneous DUO berdasarkan


waktu tempuh link diubah menjadi bentuk diskrit, kemudian model variational inequality diskrit diformulasikan menjadi pemrograman nonlinear dengan metode relaksasi. Pemrograman nonlinear tersebut selanjutnya diselesaikan menggunakan metode Frank Wolfe.

Untuk mengubah model Instantaneous DUO ke dalam bentuk pemrograman nonlinear, periode waktu

dibagi ke dalam K interval waktu yang lebih kecil dan meningkat. Setiap

waktu peningkatan merupakan sebuah unit waktu. Oleh karena itu, flow masuk ke sembarang link keluar dari link

selama interval waktu

merepresentasikan

,

merepresentasikan flow

selama interval waktu . Untuk membuat formulasi lebih sederhana, maka

modifikasikan estimasi waktu tempuh sesaat pada setiap link sedemikian sehingga setiap estimasi waktu tempuh aktual merupakan kelipatan dari interval waktu seperti berikut. ̅

̅

di mana adalah bilangan bulat dan

Model

variational

) ∑

inequality

.

yang

diselesaikan

adalah

∫ ∑ ∑

(

dan setelah diubah menjadi model variational inequality diskrit menjadi

∑ ∑

(

)

, di mana

.

Fungsi objektif pada pemrograman nonlinear yang ekivalen dengan model diskrit variational inequality yang didapat dengan metode relaksasi adalah sebagai berikut ∑ ∑ (∫

∑

(̅

̅

))

Tanda bar ( ̅ ) tersebut menyatakan bahwa pada nilai yang diberi tanda bar dilakukan metode pembulatan. Pemrograman nonlinear di atas ekivalen dengan bentuk model variational inequality diskrit karena terlihat bahwa gradien terhadap

dari fungsi objektif nonlinear

di atas sama dengan fungsi objektif pada model variational inequality diskrit.

Kendala yang telah disebutkan pada 3.3 setelah diubah menjadi bentuk diskrit adalah sebagai berikut.

∑ ∑

∑

∑


∑

∑ ∑

̃

{

[

]

}

{

}

,

Selanjutnya dalam penyelesaian pemrograman nonlinear, terlebih dahulu, notasikan variabel ̅ untuk suatu submasalah, di mana variabel tersebut berkorespondensi dengan . Pada algoritma Frank Wolfe, pemrograman nonlinear diubah menjadi pemrograman linier. Berdasarkan pembahasan pada 2.1 maka pemrograman linier yang harus diselesaikan adalah sebagai berikut ̂

∑

∑

∑

̅

∑

∑ ̅

di mana ̅

̅

∫ ∫

Penyelesaian pemrograman linier pada persamaan tersebut dapat diselesaikan dengan cara mencari rute yang memiliki bobot terendah pada expanded time-space network. Langkah langkah untuk membuat expanded time-space network adalah sebagai berikut 1. Setiap node yang berada di jaringan awal termasuk node asal dan node tujuan diekspansi sehingga jumlah setiap node

adalah

. Untuk setiap node

yang merupakan hasil

ekspansi akan mewakili node pada setiap interval waktu. 2. Karena terdapat tiga variabel untuk setiap link a, maka setiap link a yang berada pada jaringan awal diekspansi sehingga jumlah setiap link a adalah 3 di mana: a. Terdapat

node yang merupakan node transshipment, yaitu node tambahan yang

diletakkan di antara dua node pada jaringan awal. Pada Gambar 4 yang merupakan node transshipment adalah node

.


b. Terdapat

link = (

node transshipment

. Link ini mempunyai bobot

dan

jumlah kendaraan yang melalui link ini dinyatakan sebagai c. Terdapat

link = node transshipment


dan jumlah kendaraan yang melalui link ini dinyatakan sebagai d. Terdapat

link = (node transshipment

mempunyai bobot

, node transshipment

). Link ini

dan jumlah kendaraan yang lewat pada link ini dinyatakan

sebagai e. Terdapat satu link ̂

node transshipment


̂

dan

jumlah kendaraan yang lewat pada link ini dinyatakan sebagai 3. Pada expanded time-space network terdapat satu node super destination ( ) yang merupakan node tujuan akhir dari perjalanan kendaraan. Terdapat juga =

dan link

link

, di mana

merupakan node tujuan yang bukan node

super destination. Link ini mempunyai bobot

dan jumlah kendaraan yang

melalui link ini dinyatakan sebagai ̅

.

Penyelesaian submasalah pemrograman linier pada metode Frank-Wolfe yaitu dengan mencari rute yang memiliki jumlah bobot terendah pada time expanded network dengan menyesuaikan kendala flow propagation yang ada.

Penyesuaian flow propagasi dilakukan berdasarkan waktu tempuh aktual link. Jika ̅

, maka subrute untuk link

pada time expanded

network yang memenuhi flow propagasi adalah

.

Setelah menyelesaikan pemrograman linier, selanjutnya solusi yang baru dari algoritma Frank Wolfe dinotasikan sebagai berikut

di mana

adalah besar langkah perpindahan dari

ke

yang optimum, didapat

dari penyelesaian pemrograman matematika berikut ini. ∑∑∫

∑


[̅

̅

]

4. CONTOH APLIKASI

Gambar 5 Jaringan lalu lintas sederhana untuk perhitungan numerik Terdapat sebuah ilustrasi untuk mendapatkan solusi model Instantaneous DUO berbasis link yang diterapkan dalam jaringan lalu lintas sederhana yang terdiri dari 3 node dan 4 link, serta terdapat 4 rute yang menghubungkan node 1 dan node 3, yaitu rute 1 = rute 3 =

dan rute 4 =

rute 2 =

seperti yang terlihat pada Gambar 5.

Selanjutnya dilakukan peninjauan mengenai berapakah jumlah kendaraan yang melalui setiap ruas jalan agar dihasilkan waktu tempuh yang minimum dan relatif sama pada setiap rute yang menghubungkan node 1 dan node 3. Peninjauan dilakukan selama periode waktu menit dan dibagi menjadi 4 interval waktu dengan kenaikan 60 menit per interval. Asumsikan untuk semua ruas jalan atau link memiliki fungsi matematis untuk waktu tempuh perjalanan sama yaitu

Misalkan selama periode

menit flow kendaraan yang memasuki jaringan lalu lintas

pada Gambar 5 per interval waktu dapat dinyatakan sebagai berikut Tabel 1. Flow kendaraan yang memasuki jaringan lalu lintas per interval waktu Interval waktu Flow/interval

1 30

2 0

3 0

4 0

Flow kendaraan, waktu tempuh untuk setiap link, dan waktu tempuh untuk setiap rute per interval waktu dapat dinyatakan sebagai berikut Tabel 2. Flow masuk, flow keluar, jumlah kendaraan yang berada pada setiap link dan waktu tempuh untuk setiap link per interval waktu Link

Interval waktu 1 12 0 0

2 0 6 12

3 0 6 6


4 0 0 0

1.076 18 0

1.04 0 9

0.716 0 9

0.5 0 0

0 1.796 0 0 0 0.5

18 1.715 6 0 0 0.6440

9 0.986 8 3 6 0.8910

0 0.5 0 11 11 1.226

0 0 0 0.5

9 0 0 0.824

7 5 9 1.014

0 11 11 1.226

Perhitungan numerik untuk menyelesaikan model pemilihan rute dengan mempertimbangkan waktu sesaat berdasarkan kondisi Dynamic User Optimal dengan metode Frank Wolfe menggunakan bantuan perangkat lunak MATLAB. Solusi optimal kasus Tabel 2 adalah sebagai berikut.

Tabel 3. Flow masuk, flow keluar, jumlah kendaraan yang berada pada setiap link dan waktu tempuh untuk setiap link per interval waktu yang optimum

Link

Interval waktu 1 13.3755

2 0

3 0

4 0

0 0 1.2155 16.6245 0 0

7.834 13.3755 1.2207 0 8.3122 16.6245

5.5415 5.5415 0.6843 0 8.3122 8.3122

0 0 0.5 0 0 0

1.6056 0 0 0 0.5 0

0.5365 7.8340 0 0 0.7454 8.3122

0.9146 7.3887 5.0633 7.8340 0.9793 6.4651

0.5 0 10.1594 10.1594 1.1194 0

0 0 0.5

0 0 0.7764

4.6179 8.3122 0.9385

10.1594 10.1594 1.1194


Tabel 4. Waktu tempuh perjalanan setiap rute berdasarkan waktu sesaat per interval yang optimum Rute

1 1.7155 1.7155 2.1056 2.1056

Interval waktu 2 3 1.9661 1.6636 1.9971 1.6228 2.2819 1.8939 2.3129 1.8531

4 1.6194 1.6194 1.6194 1.6194

5. KESIMPULAN DAN SARAN

5.1 Kesimpulan Metode Frank Wolfe dapat digunakan untuk menyelesaikan model untuk mendapatkan flow kendaraan yang tepat untuk setiap ruas jalan dalam jaringan jalan yang memenuhi kondisi Instantaneous Dynamic User Optimal. Langkah langkah untuk menyelesaikan model Instantaneous DUO yaitu model pemilihan rute berdasarkan kondisi Instantaneous Dynamic User Optimal diformulasikan menjadi model variational inequality, selanjutnya pemrograman linier yang ekivalen dengan model variational inequality berbasis link diselesaikan dengan menggunakan Metode Frank Wolfe. Dengan menggunakan contoh jaringan lalu lintas yang sederhana, secara numerik ditunjukkan bahwa waktu tempuh yang optimum atau yang memenuhi kondisi Instantaneous DUO untuk setiap rutenya adalah relatif sama dan waktu tempuh tersebut merupakan waktu tempuh yang minimal untuk setiap kondisi awal lalu lintas. Perancangan model keseimbangan dengan mempertimbangkan waktu Instantaneous dibutuhkan untuk panduan perjalanan yang tidak mempertimbangkan kemacetan pada periode berikutnya. Model Instantaneous DUO dianjurkan untuk diaplikasikan oleh media informasi lalu lintas seperti radio, televisi, waze, dll yang memberikan informasi kepada pengendara lalu lintas saat pengendara tersebut ingin memulai perjalanannya. Model ini berguna bagi pengendara yang mengandalkan informasi lalu lintas dari media informasi tersebut atau pengendara yang tidak memperhatikan keadaan lalu lintas pada waktu yang telah berlalu.

5.2 Saran Beberapa saran dari penulis yang dapat diberikan untuk perkembangan penelitian ini adalah sebagai berikut: 1. Menyelesaikan model Instantaneous DUO pada jaringan yang lebih besar.


2. Menggunakan algoritma berbasis link lainnya yang dapat meningkatkan efisiensi komputasi dalam menyelesaikan model Instantaneous DUO. 3. Menggunakan algoritma berbasis rute dalam menyelesaikan model Instantaneous DUO.

DAFTAR REFERENSI Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1993). Network Flow: Theory, Algorithms, and Applications. United States of America.: Prentice Hall. Chiu, Y. C. (2011). Dynamic Traffic Assignment: A primer. Transportation Research Board of The National Academy. Washington D.C. Ferrentino, R. (2007). Variational Inequalities and Optimization Problems. Applied Mathematical Sciences, Vol. 1. KSP. (2009, September 10). Megapolitan : Kompas.com. Retrieved Desember 24, 2014, from Kompas.com: megapolitan.kompas.com/read/2009/09/10/14592832/wow.kerugian.akibat Lestari, H., & Caturiyati, P. (2011). Optimisasi Konveks: Konsep-Konsep. Seminar Nasional Penelitian, Pendidikan dan Penerapan MIPA, Fakultas MIPA, Universitas Negeri Yogyakarta. Mahadevan, S., & Gemp, I. (2014). Modeling Context in Cognition Using Variational Inequalities. Mahmassani, H. S., Lu, C.-C., & Zhou, X. (2008). Equivalent gap function-based reformulation and solution algorithm for the dynamic user equilibrium problem. Transportation Research Part B 43 (2009), 345–364. Nagurney, A. (2002). Variational Inequalities. Ortuzar, J. d., & Willumsen, L. G. (2011). Modelling Transport 4 th Edition. New Delhi: John Wiley &Sons, Ltd. Palomar, D. P., & Scutari, G. (2012). Variational Inequality Theory: A Mathematical Framework for Multiuser Communication Systems and Signali. International Workshop on Mathematical Issues in Information Science. Xi'an, China. Patriksson, M., & Rockafellar, R. T. (2001). Variational Geometry and Equilibrium. Purcell, E., Varberg, D., & Rigdon, S. (2006). Calculus (9rd Edition). Ran, B., & Boyce, D. (1992). A New Class of Instantaneous Dynamic User-Optimal Traffic Assignment Models. Ran, B., & Boyce, D. (1996). Modeling Dynamic Transportation Networks an Intelligent Transportation System Oriented Approach. Heidelgerg: Springer-Verlag. Sheffi, Y. (1985). Urban Transportation Networks: Equilibrium Analysis with Methematical Programming Methods. Englewood Cliffs. N. J: Prentice-Hall. Shin, S., & Lee, K. H. (2002). Physical Network Algorithm for A Link-Based Dynamic Traffic Assignment Model. KCSE Journal of Civil Engineering Vol. 6, No. 4, 509-522. Tamin, O. (2000). Perencanaan dan Pemodelan Transportasi. ITB.


Model Pemilihan Rute dengan Mempertimbangkan Waktu Sesaat Berdasarkan Kondisi Dynamic User Optimal

Recommend Documents