Tổng quan luận án

Tính cấp thiết và khoảng trống nghiên cứu

Ngành giao thông vận tải đóng vai trò cốt lõi trong phát triển kinh tế và kết nối vùng miền. Tuy nhiên, hoạt động vận tải tiêu thụ khoảng 25% tổng năng lượng của nền kinh tế và chi phí vận chuyển chiếm tới 20% giá thành sản phẩm. Sự gia tăng nhanh chóng của các phương tiện giao thông tại các đô thị lớn dẫn đến các vấn đề nghiêm trọng như tắc nghẽn giao thông, ô nhiễm không khí, tiếng ồn và tai nạn giao thông. Tại Việt Nam, theo số liệu thống kê năm 2015 từ Tổng cục Thống kê, số lượng phương tiện đạt xấp xỉ 43 triệu đơn vị, phục vụ hơn 3,3039 tỷ lượt hành khách và 1,2 tỷ tấn hàng hóa. Thực tế này đòi hỏi các hệ thống vận tải phải nâng cao năng lực phục vụ và cắt giảm chi phí di chuyển thông qua việc tối ưu hóa định tuyến phương tiện (Vehicle Routing Problem - VRP).

Các mô hình VRP kinh điển như bài toán định tuyến xe có giới hạn tải trọng (CVRP), bài toán định tuyến cực tiểu hóa lộ trình dài nhất (MMVRP) hay bài toán giao nhận hàng có cửa sổ thời gian (PDVRPTW) thường lược bỏ nhiều yếu tố thực tế. Để áp dụng trong thực tiễn, các ràng buộc mở rộng cần được tích hợp tạo thành bài toán VRP phong phú (Rich VRP - RVRP). Hoạt động định tuyến trong thực tế được chia thành hai kịch bản:

  1. Kịch bản tĩnh (Static routing scenario): Toàn bộ dữ liệu về đơn hàng, khách hàng, phương tiện và thời gian được xác định từ trước khi thực hiện hành trình.
  2. Kịch bản động (Dynamic routing scenario): Các yêu cầu vận chuyển mới xuất hiện trực tuyến trong quá trình thực hiện kế hoạch, đòi hỏi hệ thống phải cập nhật lộ trình theo thời gian thực.

Khoảng trống nghiên cứu được tác giả xác định gồm:

  • Trong kịch bản tĩnh: Chưa có công trình nào nghiên cứu bài toán phân phối hàng hóa kết hợp đồng thời các yếu tố đa kho, đa chuyến, thời gian bốc dỡ hàng phụ thuộc khối lượng, bãi đỗ xe riêng biệt, cùng với ràng buộc biên dưới tải trọng phương tiện (lower-bound capacity constraint). Việc thiếu ràng buộc biên dưới dẫn đến các chuyến xe mang tải trọng quá thấp so với công suất thiết kế, gây lãng phí chi phí và mất cân bằng tài nguyên.
  • Trong kịch bản động: Các mô hình chia sẻ hành trình taxi kết hợp chở người và bưu kiện (Shared-a-Ride Problem - SARP) trước đây chủ yếu chỉ tối ưu hóa khoảng cách cho các sự kiện đã biết trên lịch trình, chưa tận dụng dữ liệu lịch sử để dự báo nhu cầu tương lai nhằm định hướng di chuyển cho các xe taxi đang ở trạng thái rỗng (idle taxis).

Mục tiêu nghiên cứu

Luận án xác định các mục tiêu cụ thể:

  1. Mở rộng và phát biểu hình thức bài toán định tuyến phương tiện tĩnh có ràng buộc biên dưới tải trọng, đa kho, đa chuyến, áp dụng trong phân phối sản phẩm sữa (bài toán MTDLC-VR).
  2. Xây dựng mô hình quy hoạch tuyến tính nguyên hỗn hợp (MILP) và phát triển các thuật toán tìm kiếm cục bộ lân cận lớn thích nghi (A-ALNS) để giải quyết bài toán tĩnh quy mô lớn.
  3. Xây dựng mô hình định tuyến động chia sẻ hành trình taxi kết hợp vận chuyển hành khách và bưu kiện có sử dụng thông tin dự báo nhu cầu (SARP mở rộng).
  4. Phát triển khung học máy phân thùng thích nghi (adaptive binning) để học quá trình Poisson không đồng nhất (NHPP) nhằm dự báo nhu cầu taxi theo thời gian thực và đề xuất thuật toán điều hướng xe rỗng dựa trên dự báo.

Đối tượng và phạm vi nghiên cứu

  • Đối tượng nghiên cứu: Các mô hình toán học và thuật toán tối ưu hóa (chính xác và heuristic/metaheuristic) cho các biến thể tĩnh và động của bài toán định tuyến phương tiện trong vận chuyển người và hàng hóa.
  • Phạm vi nghiên cứu:
    • Không gian bài toán tĩnh: Hệ thống phân phối sản phẩm sữa của một doanh nghiệp lớn tại Việt Nam, với các bộ dữ liệu thử nghiệm có quy mô lên đến 1.256 khách hàng, 4 trung tâm phân phối và 2 bãi đỗ xe.
    • Không gian bài toán động: Mạng lưới dịch vụ taxi vận chuyển hành khách và bưu kiện, thử nghiệm trên tập dữ liệu yêu cầu taxi thực tế của thành phố San Francisco.
    • Thời gian hoàn thành: Tháng 2 năm 2023 tại Trường Công nghệ Thông tin và Truyền thông (SoICT), Đại học Bách khoa Hà Nội.

Tổng quan tài liệu và vị trí của luận án

Các hướng nghiên cứu trước

Bài toán định tuyến phương tiện bắt đầu từ công trình của Dantzig và Ramser (1959) với bài toán điều phối xe tải (Truck Dispatching Problem) phục vụ nhu cầu xăng dầu. Từ đó, nhiều biến thể VRP được hình thành:

  1. Bài toán định tuyến có cửa sổ thời gian (VRPTW):

    • Hsu et al. (2007) áp dụng thuật toán heuristic dựa trên mức độ ưu tiên để giải quyết bài toán giao thực phẩm mau hỏng nhằm tối đa hóa độ tươi ngon của sản phẩm.
    • Afshar-Nadjafi & Sisakht (2018) nghiên cứu VRPTW với nhiều cửa sổ thời gian ưu tiên trong phân phối bánh kẹo tại Iran, giải quyết bằng thuật toán ong nhân tạo nhị phân điều chỉnh qua phương pháp Taguchi.
    • Toth & Vigo (2014) khảo sát toàn diện các ứng dụng VRPTW trong vận tải hàng hóa.

  2. Bài toán định tuyến đa kho (MDVRP) và đa chuyến (MTVRP):

    • Phương pháp chính xác: Contardo & Martinelli (2014) đề xuất thuật toán Branch-and-Cut-and-Price cho MDVRP với phương tiện không đồng nhất; Mingozzi et al. (2013) dùng Branch-and-Price cho MTVRP; Cattaruzza et al. (2014) đưa ra khung giải pháp chính xác dựa trên cấu trúc cho MTVRP.
    • Phương pháp heuristic và metaheuristic: Fallahi et al. (2008) nghiên cứu bài toán đa kho đa ngăn; Hemmelmayr et al. (2012) dùng tìm kiếm lân cận biến đổi (VNS); Vidal et al. (2012) áp dụng giải thuật di truyền (GA); MirHassani & Abolghasemi (2014) và Brandão (2020) giải bài toán định tuyến xe mở đa kho (MDOVRP) bằng VNS lai Tabu Search và ALNS.
    • Bài toán đa chuyến kết hợp đóng gói: Brandão & Mercer (1997), Olivera & Viera (2007), Petch & Salhi (2003) kết hợp VRP và kỹ thuật bin-packing. Che et al. (2021) nghiên cứu thời gian xếp hàng phụ thuộc khối lượng tại Singapore sử dụng thuật toán lai ALNS.

  3. Bài toán kết hợp đa kho - đa chuyến và chia sẻ hành trình (SARP/DARP):

    • Braekers et al. (2016) đề xuất metaheuristic cho bài toán Dial-a-Ride không đồng nhất, đa kho, đa chuyến.
    • Zhang et al. (2021) nghiên cứu bài toán gom bữa ăn từ nhiều nhà cung cấp chia sẻ nguồn lực logistics bằng ALNS.
    • Wang et al. (2020) mô hình hóa bài toán giao kiện hàng thương mại điện tử tại Trung Quốc với ngày phát hành (release dates) giải bằng PSO lai GA.
    • Li et al. (2014) lần đầu tiên đưa ra mô hình toán học MILP và thuật toán cho bài toán chia sẻ hành trình taxi cho cả người và hàng (SARP). Nguyen et al. (2017) và Archetti et al. (2018) phát triển các biến thể và thuật toán heuristic tiếp theo cho SARP.
Công trình Đa chuyến Đa kho Giới hạn chuyến Không bắt đầu tại kho Thời gian phục vụ phụ thuộc tải Cửa sổ thời gian Biên dưới tải trọng Phương pháp chính xác Phương pháp heuristic
Braekers et al. (2016) Có Có Có Không Không Có Không Không Có
Fallahi et al. (2008) Không Có Không Không Không Không Không Không Có
Zhang et al. (2021) Có Có Không Không Không Có Không Không Có
Cattaruzza et al. (2014) Có Không Không Không Không Không Không Có Không
Wang et al. (2020) Có Có Không Không Không Có Không Không Có
Che et al. (2021) Có Không Không Không Có Có Không Không Có
Luận án này Có Có Có Có Có Có Có Có Có

Khoảng trống luận án giải quyết

Luận án giải quyết khoảng trống trong bài toán định tuyến thực tế:

  • Tích hợp đồng thời 3 loại điểm có tính chất tiếp cận khác nhau (bãi đỗ chỉ đến/rời một lần theo một chiều, trung tâm phân phối đến nhiều lần, khách hàng phục vụ tối đa một lần).
  • Đưa vào ràng buộc cứng về biên dưới tải trọng xe trong bài toán phân phối hàng hóa tĩnh.
  • Tích hợp học máy dự báo dòng yêu cầu vào thuật toán điều phối xe trực tuyến nhằm định hướng xe rỗng trong bài toán SARP động.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết và khái niệm sử dụng

  • Lý thuyết bài toán tối ưu hóa (Optimization Problems - OPs): Xác định vector biến quyết định ${x}_{i=1}^n$ nhằm cực tiểu hóa hàm mục tiêu $f(x)$ trên không gian nghiệm khả thi $S_f$ thỏa mãn $m$ ràng buộc bất đẳng thức $g_j(x) \le 0$ và ràng buộc miền giá trị $D_i$.
  • Lớp bài toán NP-hard: Mọi biến thể nghiên cứu trong luận án đều thuộc lớp bài toán NP-hard, không thể giải tối ưu bằng thuật toán thời gian đa thức khi kích thước bài toán tăng.
  • Mô hình quy hoạch tuyến tính nguyên hỗn hợp (Mixed-Integer Linear Programming - MILP): Sử dụng các biến liên tục, biến nguyên và biến nhị phân để mô hình hóa mạng lưới dòng chảy, quan hệ thời gian, sức chứa và thứ tự hành trình.

Phương pháp nghiên cứu

Luận án kết hợp giữa phương pháp nghiên cứu định lượng, mô hình hóa toán học, thiết kế thuật toán tối ưu và thực nghiệm tính toán:

  1. Phương pháp chính xác (Exact Methods):

    • Phân tích cơ sở lý thuyết của Quy hoạch động (Dynamic Programming), Nhánh và cận (Branch-and-Bound), Nhánh và cắt (Branch-and-Cut), Nhánh và giá (Branch-and-Price), và Lập trình ràng buộc (Constraint Programming).
    • Triển khai mô hình MILP trên bộ giải GUROBI Optimizer nhằm đối sánh và xác thực tính đúng đắn của mô hình trên các bộ dữ liệu kích thước nhỏ.

  2. Phương pháp Heuristic và Metaheuristic:

    • Heuristic xây dựng: Phân tích thuật toán tiết kiệm (Saving Algorithm - SA của Clarke và Wright), thuật toán chèn tham lam (Greedy Insertion Algorithm - GIA), phương pháp gom cụm trước - định tuyến sau (CF-RS / Sweep Algorithm), và định tuyến trước - gom cụm sau (RF-CS).
    • Tìm kiếm cục bộ (Local Search - LS): Sử dụng 7 cấu trúc lân cận cơ bản: One-point move, Two-point move, Two-opt move, Or-opt move, Three-opt move, Three-point move, Cross-exchange move.
    • Thuật toán tìm kiếm cục bộ lân cận lớn thích nghi (A-ALNS): Hoạt động theo nguyên lý phá hủy và tái tạo (ruin-and-recreate), tự động cập nhật trọng số và xác suất lựa chọn của các toán tử loại bỏ (removal operators) và chèn (insertion operators) dựa trên lịch sử tìm kiếm.

  3. Phương pháp học máy và thống kê trong định tuyến động:

    • Quá trình Poisson không đồng nhất (Non-Homogeneous Poisson Process - NHPP) để mô hình hóa tốc độ xuất hiện yêu cầu taxi theo không gian và thời gian.
    • Phương pháp phân thùng thích nghi (Adaptive Binning Method) khắc phục hiện tượng quá khớp (overfitting) của hồi quy đa thức từng đoạn.
    • Kiểm định thống kê Kolmogorov-Smirnov (KS), hàm phân phối tích lũy thực nghiệm (EDF/CDF), tối thiểu hóa rủi ro cấu trúc (Structural Risk Minimization - SRM).

Nội dung chính theo từng chương

Chapter 1: Background

Chương 1 cung cấp nền tảng lý thuyết tổng quan về bài toán tối ưu hóa, các biến thể VRP và các phương pháp giải quyết:

  • Mô hình CVRP: Phát biểu trên đồ thị $G = (V, E)$, với $V = {0, 1, \dots, n}$ ($0$ là kho, $1 \dots n$ là khách hàng), đoàn $m$ xe đồng nhất sức chứa $Q$. Mô hình gồm hàm mục tiêu cực tiểu hóa chi phí (1.1) cùng các ràng buộc bậc vào/ra (1.2), ràng buộc đoàn xe tại kho (1.3), ràng buộc liên thông loại trừ chu trình con và ràng buộc sức chứa (1.4): $$\sum_{i \in S, j \notin S} x_{i,j} \ge r(S), \quad \forall S \subset V \setminus {0}, S \neq \emptyset$$ trong đó $r(S) = \lceil \sum_{i \in S} d_i / Q \rceil$.

  • Mô hình PDVRPTW: Định nghĩa trên đồ thị với tập điểm đón $O = {1, \dots, n}$, tập điểm trả $D = {n+1, \dots, 2n}$, và kho ${0, 2n+1}$. Hệ thống ràng buộc gồm phục vụ đúng một lần (1.8-1.9), bảo toàn luồng (1.10-1.12), thời gian phục vụ điểm đón trước điểm trả (1.15), giới hạn thời lượng hành trình $R_k$ (1.16), cửa sổ thời gian $[e_i, l_i]$ (1.17) và sức chứa xe $C_k$ (1.18).

  • Mô hình bài toán chia sẻ hành trình (SARP): Mô hình MILP từ công trình của Li et al. (2014) phục vụ $n$ yêu cầu hành khách ($V^p$) và $m$ yêu cầu bưu kiện ($V^f$) trên đoàn taxi $K$ sức chứa $Q_k$, thời lượng tối đa $T_k$. Hàm mục tiêu cực đại hóa lợi nhuận (1.20): $$\max \sum_{i \in V^{p,o}} \sum_{j \in V} \sum_{k \in K} (\alpha + \sigma_1 d_{i, i+\eta}) X_{ij}^k + \sum_{i \in V^{f,o}} \sum_{j \in V} \sum_{k \in K} (\beta + \sigma_2 d_{i, i+\eta}) X_{ij}^k - \sum_{i \in V} \sum_{j \in V} \sum_{k \in K} \sigma_3 d_{ij} X_{ij}^k - \sum_{i \in V^{p,o}} \sum_{k \in K} \sigma_4 \left(\frac{r_i^k}{\tau_{i, i+\eta}} - 1\right)$$ trong đó $\alpha, \beta$ là lợi nhuận khởi tạo; $\sigma_1, \sigma_2$ là đơn giá cước/km; $\sigma_3$ là chi phí/km; $\sigma_4$ là hệ số chiết khấu cho thời gian trễ của khách.

  • Phương pháp tiếp cận: Phân loại chi tiết cây phương pháp giải VRP thành phương pháp chính xác (DP, BnB, BnC, BnP, CP) và phương pháp không chính xác (Heuristic cổ điển, Metaheuristic: ALNS, GA, ACS, PSO).

Chapter 2: Modelling and Solving a New Variant of Static Vehicle Routing Problem

Chương 2 mô hình hóa và giải quyết bài toán định tuyến phương tiện tĩnh đa chuyến, đa kho, có ràng buộc tải trọng biên dưới và thời gian bốc dỡ phụ thuộc hàng hóa (MTDLC-VR).

1. Mô tả bài toán và mô hình toán học MILP

  • Các tập hợp: Bãi đỗ xe $PK$, Trung tâm phân phối $D$, Khách hàng $C$, Điểm tổng hợp $V = PK \cup D \cup C$, Sản phẩm $P$, Đoàn xe $K$.
  • Các tham số: Thời gian chờ $twait$, thời gian bốc/dỡ một đơn vị tải trọng $tunit$, tải trọng biên dưới $\underline{c}(k)$, tải trọng biên trên $\overline{c}(k)$, số chuyến tối đa $q(k)$, ma trận hạn chế tiếp cận $rc(k, c)$, khách hàng chỉ định $vc(k, c)$.
  • Hàm mục tiêu theo thứ tự từ điển: Cực tiểu hóa vector $F = (\hat{f} g_r + g_v + g_c)$, trong đó:
    1. $g_r = \eta - \sum_{i \in C} y_i$: Số khách hàng không được phục vụ (ưu tiên cao nhất, trọng số phạt lớn $\hat{f}$).
    2. $g_v = \sum_{k \in K} f_k z^{k,1}$: Chi phí sử dụng phương tiện (ưu tiên thứ hai, ưu tiên xe nội bộ hơn xe thuê ngoài).
    3. $g_c = \sum_{k \in K} \sum_{q=1}^{q(k)} \sum_{(i,j) \in E} d_{i,j} x_{i,j}^{k,q}$: Tổng quãng đường di chuyển (ưu tiên thứ ba).

2. Thách thức của ràng buộc biên dưới tải trọng

Khi xây dựng lộ trình tuần tự, việc chèn khách hàng đầu tiên vào một chuyến xe làm phát sinh vi phạm biên dưới tải trọng ($\sum w < \underline{c}(k)$). Vi phạm chỉ biến mất khi tích lũy đủ số lượng khách hàng sao cho tổng tải trọng nằm trong $[\underline{c}(k), \overline{c}(k)]$. Các thuật toán kinh điển (SA, GIA, Sweep) không thể áp dụng trực tiếp vì không cho phép trạng thái trung gian vi phạm.

Tác giả đề xuất giải pháp kỹ thuật:

  • Cho phép vi phạm tạm thời ràng buộc biên dưới như một ràng buộc mềm trong quá trình tìm kiếm.
  • Áp dụng thủ tục chuyển nút (node transfer) giữa các chuyến xe của cùng một xe hoặc giữa các xe khác nhau để cân bằng tải trọng và triệt tiêu vi phạm.

3. Thuật toán A-ALNS

  • Thiết kế các toán tử loại bỏ (Shaw removal, Random removal, Worst removal, Supplier-oriented removal) và các toán tử chèn (Greedy insertion, Regret insertion).
  • Kết hợp thủ tục chia tách (splitting procedure) để phân bổ lộ trình thỏa mãn giới hạn thời gian làm việc và sức chứa xe.

4. Kết quả thực nghiệm

  • Kiểm chứng mô hình MILP trên GUROBI với các bộ dữ liệu nhỏ ($E21-1-2-4-6-5$, $RG-1-2-2-2-6$, $RG-2-2-2-2-6$).
  • Thuật toán A-ALNS đạt chất lượng nghiệm tiệm cận tối ưu của MILP trên mẫu nhỏ trong thời gian tính toán ngắn hơn nhiều.
  • A-ALNS xử lý thành công bài toán thực tế quy mô lớn của doanh nghiệp sữa với 1.256 khách hàng, 4 kho và 2 bãi đỗ xe.
  • Mã nguồn và dữ liệu thực nghiệm được công bố tại: https://github.com/sonnv188/MTDLC-VR.git.

Chapter 3: Modelling and Solving a New Variant of Dynamic Vehicle Routing Problem

Chương 3 phát triển mô hình định tuyến trực tuyến cho mạng lưới xe taxi chia sẻ hành trình chở người và bưu kiện dựa trên thông tin dự báo.

1. Mô hình dự báo nhu cầu taxi

  • Phân tích dữ liệu thực tế tại San Francisco cho thấy phương pháp hồi quy đa thức từng đoạn truyền thống bị hiện tượng quá khớp (overfitting).
  • Tác giả đề xuất khung học thích nghi (adaptive binning method) để ước lượng quá trình Poisson không đồng nhất (NHPP), chia nhỏ khoảng thời gian thành các khoảng con thích nghi nhằm nắm bắt chính xác quy luật xuất hiện của các yêu cầu vận chuyển.

2. Thuật toán định tuyến trực tuyến và điều hướng xe rỗng

  • Xử lý yêu cầu trực tuyến: Khi có yêu cầu mới (người hoặc bưu kiện), thuật toán tìm kiếm các vị trí chèn hợp lệ dọc theo hành trình hiện tại của các taxi đang hoạt động, đảm bảo thứ tự đón trước trả sau và các ràng buộc về thời gian chờ, thời gian di chuyển tối đa.
  • Tái tối ưu hóa lộ trình: Sử dụng toán tử hoán đổi (Exchange operator) để sắp xếp lại chuỗi phục vụ khi có sự thay đổi.
  • Chiến lược điều hướng xe rỗng (Prediction-Based Idle Taxi Direction): Khi taxi trả khách/hàng tại điểm cuối cùng và rơi vào trạng thái rỗng, thay vì đậu tại chỗ hoặc di chuyển ngẫu nhiên, hệ thống dựa trên thông tin dự báo từ mô hình NHPP để điều hướng xe di chuyển về khu vực có xác suất đón khách mới cao nhất.

3. Kết quả thực nghiệm

  • So sánh hiệu năng với 4 thuật toán định tuyến và mô hình DSARP của Li et al. (2014) trên cùng bộ tham số.
  • Kết quả chứng minh thuật toán dựa trên dự báo giúp giảm tỷ lệ từ chối yêu cầu (failure requests), giảm quãng đường chạy rỗng và tăng lợi nhuận tích lũy (accumulated profit) của hệ thống taxi.

Kết quả và những đóng góp mới

Đóng góp về mặt lý luận và khoa học

  1. Xây dựng mô hình toán học mới cho bài toán định tuyến tĩnh: Luận án định nghĩa và mô hình hóa hình thức bài toán MTDLC-VR tích hợp đầy đủ các ràng buộc thực tế: đa kho, đa chuyến, bãi đỗ riêng biệt, thời gian bốc dỡ phụ thuộc khối lượng, hạn chế xe truy cập và ràng buộc biên dưới tải trọng phương tiện.
  2. Đề xuất phương pháp giải quyết ràng buộc biên dưới: Phân tích bản chất toán học của ràng buộc biên dưới tải trọng đối với các heuristic xây dựng, đề xuất cơ chế chuyển nút (node transfer) và nới lỏng ràng buộc có kiểm soát.
  3. Phát triển mô hình định tuyến động dựa trên dự báo: Mở rộng bài toán chia sẻ hành trình chở người và hàng (SARP) bằng cách kết hợp thông tin dự báo stochastic vào quá trình ra quyết định định tuyến theo thời gian thực.
  4. Đóng góp về phương pháp học máy thống kê: Đề xuất phương pháp phân thùng thích nghi (adaptive binning) học quá trình Poisson không đồng nhất (NHPP), giải quyết vấn đề quá khớp trên dữ liệu chuỗi thời gian không gian.

Đóng góp về mặt thực tiễn và ứng dụng

  1. Giải quyết bài toán phân phối thực tế tại doanh nghiệp: Thuật toán A-ALNS giải quyết bài toán lập lịch phân phối sữa hàng ngày với quy mô hơn 1.000 điểm giao hàng tại Việt Nam, rút ngắn thời gian lập kế hoạch từ một ngày làm việc xuống mức thời gian tính toán tự động của máy tính.
  2. Cung cấp bộ dữ liệu chuẩn và mã nguồn mở: Toàn bộ mô hình, các bộ dữ liệu thử nghiệm và mã nguồn thuật toán được công khai tại kho lưu trữ GitHub phục vụ cộng đồng nghiên cứu.
  3. Nâng cao hiệu quả vận hành dịch vụ taxi: Chiến lược định hướng xe rỗng giúp tài xế taxi tăng doanh thu, giảm thời gian và quãng đường chạy không tải trong đô thị.

Hạn chế và hướng nghiên cứu tiếp

Hạn chế của nghiên cứu

  • Trong bài toán phân phối tĩnh, mô hình giả định nguồn hàng tại các trung tâm phân phối luôn sẵn sàng đáp ứng đầy đủ (không xét đến tình trạng thiếu hụt tồn kho tạm thời).
  • Trong kịch bản động, các yếu tố biến động giao thông thời gian thực (như thay đổi đột ngột vận tốc do tai nạn hoặc tắc đường nghiêm trọng) chưa được mô hình hóa thành biến ngẫu nhiên liên tục mà dựa trên ma trận thời gian di chuyển cố định theo từng khung giờ.

Hướng nghiên cứu tiếp

  • Mở rộng bài toán MTDLC-VR sang trường hợp thời gian di chuyển phụ thuộc thời gian (Time-Dependent VRP) và xét thêm yếu tố tồn kho hữu hạn tại các trung tâm phân phối.
  • Ứng dụng mô hình chia sẻ hành trình động cho các hệ thống xe điện (Electric Vehicles - EV), tích hợp ràng buộc về trạm sạc, thời gian sạc và dung lượng pin.
  • Cải tiến các kỹ thuật học sâu (Deep Learning) kết hợp học tăng cường (Reinforcement Learning) để điều phối tức thời trong các mạng lưới giao thông quy mô siêu lớn.

Giá trị tham khảo

Đối tượng thụ hưởng

  1. Nghiên cứu sinh và học viên cao học: Chuyên ngành Khoa học máy tính, Vận trù học (Operations Research), Hệ thống thông tin và Kỹ thuật Logistics.
  2. Giảng viên và nhà nghiên cứu: Tham khảo phương pháp tích hợp giữa mô hình quy hoạch toán học (MILP), giải thuật metaheuristic (ALNS) và các mô hình học máy thống kê (NHPP).
  3. Kỹ sư phát triển phần mềm và nhà quản trị logistics: Ứng dụng cấu trúc thuật toán và mô hình phân bổ đội xe trong việc xây dựng hệ thống quản lý vận tải (Transportation Management System - TMS) và ứng dụng điều xe công nghệ.

Các nội dung có giá trị tham khảo chuyên sâu

  • Mục 2.2 & 2.3 (Chương 2): Toàn bộ hệ thống ký hiệu, biến quyết định và công thức toán học hoàn chỉnh của bài toán MTDLC-VR.
  • Mục 2.3.2 (Chương 2): Phân tích cơ chế vượt qua điểm nghẽn của ràng buộc biên dưới tải trọng trong thuật toán tìm kiếm.
  • Mục 3.3 (Chương 3): Quy trình triển khai phương pháp phân thùng thích nghi cho quá trình Poisson không đồng nhất trên dữ liệu không gian - thời gian thực tế.

Câu hỏi thường gặp

1. Ràng buộc biên dưới tải trọng (lower-bound capacity constraint) trong bài toán MTDLC-VR có ý nghĩa gì và tại sao lại gây khó khăn cho các thuật toán heuristic?

Trong thực tế giao hàng của các công ty sữa, việc điều phối một chiếc xe tải trọng lớn nhưng chỉ chở một lượng hàng rất nhỏ (ví dụ xe 10 tấn chở 100 kg hàng) do ràng buộc cửa sổ thời gian ngặt nghèo sẽ gây lãng phí chi phí vận hành và mất cân bằng tài nguyên. Ràng buộc biên dưới bắt buộc tổng khối lượng hàng trên mỗi chuyến xe phải đạt một ngưỡng tối thiểu $\underline{c}(k)$.

Ràng buộc này gây khó khăn lớn cho các heuristic kinh điển (như Clarke-Wright Saving hay Greedy Insertion) vì các thuật toán này xây dựng nghiệm bằng cách chèn từng khách hàng tuần tự. Khi chèn khách hàng đầu tiên, chuyến xe luôn rơi vào trạng thái vi phạm biên dưới tải trọng và chỉ thỏa mãn khi đã gom đủ khối lượng hàng nhất định, khiến thuật toán heuristic tuần tự thông thường không thể đánh giá tính khả thi ở các bước trung gian.

2. Hàm mục tiêu của bài toán MTDLC-VR được thiết lập theo thứ tự ưu tiên như thế nào?

Hàm mục tiêu được xây dựng theo thứ tự từ điển (lexicographic order) gồm ba thành phần:

  1. $g_r$ (Số khách hàng không được phục vụ): Ưu tiên cao nhất, được nhân với trọng số phạt rất lớn $\hat{f}$ để đảm bảo tối đa hóa số lượng khách hàng được đáp ứng.
  2. $g_v$ (Số lượng và chi phí phương tiện sử dụng): Ưu tiên thứ hai, trong đó xe thuộc đội xe nội bộ có chi phí ưu tiên $f_k$ thấp hơn so với xe thuê ngoài $f_{k'}$.
  3. $g_c$ (Tổng quãng đường di chuyển): Ưu tiên thứ ba, nhằm tối ưu hóa chi phí nhiên liệu sau khi đã thỏa mãn tối đa khách hàng và tối thiểu hóa số xe.

3. Khung học máy phân thùng thích nghi (adaptive binning) ở Chương 3 giải quyết vấn đề gì trong dự báo nhu cầu taxi?

Khi phân tích dữ liệu lịch sử yêu cầu taxi tại San Francisco, phương pháp hồi quy đa thức từng đoạn với các khoảng chia thời gian cố định gặp phải hiện tượng quá khớp (overfitting), dẫn đến sai số dự báo lớn ở các khung giờ biến động nhu cầu cao. Phương pháp phân thùng thích nghi (adaptive binning) giải quyết vấn đề này bằng cách tự động điều chỉnh độ dài các khoảng thời gian dựa trên mật độ dữ liệu thực tế và nguyên lý tối thiểu hóa rủi ro cấu trúc (SRM), giúp ước lượng chính xác hàm cường độ của quá trình Poisson không đồng nhất (NHPP).

4. Chiến lược định hướng xe taxi rỗng (Prediction-Based Idle Taxi Direction) mang lại lợi ích gì so với các mô hình trước đây?

Trong các mô hình SARP trước đây (như Li et al., 2014), khi taxi hoàn thành việc trả khách hoặc hàng cuối cùng, xe sẽ ở trạng thái đứng chờ tại chỗ hoặc di chuyển ngẫu nhiên cho đến khi nhận được yêu cầu mới. Chiến lược định hướng xe rỗng trong luận án sử dụng thông tin dự báo nhu cầu tương lai từ mô hình NHPP để chủ động hướng dẫn tài xế di chuyển về các khu vực có xác suất phát sinh đơn hàng mới cao nhất. Điều này giúp giảm đáng kể thời gian và khoảng cách chạy rỗng (idle distance), đồng thời tăng tỷ lệ phục vụ thành công các yêu cầu mới xuất hiện.

Kết luận

Luận án của tác giả Nguyễn Văn Sơn đã giải quyết hai bài toán định tuyến phương tiện phức tạp trong kịch bản tĩnh và kịch bản động. Trong kịch bản tĩnh, bài toán MTDLC-VR được phát biểu hình thức cùng mô hình MILP và thuật toán metaheuristic A-ALNS, giải quyết hiệu quả bài toán phân phối hàng hóa thực tế có ràng buộc biên dưới tải trọng với quy mô trên 1.000 điểm giao hàng. Trong kịch bản động, mô hình chia sẻ hành trình taxi SARP kết hợp phương pháp phân thùng thích nghi học quá trình Poisson không đồng nhất (NHPP) đã chứng minh tính hiệu quả trong việc định hướng xe rỗng và tối ưu hóa lợi nhuận vận hành trên dữ liệu thực tế. Công trình đóng góp hệ thống mô hình toán học chặt chẽ, thuật toán giải hiệu quả và công bố toàn bộ dữ liệu, mã nguồn mở cho cộng đồng nghiên cứu.