Vehicle Routing Problem and các bài toán mở rộng 1.2.1 Bài toán định tuyến xe với ràng buộc tải trọng Bài toán VRP tiêu chuẩn là bài toán định tuyến xe có ràng buộc tải trọng (CVRP), trong đó một đội xe cố định đồng nhất được lập lộ trình để phục vụ nhu cầu của một tập khách hàng vận chuyển hàng hóa từ một kho cụ thể với chi phí vận chuyển nhỏ nhất. 1.2.2 Bài toán định tuyến xe giao và nhận với ràng buộc thời gian Một biến thể quan trọng của VRP là bài toán định tuyến xe nhận và giao hàng với khung thời gian (PDVRPTW). Trong PDVRPTW, bài toán yêu cầu tìm một hoặc nhiều tuyến với chi phí tối thiểu để phục vụ một số yêu cầu của khách hàng, trong đó mỗi yêu cầu được xác định bởi điểm nhận hàng, điểm giao hàng tương ứng và nhu cầu (hàng hóa hoặc hành khách) được vận chuyển giữa các vị trí này trong khoảng thời gian xác định trước. Hình 1.2: Rich vehicle routing problem. 1.2.3 Bài toán định tuyến taxi chia sẻ lộ trình Hầu hết các mô hình chia sẻ chuyến đi đều dựa trên bài toán định tuyến xe phục vụ yêu cầu dựa trên cuộc gọi (DARP) nổi tiếng. DARP bao gồm việc thiết kế các lộ trình cho đội xe chở một số người từ điểm đón tới điểm trả theo yêu cầu. Gần đây, Li et al. 2014 đã đề xuất mô tả về bài toán lập lộ trình taxi chia sẻ (SARP) động trong đó người và hàng hóa được phục vụ bởi cùng một mạng lưới taxi. Các tác giả trong Li et al. 2014 đã trình bày các công thức MILP cho SARP với một số ràng buộc thực tế. 1.2.4 Bài toán định tuyến xe phong phú Xu hướng mới chủ yếu tập trung vào việc áp dụng VRP và các mở rộng của chúng cho các vấn đề trong cuộc sống thực bằng cách kết hợp nhiều ràng buộc thực tế. Bài toán đó được gọi là bài toán định tuyến xe phong phú (RVRP). Hình 1.2 trình bày một số biến thể và mở rộng của bài toán VRPs.