## Tổng quan nghiên cứu

Ngành giao hàng chặng cuối đang trở thành một lĩnh vực trọng điểm trong bối cảnh thương mại điện tử phát triển mạnh mẽ, đặc biệt sau đại dịch COVID-19. Theo báo cáo Logistics Việt Nam 2022, tổng khối lượng vận chuyển hàng hóa trong 9 tháng đầu năm 2022 tăng 24.4%, luân chuyển hàng hóa tăng 31% so với cùng kỳ năm trước, trong đó vận tải đường bộ chiếm tới 72.93%. Nhu cầu giao hàng không chỉ dừng lại ở việc chuyển hàng từ nhà bán đến khách hàng mà còn đòi hỏi giao hàng đúng khung thời gian nhất định, tạo ra thách thức lớn trong việc lập kế hoạch và tối ưu hóa nguồn lực vận chuyển.

Bài toán hoạch định tuyến đường (Vehicle Routing Problem - VRP) với các biến thể như VRPTW (có khung thời gian) và MDVRPTW (nhiều kho, nhiều điểm giao hàng với khung thời gian) được ứng dụng để giải quyết vấn đề này. Tuy nhiên, bài toán này thuộc loại NP-hard, khó tìm lời giải tối ưu chính xác trong thời gian hợp lý. Luận văn tập trung nghiên cứu ứng dụng giải thuật Simulated Annealing (SA) để tối ưu hóa hoạch định tuyến đường cho một công ty giao hàng chặng cuối tại TP. Hồ Chí Minh, nhằm giảm thiểu tổng quãng đường di chuyển và đảm bảo giao hàng đúng thời gian trong 6 giờ kể từ lúc nhận đơn.

Phạm vi nghiên cứu tập trung vào bộ phận vận hành của công ty giao hàng nội thành TP. Hồ Chí Minh, sử dụng dữ liệu thực tế các đơn hàng trong một khung giờ nhất định. Mục tiêu chính là xây dựng mô hình toán và giải thuật tối ưu phù hợp, nâng cao chất lượng dịch vụ và khả năng cạnh tranh của công ty thông qua việc giảm chi phí vận chuyển và tăng tỷ lệ giao hàng thành công.

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

### Khung lý thuyết áp dụng

- **Vehicle Routing Problem (VRP):** Mô hình cơ bản xác định tuyến đường tối ưu cho đội xe phục vụ khách hàng với mục tiêu giảm tổng quãng đường di chuyển.
- **Vehicle Routing Problem with Time Windows (VRPTW):** Mở rộng VRP với ràng buộc thời gian phục vụ tại mỗi khách hàng, đảm bảo giao hàng trong khung thời gian xác định.
- **Multi-Depot VRPTW (MDVRPTW):** Mô hình phức tạp hơn với nhiều kho xuất phát, phù hợp với mạng lưới phân phối rộng lớn và đa điểm.
- **Giải thuật Simulated Annealing (SA):** Phương pháp metaheuristic dựa trên quá trình luyện kim, cho phép tìm kiếm lời giải tối ưu toàn cục bằng cách chấp nhận lời giải tệ hơn với xác suất giảm dần theo nhiệt độ, giúp tránh tối ưu cục bộ.
- **Thuật toán Greedy:** Được sử dụng để khởi tạo lời giải ban đầu có chất lượng tốt, giúp SA hội tụ nhanh hơn.

Các khái niệm chính bao gồm: khung thời gian (time windows), năng lực xe (vehicle capacity), phân cụm khách hàng (clustering), và hàm mục tiêu tối thiểu tổng chi phí vận chuyển.

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

- **Nguồn dữ liệu:** Dữ liệu thực tế từ công ty giao hàng chặng cuối tại TP. Hồ Chí Minh, bao gồm thông tin đơn hàng, tọa độ kho và khách hàng, khung thời gian giao hàng, và trạng thái đơn hàng.
- **Phương pháp phân tích:** 
  - Phân cụm khách hàng về các kho dựa trên khoảng cách địa lý sử dụng công thức Vincenty.
  - Xây dựng mô hình toán MDVRPTW với hàm mục tiêu tối thiểu tổng chi phí vận chuyển.
  - Áp dụng giải thuật Greedy để tạo lời giải ban đầu.
  - Sử dụng giải thuật Simulated Annealing để cải thiện lời giải, với các điều chỉnh nhằm tăng khả năng thoát khỏi tối ưu cục bộ và lưu giữ lời giải tốt nhất.
  - Kiểm định mô hình bằng cách so sánh kết quả với công cụ tối ưu của Google OR-tools.
- **Timeline nghiên cứu:** 
  - Thu thập và xử lý dữ liệu: 2 tháng.
  - Xây dựng mô hình và lập trình giải thuật: 3 tháng.
  - Kiểm nghiệm và đánh giá kết quả: 1 tháng.
  - Tổng thời gian thực hiện: 6 tháng.

## Kết quả nghiên cứu và thảo luận

### Những phát hiện chính

- **Giảm tổng quãng đường di chuyển:** Ứng dụng giải thuật SA đã giúp giảm hơn 30% tổng quãng đường so với phương pháp hiện trạng, tương tự kết quả nghiên cứu thực tế với 2 kho và 142 khách hàng.
- **Tăng tỷ lệ giao hàng thành công:** Tỷ lệ giao hàng thành công (Complete Rate - CR) được cải thiện từ mức trung bình khoảng 82% lên gần 90% sau khi áp dụng mô hình tối ưu.
- **Tối ưu hóa phân bổ khách hàng về kho:** Phân cụm khách hàng dựa trên khoảng cách thực tế giúp giảm các điểm giao hàng xa kho, từ đó giảm chi phí vận chuyển và thời gian giao hàng.
- **Hiệu quả của giải thuật SA:** So với các giải thuật metaheuristic khác như Genetic Algorithm (GA) và Ant Colony Optimization (ACO), SA cho kết quả tốt hơn về tổng chi phí và thời gian hội tụ, đặc biệt trong các bài toán quy mô vừa và nhỏ.

### Thảo luận kết quả

Nguyên nhân chính của việc cải thiện là do mô hình MDVRPTW kết hợp với giải thuật SA cho phép cân bằng giữa chi phí vận chuyển và ràng buộc khung thời gian, đáp ứng tốt hơn yêu cầu giao hàng đúng giờ của khách hàng. Việc phân cụm khách hàng về kho gần nhất giúp giảm quãng đường di chuyển không cần thiết, đồng thời giải thuật SA với cơ chế chấp nhận lời giải tệ hơn theo xác suất Boltzmann giúp tránh bị kẹt trong tối ưu cục bộ.

So sánh với các nghiên cứu trước đây, kết quả của luận văn phù hợp với xu hướng ứng dụng các giải thuật metaheuristic trong bài toán VRPTW và MDVRPTW. Việc sử dụng công cụ Google OR-tools để kiểm tra tính hợp lệ cũng đảm bảo độ tin cậy của mô hình.

Dữ liệu có thể được trình bày qua biểu đồ so sánh tổng quãng đường di chuyển trước và sau tối ưu, biểu đồ đường thể hiện tỷ lệ AR, FF, CR theo thời gian, và bảng so sánh hiệu suất các giải thuật.

## Đề xuất và khuyến nghị

- **Áp dụng mô hình MDVRPTW với giải thuật SA vào vận hành thực tế:** Để giảm chi phí vận chuyển và nâng cao chất lượng dịch vụ, công ty nên triển khai mô hình này trong quy trình hoạch định tuyến hàng ngày, ưu tiên các khung giờ cao điểm.
- **Cải tiến quy trình phân bổ khách hàng về kho:** Thay thế cách phân bổ theo quận bằng phân cụm dựa trên khoảng cách thực tế để tối ưu hóa tuyến đường và giảm thời gian giao hàng.
- **Tăng cường thu thập và quản lý dữ liệu thời gian giao hàng:** Thu thập thông tin chính xác về khung thời gian mong muốn của khách hàng để cải thiện độ chính xác của mô hình và giảm tỷ lệ giao hàng thất bại.
- **Đào tạo và nâng cao năng lực đội ngũ vận hành:** Tập huấn nhân viên vận hành và tài xế về quy trình mới, sử dụng công nghệ hỗ trợ để tăng tỷ lệ nhận đơn và giao hàng thành công.
- **Theo dõi và đánh giá liên tục hiệu quả mô hình:** Thiết lập hệ thống giám sát các chỉ số AR, FF, CR và chi phí vận chuyển để điều chỉnh kịp thời, đảm bảo mô hình vận hành hiệu quả trong dài hạn.

## Đối tượng nên tham khảo luận văn

- **Các công ty giao hàng chặng cuối:** Nhóm này sẽ nhận được giải pháp tối ưu hóa tuyến đường, giảm chi phí vận chuyển và nâng cao chất lượng dịch vụ giao hàng đúng giờ.
- **Doanh nghiệp thương mại điện tử:** Giúp cải thiện chuỗi cung ứng và trải nghiệm khách hàng thông qua việc tối ưu hóa vận chuyển hàng hóa.
- **Nhà nghiên cứu và sinh viên ngành kỹ thuật công nghiệp, logistics:** Cung cấp kiến thức về ứng dụng giải thuật metaheuristic trong bài toán VRPTW và MDVRPTW, cùng phương pháp xây dựng mô hình toán học thực tiễn.
- **Các nhà quản lý vận hành và phát triển phần mềm logistics:** Tham khảo để phát triển các công cụ hỗ trợ hoạch định tuyến và quản lý đội xe hiệu quả hơn.

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

1. **Giải thuật Simulated Annealing là gì và tại sao được chọn?**  
   Simulated Annealing là giải thuật metaheuristic dựa trên quá trình luyện kim, giúp tìm lời giải tối ưu toàn cục bằng cách chấp nhận lời giải tệ hơn với xác suất giảm dần. Nó được chọn vì khả năng tránh tối ưu cục bộ và hiệu quả trong bài toán VRPTW phức tạp.

2. **Mô hình MDVRPTW có điểm gì khác biệt so với VRPTW?**  
   MDVRPTW mở rộng VRPTW bằng cách có nhiều kho xuất phát (multi-depot), phù hợp với mạng lưới phân phối rộng và đa điểm, tăng tính thực tiễn cho các doanh nghiệp lớn.

3. **Làm thế nào để đảm bảo giao hàng đúng khung thời gian?**  
   Mô hình đặt ràng buộc thời gian phục vụ tại mỗi khách hàng, kết hợp với thuật toán tối ưu để lập kế hoạch tuyến đường sao cho xe đến đúng hoặc trước thời gian yêu cầu, giảm thiểu thời gian chờ và giao hàng trễ.

4. **Giải pháp này có áp dụng được cho các công ty nhỏ không?**  
   Có, giải thuật SA phù hợp với quy mô vừa và nhỏ, giúp các công ty có nguồn lực hạn chế vẫn có thể tối ưu hóa vận hành mà không cần đầu tư lớn vào công nghệ phức tạp.

5. **Kết quả nghiên cứu có thể được áp dụng ngay trong thực tế không?**  
   Có, mô hình và giải thuật đã được kiểm nghiệm trên dữ liệu thực tế và so sánh với công cụ tối ưu của Google, cho thấy hiệu quả rõ rệt, có thể triển khai trong vận hành hàng ngày.

## Kết luận

- Đã xây dựng thành công mô hình MDVRPTW kết hợp giải thuật Simulated Annealing để tối ưu hóa hoạch định tuyến đường cho công ty giao hàng chặng cuối.  
- Giải pháp giúp giảm hơn 30% tổng quãng đường di chuyển và nâng cao tỷ lệ giao hàng thành công lên gần 90%.  
- Mô hình được kiểm định chéo với công cụ Google OR-tools, đảm bảo tính chính xác và hiệu quả.  
- Đề xuất cải tiến quy trình phân bổ khách hàng và thu thập dữ liệu thời gian giao hàng để nâng cao hơn nữa chất lượng dịch vụ.  
- Khuyến nghị triển khai mô hình vào vận hành thực tế và tiếp tục nghiên cứu mở rộng cho các yếu tố bất định như giao thông, thời tiết.

Hãy áp dụng giải pháp này để nâng cao hiệu quả vận hành và cạnh tranh trên thị trường giao hàng chặng cuối đầy thách thức hiện nay.