Tugas pengiriman barang

Dalam posting ini, kita akan melihat bagaimana Flexport menggunakan matematika dan ilmu data untuk menyelesaikan masalah pengiriman dan mengirimkan barang tepat waktu dengan biaya serendah mungkin.

Pertimbangkan skenario spekulatif: pengirim memiliki sepuluh keberangkatan dan satu penerbangan tujuan untuk pengiriman apa pun. Satu-satunya keputusan yang harus diambil adalah apakah akan menetapkan setiap pengiriman untuk penerbangan tunggal ini. Jika kami tidak menetapkan beban tertentu untuk penerbangan, anggaplah mungkin untuk memindahkannya dengan cara lain.

Setiap pengiriman memiliki volume dan biaya, dan penerbangan dibatasi dalam volume. Anda mungkin menganggapnya sebagai masalah ransel yang disederhanakan. Jadi, ada 1024-1 = 1023 kemungkinan solusi (kami tidak akan mengirim pesawat kosong sama sekali).

Kita dapat membuat spreadsheet untuk mendaftar seluruh solusi dan memilih yang paling menguntungkan. Tetapi bagaimana jika Anda memiliki sepuluh keberangkatan yang sama, tetapi dua penerbangan? Ini adalah 59.049 solusi hanya dalam 10 pengiriman.

Forwarder besar memiliki lebih dari sepuluh keberangkatan dan, tentu saja, lebih dari dua penerbangan untuk dipilih, yang mengarah ke triliunan hingga triliunan solusi yang mungkin. Di antara mereka, hanya jutaan yang layak, yang berarti bahwa metode spreadsheet tradisional dapat menemukan setidaknya satu solusi yang layak. Tetapi kita tidak hanya membutuhkan solusi yang layak. Kami membutuhkan yang terbaik, solusi optimal. Bagaimana menemukan mereka di antara berbagai kemungkinan yang tak terhitung jumlahnya? Salah satu jawabannya adalah menggunakan pemrograman integer.

Pemrograman integer adalah sub-bagian dari optimasi diskrit, bidang studi operasi yang terkait dengan meminimalkan beberapa fungsi tujuan yang tunduk pada kendala. Kami ingin meminimalkan total biaya, asalkan barang dikirim tepat waktu ke tempat yang tepat, ditumpuk dalam ULD (Unit Load Device - alat pengemasan barang). Kami mengupayakan solusi optimal, tetapi dalam praktiknya terkadang kami tidak dapat mencapainya. Dalam hal ini, kami puas dengan solusi yang baik atau dekat. Di sini kita membatasi diri pada model sederhana di mana solusi optimal dapat dicapai.

Langkah pertama dalam memecahkan masalah ini adalah beralih ke literatur. Komunitas ilmiah telah berurusan dengan pengiriman barang selama bertahun-tahun. Kami menemukan beberapa karya yang sangat mengingatkan pada masalah kami. Kami mengambil banyak konsep dan notasi berikut dari karya-karya ini dan berterima kasih kepada penulis atas kontribusinya pada bidang ini.

Kita mulai dengan mendefinisikan fungsi tujuan. Untuk meminimalkan biaya, kita perlu memahami konsep bobot standar. Singkatnya, berat standar adalah berat minimum yang disetujui oleh forwarder untuk bekerja, terlepas dari berapa berat sebenarnya yang ditawarkan. Kami memiliki berat total, berat standar, dan peluang untuk kelebihan berat dan, sebaliknya, kurang berat. Bobot standar dikalikan dengan underweight, jadi kita bisa mengabaikan underweight dan fokus pada faktor kelebihan beban dikalikan dengan kelebihan beban itu sendiri.

Fungsi tujuannya adalah untuk meminimalkan biaya total, yang didefinisikan sebagai bobot total semua barang yang ditugaskan oleh ULD, dikalikan dengan faktor muatan. Misalnya, jika ULD1 memiliki 100 kilogram kemacetan dan tingkat kemacetan untuk ULD1 adalah $ 4 per kilogram, maka total biaya ULD 1 adalah $ 400. Jadi, kita perlu beberapa notasi untuk kelebihan berat badan dan nilainya.

Biarkan saja$$$y_j^E$  adalah bobot ULD j di atas standar dan$$$c_j^E$  - faktor biaya untuk ULD yang sama. Kita perlu menghitung$$$y_j^Ec_j^E$ untuk semua$$$j$ . Jika$$$j \in {1, 2, 3}$ , maka fungsi tujuan akan menjadi$$$y_1^Ec_1^E+y_2^Ec_2^E+y_3^Ec_3^E$ . Itu runtuh menjadi$$$\sum y_j^Ec_j^E$ . Kami ingin meminimalkan nilai, jadi tujuan akhir kami:

$$

$$\text{min} \sum_{j} y^E_j c^E_j$$

Nilai untuk $$$c_j^E$bukan nilai yang dihitung. Parameter ini diperoleh dari spreadsheet atau database. Tapi$$$y_j^E$ kita definisikan sebagai berat total kelebihan untuk ULD$$$j$ , yang dapat kita hitung sebagai total berat semua persediaan yang ditugaskan oleh ULD (menyatakannya$$$y_j$ ), dikurangi berat standar ULD ini. Bobot standar khusus untuk jenis ULD dan juga merupakan parameter. Biarkan saja$$$U_j^P$  adalah bobot standar untuk ULD$$$j$ dalam kilogram. Kemudian jumlah bobot ekstra untuk ULD$$$j$ didefinisikan sebagai$$$y_j^E=y_j-U_j^P$ .
Berat total ULD, tentu saja, tergantung pada bobot apa yang ditugaskan pada ULD dan beratnya. Oleh karena itu, kami memerlukan ekspresi untuk menghitungnya, termasuk detail yang disebutkan di atas.

Ini hanyalah jumlah dari bobot yang ditetapkan oleh ULD. Bagaimana cara menunjukkan bahwa sejumlah barang telah ditugaskan ke ULD tertentu? Untuk melakukan ini, kita tidak perlu parameter, tetapi variabel solusi. Variabel keputusan adalah sesuatu yang dapat dikontrol oleh pemecah sambil meminimalkan fungsi objektif.

Biarkan parameternya$$$g_i$ mewakili berat kotor beban$$$i$ dalam kilogram.
Contohnya,$$$g_4=500$ berarti muatan 4 berbobot 500 kilogram.

Biarkan saja$$$x_{i, j}$  adalah variabel keputusan yang mengambil nilai 1, jika pengiriman$$$i$ menugaskan ULD$$$j$ dan$$$0$ sebaliknya. Jadi, ketika kita ingin menghitung semua pengiriman yang ditetapkan oleh ULD 3, kita dapat mengulang semua variabel$$$x_{i, j}$ , dimana$$$j=3$ . Jika kami memiliki 4 pengiriman, dan nomor pengiriman 1 dan 3 ditugaskan ke ULD 3, akan terlihat seperti ini:

$$

$$x_{1,3} + x_{2,3} + x_{3,3} + x_{4,3} = 1 + 0 + 1 + 0 = 2$$

Tetapi kita membutuhkan berat total, bukan kuantitas. Untuk mendapatkannya, Anda cukup mengalikan setiap variabel solusi dengan parameter bobot. Karena variabel keputusan mengambil nilai 0, jika tidak diberi bobot, maka bobot ini disetel ulang dan tidak termasuk dalam total. Misalkan bobot untuk kargo satu hingga empat adalah 10, 50, 25, dan 5. Maka total berat dalam ULD 3 adalah:

$$

$$g_1x_{1,3} + g_2x_{2,3} + g_3x_{3,3} + g4x_{4,3} = (10)(1) + (50)(0) + (25)(1) + (5)(0) = 10 + 25 = 35$$

Mari kita tuliskan perhitungan total berat ini secara umum. Tentukan berat total ULD$$$j$ sebagai $$$y_j$. Kemudian$$$y_1=g_1x_{1,1}+g_2x_{2,1}+ … + g_ix_{i, 1}$, dan $$$y_2=g_1x_{1,2}+g_2x_{2,2} +…+ g_ix_{i, 2}$. Kita dapat menciutkan ini menggunakan notasi penjumlahan$$$y_1 = \sum g_ix_{i, 1}$ dan $$$y_2=\sum g_ix_{i, 2}$. Karena kami ingin ini benar untuk semua kemungkinan$$$j$, kami menggunakan tanda "untuk semua": $$$\forall$. Ini memberi kami bentuk akhir dari batas berat total kami:

$$

$$y_j=\sum_{i \in I}g_ix_{i,j} \forall j \in J$$

Berat ekstra

Sekarang kami memiliki berat total, kami dapat menerapkan formula kami untuk beban tambahan:

$$

$$y_j^E = y_j-U_j^P \quad \forall j \in J$$

Misalnya, jika $$$y_1=1500$dan dan $$$U_1^P=1000$kemudian berat ekstra $$$y_1^E = 1500 - 1000 = 500$kilogram. Lipat gandakan dengan faktor biaya untuk mendapatkan hasil dalam dolar. Sepintas ini mungkin tampak cukup, tetapi bagaimana dengan kasus ketika berat total seluruh kargo untuk ULD tidak melebihi berat standar? Dalam hal ini, jika kita menggunakan rumus "sebagaimana adanya", maka kelebihan beban akan menjadi angka negatif. Misalnya, jika berat standar adalah 1650 kilogram dan berat total yang ditetapkan adalah 1.000 kilogram, maka kelebihan muatan = 1000–1650 = -650. Fungsi objektif mengalikan angka ini dengan faktor kelebihan beban dan kami mendapatkan angka negatif. Seolah pembawa membayar kami untuk pengiriman kurang dari biaya berat standar.

Inilah yang benar-benar kita inginkan:$$$\text{max}(y_j^E, 0)$.
Ini sama dengan hanya menetapkan 0 untuk variabel, yang sesederhana membuat batasan$$$y_j^E>=0$.

$$$y_j^E >= y_j - U_j^P \quad \forall j \in J$, $$$y_j^E >= 0 \quad \forall j \in J$

Jadi, kami mengimplementasikan fungsi max () dalam pemrograman matematika: a = max (b, c), yaitu, a> = b && a> = c. Mari kita lihat definisi kita.
Fungsi objektif:$$$\text{min} \sum_{j} y^E_j c^E_j$
$$$c_j^E$: Rasio Kelebihan ULD $$$j$
$$$y_j^E$: Kelebihan ULD $$$j$; $$$y_j^ = y_j - U_j^P$
$$$U_j^P$: Berat standar ULD $$$j$
$$$g_i$: Berat Pengiriman Bruto $$$i$
$$$x_{i, j}$: variabel keputusan; $$$x_{i, j}=1$jika pengiriman $$$i$ditugaskan oleh ULD $$$j$, $$$0$jika tidak.
$$$y_j$: total berat semua pengiriman yang ditunjuk oleh ULD $$$j$; $$$y_j=\sum_{i \in I}g_ix_{i,j} \quad \forall j \in J$

Setiap muatan harus terbang

Pada titik ini, kita bisa menulis ini dengan Python dan mengirimkannya ke pemecah. Jika kami melakukan ini, kami akan menemukan bahwa pemecah menetapkan nol pengiriman untuk penerbangan apa pun, dan kami dapat dengan cepat memahami alasannya: cara terbaik untuk meminimalkan fungsi tujuan adalah dengan tidak mengakumulasi biaya apa pun. Ini mengarah pada pembatasan berikut: setiap batch harus ditugaskan untuk beberapa ULD. Kami akan memperluas ini untuk setiap kargo yang harus ditugaskan ke satu dan hanya satu ULD, meskipun dalam kenyataannya kami dapat membagi kargo menjadi beberapa ULD dan bahkan beberapa penerbangan.

Itu artinya$$$x_{i, j}$hanya bisa 1 untuk nilai tunggal $ j $. Misalnya, jika kami mempertimbangkan pengiriman 13, maka$$$x_{13,1}+x_{13,2}+ x_{13,3}+ … + x_{13, J}=1$. Kami ingin menerapkan pembatasan ini untuk setiap pengiriman.$$$i$ (yang kami tulis sebagai $$$\forall i\in I$), dan kami dapat menutup tambahan menggunakan operator penjumlahan ($$$\sum$), jadi batasan terakhir kami adalah:

$$

$$\sum_{j \in J} x_{i, j}=1\quad\forall i \in I$$

Dengan batasan ini, pemecah akan benar-benar mulai menetapkan pengiriman untuk penerbangan, tetapi dia hanya akan mendistribusikan pengiriman antara semua penerbangan yang tersedia sampai bobot terpenuhi. Pemecah kemudian akan menempatkan setiap pengiriman yang tersisa dalam satu ULD dengan biaya tambahan paling sedikit. Tidak termasuk volume atau berat ULD ini. Jadi, pembatasan tambahan berikut adalah volume dan berat.

Batasan Volume dan Berat

Mari kita putuskan $$$U_j^M$sebagai muatan maksimum dalam kilogram ULD $$$j$dan $$$U_j^$sebagai volume maksimum dalam meter kubik ULD $$$j$. Mari kita putuskan$$$v_i$, dan volume dalam meter kubik kargo $$$i$. Untuk membatasi model pada kapasitas beban maksimum dan volume maksimum, kami memiliki ketentuan:

$$

$$y_j<=U_j^M \quad \forall j \in J$$

$$

$$\sum_{i \in I} x_{i,j} v_ i <= U_j^V \quad \forall j \in J$$

Seorang veteran industri akan segera menyadari bahwa ini tidak benar. Mengapa? Karena pembatasan ini memperlakukan muatan seolah-olah dapat dituangkan, seperti air, ke volume berapa pun. Pada kenyataannya, muatannya kaku atau memiliki batasan lain, seperti susun. 10 meter kubik kargo tidak dapat dikemas dalam volume sewenang-wenang yang sama persis dengan 10 meter kubik. Untuk mengatasi kasus ini, Anda harus menyelesaikan masalah pengemasan dalam wadah. Kami memeriksa apakah volume tertentu akan cocok dengan yang lain, tetapi ini di luar cakupan artikel ini.

Sekarang pemecah menetapkan ULD pengiriman, dengan menghormati berat dan volume maksimum sambil meminimalkan biaya total. Tetapi ada masalah lain: kami tidak mengatakan apa-apa tentang penunjukan barang dan ketaatan tanggal pengiriman. Sebenarnya, ada empat stempel waktu yang perlu Anda pertimbangkan saat menetapkan kiriman:

Waktu kiriman sebenarnya siap untuk dikonsolidasikan dengan pengiriman lain di ULD dan memuat di penerbangan. Ayo gunakan$$$Q_i^-$untuk mewakili waktu pengiriman siap $$$i$.
Waktu dimana barang harus dibongkar di tujuan didekonsolidasi dan tersedia untuk penerimaan, sebagai aturan, dari terminal kargo. Mari kita gunakan $ Q_i ^ + $ untuk mewakili batas waktu pengiriman$$$i$.
Waktu dimana semua kargo harus dikirim ke terminal kargo untuk memuat ke penerbangan. Ayo gunakan$$$T_j^ -$untuk merepresentasikan waktu kliping kargo ULD $ j $.
Waktu kedatangan penerbangan: ini adalah waktu di mana kargo pada penerbangan tersedia di gudang tujuan. Ayo gunakan$$$T_j^+$ untuk mewakili waktu kedatangan penerbangan ULD $$$j$

Sumber dan Tujuan

Perkenalkan satu set lagi $$$J_i$, yang kami definisikan sebagai seperangkat penerbangan, yang sumber dan tujuannya bertepatan dengan keberangkatan dan penerimaan barang $$$i$. Dengan kata lain, jika keberangkatan 85 berasal dari Hong Kong dan tujuan di London, maka $ J_ {85} $ adalah himpunan semua ULD dengan keberangkatan dari Hong Kong dan tujuan di London.
Sekarang bisa kita gunakan$$$j \in J_i$ untuk mendapatkan kit ULD yang cocok dengan rute perdagangan pengiriman $$$i$atau bisa kita gunakan $$$j \notin J_i$untuk mendapatkan satu set ULD yang tidak cocok. Untuk melarang pengikatan kargo ke ULD, yang tidak sesuai dengan sumber dan tujuannya, kami hanya membatasi$$$x_{i,j} = 0$untuk semua penerbangan tersebut. Pembatasan sepenuhnya dijelaskan sebagai berikut:

$$

$$\sum_{j \notin J_i} x_{i,j}=0 \quad \forall i \in I$$

Waktu pengiriman

Saat bekerja dengan cap waktu dalam pengoptimalan, akan lebih mudah untuk menyajikan momen yang diperlukan sebagai waktu Unix. Keuntungan dari pendekatan:

1. Menyimpan tanggal sebagai angka.
2. Tidak perlu menangani zona waktu.
3. Pemecah menggunakan perbandingan langsung lebih-kurang.

Penerbangan harus tiba sebelum waktu pengiriman:
$$$\sum_{j \in J_i}T_j^+x_{i,j}<=Q_i^+ \quad \forall i \in I \quad$
Harap dicatat bahwa, seperti halnya pembatasan di atas pada keberangkatan dan tujuan, kami telah mengindikasikan bahwa pembatasan ini hanya berlaku untuk ULD di set $$$J_i$dimana $$$J_i$ adalah serangkaian ULD yang cocok dengan pengiriman dan penerimaan pengiriman $$$i$. Itu saja! Mari kita lihat keseluruhan model.

Model lengkap

Di bawah batasan seperti itu, pemecah menetapkan barang-barang ULD dengan cara yang paling murah, dengan setiap kargo dikirim dari tempat keberangkatan yang tepat ke tujuan yang benar. Tentu saja, barang dikirim tepat waktu dan tanpa membebani barang dengan volume atau berat.

Parameter

$$$I$: Satu set semua pengiriman. Satu pengiriman dikirimkan$$$i$
$$$J$: Satu set semua ULD. ULD individual adalah huruf kecil$$$j$.
$$$J_i$: Satu set semua ULD yang cocok dengan pengirim dan penerima $$$i$.
$$$g_i$: Pengiriman berat kotor $$$i$dalam kilogram.
$$$v_i$: Volume dalam meter kubik pengiriman $$$i$
$$$c_j^E$: Rasio Kelebihan ULD $$$j$dalam dolar AS per kilogram
$$$U_j^M$: Kapasitas berat maksimum ULD $$$j$dalam kilogram
$$$U_j^V$: Daya Surround Maksimum ULD $$$j$dalam meter kubik
$$$U_j^P$: Berat standar ULD $$$j$dalam kilogram

$$$T_j^-$: Waktu pengiriman yang diizinkan ke terminal ULD $$$j$.
$$$T_j^+$: Waktu Kedatangan ULD $$$j$.
$$$Q_i^-$: Waktu Siap Pengiriman $$$i$. 
$$$Q_i^+$: Periode pengiriman $$$i$.

Variabel keputusan dan fungsi tujuan:
$$$y_j$: Berat total ULD $$$j$
$$$y_j^E$: Kelebihan ULD $$$j$dalam kilogram.
$$$x_{i,j}$: 1 jika mengirim $$$i$ditugaskan oleh ULD $$$j$0 sebaliknya.

Fungsi target

$$

$$\text{Minimize} \sum y_j^Ec_j^E$$

Keterbatasan

$$$y_j$ - total berat pengiriman pada ULD $ j $: $$$y_j=\sum_{i \in I} g_ix_{i,j} \quad \forall j \in J$
Berat ekstra jE adalah maks (0, yj-UjP):
$$$y_j^E >=y_j-U_j^P \quad \forall j \in J$
$$$y_j^E >=0 \quad \forall j \in J$
Setiap pengiriman harus ditetapkan tepat ke 1 ULD: $$$\sum_{j \in J} x_{i,j}=1 \quad \forall i \in I$.
ULD$$$j$ tidak dapat melebihi berat maksimum: $$$y_j<=U_j^M \quad \forall j \in J$
ULD $$$j$tidak dapat melebihi kapasitas maksimum: $$$\sum_{i \in I}x_{i,j}v_i <= U_j^V \quad \forall j \in J$

Langkah selanjutnya

Artikel ini menjelaskan pemrograman matematika yang mendasari tujuan dari beban penerbangan. Tetapi menulis matematika saja tidak cukup. Langkah selanjutnya adalah mengimplementasikan program, mungkin dalam AML, seperti Pyomo, atau menggunakan API solvernya sendiri, misalnya, Python Gurobi API. Setelah itu, pengembang akan menulis kode untuk mentransfer parameter semua keberangkatan dan penerbangan yang tersedia. Kemudian instance model dikirim ke solver. Solver menetapkan nilai-nilai variabel keputusan secara optimal. Kemudian pengembang harus melakukan sesuatu dengan nilai-nilai variabel keputusan.