Vehicle Routing Problem (VRP) — Chia tuyến cho đội xe¶
Vehicle Routing Problem (VRP) chính là bài toán hằng ngày của người điều phối: có n xe và m điểm dừng, phải quyết định xe nào đi điểm nào, theo thứ tự nào — trong khi vẫn tôn trọng tải trọng xe, khung giờ giao và giờ làm việc. VRP API của VIETMAP giải bài toán này trên mạng lưới đường bộ thật của Việt Nam, nên kế hoạch trả về có tính đường một chiều, đường cấm và thời gian chạy thực tế, chứ không phải khoảng cách đường chim bay.
Làm tay thì không xuể: chỉ 3 xe và 30 điểm đã có nhiều cách chia hơn mức một người so sánh nổi, và kế hoạch xếp theo cảm tính thường chạy dư 15–30% số km so với kế hoạch được tối ưu.
TSP, VRP hay Matrix — chọn cái nào?¶
| Câu hỏi của bạn | API |
|---|---|
| "Một xe, nhiều điểm — nên đi theo thứ tự nào?" | TSP |
| "Nhiều xe, nhiều điểm — ai đi điểm nào, thứ tự ra sao?" | VRP (trang này) |
| "Đi giữa từng cặp điểm mất bao lâu?" (bạn tự lập kế hoạch) | Distance Matrix |
| "Đã biết thứ tự điểm rồi — cho tôi đường đi và phí cầu đường." | Routing |
VRP là cả kế hoạch; TSP là phần việc của một xe trong đó; còn Matrix là dữ liệu thời gian đi thô, dành cho ai tự viết bộ giải.
Dùng vào việc gì¶
| Bài toán | VRP quyết định giúp bạn |
|---|---|
| Giao hàng chặng cuối | Chia đơn trong ngày cho các shipper đang ca, sắp thứ tự để mỗi tuyến nằm gọn trong khung giờ. |
| Phân phối sỉ | Xếp hàng đầy tải cho xe tải và chạy tuyến mà không vi phạm giới hạn tải trọng trên đường cấm. |
| Bảo trì / dịch vụ tại chỗ | Giao phiếu công việc cho kỹ thuật viên theo vị trí, theo tay nghề và theo giờ hẹn. |
| Thu tiền & thu gom hàng | Hành trình vòng từ kho, quay về trước giờ đóng cửa. |
| Giao hàng lạnh | Tổng thời gian trên đường ngắn nhất, hàng nằm trên xe ít nhất. |
Cách tính tiền¶
Một lượt gọi VRP tính số xe × số điểm transaction — 3 xe chạy 20 điểm tốn 60 transaction. Xem Cách tính tiền trước khi ước lượng kế hoạch hằng ngày.
URL¶
Tham số apikey trên URL là bắt buộc. Đăng ký tại đây để lấy key.
Method¶
POST
Tham số¶
| Khóa | Kiểu | Bắt buộc | Mặc định | Ví dụ | Mô tả |
|---|---|---|---|---|---|
| jobs | array | có | không | Mảng các Job object. Mỗi job là một điểm cần ghé (ví dụ một lần giao hoặc lấy hàng). | |
| vehicles | array | có | không | Mảng các Vehicle object mô tả đội xe sẵn có để chạy các job. Phải có ít nhất một xe. |
Job Object (nhận hàng | trả hàng)¶
| Khóa | Kiểu | Bắt buộc | Mặc định | Ví dụ | Mô tả |
|---|---|---|---|---|---|
| id | integer | có | không | 1 | Mã định danh của job. Phải là duy nhất trong toàn bộ job của request. |
| location | array, double | có | không | [106.112456,10.684922] | Tọa độ của job, theo thứ tự [longitude, latitude]. |
| service | integer | không | 0 | 1 | Thời gian làm việc tại điểm sau khi xe tới, tính bằng giây. Mặc định 0. |
| delivery | array | không | không | [1,2] | Hàng được xếp lên xe từ điểm xuất phát và giao xuống tại job này. Là mảng số nguyên mô tả nhiều chỉ số cùng lúc (ví dụ [số kiện, khối lượng, thể tích]); số chiều và thứ tự chiều phải khớp với capacity của xe. |
| pickup | array | không | không | [1,2] | Hàng được thu tại job này và mang về điểm kết thúc của xe. Là mảng số nguyên mô tả nhiều chỉ số cùng lúc, cùng thứ tự chiều với capacity. |
| skills | array | không | không | [1] | Mảng số nguyên liệt kê các kỹ năng job này yêu cầu. Chỉ xe có skills chứa đủ các giá trị này mới nhận được job. |
| priority | integer | không | 0 | 1 | Mức ưu tiên đưa job vào lời giải. Số nguyên từ 0 đến 10; giá trị càng cao thì job càng dễ được phục vụ khi không thể gán hết mọi job. |
| time_windows | array | không | không | [[0,1400]] | Mảng các khung [start, end] mà job được phép bắt đầu. Thời gian tính bằng giây — tương đối so với đầu kỳ lập kế hoạch hoặc Unix timestamp tuyệt đối, miễn là cả request dùng thống nhất một kiểu. |
Vehicle Object (thông tin xe)¶
| Khóa | Kiểu | Bắt buộc | Mặc định | Ví dụ | Mô tả |
|---|---|---|---|---|---|
| id | integer | có | không | 1 | Mã định danh của xe. Phải là duy nhất trong toàn bộ xe của request. |
| start | array, double | conditional | không | [106.112456,10.684922] | Tọa độ nơi xe bắt đầu tuyến, theo thứ tự [longitude, latitude]. Không bắt buộc, nhưng phải có ít nhất một trong hai khóa start / end. |
| end | array, double | conditional | không | [106.112456,10.684922] | Tọa độ nơi xe kết thúc tuyến, theo thứ tự [longitude, latitude]. Không bắt buộc, nhưng phải có ít nhất một trong hai khóa start / end. Muốn chạy vòng thì để giống start. |
| capacity | array | không | không | [0,3] | Sức chở tối đa của xe, là mảng số nguyên mô tả nhiều chỉ số cùng lúc (ví dụ [số kiện, khối lượng, thể tích]). Thứ tự chiều phải khớp với delivery / pickup của job. |
| skills | array | không | không | [1] | Mảng số nguyên liệt kê các kỹ năng xe này có. Một job chỉ hợp lệ khi mọi kỹ năng nó yêu cầu đều nằm trong đây. |
| time_windows | array | không | không | [[0,14400]] | Giờ làm việc của xe dạng [start, end] (tính bằng giây). Quy ước thời gian giống time_windows của job (xem Lưu ý). Bỏ trống nghĩa là không giới hạn giờ. |
Lưu ý¶
- Khóa
startvàendcủa xe là tùy chọn, miễn là có ít nhất một trong hai. - Bỏ
endthì tuyến sẽ kết thúc ở điểm cuối cùng được ghé, do quá trình tối ưu tự chọn. - Bỏ
startthì tuyến sẽ bắt đầu từ điểm đầu tiên được ghé, cũng do quá trình tối ưu tự chọn. - Muốn chạy vòng tròn thì khai cả
startvàendcùng một tọa độ. - Dùng các mảng số lượng (
capacitycho xe,deliveryvàpickupcho job) để mô tả bài toán có ràng buộc sức chứa. Các mảng này mô tả được nhiều chỉ số cùng lúc, ví dụ số kiện, khối lượng, thể tích... Một xe chỉ được nhận một tập job nếu tải trọng cộng dồn tại mọi bước trên tuyến đều thấp hơn giá trịcapacitytương ứng của từng chỉ số. Khi dùng nhiều chỉ số, bạn nên đặt chỉ số quan trọng hoặc dễ chạm trần nhất lên đầu mảng. - Hệ thống mặc định toàn bộ hàng giao (
delivery) được xếp lên xe từ điểm xuất phát, còn toàn bộ hàng thu (pickup) được mang về điểm kết thúc. - Dùng
skillskhi không phải xe nào cũng làm được mọi job. Kỹ năng của job là bắt buộc: chỉ xe có đủ toàn bộ kỹ năng job yêu cầu mới nhận được job đó. Nói cách khác, job j hợp lệ với xe v khi mọi kỹ năng của j đều nằm trong danh sách kỹ năng của v. - Nếu không khai khóa
skillsnào thì coi như không có ràng buộc kỹ năng. - Hữu ích khi không thể làm hết mọi job, giúp bạn kiểm soát phần nào việc job nào bị bỏ lại.
- Đặt
prioritycao cho một số job sẽ ưu tiên đưa chúng vào lời giải, thay vì các job có mức ưu tiên thấp hơn.
Bạn tự chọn cách mô tả khung giờ:
- Giá trị tương đối, ví dụ [0, 14400] là khung 4 tiếng tính từ lúc bắt đầu kỳ lập kế hoạch. Khi đó mọi mốc thời gian trả về ở khóa
arrivalđều tính tương đối so với đầu kỳ. - Giá trị tuyệt đối, tức timestamp "thật". Khi đó mọi mốc ở khóa
arrivalđọc như timestamp. Không khai khung giờ nghĩa là không có ràng buộc thời gian. - Cụ thể, xe không có khóa
time_windowthì phục vụ được bao nhiêu job cũng được; job không có khóatime_windowsthì có thể chèn vào bất kỳ tuyến nào, vào bất kỳ lúc nào, miễn là các ràng buộc khác cho phép.
Ví dụ¶
Body
{
"vehicles": [
{
"id": 1,
"start": [
106.5983012,
10.8879148
],
"end": [
106.5983012,
10.8879148
],
"profile": "bike",
"time_window": [
1685953800,
1686418200
],
"skills": [
1,
1000
],
"breaks": [
{
"id": 1000,
"time_windows": [
[
1685966400,
1685970000
]
],
"service": 3600
},
{
"id": 1,
"time_windows": [
[
1685986200,
1685988000
]
],
"service": 54000.0
},
{
"id": 2000,
"time_windows": [
[
1686052800,
1686056400
]
],
"service": 3600
},
{
"id": 2,
"time_windows": [
[
1686072600,
1686074400
]
],
"service": 54000.0
},
{
"id": 6000,
"time_windows": [
[
1686398400,
1686402000
]
],
"service": 3600
}
],
"speed_factor": 0.6
},
/// More objects should be add to here
{
"id": 7,
"start": [
106.7086064,
10.814915
],
"end": [
106.7086064,
10.814915
],
"profile": "bike",
"time_window": [
1685953800,
1686418200
],
"skills": [
1,
7000
],
"breaks": [
{
"id": 1000,
"time_windows": [
[
1685966400,
1685970000
]
],
"service": 3600
},
{
"id": 5,
"time_windows": [
[
1686331800,
1686333600
]
],
"service": 54000.0
},
{
"id": 6000,
"time_windows": [
[
1686398400,
1686402000
]
],
"service": 3600
}
],
"speed_factor": 0.6
}
],
"jobs": [
{
"id": 1001,
"description": "HOME",
"location": [
106.5983012,
10.8879148
],
"service": 0,
"priority": 3,
"time_windows": [
[
1685986200,
1685988000
]
],
"skills": [
1000
]
},
{
"id": 304,
"description": "CO.OP FOOD NGUYỄN VĂN QUÁ",
"location": [
106.6287481,
10.8362058
],
"service": 1800,
"time_windows": [
[
1685948400,
1685980800
],
[
1686034800,
1686067200
],
[
1686121200,
1686153600
],
[
1686207600,
1686240000
],
[
1686294000,
1686326400
],
[
1686380400,
1686412800
]
],
"skills": [
1
]
},
/// More objects should be add to here
{
"id": 337,
"description": "CO.OP FOOD TỈNH LỘ 15-1031",
"location": [
106.513876765966,
11.0885457429547
],
"service": 1800,
"time_windows": [
[
1685948400,
1685980800
],
[
1686034800,
1686067200
],
[
1686121200,
1686153600
],
[
1686207600,
1686240000
],
[
1686294000,
1686326400
],
[
1686380400,
1686412800
]
],
"skills": [
1
]
}
]
}
Mô tả nội dung request¶
Xe (vehicles)¶
| Trường | Kiểu | Mô tả |
|---|---|---|
| id | number | Mã định danh của xe. |
| start | array | Tọa độ nơi xe bắt đầu tuyến, theo thứ tự [longitude, latitude]. |
| end | array | Tọa độ nơi xe kết thúc tuyến, theo thứ tự [longitude, latitude]. Muốn chạy vòng thì để giống start. |
| profile | string | Loại phương tiện, quyết định tốc độ và đường được phép đi (ví dụ bike, car, truck). |
| time_window | array | Giờ làm việc của xe dạng [start, end] (tính bằng giây, ví dụ này dùng Unix timestamp). Xe chỉ chạy trong khung này. |
| skills | array | Mảng số nguyên liệt kê các kỹ năng xe có. Job chỉ hợp lệ khi mọi kỹ năng nó cần đều nằm trong đây. |
| breaks | array | Danh sách các lần nghỉ bắt buộc của xe. Mỗi lần nghỉ là một object gồm id, time_windows (các khung [start, end] cho phép, tính bằng giây) và service (thời lượng nghỉ, tính bằng giây). |
| speed_factor | number | Hệ số nhân vào tốc độ mặc định của profile. < 1 là chạy chậm lại, > 1 là nhanh hơn (ví dụ 0.6 = 60% tốc độ mặc định). |
Công việc (jobs)¶
| Trường | Kiểu | Mô tả |
|---|---|---|
| id | number | Mã định danh của job. |
| description | string | Nhãn tự do cho job, trả về nguyên xi để bạn nhận ra điểm dừng. |
| location | array | Tọa độ của job, theo thứ tự [longitude, latitude]. |
| service | number | Thời gian làm việc tại điểm sau khi xe tới, tính bằng giây. |
| priority | number | Mức ưu tiên đưa job vào lời giải, từ 0 đến 10. Càng cao thì job càng dễ được phục vụ. |
| time_windows | array | Mảng các khung [start, end] (giây) mà job được phép bắt đầu. Một job có thể có nhiều khung rời nhau. |
| skills | array | Mảng số nguyên liệt kê kỹ năng job yêu cầu. Chỉ xe có đủ các kỹ năng này mới làm được job. |
Phản hồi
{
"code": 0,
"summary": {
"cost": 12400,
"unassigned": 0,
"service": 196200,
"duration": 12400,
"waiting_time": 237145,
"priority": 3,
"distance": 109272,
"computing_times": {
"loading": 37,
"solving": 61,
"routing": 11
}
},
"unassigned": [],
"routes": [
{
"vehicle": 1,
"cost": 12400,
"service": 196200,
"duration": 12400,
"waiting_time": 237145,
"priority": 3,
"distance": 109272,
"steps": [
{
"type": "start",
"location": [
106.5983012,
10.8879148
],
"arrival": 1685956255,
"duration": 0,
"distance": 0
},
/// More object will response here
{
"type": "break",
"id": 6000,
"service": 3600,
"waiting_time": 177741,
"arrival": 1686220659,
"duration": 12400,
"distance": 109272
},
{
"type": "end",
"location": [
106.5983012,
10.8879148
],
"arrival": 1686402000,
"duration": 12400,
"distance": 109272
}
],
"geometry": "ipmaA}|riSsAHGpB?\\ExC?l@CnBC`@OrAENK?EBCJ@FcBtBm@x@{B|CY^U`@GPG\\e@nCSp@uAlCWd@{C|F_AjBcAfB{AvCS^w@|A[j@Ub@INo@nAm@jAk@fAq@tAwBfEy@zAyAvCqAfCe@~@[j@c@z@mDxGs@vAOVw@dBw@xAi@fAOXs@rAKPyApCGLwA~CMXcUrNi@\\iHnEyBtAg[vRsCdBo[~RsCfB_CzA}BvAiC`BqBnAgEhCoMdIuAx@kNxIqAx@gAr@cDjBwDbCaF|CoBpA{@n@oAdAsCfCaDrC_FfEy@v@qApAc@f@i@t@g@r@w@~AQf@uGrP}IxUqFxNcBrEmB~EgCrGiCpGsAhDmDbJ{BpGwBtFkFhNgDzImC`H{@bBeCbE_BpCcAbBwDlG{FnJsDjGqH~LwFfJaC`EgDtFaEnHoAvCyBlFk@tAmAvCi@nA]v@eBfEeH~PwBxEgBpDgAzBaBhDqBbEmBzDkCzF_BbEwAbFoAfE{GnUSt@I`@w@fDOLKVoAfEc@lAM?MBQLELgAPaAg@eAk@eE_Cc@WqAu@uDsB_GcDaDeBuEkCwAu@}@i@kDkBkBeAy@e@aDcBcAk@uD{BgA`EgAfEfAgEfAaE_CsAqBgAcGeDQKmGkD}CcBtBuBTUlBkDfBcDbB{C`AcBl@}@NOVQ|BkAfDeBfD_B|C}AlDeBd@~@LIiB_EoEgJMYe@aAUc@{FsLqAcCoCyFwAaD[aAQy@WuAs@eE_@}Bc@iCc@mC]wBy@}E_@cC[oBi@_DMs@AKk@kDu@yEyA}IIk@CYAy@BSXmBXgBuBi@mAY{@QcAGkADyCReCNy@?}@IkAWs@GeD[iB]WSIMa@s@sAsCqAsCWc@KIUO[I_F{@qCiAgCgA{Ae@s@M_Eq@IGY]MSeAkCKSc@c@i@]{@m@kGwEgAs@c@W[MqLcDuA[cASwFi@oASyC]gC_@KEoBaAy@KkAAkILoE?]@wOLk@BQDkGhCyD|AyB|@mAj@_DpAkS~HcAh@_E~AoGjCqDxAgXzKsElB_G~BiMfFcEdBmAf@cCbA[LWHcKdEcBp@YLoHxCgFxBq`@~OwDxAgDvAwThJk@T[LqCjAsFrBiAd@}EtBkN~FcBp@qAj@c@Vo@`@kCnBqCpBuB\\u@NgA{AeE_HcBwBm@m@aFcE_DuCeFwFqA}AiKuPg@k@aCaC{D{DoCiCk@t@cA~@[VULmFfBw@Xo@TgBl@yBt@yMlEsGlB_Ct@uBl@kCh@cCl@eCj@m@LiEz@{Ev@q@JqG`AeDj@oDn@kDl@iAR^\\_@]hASjDm@nDo@dDk@pGaAp@KzEw@hE{@l@MdCk@bCm@jCi@tBm@~Bu@rGmBxMmExBu@fBm@n@Uv@YxDmAr@YTMZWbA_Aj@u@Xo@Va@hAaBlBeClHiJ`BmBtCsDnBiCb@g@d@_@bE{BxHmElBaAzB_AvIaDbAa@jHoCnE{AjJmDpCsAf@[d@a@jA_BpAqBfBgDtBqE|@gCn@cBr@aBv@cB|@kBlBqDfBcD~AsClE}HZg@zBoDNWxDkG|AkCj@gApB{DhAoBt@oAlBuDp@sAhAqB`C{DrB_DpCcEbBwCpAsBz@yAx@sApByCx@yAbCoDjAmB`EiGLS~CeFv@kAd@k@v@q@p@i@LOV_@x@wAFSFUD]Ac@]{DOmB?e@L{ALu@FOLQh@OlAQ`@GXKXOnCyCVSXITCT?d@Jp@\\bBpAXL`@N\\Df@@t@CrADvFP`@B~@HlEXhET`BJtCJf@BbFXv@Hx@JxIrAXDbFv@hANlFJ`IXrBFnBBrAHrAPpCb@dAHp@AnDSxAIzAKlAMl@M`LmEhH{CtCmA~@a@hBu@`EeBn@WbSiInCkAlEgBpAi@bCaA`Bk@|Bs@fCu@jBo@`H{BNGfA[vDgAjDiAlBm@zIoCfKcDpH_CxAc@dHyBdBi@pAa@pAa@xBw@`A]h@ObA[rAa@rAa@`Cy@bAa@~BsBvOwNfBaBvGgG~@_A~AwAlDcDdIkHzKgKdC}Bf@c@hC_Cn@m@RQnAgAd@e@`A_A`EsDvAsAzAwAhAeApCeCLMr@o@`B{AxCsCd@a@rF_FtBcB|E{DrAcArEuDnCwBhDkCt@c@jBy@p@[|@c@|CgBl@]pBgA|CgBrC_BdCuAz@i@@ArL_H~BsA|BsAhDuBLEb@?`AFTD`BXjBd@rA^fEhAl@Rz@^x@\\PJhAr@ZVRLPDZDZ@~@ClDc@fCGdE@rBB^BzE^`BNxIp@dE`@zFr@zCd@tIhApGv@pGz@hXrDpDh@lEh@~Ex@pANX@tEJpBBzLP`ABdBDtEJV@fCDpADhAFhBNhBRRBlALt@HxBTzAN^Dt@@rD@l@?|L@dVAl@ErCc@ZEfAOfBUp@ChAB~ATj@LdEhAtA^|Cx@b@LjDfAfGnBf@N`Bf@hA^NFjCx@t@VrBn@v@VfAZTD\\@|ABvED|A@nA@~@BDyC?]FqBrAInAIhDW~AMxAKrDYtBKz@FxANn@Dx@@VCVEb@Qn@U`DsA`@MdB_@NAl@?jE?rMB^F|Bl@La@b@{@r@mAJUh@{AVq@Jm@Hy@DiAFa@Pm@P_@vByDr@yA\\o@s@Ur@T]n@s@xAwBxDQ^Ql@G`@EhAIx@Kl@Wp@i@zAKTs@lAc@z@M`@dG|Ap@PzA^bHjB|@X\\J~DtAx@V~Ah@x@XJPzAaAFH`A`Bb@hAXvANnANzAJrA@f@EXKJc@Nn@fDT|AJzAHdBBX`@nA@JEP[r@CR@XRv@?TEx@Mz@qESS@IHGJ]zAMRGDWAwAYERDSvAXV@FELS\\{AFKHIRApER`ENV@xBDbBD`CHpDNrDLjFLj@?hAGfDQ`AUvAi@b@I`AMtF_@nBK`CKxAIfG_@v@AT?h@BvB^xAP`@BdBH`@Fj@N^Jv@VfBp@jBt@hA^XHhBf@fDtAl@\\}ApB]d@\\e@|AqBV[~@gA`AqA|BaDx@kAdAyARWlGwIf@u@r@aAj@s@zCsEfAyAVWjBgBdAaArEuEbA_AbAaA`@g@pAaCJOhAgBr@y@~AuBxAkB|AqBl@w@~@kAl@u@LOxAkB^e@tAgBp@_Aq@~@uAfB_@d@yAjBMNm@t@_AjAm@v@}ApByAjBsCnDgBkB_@[WOg@Se@QwAY}@EuCAmBL_A?gACy@Gy@IoBQa@IkAYsBi@OIeL~@c@FyALg@?kFu@yB]}AUs@KsBWsJyAUEWCuHmAmAQToALm@@Y?Q_@oAmAqBo@eAg@y@MSq@eAs@kAGIb@WrBqApCgBxBsAdEaCzJqFFH^t@GX@JdAfBLBLCr@a@fC{AhB}@VQ`Am@hCyALGZODCj@Y`DgBc@u@_@s@e@u@Sa@GIdMaHdE_CvAe@RM~EoC^SfBaArCyAbAe@NDP?REFENMFQBMC[IQMMQGYAy@w@]_@oC_DyAaBnBuA|DgCtDaC|CqBdAo@i@WF[GOYg@KO]aArA_@]mBBQmAwBVOf@_@dAq@TSRKP_@w@eAxBoApFmCJKP[F[`@mEH{@h@iGjADZ@~BJx@D@w@Ds@D]VuA^kBXFl@Jm@KYGk@KaBWs@MaAQq@Mk@IaBYsDo@KC_AMqAOq@Gm@G}C_A_AYkA_@iBk@yAe@iA]]Ue@c@c@_@aFeEk@e@q@m@USm@y@s@aAQSaAsA{@eAU_@]YQKm@_@iAm@}@g@}@g@|@f@|@f@hAl@l@^eIdMiAhBy@hA[b@o@nAYt@i@dBOt@QvAGf@cAlJE`@KZWr@SZe@b@g@XsAj@sDxAi@XkAp@aAv@_A|@_AhAa@l@{@~A_@~@c@Lm@Bs@g@a@P`@QkCeBeCeBK[IcBEyAG}B[_HCu@Y{DGCw@Im@O[Q_Au@uAmAw@q@YWw@s@wAoAyBkB{GyDkAzAjA{AkCqAi@Yo@[{@e@KEaB{@wAo@q@[SK[MqAi@w@Y_Bk@kC{@sAo@WIw@[qAe@cA_@UASGRFNNdA^BMNg@@[CuBKmBKmAm@oEAU@KH[T_@Zg@d@u@dAcBT_@zBeEYI{Aq@]OeAg@m@YCAc@UcCsAiAk@UK_@S}C}A{GgDyDoB{CqAcDsAgBq@}@]{@a@e@Wa@a@g@Oj@eIVmCoDFwFJkDHbACfBEOkEAq@MgDEuACyBAgAA_@Aw@AMM_@OWa@s@m@mAMo@EyAASq@_OMeDEcAEeBA}@SuP?OO{IKg@a@gBEYIeCBa@J{@V{ALa@X_@HMZaB?a@OsAa@uAIc@GcCEk@G]h@Ij@Il@Il@INAp@KNAjAOjBYT?Ra@H[?KC_@@YJyAC]EOGMMe@E_AE}@CmAT}ABU?QI[NMh@e@`@a@hAkApAuAFON[z@cAOMsAiAWUaAw@eDoCk@e@gAo@q@_@[Oi@YN]FG|Aw@zBcAhB}@r@_@BKGWg@qAaA}BWk@aAyBQ]QWOQGKc@cAkAcDOi@Me@q@}BcA{BOY_@yA??Ka@]L\\Mj@zBNXd@l@\\lAp@|BLd@Nh@jAbDb@bAFJNPPVP\\`AxBVj@`A|Bf@pAFVCJs@^iB|@{BbA}Av@GFO\\o@x@kAXaDl@{Bb@KFEH@TXl@FXH|@BfA?|CBxBJlCJfDZ`FB\\HbCBRTx@|@|BDRF\\Dj@FbCHb@`@tANrA?`@Ir@Ql@ILY^M`@WzAKz@C`@@fAF|@DX`@fBJf@Dh@HpH?NRtP@|@DdBDbALdDZlHTpEkH\\e@Hi@LmCz@mAb@sBp@DRHx@ZbCNn@j@fBX`BN`B{@@u@Cy@Mk@Mc@Kb@Jj@Lx@Lt@Bz@Al@AD|CJ~EAz@Kx@Cx@CTQz@Uj@GPKj@Gj@@JFJ?NCd@Kv@E\\rATJDVPb@\\LPTZRLjBf@BHCf@@FFHJBp@DETCv@Kx@?d@N@HBlAr@rAv@bAj@xChBdBdAXPb@ZfAf@IxAGbATF??VJnLhG~HvE|FdDrChBzBfANF{@~Ae@|@a@t@m@z@k@v@]|AWv@Yl@w@|Au@dBe@v@]j@[h@i@~@MRqAtBeBnDUlBIr@Kr@WzACNY~Ai@zCe@tCG~@s@Zq@^i@Z}BhA[PQTSd@cAbCmBaBL]M\\gByAq@k@_C{Ao@a@gCaBuAy@wA}@a@W{@g@_@Uk@]sBqAmCcBo@c@mCkBgC}AoA{@\\gA]fAUMeBoAKKi@i@e@_@e@]sA_AOMk@_@u@g@e@[OKo@e@oDcCm@_@OK}@o@gAu@oKiHm@_@GEcAs@wA_Aa@Ys@e@cH}EcDZmBZUDuAl@wAb@o@XqBjAWNy@b@Ua@Ya@YGu@CoAH{@Ro@J{@Jk@Js@RyCx@yCx@yCb@]Jq@PmAd@MWgBqD]u@\\t@fBpDLVLVvCrGl@rAh@jA^v@lDrHbD`Hn@pAd@dAzAbDrAvC`@v@t@pAl@bAj@|@lAjBFJbErGpApB`BjCrCtEl@~@n@bA`A|Az@tAXb@hAhBzBrDxA|B|BrDh@x@Vn@Hf@r@xDt@hEt@bEX|AV`Ah@vAjAjCzA`D`@`Af@rATfAt@vGBf@E~@GlCBlAFj@ThCT|ENpAL|@Tz@d@rAd@rAXl@JNa@`BGl@EXEnCAdAA`AMdCg@zDAd@Cr@rAI"
}
]
}
Mô tả nội dung phản hồi¶
| Trường | Kiểu | Mô tả |
|---|---|---|
| code | number | Mã trạng thái phản hồi. 0 là giải xong bài toán thành công. |
| summary | object | Số liệu tổng hợp của toàn bộ tuyến trong lời giải. |
| summary.cost | number | Tổng chi phí của lời giải (giá trị mà bộ giải tìm cách giảm nhỏ nhất, chủ yếu dựa trên thời gian di chuyển). |
| summary.unassigned | number | Số job không gán được cho xe nào. |
| summary.service | number | Tổng thời gian làm việc tại tất cả các điểm đã ghé, tính bằng giây. |
| summary.duration | number | Tổng thời gian chạy xe của mọi tuyến, tính bằng giây. |
| summary.waiting_time | number | Tổng thời gian xe phải chờ tới khung giờ cho phép, tính bằng giây. |
| summary.priority | number | Tổng giá trị priority của mọi job đã được gán. |
| summary.distance | number | Tổng quãng đường của mọi tuyến, tính bằng mét. |
| summary.computing_times | object | Thời gian bộ giải bỏ ra ở từng giai đoạn, tính bằng mili giây. |
| summary.computing_times.loading | number | Thời gian nạp và chuẩn bị dữ liệu đầu vào, tính bằng mili giây. |
| summary.computing_times.solving | number | Thời gian tối ưu các tuyến, tính bằng mili giây. |
| summary.computing_times.routing | number | Thời gian dựng hình học của tuyến, tính bằng mili giây. |
| unassigned | array | Danh sách job không phục vụ được, kèm id và location. Rỗng khi mọi job đều được gán. |
| routes | array | Mỗi phần tử là một xe được dùng trong lời giải. |
| routes[].vehicle | number | id của xe chạy tuyến này. |
| routes[].cost | number | Phần chi phí mà tuyến này đóng góp vào summary.cost. |
| routes[].service | number | Tổng thời gian làm việc tại các điểm trên tuyến này, tính bằng giây. |
| routes[].duration | number | Tổng thời gian chạy xe của tuyến này, tính bằng giây. |
| routes[].waiting_time | number | Thời gian xe phải chờ khung giờ trên tuyến này, tính bằng giây. |
| routes[].priority | number | Tổng priority của các job trên tuyến này. |
| routes[].distance | number | Quãng đường của tuyến này, tính bằng mét. |
| routes[].steps | array | Danh sách điểm dừng của xe trên tuyến, theo đúng thứ tự. |
| routes[].steps[].type | string | Loại bước: start, job, pickup, delivery, break hoặc end. |
| routes[].steps[].id | number | id của job hoặc lần nghỉ mà bước này ứng với (có ở bước job, pickup, delivery và break). |
| routes[].steps[].location | array | Tọa độ của bước, theo thứ tự [longitude, latitude] (có ở bước start, end và các bước job). |
| routes[].steps[].service | number | Thời lượng làm việc hoặc nghỉ tại bước này, tính bằng giây. |
| routes[].steps[].waiting_time | number | Thời gian xe chờ tại bước này trước khi được bắt đầu làm, tính bằng giây. |
| routes[].steps[].arrival | number | Thời điểm xe tới bước này, tính bằng giây (tương đối so với đầu kỳ hoặc dạng Unix timestamp, khớp với time_windows ở đầu vào). |
| routes[].steps[].duration | number | Thời gian chạy cộng dồn từ đầu tuyến tới bước này, tính bằng giây. |
| routes[].steps[].distance | number | Quãng đường cộng dồn từ đầu tuyến tới bước này, tính bằng mét. |
| routes[].geometry | string | Hình học đầy đủ của tuyến, mã hóa dạng chuỗi google polyline 5. |
Câu hỏi thường gặp¶
VRP API là gì?¶
VRP (Vehicle Routing Problem) API nhận vào một đội xe và danh sách điểm dừng, rồi trả về kế hoạch: xe nào đi những điểm nào, theo thứ tự ra sao. VIETMAP giải bài toán này trên mạng lưới đường bộ thật của Việt Nam, có tính tải trọng và khung giờ, nên kế hoạch chạy được ngoài đường chứ không phải chỉ đúng trên lý thuyết.
TSP và VRP khác nhau thế nào?¶
TSP sắp thứ tự điểm dừng cho một xe. Còn VRP trước hết quyết định chia điểm cho nhiều xe thế nào, rồi mới sắp thứ tự tuyến của từng xe. Một tài xế thì dùng TSP; cả đội xe thì dùng VRP.
VRP xử lý được những ràng buộc nào?¶
Tải trọng xe và khung giờ giao hàng là hai thứ ảnh hưởng nhiều nhất tới kế hoạch, bên cạnh loại xe — chạy xe tải hay container thì phải tuân theo giới hạn tải trọng và đường cấm, còn tuyến xe máy thì không vướng.
Một lượt gọi VRP tốn bao nhiêu transaction?¶
số xe × số điểm. Ba xe chạy hai mươi điểm là 60 transaction. Xem Cách tính tiền.
