Opsi Perutean

Bagian ini menjelaskan beberapa opsi untuk pemecah masalah pemilihan rute.

Batas penelusuran

Batas penelusuran menghentikan pemecah soal setelah mencapai batas yang ditentukan, seperti durasi maksimum, atau jumlah solusi yang ditemukan. Anda dapat menetapkan batas penelusuran melalui parameter penelusuran pemecah soal. Lihat Batas waktu untuk mengetahui contohnya.

Tabel berikut menjelaskan batas penelusuran yang paling umum.

Nama Type Default Deskripsi
solution_limit int64 Kint64maks Batasi jumlah solusi yang dihasilkan selama penelusuran.
time_limit.seconds int64 Kint64maks Batasi dalam detik untuk waktu yang dihabiskan : dalam penelusuran.
lns_time_limit.seconds int64 100 Batasi dalam detik untuk waktu yang dihabiskan dalam : penelusuran penyelesaian untuk setiap tetangga penelusuran lokal.

Strategi solusi pertama

Strategi solusi pertama adalah metode yang digunakan pemecah soal untuk menemukan solusi awal. Tabel berikut mencantumkan opsi untuk first_solution_strategy.

Opsi Deskripsi
AUTOMATIC Biarkan pemecah soal mendeteksi strategi yang akan digunakan sesuai dengan model yang sedang dipecahkan.
PATH_CHEAPEST_ARC Mulai dari node "start" rute, hubungkan ke node yang menghasilkan segmen rute termurah, lalu perluas rute dengan iterasi pada node terakhir yang ditambahkan ke rute.
PATH_MOST_CONSTRAINED_ARC Serupa dengan PATH_CHEAPEST_ARC, tetapi busur dievaluasi dengan pemilih berbasis perbandingan yang akan lebih memilih busur yang paling terbatas. Untuk menetapkan pemilih ke model pemilihan rute, gunakan metode ArcIsMoreConstrainedThanArc().
EVALUATOR_STRATEGY Serupa dengan PATH_CHEAPEST_ARC, kecuali bahwa biaya arc dievaluasi menggunakan fungsi yang diteruskan ke SetFirstSolutionEvaluator().
SAVINGS Algoritme penghematan (Clarke & Wright). Referensi Clarke, G. & Wright, J.W. "Scheduling of Vehicles from Central Depot to a Number of Delivery Points", Operations Research, Vol. 12, 1964, hlm. 568-581.
SWEEP Algoritme Sapu (Wren & Holliday). Referensi Penjadwalan Anthony Wren & Alan Holliday untuk Kendaraan dari Satu atau Beberapa Depot ke Sejumlah Titik Pengiriman Operasional Riset Triwulanan (1970-1977), Vol. 23, No. 3 (Sep., 1972), hlm. 333-344.
CHRISTOFIDES Algoritme Christofides (sebenarnya varian dari algoritme Christofides menggunakan pencocokan maksimal, bukan pencocokan maksimum, yang tidak menjamin faktor 3/2 dari perkiraan pada staf penjualan perjalanan metrik). Berfungsi pada model pemilihan rute kendaraan umum dengan memperluas rute hingga tidak ada node yang dapat disisipkan pada rute tersebut. Referensi Nicos Christofides, Analisis kasus terburuk dari heuristik baru untuk masalah staf penjualan yang sedang bepergian, Laporan 388, Graduate School of Industrial Administration, CMU, 1976.
ALL_UNPERFORMED Nonaktifkan semua node. Hanya temukan solusi jika node bersifat opsional (merupakan elemen batasan disjunksi dengan biaya penalti yang terbatas).
BEST_INSERTION Buat solusi secara berulang dengan memasukkan node termurah di posisi termurahnya; biaya penyisipan didasarkan pada fungsi biaya global model pemilihan rute. Sejak 2/2012, hanya berfungsi pada model dengan node opsional (dengan biaya penalti yang terbatas).
PARALLEL_CHEAPEST_INSERTION Buat solusi secara berulang dengan memasukkan node termurah di posisi termurahnya; biaya penyisipan didasarkan pada fungsi biaya busur. Lebih cepat dari BEST_INSERTION.
LOCAL_CHEAPEST_INSERTION Buat solusi secara berulang dengan memasukkan setiap node ke posisi termurah; biaya penyisipan didasarkan pada fungsi biaya busur. Berbeda dari PARALLEL_CHEAPEST_INSERTION oleh node yang dipilih untuk penyisipan; di sini node dipertimbangkan dalam urutan pembuatannya. Lebih cepat dari PARALLEL_CHEAPEST_INSERTION.
GLOBAL_CHEAPEST_ARC Menghubungkan dua node secara berulang yang menghasilkan segmen rute termurah.
LOCAL_CHEAPEST_ARC Pilih node pertama dengan penerus yang tidak terikat, lalu hubungkan ke node yang menghasilkan segmen rute termurah.
FIRST_UNBOUND_MIN_VALUE Pilih node pertama dengan penerus yang tidak terikat, lalu hubungkan ke node pertama yang tersedia. Ini setara dengan strategi CHOOSE_FIRST_UNBOUND yang dikombinasikan dengan ASSIGN_MIN_VALUE (cf. constraint_solver.h).

Status penelusuran

Anda dapat menampilkan status penelusuran menggunakan metode status model pemilihan rute. Berikut adalah kode Python untuk mencetak status penelusuran:

print("Solver status: ", solver.status())

Tindakan ini akan mencetak bilangan bulat dengan arti berikut:

Nilai Deskripsi
0 ROUTING_NOT_SOLVED: Masalah belum terselesaikan.
1 ROUTING_SUCCESS: Masalah berhasil diselesaikan.
2 ROUTING_PARTIAL_SUCCESS_LOCAL_OPTIMUM_NOT_REACHED: Masalah berhasil diselesaikan setelah memanggil RoutingModel.Solve(), kecuali jika optimum lokal belum tercapai. Dengan meluangkan lebih banyak waktu, Anda dapat meningkatkan solusi.
3 ROUTING_FAIL: Tidak ditemukan solusi untuk masalah tersebut.
4 ROUTING_FAIL_TIMEOUT: Batas waktu tercapai sebelum menemukan solusi.
5 ROUTING_INVALID: Model, parameter model, atau flag tidak valid.
6 ROUTING_INFEASIBLE: Masalah yang terbukti tidak layak.

Opsi penelusuran lokal

Tabel berikut mencantumkan opsi untuk strategi penelusuran lokal (juga disebut metaheuristik). Lihat Mengubah strategi penelusuran untuk mengetahui contoh setelan opsi ini.

Opsi Deskripsi
AUTOMATIC Pemecah soal dapat memilih metaheuristik.
GREEDY_DESCENT Menerima peningkatan (penurunan biaya) tetangga penelusuran lokal hingga jumlah minimum lokal tercapai.
GUIDED_LOCAL_SEARCH Menggunakan penelusuran lokal terpandu untuk menghindari minimum lokal. (lih. Penelusuran Lokal Berpemandu) ini umumnya adalah metaheuristik yang paling efisien untuk perutean kendaraan.
SIMULATED_ANNEALING Menggunakan simulasi annealing untuk meng-escape minima lokal (lih. Simulasi Annealing).
TABU_SEARCH Menggunakan penelusuran tabu untuk meng-escape minima lokal (lih. Tabu Search).
GENERIC_TABU_SEARCH Menggunakan penelusuran tabu tentang nilai tujuan solusi untuk meng-escape minimum lokal.

Kontrol propagasi

Nama Type Default Deskripsi
use_full_propagation bool benar Gunakan batasan dengan propagasi penuh dalam model perutean (bukan hanya persebaran saja). Penerapan penuh hanya diperlukan saat menggunakan penelusuran kedalaman-pertama atau untuk model yang memerlukan propagasi kuat untuk menyelesaikan nilai variabel sekunder. Mengubah setelan ini ke true akan memperlambat penelusuran pada sebagian besar kasus dan meningkatkan konsumsi memori dalam semua kasus.