Halaman ini diterjemahkan oleh Cloud Translation API.

Opsi Perutean

Bagian ini menjelaskan beberapa opsi untuk pemecah masalah {i>routing<i}.

Batas penelusuran

Batas penelusuran menghentikan pemecah setelah mencapai batas yang ditentukan, seperti durasi maksimum, atau jumlah solusi yang ditemukan. Anda dapat menyetel penelusuran pembatasan melalui parameter pencarian pemecah masalah. Lihat Batas waktu sebagai contoh.

Tabel berikut menjelaskan batas penelusuran yang paling umum.

Nama	Jenis	Default	Deskripsi
`solution_limit`	int64	kint64max	Batasi ke jumlah solusi yang dihasilkan selama pencarian.
`time_limit.seconds`	int64	kint64max	Batasi dalam detik untuk waktu yang dihabiskan : dalam pencarian.
`lns_time_limit.seconds`	int64	100	Batasi dalam detik untuk waktu yang dihabiskan di : pencarian penyelesaian untuk setiap tetangga pencarian lokal.

Strategi solusi pertama

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

Opsi	Deskripsi
`AUTOMATIC`	Memungkinkan pemecah masalah mendeteksi strategi mana yang akan digunakan sesuai dengan model yang sedang dipecahkan.
`PATH_CHEAPEST_ARC`	Memulai dari rute "start" tersebut, hubungkan node yang menghasilkan segmen rute termurah, kemudian memperluas rute dengan melakukan iterasi pada {i>node<i} terakhir yang ditambahkan ke rute.
`PATH_MOST_CONSTRAINED_ARC`	Serupa dengan `PATH_CHEAPEST_ARC`, tetapi busur bersifat dievaluasi dengan pemilih berbasis perbandingan yang akan lebih memilih sebagian besar dibatasi terlebih dahulu. Untuk menetapkan pemilih ke model perutean, gunakan `ArcIsMoreConstrainedThanArc()`.
`EVALUATOR_STRATEGY`	Serupa dengan `PATH_CHEAPEST_ARC`, dengan pengecualian biaya Arc dievaluasi menggunakan fungsi yang diteruskan ke `SetFirstSolutionEvaluator()`.
`SAVINGS`	Algoritma penghematan (Clarke &Wright). Referensi Clarke, G. & Wright, J.W. "Penjadwalan Kendaraan dari Depot Pusat ke Jumlah Titik Pengiriman" , Operations Research, Vol. 12, 1964, hlm. 568-581.
`SWEEP`	Algoritma sapu (Wren &Holliday). Referensi Anthony Wren & Alan Holliday: Penjadwalan Komputer, Kendaraan dari Satu atau Beberapa Depot ke Beberapa Titik Pengiriman Operasional Research Quarterly (1970-1977), Vol. 23, No. 3 (September, 1972), hal. 333-344.
`CHRISTOFIDES`	Algoritma Christofides (sebenarnya merupakan varian dari Algoritma Christofides menggunakan pencocokan maksimal, bukan pencocokan maksimum pencocokan, yang tidak menjamin faktor 3/2 dari perkiraan pada metrik untuk staf penjualan yang bepergian). Berfungsi pada model pemilihan rute kendaraan generik dengan memperluas rute sampai tidak ada {i>node<i} yang dapat disisipkan padanya. Referensi Nicos Christofides, Analisis kasus terburuk dari heuristik baru untuk masalah penjual yang bepergian, Laporan 388, Graduate School of Industrial Administration, CMU, 1976.
`ALL_UNPERFORMED`	Menonaktifkan semua node. Hanya menemukan solusi jika {i>node<i} bersifat opsional (merupakan elemen batasan disjungsi dengan biaya penalti terbatas).
`BEST_INSERTION`	Bangun solusi secara iteratif dengan memasukkan {i>node<i} di posisi termurahnya; biaya pemasangan iklan didasarkan pada dari model perutean. Mulai 2/2012, hanya berfungsi pada model dengan node opsional (dengan biaya penalti terbatas).
`PARALLEL_CHEAPEST_INSERTION`	Bangun solusi secara iteratif dengan memasukkan {i>node<i} termurah di posisi termurahnya; biaya penyisipan didasarkan pada fungsi biaya busur. Lebih cepat dari `BEST_INSERTION`.
`LOCAL_CHEAPEST_INSERTION`	Bangun solusi secara iteratif dengan memasukkan masing-masing {i>node<i} di posisi termurahnya; biaya penyisipan didasarkan pada busur fungsi biaya. Berbeda dari `PARALLEL_CHEAPEST_INSERTION` menurut node dipilih untuk disisipkan; di sini {i>node<i} dipertimbangkan sesuai dengan urutan pembuatan konten. Lebih cepat dari `PARALLEL_CHEAPEST_INSERTION`.
`GLOBAL_CHEAPEST_ARC`	Secara iteratif menghubungkan dua {i>node<i} yang menghasilkan segmen rute termurah.
`LOCAL_CHEAPEST_ARC`	Pilih {i>node<i} pertama dengan penerus yang tidak terikat dan menghubungkannya ke {i>node<i} yang menghasilkan segmen rute termurah.
`FIRST_UNBOUND_MIN_VALUE`	Pilih node pertama dengan penerus yang tidak terikat dan menghubungkannya ke {i>node<i} pertama yang tersedia. Fungsi ini setara dengan Strategi `CHOOSE_FIRST_UNBOUND` dikombinasikan dengan `ASSIGN_MIN_VALUE` (cf. constraint_resolver.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 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 terselesaikan berhasil setelah memanggil `RoutingModel.Solve()`, kecuali bahwa optimal belum tercapai Memberikan lebih banyak waktu akan memungkinkan peningkatan solusi.
`3`	`ROUTING_FAIL`: Tidak ditemukan solusi untuk masalah ini.
`4`	`ROUTING_FAIL_TIMEOUT`: Batas waktu yang tercapai sebelum menemukan solusi.
`5`	`ROUTING_INVALID`: Model, parameter model, atau flag tidak valid.
`6`	`ROUTING_INFEASIBLE`: Masalah terbukti tidak layak.

Opsi penelusuran lokal

Tabel berikut mencantumkan opsi untuk strategi penelusuran lokal (juga disebut metaheuristik). Lihat Mengubah strategi penelusuran untuk contoh tentang cara menetapkan opsi ini.

Opsi	Deskripsi
`AUTOMATIC`	Memungkinkan pemecah masalah memilih metaheuristik.
`GREEDY_DESCENT`	Menerima peningkatan (mengurangi biaya) tetangga penelusuran lokal hingga minimum tercapai.
`GUIDED_LOCAL_SEARCH`	Menggunakan penelusuran lokal terpandu untuk menghindari minimum lokal. (lih. Penelusuran Lokal yang Dipandu) ini umumnya merupakan metaheuristik yang paling efisien untuk {i>routing<i} kendaraan.
`SIMULATED_ANNEALING`	Menggunakan simulasi annealing untuk melarikan minimuma lokal (cf. Simulasi Annealing).
`TABU_SEARCH`	Menggunakan pencarian tabu untuk meng-escape minimum lokal (cf. Penelusuran Tambo).
`GENERIC_TABU_SEARCH`	Menggunakan penelusuran tabu pada nilai tujuan solusi untuk menghindari konversi lokal minimum.

Kontrol propagasi

Nama	Jenis	Default	Deskripsi
`use_full_propagation`	bool	true	Menggunakan batasan dengan penerapan penuh dalam model perutean (bukan hanya propagasi cahaya). Penuh propagasi hanya diperlukan saat menggunakan penelusuran depth-first atau untuk model yang membutuhkan propagasi kuat untuk memfinalisasi nilai sekunder variabel. Mengubah setelan ini ke true akan memperlambat pencarian dalam kebanyakan kasus dan meningkatkan konsumsi memori di semua kasus.