- TÓM TẮT LUẬN VĂN THẠC SĨĐề tài: Bài toán định tuyến cho mạng phương tiện giao thôngTác giả luận văn: Hà Trọng Sỹ Khóa: CH2015BNgười hướng dẫn: TS. - Tạ Anh SơnTừ khóa: Vehicle Routing Problem, Multi-depot Pickup and DeliveryProblem, Tabu Search, DC Programming, DCA-CUT, Mixed Integer Lin-ear Programming.Nội dung tóm tắt:a) Lý do chọn đề tàiNgày nay, bài toán vận tải đóng vai trò vô cùng quan trọng trongcuộc sống hàng ngày của chúng ta. - Trong đókhâu quan trọng nhất là vận tải, logistic chiếm khoảng 40% chi phí. - Bởi vậy, nghiêncứu về bài toán định tuyến (VRP - Vehicle Routing Problem) nói chungkhông chỉ giúp giảm chi phí vận tải, mà còn đóng góp vào việc bảo vệmôi trường.Trong thời đại công nghệ thông tin hiện nay, một trong những nghànhphát triển nhanh nhất đồng thời mang lại lợi nhuận khổng lồ là thươngmại điện tử. - Các công ty trong lĩnh vựcthương mại điện tử phần lớn có chiến lược vận chuyển hàng hóa từ nhà1 cung cấp tới khách hàng thông qua các trạm hay trung tâm giao vận.Họ không lưu trữ một lượng hàng sẵn của các nhà cung cấp trong kho,chỉ khi nào phát sinh đơn hàng từ khách hàng thì họ mới lấy hàng từnhà cung cấp về kho hoặc trạm của họ trước khi giao khách hàng, điềunày giúp giảm phần lớn chi phí kho bãi cho công ty. - Do đó công việcvận chuyển hàng hóa tới tay khách hàng cũng là công việc quan trọngnhất trong ngành thương mại điện tử. - Việc xây dựng một mô hình vậntải hợp lý và tối ưu hóa chi phí vận chuyển ảnh hưởng rất lớn đến lợinhuận của công ty. - Một trong những mô hình hiện đang được áp dụngtại nhiều công ty thương mại điện tử ở Việt Nam được mô tả trong luậnvăn này.Mô hình vận tải được xem xét ở đây là một dạng cụ thể của bàitoán định tuyến, thuộc lớp các bài toán lấy và giao hàng - Pickup andDelivery Problem (PDP). - Nhìn chung, yêu cầu cơ bản trong lớp các bàitoán này là: có một tập các đơn hàng cần được xử lý bằng cách vậnchuyển hàng từ nhà cung cấp đến khách hàng. - Mô hình ta quan tâm đến ởđây được mô tả và có các yêu cầu cụ thể như sau:• Bài toán thiết lập trên một vùng lãnh thổ, khách hàng và nhà cungcấp đều thuộc trong lãnh thổ này.• Có N đơn hàng cần xử lý, mỗi đơn hàng cần được xử lý vận chuyểntừ nhà cung cấp (nơi bán) đến khách hàng.• Có S trung tâm xử lý đơn hàng được thiết lập sẵn, ta gọi là trạmgiao nhận (depot). - Đơn hàng luôn được thông qua trạm giao nhậntrước khi đến tay khách hàng.• Mỗi trạm có một số lượng xe phục vụ công việc lấy hàng và giaohàng.• Mỗi nhà cung cấp hoặc khách hàng sẽ được trạm giao nhận gầnnhất phụ trách, tức là công việc lấy hàng hoặc giao hàng sẽ do xexuất phát từ trạm đó đến xử lý.• Nếu trong một đơn hàng, nhà cung cấp và khách hàng do hai trạm2 khác nhau phụ trách, thì đơn hàng sẽ được trung chuyển từ trạmphụ trách lấy hàng sang trạm phụ trách giao hàng.Bài toán tối ưu tuyến xe cho mô hình này được gọi là Bài toán giaovận thông qua nhiều trạm - Multi-depots Pickup and Delivery Problemwith Transferring (MDPDPT). - Tổng quát, bài toán MDPDPT mô tảnhư sau:1. - Đầu vào:• Vị trí tọa độ của N cặp nhà cung cấp - khách hàng, S trạmgiao nhận.• Ma trận chi phí đi lại giữa các điểm ở trên.• Danh sách số lượng hàng hóa mỗi khách hàng yêu cầu.2. - Đầu ra: Tập các tuyến xe, lộ trình của từng tuyến xe đi qua lần lượtnhững điểm nào, xử lý những đơn hàng nào.Bài toán này là một bài toán tối ưu tổ hợp thuộc lớp các bài toánNP-khó. - Một số thuật toán có thể tìm chính xác nghiệm tối ưu của bàitoán này. - Tuy nhiên chúng chỉ hạn chế cho bài toán kích thước nhỏ vìthời gian chạy thuật toán thường rất lớn. - Trong thực tế, ta thường phảixử lý hàng trăm hoặc thậm chí tới hàng nghìn đơn hàng, nên các thuậttoán giải chính xác thường khó thể áp dụng được. - Trong khi đó, cácthuật toán heuristic có thể cung cấp một lời giải gần với nghiệm tốiưu với thời gian chạy chấp nhận được. - Những năm gần đây, các thuậttoán heuristic đã được áp dụng thành công vào rất nhiều bài toán địnhtuyến với quy mô lớn trong thực tế. - Trong đó, thuật toán Tabu Searchdần được đề cử là thuật toán tốt nhất giải các bài toán VRP nói chung.Trong luận văn này, thuật toán Tabu Search được áp dụng và chỉnh sửacho phù hợp với bài toán MDPDPT và hi vọng có thể áp dụng kết quảvào thực tế.Bên cạnh đó, thuật toán DCA-CUT sẽ được áp dụng để cải thiệnkết quả thu được từ thuật toán Tabu Search. - Thuật toán này đã đượcthử nghiệm trên bài toán quy hoạch nguyên hỗn hợp 0 - 1 (MIP) và chokết quả khả quan. - Trong luận văn này, bài toán MDPDPT sẽ được mô3 hình hóa dưới dạng một bài toán MIP, từ đó ta có thể dễ dàng áp dụngthuật toán DCA-CUT.b) Mục đích nghiên cứuMục đích của Luận văn là mô hình hóa cho một bài toán giao vậnthực tế, tìm cách áp dụng giải thuật Tabu Search và thuật toán DCA-CUT để tìm lời giải cho bài toán. - Đánh giá kết quả đạt được và khả năngáp dụng vào thực tế để giảm chi phí vận hành cho các công ty đang sửdụng mô hình giao vận này.c) Đối tượng và phạm vi nghiên cứu• Nghiên cứu mô hình giao vận thông qua nhiều trạm, có sự trungchuyển hàng hóa giữa các trạm.• Tìm hiểu giải thuật Tabu Search, nghiên cứu cách triển khai cho bàitoán MDPDPT.• Ứng dụng thuật toán DCA-CUT vào giải bài toán MDPDPT và cảithiện kết quả thu được từ Tabu Search.• Đánh giá kết quả thuật toán trên các bộ dữ liệu trong khoảng 200điểm, tương ứng 100 cặp nhà cung cấp - khách hàng.d) Các kết quả chính của luận vănLuận văn trình bài các kết quả chính sau:• Đề xuất mô hình toán học cho bài toán MDPDPT dưới dạng mộtbài toán MIP.• Áp dụng thuật toán Tabu Search được đề xuất bởi Min Wen (2009)cho bài toán MDPDPT. - Kết quả thử nghiệm thu được trên các bộdữ liệu kích thước trong khoảng 200 điểm, tương ứng 100 cặp nhà4 cung cấp - khách hàng, cho thấy tính khả thi của thuật toán nếuáp dụng vào thực tế.• Thuật toán DCA-CUT cũng được trình bày và áp dụng cho bàitoán MDPDPT. - Thuật toán DCA-CUT giải bài toán MIP đã đượctrình bày trong báo cáo "Solving Relaxation Orienteering Problemusing DCA-CUT" tại hội nghị MCO 2015 (Conference on Mod-elling, Computation and Optimization in Information Systems andManagement Sciences). - Trong báo cáo trên, thuật toán DCA-CUTđã được áp dụng cho bài toán "Orienteering Problem", đây cũnglà một dạng của bài toán định tuyến, thuật toán đã cho thấy sựhiệu quả bước đầu của thuật toán. - Trong luận văn này, thuật toánDCA-CUT được áp dụng với điểm xuất phát là lời giải lấy từ kếtquả chạy thuật toán Tabu Search. - Kết quả cho thấy DCA-CUT đãcải thiện được lời giải, cho ta kết quả tốt hơn.Luận văn được trình bày theo bố cục sau: Chương 1 mô tả bài toánMDPDPT và trình bày mô hình toán học của bài toán này dưới dạngmột bài toán MIP. - Chương 2 trình bày hai thuật giải được áp dụng chobài toán này: thuật toán Tabu Search và thuật toán DCA-CUT. - Chương3 trình bày các kết quả thử nghiệm và đánh giá khả năng áp dụng thựctế của thuật toán.e) Phương pháp nghiên cứu• Nghiên cứu tài liệu khoa học về các bài toán VRP, các mô hình toánhọc.• Nghiên cứu tổng quan về các thuật giải đã được áp dụng cho cácbài toán VRP.• Nghiên cứu lý thuyết và cách áp dụng thuật toán Tabu Search.• Nghiên cứu thuật toán DCA-CUT và áp dụng cho bài toán MD-PDPT.5
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt