Car Pooling

C A R P O O L I N G, PROBLEMS AND ALGORITHM

Combinatorial Optimization

A presentation by Daniel, Regita, and Husein

PEOPLE BEHIND THE GREAT WORK

May !e Force Be With Us

Daniel Adi Kristanto

Regitha Lorenza

Husein Abdulsalam

10111023 10110037 10111023

Suatu perusahaan di kota P memiliki agen yang ditempatkan ditiap-tiap kota terpisah. Setiap bulannya perusahaan ini mengadakan rapat di kota P. Pada awal keberjalanannya tiap agen berangkat dengan mobil masing-masing ke kota P. Karena biaya operasional naik, maka perusahaan harus menghemat. Untuk meminimalkan biaya pergi meeting para agen, perusahaan menerapkan kebijakan supaya terdapat agen-agen yang menjemput dan memberi tumpangan agen-agen lain.

I n t r o

Hanya beberapa agen saja yang bisa bertemu dan berangkat dari suatu kota. Berangkatnya bersama-sama dengan satu mobil dan meninggalkan mobil lainnya di kota itu. Mobil tidak dapat ditinggalkan kecuali di rumah seorang agen Semua mobil memiliki kapasitas terbatas, termasuk supir.

A s u m s i

!

"

#$%

$&

$%

$'

$(%%

#

$"$(

!

$$

$!

$&%%

(#

$$

(

$%

$%$(

)$(

$*

(

$"$!

$!

$*

'

$"$"

#

$&

!$'

!

'$$

$$$$

$*$

%

)

&

"

'

(

!

#

$*

Misalkan kita representasikan tiap kota adalah titik dan jalan yang menghubungkan kota satu dan kota lain adalah edge atau ruas garis dari suatu graf. Bobot edge merepresentasikan jarak yang menghubungkan kota i dan j De!nisikan C sebagai himpunan dari pohon-pohon. C= (T1, T2, ..., Tm) Tiap pohon Ti adalah subgraf dari G.

K o n s e p

Tiap titik selain P, adalah anggota tepat dari satu pohon. Titik P adalah anggota dari semua pohon. Tiap pohon memiliki maksimum titik. Jumlah jarak semua edge dalam pohon adalah minimal.

S y a r a t

!e Nearest-Point Procedure

!e Triangular Heuristic

!e Tree-Collapsing Heuristic

M e t o de

Konsep Membandingkan jarak antar daerah dan mengkonstruksi perjalanan dari daerah terjauh ke daerah terdekat. Pohon yang ditemukan Tidak terjadi cycling dengan edge yang sudah terpilih Setiap trip tidak lebih dari 5 edge sudah termasuk verteks tujuan. Setiap trip harus mengikutsertakan verteks tujuan (dalam hal ini P).

Nearest-point Procedure

•  Urutkan setiap titik asal dari yang terjauh hingga terdekat dengan verteks tujuan (titik P).

•  Ambil titik terjauh dari P, misalkan x1. Ambil titik dengan jarak terkecil dari x1, misalkan x2. Bentuk x1, x2 sebagai suatu trip x1, x2. Lakukan iterasi ini dari titik yang terjauh hingga terdekat dengan P. Jika suatu titik membentuk trip yang menyebabkan siklus dengan trip lainnya, maka ganti jarak terkecil semula ke jarak terkecil selanjutnya.

•  Gabungkan trip-trip yang telah terbentuk di langkah 2.

•  Hitung total jarak yang ditempuh seluruh trip.


A l g o r i t m a


P e n e r a p a n

Kota Kota Tujuan 1 2 3 4 5 6 7 8 9 10

2 8 0 9 15 17 8 11 18 14 22 3 5 9 0 7 9 11 7 12 12 17 4 9 15 7 0 3 17 10 7 15 18 5 12 17 9 3 0 18 10 6 15 15 6 14 8 11 17 18 0 9 14 8 16 7 12 11 7 10 10 9 0 8 6 11 8 16 18 12 7 6 14 8 0 11 11 9 17 14 12 15 15 8 6 11 0 10

10 22 22 17 18 15 16 11 11 10 0

Urutkan setiap titik asal dari yang terjauh hingga terdekat dengan kota 1. Perhatikan kolom pertama

Titik P = kota kumpul adalah kota 1 Baris pertama dihilangkan karena kita mementingkan jarak ke kota 1

10 à 9 à 8 à 6 à 7 à 5 à 4 à 2 à 3

Kota 10 adalah kota terjauh dari kota 1 Kota terdekat dengan kota 10 yaitu kota 9. Pilih kota 9 Maka {10,9} adalah bagian dari solusi

10

9

1

2

4

5

8

6

3

7

Selanjutnya dari kota terjauh urutan kedua yaitu kota 9, pilih kota yang terdekat dengan kota 9 yaitu kota 7 Maka {9,7} adalah bagian dari solusi

Selanjutnya kota 8, pilih kota yang jaraknya terdekat dengan kota 8 yaitu kota 5 Maka {8,5} adalah bagian dari solusi

Selanjutnya pada kota 6 kita pilih jarak kota terdekat pilih indeks terbesar yaitu kota 9 Maka {6,9} adalah bagian dari solusi

Selanjutnya kota 7, pilih kota terdekat yakni kota 9 tetapi cycle, maka pilih terdekat kedua yaitu kota 3 Maka {7,3} adalah bagian dari solusi

Sambungkan kota 3 ke kota 1. Dengan mengabaikan {8,5} sudah mempunyai 5 sisi yaitu kota 6,9,10,7,3 serta 1

Urutan kota berdasarkan jarak ke kota 1 : 10 à 9 à 8 à 6 à 7 à 5 à 4 à 2 à 3

Selanjutnya kota 5, pilih kota terdekat yaitu kota 4 Maka {5,4} adalah bagian dari solusi

Kota selanjutnya yang terdekat dengan kota 4 adalah kota 3 dan kota 8, jika pilih kota 8 akan cycle, jika pilih kota 3 akan lebih dari 5 sisi maka pilih kota 1 Maka {4,1} adalah bagian dari solusi

Selanjutnya kota 4, pilih kota terdekat yaitu kota 5 akan siklus maka ini ditolak

Konsep Membangun solusi pohon dengan membandingkan jarak terkecil antartitik secara rekursif. Pohon yang ditemukan Tidak terjadi cycling dengan edge yang sudah terpilih Setiap trip tidak lebih dari 5 edge sudah termasuk verteks tujuan. Setiap trip harus mengikutsertakan verteks tujuan (dalam hal ini P).

"e Triangular Heuristic

Pilih p verteks yang belum dipilih dengan jarak terjauh dari 1. Daftar semua edge p,j dengan aturan : 1. d(j,1) = d(p,1) 2. d(p,j) = d(p,1) Pilih edge yang sudah didaftar di langkah 2 dengan edge (p,j) . Pilih yang jaraknya paling minimum dan tidak membentu siklus atau membuat pohon dengan lebih dari 5 edge Jika tidak terdapat edge yang memenuhi syarat pada langkah 3, pilih edge (p,1). Jika ada, ganti p dengan j, dan ulangi langkah 2, 3, dan 4 Ulangi langkah 1-4 sampai semua verteks menjadi bagian dari masing-masing pohon.

"e Triangular Heuristic

A l g o r i t m a


P e n e r a p a n

Kota Kota Tujuan 1 2 3 4 5 6 7 8 9 10

2 8 0 9 15 17 8 11 18 14 22 3 5 9 0 7 9 11 7 12 12 17 4 9 15 7 0 3 17 10 7 15 18 5 12 17 9 3 0 18 10 6 15 15 6 14 8 11 17 18 0 9 14 8 16 7 12 11 7 10 10 9 0 8 6 11 8 16 18 12 7 6 14 8 0 11 11 9 17 14 12 15 15 8 6 11 0 10

10 22 22 17 18 15 16 11 11 10 0

Urutkan setiap titik asal dari yang terjauh hingga terdekat dengan kota 1. Perhatikan kolom pertama

Titik P = kota kumpul adalah kota 1 Baris pertama dihilangkan karena kita mementingkan jarak ke kota 1

10 à 9 à 8 à 6 à 7 à 5 à 4 à 2 à 3

10

9

6

1

2

4

5

8

3

7

Kota 2 3 4 5 6 7 8 9 10

1 8 5 9 12 14 12 16 17 22

Jarak kota 1 ke kota lainnya

Jarak kota p ke kota lainnya

Kota 1 2 3 4 5 6 7 8 9 10

P=10 22 22 17 18 15 16 11 11 10 0

Bandingkan, Pilih, Ganti

Car Pooling

Documents