Chương I: "Iổng quan về bài toán lộ trình vận chuyển (VIRP)” trình bày các khái niệm và các biến thể cơ bản của bài toán VRP nói chung và bài toán VRP với hạn chế thời gian (VRPTW) nói riêng, một biến thế của bài toán VRP mà hiện nay được nghiên cứu và ứng dụng khá nhiều trong thực tế. Trong đó, chúng ta sẽ đi tìm hiểu chi tiết về mô hình toần học và các bài toán mở rộng của VRPTW. Chương 2: "Các phương pháp giải bài toán VRP" trình bày sơ lược về các phương pháp giải bài toán VRP bao gồm: các phương pháp giải đúng (thuật toán nhánh và cận, thuật toán nhánh và cất) và các phương pháp giải gần đúng (thuật toần beuristic cổ điển và thuật toần mrelaheuristi ). TOM TAT Bài toán lộ trình vận chuyển với hạn chế về thời gian là một bài toần mở rộng của hài toán lộ trình vận chuyển nổi tiếng.
Sử dụng thuật toãn di truyền để giải bài toán VRPTW đã nhận được nhiễu sự quan tâm trong những năm gần đây. Trong VRTTW, một đội xe được khởi hành từ kho chứa tới phục vụ ruột số khách hồng tại các vị trí khác nhau trong các khung thời gian xác định và quay trở về kho chứa. Luận văn này đã đưa ra một phương pháp giải bài toán VRPTW sử dụng thuật toán di truyền song song. Thuật toán sử dụng một chuỗi số nguyên để biểu diễn vị trí các khách hàng trong các lộ trmh và quần thể ban dầu dược khởi tạo bằng thuật toán chén heuristic (Push Forard Insertion Heuristic).
Bên cạnh đổ, luận văn đã trình bầy ba mô hình song song cho thuật giẫ: dì truyền: Master-SIave, Island và Celular. và sử dụng mô hình Master-Slave để giả bài toán VRPTW. Cuối cùng, thuật toán đã được thực nghiệm trên 56 bài toán chuẩn của Solomon và được so sánh với các lời giải tốt nhất hiện nay theo phương pháp hcuristic. Từ khoá: lộ Irinh vận chuyển, thuật.
toán di Iruyền, thuật toán di truyễn song song, LỜI CẢM ƠN Tôi xin chân thành cám ơn các tổ chức, cá nhân đã giúp dỡ tôi về mặt nội dung của luận văn. Sự giúp đỡ đó đã giúp Lôi vượt qua nhiều khó khăn để hoàn thành luận văn nghiên cứu của mình "Tôi xim tran trọng cảm ơn: -_ Viên đão tạo Sau đạt học - 'Irường Đại học Hách Khoa Hà Nội -_ Các thấy, cô giáo trong Viện Công nghệ thông tin và Truyền thông, và trong bộ môn Khoa học máy tính cùng toàn thể các bạn đồng nghiệp. Vũ đặc biệu tôi xin chân thành cám ơn thấy giáo, PGS. Nguyễn Đức Nghĩa người đã Irực tiếp hướng dẫn và chơ tôi những ý kiến quý báu để lôi có được thành quả hôm nay.
1rong một khoảng thời gian ngắn, những nội dung được trình bảy trong luận văn chắc chưa đẩy đủ và còn thiếu sót. Nội đung của luận văn sẽ còn được tiếp tục nghiên cứu, hy vọng tiếp tục nhận dược những ý kiến dóng góp cha moi người để luận văn được hoàn thiện hơn trong thời gian tới Hà Nội, ngày. nâm 2009 Tac giả luận vẫn Nguyễn Thị Quỳnh Vinh LỜI CẢM ƠN Tôi xin chân thành cám ơn các tổ chức, cá nhân đã giúp dỡ tôi về mặt nội dung của luận văn. Sự giúp đỡ đó đã giúp Lôi vượt qua nhiều khó khăn để hoàn thành luận văn nghiên cứu của mình "Tôi xim tran trọng cảm ơn: -_ Viên đão tạo Sau đạt học - 'Irường Đại học Hách Khoa Hà Nội -_ Các thấy, cô giáo trong Viện Công nghệ thông tin và Truyền thông, và trong bộ môn Khoa học máy tính cùng toàn thể các bạn đồng nghiệp.
Vũ đặc biệu tôi xin chân thành cám ơn thấy giáo, PGS. Nguyễn Đức Nghĩa người đã Irực tiếp hướng dẫn và chơ tôi những ý kiến quý báu để lôi có được thành quả hôm nay. 1rong một khoảng thời gian ngắn, những nội dung được trình bảy trong luận văn chắc chưa đẩy đủ và còn thiếu sót. Nội đung của luận văn sẽ còn được tiếp tục nghiên cứu, hy vọng tiếp tục nhận dược những ý kiến dóng góp cha moi người để luận văn được hoàn thiện hơn trong thời gian tới Hà Nội, ngày.
nâm 2009 Tac giả luận vẫn Nguyễn Thị Quỳnh Vinh GIỚI THIỆU Trong những thập niên gần đây, sử dụng các gói phần mềm tối ưu để quản lý hiệu quả quá trình cung cấp hàng hóa và dịch vụ trong hệ thống phân phối ngày căng tăng, Phần lớn các ứng dụng thực tế dã chỉ ra rằng, máy tính hóa những thủ tục cho quá trình lập kế hoạch phân phối sản phẩm tết kiệm được chỉ phí đáng kế (thông thường lữ 5% tới 20%) trong tuần bộ chỉ phí vận chuyển. Dễ dàng thấy lác động của khoãn tiết kiệm này đến chỉ phí sản xuất sản xuất nói chung và giá thành sẵn phẩm nói riêng là không nhổ. Bài toán lộ trình vận chuyển (VRP) được đưa ra dấu tiên bởi Danzig và Ranscr (1959), với ứng dụng phân phối xảng dầu cho nhà ga, đã dành dược sự quan tâm rất lớn của nhiều nhà khoa học. Đã có hàng trâm cấc mô hình và thuật tgần khác nhau eho các phiên bản cũa VRP.
Hiện nay, một biến thể của VRP, VRP với hạn chế thời gian (VRPLW), được nghiên cứu và ứng dụng khá nhiều trong thực tế, như các ứng dụng đọn đẹp đường phố, dịnh hướng lộ trình xe bus, chuyên chở người khuyết tật, lập lịch quá trình phân phối hàng hoá cho người bán hàng. Với những ý nghĩa thực tiễn đồ của bài Loan, 101 chọn để ¡ luận văn tốt nghiệp là: “Thuật toán dĩ truyền song song giải bài toân lộ trình vận chuyển với hạn chế thời gian (VRPTW)” Nội dung của luận văn dược trình bày như sau: Chương I: "Iổng quan về bài toán lộ trình vận chuyển (VIRP)” trình bày các khái niệm và các biến thể cơ bản của bài toán VRP nói chung và bài toán VRP với hạn chế thời gian (VRPTW) nói riêng, một biến thế của bài toán VRP mà hiện nay được nghiên cứu và ứng dụng khá nhiều trong thực tế. Trong đó, chúng ta sẽ đi tìm hiểu chi tiết về mô hình toần học và các bài toán mở rộng của VRPTW. Chương 2: "Các phương pháp giải bài toán VRP" trình bày sơ lược về các phương pháp giải bài toán VRP bao gồm: các phương pháp giải đúng (thuật toán nhánh và cận, thuật toán nhánh và cất) và các phương pháp giải gần đúng (thuật toần beuristic cổ điển và thuật toần mrelaheuristi ).
GIỚI THIỆU Trong những thập niên gần đây, sử dụng các gói phần mềm tối ưu để quản lý hiệu quả quá trình cung cấp hàng hóa và dịch vụ trong hệ thống phân phối ngày căng tăng, Phần lớn các ứng dụng thực tế dã chỉ ra rằng, máy tính hóa những thủ tục cho quá trình lập kế hoạch phân phối sản phẩm tết kiệm được chỉ phí đáng kế (thông thường lữ 5% tới 20%) trong tuần bộ chỉ phí vận chuyển. Dễ dàng thấy lác động của khoãn tiết kiệm này đến chỉ phí sản xuất sản xuất nói chung và giá thành sẵn phẩm nói riêng là không nhổ. Bài toán lộ trình vận chuyển (VRP) được đưa ra dấu tiên bởi Danzig và Ranscr (1959), với ứng dụng phân phối xảng dầu cho nhà ga, đã dành dược sự quan tâm rất lớn của nhiều nhà khoa học. Đã có hàng trâm cấc mô hình và thuật tgần khác nhau eho các phiên bản cũa VRP.
Hiện nay, một biến thể của VRP, VRP với hạn chế thời gian (VRPLW), được nghiên cứu và ứng dụng khá nhiều trong thực tế, như các ứng dụng đọn đẹp đường phố, dịnh hướng lộ trình xe bus, chuyên chở người khuyết tật, lập lịch quá trình phân phối hàng hoá cho người bán hàng. Với những ý nghĩa thực tiễn đồ của bài Loan, 101 chọn để ¡ luận văn tốt nghiệp là: “Thuật toán dĩ truyền song song giải bài toân lộ trình vận chuyển với hạn chế thời gian (VRPTW)” Nội dung của luận văn dược trình bày như sau: Chương I: "Iổng quan về bài toán lộ trình vận chuyển (VIRP)” trình bày các khái niệm và các biến thể cơ bản của bài toán VRP nói chung và bài toán VRP với hạn chế thời gian (VRPTW) nói riêng, một biến thế của bài toán VRP mà hiện nay được nghiên cứu và ứng dụng khá nhiều trong thực tế. Trong đó, chúng ta sẽ đi tìm hiểu chi tiết về mô hình toần học và các bài toán mở rộng của VRPTW. Chương 2: "Các phương pháp giải bài toán VRP" trình bày sơ lược về các phương pháp giải bài toán VRP bao gồm: các phương pháp giải đúng (thuật toán nhánh và cận, thuật toán nhánh và cất) và các phương pháp giải gần đúng (thuật toần beuristic cổ điển và thuật toần mrelaheuristi ).
Chương 3: "Thuật toần di truyền” trình bày các khái niệm cơ bản về thuật toán di truyén va tìm hiểu ba mô hình song song cho thuật toán di truyền: mô hình Master slave, md hinh Island vi mf tinh Cenlluiar, Chương 4: “Thuật toán di truyền song song cho bài toán VRPTW" trình bày thuật toán di truyền cho bài toán VRPTW và áp dụng mô hình master-siavc cho thuật toán dị truyền khi giải bài toán VKPTW Chương 5: “Cài đặt và chạy thực nghiệm”. Chương này trình bày kiến trúc của hệ thống máy tính được sử dụng để cài đặt chương trình và trình bày hệ thống chương trình sẽ dược chạy thực nghiệm trên ộ dữ liệu của Solomon. Đây là bộ dữ li phd biến thường được sử dựng cho các bài loán VRP. Sau đồ, tổng hợp các kết quả đã đạt được của thực nghiệm và thực hiện so sánh kết quả đạt được của chương trình với các lời giải được biết là tốt nhất hiện nay, ABSTRACT The Vehicle Routing Probicm with Time Windows is an extensive of the well-known Vehicle Routing Problem (VRP).
Using genetic algorithm to solve Vehicle Routing Problem with Time Windows (VRPTW) has received considerable altention im recent years. In the VRPTW, a fleet of verticles set-off (ror a depot to serve a number of customers at detterent geographic locations with various demands within specific time windows before returning to the depot eventually. This thesis proposes an approach for the solving VRPTW using a parallel genetic algorithm. The algoritim uscs an inleger representation in which a string ol customer identifiers represents the sequence of deliveries covered by each of the veliicles and the mitial population 1s mrtialized using Push Forard Insertion Heuristic (PIM).
In addition, the thesis has presented three main parallelization models for genetic algorithms: master-slave, island and cellular, and uses a master-slave model to solve the VRPTW problem.