Giải pháp bài toán định tuyến phương tiện (VRP) giúp tối ưu hóa lộ trình và hoạt động logistics. Nó tính toán lộ trình hiệu quả nhất cho đội xe, cân nhắc các ràng buộc như cửa sổ thời gian, sức chứa phương tiện và thứ tự ưu tiên giao nhận. API này phù hợp với doanh nghiệp muốn tối ưu hóa hoạt động, giảm chi phí và cải thiện hiệu suất giao hàng bằng cách tối thiểu hóa thời gian và quãng đường di chuyển, đồng thời duy trì chất lượng dịch vụ.

Ghi chú: - thứ tự tọa độ trong mảng là [kinh độ, vĩ độ] - mọi thời gian tính bằng giây - mọi khoảng cách tính bằng mét - đối tượng time_window có dạng [bắt đầu, kết thúc] - các khóa lỗi thời sẽ bị gạch ngang - giá trị cost trong đầu ra là chi phí tối ưu hóa nội bộ - "nhiệm vụ" có thể là công việc, điểm lấy hàng hoặc giao hàng

Endpoint

https://maps.track-asia.com/api/v1/vrp

Đầu vào

Mô tả bài toán được đọc từ đầu vào chuẩn hoặc file (sử dụng -i) và phải có định dạng json như sau:

Jobs

Đối tượng job có các thuộc tính:

Sẽ báo lỗi nếu hai đối tượng job có cùng id.

Shipments

Đối tượng shipment có các thuộc tính:

shipment_step tương tự đối tượng job (trừ các khóa chung đã có trong shipment):

Sẽ báo lỗi nếu hai đối tượng delivery (hoặc pickup) có cùng id.

Vehicles

Đối tượng vehicle có các thuộc tính:

Đối tượng cost có các thuộc tính:

Việc sử dụng giá trị per-hour không mặc định có nghĩa là xác định chi phí di chuyển dựa trên thời gian di chuyển với hệ số nhân. Do đó, việc cung cấp ma trận chi phí tùy chỉnh cho phương tiện là không nhất quán và sẽ gây lỗi.

Đối tượng break có các thuộc tính:

Sẽ báo lỗi nếu hai đối tượng break có cùng id cho cùng một phương tiện.

Đối tượng vehicle_step có các thuộc tính:

Ghi chú

Vị trí nhiệm vụ

Đối với job, pickup và delivery:

• location_index là bắt buộc nếu có ma trận tùy chỉnh
• location là tùy chọn nhưng có thể thiết lập để lấy tọa độ trong phản hồi

Nếu không có ma trận tùy chỉnh:

• sẽ gửi truy vấn table đến hệ thống định tuyến
• location là bắt buộc
• location_index không có hiệu lực

Vị trí phương tiện

• start và end là tùy chọn cho vehicle, miễn là có ít nhất một trong hai được cung cấp
• nếu thiếu end, lộ trình sẽ dừng tại nhiệm vụ cuối cùng
• nếu thiếu start, lộ trình sẽ bắt đầu từ nhiệm vụ đầu tiên
• để yêu cầu lộ trình khứ hồi, chỉ cần thiết lập start và end cùng tọa độ
• tùy theo việc có ma trận tùy chỉnh hay không, các trường bắt buộc sẽ theo logic tương tự như job

Ràng buộc sức chứa

Sử dụng amount (capacity cho phương tiện, delivery và pickup cho công việc, amount cho shipments) để mô tả bài toán có ràng buộc sức chứa. Các mảng này có thể dùng để mô hình hóa các ràng buộc tùy chỉnh cho nhiều chỉ số cùng lúc, ví dụ: số lượng, trọng lượng, thể tích. Phương tiện chỉ được phép phục vụ tập hợp nhiệm vụ nếu tải trọng tại mỗi bước không vượt quá giá trị tương ứng trong capacity. Khi sử dụng nhiều chỉ số, nên đặt các chỉ số quan trọng nhất ở đầu.

Giả định rằng mọi hàng giao sẽ được tải lên từ đầu, trong khi hàng lấy sẽ được mang về cuối lộ trình.

Kỹ năng

Sử dụng skills để mô tả bài toán nơi không phải mọi nhiệm vụ đều có thể được phục vụ bởi tất cả phương tiện. Kỹ năng công việc là bắt buộc, tức là phương tiện chỉ được phục vụ công việc nếu có đầy đủ các kỹ năng yêu cầu. Nói cách khác: công việc j phù hợp phương tiện v nếu j.skills là tập con của v.skills.

Điều này ngụ ý đặc biệt rằng:

• công việc không có kỹ năng có thể được phục vụ bởi bất kỳ phương tiện nào;
• phương tiện không có kỹ năng chỉ có thể phục vụ công việc không yêu cầu kỹ năng.

Để đơn giản hóa bài toán không yêu cầu kỹ năng, việc không cung cấp skills sẽ mặc định là mảng rỗng.

Ưu tiên công việc

Hữu ích khi không thể phục vụ hết tất cả công việc, để kiểm soát việc ưu tiên giao hàng. Thiết lập giá trị priority cao cho công việc sẽ giúp chúng được ưu tiên trong lộ trình hơn các công việc có độ ưu tiên thấp.

Thời gian chuẩn bị

Thời gian chuẩn bị mô tả thời gian cần thiết để bắt đầu công việc tại một vị trí. Đây là khoảng thời gian không được áp dụng lại cho các công việc tiếp theo tại cùng vị trí. Tổng thời gian "hành động" cho một công việc là setup + service nếu đến vị trí mới hoặc chỉ service nếu thực hiện tại vị trí trước đó.

Cửa sổ thời gian

Người dùng có thể quyết định mô tả cửa sổ thời gian theo hai cách:

• giá trị tương đối, ví dụ: [0, 14400] cho cửa sổ 4 giờ tính từ thời điểm bắt đầu kế hoạch. Trong trường hợp này, mọi thời gian arrival trong phản hồi đều tính tương đối từ thời điểm bắt đầu;
• giá trị tuyệt đối, các timestamp "thực". Trong trường hợp này, mọi thời gian arrival trong phản hồi đều có thể được diễn giải là timestamp.

Việc thiếu cửa sổ thời gian trong đầu vào có nghĩa là không có ràng buộc thời gian. Cụ thể, phương tiện không có time_window có thể phục vụ bất kỳ số lượng công việc nào, và công việc không có time_windows có thể được thực hiện bất kỳ lúc nào miễn là đáp ứng các ràng buộc khác.

steps của phương tiện

Chế độ lập kế hoạch

Mảng steps mô tả chính xác thứ tự lộ trình sẽ được tạo trong phản hồi. Các khóa service_* của đối tượng vehicle_step được dùng như ràng buộc thời gian cứng.

Chế độ giải bài toán

Việc sử dụng steps trong chế độ giải bài toán mặc định là cách để bắt đầu tìm kiếm từ giải pháp do người dùng định nghĩa, nếu hợp lệ. Khác với hành vi mặc định là chạy nhiều luồng tìm kiếm song song, điều này có nghĩa là chỉ theo một lộ trình duy nhất bắt đầu từ giải pháp do người dùng cung cấp. Chất lượng kết quả do đó phụ thuộc nhiều vào điểm khởi đầu do người dùng định nghĩa.

Trong bối cảnh này: - chỉ các bước có type=job, pickup hoặc delivery được dùng để quyết định thứ tự lộ trình - các khóa service_* không được sử dụng

Sẽ báo lỗi nếu lộ trình do người dùng định nghĩa không đáp ứng các ràng buộc.

Ma trận tùy chỉnh

Đối tượng matrices cho phép nhập các ma trận tùy chỉnh cho mỗi hồ sơ phương tiện. Mỗi ma trận là mảng các mảng số nguyên không trống được phân loại theo khóa profile, sau đó là:

• durations cho ma trận thời gian di chuyển tùy chỉnh sẽ được dùng để kiểm tra mọi ràng buộc thời gian;
• distances cho ma trận khoảng cách tùy chỉnh;
• costs cho ma trận chi phí tùy chỉnh sẽ được dùng trong mọi đánh giá chi phí lộ trình.

Nếu chỉ cung cấp durations, chi phí nội bộ sẽ được tính dựa trên thời gian di chuyển và các thuộc tính costs của phương tiện.

Ví dụ mô tả các ma trận khác nhau cho các hồ sơ phương tiện:

"matrices": {
    "car": {
        "durations": [[0, 14], [21, 0]]
    },
    "moto": {
        "durations": [[0, 57], [43, 0]]
    }
}

Nếu cung cấp đầy đủ ma trận cho mọi profile yêu cầu, các thuộc tính location, start và end trở thành tùy chọn. Thay vào đó, các chỉ số hàng/cột được cung cấp qua *_index sẽ được dùng trong quá trình tối ưu hóa.

Đầu ra

Giải pháp được ghi dưới dạng json ra đầu ra chuẩn hoặc file (sử dụng -o), định dạng như sau:

Mã trạng thái

Các giá trị có thể:

Summary

Đối tượng summary có các thuộc tính:

*: chỉ xuất hiện khi dùng cờ -g hoặc cung cấp ma trận khoảng cách trong đầu vào.

Routes

Đối tượng route có các thuộc tính:

: chỉ xuất hiện khi dùng cờ -g. *: chỉ xuất hiện khi dùng cờ -g hoặc cung cấp ma trận khoảng cách trong đầu vào.

Steps

Đối tượng step có các thuộc tính:

*: chỉ xuất hiện khi dùng cờ -g.

Violation

Đối tượng violation có các thuộc tính:

Các nguyên nhân vi phạm có thể: - "delay" nếu thời gian bắt đầu phục vụ vượt quá cửa sổ thời gian - "lead_time" nếu thời gian bắt đầu phục vụ sớm hơn cửa sổ thời gian - "load" nếu tải trọng phương tiện vượt quá sức chứa - "max_tasks" nếu số nhiệm vụ vượt quá max_tasks - "skills" nếu phương tiện không có đầy đủ kỹ năng yêu cầu - "precedence" nếu vi phạm ràng buộc shipment (giao hàng không có điểm lấy hàng tương ứng, lấy hàng không có giao hàng tương ứng) - "missing_break" nếu thiếu giải lao trong lộ trình tùy chỉnh - "max_travel_time" nếu thời gian di chuyển vượt quá max_travel_time - "max_distance" nếu quãng đường di chuyển vượt quá max_distance - "max_load" nếu tải trọng trong thời gian giải lao vượt quá max_load

Ghi chú về vi phạm: báo cáo chỉ thực sự có ý nghĩa khi dùng cờ -c để chọn lộ trình tùy chỉnh qua khóa steps của vehicle. Khi dùng chế độ tối ưu hóa thông thường, vi phạm vẫn được báo cáo để nhất quán, nhưng đảm bảo là "rỗng", tức là các mảng violations sẽ trống.

Mã ví dụ

var jobs = [];

var shipments = [

    {

        amount: [1],

        pickup: {

            id: 1,

            service: 60,

            location: [106.6984834, 10.72843945],

            description: "Đ. Số 65, Phường Tân Phong, Quận 7, Thành phố Hồ Chí Minh, Vietnam",

            time_windows: [[1725843600, 1725850800]],

        },

        delivery: {

            id: 1,

            service: 300,

            location: [106.7185714, 10.72843945],

            description: "Crescent Mall 101 Tôn Dật Tiên, Tân Phú, Quận 7, Thành phố Hồ Chí Minh 7000, Vietnam",

            time_windows: [[1725843600, 1725850800]],

        },

    },

    {

        amount: [1],

        pickup: {

            id: 2,

            service: 60,

            location: [106.7185714, 10.72843945],

            description: "Crescent Mall 101 Tôn Dật Tiên, Tân Phú, Quận 7, Thành phố Hồ Chí Minh 7000, Vietnam",

            time_windows: [[1725843600, 1725850800]],

        },

        delivery: {

            id: 2,

            service: 300,

            location: [106.723533, 10.73042726],

            description: "Capri by Fraser, Ho Chi Minh 2 Đường C - Bắc, Tân Phú, Quận 7, Thành phố Hồ Chí Minh, Vietnam",

            time_windows: [[1725843600, 1725850800]],

        },

    },

];

var vehicles = [

    {

        id: 5,

        start: [106.6984834, 10.72843945],

        end: [106.723533, 10.73042726],

        time_window: [1725879600, 1725880800],

        capacity: [1],

        skills: [1, 14],

        startDescription: "Start",

        endDescription: "End",

    },

];

var options = {

    g: true,

};



fetch("https://maps.track-asia.com/api/v1/vrp?key=public_key", {

    method: "POST",

    headers: { "content-type": "application/json" },

    body: JSON.stringify({

        jobs: jobs,

        shipments: shipments,

        vehicles: vehicles,

        options: options,

    }),

})

    .then((response) => response.json())

    .then((data) => console.log(data))

    .catch((error) => console.error("Error:", error));

Các bước tiếp theo

• Thử API playground