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. |