Algoritma Cabang dan Harga

Question

Dapatkah branch and price menjadi pendekatan solusi yang baik untuk masalah routing dengan fungsi objektif min-max? Misalnya, meminimalkan panjang maksimal setiap rute kendaraan di VRP.

Dalam literatur, saya belum pernah melihat bahwa pendekatan solusi ini digunakan untuk menyelesaikan masalah seperti itu. Sejauh yang saya tahu, pendekatan ini digunakan untuk menyelesaikan VRP yang meminimalkan total biaya.

Answer 1

Menjadi pendekatan yang baik atau buruk akan bergantung pada beberapa faktor, misalnya:

• ukuran instance
• waktu yang tersedia untuk menemukan solusi (ini cenderung menjadi masalah penting dalam aplikasi perutean kendaraan)
• daya komputasi
• tingkat kualitas solusi apa yang memenuhi syarat sebagai cukup baik

Lihat karya Yu, Nagarajan dan Shen ini pada minimum makespan VRP dengan batasan kompatibilitas, karena ini adalah masalah serupa yang telah dipelajari sebelum menggunakan branch-and-price sebagai pendekatan untuk menyelesaikan varian VRP makespan. Ini bekerja dengan cukup baik. Perhatikan bahwa dalam kasus mereka, mereka merancang algoritme perkiraan untuk mempercepat waktu eksekusi B&P.

Saya menyarankan percobaan berikut:

Langkah pertama: Mengikuti jawaban @ RobPratt untuk pertanyaan Anda sebelumnya tentang minimisasi makespan di VRP :

Membiarkan $d_i$ menjadi permintaan pelanggan $i\in N$, biarkan $V=\{1,\dots,K\}$ jadilah set kendaraan, dan biarkan $P$ menjadi kumpulan kolom, di mana setiap kolom sesuai dengan subtour yang layak mulai dari depot, dengan variabel busur $x_{i,j}$ dan variabel node $y_i$. Membiarkan$z$jadilah makespan tersebut. Masalah utama selesai$z$ dan $\lambda$adalah sebagai berikut, dengan variabel ganda dalam tanda kurung: \ begin {align} & \ text {minimalkan} & z \\ & \ text {subject to} & z - \ sum_ {p \ in P} \ left (\ sum_ {i, j } c_ {i, j} x_ {i, j} ^ p \ right) \ lambda ^ p_v & \ ge 0 && \ text {untuk$v\in V$} && (\ pi_v \ ge 0) \\ && \ sum_ {v \ in V} \ sum_ {p \ in P} y_i ^ p \ lambda ^ p_v & \ ge 1 && \ text {untuk $i\in N$} && (\ teks {$\alpha_i \ge 0$}) \\ && - \ sum_ {p \ in P} \ lambda ^ p_v & \ ge -1 && \ text {untuk $v\in V$} && (\ teks {$\beta_v \ge 0$}) \\ && \ lambda ^ p_v & \ ge 0 && \ text {untuk $v\in V$ dan $p\in P$} \ end {align}

Masalah pembuatan kolom selesai $x$ dan $y$ untuk setiap $v\in V$ kemudian meminimalkan pengurangan biaya $\lambda^p_v$. Artinya, minimalkan$$\pi_v \sum_{i,j} c_{i,j} x_{i,j} - \sum_{i \in N} \alpha_i y_i + \beta_v$$ tunduk pada $(x,y)$ membentuk subtour yang layak dimulai dari depo, dengan $\sum_i d_i y_i \le L$, dimana $L$ adalah kapasitas setiap kendaraan.

Seperti yang dinyatakan di sana, subproblem dapat diformulasi ulang sebagai jalur terpendek dasar: Pisahkan depot menjadi sumber dan wastafel, dan pindahkan bobot node ke busur: $\pi_v c_{i,j}−\alpha_i$ untuk berat busur $(i,j)$ di subproblem jalur terpendek dasar.

Kedua: Terapkan metode di atas. Saya sarankan mencoba menggunakan VRPy, seperti yang disarankan oleh Kuifje di sini . Dengan begitu, Anda tidak perlu menerapkan semua cabang dan operasi harga dari awal. Langkah-langkah mendetail:

1. Lihat dokumentasi proyek.
2. Lihat kode di GitHub.
3. Buat garpu atau unduh proyek sebagai .zip, sehingga Anda dapat membuat perubahan secara lokal.
4. Ubah kode terkait subproblem , sehingga depo terpecah seperti yang dijelaskan di atas.
5. Jalankan eksperimen, Anda dapat mengikuti contoh contoh dari dokumentasi seperti di sini dan di sini .
6. Beri tahu kami cara kerjanya. Dan ingatlah untuk mengakui VRPy dan pengembangnya dalam pekerjaan Anda (baik itu laporan proyek, tesis, publikasi, dll), serta menghormati persyaratan pada lisensi perpustakaan sehubungan dengan modifikasi.

Answer 2

VRPy (v0.3.0) sekarang mendukung opsi ini: yang harus Anda lakukan hanyalah menyetel minimize_global_spanopsi ke Truesaat membuat instance VehicleRoutingProblemobjek:

prob = VehicleRoutingProblem(G, num_vehicles=2, minimize_global_span=True)
prob.solve()

Tentu saja, grafik Anda $G$ harus didefinisikan dengan baik di tempat pertama.

Formulasi yang diusulkan oleh @RobPratt diterapkan. Jika Anda bermain-main dengan beberapa masalah mainan, Anda akan melihat bahwa formulasinya lemah dibandingkan dengan yang klasik (tanpa makespan). Sangat mudah untuk melihat kendala itu$$ z - \sum_{p\in P} \left(\sum_{i,j} c_{i,j}x_{i,j}^p\right) \lambda^p_v \ge 0 \quad \text{ for $v \ dalam V$} $$ bertanggung jawab untuk ini.

Anda juga dapat mencoba pendekatan alternatif berikut:

1. Selesaikan masalah tanpa opsi min_max

2. Kueri rentang terbesar

3. Selesaikan lagi tanpa min_max, tetapi batasi masalah sedemikian rupa sehingga setiap rute memiliki rentang yang lebih kecil daripada yang terbesar yang dikueri di 2.

4. Jika tidak memungkinkan, hentikan, jika tidak, lanjutkan ke langkah 2.

Semua ini mudah dilakukan dengan ekosistem VRPy. Selamat bersenang-senang.