Algoritme Pembuatan Kolom

Question

Saya ingin menyelesaikan VRP dengan algoritma pembuatan kolom. Tujuan dari permasalahan tersebut adalah minimisasi makespan. tetapi ada gunanya menghitung waktu kedatangan kendaraan di setiap node. Kendaraan harus disinkronkan dengan moda transportasi lain seperti kereta api yang rutenya telah ditentukan sebelum menyelesaikan VRP tersebut di atas. Kereta api bisa saja lewat dari beberapa titik yang dilalui kendaraan dan di simpul tersebut, waktu kedatangannya adalah maksimal dari waktu kedatangan kereta dan kendaraan. Saya ingin tahu bagaimana saya harus menyelesaikan subproblem harga?

Answer 1

Jika saya memahami masalah Anda dengan benar, maka satu-satunya perbedaan dengan versi awal (tanpa kereta) adalah bahwa fungsi waktu bukan aditif.

Misalnya, kereta api melewati node $j$ pada waktu (yang diberikan) $t_j$, dan Anda menghitung jalur $p$ yang simpul terakhirnya $i$. Total waktu yang terkumpul di jalur ini dilambangkan dengan$\tau_p(i)$. $\Delta t_{ij}$ menunjukkan waktu yang dibutuhkan kendaraan untuk pergi $i$ untuk $j$. Jika Anda ingin memperluas jalur dan menambahkan node$j$, lalu total waktu yang terakumulasi untuk jalan $p$, $\tau_p$, dinaikkan sebagai berikut: $$ \tau_p(j) := \max\{ t_j, \tau_p(i) + \Delta t_{ij} \} $$

Jika kereta tiba sebelum kendaraan, maka total waktu yang terakumulasi membutuhkan nilai $\tau_p(i) + \Delta t_{ij}$, jika tidak, itu membutuhkan nilai $t_j$.

Perhatikan bahwa ini seperti memiliki jendela waktu di simpul kereta Anda, dengan hanya batas bawah: Anda bisa menambahkan jendela waktu $[t_j, +\infty[$ di node $j$ dan jalankan algoritme jalur terpendek Anda dengan jendela waktu (jika Anda punya).

Dengan kata lain, fungsi ekstensi sumber daya (waktu) bukanlah aditif. Ini ditangani misalnya oleh cspy , pustaka python hebat yang menghitung jalur terpendek dengan batasan sumber daya, di mana Anda dapat memasukkan aturan ekstensi sumber daya yang Anda sesuaikan sendiri (lihat dokumen di mana contoh seperti itu diberikan). VRPy , pustaka python VRP untuk VRP bergantung pada cspy untuk menghitung jalur terpendeknya untuk pembuatan kolom. Sejak VRPy menangani jendela waktu, Anda memiliki titik awal yang baik!