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

Phần này mô tả một số lựa chọn cho trình giải quyết định tuyến.

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

Giới hạn tìm kiếm sẽ chấm dứt trình giải sau khi đạt đến một giới hạn nhất định, chẳng hạn như thời gian tối đa hoặc số lượng giải pháp tìm được. Bạn có thể đặt một chế độ tìm kiếm thông qua các thông số tìm kiếm của trình giải. Xem Giới hạn thời gian để biết ví dụ.

Bảng sau đây mô tả các giới hạn phổ biến nhất về số lượt tìm kiếm.

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

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 pháp mà trình giải sử dụng để tìm ra cách giải quyết ban đầu Cloud. Bảng sau đây liệt kê các tuỳ chọn cho first_solution_strategy.

Phương thức Mô tả
AUTOMATIC Giúp trình giải quyết định nê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ừ một tuyến đường "điểm bắt đầu" hãy kết nối nút đó với nút tạo ra đoạn tuyến rẻ nhất, sau đó mở rộng tuyến đường bằng lặp lại trên nút cuối cùng được thêm vào tuyến.
PATH_MOST_CONSTRAINED_ARC Tương tự như PATH_CHEAPEST_ARC, nhưng các vòng cung thì được đánh giá bằng bộ chọn dựa trên so sánh sẽ ưu tiên vòng cung cố định trước. Để gán 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í vòng cung được đánh giá bằng cách sử dụng hàm được chuyể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 vận chuyển từ một 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). Tài liệu tham khảo Anthony khám phá & Alan Holliday lên lịch trình cho xe từ một hoặc nhiều kho hàng đến một số điểm giao hà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 ra là một biến thể của Thuật toán Christofides sử dụng kiểu khớp tối đa thay vì kiểu khớp tối đa kết quả phù hợp, không đảm bảo hệ số 3/2 của kết quả gần đúng trên chỉ số di chuyển). Hoạt động trên các mô hình định tuyến xe chung của kéo dài một tuyến cho đến khi không thể chèn nút nào trên đó. Tham khảo Nicos Christofides, Phân tích trường hợp xấu nhất về một suy nghiệm mới cho vấn đề nhân viên bán hàng lưu động, Báo cáo 388, Trường đào tạo sau đại học về Công nghiệp Quản trị, CMU, 1976.
ALL_UNPERFORMED Đặt tất cả các nút ở trạng thái không hoạt động. Chỉ tìm thấy lời giải nếu các nút là không bắt buộc (là một yếu tố của giới hạn phân tách với chi phí phạt hữu hạn).
BEST_INSERTION Liên tục xây dựng một giải pháp bằng cách chèn giá trị rẻ nhất nút ở vị trí rẻ nhất; chi phí chèn quảng cáo được tính dựa trên hàm chi phí của mô hình định tuyến. Tính đến tháng 2/2012, chỉ các tính năng các nút không bắt buộc (với chi phí phạt hữu hạn).
PARALLEL_CHEAPEST_INSERTION Liên tục tạo giải pháp bằng cách chèn nút rẻ nhất ở vị trí rẻ nhất; chi phí chèn quảng cáo được tính dựa trên hàm chi phí Arc. Nhanh hơn BEST_INSERTION.
LOCAL_CHEAPEST_INSERTION Liên tục xây dựng một giải pháp bằng cách chèn mỗi nút ở vị trí rẻ nhất; chi phí chèn được tính dựa trên vòng cung hàm chi phí. Khác với PARALLEL_CHEAPEST_INSERTION theo nút được chọn để chèn; Các nút ở đây được xem xét theo thứ tự sáng tạo. Nhanh hơn PARALLEL_CHEAPEST_INSERTION.
GLOBAL_CHEAPEST_ARC Kết nối hai nút lặp lại để tạo ra đoạn đường rẻ nhất.
LOCAL_CHEAPEST_ARC Chọn nút đầu tiên có một nút kế thừa không liên kết 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ó một nút kế tiếp không 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 (xem Constraintt_solver.h).

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

Bạn có thể trả về trạng thái tìm kiếm bằng cách sử dụng phương thức status của mô hình định tuyến. Dưới đâ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 in một số nguyên có các ý nghĩa sau:

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

Tùy chọn tìm kiếm tại đị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 được gọi là metaheuristics). Xem phần Thay đổi chiến lược tìm kiếm để có ví dụ về cách đặt các tuỳ chọn này.

Phương thức Mô tả
AUTOMATIC Hãy để trình giải chọn phương pháp phỏng đoán meta.
GREEDY_DESCENT Chấp nhận việc cải thiện (giảm chi phí) hàng xóm tìm kiếm tại địa phương cho đến khi một người dùng đã đạt đến giá trị tối thiểu.
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ối thiểu cục bộ. (xem Tìm kiếm địa phương có hướng dẫn) thường là phương pháp siêu suy nghiệm hiệu quả nhất để định tuyến xe.
SIMULATED_ANNEALING Sử dụng quy trình ủ mô phỏng để thoát khỏ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 tabu để thoát khỏi tiêu chuẩn cục bộ (xem Tìm kiếm Thẻ).
GENERIC_TABU_SEARCH Sử dụng tính năng tìm kiếm tabu trên giá trị mục tiêu của giải pháp để thoát khỏi cục bộ nhỏ nhất.

Kiểm soát việc truyền

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