Di seluruh negeri, ratusan ribu pengemudi mengirimkan paket ke pelanggan dan perusahaan setiap hari, dengan rata-rata waktu klik ke pintu yang rata-rata hanya beberapa hari. Mengkoordinasikan pencapaian rantai pasokan sebesar ini dengan cara yang dapat diprediksi dan tepat waktu merupakan masalah riset operasi yang sudah berlangsung lama, di mana para peneliti telah berupaya mengoptimalkan rute pengiriman tahap terakhir. Hal ini karena tahap terakhir dari proses ini sering kali merupakan proses yang paling mahal akibat inefisiensi seperti jarak antar halte yang jauh karena meningkatnya permintaan e-commerce, penundaan karena cuaca, lalu lintas, kurangnya ketersediaan tempat parkir, preferensi pengiriman pelanggan, atau truk yang terisi sebagian — inefisiensi menjadi lebih parah. berlebihan dan nyata selama pandemi.
Dengan teknologi yang lebih baru dan data yang lebih individual dan bernuansa, para peneliti dapat mengembangkan model dengan opsi perutean yang lebih baik namun pada saat yang sama perlu menyeimbangkan biaya komputasi untuk menjalankannya. Matthias Winkenbach, ilmuwan peneliti utama MIT, direktur penelitian Pusat Transportasi dan Logistik (CTL) MIT dan peneliti di MIT-IBM Watson AI Lab, membahas bagaimana kecerdasan buatan dapat memberikan solusi komputasi yang lebih baik dan efisien untuk optimalisasi kombinatorial masalah seperti ini.
Q: Apa masalah rute kendaraan, dan bagaimana metode riset operasi (OR) tradisional mengatasinya?
A: Masalah perutean kendaraan dihadapi oleh hampir semua perusahaan logistik dan pengiriman seperti USPS, Amazon, UPS, FedEx, DHL setiap hari. Sederhananya, ini adalah menemukan rute efisien yang menghubungkan sekelompok pelanggan yang perlu diantar, atau sesuatu perlu diambil dari mereka. Ini menentukan pelanggan mana dari setiap kendaraan tersebut — yang Anda lihat di jalan — yang harus dikunjungi pada hari tertentu dan dalam urutan apa. Biasanya tujuannya adalah untuk menemukan rute yang menuju ke rute terpendek, tercepat, atau termurah. Namun sering kali hal ini juga didorong oleh kendala yang khusus terjadi pada pelanggan. Misalnya, jika Anda memiliki pelanggan yang memiliki jangka waktu pengiriman yang ditentukan, atau pelanggan di lantai 15 di gedung bertingkat tinggi versus lantai dasar. Hal ini membuat pelanggan ini lebih sulit untuk diintegrasikan ke dalam rute pengiriman yang efisien.
Untuk mengatasi masalah perutean kendaraan, kami jelas tidak dapat melakukan pemodelan tanpa informasi permintaan yang tepat dan, idealnya, karakteristik terkait pelanggan. Misalnya, kita perlu mengetahui ukuran atau berat paket yang dipesan oleh pelanggan tertentu, atau berapa unit produk tertentu yang perlu dikirim ke lokasi tertentu. Semua ini menentukan waktu yang Anda perlukan untuk melayani perhentian tersebut. Untuk masalah realistis, Anda juga ingin mengetahui di mana pengemudi dapat memarkir kendaraannya dengan aman. Secara tradisional, perencana rute harus menghasilkan perkiraan yang baik untuk parameter-parameter ini, sehingga sering kali Anda menemukan model dan alat perencanaan yang membuat asumsi menyeluruh karena tidak tersedia data spesifik perhentian.
Pembelajaran mesin bisa menjadi sangat menarik dalam hal ini karena saat ini sebagian besar pengemudi memiliki ponsel cerdas atau pelacak GPS, sehingga ada banyak sekali informasi mengenai berapa lama waktu yang dibutuhkan untuk mengirimkan paket. Anda sekarang dapat, dalam skala besar, dengan cara yang agak otomatis, mengekstrak informasi tersebut dan mengkalibrasi setiap pemberhentian untuk dimodelkan dengan cara yang realistis.
Menggunakan pendekatan OR tradisional berarti Anda menulis model optimasi, di mana Anda memulai dengan mendefinisikan fungsi tujuan. Dalam kebanyakan kasus, itu semacam fungsi biaya. Lalu ada banyak persamaan lain yang menjelaskan cara kerja masalah perutean. Misalnya, Anda harus memberi tahu model bahwa, jika kendaraan mengunjungi pelanggan, kendaraan tersebut juga harus meninggalkan pelanggan lagi. Dalam istilah akademis, hal itu biasa disebut konservasi aliran. Demikian pula, Anda perlu memastikan bahwa setiap pelanggan dikunjungi tepat satu kali pada rute tertentu. Kendala-kendala ini dan banyak hambatan lain di dunia nyata bersama-sama menentukan rute yang layak. Ini mungkin tampak jelas bagi kita, tapi ini perlu dikodekan secara eksplisit.
Setelah masalah optimasi dirumuskan, terdapat algoritma di luar sana yang membantu kita menemukan solusi terbaik; kami menyebut mereka sebagai pemecah masalah. Seiring waktu mereka menemukan solusi yang sesuai dengan semua kendala. Kemudian, ia mencoba menemukan rute yang lebih baik dan lebih baik, lebih murah dan lebih murah hingga Anda berkata, “Oke, ini cukup baik bagi saya,” atau hingga ia dapat membuktikan secara matematis bahwa ia menemukan solusi optimal. Rata-rata kendaraan pengiriman di kota AS melakukan sekitar 120 pemberhentian. Diperlukan waktu cukup lama untuk menyelesaikan masalah ini secara eksplisit, sehingga hal ini biasanya tidak dilakukan oleh perusahaan, karena terlalu mahal secara komputasi. Oleh karena itu, mereka menggunakan apa yang disebut heuristik, yaitu algoritma yang sangat efisien dalam menemukan solusi yang cukup baik namun biasanya tidak dapat mengukur seberapa jauh solusi tersebut dari optimal teoritis.
Q: Anda sedang menerapkan pembelajaran mesin pada masalah perutean kendaraan. Bagaimana Anda menggunakannya untuk memanfaatkan dan mungkin mengungguli metode OR tradisional?
A: Itulah yang sedang kami kerjakan bersama orang-orang dari MIT-IBM Watson AI Lab. Di sini, ide umumnya adalah Anda melatih model pada sekumpulan besar solusi perutean yang ada yang Anda amati dalam operasi dunia nyata perusahaan atau yang Anda hasilkan menggunakan salah satu heuristik efisien ini. Di sebagian besar model pembelajaran mesin, Anda tidak lagi memiliki fungsi tujuan eksplisit. Sebaliknya, Anda perlu membuat model memahami jenis masalah yang sebenarnya dihadapinya dan seperti apa solusi yang baik untuk masalah tersebut. Misalnya, serupa dengan melatih model bahasa besar tentang kata-kata dalam bahasa tertentu, Anda perlu melatih model pembelajaran rute tentang konsep berbagai perhentian pengiriman dan karakteristik permintaannya. Seperti memahami tata bahasa yang melekat pada bahasa alami, model Anda perlu memahami cara menghubungkan penghentian pengiriman ini sedemikian rupa sehingga menghasilkan solusi yang baik — dalam kasus kami, solusi yang murah atau cepat. Jika Anda kemudian mengajukan serangkaian permintaan pelanggan yang benar-benar baru, perusahaan tersebut masih dapat menghubungkan titik-titik tersebut secara harfiah dengan cara yang juga akan Anda lakukan jika Anda mencoba menemukan rute yang baik untuk menghubungkan pelanggan-pelanggan ini.
Untuk ini, kami menggunakan arsitektur model yang diketahui kebanyakan orang dari ruang pemrosesan bahasa. Tampaknya agak berlawanan dengan intuisi karena apa hubungannya pemrosesan bahasa dengan perutean? Namun sebenarnya, sifat-sifat model ini, terutama model transformator, pandai dalam menemukan struktur bahasa — menghubungkan kata-kata sedemikian rupa sehingga membentuk kalimat. Misalnya, dalam suatu bahasa, Anda mempunyai kosakata tertentu, dan itu tetap. Ini adalah kumpulan kata-kata terpisah yang dapat Anda gunakan, dan tantangannya adalah menggabungkan kata-kata tersebut dengan cara yang bermakna. Dalam perutean, serupa. Di Cambridge ada sekitar 40.000 alamat yang bisa Anda kunjungi. Biasanya, yang perlu dikunjungi adalah subkumpulan alamat tersebut, dan tantangannya adalah: Bagaimana kita menggabungkan subkumpulan ini — “kata-kata” ini — dalam urutan yang masuk akal?
Itulah kebaruan dari pendekatan kami — memanfaatkan struktur yang telah terbukti sangat efektif dalam ruang bahasa dan membawanya ke optimasi kombinatorial. Perutean hanyalah sebuah uji coba yang bagus bagi kami karena ini adalah masalah paling mendasar dalam industri logistik.
Tentu saja, sudah ada algoritma perutean yang sangat bagus yang muncul dari riset operasi selama puluhan tahun. Apa yang kami coba lakukan dalam proyek ini adalah menunjukkan bahwa dengan pendekatan metodologis berbasis pembelajaran mesin yang benar-benar berbeda, kami dapat memprediksi rute yang sama bagusnya, atau lebih baik dari, rute yang akan Anda dapatkan. menjalankan heuristik pengoptimalan rute yang canggih.
Q: Apa kelebihan metode seperti milik Anda dibandingkan teknik OR canggih lainnya?
A: Saat ini, metode terbaik masih sangat membutuhkan sumber daya komputasi yang diperlukan untuk melatih model ini, namun Anda dapat melakukan sebagian dari upaya ini. Kemudian, model yang dilatih relatif efisien dalam menghasilkan solusi baru sesuai kebutuhan.
Aspek lain yang perlu dipertimbangkan adalah lingkungan operasional suatu rute, terutama di perkotaan, terus berubah. Infrastruktur jalan yang tersedia, atau peraturan lalu lintas dan batas kecepatan mungkin berubah, tempat parkir yang ideal mungkin ditempati oleh hal lain, atau lokasi konstruksi mungkin memblokir jalan. Dengan pendekatan berbasis OR murni, Anda mungkin sebenarnya berada dalam masalah karena pada dasarnya Anda harus menyelesaikan seluruh masalah secara instan begitu informasi baru tentang masalah tersebut tersedia. Karena lingkungan operasional berubah secara dinamis, Anda harus melakukan hal ini berulang kali. Meskipun jika Anda memiliki model terlatih yang pernah mengalami masalah serupa sebelumnya, model tersebut berpotensi menyarankan rute terbaik berikutnya untuk diambil, hampir secara instan. Ini lebih merupakan alat yang akan membantu perusahaan untuk menyesuaikan diri terhadap perubahan lingkungan yang semakin tidak dapat diprediksi.
Selain itu, algoritme pengoptimalan sering kali dibuat secara manual untuk memecahkan masalah spesifik suatu perusahaan. Kualitas solusi yang diperoleh dari algoritma eksplisit tersebut dibatasi oleh tingkat detail dan kecanggihan yang digunakan dalam desain algoritma. Sebaliknya, model berbasis pembelajaran terus mempelajari kebijakan perutean dari data. Setelah Anda menentukan struktur model, model pembelajaran rute yang dirancang dengan baik akan menyaring potensi peningkatan kebijakan perutean Anda dari sejumlah besar rute yang sedang dilatih. Sederhananya, alat perutean berbasis pembelajaran akan terus menemukan perbaikan pada rute Anda tanpa Anda harus berinvestasi secara eksplisit merancang perbaikan ini ke dalam algoritma.
Terakhir, metode berbasis optimasi biasanya terbatas pada optimasi fungsi tujuan yang didefinisikan dengan sangat jelas, yang sering kali berupaya meminimalkan biaya atau memaksimalkan keuntungan. Pada kenyataannya, tujuan yang dihadapi perusahaan dan pengemudi jauh lebih kompleks, dan sering kali saling bertentangan. Misalnya, sebuah perusahaan ingin menemukan rute yang efisien, namun juga ingin memiliki jejak emisi yang rendah. Pengemudi juga ingin aman dan memiliki cara yang nyaman dalam melayani pelanggan tersebut. Selain itu semua, perusahaan juga peduli terhadap konsistensi. Model pembelajaran rute yang dirancang dengan baik pada akhirnya dapat menangkap tujuan-tujuan berdimensi tinggi ini dengan sendirinya, dan itu adalah sesuatu yang tidak akan pernah dapat Anda capai dengan cara yang sama dengan pendekatan optimasi tradisional.
Jadi, aplikasi pembelajaran mesin seperti inilah yang benar-benar dapat memberikan dampak nyata di dunia industri, masyarakat, dan lingkungan. Industri logistik mempunyai permasalahan yang jauh lebih kompleks dari ini. Misalnya, jika Anda ingin mengoptimalkan seluruh rantai pasokan — katakanlah, aliran produk dari produsen di Tiongkok melalui jaringan pelabuhan berbeda di seluruh dunia, melalui jaringan distribusi pengecer besar di Amerika Utara ke toko Anda di mana Anda membelinya — ada begitu banyak keputusan yang terlibat di dalamnya, yang jelas menjadikannya tugas yang jauh lebih sulit daripada mengoptimalkan satu rute kendaraan. Harapan kami adalah dengan upaya awal ini, kami dapat meletakkan dasar bagi penelitian dan juga upaya pengembangan sektor swasta untuk membangun alat yang pada akhirnya akan memungkinkan optimalisasi rantai pasokan end-to-end yang lebih baik.
