Traveling Salesman Problem (TSP) v4 — Tối ưu thứ tự điểm¶
Traveling Salesman Problem (TSP) là bài toán kinh điển trong khoa học máy tính và vận trù học. Cho một tập điểm và khoảng cách giữa chúng, TSP đi tìm lộ trình ngắn nhất đi qua mỗi điểm đúng một lần rồi quay về điểm xuất phát. Đưa vào bài toán bản đồ và chỉ đường thì các "thành phố" chính là địa điểm, còn "khoảng cách" là quãng đường hoặc thời gian di chuyển.
TSP Maps API của VIETMAP là bộ công cụ giúp bạn giải bài toán TSP cho một tập địa điểm cho trước. API cung cấp thuật toán tìm lời giải tối ưu hoặc gần tối ưu, kèm dữ liệu để vẽ lộ trình lên bản đồ. Bạn dùng nó để làm các ứng dụng tối ưu lộ trình và dẫn đường, ví dụ tối ưu tuyến giao hàng hay quản lý logistics.
Tích hợp AI Agent 
MỚI
Tải bộ tài liệu đã tối ưu cho AI agent (Matrix + TSP + VRP): Logistics Agent Doc
Traveling Salesman Problem (TSP) đặt một câu hỏi đơn giản nhưng khó trả lời: cho một loạt điểm dừng, một xe nên đi theo thứ tự nào để tổng hành trình ngắn nhất mà vẫn quay về chỗ xuất phát? TSP API của VIETMAP trả lời trên mạng lưới đường bộ thật của Việt Nam, nên thứ tự trả về dựa trên thời gian chạy xe thực tế — có tính đường một chiều, cấp đường và loại phương tiện — chứ không phải khoảng cách đường chim bay.
Số thứ tự khả dĩ tăng theo giai thừa: mới 10 điểm đã có hơn 3 triệu cách sắp, nên thứ tự tuyến đáng để giải chứ đừng đoán.
Chọn TSP hay VRP?¶
| Tình huống của bạn | API |
|---|---|
| Một xe, nhiều điểm — chỉ cần biết thứ tự | TSP v4 (trang này) |
| Nhiều xe — chia ai đi điểm nào rồi mới sắp thứ tự từng tuyến | VRP |
| Chỉ cần thời gian đi thô, tự lập kế hoạch | Distance Matrix |
| Đã biết thứ tự, chỉ cần đường đi | Routing |
Dùng vào việc gì¶
| Bài toán | TSP cho bạn gì |
|---|---|
| Vòng giao hàng của một shipper | Thứ tự điểm giúp giao hết đơn trong ngày với thời gian trên đường ít nhất. |
| Lịch đi bảo trì | Sắp một ngày của kỹ thuật viên sao cho di chuyển giữa các cuộc hẹn ít nhất. |
| Tuyến thu gom | Sắp thứ tự lấy hàng để về kho trước giờ đóng cửa. |
| Đi tuyến bán hàng / trưng bày | Thứ tự ghé các điểm bán nằm gọn trong giờ làm việc. |
| Lịch trình du lịch | Thứ tự điểm tham quan sao cho thời gian di chuyển giữa chúng ít nhất. |
Cách tính tiền¶
Một lượt gọi TSP tính một transaction cho mỗi điểm dừng — lộ trình 20 điểm tốn 20 transaction. Xem Cách tính tiền.
URL¶
https://maps.vietmap.vn/api/tsp/v4?apikey={your-apikey}&point={point}&point={point}&point={point}&points_encoded={points_encoded}&vehicle={vehicle}&roundtrip={roundtrip}&destinations={destinations}&sources={sources}
Method¶
GET
Chuyển từ v3 lên v4 (tóm tắt)¶
- Endpoint đổi từ
/api/tsp/v3sang/api/tsp/v4. - TSP v4 chạy trên cùng bộ máy định tuyến v4 với Route v4, nên kết quả khớp với tuyến v4.
- Tham số request và định dạng phản hồi giữ nguyên, nên chuyển đổi chỉ là đổi URL.
Xem tài liệu bản cũ: TSP v3.
Tham số¶
| Tham số | Kiểu | Bắt buộc | Mặc định | Mô tả |
|---|---|---|---|---|
| apikey | string | có | không | API key VIETMAP cấp cho tài khoản của bạn. Đăng ký tại đây |
| point | array string | có | không | Các điểm cần tính tuyến. Định dạng [latitude,longitude] — vĩ độ trước. Ít nhất phải có điểm đi và điểm đến; có thể thêm điểm trung gian. Số điểm tối đa tùy theo gói bạn đang dùng. Ví dụ: &point=10.762622,106.660172 |
| points_encoded | boolean | không | true | Chọn cách mã hóa tọa độ trả về trong points và snapped_waypoints. true: chuỗi polyline google polyline 5 — payload nhỏ, phía client phải dùng thư viện polyline để giải mã. false: trả về mảng tọa độ thô, đọc được ngay. Mặc định true. Chúng tôi khuyên để true để giảm kích thước JSON phản hồi. |
| vehicle | string | không | car | Enum: car, motorcycle, truck, container. Chọn loại phương tiện để tính tuyến. |
| roundtrip | boolean | không | true | Giá trị: true (mặc định), false. Tuyến trả về là hành trình vòng (quay lại điểm đầu tiên) |
| sources | string | không | any | Giá trị: any (mặc định), first. Tuyến bắt đầu từ điểm bất kỳ hoặc từ điểm đầu tiên |
| destinations | string | không | any | Giá trị: any (mặc định), last. Tuyến kết thúc ở điểm bất kỳ hoặc ở điểm cuối cùng |
Ví dụ¶
Đầu vào
https://maps.vietmap.vn/api/tsp/v4?apikey={your-apikey}&point=10.79628438955497,106.70592293472612&point=10.801891047584164,106.70660958023404&point=10.801595962927763,106.6898296806408&points_encoded=true&vehicle=motorcycle&roundtrip=true
{
"license": "vietmap",
"code": "OK",
"messages": null,
"paths": [
{
"distance": 7720.5,
"weight": 1022.8,
"time": 1022800,
"transfers": 0,
"points_encoded": true,
"bbox": [
106.68973,
10.79352,
106.71098,
10.80307
],
"points": "}s{`Ac_hjSIP[r@KTuAxCOb@QVuAoAi@g@w@u@oCmC_BgBm@}@QUcB{C}@qBMYs@{B]}A_@kBSkCIo@oABFbAHtAPtAPpAbApDXv@Rj@dAzBT^dAdBqA^e@Jo@F{BLCcAAEICq@@p@AHB@DBbAzBMn@Gd@KpA_@LRZh@dAvAv@z@pI`I[t@u@vA|@h@LJDLa@jL?`AF^gBVeF~@GZuAb@sARgDr@uHfBa@PGBd@xAF\\?RGz@WnEk@~HSzCUlDH?bB?TnAJbAH|@?VBz@?j@?JGJGXGf@?n@Db@H~BjCn@?B?JAFI?}BCAcAI_CEc@?o@Fg@FYFK?K?k@C{@?WI}@KcAUoAdAAz@CP?`A?b@?z@CbAI\\E^GHAJ?VClAGbBGPA`ACLAv@CH?~BOj@C~@Al@Ar@C@kADKbDJ~@Bh@LGk@Bo@H[T[TOPGNCNA`AFlA@REVSFIFQBYGkA@{@Ig@[_AA}B@y@Hq@BO@g@EmAAWCg@Ac@BwAX_DHs@H{@DUP_@No@Be@?KEMGd@GJIDE?k@i@Q?WJGG}AqA?a@mAoAeDcDQQUUyEmEPWNc@tAyCJUZs@HQ",
"instructions": [
{
"distance": 192,
"heading": 0,
"sign": 0,
"interval": [
0,
6
],
"text": "Tiếp tục theo Đường Nguyễn Cửu Vân",
"time": 25900,
"street_name": "Đường Nguyễn Cửu Vân",
"last_heading": null
},
/// More instruction objects will response here
{
"distance": 0,
"heading": 0,
"sign": 4,
"interval": [
201,
201
],
"text": "Đích đến",
"time": 0,
"street_name": "Đường Nguyễn Cửu Vân",
"last_heading": null
}
],
"snapped_waypoints": "}s{`Ac_hjS}`@{CVphB"
}
]
}
Mô tả phản hồi¶
| Trường | Kiểu | Mô tả |
|---|---|---|
| license | string | Loại giấy phép của dữ liệu bản đồ. |
| code | string | Mã trạng thái của phản hồi. Chi tiết ở Các mã trạng thái |
| messages | null | Thông báo kèm theo phản hồi, nếu có. |
| paths | array | Mảng chứa thông tin tuyến đường: quãng đường, thời gian và hướng dẫn đi. |
Mỗi phần tử trong mảng paths gồm các trường sau:
| Trường | Kiểu | Mô tả |
|---|---|---|
| distance | float | Tổng quãng đường của tuyến (mét). |
| weight | float | Trọng số của tuyến. |
| time | integer | Tổng thời gian đi hết tuyến (mili giây). |
| transfers | integer | Số lần chuyển tuyến trong hành trình. |
| points_encoded | boolean | Cho biết các điểm có được mã hóa hay không. |
| bbox | array | Khung bao của tuyến. |
| points | string | Chuỗi điểm đã mã hóa dọc theo tuyến. |
| instructions | array | Mảng chứa hướng dẫn đi từng bước trên tuyến. |
| snapped_waypoints | string | Các điểm đã bám vào đường dọc theo tuyến. |
Mỗi phần tử trong mảng instructions gồm các trường sau:
| Trường | Kiểu | Mô tả |
|---|---|---|
| distance | float | Quãng đường của bước hướng dẫn này, tính bằng mét |
| heading | integer | Hướng đi tại bước này, tính bằng độ (0 = Bắc) |
| sign | integer | Mã chỉ hành động cần làm (ví dụ rẽ trái). |
| interval | array | Chỉ số đầu và cuối (trong mảng points) của đoạn tuyến mà hướng dẫn này nói tới. |
| text | string | Nội dung hướng dẫn dạng chữ. |
| time | integer | Thời gian đi hết bước này, tính bằng mili giây |
| street_name | string | Tên đường của bước hướng dẫn. |
| last_heading | null | Hướng đi cuối của bước hướng dẫn. |
Các mã trạng thái¶
OK: Yêu cầu thành công, phản hồi chứa dữ liệu hợp lệ.INVALID_REQUEST: Tham số gửi lên không hợp lệ. Chi tiết lỗi nằm trong trường messages của phản hồi.OVER_DAILY_LIMIT: API key đã vượt hạn mức lượt gọi trong ngày. Các lượt gọi tiếp theo sẽ không được xử lý cho tới khi hạn mức được đặt lại.MAX_POINTS_EXCEED: Số điểm trong URL vượt quá mức tối đa của gói bạn đang dùng. Bạn giảm bớt số điểm rồi gọi lại.ERROR_UNKNOWN: Có lỗi ngoài dự kiến khi xử lý yêu cầu. Bạn xem trường messages để biết thêm, hoặc liên hệ hỗ trợ nếu vẫn không được.ZERO_RESULTS: Không tìm được tuyến đường khả thi giữa các điểm yêu cầu.
Câu hỏi thường gặp¶
TSP API là gì?¶
TSP (Traveling Salesman Problem) API nhận vào danh sách điểm dừng và trả về thứ tự mà một xe nên đi để tổng quãng di chuyển ngắn nhất rồi quay về chỗ xuất phát. VIETMAP tính trên mạng lưới đường thật, nên kết quả dựa trên thời gian chạy xe chứ không phải khoảng cách đường chim bay.
Khi nào dùng TSP thay vì VRP?¶
Dùng TSP khi chỉ một xe chạy hết các điểm và bạn chỉ cần biết thứ tự. Có từ hai xe trở lên thì dùng VRP, vì lúc đó phần khó là chia điểm cho ai trước khi sắp thứ tự.
TSP có tính đường một chiều và loại xe không?¶
Có. Lộ trình được tính trên mạng lưới đường VIETMAP kèm loại phương tiện, nên đường một chiều, cấp đường và các hạn chế theo loại xe đều ảnh hưởng tới thứ tự trả về.
Một lượt gọi TSP tốn bao nhiêu transaction?¶
Mỗi điểm dừng tính một transaction — lộ trình 20 điểm tốn 20 transaction. Xem Cách tính tiền.
