Tổng quan luận án

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

Vận tải đóng vai trò thiết yếu trong việc phát triển kinh tế và kết nối liên vùng. Theo báo cáo sơ bộ của Tổng cục Thống kê Việt Nam năm 2015, cả nước có khoảng 43 triệu phương tiện giao thông, vận chuyển hơn 3,3039 tỷ lượt hành khách và 1,2 tỷ tấn hàng hóa. Vận tải chiếm khoảng 25% tổng năng lượng tiêu thụ của một nền kinh tế và chi phí vận tải chiếm xấp xỉ 20% tổng giá thành sản phẩm. Sự mở rộng nhanh chóng về diện tích và dân số đô thị dẫn đến các hệ quả như ùn tắc giao thông, tiếng ồn, ô nhiễm và tai nạn. Do đó, việc tối ưu hóa lộ trình vận chuyển người và hàng hóa là bài toán cấp thiết nhằm nâng cao năng lực vận chuyển, tiết kiệm chi phí, tăng lợi nhuận cho doanh nghiệp và giảm tải áp lực hạ tầng.

Bài toán định tuyến phương tiện (Vehicle Routing Problem - VRP) là bài toán thuộc lớp NP-khó (NP-hard). Các mô hình VRP kinh điển như bài toán VRP có ràng buộc tải trọng (CVRP), bài toán Min-Max VRP không có ràng buộc tải trọng (MMVRP), hay bài toán giao nhận hàng có khung thời gian (PDVRPTW) thường đơn giản hóa so với thực tế vận hành. Trong thực tiễn, việc điều phối phương tiện được chia thành hai kịch bản chính: tĩnh (static) và động (dynamic).

Khoảng trống nghiên cứu được tác giả xác định bao gồm hai vấn đề lớn:

  1. Trong kịch bản tĩnh: Các mô hình hiện có chủ yếu áp dụng chặn trên tải trọng (upper-bound capacity). Tuy nhiên, trong phân phối thực tế của doanh nghiệp, việc phương tiện thực hiện chuyến đi với tải trọng quá thấp gây lãng phí nguồn lực và giảm hiệu quả kinh tế. Ràng buộc chặn dưới tải trọng phương tiện (lower-bound capacity constraint) kết hợp với các yếu tố thực tế như đa chuyến (multi-trip), đa trung tâm phân phối (multi-depot), thời gian bốc/dỡ hàng phụ thuộc khối lượng và chủng loại sản phẩm chưa được nghiên cứu đầy đủ trong y văn.
  2. Trong kịch bản động: Các mô hình chia sẻ chuyến đi giữa hành khách và bưu kiện (Shared-a-Ride Problem - SARP) thường chỉ tối ưu hóa cục bộ các sự kiện hiện hành mà chưa khai thác hiệu quả thông tin dự báo nhu cầu tương lai để định hướng lộ trình cho các phương tiện đang rỗng (idle vehicles), dẫn đến quãng đường di chuyển không tải còn cao.

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

Mục tiêu chính của luận án là mở rộng các biến thể VRP hiện có nhằm phản ánh sát thực tế vận hành, xây dựng mô hình toán học và phát triển các thuật toán hiệu quả để giải quyết:

  • Mục tiêu 1: Xây dựng mô hình quy hoạch tuyến tính nguyên hỗn hợp (MILP) và thuật toán heuristic/metaheuristic thích ứng cho bài toán định tuyến phương tiện phân phối hàng hóa tĩnh với ràng buộc chặn dưới tải trọng, đa chuyến, đa kho và thời gian phục vụ phụ thuộc tải trọng (bài toán MTDLC-VR).
  • Mục tiêu 2: Phát triển mô hình định tuyến taxi chia sẻ chuyến cho người và hàng hóa trong kịch bản động, kết hợp phương pháp học máy dựa trên dữ liệu để dự báo nhu cầu đặt xe theo thời gian thực và thuật toán định hướng phương tiện rỗng nhằm giảm thời gian chờ và quãng đường không tải.

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

  • Đối tượng nghiên cứu: Các mô hình tối ưu hóa định tuyến phương tiện (VRP tĩnh và động), các thuật toán chính xác, thuật toán heuristic xây dựng (construction heuristics), thuật toán tìm kiếm cục bộ (local search), thuật toán tìm kiếm lân cận lớn thích ứng (ALNS), và các mô hình học máy thống kê dự báo quá trình Poisson không đồng nhất (Non-Homogeneous Poisson Process - NHPP).
  • Phạm vi nghiên cứu:
    • Về không gian và dữ liệu thực nghiệm kịch bản tĩnh: Dữ liệu vận hành thực tế từ một công ty phân phối sữa quy mô lớn tại Việt Nam, với quy mô thử nghiệm lên tới 1256 khách hàng, 4 trung tâm phân phối và 2 bãi đỗ xe.
    • Về không gian và dữ liệu thực nghiệm kịch bản động: Dữ liệu di chuyển của mạng lưới taxi thực tế tại thành phố San Francisco (Mỹ).
    • Về thời gian: Phân tích dữ liệu vận tải và các mô hình được công bố đến năm 2023.

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

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

Tác giả đã tổng hợp và phân loại các công trình nghiên cứu VRP từ kinh điển đến hiện đại:

  • Nguồn gốc bài toán VRP: Dantzig và Ramser (1959) lần đầu giới thiệu bài toán điều phối xe tải (Truck Dispatching Problem). Sau đó, bài toán được mở rộng thành CVRP, PDVRPTW, MDVRP (Multi-Depot VRP) và MTVRP (Multi-Trip VRP) (Toth & Vigo, 2002; Golden et al., 2008).
  • Mở rộng khung thời gian (VRPTW): Các nghiên cứu của Ghiani et al. (2014), Belhaiza et al. (2014) về phân phối hàng thực phẩm tươi sống có thời gian sử dụng ngắn; Rahimi-Vahed et al. (2015) nghiên cứu VRPTW đa mức độ ưu tiên cho phân phối bánh kẹo tại Iran; Braekers et al. (2016) tổng quan các ứng dụng vận tải hàng hóa.
  • Mô hình đa kho (MDVRP) và đa kho mở (MDOVRP): Ramos et al. (2014) khảo sát MDVRP; Contardo và Martinelli (2014) đề xuất thuật toán Branch-and-Cut-and-Price (BnC/BnP); Mirabi et al. (2010), Zhen et al. (2020) nghiên cứu giải thuật biến đổi lân cận (Variable Neighborhood Search); Sadati et al. (2021) kết hợp ALNS và tìm kiếm Tabu cho MDOVRP.
  • Mô hình đa chuyến (MTVRP): Fleischmann (1990) đề xuất khái niệm xe thực hiện nhiều hành trình trong ngày; Taillard et al. (1996) đưa ra mô hình set covering; Mingozzi et al. (2013), Cattaruzza et al. (2016) phát triển thuật toán chính xác; Pisinger và Ropke (2007), Nguyen et al. (2013) giải MTVRP bằng cách kết hợp VRP và bài toán đóng gói (bin packing).
  • Mô hình kết hợp đa chuyến, đa kho (Multi-Trip Multi-Depot): Li et al. (2018) nghiên cứu bài toán Dial-a-Ride không đồng nhất; Yan et al. (2020) nghiên cứu chia sẻ tài nguyên vận chuyển đồ ăn từ nhiều nhà cung cấp; Wang et al. (2020) khảo sát mô hình giao hàng thương mại điện tử có ngày phát hành hàng (release dates).
  • Mô hình chia sẻ vận chuyển người và hàng hóa (SARP): Xuất phát từ bài toán Dial-A-Ride (DARP) (Cordeau & Laporte, 2007), Li et al. (2014) đề xuất mô hình SARP cho taxi phục vụ đồng thời người và bưu kiện ở cả hai kịch bản tĩnh và động; Nguyen et al. (2017) phát triển các thuật toán heuristic mở rộng cho mô hình này.

Bảng tổng hợp các đặc điểm nghiên cứu liên quan

Dưới đây là bảng đối sánh các ràng buộc và phương pháp giữa các công trình tiêu biểu được tác giả tổng hợp trong luận án:

Công trình Đa chuyến (Multi-trip) Đa kho (Multi-depot) Giới hạn số chuyến Không bắt đầu tại kho Thời gian phục vụ phụ thuộc Khung thời gian (Time-window) Chặn dưới tải trọng (Lower-bound capacity) Phương pháp chính xác Phương pháp heuristic
Li et al. (2018) Có Có - - - Có Không - Có
Zhen et al. (2020) - Có - - - Có Không - Có
Yan et al. (2020) Có Có - - - - Không - Có
Cattaruzza et al. (2016) Có - Có - - Có Không Có -
Wang et al. (2020) Có Có - - - Có Không - Có
Nguyen et al. (2013) Có - - - Có Có Không - Có
Luận án này Có Có Có Có Có Có Có Có Có

Vị trí và khoảng trống luận án giải quyết

Luận án định vị nghiên cứu vào việc giải quyết đồng thời các ràng buộc thực tiễn phức hợp chưa từng được tích hợp đầy đủ:

  1. Đưa ra ràng buộc chặn dưới tải trọng đối với từng chuyến đi trong bài toán VRP tĩnh đa kho, đa chuyến nhằm tránh tình trạng xe chạy dưới định mức kinh tế.
  2. Tích hợp ba loại điểm địa lý với cơ chế tiếp cận khác nhau: điểm đỗ xe (thăm 1 lần), trung tâm phân phối (thăm nhiều lần), và điểm khách hàng (thăm tối đa 1 lần).
  3. Đề xuất cơ chế điều phối xe rỗng trong bài toán SARP động dựa trên việc học phân phối Poisson không đồng nhất của dữ liệu nhu cầu tương lai.

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

Cơ sở lý thuyết và khung phân tích

  • Lý thuyết tối ưu hóa tổ hợp và bài toán quy hoạch toán học: Mô hình hóa bài toán VRP dưới dạng đồ thị có hướng $G = (V, E)$, xây dựng mô hình quy hoạch tuyến tính nguyên hỗn hợp (MILP) với các ràng buộc bảo toàn luồng, ràng buộc khung thời gian, giới hạn tải trọng hai phía và ràng buộc thứ tự phục vụ.
  • Lý thuyết tìm kiếm lân cận và Metaheuristics: Khung tìm kiếm lân cận lớn thích ứng (ALNS - Adaptive Large Neighborhood Search) dựa trên nguyên lý phá hủy và tái tạo (ruin-and-recreate) của Schrimpf et al. (2000) và Ropke & Pisinger (2006). Tích hợp các toán tử tìm kiếm cục bộ (Local Search) kinh điển: One-point move, Two-point move, Two-opt move, Or-opt move, Three-opt move, Three-point move, Cross-exchange move.
  • Lý thuyết xác suất thống kê và quá trình ngẫu nhiên: Mô hình hóa luồng yêu cầu vận tải động theo quá trình Poisson không đồng nhất (NHPP - Non-Homogeneous Poisson Process).
  • Lý thuyết học máy: Phương pháp giảm thiểu rủi ro kinh nghiệm (Empirical Risk Minimization - ERM) và giảm thiểu rủi ro cấu trúc (Structural Risk Minimization - SRM), kiểm định Kolmogorov-Smirnov (KS), hàm phân phối tích lũy thực nghiệm (EDF).

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

  • Phương pháp mô hình hóa toán học: Thiết lập hệ thống công thức giải tích cho bài toán tối ưu hóa tĩnh và động.
  • Phương pháp giải tích chính xác: Sử dụng phần mềm thương mại GUROBI Optimizer để giải mô hình MILP trên các bộ dữ liệu quy mô nhỏ nhằm kiểm chứng tính đúng đắn của mô hình toán học và tìm nghiệm tối ưu toàn cục ($s^*$).
  • Phương pháp thiết kế thuật toán Heuristic/Metaheuristic:
    • Xây dựng thuật toán Heuristic chèn thích ứng (Adapted Construction Heuristics) kết hợp thủ tục phân tách chuyến (Splitting procedure) và chuyển đổi điểm (Node transfer) để xử lý ràng buộc chặn dưới tải trọng.
    • Thiết kế thuật toán A-ALNS (Adapted ALNS) với cơ chế tự điều chỉnh trọng số toán tử phá hủy (removal) và tái tạo (insertion) dựa trên lịch sử tìm kiếm.
    • Thiết kế khung học phân vùng thích ứng (Adaptive Binning Method) để học tỷ lệ đến của yêu cầu taxi theo thời gian và không gian, kết hợp thuật toán định tuyến trực tuyến (Online Routing Algorithm) có bước định hướng phương tiện rỗng (Prediction-Based Idle Taxi Direction).

Nguồn tư liệu và dữ liệu thực nghiệm

  1. Bộ dữ liệu phân phối thực tế thu thập từ doanh nghiệp sữa tại Việt Nam (bao gồm tọa độ bãi đỗ, trung tâm phân phối, khách hàng, ma trận thời gian và khoảng cách di chuyển thực tế, khối lượng hàng hóa yêu cầu).
  2. Bộ dữ liệu chuẩn (benchmark instances) của bài toán VRP được điều chỉnh bổ sung ràng buộc chặn dưới.
  3. Bộ dữ liệu di chuyển và đặt xe taxi công khai tại thành phố San Francisco.

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

Chương 1: Kiến thức nền tảng (Background)

Chương 1 hệ thống hóa cơ sở lý thuyết về bài toán tối ưu hóa, bài toán định tuyến phương tiện và các phương pháp giải thuật:

  • Mô hình hóa không gian tìm kiếm: Định nghĩa không gian nghiệm khả thi $S_f$, các điểm cực tiểu địa phương ($s_1, s_2$) và cực tiểu toàn cục ($s^*$) trong bài toán tối ưu hóa hàm mục tiêu $f(x)$ với các ràng buộc đẳng thức và bất đẳng thức.
  • Hệ thống hóa các biến thể VRP:
    • CVRP: Mô hình hóa toán học trên đồ thị $G=(V,E)$ với $m$ phương tiện đồng nhất có tải trọng $Q$, mỗi khách hàng $i$ có nhu cầu $d_i$, cực tiểu hóa tổng chi phí di chuyển $\sum c_{i,j} x_{i,j}$.
    • PDVRPTW: Xây dựng mô hình MIP bao gồm tập điểm lấy hàng $O = {1, \dots, n}$, tập điểm giao hàng $D = {n+1, \dots, 2n}$, ràng buộc xe phải đến điểm lấy hàng trước điểm giao hàng ($ST^k_i + s_i + t_{i,n+i} \le ST^k_{n+i}$), tải trọng xe $W^k_i$ và thời gian phục vụ trong khung $[e_i, l_i]$.
    • SARP (Shared-A-Ride Problem): Phân tích mô hình toán học của Li et al. (2014) phục vụ $\eta = m+n$ yêu cầu (người và bưu kiện), hàm mục tiêu tối đa hóa lợi nhuận kết hợp chi phí xăng xe và hệ số phạt giảm giá khi kéo dài thời gian di chuyển của khách.
    • Rich VRP (RVRP): Phân tích các đặc trưng đa kho (MDVRP), đa chuyến (MTVRP), quay đầu (VRPB), Min-Max (MMCVRP).
  • Phân loại phương pháp giải quyết:
    • Phương pháp chính xác: Quy hoạch động (Dynamic Programming), thuật toán Nhánh - Cận (Branch-and-Bound - BnB), Nhánh - Cắt (Branch-and-Cut - BnC), Nhánh - Giá (Branch-and-Price - BnP), Quy hoạch ràng buộc (Constraint Programming - CP).
    • Thuật toán Heuristic cổ điển: Chiến lược Route-First Cluster-Second (RF-CS), Cluster-First Route-Second (CF-RS), thuật toán quét (Sweep Algorithm - SW), thuật toán tiết kiệm (Saving Algorithm - SA của Clarke & Wright), thuật toán chèn tham lam (Greedy Insertion Algorithm - GIA của Solomon).
    • Thuật toán tìm kiếm cục bộ và cấu trúc lân cận: Chi tiết 7 toán tử di chuyển phổ biến gồm One-point move, Two-point move, Two-opt move, Or-opt move, Three-opt move, Three-point move, Cross-exchange move.
    • Metaheuristics: Cơ chế đa dạng hóa (diversification) và tăng cường (intensification), khung thuật toán ALNS, GA, ACS, PSO.

Chương 2: Mô hình hóa và giải quyết biến thể mới của bài toán định tuyến xe tĩnh (Modelling and Solving a New Variant of Static Vehicle Routing Problem)

Chương 2 tập trung vào bài toán định tuyến xe tĩnh có ràng buộc chặn dưới tải trọng (MTDLC-VR):

  • Mô tả bài toán MTDLC-VR: Hệ thống vận chuyển gồm các bãi đỗ xe ($PK$), trung tâm phân phối ($D$), khách hàng ($C$) và danh mục sản phẩm ($P$). Mỗi xe $k$ có bãi đỗ $p(k)$, tải trọng chặn dưới $\underline{c}(k)$, tải trọng chặn trên $\overline{c}(k)$, số chuyến tối đa $q(k)$, hệ số ưu tiên phương tiện $f_k$ (phân biệt giữa xe nội bộ và xe thuê ngoài), tập khách hàng hạn chế tiếp cận $rc(k,c)$ và khách hàng chỉ định $vc(k,c)$.
  • Mô hình toán học MILP:
    • Hàm mục tiêu: Cực tiểu hóa tổng chi phí kết hợp theo thứ tự ưu tiên: $$\text{Minimize } F = f_b g_r + g_v + g_c$$ Trong đó $g_r$ là số lượng khách hàng không được phục vụ ($g_r = \eta - \sum_{i \in C} y_i$), $g_v$ là số lượng phương tiện huy động ($g_v = \sum_{k \in K} f_k z^{k,1}$), $g_c$ là tổng quãng đường di chuyển ($g_c = \sum_{k \in K} \sum_{q=1}^{q(k)} \sum_{(i,j) \in E} d_{i,j} x^{k,q}_{i,j}$), với $f_b$ là hệ số phạt cho mỗi khách hàng bị bỏ lỡ.
    • Hệ thống ràng buộc: Bảo toàn luồng trên từng chuyến và toàn bộ hành trình; xe rời bãi đỗ tối đa một lần và quay về bãi đỗ tối đa một lần; thời gian bắt đầu phục vụ tại điểm tiếp theo tính cả thời gian chờ $t_{wait}(dp)$ và thời gian bốc xếp phụ thuộc tải trọng $\sum_p w(p) \cdot t_{unit}(dp)$; ràng buộc tải trọng nằm trong đoạn $[\underline{c}(k), \overline{c}(k)]$.

Bảng tóm tắt các tập hợp, tham số và biến số mô hình MTDLC-VR

Ký hiệu Loại Diễn giải ý nghĩa
$PK, D, C, P, K$ Tập hợp Lần lượt là tập bãi đỗ xe, trung tâm phân phối, khách hàng, sản phẩm, và đội phương tiện
$[e(i), l(i)]$ Tham số Khung thời gian phục vụ tại điểm $i \in PK \cup D \cup C$
$t_{wait}(i), t_{unit}(i)$ Tham số Thời gian chờ bắt đầu và thời gian bốc/dỡ một đơn vị khối lượng tại điểm $i$
$\underline{c}(k), \overline{c}(k)$ Tham số Giới hạn chặn dưới và chặn trên tải trọng của phương tiện $k$
$f_k, f_b$ Tham số Hệ số chi phí sử dụng xe $k$ và hệ số phạt cho một khách hàng không được phục vụ
$rc(k,c), vc(k,c)$ Tham số Ma trận nhị phân giới hạn quyền tiếp cận và chỉ định phục vụ giữa xe $k$ và khách hàng $c$
$x^{k,q}_{i,j}$ Biến nhị phân Bằng 1 nếu xe $k$ di chuyển trên cung $(i,j)$ trong chuyến thứ $q$; ngược lại bằng 0
$y_i$ Biến nhị phân Bằng 1 nếu khách hàng $i$ được phục vụ; ngược lại bằng 0
$z^{k,q}$ Biến nhị phân Bằng 1 nếu xe $k$ thực hiện chuyến đi thứ $q$; ngược lại bằng 0
$wp^{k,q}_p$ Biến liên tục Tổng khối lượng sản phẩm $p$ được xe $k$ vận chuyển trong chuyến thứ $q$
$s^{k,q}_i$ Biến liên tục Thời điểm bắt đầu phục vụ của xe $k$ tại điểm $i$ trong chuyến thứ $q$
  • Phân tích thách thức của ràng buộc chặn dưới tải trọng: Tác giả chứng minh rằng các thuật toán chèn tuần tự kinh điển (SA, GIA, SW) bị mất tính khả thi khi áp dụng trực tiếp do việc chèn khách hàng đầu tiên luôn gây vi phạm tức thời điều kiện chặn dưới tải trọng.
  • Đề xuất giải thuật:
    • Thuật toán khởi tạo thích ứng kết hợp thủ tục phân tách (Adapted construction algorithms with splitting procedure) và chuyển đổi điểm (Node transfer) giữa các chuyến xe hoặc giữa các phương tiện để đưa tải trọng vào khoảng hợp lệ $[\underline{c}, \overline{c}]$.
    • Thuật toán tìm kiếm lân cận lớn thích ứng cải tiến (A-ALNS) với các toán tử loại bỏ (removal operators) và toán tử chèn (insertion operators) chuyên biệt cho ràng buộc chặn dưới.
  • Kết quả thực nghiệm Chương 2:
    • Bộ giải GUROBI giải thành công nghiệm tối ưu cho các bộ dữ liệu nhỏ (ví dụ các bộ thực nghiệm $E21-1-2-4-6-5$, $RG-1-2-2-2-6$).
    • Thuật toán A-ALNS cho kết quả xấp xỉ nghiệm tối ưu của MILP trên dữ liệu nhỏ nhưng có thời gian tính toán ngắn hơn đáng kể, đồng thời xử lý tốt các bộ dữ liệu lớn lên tới 1256 khách hàng.
    • Phân tích độ nhạy (Sensitivity analysis) cho thấy mối tương quan rõ rệt giữa mức chặn dưới tải trọng và số lượng khách hàng bị từ chối phục vụ hoặc số chuyến bị hủy.

Chương 3: Mô hình hóa và giải quyết biến thể mới của bài toán định tuyến xe động (Modelling and Solving a New Variant of Dynamic Vehicle Routing Problem)

Chương 3 giải quyết bài toán điều phối taxi chia sẻ hành trình (SARP) trong kịch bản động có tích hợp thông tin dự báo:

  • Mô hình định tuyến taxi chia sẻ trực tuyến (Online Taxi-Share Routing): Mở rộng từ mô hình của Li et al. (2014) và Nguyen et al., cho phép người và bưu kiện cùng chia sẻ không gian taxi dưới các điều kiện thời gian thực.
  • Dự báo nhu cầu đặt xe (Taxi Demand Prediction):
    • Chỉ ra hiện tượng quá khớp (overfitting) của mô hình hồi quy đa thức từng đoạn (piecewise-polynomial regression) trên dữ liệu thực tế.
    • Đề xuất khung học thích ứng (Adaptive Binning Method) để ước lượng hàm cường độ của quá trình Poisson không đồng nhất (NHPP) theo các khoảng thời gian và khu vực địa lý không đồng đều.
  • Thuật toán định tuyến trực tuyến khai thác dự báo (Online Routing Algorithm):
    • Xác định các vị trí chèn khả thi (Possible Positions for Insertion) khi có yêu cầu mới xuất hiện.
    • Tái tối ưu hóa tuyến đường hiện tại (Route Re-optimization) bằng các toán tử trao đổi (Exchange operator).
    • Đề xuất cơ chế điều hướng taxi rỗng dựa trên dự báo (Prediction-Based Idle Taxi Direction): Khi taxi hoàn thành điểm trả khách cuối cùng và rơi vào trạng thái rỗng, hệ thống sẽ đề xuất lộ trình di chuyển hướng về các khu vực có xác suất xuất hiện nhu cầu cao nhất thay vì đứng yên hoặc di chuyển ngẫu nhiên.
  • Kết quả thực nghiệm Chương 3:
    • Thử nghiệm trên tập dữ liệu taxi San Francisco qua hai kịch bản mô phỏng.
    • So sánh hiệu năng giữa 4 thuật toán lập lịch: Thuật toán tích hợp dự báo đề xuất cho lợi nhuận tích lũy (accumulated profit) cao hơn và tỷ lệ yêu cầu thất bại (percentage of failure requests) thấp hơn so với các phương pháp không sử dụng thông tin dự báo.

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

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

  1. Định nghĩa và mô hình hóa biến thể bài toán VRP tĩnh mới (MTDLC-VR): Tích hợp thành công ràng buộc chặn dưới tải trọng phương tiện cùng các đặc trưng đa kho, đa chuyến, đa bãi đỗ, thời gian phục vụ phụ thuộc khối lượng bốc dỡ, khách hàng hạn chế và khách hàng chỉ định vào một mô hình quy hoạch tuyến tính nguyên hỗn hợp (MILP) hoàn chỉnh.
  2. Làm rõ tính chất toán học của ràng buộc chặn dưới: Phân tích bản chất đứt gãy không gian nghiệm khả thi của ràng buộc chặn dưới đối với các giải thuật chèn tuần tự truyền thống, thiết lập nền tảng lý thuyết cho các toán tử chuyển giao nút (node transfer) và phân tách lộ trình.
  3. Mô hình hóa bài toán SARP động kết hợp học máy dự báo: Thiết lập khung lý thuyết tích hợp giữa mô hình ngẫu nhiên NHPP với thuật toán định tuyến trực tuyến, mở rộng lý thuyết điều phối xe thông minh trong đô thị.

Đóng góp về mặt giải thuật và thực tiễn

  1. Phát triển thuật toán thích ứng A-ALNS: Xây dựng thành công thuật toán A-ALNS kết hợp các toán tử phá hủy và tái tạo đặc thù, giải quyết hiệu quả bài toán phân phối hàng hóa quy mô lớn lên đến 1256 điểm khách hàng tại doanh nghiệp sữa thực tế ở Việt Nam.
  2. Phương pháp phân vùng thích ứng (Adaptive Binning) cho NHPP: Đề xuất phương pháp học không tham số dựa trên dữ liệu giúp khắc phục triệt để hiện tượng quá khớp trong dự báo nhu cầu đặt xe taxi.
  3. Chiến lược điều hướng phương tiện rỗng: Giảm thiểu quãng đường di chuyển không tải của tài xế taxi, nâng cao tỷ lệ phục vụ thành công và tối ưu hóa doanh thu tổng thể của hệ thống chia sẻ chuyến đi.

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

Hạn chế

  • Mô hình MTDLC-VR tĩnh giả định thời gian di chuyển giữa các nút giao thông là hằng số xác định, chưa xét đến biến động vận tốc theo các khung giờ cao điểm trong đô thị.
  • Phương pháp dự báo nhu cầu taxi bằng NHPP trong Chương 3 chủ yếu dựa trên dữ liệu lịch sử không gian - thời gian, chưa tích hợp các yếu tố ngoại cảnh đột xuất như thời tiết cực đoan hoặc sự kiện đặc biệt.
  • Phạm vi giải quyết chính xác bằng MILP qua GUROBI bị giới hạn ở kích thước mẫu nhỏ do độ phức tạp tổ hợp tăng theo hàm mũ.

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

  • Mở rộng mô hình MTDLC-VR sang kịch bản phụ thuộc thời gian (Time-Dependent VRP) nhằm phản ánh chính xác tình trạng tắc nghẽn giao thông thực tế.
  • Tích hợp các mạng nơ-ron sâu (Deep Learning) hoặc mô hình học tăng cường (Reinforcement Learning) vào cơ chế định hướng xe rỗng trực tuyến trong bài toán SARP.
  • Nghiên cứu mô hình phối hợp đồng thời cả đội xe tự hành (autonomous vehicles) và xe truyền thống trong hệ thống giao nhận hành khách - hàng hóa kết hợp.

Giá trị tham khảo

  • Đối với nghiên cứu sinh và nhà nghiên cứu: Luận án cung cấp khung mô hình toán học chi tiết (MILP) cho các bài toán VRP mở rộng phức tạp; tài liệu tham khảo có giá trị về cách thích ứng giải thuật ALNS và phương pháp tích hợp mô hình học máy thống kê vào bài toán tối ưu hóa tổ hợp.
  • Đối với giảng viên và cơ sở đào tạo: Cung cấp tài liệu giảng dạy chuyên sâu cho các học phần Tối ưu hóa tổ hợp, Vận trù học (Operations Research), Trí tuệ nhân tạo và Ứng dụng khoa học máy tính trong logistics.
  • Đối với doanh nghiệp logistics và nhà hoạch định giao thông đô thị: Cung cấp giải pháp công nghệ trực tiếp để giải quyết bài toán phân phối hàng hóa thực tế tại Việt Nam, nâng cao hiệu suất tải của đội xe, giảm chi phí thuê ngoài và tối ưu hóa hệ thống vận hành xe công nghệ chia sẻ chuyến.

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

1. Tại sao ràng buộc chặn dưới tải trọng (lower-bound capacity) lại gây khó khăn cho các thuật toán heuristic kinh điển?

Các thuật toán heuristic kinh điển như Thuật toán Tiết kiệm (Saving Algorithm) hay Chèn tham lam (Greedy Insertion) xây dựng lộ trình bằng cách chèn từng khách hàng tuần tự. Khi bắt đầu chèn khách hàng đầu tiên, tải trọng trên xe lớn hơn 0 nhưng nhỏ hơn mức chặn dưới, khiến trạng thái trung gian luôn vi phạm ràng buộc khả thi. Do đó, các giải thuật này không thể đánh giá đúng chất lượng nghiệm nếu không có thủ tục gom nhóm hoặc chuyển đổi điểm (node transfer) bổ trợ.

2. Mô hình MTDLC-VR trong Chương 2 phân biệt xe nội bộ và xe thuê ngoài như thế nào trong hàm mục tiêu?

Mô hình sử dụng hệ số ưu tiên $f_k$ gán cho từng phương tiện $k \in K$. Do chi phí vận hành xe nội bộ thấp hơn chi phí thuê ngoài từ đơn vị thứ ba, tác giả thiết lập trọng số $f_k < f_{k'}$ (trong đó $k$ là xe nội bộ, $k'$ là xe thuê ngoài). Khi cực tiểu hóa thành phần $g_v = \sum f_k z^{k,1}$, mô hình ưu tiên sử dụng tối đa năng lực của đội xe nội bộ trước khi điều động xe thuê ngoài.

3. Phương pháp phân vùng thích ứng (Adaptive Binning Method) trong Chương 3 giải quyết nhược điểm gì của mô hình hồi quy đa thức?

Mô hình hồi quy đa thức từng đoạn truyền thống khi áp dụng trên dữ liệu đặt xe taxi thường gặp hiện tượng quá khớp (overfitting) tại các khoảng thời gian có lượng dữ liệu thưa thớt hoặc biến động mạnh. Phương pháp Adaptive Binning chia nhỏ miền dữ liệu thành các khoảng không gian - thời gian thích ứng dựa trên kiểm định thống kê Kolmogorov-Smirnov, 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) mà không bị phụ thuộc vào bậc đa thức cố định.

4. Dữ liệu thực nghiệm của luận án được thu thập từ những nguồn nào?

Luận án sử dụng hai nguồn dữ liệu chính:

  • Dữ liệu vận hành phân phối sữa thực tế tại Việt Nam với các bài toán quy mô từ nhỏ đến lớn (lên tới 1256 khách hàng, 4 kho hàng, 2 bãi đỗ xe).
  • Dữ liệu hành trình và yêu cầu đặt xe taxi công khai tại thành phố San Francisco (Mỹ) để kiểm thử mô hình điều phối động.

Kết luận

Luận án tiến sĩ của tác giả Nguyễn Văn Sơn đã giải quyết toàn diện hai bài toán cốt lõi trong vận tải hiện đại: bài toán định tuyến phân phối hàng hóa tĩnh với ràng buộc chặn dưới tải trọng (MTDLC-VR) và bài toán điều phối taxi chia sẻ chuyến động tích hợp thông tin dự báo (SARP). Bằng việc kết hợp chặt chẽ giữa mô hình hóa toán học chính xác (MILP), các giải thuật metaheuristic thích ứng (A-ALNS) và phương pháp học máy thống kê (NHPP Adaptive Binning), công trình đã đóng góp cả về mặt học thuật tối ưu hóa lẫn hiệu quả ứng dụng thực tiễn trong ngành logistics. Các kết quả thực nghiệm trên dữ liệu doanh nghiệp Việt Nam và dữ liệu giao thông quốc tế khẳng định tính đúng đắn, khả thi và giá trị ứng dụng cao của các phương pháp được đề xuất trong luận án.