Quy hoạch tuyến đường là quá trình tìm kiếm lộ trình tối ưu từ điểm xuất phát đến điểm đích dựa trên mô hình môi trường và các ràng buộc cụ thể (như quãng đường ngắn nhất, thời gian di chuyển nhanh nhất, chi phí thấp nhất...). Trong trường hợp mở rộng, bài toán quy hoạch nhiều điểm nhằm xác định lộ trình tối ưu đi qua nhiều địa điểm được chỉ định. Ứng dụng này đặc biệt hữu ích trong lĩnh vực chia sẻ xe, giao hàng và lập kế hoạch giao thông công cộng.
Xe buýt theo yêu cầu - mô hình chia sẻ di chuyển hiện đại - đang dần trở thành thành phần thiết yếu trong hệ thống giao thông đô thị. Nhờ khả năng kết nối chính xác giữa nhu cầu hành khách và tuyến đường, loại hình này không chỉ giảm ùn tắc mà còn nâng cao trải nghiệm di chuyển. Trong bối cảnh tối ưu hóa chi phí và hiệu suất vận hành, xe buýt cá nhân hóa đóng vai trò then chốt trong việc phân bổ lại nguồn lực giao thông công cộng. Bài toán cốt lõi ở đây chính là giải quyết quy hoạch tuyến đường đa điểm.
API định tuyến của nền tảng bản đồ Amap cung cấp khả năng lập kế hoạch đường đi cho nhiều phương thức di chuyển (ô tô, đi bộ, xe đạp, xe buýt...). Bằng cách kết hợp API lái xe của Amap với thuật toán tối ưu hóa đường đi TSP (Traveling Salesman Problem), chúng ta có thể xây dựng giải pháp quy hoạch tuyến đường qua nhiều điểm. Quy trình cơ bản bao gồm: sắp xếp các điểm đến bằng thuật toán, sau đó tổng hợp các đoạn đường đi để tạo thành lộ trình hoàn chỉnh.
Chi tiết triển khai
Để minh họa và kiểm chứng giải pháp, hệ thống được phát triển với ba thành phần chính:
- Thuật toán xử lý và xử lý hậu kỳ (Python)
- Dịch vụ backend sử dụng FastAPI
- Giao diện người dùng xử lý tương tác
1️⃣ Thuật toán xử lý, tệp ialgo.py
# -*- coding:utf-8 -*-
import itertools
from geopy.distance import geodesic
from shapely.geometry import LineString
from pygeoops import centerline
import geopandas as gpd
import requests
import logging
from shapely.geometry import MultiPoint, MultiLineString, MultiPolygon
logging.basicConfig(level=logging.DEBUG)
class ThuatToanTSP:
# Giải bài toán người bán hàng
# Đầu vào: danh sách tọa độ (vĩ độ, kinh độ)
# Đầu ra: dãy điểm đã sắp xếp
def __init__(self, cac_diem):
self.diem_den = cac_diem # Danh sách tọa độ
self.khoang_cach_min = float('inf') # Khởi tạo khoảng cách nhỏ nhất
self.luot_di_tot_nhat = [] # Lộ trình tối ưu
def tinh_khoang_cach(self, diem_a, diem_b):
"""Tính khoảng cách Euclid giữa hai điểm"""
# Chuyển đổi định dạng tọa độ
a = [diem_a['lat'], diem_a['lng']]
b = [diem_b['lat'], diem_b['lng']]
# Kiểm tra định dạng đầu vào
if not (isinstance(a, (tuple, list)) and isinstance(b, (tuple, list))):
raise ValueError("Tọa độ phải ở dạng tuple hoặc list")
# Tính toán khoảng cách
khoang_cach = geodesic(a, b).m
# Ghi nhật ký
logging.debug(f"Tính khoảng cách giữa {a} và {b}")
logging.debug(f"Kết quả: {khoang_cach} mét")
return khoang_cach
def tim_luot_di_ngan_nhat(self):
"""Tìm lộ trình tối ưu cho bài toán TSP"""
# Xét tất cả các hoán vị có thể
for thu_tu in itertools.permutations(self.diem_den):
khoang_cach = self.tinh_chieu_dai_tong(thu_tu)
if khoang_cach < self.khoang_cach_min:
self.khoang_cach_min = khoang_cach
self.luot_di_tot_nhat = thu_tu
return self.luot_di_tot_nhat
def tinh_chieu_dai_tong(self, thu_tu):
"""Tính tổng chiều dài của lộ trình"""
tong_khoang_cach = 0
for i in range(len(thu_tu) - 1):
tong_khoang_cach += self.tinh_khoang_cach(thu_tu[i], thu_tu[i + 1])
return tong_khoang_cach
class TinhDuongTrungTam:
def __init__(self, cac_diem, he_toa_do='epsg:4525'):
# Danh sách tọa độ (kinh độ, vĩ độ)
self.gps = gpd.GeoSeries(LineString(cac_diem), crs=4326).to_crs(he_toa_co)
self.he_toa_do = he_toa_do
def tao_duong_trung_tam(self):
sline = self.gps.geometry.values[0]
sline = sline.buffer(30).buffer(-15)
cline = centerline(sline)
if cline.geom_type != "LineString":
cls = [_.length for _ in cline.geoms]
idx = cls.index(max(cls))
cline = cline.geoms[idx]
gps = gpd.GeoSeries(cline, crs=self.he_toa_do).to_crs(4326)
return [{'lng': lng, 'lat': lat} for lng, lat in self.lay_toa_do(gps.geometry.values[0])]
def lay_toa_do(hinh_hoc):
if isinstance(hinh_hoc, (MultiPoint, MultiLineString, MultiPolygon)):
return [coord for part in hinh_hoc.geoms for coord in part.coords]
else:
return list(hinh_hoc.coords)
<br></br><br></br>class GiaiThucAmap:
def __init__(self, khoa_api):
self.khoa_api = khoa_api
self.duong_dan = "https://restapi.amap.com/v3/direction/driving"
def lay_duong_di(self, diem_khoi_hanh, diem_den):
tham_so = {
'key': self.khoa_api,
'origin': diem_khoi_hanh, # Định dạng "kinh độ,vĩ độ"
'destination': diem_den # Định dạng "kinh độ,vĩ độ"
}
ket_qua = requests.get(self.duong_dan, params=tham_so).json()
if ket_qua.get('status') == '1':
cac_doan = ket_qua.get('route').get('paths')[0].get('steps')
duong_di = []
for doan in cac_doan:
duong_di.append(doan.get('polyline'))
ket_qua = ';'.join(duong_di)
else:
ket_qua = ''
print("Thông tin đường đi:", ket_qua)
return ket_qua
2️⃣ Dịch vụ backend, tệp app.py
# -*- coding:utf-8 -*-
from fastapi import FastAPI, Body
from fastapi.responses import FileResponse
from pydantic import BaseModel
from typing import List
from ialgo import ThuatToanTSP
from ialgo import GiaiThucAmap
from ialgo import TinhDuongTrungTam
ap = FastAPI()
class DiemToaDo(BaseModel):
lat: float
lng: float
class DanhSachDiem(BaseModel):
cac_diem: List[DiemToaDo]
@ap.post("/diem-toa-do/")
async def nhan_diem(diem: DanhSachDiem):
# Xử lý dữ liệu tọa độ từ frontend
cac_diem = [{"lat": _.lat, "lng": _.lng} for _ in diem.cac_diem]
thuat_toan = ThuatToanTSP(cac_diem)
cac_diem = thuat_toan.tim_luot_di_ngan_nhat() # Sắp xếp điểm
cac_doan_duong = [] # Lưu trữ các đoạn đường
for diem_bat_dau, diem_ket_thuc in zip(cac_diem, cac_diem[1:]):
giai_thuc = GiaiThucAmap('****') # Cần thay thế bằng khóa API hợp lệ
diem_xuat_phat = '{},{}'.format(diem_bat_dau['lng'], diem_bat_dau['lat'])
diem_den = '{},{}'.format(diem_ket_thuc['lng'], diem_ket_thuc['lat'])
duong_di = giai_thuc.lay_duong_di(diem_xuat_phat, diem_den)
cac_doan_duong.append(duong_di)
duong_di_gop = ';'.join(cac_doan_duong) # Nối các đoạn đường
cac_toa_do = [eval(_) for _ in duong_di_gop.split(';')]
duong_trung_tam = TinhDuongTrungTam(cac_toa_do) # Xử lý đường trung tâm
ket_qua = duong_trung_tam.tao_duong_trung_tam()
# Định dạng giống DanhSachDiem
cac_toa_do_ket_qua = [(item['lng'], item['lat']) for item in ket_qua]
return cac_toa_do_ket_qua
@ap.get("/")
async def hien_thi_giao_dien():
return FileResponse('templates/duong-di-nhieu-diem.html')
if __name__ == "__main__":
import uvicorn
uvicorn.run(ap, host="0.0.0.0", port=8000)
3️⃣ Giao diện người dùng duong-di-nhieu-diem.html (nằm trong thư mục templates)
<html lang="vi">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Ví dụ bản đồ Amap</title>
<style>
#ban-do {
height: 600px;
}
#tinh-duong {
position: absolute;
top: 10px;
left: 130px;
z-index: 1000;
padding: 10px;
background-color: white;
border: 1px solid #ccc;
border-radius: 5px;
box-shadow: 0 2px 5px rgba(0, 0, 0, 0.3);
}
#xoa-duong {
position: absolute;
top: 10px;
left: 30px;
z-index: 1000;
padding: 10px;
background-color: white;
border: 1px solid #ccc;
border-radius: 5px;
box-shadow: 0 2px 5px rgba(0, 0, 0, 0.3);
}
</style>
</head>
<body>
<div id="ban-do"></div>
<button id="tinh-duong" class="btn">Đường đi Amap</button>
<button id="xoa-duong" class="btn">Xóa đường đi</button>
<script
src="https://webapi.amap.com/maps?v=1.4.15&key=YourAmapKey&plugin=AMap.Driving"></script>
<script> // Thay thế bằng khóa API thực tế
var banDo = new AMap.Map('ban-do', {
center: [113.5, 34.8], // Kinh độ, vĩ độ
zoom: 13 // Cấp độ zoom
});
let cac_diem = [];
let cac_diem_nhan = [];
let duong_bi;
banDo.on('click', function (su_kien) {
var vi_do = su_kien.lnglat.lat;
var kinh_do = su_kien.lnglat.lng;
console.log('Vị trí được click: ', vi_do, kinh_do);
cac_diem.push({ 'lat': vi_do, 'lng': kinh_do });
var diem_nhan = new AMap.Marker({
position: su_kien.lnglat
});
banDo.add(diem_nhan);
cac_diem_nhan.push(diem_nhan);
var thong_tin = new AMap.InfoWindow({
content: `Vị trí: ${vi_do.toFixed(5)}, ${kinh_do.toFixed(5)}`,
position: su_kien.lnglat
});
thong_tin.open(banDo, su_kien.lnglat);
});
document.getElementById("xoa-duong").addEventListener('click', function () {
console.log('Xóa các điểm');
cac_diem = [];
if (duong_bi) {
banDo.remove(duong_bi);
};
if (cac_diem_nhan) {
cac_diem_nhan.forEach(diem => {
banDo.remove(diem);
});
};
});
document.getElementById('tinh-duong').addEventListener('click', async function () {
console.log('Bắt đầu tính toán');
if (cac_diem.length === 0) {
console.log('Không có điểm nào để tính toán');
return;
}
const ket_qua = await gui_diem_den_backend(cac_diem);
console.log('Kết quả đường đi:', ket_qua);
// Vẽ đường đi
duong_bi = new AMap.Polyline({
path: ket_qua, // Danh sách tọa độ
strokeColor: "#FF33FF", // Màu đường
strokeOpacity: 1, // Độ trong suốt
strokeWeight: 3, // Độ dày
strokeStyle: "solid", // Kiểu đường
lineJoin: 'round', // Góc nối
isOutline: false // Viền ngoài
});
// Hiển thị đường đi
banDo.add(duong_bi);
});
async function gui_diem_den_backend(cac_diem) {
const du_lieu = {
cac_diem: cac_diem
};
try {
const phan_hoi = await fetch('http://localhost:8000/diem-toa-do', {
method: 'POST',
headers: {
'Content-Type': 'application/json'
},
body: JSON.stringify(du_lieu)
});
const du_lieu_ket_qua = await phan_hoi.json();
console.log('Dữ liệu nhận được:', du_lieu_ket_qua);
return du_lieu_ket_qua;
} catch (loi) {
console.error('Lỗi:', loi);
}
};
</script>
</body>
</html>
Kết quả đạt được
Tham khảo: https://lbs.amap.com/api/javascript-api/guide/services/navigation