Đề tài Thuật toán tối ưu định tuyến drone để giao đồ ăn theo yêu cầu

Thuật toán tối ưu định tuyến drone để giao đồ ăn theo yêu cầu Bài báo trong tạp chí Computers & Operations Research Tác giả: Yanchao Liu Ngày xuất bản: 26/5/2019 Sinh viên: Đặng Duy Anh – 20183471 GVHD: Huỳnh Thị Thanh Bình 1 1. Giới thiệu Có một thị trường rộng lớn cho dịch vụ giao bữa ăn theo yêu cầu bằng máy bay không người lái. Máy bay không người lái đang được phát triển như một nền tảng phương tiện giao thông thế hệ tiếp theo để cung cấp bữa ăn. Bài báo này trình bày một mô hình qui hoạch số nguyên hỗn hợp – mixed integer programming (MIP) mô tả toàn diện tất cả các khía cạnh liên quan của kịch bản kinh doanh. Cho phép nhập thông tin đơn hàng động với các địa điểm nhận hàng và giao hàng tùy ý theo thời gian. Mô hình được tăng cường với các ràng buộc đặc biệt và một hàm mục tiêu để chuyển tiếp hiệu quả các trạng thái của hệ thống giữa các khoảng thời gian liên tiếp. 2 (a) Người giao hàng của Uber Eats đang vận chuyển các thùng carton đồ ăn bằng xe đạp (b) Robot giao hàng được phát triển bởi Starship Technologies (c) Drone giao hàng của Ele.me Sự phát triển của công nghệ giao đồ ăn theo thời gian 3 2. Các bài báo liên quan Bài toán nhiều xe tải giao hàng trong thời gian thực của Jian Yang, Patrick Jaillet và Hani Mahmassani. Bài báo nghiên cứu về khả năng định hướng các phương tiện trong thời gian thực bằng chiến lược tìm kiếm Tabu của Ichoua và cộng sự. Định tuyến phương tiện động ngẫu nhiên trong mặy phẳng Euclid của Dimitris J. Bertsimas, và Garrett van Ryzin . Định tuyến phương tiện động, mô hình và thuật toán của Allan Larsen, Oli B. G. Madsen, and Marius M. Solomon    4 3. Giả thiết Quy trình vận chuyển một đơn hàng đồ ăn như sau: Khách hàng đặt một đơn hàng (khởi tạo), đơn hàng sẽ có các thông tin về món ăn, nhà hàng làm đồ ăn và địa chỉ khách nhận đồ ăn. Khách không yêu cầu thời gian chính xác nhận hàng, hệ thống sẽ dự đoán thời gian giao hàng khi nhà hàng chuẩn bị xong đồ ăn. Chọn một trong những drone ở gần nhà hàng để giao hàng, nếu không có thì triệu tập một drone từ xa. Nếu đơn hàng vượt quá trọng tải của drone, thì nhiều drone sẽ cùng vận chuyển các phần của đơn hàng. Một drone đang giao hàng có thể tiếp tục nhận hàng để giao đồng thời. 5 4. Giả thiết Mỗi drone chỉ được giao một loại đồ ăn (nóng hoặc lạnh) với số lượng nhất định. Đơn vị thời gian là một phút. Load và Unload đơn hàng lên drone sẽ mất một vài phút nhất định. Độ hao pin tỉ lệ với trọng tải đơn hàng và drone. Drone sẽ ngay lập tức được thay pin đầy nếu nó đến các kho sạc, việc thay pin mất vài phút. Các đơn hàng được khởi tạo sớm hơn thì có độ ưu tiên cao hơn. Phạm vi hoạt động của drone sẽ được biểu diễn trong hệ tọa độ hai chiều. 6 5. Các thành phần và ràng buộc của bài toán Gọi O là tập hợp các đơn hàng (Order) Trong đó o là một đơn hàng ϵ O 5.1 Order 7 Độ trễ của đơn hàng Lateness o,t tại thời điểm t là một thành phần sẽ được cực tiểu của hàm mục tiêu: - Đơn hàng chỉ có thể được giao khi nó sẵn sàng , Ready o,t cho biết tại thời điểm t đơn hàng đã sẵn sàng được giao chưa 8 5.2 Drone Gọi R là tập hợp các drone Các thuộc tính của một drone: Capacity r là trọng tải tối đa lượng hàng drone r có thể chở đồng thời. BatteryCap r là dung lượng pin của máy bay, được tính bằng trọng tải/ phút (VD: BatteryCap r 400 = 100 phút giao 4 đơn hàng tiêu chuẩn) BatThresh r là mức pin an toàn, nếu dưới mức pin này thì máy bay phải đến kho sạc MaxSpeed r là khoảng cách xa nhất drone r bay được trong một phút Weight r là trọng lượng của drone r Tập các hành động của một drone r là A = { Load, Unload, Move, Swap }, drone r sẽ ở trong trạng thái Move nếu như nó không ở trong ba trạng thái còn lại bất kể vận tốc là bao nhiêu. MinTime r là thời gian ngắn nhất drone hoàn thành 1 hành động, nghĩa là khi nó thực hiện một hành động thì nó phải thực hiện trong ít nhất MinTime r 9 5.3 Charging Depots Gọi E là tập hợp các điểm sạc e Mỗi một điểm sạc có: LocX e là tọa độ x của điểm sạc LocY e là tọa độ y của điểm sạc CRad e là bán kính của điểm sạc drone có thể đáp xuống để thay pin Giả thiết rằng điểm sạc luôn có sẵn pin đầy để thay cho drone khi nó đáp xuống  10 5.4 Khung thời gian của thuật toán Vì thực tế, các đơn đặt hàng được cập nhật và xuất hiện dần theo thời gian nên việc giải bài toán sẽ chia thành các lần lập với chu kì T và khoảng cách M. Các thời điểm trong chu kì thứ k : - Các đơn hàng mà sẽ được hệ thống cân nhắc điều phối drone đi giao: Công thức (4) đảm bảo hệ thống chỉ giao đơn hàng o khi nó đã được khởi tạo tại thời điểm bắt đầu vòng lặp và thời điểm đơn hàng sẵn sàng để giao không quá xa với thời điểm đang xét 11 6 Các công thức toán học Các biến nhị phân z: 12 6 Các công thức toán học Các biến liên tục : 13 5.4 Khung thời gian làm việc k = 1 k = 2 k = 3 14 Các công thức toán học Các biến liên tục dương : 15 Các ràng buộc 16 Các ràng buộc 17 Các ràng buộc 18 Các ràng buộc 19 Các ràng buộc 20 Các ràng buộc 21 Hàm mục tiêu Minimize a) Bay đến điểm sạc ngay khi pin yếu b) Bay đến điểm sạc gần nhất c) Drone nhặt những đơn hàng chưa được giao d) Hạn chế để đơn hàng bị “staged” – dở e) Drone load và unload đơn hàng khi đến nơi f) Điều drone gần nhất đến các invisible order g) Stage gần chỗ giao hàng h) Drone rảnh không đi lang thang i) Không đổi pin nhiều lần j) Đổ đầy pin mỗi lần sạc 22 Các tham số = 100 = 1 = 0.1 = 0.001 = 1000 = 100 CRad e = 20 = 5 = 8 MinTime = 1 23 7 Thử nghiệm - Không gian hoạt động : [0, 500] x [0, 500] - Tọa độ các điểm sạc pin: [125, 125], [125, 375], [375, 125], [375, 375] Thời gian hoạt động: 6 tiếng 353 đơn hàng được sinh ngẫu nhiên trong 6 tiếng với trọng lượng từ 1 đến 3, và thời gian nấu từ 2 đến 7 phút 50 máy bay, 24 máy bay lớn với trọng tải là 6 và tốc độ là 20, 13 máy bay nhỏ với tốc độ là 10 và trọng tải là 2, 13 máy bay nhỏ với tốc độ là 10 và trọng tải là 3. 24 - Kết quả thuật toán khi chạy với giá trị T và M khác nhau của tác giả 25 26 - Kết quả thuật toán khi chạy với giá trị T và M khác nhau tự tìm được T M Delay Tự tìm được Delay Của tác giả 5 4 49.7 43.5 5 3 48.5 41.3 Thanks for listening 27