Optimizing Logistics Distribution Routes: A Graph Theory Approach

Learn By Building adalah metode pembelajaran dengan cara melakukannya dengan menggunakan data kondisi aktual

Tujuan dan Metode

Sebuah perusahaan ingin menemukan jalur distribusi yang paling optimal untuk mengirimkan barang ke masing-masing tujuan.

Metode:

💡 Menggunakan bantuan NetworkX yang merupakan package Python yang digunakan untuk menganalisa jaringan kompleks

💡 Merepresentasikan records ke dalam Graf kemudian mencari rute-rute dengan weight terendah.

💡 weight bisa dalam bentuk total biaya (cost) yang dikeluarkan masing-masing rutenya.

💡 Total cost dapat diekstrak dari data records dengan informasi-informasi yang kita ketahui.

💬 Informasi apa saja yang dapat digunakan untuk mendapatkan biaya?

Studi Kasus

Kita adalah seorang data saintis di sebuah perusahaan produsen makanan dingin di Makassar. Kita diberikan data records_mks, dan lokasi_makassar yang berisi informasi pengiriman antar lokasinya.

Batasan Masalah

Selain informasi dari data ini, kita juga mengetahui beberapa informasi antara lain:

Aturan

Biaya:

⚠ Disclaimer: Bisnis problem dan data bersifat dummy yang terinspirasi dari hasil penelitian Liang, Wu dan Sun [[2](https://doi.org/10.2991/asei-15.2015.145)] dimana mencari rute optimal pada kasus cold chain logistics menggunakan Particle Swarm Optimization (PSO). Inspirasi lain juga berasal dari artikel Samir Saci [[3](https://towardsdatascience.com/transportation-network-analysis-with-graph-theory-55eceb7e4de4)] yang melakukan analisis jaringan distribusi menggunakan Teori Graf.

Persiapan Data

Membaca Data

Deskripsi Data:

Data records merupakan kumpulan catatan pengiriman distribusi. Berikut informasi dari setiap kolom:

Pre-Processing & Feature Engineering

Menyesuaikan Tipe Data

Menambah kolom

Menghitung Biaya Bahan Bakar

Informasi yang dapat digunakan:

💡 Langkah:

Additional Notes: Semakin besar nilai lge/100km maka semakin boros bensin untuk rute tersebut. Hal ini dapat dipengaruhi oleh tingkat kemacetan jalanan dimana penggunaan bahan bakar dapat meningkat 90-170% dari konsumsi normal bensin [[4](https://www.viamichelin.com/magazine/article/traffic-jams-our-tips-for-saving-fuel/#:~:text=An%20idling%20vehicle%20uses%20about,and%20175%25%20in%20urban%20areas)].

Menghitung Biaya Pendingin

Informasi yang dapat digunakan:

💡 Langkah:

Pada datetime dapat dilakukan subtraksi datetime seperti di bawah ini

Biaya Keseluruhan

Total cost akan kita jadikan sebagai weight dalam Graf kita nantinya. Sehingga kita akan mendapatkan kombinasi masing-masing rute beserta total biayanya.

Informasi yang digunakan:

💡 Langkah:

Menjumlahkan masing-masing cost

$ total = costfuel + costrefri + addcost $

5 rute yang membutuhkan cost terbesar

Memeriksa Frekuensi Tertinggi pengiriman barang berdasarkan minggu dalam setahun

disini dapat kita lihat, dari minggu ke-14 sampai minggu ke-18, minggu ke-18 lah yang mengalami frekuensi pengiriman yang paling tinggi dengan 6 rute

dapat kita lihat bahwa hari rabu lah yang mengalami frekuensi pengiriman yang paling tinggi

Mari kita lihat pengiriman pada minggu ke-18 karena mempunyai jadwal pengiriman yang paling tinggi (dengan asumsi pengiriman tinggi adalah pengiriman yang paling lengkap)

Visualisasi Rute Existing

Improvisasi Dengan Graf

Berikut adalah cara untuk mendapatkan rute dengan weight yang paling optimal (minimum weight)

Total Cost -> Total biaya per-rute.

Total Biaya = Biaya bensin + Biaya pendingin + Addition Cost (Tol)

Duplikat

Melihat apakah terdapat duplikat rute. Untuk melakukan pengecekan terhadap ada atau tidaknya data yang duplikat, kita dapat menggunakan method duplicated().

Syntax:

records.duplicated(subset = [kolom], keep = 'first')

Ket:

Visualisasi Graf

Selanjutnya mari kita melakukan pembentukan graf berdasarkan data kita. Sebelum itu mari kita mengambil kolom2 yang dibutuhkan untuk membuat graf

Pencarian Rute Optimal (Total Cost)

Kita dapat menggunakan fungsi graph.get_total() dimana akan membuat dataframe dengan weight terurut dari masing-masing rute.

Sintaks

graph.get_total(G, source, target, cutoff)

keterangan:

Cutoff diset angka 2 karena kapasitas truk hanya dapat menampung 2.2 ton dimana kebutuhan tonase tiap alamat pengiriman adalah 1 ton.

Dilakukan beberapa kali pemeriksaan untuk menemukan variasi rute yang paling rendah totalnya.

Rekomendasi Rute Baru

Rekomendasi Rute Baru (VRP)

Vehicle Routing Problem

Dari hasil yang didapatkan, terdapat 3 rekomendasi rute optimal yang telah mencakup keseluruhan lokasi, antara lain:

Perspektif Bisnis

Selanjutnya mari kita bandingkan total biaya rekomendasi rute baru dengan rute-rute lama.

Kita dapat melihat total biaya untuk setiap pekannya dengan melakukan agregasi tabel menggunakan .pivot_table().

Syntax:

{python}
data.pivot_table(
    index=...,
    columns=...,
    values=...,
    aggfunc=...
)

Kita dapat menggunakan pivot_table dengan beberapa parameter sebagai berikut.

Berhubung rute yang lengkap hanya terjadi pada 3 pekan terakhir

(pekan ke-16, 17 dan 18; diperiksa menggunakan perintah records.weekofyear.value_counts()) .

Maka dari itu kita hanya membandingkan rute rekomendasi dengan rute 3 pekan terakhir.

Biaya total untuk rute 3 pekan terakhir adalah Rp199.368, Rp215.321 dan Rp195.598 (Rerata Rp203.429). Mari kita bandingkan dengan total rute optimal yang kita dapatkan.

Biaya rute baru ini dapat lebih hemat Rp 36.209 (Rerata Rp 203.429 - Rp 167.220)

Visualisasi Rute Baru

Dalam pembuatan visualisasi peta, terdapat 2 step yang harus dilakukan.

  1. Membuat objek peta dengan graph.create_map_object() yang disimpan ke dalam map_object. Inputan fungsi ini adalah string nama daerah koordinat yang ingin kita visualisasikan, dalam hal ini adalah 'Jakarta, Indonesia'.
  2. Melakukan plotting koordinat dan jalur antar koordinat dengan graph.visualize_route(map_object, dataframe). Dimana map_object adalah object dari step 1 dan dataframe adalah kumpulan data koordinat yang ingin kita visualisasikan, dalam hal ini adalah week6. Kolom wajib yang harus terdapat di dalam dataframe:
    • day
    • lokasi_start
    • longitude_start
    • latitude_start
    • lokasi_end
    • longitude_end
    • latitude_end

Mari kita membuat dataframe yang berisi rute baru dan memiliki kolom-kolom yang diperlakukan.

(Pengisian hari diasumsikan pengiriman pada hari yang sama, pada contoh AFB dilakukan pada hari Senin, ADC pada hari selasa dan AEG pada hari rabu)

Dataframe optimize masih belum memiliki nama lokasi_start, lokasi_end serta koordinat titik start (long_start, lat_start) dan koordinat titik end (long_end, lat_end).

Mari kita mengambil informasi nama lokasi dan koordinat lokasi dari dataframe location dengan melakukan pd.merge().

Syntaks:

pd.merge(df_kiri, df_kanan, left_on='key', right_on='key', how='left|right|inner', suffixes=('_x', '_y'))

Keterangan:

Perbandingan dengan rute sebelumnya

Vehicle Routing Problem

Rekomendasi Rute Baru (TRP)

Travelling Salesman Problem

Pada kasus sebelumnya, kita mencari rute optimal dengan maksimal mendatangi 2 lokasi dalam 1 perjalanan. Bagaimana jika kita ingin mendapatkan rute terbaik dengan mendatangi setiap lokasi dalam satu perjalanan? Urutan jalur manakah yang paling optimal? Dan bagaimana cara mencarinya?

Permasalahan ini disebut sebagai Travelling Salesman Problem (TSP) dimana seorang salesman memiliki daftar kota yang harus dikunjungi untuk menjual produk, namun mencari cara paling efisien untuk mengunjungi setiap kota tepat sekali dan kemudian dapat kembali ke titik awal. Cara paling efisien dalam kasus kita tentu saja berarti total cost yang paling rendah untuk mendatangi seluruh lokasi dalam 1 perjalanan.

Networkx telah menyediakan method untuk menyelesaikan permasalahan TSP ini, yaitu menggunakan nx.approximation.travelling_salesman_problem().

Syntax:

nx.approximation.travelling_salesman_problem(G, cycle = True, nodes = G.nodes)

Keterangan:

Detail lebih lengkap dapat merujuk di dokumentasi

Kita telah mendapatkan jalur optimal untuk mengunjungi setiap lokasi dalam 1 kali perjalanan. Jalur optimal ini dihitung berdasarkan weight pada kasus ini adalah total_cost.

Selanjutnya mari kita melihat total weight jalur ini menggunakan nx.path_weight().

Pada perhitungan ini, didapatkan bahwa jalur optimal untuk mengunjungi setiap lokasi dalam 1 kali perjalanan adalah 128.6rb rupiah.

Selanjutnya mari kita lakukan visualisasi rute hasil dari travelling salesman problem. Ingat kembali, untuk membuat visualisasi peta, terdapat 2 step yang harus dilakukan.

  1. Membuat objek peta dengan graph.create_map_object() yang disimpan ke dalam map_object. Inputan fungsi ini adalah string nama daerah koordinat yang ingin kita visualisasikan, dalam hal ini adalah 'Jakarta, Indonesia'.
  2. Melakukan plotting koordinat dan jalur antar koordinat dengan graph.visualize_route(map_object, dataframe). Dimana map_object adalah object dari step 1 dan dataframe adalah kumpulan data koordinat yang ingin kita visualisasikan, dalam hal ini adalah week6. Kolom wajib yang harus terdapat di dalam dataframe:
    • day
    • lokasi_start
    • longitude_start
    • latitude_start
    • lokasi_end
    • longitude_end
    • latitude_end

Maka dari itu mari kita membuat dataframe awal seperti pada "Visualisasi Rute Baru" dimana terdapat kolom start, end, dan day. Pada kasus ini karena kita mengunjungi seluruh lokasi dalam 1 kali perjalanan, maka semua kita samakan saja harinya menjadi Monday.

Dataframe optimize_tsp masih belum memiliki nama lokasi_start, lokasi_end serta koordinat titik start (long_start, lat_start) dan koordinat titik end (long_end, lat_end).

Mari kita mengambil informasi nama lokasi dan koordinat lokasi dari dataframe lokasi dengan melakukan pd.merge().

Dataframe tsp_merge telah siap untuk dilakukan visualisasi, langsung kita lakukan visualisasi menggunakan graph.visualize_route().

Rekomendasi Rute Baru (TRP V2.0)

Dilakukan untuk memastikan titik start dan titik akhir berada di A (Warehouse)

Kesimpulan

Seiring dengan perkembangan komputasi, perusahaan dapat terbantu dengan adanya algoritma yang dapat membantu mengoptimalkan pendistribusian barang. Hal ini dapat dikembangkan secara luas berdasarkan banyaknya data yang tersedia.

References

[1] Wilson, R. J. (2010). Introduction to Graph Theory. New York: Prentice Hall/Pearson. ISBN: 027372889X 9780273728894

[2] Liang, Di & Wu, Shuang & Sun, Guizhi. (2015). Study on Optimization of Cold Chain Logistics Distribution Based on Improved Particle Swarm Optimization Algorithm. 10.2991/asei-15.2015.145.

[3] Saci, Samir. (2022). Transportation Network Analysis with Graph Theory. towardsdatascience.com

[4] Michelin. (2022). Traffic jams: our tips for saving fuel. viamichelin.com

[5] Taherdoost, Hamed, and Mitra Madanchian. 2023. "Multi-Criteria Decision Making (MCDM) Methods and Concepts" Encyclopedia 3, no. 1: 77-87. https://doi.org/10.3390/encyclopedia3010006