Jika Anda belum membacanya, silakan mulai dengan Bagian 1 untuk memahami dasar-dasar proyek ini dan alasan kami melakukannya!

Implementasi

Di bagian 1, kita membahas tentang penerapan pola pikir ilmu data pada masalah akurasi lokasi. Namun bagaimana sebenarnya kita melakukan proses ini? Kami menggunakan python dan kombinasi beberapa alat (lihat tabel di bawah) untuk mewujudkan ide ini. Hal pertama yang kami butuhkan adalah teknik clustering.

DBSCAN, atau “Pengelompokan aplikasi spasial berbasis kepadatan dengan kebisingan”, adalah cara mengelompokkan titik-titik dalam ruang dua dimensi, sehingga berguna untuk kasus seperti yang kita lakukan di mana titik-titik tersebut merupakan tempat sebenarnya di peta. Penjelasan singkatnya adalah kita melihat titik-titik yang tersedia, mencari wilayah dengan volume tertinggi/titik terpadat, dan mengelompokkannya. Jika poin tidak dikaitkan dengan kelompok ini, kami menandainya sebagai outlier.

DBSCAN, atau “Pengelompokan aplikasi spasial berbasis kepadatan dengan noise”, adalah cara mengelompokkan titik-titik dalam ruang dua dimensi.

Untuk lebih detailnya, animasi ini membantu menjelaskan prosedurnya. (Mohon maafkan kemampuan artistik saya.)

Pertama, algoritme akan memeriksa setiap titik secara bergantian, dan menghitung titik-titik lain di lingkungan terdekatnya, suatu ruang yang ditentukan oleh parameter ε (epsilon). Kita mempunyai batas bawah yang menetapkan berapa banyak tetangga di dalam ruang yang harus dimiliki suatu titik, dan jika titik tersebut memenuhi kriteria ini, maka titik tersebut akan dianggap sebagai titik “inti”.

Setelah setiap titik dinilai, titik-titik inti yang berdekatan satu sama lain dikelompokkan ke dalam apa yang disebut komponen-komponen yang terhubung, dan komponen-komponen ini membentuk basis penting dari klaster. Beberapa titik akan berdekatan dengan titik inti, dan membentuk tetangganya, namun tidak akan menjadi titik inti karena titik tetangganya terlalu sedikit (dalam praktiknya hal ini menunjukkan bahwa titik tersebut berada di tepi luar cluster). Ini akan didefinisikan sebagai titik-titik non-inti yang termasuk dalam cluster yang relevan.

Pada titik ini, klaster kita sudah selesai, dan kita dapat menandai semua titik tersisa yang bukan merupakan anggota klaster inti atau non-inti sebagai outlier.

Untuk kasus penggunaan kami, kami menggunakan ping telemetri dari riwayat pergerakan truk pelanggan sebagai bahan baku untuk dikerjakan oleh DBSCAN. Jika pengiriman melibatkan lokasi tertentu, sebagai salah satu perhentian terjadwal, kami akan mengambil titik telemetri yang berisi pengiriman dan memasukkannya ke dalam set pelatihan kami. Ini mungkin berisi titik-titik yang jauh dari perhentian, atau yang menurut kami terkait dengan perhentian lain dalam perjalanan, dan tidak apa-apa! Kami mulai menggunakan jaring yang luas, dan kami akan segera mempersempitnya menggunakan algoritme.

Strategi ini memiliki banyak parameter yang dapat disesuaikan, dan memungkinkan kami menyesuaikan algoritme dengan cukup baik untuk memenuhi kebutuhan pelanggan dan jenis bisnis yang berbeda. Selain parameter DBSCAN, kita harus memutuskan hal berikut:

  • Seberapa jauh kita akan menebarkan jaring untuk menemukan titik-titik yang relevan di sekitar lokasi tersebut? Hal ini juga dipengaruhi oleh adanya beberapa perhentian dari pelanggan yang sama yang sangat berdekatan — kita akan memperkecil seberapa jauh kita melihat untuk telemetri jika ada fasilitas lain di dekatnya, untuk menghindari penggabungan keduanya.
  • Berapa banyak titik yang perlu kita temukan di sekitar lokasi agar menjadi kandidat yang memadai untuk geofencing? Jika riwayat lalu lintas di sekitar terlalu sedikit, algoritme kemungkinan besar akan memberikan hasil yang salah, dan kami lebih memilih tidak memiliki pembatasan wilayah yang cerdas daripada pembatasan wilayah yang buruk.

Setelah kita memilih poin dan menjalankan DBSCAN, lebih banyak keputusan harus diambil, termasuk:

  • Seberapa jauh cluster dapat berada dan masih dapat dimasukkan dari titik awal kita? Terkadang kita akan menemukan cluster yang sangat tersebar, dan beberapa cukup jauh dari lokasi sebenarnya. Dalam implementasinya, kami mengambil klaster yang paling dekat dengan titik awal (yang sebenarnya tidak perlu terlalu dekat, mengingat terkadang alamatnya salah), dan mewajibkan semua klaster lainnya berada relatif dekat dengan titik tersebut. Hal ini memberi kami fleksibilitas yang diperlukan untuk mengelola ketika kami mendapat sedikit kesalahan alamat atau koordinat dari pelanggan.

Setelah semua pekerjaan selesai, kami memiliki sekumpulan titik telemetri berkerumun yang kami yakini mewakili lalu lintas yang relevan dengan lokasi yang kami minati. Tugas terakhir adalah menggambar pembatasan wilayah lokasi, yang kami dilakukan dengan menerapkan convexhull menggunakan GeoPandas pada seluruh titik di seluruh klaster kualifikasi. Kemudian, jika diinginkan (dan biasanya memang demikian), kami menerapkan sejumlah kecil ruang penyangga di seluruh sisi pembatasan wilayah, untuk mengakomodasi ketidakakuratan kecil apa pun. Biasanya jaraknya kurang dari 200 meter.

Evaluasi

Setelah kami membuat pembatasan wilayah lokasi dengan teknik ini, kami perlu menguji dan memvalidasi hasil kami sebelum mengirimkannya ke seluruh dunia. Kami dapat melihatnya di peta (kami menggunakan Folium dan GeoPandas untuk memvisualisasikan pembatasan wilayah dalam volume besar dengan hasil yang luar biasa). Namun, kami mempunyai masalah — kami mungkin tidak memiliki geofence lokasi akurat yang cukup untuk dibandingkan. Terkadang kami memiliki beberapa geofence yang dibuat khusus dan kami pasti dapat melapisinya dengan geofence “pintar” kami yang baru untuk melihat seberapa cocoknya, namun hal ini sulit untuk diukur.

Dalam kasus kami, saya mencoba kembali ke prinsip pertama — untuk apa pembatasan wilayah ini? Tujuan utamanya adalah untuk menangkap secara akurat saat truk mengunjungi suatu lokasi, tanpa menimbulkan kesalahan positif. Jadi, pertama-tama saya mengambil data riwayat perjalanan truk dan menjalankannya kembali dalam simulasi menggunakan batas geofence lokasi baru. Hal ini efektif, namun membutuhkan banyak sumber daya. Namun, hal ini memberikan hasil yang cukup kuat sehingga memungkinkan kami melanjutkan dengan percaya diri.

Pada langkah berikutnya, saya melakukan studi percontohan dengan beberapa pelanggan utama, dan membandingkan perilaku pengiriman sebelum dan sesudahnya. Dua metrik menjadi yang paling berguna, karena keduanya mengukur aspek berbeda dari apa yang kami cari dalam evaluasi perjalanan seimbang.

Yang pertama adalah penarikan kembali pemberhentian, atau persentase pemberhentian terjadwal yang kami catat kunjungannya. Artinya, kami melihat pengiriman dan melihat seberapa sering kami melewatkan pemberhentian, yang mungkin terlalu berlebihan. sering kali jika pembatasan wilayah lokasi kita bentuknya salah atau terlalu kecil. Jika truk mendekat tetapi tidak melintasi pembatasan wilayah pada saat pembaruan, penghentian kedatangan dapat terjadi tetapi tidak ditangkap. Jika nilai ini tidak turun, kita dapat mengatakan bahwa kita menghasilkan geofence lokasi yang cukup besar. Dalam praktiknya, kami telah melihat metrik ini meningkat pada banyak pelanggan, karena pembatasan wilayah yang cerdas tidak hanya lebih kecil, namun terkadang diposisikan lebih akurat dibandingkan alternatif lainnya.

Metrik kedua adalah pengiriman yang rusak, atau pengiriman yang kami catat kunjungan ke pemberhentian tidak mengikuti urutan numerik yang tercantum dalam jadwal. Di sini kami mencoba mengukur kapan pengemudi “memotong” barang yang terlalu besar pembatasan wilayah lokasi secara sepintas — membuat catatan kedatangan yang sebenarnya tidak terjadi (positif palsu). Akibat dari hal ini adalah kami menafsirkan bahwa pemberhentian pengiriman dikunjungi dalam urutan yang berbeda dari yang sebenarnya. Ini adalah masalah yang lebih besar dari yang Anda bayangkan, dan kami ingin mengurangi kasus-kasus di mana hal tersebut terjadi.

Meskipun terkadang pengemudi berhenti dalam urutan yang berbeda dari jadwal, bagi sebagian besar pelanggan kami, hal ini bukanlah hal yang umum. Oleh karena itu, jika kiriman tercatat terjadi tidak sesuai pesanan, setidaknya pada beberapa waktu hal tersebut disebabkan karena kami memicu kedatangan dengan memasukkan geofence lokasi secara tidak sengaja — ini berarti kami dapat menggunakan total volume kiriman yang tidak sesuai pesanan sebagai proksi kasar untuk volume pembatasan wilayah yang terlalu besar. Batasan wilayah yang lebih kecil dan bertarget mengurangi terjadinya hal ini, dan menjadikan pelacakan pengiriman kami secara keseluruhan jauh lebih akurat. Jika kami melihat penurunan pengiriman yang tidak sesuai pesanan, maka kami dapat mengatakan bahwa kami memproduksi geofence lokasi yang cukup kecil.

Kedua metrik ini memungkinkan kita mengejar semacam pembatasan wilayah yang sesuai dengan lokasi “goldilocks” yang tidak terlalu kecil atau terlalu besar. Sesuatu seperti ini!

Penerapan

Jadi, kami mengembangkan teknik kami dan memvalidasinya dengan kondisi dunia nyata — kami masih harus menentukan cara terbaik untuk menerapkannya kepada pelanggan. Jika kami hanya memiliki sedikit pelanggan dengan beberapa lokasi yang dilayani, ini mungkin mudah, namun sebenarnya kami memiliki ribuan pelanggan dan jutaan lokasi untuk ditangani.

Saat kami mulai menerapkan fitur ini, hal ini menimbulkan beberapa kekhawatiran seputar biaya dan kepraktisan. Satu hal yang kami sadari adalah banyak lokasi yang relatif jarang dijadwalkan atau dikunjungi. Banyak pelanggan kami yang mengalami kesulitan karena lokasi tujuan pengiriman mereka hanya sekali atau dua kali dalam beberapa tahun. Berdasarkan hal ini, kami memilih untuk terlebih dahulu melihat lokasi yang telah dikunjungi lebih dari beberapa kali dalam satu tahun terakhir, yang membantu mengurangi keseluruhan volume lokasi yang perlu diproses di awal.

Jika kami hanya memiliki sedikit pelanggan dengan beberapa lokasi yang dilayani, ini mungkin mudah, namun sebenarnya kami memiliki ribuan pelanggan dan jutaan lokasi untuk ditangani.

Selain itu, kami bekerja dengan tim Teknik Data untuk mengoptimalkan kueri Snowflake yang kami lakukan dalam proses ini, untuk membuatnya secepat mungkin dan mengurangi waktu aktif gudang yang diperlukan untuk membuat pembatasan wilayah yang cerdas. Salah satu upayanya termasuk penerapan paralelisasi terbatas dengan Dask. Kami awalnya memparalelkan di 16 thread, tapi ini mengirimkan banyak pertanyaan ke Snowflake secara berurutan dan membuat cadangan antrian. Untuk menghindari Snowflake membebani secara berlebihan, kami membatasinya menjadi empat thread — tetap mendapatkan sebagian besar keunggulan kecepatan paralelisasi tanpa membuat I/O kami terhenti. Dengan cara ini kami memangkas biaya signifikan terkait penggunaan Snowflake dari proyek.

Kami juga perlu menentukan cara kami menjalankan tugas untuk pelanggan yang berbeda, dan menjadikannya dapat dijalankan ulang dari waktu ke waktu ketika data historis baru dikumpulkan dan pembatasan wilayah lokasi baru perlu dilakukan. Ilmuwan data kami sudah menggunakan Airflow untuk penjadwalan DAG, jadi ini adalah pilihan yang mudah.

Untuk meneruskan parameter khusus pelanggan ke pekerjaan, kami menggunakan kelas konfigurasi yang memiliki default yang dapat kami sesuaikan saat inisialisasi atau setelahnya. Kami menginisialisasi konfigurasi dan menjalankan pekerjaan Airflow, dan pembatasan wilayah cerdas secara otomatis dibuat dan disimpan langsung di Snowflake. Saat kami membuat pembatasan wilayah untuk banyak pelanggan sekaligus, kami meneruskan daftar pelanggan ke tugas Airflow, yang membuat tugas untuk masing-masing pelanggan dan menjalankannya secara serial (bukan paralel, karena hal itu akan membebani Snowflake seperti yang telah kami bahas di atas) . Slack hooks memberi kami informasi tentang kemajuan tugas ini.

Airflow menggunakan Dask seperti yang digunakan mesin lokal kami, jadi kami masih bisa mendapatkan peningkatan kinerja paralelisasi. Kami dapat menerapkan paralelisme di dalam DAG di Airflow, namun kami tidak ingin mengikat pekerjaan secara permanen ke Airflow, jika kami ingin menggunakan alat penjadwal lainnya. Fleksibilitas Dask berarti kami berkomitmen menggunakan python untuk pekerjaan itu, tapi tidak ada yang lebih spesifik dari itu.

Kesimpulan

Teknik ini ternyata sangat berguna bagi kami dan pelanggan kami. Awalnya kami hanya ingin mengurangi kedatangan “positif palsu”, namun berakhir dengan banyak manfaat lainnya. Misalnya, ketika data alamat pelanggan untuk suatu lokasi sedikit melenceng, katakanlah mereka telah menuliskan 123 Main Street tetapi fasilitasnya ada di 127 Main Street, algoritma ini secara teratur mampu memperbaikinya dan menempatkan geofence lokasi pada posisi yang benar. .

Kami kini juga menghasilkan waktu kedatangan yang lebih tepat dan akurat, yang sangat penting ketika operator dapat dikenakan penalti karena terlambat atau lebih awal dalam membuat janji. Selain itu, kami telah menghemat waktu berjam-jam bagi pelanggan dalam melakukan pekerjaan manual dalam menggambar pembatasan wilayah, dan akan terus menghemat waktu pelanggan baru dalam melakukan pekerjaan yang membosankan ini.

Saya rasa proyek ini adalah contoh nyata bagaimana ilmu data dapat memberikan peningkatan yang berarti dalam cara kita melakukan berbagai hal di industri. Daripada hanya melakukan pekerjaan teoretis, saya senang menyusun solusi praktis berdasarkan data untuk mengatasi masalah dan tantangan masyarakat nyata. Saya beruntung berada di perusahaan yang memprioritaskan hal ini — menyelesaikan masalah pelanggan untuk membuat logistik dan rantai pasokan lebih efisien dan transparan. Hal ini memberikan manfaat bagi semua orang, karena ini berarti semua barang yang diangkut ke seluruh dunia setiap hari (bahkan sampai ke depan pintu Anda!) dapat dilacak secara akurat dan transparan.

Terima kasih telah membaca hingga akhir seri ini — Saya harap upaya kami menginspirasi Anda untuk menerapkan pola pikir data scientist terhadap tantangan dalam pekerjaan Anda!

Stephanie Kirmer adalah Staf Ilmuwan Data di project44, penyedia platform visibilitas dan analitik terkemuka untuk pengiriman dan logistik. Dia memiliki pengalaman ilmu data terapan dan rekayasa data selama satu dekade di sejumlah industri, termasuk perhotelan/perjalanan, IOT, perangkat lunak, dan akademisi. Dalam perannya saat ini, ia adalah pimpinan teknis ilmu data untuk sektor Over the Road, yang mencakup angkutan truk di AS dan global. Sebelum menjadi data scientist, ia bekerja di dunia akademis dan mengajar sosiologi dan kebijakan kesehatan di DePaul University. Untuk mempelajari lebih lanjut, kunjungi www.stephaniekirmer.com.