- TẠ ANH SƠN Hà Nội – 2016 Mục lụcLời cam đoan 3Danh mục các kí hiệu, chữ viết tắt 4Danh sách các bảng 5Danh sách các hình vẽ 6Mở đầu 71 Bài toán giao vận thông qua nhiều trạm 141.1 Mô tả bài toán. - 141.2 Mô hình toán học. - 232 Thuật giải cho bài toán MDPDPT 242.1 Thuật toán Tabu Search. - 302.2 Thuật toán DCA-CUT. - 312.2.1 Thuật toán DCA. - 312.2.2 Thuật toán DCA-CUT giải bài toán MIP. - 333 Kết quả thử nghiệm 383.1 Dữ liệu. - 383.2 Kết quả. - 403.2.1 Thuật toán Tabu Search. - 403.2.2 Thuật toán DCA-CUT. - 421 Kết luận 442 Lời cam đoanTôi xin cam đoan Luận văn thạc sĩ "Bài toán định tuyến trong mạngphương tiện giao thông" là công trình nghiên cứu của riêng tôi. - Các sốliệu, kết quả nêu trong Luận văn là trung thực và chưa từng được aicông bố trong bất kỳ công trình nào khác. - Tôi xin cam đoan rằng mọi sựgiúp đỡ cho việc thực hiện Luận văn này đã được cảm ơn và các thôngtin trích dẫn trong Luận văn đã được chú thích nguồn gốc rõ ràng, minhbạch.Tôi xin hoàn toàn chịu trách nhiệm về lời cam đoan trên.Học viên thực hiện Luận vănHà Trọng Sỹ3 Danh mục các kí hiệu, chữ viết tắtVRP Vehicle Routing Problem - bài toán địnhtuyến xeMDPDPT Multi-depot Pickup and Delivery problemwith Transfering - bài toán giao vận quanhiều trạm, có trung chuyểnB&B Branch and Bound - thuật toán nhánh cậnB&P Branch and PriceB&C Branch and CutTS thuật toán tìm kiếm Tabudepot trạm giao nhậnneighborhood phương án lân cậnmove bước di chuyển|N| số phần tử của tập hợp NMIP Mixed Integer Problem - bài toán quyhoạch nguyên hỗn hợp4 Danh sách bảng3.1 Dữ liệu thử nghiệm. - 403.2 Kết quả thử nghiệm Tabu Search. - 413.3 Kết quả thử nghiệm DCA-CUT. - 435 Danh sách hình vẽ1.1 Ví dụ bài toán MDPDPT. - 172.1 Bài toán MDPDPT với 5 đơn hàng, 2 trạm. - 293.1 Bài toán MDPDPT với c = 20, d = 3. - 393.2 Bài toán MDPDPT với c = 20, d = 3. - 393.3 Nghiệm bài toán MDPDPT với c = 20, d = 3 từ thuậttoán TS. - 426 Mở đầuLý 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. - 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à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ều7 nà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ạmkhá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 giao8 vậ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. - 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 ([1]) sẽ được áp dụng để cảithiện kết quả thu được từ thuật toán Tabu Search. - Thuật toán này đãđược thử nghiệm trên bài toán quy hoạch nguyên hỗn hợp 0 - 1 (MIP)và cho kết quả khả quan. - Trong luận văn này, bài toán MDPDPT sẽđược mô hình hóa dưới dạng một bài toán MIP, từ đó ta có thể dễ dàngáp dụng thuật toán DCA-CUT.9 Lịch sử nghiên cứuBài toán MDPDPT được giới thiệu trong đề tài này là một biến thểmới trong bài toán định tuyến và thuộc lớp các bài toán lấy và giaohàng (Pickup and Delivery Problem - PDP). - Bài toán MDPDPT xemxét việc giao nhận hàng thông qua nhiều trạm (multi-depot), mỗi mónhàng cần đi qua trạm trước khi được giao (cross-docking), có sự trungchuyển hàng giữa các trạm và đồng thời cân nhắc đến khung thời giangiao nhận (time windows).Đã có rất nhiều những nghiên cứu trên các biến thể khác nhau củabài toán PDP từ khoảng ba thập kỷ trở lại đây. - (2008a,b) đã chia các bài toán dạngnày thành hai lớp con: lớp đầu tiên là các bài toán vận chuyển hàng hóatừ điểm lấy đến trạm và từ trạm đến khách hàng, trong khi đó lớp thứ2 gồm cái bài toán vận chuyển hàng hóa trực tiếp từ điểm lấy đến điểmgiao. - Đặc điểm chung của các bài toán dạng này là giai đoạn lấy hàngluôn phải thực hiện trước khi bắt đầu thực hiện giao hàng. - Bài toánMDPDPT được xét đến trong luận văn này thuộc về lớp con thứ nhất.Bài toán có độ tương quan gần nhất với bài toán MDPDPT được xétđến ở đây là bài toán lấy và giao hàng qua trạm (Pickup and DeliveryProblem with Cross-Docking - PDPCD. - Bài toán PDPCD tổng quátmiêu tả việc vận chuyển hàng hóa từ một tập các nhà cung cấp đến mộttập các khách hàng tương ứng thông qua một trạm (cross-dock). - Những năm gần đây cũng đã cónhiều nghiên cứu trên các mô hình cụ thể được đưa ra. - Trong số đó, bài toán được xét đếntrong Lee et al. - (2010) có môhình tương quan nhất với bài toán của chúng ta, mỗi phương tiện thựchiện việc lấy hàng và giao hàng theo từng giai đoạn riêng rẽ.10 Trong Lee et al. - (2006), Lee, Jung and Lee đã giải bài toán với thiếtlập một trạm cross-dock duy nhất, nhiều nhà cung cấp và nhiều kháchhàng, thời gian phục vụ được xét đến ràng buộc cho khách hàng. - Các tác giả đã mô hình bài toán dưới dạng một bài toán quy hoạchnguyên hỗn hợp (mixed integer programming - MIP) và đề xuất mộtthuật toán gần đúng dựa trên thuật toán tabu search.Wen et al. - (2008) cũng đã phát triển một mô hình quy hoạch nguyênhỗn hợp để giải bài toán VRP với cross-docking và thời gian phục vụ tạicác điểm được ràng buộc. - Mục tiêu bài toán là giảm thiểu tổng thời giandi chuyển của các phương tiện. - Các tác giả đã giải bài toán bằng thuậttoán tabu search kết hợp với một thủ tục được gọi là adaptive memoryprocedure (AMP). - Thuậttoán tabu search đã được các tác giả cải tiến bằng cách kết hợp hai cáchtìm kiếm lân cận ở trên để đạt được kết quả tốt hơn. - Luận văn này cũngsẽ áp dụng thuật toán kết hợp trên cho bài toán MDPDPT.Liao et al. - (2010) đã mở rộng kết quả của Lee et al. - (2006) và cũngđề xuất thuật toán dựa trên tabu search, với mục tiêu giảm thời gianthực thi và giảm số lượng xe được sử dụng. - (2006), với cùngtham số đầu vào và so sánh thời gian thực thi.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.11 Đố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.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 cho bài toán MDPDPT. - Kết quả thử nghiệm thu được trên cácbộ dữ liệu kích thước trong khoảng 200 điểm, tương ứng 100 cặpnhà cung cấp - khách hàng, cho thấy tính khả thi của thuật toánnế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) [1]. - Trong báo cáo trên, thuật toán DCA-CUT đã được áp dụng cho bài toán "Orienteering Problem", đâycũng là một dạng của bài toán định tuyến, thuật toán đã cho thấysự hiệu quả bước đầu của thuật toán. - Trong luận văn này, thuậttoán DCA-CUT được áp dụng với điểm xuất phát là lời giải lấy từ12 kết quả 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.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.13 Chương 1Bài toán giao vận thông qua nhiềutrạmTrong chương này, bài toán MDPDPT sẽ được mô hình hóa thànhmột bài toán quy hoạch nguyên hỗn hợp (MIP). - Cách thức xây dựng môhình toán học cho bài toán này được tham khảo từ các bài toán VRPwith Cross-Docking có mô hình gần tương tự trong Wen et al. - (2008) vàtừ tài liệu [9], sau đó bổ sung thêm các biến và ràng buộc cho phù hợpvới bài toán.1.1 Mô tả bài toánBài toán MDPDPT dựa trên mô hình giao vận nhằm vận chuyểnhàng hóa từ một tập các nhà cung cấp đến các khách hàng tương ứngthông qua một tập các trạm giao nhận trên một vùng cụ thể. - Mỗi mộtđơn hàng được định nghĩa là một yêu cầu mua hàng từ một nhà cungcấp đến một khách hàng, khách hàng có thể mua nhiều đơn hàng khácnhau. - Vùng được chia thành các khu vực riêng rẽ, mỗi khu vực đượcthiết lập một trạm giao nhận, trạm này sẽ phụ trách tất cả các địa điểmtrong khu vực của nó, bao gồm việc lấy hàng từ nhà cung cấp và giaohàng tới khách hàng trong khu vực. - Với mỗi một đơn hàng như vậy, góihàng tương ứng sẽ được lấy hàng bởi trạm giao nhận gần nhất và đượcgiao bởi trạm giao nhận trong khu vực mà khách hàng ở
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt