Tùy chọn định tuyến

Phần này mô tả một số tuỳ chọn cho trình giải mã định tuyến.

Giới hạn tìm kiếm

Giới hạn tìm kiếm sẽ kết thúc trình giải quyết sau khi đạt đến giới hạn đã chỉ định, chẳng hạn như khoảng thời gian tối đa hoặc số giải pháp tìm được. Bạn có thể đặt giới hạn tìm kiếm thông qua các thông số tìm kiếm của trình giải quyết. Hãy xem Giới hạn thời gian để biết ví dụ.

Bảng sau đây mô tả các giới hạn tìm kiếm phổ biến nhất.

Tên Loại Mặc định Mô tả
solution_limit int64 kint64max Giới hạn số lượng giải pháp tạo ra trong quá trình tìm kiếm.
time_limit.seconds int64 kint64max Giới hạn tính bằng giây cho thời gian dành ra : trong tìm kiếm.
lns_time_limit.seconds int64 100 Giới hạn tính bằng giây cho thời gian dành cho : tìm kiếm hoàn thành cho từng vùng lân cận tìm kiếm cục bộ.

Chiến lược giải pháp đầu tiên

Chiến lược giải pháp đầu tiên là phương thức mà trình giải quyết sử dụng để tìm giải pháp ban đầu. Bảng sau đây liệt kê các tuỳ chọn cho first_solution_strategy.

Lựa chọn Mô tả
AUTOMATIC Cho phép trình giải quyết phát hiện sử dụng chiến lược nào theo mô hình đang được giải quyết.
PATH_CHEAPEST_ARC Bắt đầu từ nút "start" của tuyến đường, hãy kết nối nút đó với nút tạo ra đoạn tuyến đường rẻ nhất, sau đó mở rộng tuyến bằng cách lặp lại trên nút cuối cùng đã thêm vào tuyến đường.
PATH_MOST_CONSTRAINED_ARC Tương tự như PATH_CHEAPEST_ARC, nhưng các cung được đánh giá bằng bộ chọn dựa trên so sánh để ưu tiên cung cấp nhiều hạn chế nhất trước. Để chỉ định một bộ chọn cho mô hình định tuyến, hãy sử dụng phương thức ArcIsMoreConstrainedThanArc().
EVALUATOR_STRATEGY Tương tự như PATH_CHEAPEST_ARC, ngoại trừ chi phí arc được đánh giá bằng hàm được truyền đến SetFirstSolutionEvaluator().
SAVINGS Thuật toán tiết kiệm (Clarke & Wright). Tham khảo Clarke, G. & Wright, J.W. "Lên lịch cho phương tiện từ một nhà kho trung tâm đến một số điểm giao hàng", Nghiên cứu hoạt động, Tập 12, 1964, trang 568-581.
SWEEP Thuật toán quét (Wren và Holliday). Tham khảo Anthony Wren & Alan Holliday Lên lịch cho máy tính từ một hoặc nhiều nhà kho đến một số điểm giao hàng Hoạt động nghiên cứu hàng quý (1970-1977), Tập 23, số 3 (tháng 9, 1972), trang 333-344.
CHRISTOFIDES Thuật toán Christofides (thực tế là một biến thể của thuật toán Christofides sử dụng so khớp tối đa thay vì so khớp tối đa, không đảm bảo hệ số 3/2 của một số xấp xỉ trên một nhân viên bán hàng du lịch theo chỉ số). Hoạt động trên các mô hình định tuyến phương tiện chung bằng cách mở rộng tuyến đường cho đến khi không thể chèn nút nào trên đó. Tham khảo Nicos Christofides, Phân tích tình huống tồi tệ nhất về một phương pháp phỏng đoán mới cho vấn đề nhân viên bán hàng du lịch, Báo cáo 388, Trường sau đại học về Quản trị công nghiệp, CMU, 1976.
ALL_UNPERFORMED Đặt tất cả các nút không hoạt động. Chỉ tìm giải pháp nếu các nút không bắt buộc (là phần tử của một quy tắc ràng buộc với một chi phí hình phạt hữu hạn).
BEST_INSERTION Xây dựng lại một giải pháp bằng cách chèn nút rẻ nhất ở vị trí rẻ nhất. Chi phí chèn dựa trên hàm chi phí toàn cầu của mô hình định tuyến. Kể từ tháng 2/2012, chỉ hoạt động trên các mô hình có nút không bắt buộc (với chi phí phạt phạt hữu hạn).
PARALLEL_CHEAPEST_INSERTION Xây dựng lại một giải pháp bằng cách chèn nút rẻ nhất ở vị trí rẻ nhất; chi phí chèn dựa trên hàm chi phí hồ quang. Nhanh hơn BEST_INSERTION.
LOCAL_CHEAPEST_INSERTION Xây dựng lại một giải pháp bằng cách chèn từng nút ở vị trí rẻ nhất; chi phí chèn dựa trên hàm chi phí hồ quang. Khác với PARALLEL_CHEAPEST_INSERTION theo nút được chọn để chèn; đây là các nút được xem xét theo thứ tự tạo. Nhanh hơn PARALLEL_CHEAPEST_INSERTION.
GLOBAL_CHEAPEST_ARC Kết nối hai nút lặp đi lặp lại để tạo ra đoạn đường rẻ nhất.
LOCAL_CHEAPEST_ARC Chọn nút đầu tiên có thành phần kế tiếp không bị ràng buộc và kết nối nút đó với nút tạo ra đoạn đường rẻ nhất.
FIRST_UNBOUND_MIN_VALUE Chọn nút đầu tiên có người kế nhiệm chưa được liên kết và kết nối nó với nút có sẵn đầu tiên. Điều này tương đương với chiến lược CHOOSE_FIRST_UNBOUND kết hợp với ASSIGN_MIN_VALUE (cf.constraint_solver.h).

Trạng thái tìm kiếm

Bạn có thể trả về trạng thái của một lượt tìm kiếm bằng cách sử dụng phương thức status của mô hình định tuyến. Sau đây là mã Python để in trạng thái của tìm kiếm:

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

Thao tác này sẽ in một số nguyên với các ý nghĩa sau:

Giá trị Mô tả
0 ROUTING_NOT_SOLVED: Sự cố chưa được giải quyết.
1 ROUTING_SUCCESS: Vấn đề đã được giải quyết thành công.
2 ROUTING_PARTIAL_SUCCESS_LOCAL_OPTIMUM_NOT_REACHED: Đã giải quyết thành công vấn đề sau khi gọi RoutingModel.Solve(), ngoại trừ việc chưa đạt được thông số tối ưu cục bộ. Việc dành nhiều thời gian hơn sẽ cho phép cải thiện giải pháp.
3 ROUTING_FAIL: Không tìm thấy giải pháp nào cho vấn đề.
4 ROUTING_FAIL_TIMEOUT: Đã đạt đến giới hạn thời gian trước khi tìm giải pháp.
5 ROUTING_INVALID: Mô hình, thông số mô hình hoặc cờ không hợp lệ.
6 ROUTING_INFEASIBLE: Vấn đề đã được chứng minh là không khả thi.

Tùy chọn tìm kiếm địa phương

Bảng sau đây liệt kê các tuỳ chọn cho chiến lược tìm kiếm cục bộ (còn gọi là metaheuristics). Hãy xem bài viết Thay đổi chiến lược tìm kiếm để biết các ví dụ về cách đặt các tuỳ chọn này.

Lựa chọn Mô tả
AUTOMATIC Cho phép trình giải chọn metaheuristic.
GREEDY_DESCENT Chấp nhận cải tiến (giảm chi phí) vùng lân cận tìm kiếm địa phương cho đến khi đạt được mức tối thiểu cục bộ.
GUIDED_LOCAL_SEARCH Sử dụng tính năng tìm kiếm địa phương có hướng dẫn để thoát khỏi tính năng tối thiểu cục bộ. (xem Tìm kiếm địa phương có hướng dẫn) thường là siêu dữ liệu hiệu quả nhất để định tuyến xe.
SIMULATED_ANNEALING Sử dụng chức năng ủ được mô phỏng để thoát khỏi lỗi tối thiểu cục bộ (xem Ủ mô phỏng).
TABU_SEARCH Sử dụng tính năng tìm kiếm thẻ để thoát khỏi tối thiểu địa phương (xem Tìm kiếm tabu).
GENERIC_TABU_SEARCH Sử dụng tính năng tìm kiếm bằng thẻ để xác định giá trị khách quan của giải pháp nhằm tránh được tình trạng tối thiểu cục bộ.

Kiểm soát lan truyền

Tên Loại Mặc định Mô tả
use_full_propagation bool true Sử dụng các quy tắc ràng buộc có phương thức nhân đầy đủ trong mô hình định tuyến (thay vì chỉ truyền light). Bạn chỉ cần sử dụng toàn bộ phương thức khi sử dụng tính năng tìm kiếm theo chiều sâu hoặc cho các mô hình yêu cầu truyền mạnh để hoàn tất giá trị của các biến phụ. Việc thay đổi tùy chọn cài đặt này thành true sẽ làm chậm quá trình tìm kiếm trong hầu hết các trường hợp và làm tăng mức tiêu thụ bộ nhớ trong mọi trường hợp.