Kích thước

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

Phần này giải thích cách xác định và sử dụng 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 trong các phần trước.

  • Ví dụ về VRPTW tạo một phương diện để theo dõi thời gian đi tích luỹ của mỗi chiếc xe. Trình giải toán sử dụng phương diện này để thực thi giới hạn mà xe chỉ có thể ghé thăm một vị trí trong phạm vi của vị trí đó khoảng thời gian.

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

Các ví dụ bên dưới xác định kích thước cho VRPTW bằng cách sử dụng 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. Chiến lược phát hành đĩa đơn chỉ mục, là tham chiếu nội bộ của trình giải đến lệnh gọi lại, được tạo bằng như RegisterTransitCallback hoặc RegisterUnitaryTransitCallback.
  • slack_max: Giá trị lớn nhất cho độ trễ, một biến dùng để biểu thị thời gian chờ thời gian tại các vị trí. Hãy xem các biến chậm bên dưới để biết chi tiết. Nếu vấn đề không liên quan đến thời gian chờ, bạn thường có thể đặt slack_max thành 0.
  • capacity: Giá trị tối đa cho tổng số lượng được tích luỹ dọc theo mỗi tuyến. Sử dụng capacity để tạo các quy tắc ràng buộc như những quy tắc ràng buộc trong TLCĐ. Nếu vấn đề của bạn không có quy tắc ràng buộc, bạn có thể đặt capacity thành một giá trị đủ lớn để không áp dụng hạn chế nào đối với tuyến đường, ví dụ: tổng của tất cả các mục nhập 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 đúng, giá trị tích luỹ của số lượng bắt đầu từ 0. Trong hầu hết các trường hợp, bạn nên đặt thuộc tính này thành True. Tuy nhiên, đối với VRPTW hoặc sự cố với hạn chế về tài nguyên, một số loại xe có thể phải bắt đầu sau thời gian 0 do giới hạn về khoảng thời gian, vì vậy bạn nên đặt fix_start_cumulative_to_zero thành False đối với những bài toán này.
  • dimension_name: Chuỗi tên phương diện, chẳng hạn như 'Distance', mà bạn có thể sử dụng để 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 ra một loại thứ nguyên hơi khác một chút bằng cách sử dụng AddDimensionWithVehicleCapacity . Phương thức này sử dụng một mảng dung lượng, với một mục nhập cho mỗi chiếc xe. (Ngược lại, AddDimension nhận một giá trị duy nhất cho capacity, vì vậy tất cả xe được giả định là có cùng sức chứa.)

Xem RoutingModel để biết các phương pháp khác tạo thứ nguyên.

Mục Lưu khoảng thời gian giải pháp vào một danh sách hoặc mảng hiển thị các hàm lưu dữ liệu tích luỹ ở một chiều dưới dạng danh sách hoặc mảng.

Biến Slack

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

  • Thời gian tích luỹ của xe lúc i là 100 phút.
  • Thời gian tích luỹ của xe tại thời điểm j là 200 phút.
  • Thời gian đi từ i đến j là 75 phút.

Xe không thể rời khỏi vị trí i ngay khi đến nơi hoặc rời khỏi vị trí tích luỹ thời gian tại vị trí 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, độ trễ tại vị trí i là 25.

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

Mặt khác, đối với CVRP, thay đổi trong tải tích luỹ từ i thành j luôn bằng với nhu cầu tại i, do đó không có độ trễ. Đối với các vấn đề như điều 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ề độ trễ. Trong nội bộ, một phương diện 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 vận chuyển: Tăng hoặc giảm số lượng ở mỗi bước của một tuyến đường. Nếu i -> j là một bước trong tuyến đường, biến phương tiện công cộng sẽ là i, Mục j của ma trận phương tiện (đối với lệnh gọi lại phương tiện công cộng) hoặc đơn giản 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 luỹ: Tổng số lượng biến tích luỹ tại mỗi vị trí. Bạn có thể truy cập biến tích luỹ tại vị trí i bằng cách dimension_name.CumulVar(i). Để biết ví dụ, hãy xem các điều kiện ràng buộc về khoảng thời gian trong ví dụ VRPTW.

Giả sử một chiếc xe đi từ vị trí i đến vị trí j trong một bước, slack 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 về phương diện, hãy xem RoutingDimension trong phần tài liệu tham khảo.