Oleh :
- Felicia Gillian Tekad Tuerah
- 13518070
Welcome to Oldenburg ! Kota kecil cantik ini merupakan sebuah kota kecil di barat lau kota Bremen , Jerman , dengan penduduk kurang lebih 168 ribu jiwa [2018]. Kota kecil ini cocok menjadi lahan uji coba untuk melakukan pemodelan sederhana pembuatan rute pengantaran logistik.
Setiap beberapa jam sekali, sebuah perusahaan logistik akan mengirimkan beberapa kurirnya untuk mengantar barang dari kantor pusat mereka ke beberapa titik tujuan yang tersebar di penjuru kota Oldenburg. Anda diminta untuk mencari rute untuk seluruh kurir sehingga jarak yang ditempuh oleh semua kurir paling kecil, sehingga perusahaan logistik dapat menghemat biaya bensin.
Masalah pengantaran barang untuk satu kendaraan dengan fungsi objektif jarak minimal dapat dimodelkan oleh Travelling Salesman Problem. Akan tetapi, perusahaan logistik biasanya memiliki lebih dari satu kendaraan yang berangkat bersamaan, sehingga TSP kurang cocok digunakan. Generalisasi TSP untuk beberapa agen adalah multiple-agent TSP (mTSP), dan model masalah ini akan kita gunakan. Pada mTSP, akan terdapat m tur yang akan dibangun. Syarat dari semua tur mirip dengan TSP, yaitu bahwa seluruh tur akan kembali ke simpul awal (mewakili kantor pusat) dan setiap tujuan hanya akan dilewati oleh satu tur.
Kita akan menggunakan dataset jalanan pada kota Oldenburg yang dapat diakses pada tautan ini. Lakukan pengunduhan untuk kedua data jalanan di kota Oldenburg. Data pertama merupakan koordinat simpul, data kedua merupakan data sisi antar simpul. Asumsikan seluruh jalan dua arah.
Seperti yang disebutkan sebelumnya, kita akan menggunakan pendekatan mTSP dalam permasalahan ini. Untuk mempermudah anda dan mempermudah penilaian, tugas akan dibagi dalam beberapa tahap.
Dalam menyelesaikan tugas ini, saya menggunakan beberapa library yakni:
- networkx (untuk menggambar simpul dan sisi dari upagraf)
- matplotlib (untuk menampilkan gambar graf )
Sebelum menjalankan program, yang perlu disiapkan adalah :
- Python 3.0 or above
- Networkx
pip install networkx
- Matplotlib
pip install matplotlib
Cara menjalankan program cukup mudah yakni :
- Buka folder tempat kode disimpan
- Menjalankan kode main dari kode sumber di terminal
py main.py
- Kemudian, ikuti instruksi dari program
Algoritma dibuat dengan menggunakan prinsip backtracking dan rekursif untuk memperoleh jarak terpendek dari simpul satu ke simpul lainnya. Algoritma ini digunakan untuk memperoleh upagraf dan matriks jarak dari beberapa kota tujuan dan kantor pusat terlebih dahulu. Syarat dari algoritma ini adalah tidak boleh ada kota yang terlewati dua kali. Kemudian, untuk penyelesaian mTSP memanfaatkan matriks jarak upagraf yang diperoleh sebelumnya serta memanfaatkan algoritma Branch and Bound dengan mengambil jarak terkecil di setiap langkahnya.
Silahkan gunakan referensi berikut sebagai awal pengerjaan tugas:
[1] Dataset : https://www.cs.utah.edu/~lifeifei/SpatialDataset.htm
[2] Pengenalan dan formulasi mTSP : https://neos-guide.org/content/multiple-traveling-salesman-problem-mtsp
[3] MIP , pustaka Python untuk optimisasi : https://python-mip.readthedocs.io/en/latest/intro.html
[4] OpenGL untuk Python : https://stackabuse.com/brief-introduction-to-opengl-in-python-with-pyopengl/
[5] Li, Feifei, Dihan Cheng, Marios Hadjieleftheriou, George Kollios, and Shang-Hua Teng. "On trip planning queries in spatial databases." In International symposium on spatial and temporal databases, pp. 273-290. Springer, Berlin, Heidelberg, 2005.
Thank you for Li Fei Fei et. al. for providing the data.