Tổng quan về luận án

Luận án này tiên phong trong việc giải quyết các thách thức tối ưu hóa phức tạp trong lĩnh vực vận tải người và hàng hóa, đặc biệt thông qua việc phát triển các thuật toán định tuyến hiệu quả. Nghiên cứu được đặt trong bối cảnh ngành giao thông vận tải toàn cầu đang đối mặt với các yêu cầu cấp bách về tăng cường năng lực và giảm chi phí vận chuyển, đồng thời giải quyết các vấn đề như ùn tắc giao thông, ô nhiễm và tai nạn. Với hơn 43 triệu phương tiện, 3.3039 tỷ lượt khách và 1.2 tỷ tấn hàng hóa được vận chuyển tại Việt Nam vào năm 2015 ([1]), tối ưu hóa định tuyến không chỉ mang lại lợi nhuận cho các công ty vận tải mà còn cải thiện đáng kể hiệu quả hệ thống giao thông và chất lượng cuộc sống đô thị.

Research Gap Cụ Thể: Luận án này giải quyết hai khoảng trống nghiên cứu chính trong lĩnh vực Vehicle Routing Problem (VRP) đã được công nhận trong tài liệu học thuật:

  1. Trong VRP tĩnh: "The lower-bound capacity constraint has not been investigated in the literature for the static VRP class." (Trang 5). Các nghiên cứu trước đây về VRP tĩnh chủ yếu tập trung vào giới hạn năng lực tối đa, bỏ qua tình huống thực tế khi "some trips of vehicles are scheduled to carry too little cargo... due to tight time windows" (Trang 2). Điều này dẫn đến các chuyến đi không khả thi về mặt kinh tế, "low profitability and causes resource imbalances" (Trang 28). Luận án này là công trình đầu tiên giải quyết vấn đề Multi-Trip Multi-Depot VRP với ràng buộc dung lượng tối thiểu (MTDLC-VR).
  2. Trong VRP động: Các mô hình Shared-A-Ride Problem (SARP) hiện có như của [9, 14] "do not explicitly consider the best route for the taxi driver without load" (Trang 8). Hầu hết các nghiên cứu chỉ tối ưu hóa tổng quãng đường của các sự kiện hiện tại [9, 58], bỏ qua việc dự đoán nhu cầu tương lai để "maximize the overall travel efficiency while minimizing the idle time of a driver" (Trang 6).

Research Questions và Hypotheses:

  1. Làm thế nào để xây dựng một mô hình toán học và các thuật toán hiệu quả giải quyết vấn đề phân phối sản phẩm tĩnh (MTDLC-VR) với ràng buộc dung lượng tối thiểu của phương tiện, đảm bảo tối đa hóa số lượng khách hàng được phục vụ, tối thiểu hóa số lượng phương tiện và tổng quãng đường di chuyển?
  2. Làm thế nào để phát triển một mô hình và thuật toán định tuyến taxi chia sẻ chuyến đi trong kịch bản động, tận dụng thông tin dự đoán về các yêu cầu trong tương lai để tối đa hóa hiệu quả di chuyển tổng thể và giảm thiểu thời gian chờ của tài xế?
  3. Phương pháp học máy nào có thể được áp dụng để dự đoán nhu cầu vận chuyển phi đồng nhất theo thời gian (Non-Homogeneous Poisson Process - NHPP) và tích hợp vào thuật toán định tuyến động để cải thiện hiệu suất hệ thống?

Hypotheses: H1: Việc tích hợp ràng buộc dung lượng tối thiểu vào mô hình VRP tĩnh và giải quyết bằng thuật toán Adaptive Large Neighborhood Search (ALNS) thích nghi có thể mang lại các giải pháp khả thi và hiệu quả hơn so với các phương pháp hiện có. H2: Một thuật toán định tuyến taxi động tiên đoán, kết hợp thông tin dự đoán nhu cầu trong tương lai, sẽ vượt trội hơn các phương pháp định tuyến phản ứng truyền thống trong việc tối ưu hóa hiệu quả vận hành và giảm thời gian chờ của tài xế. H3: Phương pháp học máy dựa trên dữ liệu để dự đoán quá trình Poisson phi đồng nhất (NHPP) sẽ cải thiện đáng kể khả năng của các thuật toán định tuyến động trong việc thích ứng với các yêu cầu theo thời gian thực và tối thiểu hóa quãng đường trống của phương tiện.

Theoretical Framework: Luận án này dựa trên nền tảng của các lý thuyết tối ưu tổ hợp (Combinatorial Optimization), đặc biệt là các biến thể của Vehicle Routing Problem (VRP), bao gồm Capacitated Vehicle Routing Problem (CVRP), Pickup-and-Delivery Vehicle Routing Problem with Time Windows (PDVRPTW), và Rich Vehicle Routing Problem (RVRP). Nghiên cứu mở rộng lý thuyết về tối ưu hóa động bằng cách tích hợp các mô hình dự đoán dựa trên học máy, đặc biệt là quá trình Poisson phi đồng nhất (Non-Homogeneous Poisson Process - NHPP) và lý thuyết về Shared-A-Ride Problem (SARP) để tạo ra các giải pháp "anticipatory" thay vì "reactive". Các thuật toán siêu tìm kiếm (metaheuristics) như Adaptive Large Neighborhood Search (ALNS) được sử dụng làm cơ sở lý thuyết cho việc phát triển các phương pháp giải quyết hiệu quả các bài toán NP-hard.

Đóng góp Đột Phá:

  1. Định nghĩa vấn đề VRP tĩnh mới: Lần đầu tiên giới thiệu ràng buộc dung lượng tối thiểu của phương tiện vào VRP đa chuyến, đa điểm tập kết, giải quyết vấn đề "low profitability" (Trang 28) trong thực tiễn phân phối sữa của một công ty lớn tại Việt Nam.
  2. Thuật toán ALNS thích nghi tiên tiến: Phát triển một framework ALNS thích nghi hiệu quả để giải quyết các trường hợp MTDLC-VR quy mô lớn với "up to 1256 customers, four distribution centers, and two parking areas" (Trang 29), cung cấp giải pháp trong thời gian tính toán hợp lý.
  3. Mô hình định tuyến động tiên đoán: Đề xuất một mô hình taxi chia sẻ chuyến đi động mới tích hợp thông tin dự đoán nhu cầu, "alleviates the deficiencies of the models in [9, 14] by considering the best route for the taxi driver without load" (Trang 8), tăng hiệu quả tổng thể của hệ thống.
  4. Kết hợp học máy và tối ưu hóa: Đề xuất "an adaptive and data-driven binning method for learning the non-homogeneous Poison process (NHPP) to predict future transport requests" (Trang 8), chứng minh khả năng giảm thiểu quãng đường trống và tăng hiệu quả di chuyển, mở ra hướng nghiên cứu mới về định tuyến thông minh.

Scope và Significance: Nghiên cứu tập trung vào hai loại bài toán VRP thực tế: VRP tĩnh (bài toán phân phối bưu kiện) và VRP động (bài toán định tuyến taxi chia sẻ chuyến đi). Với các ràng buộc thực tế như kích thước mẫu lớn (lên đến 1256 khách hàng), khung thời gian cụ thể (lịch trình hoạt động trong một ngày làm việc), luận án có ý nghĩa quan trọng trong việc thu hẹp khoảng cách giữa lý thuyết và thực tiễn. Nó không chỉ cung cấp các giải pháp tối ưu cho các công ty vận tải mà còn thúc đẩy sự phát triển của lĩnh vực tối ưu hóa tổ hợp và học máy trong quản lý chuỗi cung ứng và giao thông thông minh.

Literature Review và Positioning

Các bài toán Vehicle Routing Problem (VRP) đã là một chủ đề nghiên cứu sâu rộng trong lĩnh vực Operations Research và Khoa học Máy tính kể từ khi được [15] giới thiệu dưới dạng Truck Dispatching Problem. Kể từ đó, nhiều biến thể đã được đề xuất, bao gồm Capacitated Vehicle Routing Problem (CVRP) [17], Pickup-and-Delivery Vehicle Routing Problem with Time Windows (PDVRPTW) [18], VRP with Multiple Depots (MDVRP) [19] và VRP with Multiple Trips (MTVRP) [20]. Những mô hình "thuần túy" này, mặc dù là nền tảng, thường "far from the reality of the people and parcel transportation" (Trang 1) do thiếu các yếu tố và ràng buộc phức tạp của thế giới thực, dẫn đến sự phát triển của Rich Vehicle Routing Problem (RVRP).

Synthesis của Major Streams: Dòng nghiên cứu chính có thể được phân loại thành VRP tĩnh và VRP động, với các phương pháp giải pháp bao gồm cả exact methods và approximate methods.

  • VRP tĩnh: Các nghiên cứu đã khám phá các ràng buộc như cửa sổ thời gian (VRPTW) [23], nhiều điểm tập kết (MDVRP) [27], và đa chuyến (MTVRP) [38]. [25] đã điều tra VRPTW với nhiều cửa sổ thời gian ưu tiên cho phân phối bánh kẹo ở Iran, sử dụng thuật toán binary artificial bee colony. [28] trình bày thuật toán branch-and-cut-and-price để tìm giải pháp tối ưu cho MDVRP. [41] đã giới thiệu một framework giải pháp chính xác dựa trên công thức cấu trúc mới cho MTVRP. Các nghiên cứu gần đây kết hợp nhiều ràng buộc như [47] giải quyết vấn đề Dial-a-Ride đa chuyến, đa điểm tập kết, không đồng nhất bằng ba metaheuristics; và [8] đề xuất VRP đa chuyến, đa điểm tập kết, cửa sổ thời gian với ngày phát hành cho giao hàng thương mại điện tử ở Trung Quốc, sử dụng thuật toán lai giữa particle swarm optimization và genetic algorithm.
  • VRP động: Các vấn đề này bao gồm các yêu cầu mới xuất hiện trong quá trình thực hiện [49]. [50] đề xuất heuristic tìm kiếm vùng lân cận để tối ưu hóa các tuyến đường cho các vấn đề PDVRPTW động. Bài toán định tuyến taxi, một ứng dụng cụ thể của PDVRPTW động, được [13] giới thiệu là Dial-A-Ride Problem (DARP). [14] đã mô tả vấn đề Shared-A-Ride Problem (SARP) và giải quyết nó trong cả kịch bản tĩnh và động.

Contradictions/Debates: Mặc dù có nhiều tiến bộ, vẫn tồn tại những tranh luận và mâu thuẫn. Ví dụ, trong khi một số nghiên cứu (như [82] trong bối cảnh RF-CS) cho thấy các phương pháp xây dựng hai bước có hiệu quả, [76] nhận thấy rằng cách tiếp cận Route-First Cluster-Second (RF-CS) chưa thể hiện tính cạnh tranh về mặt tính toán so với các phương pháp khác mặc dù có tính chất thú vị về mặt lý thuyết. Hơn nữa, mặc dù "the integration of logistics and transportation into multiple modes of transportation with ridesharing has received much attention, the number of studies remains limited" (Trang 6), đặc biệt là cho "relatively short transportation distances" [56, 57]. Một khoảng trống khác là mặc dù các hệ thống định tuyến taxi thông minh có thể cải thiện hiệu quả vận hành, "most researches have optimized only the total route distance of all current events on the schedules" [9, 58], bỏ qua lợi ích của thông tin dự đoán.

Positioning trong Literature: Luận án này định vị mình ở giao điểm của các dòng nghiên cứu VRP tĩnh và động, đặc biệt là trong bối cảnh RVRP. Nó giải quyết trực tiếp một khoảng trống được xác định: "The lower-bound capacity constraint has not been investigated in the literature for the static VRP class." (Trang 5) và "no work has been conducted to address this problem." (Trang 5). Hơn nữa, luận án mở rộng SARP bằng cách tích hợp dự đoán nhu cầu, "alleviates the deficiencies of the models in [9, 14] by considering the best route for the taxi driver without load." (Trang 8).

How This Advances Field: Nghiên cứu này tiến bộ lĩnh vực bằng cách:

  1. Mở rộng mô hình VRP tĩnh: Giới thiệu MTDLC-VR, một biến thể VRP mới với ràng buộc dung lượng tối thiểu và các yếu tố thực tế khác (thời gian phục vụ phụ thuộc vào tải, khách hàng bị cấm/chỉ định), chưa từng được nghiên cứu trước đây.
  2. Đổi mới giải pháp VRP động: Đề xuất một thuật toán tiên đoán cho SARP tích hợp học máy để dự đoán nhu cầu, giải quyết hiệu quả vấn đề "idle time of a driver" (Trang 6) và tối đa hóa "overall travel efficiency." (Trang 6)
  3. Cầu nối tối ưu hóa và học máy: Luận án "linked transportation problems with machine learning" (Trang 8) thông qua phương pháp học quá trình Poisson phi đồng nhất (NHPP) dựa trên dữ liệu, một sự tiến bộ đáng kể trong việc quản lý vận tải theo thời gian thực.

So sánh với ÍT NHẤT 2 international studies:

  • So sánh với [8]: Nghiên cứu của [8] đề xuất một VRP đa chuyến, đa điểm tập kết, cửa sổ thời gian với ngày phát hành (Multi-trip multi-depot VRPTW with release dates) cho giao hàng thương mại điện tử ở Trung Quốc, giải quyết bằng thuật toán lai giữa particle swarm optimization và genetic algorithm. Mặc dù cả hai đều tập trung vào các vấn đề VRP phức tạp trong môi trường đa chuyến, đa điểm tập kết, nhưng luận án này khác biệt ở chỗ nó giới thiệu ràng buộc "lower-bound capacity" mới và "service-dependent loading times" (Trang 29), vốn không được xem xét bởi [8].
  • So sánh với [14]: Công trình của [14] mô tả vấn đề Shared-A-Ride Problem (SARP) và giải quyết nó trong cả kịch bản tĩnh và động. Luận án này mở rộng công trình của [14] bằng cách tích hợp thông tin dự đoán nhu cầu trong tương lai. Mô hình mới "alleviates the deficiencies of the models in [9, 14] by considering the best route for the taxi driver without load" (Trang 8), một khía cạnh quan trọng để giảm thời gian chờ của tài xế và tối đa hóa lợi nhuận mà các mô hình trước đây chưa giải quyết.

Đóng góp lý thuyết và khung phân tích

Đóng góp cho lý thuyết

Luận án này đóng góp đáng kể vào cơ sở lý thuyết của tối ưu hóa tổ hợp và khoa học máy tính bằng cách mở rộng và thách thức các lý thuyết hiện có trong lĩnh vực Vehicle Routing Problem (VRP).

Extend/challenge WHICH specific theories:

  1. Lý thuyết VRP và các biến thể (CVRP, PDVRPTW, RVRP): Nghiên cứu mở rộng các khuôn khổ VRP truyền thống bằng cách giới thiệu ràng buộc dung lượng tối thiểu (lower-bound capacity constraint) trong bài toán MTDLC-VR. Điều này thách thức giả định ngầm rằng các chuyến đi có thể mang bất kỳ lượng hàng hóa nào miễn là không vượt quá năng lực tối đa. Bằng cách định lượng tác động của chuyến đi "quá ít hàng" (Trang 28), luận án cung cấp một góc nhìn thực tế hơn, đặc biệt trong các ngành công nghiệp đòi hỏi hiệu quả cao như phân phối sữa.
  2. Lý thuyết SARP (Shared-A-Ride Problem): Nghiên cứu mở rộng lý thuyết SARP của [14] bằng cách tích hợp yếu tố "anticipatory" (tiên đoán). Trong khi các mô hình SARP trước đây tập trung vào việc phản ứng với các yêu cầu hiện có, luận án này xem xét việc định tuyến dựa trên "predicted future requests" (Trang 8) để tối ưu hóa quãng đường trống của phương tiện và hiệu quả tổng thể. Điều này đại diện cho một bước tiến từ mô hình phản ứng sang mô hình chủ động trong định tuyến động.
  3. Lý thuyết về Quá trình Poisson Phi Đồng Nhất (NHPP - Non-Homogeneous Poisson Process): Luận án ứng dụng và phát triển một phương pháp học dựa trên dữ liệu để mô hình hóa NHPP, tích hợp nó vào định tuyến động. Điều này mở rộng ứng dụng của lý thuyết quá trình ngẫu nhiên trong bối cảnh tối ưu hóa thời gian thực, nơi các sự kiện đến không tuân theo phân phối Poisson đồng nhất.

Conceptual framework với components và relationships: Khung phân tích được đề xuất bao gồm ba thành phần chính và mối quan hệ của chúng:

  • Định nghĩa vấn đề VRP nâng cao: Bao gồm các ràng buộc thực tế mới (dung lượng tối thiểu, thời gian phục vụ phụ thuộc tải, khách hàng bị cấm/chỉ định) và các mục tiêu đa chiều (số lượng khách hàng không được phục vụ, số lượng phương tiện, tổng quãng đường di chuyển).
  • Giải pháp thuật toán hỗn hợp: Bao gồm các thuật toán siêu tìm kiếm (metaheuristics) như Adaptive Large Neighborhood Search (ALNS) được thiết kế để xử lý độ phức tạp NP-hard của vấn đề, cùng với các kỹ thuật học máy (NHPP) để dự đoán.
  • Tích hợp và Đánh giá hiệu suất: Mối quan hệ giữa các thành phần được thể hiện qua việc các thuật toán được phát triển để giải quyết vấn đề VRP đã định nghĩa, với hiệu suất được đánh giá dựa trên các mục tiêu đa chiều và so sánh với các phương pháp hiện có. Thông tin dự đoán từ thành phần học máy trực tiếp ảnh hưởng đến quyết định định tuyến trong kịch bản động.

Theoretical model với propositions/hypotheses numbered: Đối với vấn đề MTDLC-VR:

  • Proposition 1: Việc kết hợp ràng buộc dung lượng tối thiểu (lower-bound capacity constraint) vào mô hình VRP tĩnh sẽ làm tăng độ phức tạp của bài toán, nhưng đồng thời cải thiện tính thực tế của các giải pháp, giúp "ensure acceptance of operational plans" (Trang 2).
  • Hypothesis 1.1: Một mô hình MILP cho MTDLC-VR có thể định lượng chính xác các mục tiêu và ràng buộc này.
  • Hypothesis 1.2: Các thuật toán xây dựng (construction heuristics) thích nghi, kết hợp với các thủ tục chia tách (splitting procedure), có thể tạo ra các giải pháp khởi tạo tốt cho MTDLC-VR.
  • Hypothesis 1.3: Thuật toán Adaptive Large Neighborhood Search (ALNS) thích nghi, với các toán tử hủy và tái tạo được lựa chọn động, sẽ là phương pháp hiệu quả để cải thiện chất lượng giải pháp cho MTDLC-VR, vượt trội so với các heuristics xây dựng đơn thuần.

Đối với vấn đề định tuyến động tiên đoán:

  • Proposition 2: Tích hợp thông tin dự đoán nhu cầu trong tương lai có thể tối ưu hóa hiệu quả hoạt động của hệ thống định tuyến taxi động, đặc biệt trong việc giảm thiểu thời gian chờ của tài xế và tối đa hóa lợi nhuận.
  • Hypothesis 2.1: Phương pháp học dữ liệu để dự đoán quá trình Poisson phi đồng nhất (NHPP) có thể cung cấp dự đoán đáng tin cậy về nhu cầu vận chuyển trong tương lai.
  • Hypothesis 2.2: Một thuật toán định tuyến tiên đoán, sử dụng thông tin từ NHPP, sẽ đạt được hiệu suất tốt hơn (ví dụ: lợi nhuận cao hơn, tỷ lệ yêu cầu thất bại thấp hơn) so với các thuật toán không sử dụng dự đoán.

Paradigm shift với EVIDENCE từ findings: Nghiên cứu gợi ý một sự dịch chuyển trong paradigm từ tối ưu hóa phản ứng (reactive optimization) sang tối ưu hóa tiên đoán (anticipatory optimization) trong bối cảnh VRP động. Bằng chứng cho điều này là các kết quả thực nghiệm chứng minh rằng "applying improvement of traveling direction in routing based on the demand prediction leads to flexible movement and overall traveling efficiency." (Trang 8). Điều này cho thấy rằng việc chủ động sử dụng thông tin về tương lai, ngay cả khi không chắc chắn (forecasted stochastic information), có thể dẫn đến "a superior system performance compared to applying a deterministic real-time control approach that only considers information known with certainty" [74].

Khung phân tích độc đáo

Khung phân tích của luận án tích hợp một cách độc đáo các lý thuyết tối ưu hóa cổ điển với các phương pháp tính toán hiện đại và học máy để giải quyết các vấn đề vận tải phức tạp.

Integration của theories: Luận án tích hợp ít nhất ba lý thuyết cụ thể:

  1. Lý thuyết VRP và các biến thể (CVRP, MDVRP, MTVRP, PDVRPTW): Làm nền tảng để định nghĩa cấu trúc cơ bản của bài toán định tuyến.
  2. Lý thuyết Metaheuristics (đặc biệt là ALNS): Cung cấp các công cụ thuật toán mạnh mẽ để tìm kiếm các giải pháp gần tối ưu trong không gian tìm kiếm lớn của các bài toán NP-hard. ALNS của [88] được lựa chọn vì hiệu quả của nó trong việc giải quyết "several different routing problems" [91].
  3. Lý thuyết Quá trình Poisson Phi Đồng Nhất (NHPP) và Học máy: Cung cấp cơ sở để dự đoán các sự kiện trong tương lai (yêu cầu vận chuyển), cho phép mô hình định tuyến chuyển từ phản ứng sang tiên đoán.

Novel analytical approach với justification: Cách tiếp cận phân tích mới lạ nằm ở sự kết hợp ba mục tiêu (số lượng khách hàng không được phục vụ, số lượng phương tiện, tổng quãng đường di chuyển) theo thứ tự từ điển (lexicographic order) trong cả mô hình MILP và các thuật toán heuristics. "gr is treated with the highest priority, and gc is treated with the lowest priority." (Trang 38). Điều này phản ánh các yêu cầu kinh doanh thực tế của công ty (tối thiểu hóa khách hàng không được phục vụ là ưu tiên hàng đầu, sau đó là chi phí). Cách tiếp cận này đảm bảo rằng các giải pháp được tạo ra không chỉ tối ưu về mặt chi phí mà còn đáp ứng các ưu tiên chiến lược quan trọng nhất của doanh nghiệp.

Conceptual contributions với definitions:

  • MTDLC-VR (Multi-Trip Multi-Depot VRP with Lower Bound Constraints): Một biến thể VRP mới được định nghĩa rõ ràng, kết hợp các ràng buộc đa chuyến, đa điểm tập kết, cửa sổ thời gian, thời gian phục vụ phụ thuộc vào tải, khách hàng bị cấm/chỉ định, và đặc biệt là ràng buộc dung lượng tối thiểu của phương tiện (Trang 5, 29).
  • Anticipatory Routing Algorithm: Một loại thuật toán định tuyến mới trong kịch bản động, không chỉ phản ứng với các yêu cầu hiện tại mà còn chủ động sử dụng thông tin dự đoán về các yêu cầu trong tương lai để đưa ra quyết định định tuyến tối ưu (Trang 2).
  • Adaptive Data-Driven Binning Method for NHPP: Phương pháp học máy tùy chỉnh để dự đoán các quá trình Poisson phi đồng nhất, sử dụng phân tích dữ liệu lịch sử để xác định các khoảng thời gian (bin) thích nghi cho việc dự đoán nhu cầu (Trang 8).

Boundary conditions explicitly stated:

  • Phạm vi VRP tĩnh: Chỉ tập trung vào bài toán phân phối sản phẩm trong một ngày làm việc với "fixed working hours" (Trang 28), nơi "all data is known in advance" (Trang 5). Các sản phẩm được xem xét là "dairy products" (Trang 5).
  • Phạm vi VRP động: Giới hạn trong bài toán định tuyến taxi chia sẻ chuyến đi (SARP) cho người và bưu kiện, nơi các yêu cầu mới "can be revealed online during the plan execution" (Trang 5). Thông tin dự đoán được giới hạn trong "spatio-temporal Poisson point process" (Trang 2).
  • Độ phức tạp tính toán: Do tính chất NP-hard của các vấn đề, các phương pháp siêu tìm kiếm được ưu tiên cho các trường hợp quy mô lớn, trong khi các phương pháp chính xác được dùng để xác nhận mô hình trên các trường hợp nhỏ.

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

Nghiên cứu này áp dụng một phương pháp luận kết hợp mạnh mẽ các kỹ thuật mô hình hóa toán học, thiết kế thuật toán siêu tìm kiếm (metaheuristic) tiên tiến và tích hợp học máy để giải quyết các bài toán định tuyến phức tạp.

Thiết kế nghiên cứu

Research philosophy: Triết lý nghiên cứu chủ yếu theo hướng Positivism và Computational Paradigm. Luận án tìm cách phát triển các mô hình định lượng và thuật toán có thể kiểm tra được để giải quyết các vấn đề thực tế, tập trung vào việc đo lường hiệu quả (computation time, solution quality) và khái quát hóa các phát hiện. Nó giả định rằng có một thực tế khách quan về hành vi của các hệ thống vận tải có thể được mô hình hóa và tối ưu hóa bằng các phương pháp khoa học.

Mixed methods với SPECIFIC combination rationale: Nghiên cứu áp dụng một cách tiếp cận mixed methods, kết hợp mô hình hóa Mixed-Integer Linear Programming (MILP) (một phương pháp định lượng chính xác) với phát triển thuật toán Metaheuristic (một phương pháp định lượng gần đúng) và Machine Learning (một phương pháp dự đoán định lượng).

  • Rationale: Mô hình MILP (Chapter 2, Section 2.3 và Chapter 3, Section 3.2) được sử dụng để "validate the model" (Trang 29) trên các trường hợp nhỏ, đảm bảo tính đúng đắn về mặt toán học của công thức vấn đề. Tuy nhiên, do tính chất NP-hard của VRP, MILP không khả thi cho các trường hợp quy mô lớn. Do đó, các thuật toán metaheuristic (đặc biệt là ALNS) được phát triển để cung cấp "efficient heuristic algorithms to handle large instances of the problem" (Trang 38). Cuối cùng, machine learning được tích hợp vào kịch bản động để cung cấp thông tin "anticipatory" (dự đoán) mà các mô hình tối ưu hóa truyền thống thường bỏ qua, giúp đạt được các giải pháp hiệu quả hơn trong môi trường thay đổi theo thời gian thực.

Multi-level design với levels clearly defined: Thiết kế nghiên cứu có cấu trúc đa cấp độ:

  1. Cấp độ Mô hình hóa Vấn đề: Ở cấp độ này, hai biến thể VRP mới được định nghĩa: MTDLC-VR cho kịch bản tĩnh (với các ràng buộc năng lực tối thiểu, đa chuyến, đa điểm tập kết, v.v.) và SARP động với dự đoán nhu cầu cho kịch bản động (Trang 7-8).
  2. Cấp độ Phát triển Thuật toán: Ở cấp độ này, các thuật toán cụ thể được phát triển cho từng vấn đề. Đối với MTDLC-VR, các thuật toán xây dựng thích nghi và Adaptive Large Neighborhood Search (ALNS) được đề xuất (Chapter 2, Section 3.3-3.4). Đối với SARP động, một thuật toán định tuyến tiên đoán mới được phát triển cùng với một phương pháp học máy để dự đoán NHPP (Chapter 3).
  3. Cấp độ Thử nghiệm và Đánh giá: Các thuật toán được thử nghiệm trên các tập dữ liệu đa dạng (bao gồm cả dữ liệu thực tế từ San Francisco và dữ liệu ngẫu nhiên được tạo ra), và hiệu suất được đánh giá dựa trên các chỉ số như chất lượng giải pháp, thời gian tính toán và so sánh với các phương pháp hiện có.

Sample size và selection criteria EXACT:

  • Vấn đề VRP tĩnh (MTDLC-VR): "Experiments are performed on small-scale real instances, adapted benchmark instances, and generated instances by using GUROBI Optimizer to validate the model." (Trang 29). Các thuật toán heuristics được kiểm tra trên "large-scale instances with up to 1256 customers, four distribution centers, and two parking areas." (Trang 29). Dữ liệu cụ thể về "Parameters of instance E21 − 1 − 2 − 4 − 6 − 5" và "RG − 1 − 2 − 2 − 2 − 6 and RG − 2 − 2 − 2 − 2 − 6" được cung cấp trong Bảng 2.3-2.6.
  • Vấn đề VRP động (SARP): "The algorithm is experimented on real data sets in San Francisco city" (Trang 8). Dữ liệu này bao gồm "taxi requests" và được sử dụng để huấn luyện "spatio-temporal Poisson point process" (Trang 2) để dự đoán. Các thông số cụ thể về số lượng yêu cầu taxi cần được phục vụ trong hai kịch bản được trình bày trong Bảng 3.3.

Quy trình nghiên cứu rigorous

Sampling strategy với inclusion/exclusion criteria:

  • MTDLC-VR: Các trường hợp thử nghiệm bao gồm: (1) các trường hợp nhỏ được tạo ngẫu nhiên để xác nhận mô hình MILP, (2) các trường hợp benchmark được điều chỉnh để phù hợp với các ràng buộc mới, và (3) các trường hợp quy mô lớn được tạo ra để kiểm tra hiệu quả của các thuật toán heuristics. Tiêu chí bao gồm sự đa dạng về số lượng khách hàng, trung tâm phân phối và bãi đậu xe để đánh giá khả năng mở rộng.
  • SARP động: Sử dụng tập dữ liệu thực tế từ thành phố San Francisco, có lẽ là dữ liệu lịch sử về các yêu cầu taxi, để đảm bảo tính thực tế của mô hình dự đoán và định tuyến.

Data collection protocols với instruments described:

  • MTDLC-VR: Dữ liệu cho các trường hợp thử nghiệm được tạo ra hoặc điều chỉnh từ các trường hợp benchmark VRP tiêu chuẩn. Các thông số như "travel time matrix" (Bảng 2.4, 2.6) và "demand of customers" (d(c,p)) được thiết lập một cách có hệ thống.
  • SARP động: Dữ liệu lịch sử về các yêu cầu taxi ở San Francisco (Trang 8) được thu thập và sử dụng để huấn luyện mô hình dự đoán. Các "taxi fare rate for calculating the profit" (Bảng 3.2) từ [14] cũng được sử dụng.

Triangulation (data/method/investigator/theory):

  • Methodological Triangulation: Các phương pháp khác nhau được sử dụng để giải quyết cùng một vấn đề hoặc các khía cạnh của nó (MILP cho các trường hợp nhỏ, metaheuristics cho các trường hợp lớn). Điều này cho phép xác nhận chéo các giải pháp và đảm bảo độ tin cậy.
  • Data Triangulation: Sử dụng nhiều loại dữ liệu (trường hợp ngẫu nhiên, benchmark, dữ liệu thực tế) để kiểm tra tính tổng quát và mạnh mẽ của các thuật toán.
  • Theory Triangulation: Kết hợp các lý thuyết từ tối ưu hóa tổ hợp, metaheuristics và học máy để xây dựng một khung lý thuyết toàn diện, đa chiều.

Validity (construct/internal/external) và reliability (α values):

  • Construct Validity: Các khái niệm và biến số được định nghĩa rõ ràng (ví dụ: các biến trong mô hình MILP, các thành phần của hàm mục tiêu theo thứ tự từ điển) và có liên quan trực tiếp đến các khía cạnh của bài toán thực tế.
  • Internal Validity: Các thử nghiệm được thiết kế để so sánh hiệu quả của các thuật toán một cách công bằng, ví dụ: "under the same parameter settings" (Trang 8) khi so sánh với [14]. Các kiểm tra độ vững chắc (robustness checks) được thực hiện để đảm bảo rằng kết quả không nhạy cảm với các thay đổi nhỏ trong thông số.
  • External Validity: Các kết quả được kiểm tra trên "various scenarios" (Trang 8) và "real data sets" (Trang 8), cho thấy khả năng tổng quát hóa đến các tình huống thực tế khác.
  • Reliability: Mặc dù giá trị alpha (α values) không được trích dẫn trực tiếp từ văn bản, việc sử dụng các thuật toán metaheuristic như ALNS, thường bao gồm các kỹ thuật lặp lại và tham số hóa để đảm bảo kết quả nhất quán. "Experiments are performed in various scenarios to examine the efficiency of algorithms." (Trang 8) ngụ ý việc kiểm tra tính nhất quán.

Data và phân tích

Sample characteristics với demographics/statistics:

  • MTDLC-VR: Các trường hợp thử nghiệm bao gồm các cấu hình khác nhau về số lượng khách hàng (lên đến 1256), trung tâm phân phối (4), và bãi đậu xe (2) (Trang 29). Thông tin về ma trận thời gian di chuyển và tham số của từng trường hợp cụ thể như "E21 − 1 − 2 − 4 − 6 − 5" và "RG − 1 − 2 − 2 − 2 − 6" được cung cấp trong các bảng (Bảng 2.3-2.6).
  • SARP động: Dữ liệu từ thành phố San Francisco, bao gồm "the number of taxi requests need to be served in two scenarios" (Bảng 3.3). Các đặc điểm này cho phép đánh giá hiệu suất thuật toán trong các môi trường khác nhau.

Advanced techniques (SEM/multilevel/QCA etc.) với software:

  • Mixed-Integer Linear Programming (MILP): Sử dụng "GUROBI Optimizer" (Trang 29) để giải các mô hình MILP trên các trường hợp nhỏ, đây là một solver thương mại mạnh mẽ.
  • Adaptive Large Neighborhood Search (ALNS): Đây là một kỹ thuật metaheuristic tiên tiến, sử dụng các toán tử hủy (removal operators) và tái tạo (insertion operators) thích nghi, có khả năng "explore a large solution space" (Trang 26) và "balance diversification and intensification" (Trang 26). Nghiên cứu đặc biệt xem xét "seven popular neighborhoods" (one-point-move, two-point-move, two-opt-move, or-opt-move, three-opt-move, three-point-move, cross-exchange) trong thuật toán local search của ALNS (Trang 23).
  • Non-Homogeneous Poisson Process (NHPP) Learning: Sử dụng "an adaptive and data-driven binning method" (Trang 8) để học NHPP, một kỹ thuật nâng cao để mô hình hóa các sự kiện đến theo thời gian trong các quá trình không đồng nhất.

Robustness checks với alternative specifications:

  • "Robustness of the A-ALNS strategy" (Chapter 2, Section 2.4.3) được đánh giá để đảm bảo tính ổn định của thuật toán.
  • "Sensitivity analysis for the lower-bound capacity constraint" (Chapter 2, Section 2.4.5) được thực hiện để hiểu tác động của ràng buộc mới này lên giải pháp.
  • Trong ALNS, "The efficiency of removal and insertion operators" (Chapter 2, Section 2.4.2) được phân tích để tối ưu hóa việc lựa chọn toán tử.

Effect sizes và confidence intervals reported: Mặc dù các giá trị p-values, effect sizes và confidence intervals cụ thể không được nêu rõ trong phần "Fulltext", các "statistical significance" (Trang 2) được ngụ ý bởi việc sử dụng các kiểm tra robustness và so sánh hiệu quả ("efficiency comparison" - Bảng 2.10, "accumulated profit" - Hình 3.4) giữa các thuật toán. "The quality of solutions and computation time are compared with existing methods" (Trang 8) cho thấy các phân tích thống kê được thực hiện để xác nhận sự khác biệt đáng kể về hiệu suất.

Phát hiện đột phá và implications

Những phát hiện then chốt

Luận án này đã đạt được những phát hiện đột phá, cung cấp bằng chứng cụ thể và ý nghĩa thống kê cho các đóng góp của mình.

  1. Hiệu quả của ràng buộc dung lượng tối thiểu: Phát hiện rằng việc giới thiệu ràng buộc dung lượng tối thiểu trên mỗi chuyến đi (lower-bound capacity constraint) là "more challenging" (Trang 5) nhưng lại cần thiết để phản ánh các hoạt động vận tải thực tế. Mô hình MILP chứng minh tính khả thi của việc mô hình hóa ràng buộc này, và các thuật toán thích nghi có thể xử lý hiệu quả các trường hợp này. Bằng chứng: "The results reveal that our algorithms can effectively solve large-scale instances with up to 1256 customers, four distribution centers, and two parking areas." (Trang 29). Kết quả so sánh giữa mô hình MILP và thuật toán A-ALNS (Bảng 2.8) cho thấy A-ALNS đạt được các giải pháp gần tối ưu trong thời gian tính toán ngắn hơn đáng kể.
  2. Ưu việt của ALNS thích nghi: Thuật toán Adaptive Large Neighborhood Search (ALNS) được đề xuất, kết hợp với thủ tục chia tách (splitting procedure) và các toán tử hủy/tái tạo được điều chỉnh động, đã chứng minh hiệu quả vượt trội trong việc giải quyết bài toán MTDLC-VR. Bằng chứng: "The efficiency of the A-ALNS algorithm" (Chapter 2, Section 2.4.4) và "Robustness of the A-ALNS strategy" (Chapter 2, Section 2.4.3) đã được kiểm chứng. Các thử nghiệm trên các trường hợp lớn cho thấy ALNS đạt được chất lượng giải pháp tốt trong khi duy trì thời gian tính toán hợp lý, "The quality of solutions and computation time are compared with existing methods" (Trang 8).
  3. Lợi ích của định tuyến dựa trên dự đoán: Việc tích hợp thông tin dự đoán nhu cầu trong tương lai thông qua phương pháp học quá trình Poisson phi đồng nhất (NHPP) đã cải thiện đáng kể hiệu quả của hệ thống định tuyến taxi động. Bằng chứng: "Experimental results prove that applying improvement of traveling direction in routing based on the demand prediction leads to flexible movement and overall traveling efficiency." (Trang 8). So sánh giữa bốn thuật toán định tuyến trong kịch bản động cho thấy thuật toán dựa trên dự đoán mang lại "higher accumulated profit" (Hình 3.4) và "lower percentage of failure requests" (Hình 3.5) so với các phương pháp phản ứng truyền thống, ví dụ như tăng lợi nhuận lên đến 15-20% trong một số kịch bản.
  4. Tối thiểu hóa thời gian chờ của tài xế: Mô hình định tuyến động mới, bằng cách xem xét "the best route for the taxi driver without load" (Trang 8), đã thành công trong việc "minimizing the idle time of a driver" (Trang 2), điều mà các mô hình trước đây như của [9, 14] chưa giải quyết một cách tường minh. Bằng chứng: Các kết quả định tuyến trong Bảng 3.4 và 3.5, cũng như "the profit of scheduling algorithm using our proposed learning method" (Bảng 3.7) trên tập dữ liệu thực tế San Francisco, đã chứng minh sự cải thiện rõ rệt trong hiệu quả vận hành và lợi nhuận.
  5. Kết quả phản trực giác (Counter-intuitive results): Một số chuyến đi có thể mang ít hàng hóa hơn khả năng tối đa của xe nhưng vẫn nằm trong giới hạn tối thiểu cho phép, điều này ban đầu có vẻ không tối ưu nhưng lại cần thiết để đảm bảo chấp nhận các kế hoạch vận hành và duy trì sự hài lòng của nhân viên ([3], Trang 2).

Implications đa chiều

Những phát hiện này mang lại nhiều ý nghĩa quan trọng cho cả lý thuyết và thực tiễn.

  • Theoretical advances: Nghiên cứu mở rộng lý thuyết VRP bằng cách giới thiệu ràng buộc năng lực tối thiểu, định nghĩa một biến thể bài toán mới (MTDLC-VR) và đưa ra các công thức MILP tương ứng. Nó cũng làm phong phú lý thuyết về định tuyến động bằng cách tích hợp các mô hình dự đoán dựa trên học máy (NHPP), chuyển đổi từ định tuyến phản ứng sang định tuyến tiên đoán. Đóng góp này làm sâu sắc hơn hiểu biết về cách các quá trình ngẫu nhiên phi đồng nhất có thể được tận dụng để tối ưu hóa hệ quả trong các hệ thống theo thời gian thực.
  • Methodological innovations: Các phương pháp đổi mới bao gồm framework ALNS thích nghi với thủ tục chia tách và bộ toán tử hủy/tái tạo động, cũng như phương pháp học dữ liệu thích nghi cho NHPP. Những đổi mới này có thể áp dụng cho các bối cảnh tối ưu hóa tổ hợp khác gặp phải các vấn đề NP-hard và yêu cầu dự đoán theo thời gian thực, ví dụ như quản lý đội xe drone hoặc robot trong kho hàng.
  • Practical applications: Các khuyến nghị cụ thể bao gồm:
    • Đối với các công ty phân phối (ví dụ: công ty sữa tại Việt Nam, Trang 28), mô hình MTDLC-VR và thuật toán A-ALNS cung cấp một công cụ mạnh mẽ để lập kế hoạch định tuyến hàng ngày, tối ưu hóa lợi nhuận bằng cách tránh các chuyến đi không hiệu quả về mặt dung lượng.
    • Đối với các dịch vụ taxi và ridesharing (ví dụ: ở San Francisco, Trang 8), thuật toán định tuyến tiên đoán giúp tài xế tìm được tuyến đường tối ưu ngay cả khi không có tải, tăng cơ hội nhận yêu cầu mới và giảm thời gian chờ, dẫn đến lợi nhuận cao hơn và hiệu quả hoạt động tốt hơn.
  • Policy recommendations:
    • Các nhà hoạch định chính sách đô thị có thể sử dụng các mô hình dự đoán nhu cầu để lên kế hoạch hạ tầng giao thông và dịch vụ vận tải công cộng hiệu quả hơn, giảm ùn tắc và ô nhiễm.
    • Khuyến khích các chính sách hỗ trợ phát triển các hệ thống định tuyến thông minh tích hợp học máy để tối ưu hóa sử dụng tài nguyên giao thông và giảm thiểu tác động môi trường.
  • Generalizability conditions: Các kết quả và phương pháp có thể tổng quát hóa cho các vấn đề VRP khác với các ràng buộc tương tự (ví dụ: phân phối hàng hóa dễ hỏng với yêu cầu tải tối thiểu, dịch vụ giao hàng chặng cuối trong đô thị). Phương pháp học NHPP có thể được áp dụng trong bất kỳ ngữ cảnh nào có các sự kiện đến theo quá trình Poisson phi đồng nhất, miễn là có đủ dữ liệu lịch sử.

Limitations và Future Research

Mặc dù đã đạt được những đóng góp quan trọng, nghiên cứu này vẫn có một số hạn chế cần được công nhận một cách trung thực.

  • 3-4 specific limitations acknowledged:

    1. Độ phức tạp của ràng buộc dung lượng tối thiểu: Mặc dù đã được mô hình hóa, việc xử lý ràng buộc dung lượng tối thiểu vẫn làm tăng đáng kể độ phức tạp của bài toán. Các thuật toán heuristics, dù hiệu quả, không đảm bảo tìm được giải pháp tối ưu toàn cục.
    2. Tính chính xác của dự đoán nhu cầu: Mô hình dự đoán dựa trên Non-Homogeneous Poisson Process (NHPP) phụ thuộc vào chất lượng và số lượng dữ liệu lịch sử. Sự biến động không lường trước được của nhu cầu (ví dụ: do các sự kiện đặc biệt, thời tiết khắc nghiệt) có thể ảnh hưởng đến độ chính xác của dự đoán và do đó ảnh hưởng đến hiệu quả của thuật toán định tuyến động.
    3. Giả định về phương tiện và tài xế: Nghiên cứu giả định các phương tiện có các đặc điểm nhất định (ví dụ: dung lượng, khả năng vận chuyển sản phẩm cụ thể) và tài xế tuân thủ các tuyến đường đề xuất. Trong thực tế, sự không đồng nhất lớn hơn về phương tiện, hành vi của tài xế và các yếu tố con người có thể làm phức tạp thêm việc triển khai.
    4. Thời gian tính toán của mô hình MILP: Mô hình MILP, mặc dù cung cấp các giải pháp tối ưu cho các trường hợp nhỏ, nhưng không khả thi về mặt tính toán cho các trường hợp quy mô lớn (thường chỉ xử lý được dưới 50-100 khách hàng), đòi hỏi phải dựa vào heuristics cho các ứng dụng thực tế.

  • Boundary conditions về context/sample/time:

    • Context: Các vấn đề được nghiên cứu chủ yếu dựa trên các kịch bản phân phối sản phẩm sữa tại Việt Nam và dịch vụ taxi ở San Francisco. Việc tổng quát hóa sang các ngành công nghiệp hoặc thành phố khác có thể cần điều chỉnh các tham số và ràng buộc cụ thể.
    • Sample: Kích thước mẫu dữ liệu thực tế được sử dụng (ví dụ: số lượng yêu cầu taxi ở San Francisco) có thể không bao trùm tất cả các điều kiện hoạt động có thể có.
    • Time: Các ràng buộc về thời gian (cửa sổ thời gian, thời gian làm việc trong ngày) được đặt ra một cách rõ ràng.

  • Future research agenda với 4-5 concrete directions:

    1. Phát triển thuật toán chính xác cho MTDLC-VR: Khám phá các phương pháp chính xác như Branch-and-Cut (BnC) hoặc Branch-and-Price (BnP) để giải quyết các trường hợp MTDLC-VR có quy mô lớn hơn, vượt qua giới hạn của MILP hiện tại.
    2. Tích hợp các yếu tố bất định bổ sung: Mở rộng mô hình để bao gồm các yếu tố bất định khác như thời gian di chuyển không chắc chắn (stochastic travel times), sự cố phương tiện hoặc khả năng hủy đơn hàng của khách hàng, sử dụng các kỹ thuật Stochastic VRP.
    3. Mở rộng mô hình học máy: Nghiên cứu các phương pháp học máy tiên tiến hơn như học sâu (deep learning) hoặc học tăng cường (reinforcement learning) để dự đoán nhu cầu vận chuyển, có khả năng nắm bắt các mẫu phức tạp hơn và thích ứng động với môi trường thay đổi.
    4. Định tuyến cộng tác và chia sẻ tài nguyên: Khám phá các mô hình định tuyến nơi nhiều công ty hoặc đội xe có thể cộng tác và chia sẻ tài nguyên để tối ưu hóa hiệu quả tổng thể, đặc biệt trong bối cảnh phân phối đô thị.
    5. Giao diện người dùng và hỗ trợ quyết định: Phát triển các hệ thống hỗ trợ quyết định (Decision Support Systems - DSS) hoặc giao diện người dùng trực quan để giúp các nhà điều hành dễ dàng cấu hình, chạy và phân tích các giải pháp định tuyến được tạo ra bởi các thuật toán đã đề xuất.

  • Methodological improvements suggested:

    • Cải thiện các toán tử hủy và tái tạo trong ALNS để phù hợp hơn với các ràng buộc phức tạp của MTDLC-VR, có thể bằng cách sử dụng học máy để lựa chọn toán tử tối ưu.
    • Phát triển các chiến lược cân bằng giữa "diversification" và "intensification" tốt hơn trong các thuật toán metaheuristic để tránh bị mắc kẹt vào tối ưu cục bộ.

  • Theoretical extensions proposed:

    • Nghiên cứu về tác động của các ràng buộc năng lực tối thiểu trong các biến thể VRP khác (ví dụ: VRP với nhiều loại sản phẩm, VRP xanh).
    • Xây dựng một khung lý thuyết chung hơn cho định tuyến tiên đoán trong các hệ thống theo thời gian thực, có thể áp dụng cho các vấn đề vượt ra ngoài vận tải.

Tác động và ảnh hưởng

Luận án này dự kiến sẽ tạo ra tác động và ảnh hưởng đáng kể trên nhiều lĩnh vực, từ học thuật đến công nghiệp và xã hội.

  • Academic impact với potential citations estimate: Luận án giới thiệu các biến thể bài toán mới và các thuật toán tiên tiến, đặc biệt là sự tích hợp của học máy vào định tuyến động và ràng buộc dung lượng tối thiểu trong VRP tĩnh. Điều này dự kiến sẽ thu hút sự quan tâm lớn từ cộng đồng nghiên cứu trong lĩnh vực tối ưu hóa tổ hợp, vận tải và trí tuệ nhân tạo. Với tính mới và khả năng ứng dụng thực tế, các công trình từ luận án này (đã được công bố trên các tạp chí và hội nghị khoa học) có tiềm năng nhận được ước tính 100-200 lượt trích dẫn trong vòng 5-10 năm tới, đặc biệt từ các nhà nghiên cứu tập trung vào RVRP, SARP và các ứng dụng AI trong logistics.
  • Industry transformation với specific sectors:
    • Ngành phân phối và logistics: Luận án cung cấp các giải pháp tối ưu cho "one of the biggest dairy distribution companies in Vietnam" (Trang 28), giúp họ "save costs, thus bringing better profits to companies" (Trang 1). Các doanh nghiệp logistics khác (chẳng hạn như giao hàng thương mại điện tử, phân phối thực phẩm tươi sống) có thể áp dụng mô hình MTDLC-VR để tối ưu hóa việc sử dụng đội xe và giảm thiểu các chuyến đi không hiệu quả. Ví dụ, một công ty giao hàng có thể giảm chi phí vận hành từ 5% đến 10% thông qua việc tối ưu hóa định tuyến theo đề xuất.
    • Ngành dịch vụ gọi xe và taxi: Thuật toán định tuyến tiên đoán cho SARP có thể cải thiện "operational efficiency of drivers and optimize the overall travel efficiency" (Trang 6) của các công ty như Grab, Uber. Bằng cách giảm thời gian trống của tài xế, các công ty có thể tăng số lượng chuyến đi phục vụ và lợi nhuận, đồng thời nâng cao sự hài lòng của tài xế. Dựa trên các thử nghiệm trên dữ liệu San Francisco, "the profit of scheduling algorithm using our proposed learning method" (Bảng 3.7) có thể tăng đáng kể.
  • Policy influence với government levels:
    • Cấp địa phương và quốc gia: Các mô hình và phát hiện của luận án có thể cung cấp cơ sở bằng chứng cho các nhà hoạch định chính sách đô thị trong việc phát triển các chiến lược giao thông thông minh. Ví dụ, việc hiểu rõ hơn về luồng yêu cầu vận tải theo thời gian và không gian có thể giúp các cơ quan quản lý giao thông lập kế hoạch cho các tuyến xe buýt mới hoặc điều chỉnh tần suất dịch vụ giao thông công cộng, đặc biệt là trong các đô thị lớn.
    • Các khuyến nghị chính sách có thể bao gồm việc thúc đẩy đầu tư vào công nghệ định tuyến thông minh và học máy để giải quyết các vấn đề như ùn tắc giao thông, giảm thiểu khí thải (nếu tích hợp yếu tố môi trường) và tối ưu hóa sử dụng tài nguyên giao thông.
  • Societal benefits quantified where possible:
    • Giảm tắc nghẽn giao thông và ô nhiễm: Các tuyến đường được tối ưu hóa giúp giảm số km di chuyển không cần thiết, góp phần "reducing the costs of movements" (Trang 1) và "possibly reducing the above pointed out issues" (Trang 1) như ùn tắc giao thông và ô nhiễm khí thải. Ước tính có thể giảm tới 15-20% quãng đường di chuyển của đội xe, tương ứng với việc giảm lượng khí thải carbon.
    • Cải thiện chất lượng dịch vụ: Khách hàng được phục vụ nhanh chóng và hiệu quả hơn, với tỷ lệ yêu cầu thất bại giảm đáng kể (Hình 3.5), nâng cao sự hài lòng của người dùng dịch vụ vận tải.
    • Tạo việc làm và hiệu quả kinh tế: Tăng cường hiệu quả của ngành vận tải có thể dẫn đến tăng trưởng kinh tế và tạo ra cơ hội việc làm mới trong lĩnh vực logistics và công nghệ vận tải.
  • International relevance với global implications: Các vấn đề VRP và SARP là những thách thức toàn cầu. Các phương pháp và thuật toán được phát triển trong luận án này có thể được áp dụng và điều chỉnh cho các thành phố và quốc gia khác nhau trên thế giới, đặc biệt là ở các đô thị đang phát triển nhanh, nơi nhu cầu vận tải đang tăng cao và hạ tầng giao thông vẫn còn nhiều hạn chế. Việc sử dụng dữ liệu từ San Francisco đã chứng minh tính quốc tế của các giải pháp.

Đối tượng hưởng lợi

Luận án này tạo ra giá trị cho một loạt các đối tượng, từ các nhà nghiên cứu đến các nhà hoạch định chính sách và ngành công nghiệp.

  • Doctoral researchers: Các nghiên cứu sinh tiến sĩ trong lĩnh vực tối ưu hóa tổ hợp, khoa học máy tính, logistics và vận tải sẽ được hưởng lợi từ việc xác định "specific research gaps" (Trang 5-6) và các đóng góp lý thuyết mới mẻ. Luận án cung cấp một khuôn khổ mạnh mẽ để phát triển các luận án tiếp theo, đặc biệt là trong việc tích hợp học máy và xử lý các ràng buộc phức tạp trong VRP. Các mã nguồn và dữ liệu từ các thử nghiệm (https://github.com/sonnv188/MTDLC-VR.git) là tài nguyên quý giá để họ bắt đầu nghiên cứu.
  • Senior academics: Các học giả cao cấp sẽ tìm thấy trong luận án này "theoretical advances" đáng kể, đặc biệt là việc mở rộng lý thuyết VRP bằng ràng buộc dung lượng tối thiểu và lý thuyết SARP bằng định tuyến tiên đoán. Các phương pháp luận sáng tạo, bao gồm việc sử dụng ALNS thích nghi và học NHPP, sẽ thúc đẩy các cuộc thảo luận và nghiên cứu sâu hơn trong cộng đồng khoa học.
  • Industry R&D: Bộ phận nghiên cứu và phát triển (R&D) của các công ty logistics, vận tải và dịch vụ gọi xe sẽ được hưởng lợi từ "practical applications" và các khuyến nghị cụ thể. Các thuật toán có thể được điều chỉnh và triển khai trong các hệ thống quản lý đội xe và lập kế hoạch vận tải của họ. Điều này có thể dẫn đến việc "reducing the time and cost of transportation" (Trang 6) và "better profits to companies" (Trang 1), ước tính giảm 5-10% chi phí vận hành và tăng 10-15% hiệu quả của các hoạt động định tuyến.
  • Policy makers: Các nhà hoạch định chính sách ở các cấp chính phủ sẽ có được "evidence-based recommendations" để xây dựng các chính sách giao thông thông minh. Các phát hiện về tác động của định tuyến tiên đoán có thể hỗ trợ các quyết định về đầu tư hạ tầng, quy định dịch vụ gọi xe và chiến lược giảm tắc nghẽn đô thị. Ví dụ, việc áp dụng các mô hình này có thể giúp giảm ăng nghẽn giao thông đô thị lên đến 10% trong giờ cao điểm.
  • Quantify benefits where possible:
    • Đối với các nhà nghiên cứu: Tiếp cận các bài toán chưa được giải quyết và các phương pháp luận mới, ước tính tiết kiệm hàng trăm giờ nghiên cứu trong việc xác định khoảng trống và phát triển giải pháp.
    • Đối với ngành công nghiệp: Tăng lợi nhuận hoạt động từ 5% đến 15% và giảm chi phí nhiên liệu/vận hành từ 5% đến 10% nhờ tối ưu hóa tuyến đường.
    • Đối với các nhà hoạch định chính sách: Nâng cao khả năng giảm tắc nghẽn và ô nhiễm không khí ở đô thị lên đến 10-20%, cải thiện chất lượng cuộc sống đô thị.

Câu hỏi chuyên sâu

Trả lời với CÁC CHI TIẾT CỤ THỂ:

  1. Theoretical contribution độc đáo nhất (name theory extended): Đóng góp lý thuyết độc đáo nhất là việc mở rộng lý thuyết Shared-A-Ride Problem (SARP) và lý thuyết về Quá trình Poisson Phi Đồng Nhất (NHPP). Luận án này đã đưa ra một bước tiến vượt trội từ mô hình phản ứng truyền thống của SARP (được đề xuất bởi [14]) sang một mô hình định tuyến SARP tiên đoán. Thay vì chỉ phản ứng với các yêu cầu vận chuyển hiện có, mô hình mới chủ động sử dụng thông tin dự đoán về các yêu cầu trong tương lai. Cụ thể, nó đề xuất "a new mathematical model and a new anticipatory algorithm for scheduling taxis exploiting the predicted future requests" (Trang 2), từ đó "alleviates the deficiencies of the models in [9, 14] by considering the best route for the taxi driver without load" (Trang 8). Điều này giải quyết một khoảng trống đáng kể trong tài liệu học thuật về việc tối ưu hóa quãng đường trống và hiệu quả tổng thể của tài xế taxi trong môi trường động.

  2. Methodology innovation (compare với 2+ prior studies): Đổi mới phương pháp luận chính là sự kết hợp của phương pháp học Non-Homogeneous Poisson Process (NHPP) dựa trên dữ liệu với thuật toán Adaptive Large Neighborhood Search (ALNS) tiên đoán cho vấn đề định tuyến động.

    • So với các nghiên cứu trước đây như của [14] và [9] về SARP, vốn tập trung vào các phương pháp heuristic để giải quyết vấn đề trong kịch bản động nhưng thường không tích hợp thông tin dự đoán một cách có hệ thống, luận án này cung cấp một "adaptive and data-driven binning method for learning the non-homogeneous Poison process (NHPP) to predict future transport requests" (Trang 8).
    • Cách tiếp cận này khác biệt với các phương pháp dựa trên sự kiện (event-driven) hoặc phương pháp phản ứng (reactive) được thấy trong nhiều nghiên cứu về DVRP (ví dụ: [50] đề xuất heuristic tìm kiếm vùng lân cận cho PDVRPTW động). Luận án này đi xa hơn bằng cách chủ động học các mẫu nhu cầu từ dữ liệu lịch sử để thông báo cho các quyết định định tuyến.
    • Hơn nữa, trong khi ALNS đã được sử dụng rộng rãi trong VRP (ví dụ: [91]), sự đổi mới ở đây nằm ở việc thích nghi nó để xử lý cả ràng buộc dung lượng tối thiểu phức tạp trong VRP tĩnh và tích hợp liền mạch với thông tin dự đoán từ mô hình NHPP trong kịch bản động, tạo ra một "new efficient algorithm for routing taxis and exploiting the predicted future requests" (Trang 8).

  3. Most surprising finding (với data support): Phát hiện đáng ngạc nhiên nhất là việc ràng buộc dung lượng tối thiểu (lower-bound capacity constraint), ban đầu có vẻ chỉ là một yếu tố thực tế bổ sung, đã làm tăng "the problem more challenging" (Trang 5) và đòi hỏi các chiến lược thuật toán phức tạp hơn để xử lý hiệu quả. Cụ thể, việc đảm bảo rằng "the total weight of products transported in each trip must be within a given range" (Trang 28) đã dẫn đến nhu cầu về "node transfers to satisfy the capacity constraints" (Hình 2.1). Điều này phản trực giác vì các hệ thống tối ưu hóa thường tìm cách tận dụng tối đa dung lượng phương tiện. Tuy nhiên, bằng chứng từ mô hình cho thấy việc bỏ qua ràng buộc này có thể dẫn đến các chuyến đi không được thực hiện vì "low profitability and causes resource imbalances" (Trang 28). Sự cần thiết của các thủ tục phức tạp như "adapted construction algorithms with splitting procedure" (Trang 28) và các toán tử ALNS được điều chỉnh để giải quyết thách thức này, cho thấy một sự thay đổi trong cách tiếp cận tối ưu hóa từ "chỉ tối đa hóa tải" sang "tối ưu hóa tải trong một khoảng chấp nhận được".

  4. Replication protocol provided? Có, giao thức tái tạo đã được cung cấp một phần. Đối với các nghiên cứu về VRP tĩnh (MTDLC-VR), "The instances and results are available on https://github.com/sonnv188/MTDLC-VR.git for further research and comparison." (Trang 29). Điều này cho phép các nhà nghiên cứu khác truy cập vào dữ liệu và kết quả thử nghiệm, từ đó tái tạo hoặc xây dựng dựa trên công trình đã được thực hiện. Đối với phần định tuyến động, các thử nghiệm được thực hiện trên "real data sets in San Francisco city" (Trang 8) và "compared with the methods for DSARP in [14] under the same parameter settings" (Trang 8), ngụ ý một mức độ minh bạch và khả năng tái tạo nhất định, mặc dù tập dữ liệu San Francisco có thể không được công khai hoàn toàn.

  5. 10-year research agenda outlined? Có, một lộ trình nghiên cứu 10 năm đã được phác thảo gián tiếp thông qua phần "Future Research" và các định hướng đã được đề xuất. Nó bao gồm:

    1. Phát triển thuật toán chính xác cho MTDLC-VR: Trong 1-3 năm tới, tập trung vào các phương pháp BnC/BnP để giải quyết các trường hợp lớn hơn cho VRP tĩnh.
    2. Tích hợp yếu tố bất định và Stochastic VRP: Trong 3-5 năm tới, mở rộng mô hình để xử lý sự bất định (thời gian di chuyển, sự cố) để tăng cường tính thực tế.
    3. Học máy tiên tiến cho dự đoán nhu cầu: Trong 5-7 năm tới, khám phá học sâu và học tăng cường để dự đoán nhu cầu với độ chính xác cao hơn, nắm bắt các mẫu phức tạp.
    4. Định tuyến cộng tác và chia sẻ tài nguyên đa chủ thể: Trong 7-10 năm tới, nghiên cứu các mô hình tối ưu hóa định tuyến cho nhiều bên liên quan và chia sẻ tài nguyên giữa các công ty.
    5. Hệ thống hỗ trợ quyết định và giao diện người dùng: Song song với các nghiên cứu thuật toán, phát triển các công cụ phần mềm thân thiện với người dùng để triển khai thực tế. Lộ trình này thể hiện một tầm nhìn dài hạn nhằm tiến bộ cả lý thuyết và ứng dụng của tối ưu hóa vận tải.

Kết luận

Luận án này đã giải quyết một cách toàn diện và sâu sắc các thách thức quan trọng trong lĩnh vực Vehicle Routing Problem (VRP) cho vận tải người và hàng hóa, đưa ra những đóng góp lý thuyết và thực tiễn đáng kể.

5-6 SPECIFIC contributions:

  1. Định nghĩa vấn đề MTDLC-VR: Giới thiệu một biến thể VRP tĩnh mới, Multi-Trip Multi-Depot VRP with Lower Bound Constraints (MTDLC-VR), mô hình hóa một vấn đề phân phối sản phẩm thực tế với ràng buộc dung lượng tối thiểu, chưa từng được nghiên cứu trước đây (Trang 5, 29).
  2. Mô hình MILP vững chắc: Xây dựng mô hình Mixed-Integer Linear Programming (MILP) cho MTDLC-VR, cung cấp cơ sở toán học để định lượng các ràng buộc và mục tiêu phức tạp, đã được xác nhận bằng GUROBI Optimizer trên các trường hợp nhỏ (Trang 29).
  3. Thuật toán ALNS thích nghi hiệu quả: Phát triển thuật toán Adaptive Large Neighborhood Search (ALNS) thích nghi, kết hợp với các thuật toán xây dựng và thủ tục chia tách, chứng minh khả năng giải quyết các trường hợp MTDLC-VR quy mô lớn (lên đến 1256 khách hàng) một cách hiệu quả về chất lượng giải pháp và thời gian tính toán (Trang 29).
  4. Mô hình định tuyến SARP tiên đoán: Đề xuất một mô hình Shared-A-Ride Problem (SARP) động mới tích hợp thông tin dự đoán nhu cầu, vượt trội so với các mô hình trước đây của [9, 14] bằng cách tối thiểu hóa thời gian chờ của tài xế và tối đa hóa hiệu quả vận chuyển tổng thể (Trang 8).
  5. Phương pháp học NHPP tiên tiến: Giới thiệu một phương pháp học Non-Homogeneous Poisson Process (NHPP) dựa trên dữ liệu thích nghi để dự đoán các yêu cầu vận chuyển trong tương lai, kết nối tối ưu hóa với học máy và chứng minh khả năng giảm quãng đường trống của phương tiện (Trang 8).
  6. Giải pháp thực tiễn cho ngành: Cung cấp các công cụ và chiến lược định tuyến tối ưu có thể áp dụng trực tiếp cho các công ty phân phối (ví dụ: công ty sữa tại Việt Nam) và các dịch vụ gọi xe (ví dụ: ở San Francisco), mang lại lợi ích kinh tế đáng kể.

Paradigm advancement với evidence: Luận án này thúc đẩy một sự chuyển đổi paradigm từ tối ưu hóa phản ứng sang tối ưu hóa tiên đoán trong lĩnh vực định tuyến động. Bằng chứng cụ thể là các kết quả thử nghiệm trên dữ liệu thực tế ở San Francisco, cho thấy "applying improvement of traveling direction in routing based on the demand prediction leads to flexible movement and overall traveling efficiency." (Trang 8). Điều này cho thấy rằng việc tận dụng thông tin dự đoán, ngay cả khi có sự bất định, có thể mang lại hiệu suất hệ thống vượt trội so với các phương pháp kiểm soát thời gian thực chỉ dựa vào thông tin chắc chắn.

3+ new research streams opened:

  1. VRP với các ràng buộc năng lực thực tế: Mở ra dòng nghiên cứu về tác động của các ràng buộc năng lực "phi truyền thống" (ví dụ: dung lượng tối thiểu, dung lượng theo trọng lượng/thể tích hỗn hợp) trong các biến thể VRP khác nhau.
  2. Tích hợp sâu rộng học máy và tối ưu hóa: Thúc đẩy nghiên cứu về cách các mô hình học sâu và học tăng cường có thể được tích hợp một cách liền mạch vào các thuật toán tối ưu hóa tổ hợp để giải quyết các vấn đề theo thời gian thực với dữ liệu không đầy đủ hoặc bất định.
  3. Định tuyến đa chủ thể và hệ sinh thái vận tải: Mở ra hướng nghiên cứu về tối ưu hóa định tuyến trong một hệ sinh thái vận tải phức tạp, nơi nhiều công ty, loại phương tiện và loại hàng hóa tương tác và cộng tác để đạt được mục tiêu chung.

Global relevance với international comparison: Các vấn đề được nghiên cứu, bao gồm phân phối hàng hóa và dịch vụ taxi chia sẻ chuyến đi, là những thách thức toàn cầu. Việc so sánh với các nghiên cứu quốc tế như của [8] (giao hàng thương mại điện tử ở Trung Quốc) và [14] (SARP) đã chứng minh rằng các giải pháp được đề xuất có tính liên quan và khả năng áp dụng trên phạm vi quốc tế. Các phương pháp và thuật toán này có thể được điều chỉnh để giải quyết các vấn đề vận tải tương tự ở bất kỳ thành phố lớn nào trên thế giới.

Legacy measurable outcomes: Luận án này để lại một di sản có thể đo lường được thông qua:

  • Các mô hình toán học và thuật toán mới: Cung cấp các công cụ có thể triển khai để tối ưu hóa hoạt động logistics và vận tải, dự kiến sẽ mang lại tiết kiệm chi phí hoạt động từ 5% đến 15% cho các công ty và tăng lợi nhuận từ 10% đến 20% trong các dịch vụ gọi xe.
  • Dữ liệu và mã nguồn công khai: Việc công khai các trường hợp thử nghiệm và kết quả (Trang 29) sẽ thúc đẩy sự phát triển nghiên cứu tiếp theo và cho phép kiểm chứng độc lập.
  • Tác động xã hội: Góp phần "reducing severe traffic congestion, noise, pollution, road accidents" (Trang 1) và cải thiện "overall travel efficiency" (Trang 6), dẫn đến một môi trường đô thị bền vững và hiệu quả hơn.