Kích thước

Trình giải mã định tuyến sử dụng một đối tượng có tên là phương diện để theo dõi các số lượng tích luỹ dọc theo tuyến đường của xe, chẳng hạn như thời gian di chuyển hoặc nếu xe đang đến lấy hàng và giao hàng, thì tổng trọng lượng của xe. Nếu vấn đề về định tuyến có liên quan đến số lượng như vậy, thì trong các quy tắc ràng buộc hoặc hàm mục tiêu, bạn cần xác định một phương diện để chỉ định các biến đó.

Phần này giải thích cách xác định và sử dụng các phương diện.

Ví dụ về phương diện

Dưới đây là một vài ví dụ về phương diện từ các phần trước.

  • Ví dụ về VRPTW tạo một phương diện để theo dõi thời gian di chuyển tích luỹ của từng xe. Trình giải mã sử dụng phương diện để thực thi quy tắc ràng buộc mà phương tiện chỉ có thể truy cập vào một vị trí trong khoảng thời gian của vị trí đó.

  • Ví dụ CVRP tạo một phương diện cho các nhu cầu (ví dụ: trọng lượng hoặc khối lượng gói hàng sẽ đến lấy), theo dõi tải trọng tích lũy mà xe đang vận chuyển trên tuyến đường của mình. Trình giải toán sử dụng kích thước để thực thi quy tắc ràng buộc mà tải của xe không được vượt quá dung lượng.

Các ví dụ bên dưới xác định một phương diện cho VRPTW bằng phương thức AddDimension.

Python

routing.AddDimension(
    callback_index,
    slack_max,
    capacity,
    fix_start_cumul_to_zero,
    dimension_name)

C++

routing.AddDimension(
    callback_index,
    slack_max,
    capacity,
    fix_start_cumul_to_zero,
    dimension_name)

Java

routing.addDimension(
    callbackIndex,
    slackMax,
    capacity,
    fixStartCumulToZero,
    dimensionName)

C#

routing.AddDimension(
    callbackIndex,
    slackMax,
    capacity,
    fixStartCumulToZero,
    dimensionName)

Phương thức AddDimension có các dữ liệu đầu vào sau:

  • callback_index: Chỉ mục cho lệnh gọi lại trả về số lượng. Chỉ mục (là tham chiếu nội bộ của trình giải quyết cho lệnh gọi lại) được tạo bằng các phương thức như RegisterTransitCallback hoặc RegisterUnitaryTransitCallback.
  • slack_max: Tối đa cho khoá, một biến dùng để biểu thị thời gian đợi tại các vị trí. Hãy xem các biến chập bên dưới để biết thông tin chi tiết. Nếu vấn đề không liên quan đến thời gian chờ, thì thông thường bạn có thể đặt slack_max thành 0.
  • capacity: Tối đa cho tổng số lượng được tích luỹ dọc theo từng tuyến. Sử dụng capacity để tạo các điều kiện ràng buộc như các quy tắc ràng buộc trong CVRP. Nếu sự cố không có hạn chế như vậy, bạn có thể đặt capacity thành một giá trị đủ lớn để không giới hạn lộ trình nào, ví dụ: tổng của tất cả các mục của ma trận hoặc mảng dùng để xác định lệnh gọi lại.
  • fix_start_cumulative_to_zero: Giá trị Boolean. Nếu là đúng, giá trị tích luỹ của số lượng sẽ bắt đầu bằng 0. Trong hầu hết các trường hợp, bạn phải đặt giá trị này thành True. Tuy nhiên, đối với VRPTW hoặc các vấn đề về giới hạn tài nguyên, một số xe có thể phải bắt đầu sau thời gian 0 do các hạn chế về khoảng thời gian, vì vậy, bạn nên đặt fix_start_cumulative_to_zero thành False cho các vấn đề này.
  • dimension_name: Chuỗi cho tên cho thứ nguyên, chẳng hạn như 'Distance', bạn có thể sử dụng chuỗi này để truy cập vào các biến ở nơi khác trong chương trình.

Chương trình CVRP tạo một loại phương diện hơi khác bằng cách sử dụng phương thức AddDimensionWithVehicleCapacity. Phương thức này sử dụng nhiều loại dung lượng, mỗi mục cho một xe. (Ngược lại, AddDimension nhận một giá trị duy nhất cho capacity, vì vậy tất cả các xe được giả định có cùng dung lượng.)

Hãy xem trang tham khảo RoutingModel để biết các phương thức tạo phương diện khác.

Phần Lưu thời gian giải pháp vào danh sách hoặc mảng sẽ trình bày các hàm lưu dữ liệu tích luỹ trong một phương diện trong danh sách hoặc mảng.

Biến Slack

Dưới đây là ví dụ minh họa các biến chùng cho một vấn đề liên quan đến thời gian đi lại. Giả sử rằng một xe đi từ vị trí i đến vị trí j trong một bước của tuyến đường và:

  • Thời gian di chuyển tích lũy của xe là 100 phút.
  • Thời gian di chuyển tích lũy của xe lúc j là 200 phút.
  • Thời gian đi từ i đến j là 75 phút.

Xe này không thể rời khỏi địa điểm tôi ngay khi đến nơi, nếu không thời gian tích luỹ ở địa điểm j sẽ là 175. Thay vào đó, xe phải đợi 25 phút tại vị trí i trước khi khởi hành; nói cách khác, độ chùng ở vị trí i là 25.

Bạn cần cho phép thời gian chờ trong VRPTW vì xe có thể phải đợi trước khi ghé thăm một địa điểm, do hạn chế về thời gian. Trong sự cố như vậy, hãy đặt slack_max thành khoảng thời gian tối đa bạn muốn cho phép các phương tiện chờ tại một vị trí trước khi chuyển sang vị trí tiếp theo. Nếu thời gian họ chờ đợi không quan trọng, bạn chỉ cần đặt slack_max thành một số rất lớn.

Đối với CVRP, mặt khác, thay đổi trong tải tích lũy từ i thành j luôn bằng với nhu cầu tại i, do đó không có sự chậm chạp. Đối với các vấn đề như thế này, bạn có thể đặt slack_max thành 0.

Tiếp theo, chúng ta sẽ đưa ra định nghĩa chính thức về tính chậm chạp. Trong nội bộ, một phương diện sẽ lưu trữ hai loại biến liên quan đến số lượng tích luỹ dọc theo các tuyến:

  • Biến giao thông: Mức tăng hoặc giảm của số lượng ở mỗi bước của một tuyến. Nếu i -> j là một bước trong tuyến đường, thì biến chuyển tuyến là mục nhập i, j của ma trận chuyển tuyến (đối với lệnh gọi lại phương tiện công cộng), hoặc chỉ là giá trị gọi lại tại vị trí i (nếu lệnh gọi lại chỉ phụ thuộc vào một vị trí).
  • Biến tích lũy: Tổng số lượng tích lũy tại mỗi vị trí. Bạn có thể truy cập vào biến tích luỹ tại vị trí i bằng dimension_name.CumulVar(i). Để biết ví dụ, hãy xem các giới hạn về thời lượng trong ví dụ về VRPTW.

Giả sử một chiếc xe đi từ vị trí i đến vị trí j trong một bước, nhóm sẽ liên quan đến các biến này như sau: 

slack(i) = cumul(j) - cumul(i) - transit(i, j)

Để biết thêm thông tin chi tiết về kích thước, hãy xem RoutingDimension trong phần tài liệu tham khảo.