Luận văn thạc sĩ quản lý xây dựng tối ưu hóa bình đồ công trường bằng thuật toán tối ưu đàn kiến aco

Luận văn thạc sĩ nghiên cứu quản lý xây dựng tối ưu hóa bình đồ công trường bằng thuật toán tối ưu đàn kiến aco, đánh giá hiện trạng, phân tích vấn đề, đề xuất biện pháp hoàn

• Tác giả: Lương Công Luật
• Người hướng dẫn: TS. Phạm Vũ Hồng Sơn
• Trường học: Đại học Bách Khoa, Đại học Quốc gia Thành phố Hồ Chí Minh
• Chuyên ngành: Quản lý xây dựng
• Đề tài: Tối ưu hóa bình đồ công trường bằng thuật toán đàn kiến ACO
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2019
• Địa điểm: Thành phố Hồ Chí Minh

Mục lục chi tiết

• LỜI CẢM ƠN
• TÓM TẮT
• ABSTRACT
• LỜI CAM ĐOAN
• DANH MỤC BẢNG
• MỤC LỤC HÌNH ẢNH
• DANH SÁCH CÁC CHỮ VIẾT TẮT
• 1. CHƯƠNG 1: ĐẶT VẤN ĐỀ
• 1.1. Giới thiệu chung
• 1.2. Nghiên cứu, mục tiêu và giả thiết
• 1.3. Phạm vi nghiên cứu
• 1.4. Phương pháp nghiên cứu
• 1.5. Bố cục của luận văn
• 2. CHƯƠNG 2: TỔNG QUAN
• 2.1. Tổng quan các nghiên cứu về đàn kiến và tối ưu công trường
• 2.2. Nhận xét chung về các thuật toán ACO
• 3. CHƯƠNG 3: PHƯƠNG PHÁP NGHIÊN CỨU
• 3.1. Từ kiến thực đến kiến nhân tạo
• 3.2. Phương pháp thuật toán ACO
• 3.3. Những kết quả đạt được từ thuật toán ACO từ các nghiên cứu
• 4. CHƯƠNG 4: THUẬT TOÁN TỐI ƯU HÓA ĐÀN KIẾN
• 4.1. Khởi tạo giải pháp ban đầu trong thuật toán ACO
• 4.2. Mô hình thuật toán ACO
• 5. CHƯƠNG 5: BÀI TOÁN CỤ THỂ
• 5.1. Nghiên cứu đơn giản để minh họa vấn đề bố trí công trường xây dựng
• 5.2. Xây dựng hàm chi phí cho bình đồ công trường
• 5.3. Mô tả bài toán
• 6. CHƯƠNG 6: KẾT LUẬN VÀ KIẾN NGHỊ

Tóm tắt

I. Giới thiệu chung

Luận văn thạc sĩ này tập trung vào việc tối ưu hóa bình đồ công trường bằng cách sử dụng thuật toán đàn kiến ACO. Bố trí công trường xây dựng là một bước quan trọng trong quá trình thiết kế thi công, nhằm xác định biện pháp thi công hiệu quả nhất. Việc bố trí các cơ sở vật chất vào các vị trí thích hợp là một bài toán phức tạp, đòi hỏi sự tối ưu hóa để giảm thiểu chi phí và thời gian vận chuyển. Thuật toán ACO được đề xuất như một giải pháp hiệu quả để giải quyết vấn đề này, với khả năng tìm kiếm địa phương và toàn cục đồng thời.

1.1. Mục tiêu nghiên cứu

Mục tiêu chính của nghiên cứu là áp dụng thuật toán ACO để tối ưu hóa bình đồ công trường, giúp các nhà quản lý xây dựng đưa ra quyết định hiệu quả hơn. Nghiên cứu cũng nhằm so sánh hiệu quả của ACO với các phương pháp tối ưu hóa khác trong việc giải quyết các vấn đề bố trí công trường.

1.2. Phạm vi nghiên cứu

Nghiên cứu tập trung vào việc bố trí các cơ sở vật chất trên công trường xây dựng, bao gồm các yếu tố như khoảng cách, chi phí vận chuyển và hiệu quả sử dụng không gian. Thuật toán ACO được áp dụng để tìm ra giải pháp tối ưu nhất cho các bài toán này.

II. Tổng quan về thuật toán ACO

Thuật toán đàn kiến ACO là một phương pháp tối ưu hóa dựa trên nguyên lý hoạt động của đàn kiến tự nhiên. Kiến để lại vết mùi (pheromone) trên đường đi, giúp các con kiến khác tìm được đường ngắn nhất đến nguồn thức ăn. ACO mô phỏng quá trình này để giải quyết các bài toán tối ưu hóa phức tạp. Trong nghiên cứu này, ACO được sử dụng để tối ưu hóa bố trí công trường, với khả năng tìm kiếm địa phương và toàn cục đồng thời.

2.1. Nguyên lý hoạt động của ACO

Thuật toán ACO hoạt động dựa trên việc mô phỏng hành vi của đàn kiến. Các 'con kiến nhân tạo' di chuyển trong không gian tìm kiếm, để lại vết mùi trên các đường đi. Vết mùi này được cập nhật liên tục, giúp các con kiến khác tìm được đường đi tối ưu nhất. Quá trình này được lặp lại cho đến khi tìm ra giải pháp tốt nhất.

2.2. Ưu điểm của ACO

ACO có nhiều ưu điểm trong việc giải quyết các bài toán tối ưu hóa phức tạp, đặc biệt là khả năng tìm kiếm địa phương và toàn cục đồng thời. Ngoài ra, ACO có thể xử lý các bài toán có nhiều ràng buộc và biến số, giúp nâng cao hiệu quả trong việc bố trí công trường.

III. Ứng dụng ACO trong tối ưu hóa bình đồ công trường

Nghiên cứu này đề xuất việc áp dụng thuật toán ACO để tối ưu hóa bình đồ công trường. Bằng cách mô phỏng hành vi của đàn kiến, ACO giúp tìm ra vị trí tối ưu cho các cơ sở vật chất trên công trường, giảm thiểu chi phí vận chuyển và tăng hiệu quả sử dụng không gian. Kết quả nghiên cứu cho thấy ACO có hiệu quả vượt trội so với các phương pháp tối ưu hóa truyền thống.

3.1. Mô hình hóa bài toán

Bài toán tối ưu hóa bình đồ công trường được mô hình hóa dưới dạng bài toán phân công bậc hai (QAP). ACO được sử dụng để tìm ra giải pháp tối ưu cho bài toán này, với các ràng buộc về khoảng cách, chi phí và hiệu quả sử dụng không gian.

3.2. Kết quả thực nghiệm

Kết quả thực nghiệm cho thấy ACO có khả năng tìm ra giải pháp tối ưu cho bài toán bố trí công trường một cách hiệu quả. So với các phương pháp truyền thống, ACO giảm thiểu chi phí vận chuyển và tăng hiệu quả sử dụng không gian, giúp nâng cao hiệu quả quản lý công trường.

IV. Kết luận và kiến nghị

Nghiên cứu đã chứng minh rằng thuật toán ACO là một công cụ hiệu quả để tối ưu hóa bình đồ công trường. Việc áp dụng ACO giúp các nhà quản lý xây dựng đưa ra quyết định chính xác hơn, giảm thiểu chi phí và tăng hiệu quả sử dụng không gian. Nghiên cứu cũng đề xuất việc mở rộng ứng dụng ACO trong các lĩnh vực khác của quản lý xây dựng.

4.1. Giá trị thực tiễn

Nghiên cứu này mang lại giá trị thực tiễn cao trong việc quản lý công trường xây dựng. ACO giúp tối ưu hóa bố trí các cơ sở vật chất, giảm thiểu chi phí và thời gian vận chuyển, đồng thời nâng cao hiệu quả sử dụng không gian.

4.2. Hướng phát triển trong tương lai

Trong tương lai, nghiên cứu có thể mở rộng ứng dụng ACO trong các lĩnh vực khác của quản lý xây dựng, như quản lý tiến độ, quản lý chi phí và quản lý rủi ro. Việc kết hợp ACO với các công nghệ mới như AI và IoT cũng là một hướng nghiên cứu tiềm năng.

Nội dung chính

Tổng quan nghiên cứu

Trong quản lý dự án xây dựng hiện đại, chi phí logistics và xử lý nguyên vật liệu nội bộ chiếm từ 20% đến 50% tổng chi phí vận hành công trường. Việc bố trí mặt bằng thiếu khoa học có thể làm gia tăng khoảng 36% chi phí trung chuyển và gây lãng phí nghiêm trọng nguồn lực thi công. Vấn đề quy hoạch tổng mặt bằng công trường xây dựng (Construction Site Layout Problem - CSLP) là bài toán tối ưu hóa tổ hợp phi tuyến thuộc nhóm NP-khó. Khi số lượng cơ sở vật chất tạm thời đạt 10 hạng mục, số lượng phương án hoán vị không gian có thể lên tới 10! tương đương 3.628.800 kịch bản bố trí, khiến phương pháp lập kế hoạch dựa trên trực giác truyền thống không thể tìm ra lời giải tối ưu.

Mục tiêu trọng tâm của nghiên cứu là xây dựng mô hình thuật toán tối ưu hóa đàn kiến lai (Ant Colony Optimization - ACO) nhằm tự động hóa việc xác lập vị trí các công trình phụ trợ tạm thời như kho bãi, cần trục tháp, lán trại và trạm trộn. Đề tài tập trung giải quyết bài toán bố trí không gian theo thời gian thi công thực tế tại các dự án dân dụng quy mô lớn tại Thành phố Hồ Chí Minh trong giai đoạn năm 2019. Ý nghĩa thực tiễn của công trình thể hiện qua việc giảm thiểu tối thiểu 22% quãng đường di chuyển nội bộ, tiết kiệm từ 18% đến 25% chi phí vận chuyển phụ trợ, đồng thời rút ngắn 40% thời gian lập tổng mặt bằng so với phương pháp thủ công, góp phần đáp ứng các tiêu chuẩn quản lý xây dựng hiện hành.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu được thiết lập dựa trên nền tảng bài toán phân bổ bậc hai (Quadratic Assignment Problem - QAP) do Koopmans và Beckmann đề xuất từ năm 1957. Mô hình toán học này lượng hóa sự tương tác không gian giữa n cơ sở vật chất tạm thời và m vị trí khả dụng trên mặt bằng. Khung lý thuyết chủ đạo thứ hai là thuật toán tối ưu hóa đàn kiến (ACO) do Marco Dorigo công bố năm 1991, hoạt động dựa trên cơ chế phỏng sinh học mô phỏng tập tính tìm đường đi ngắn nhất của loài kiến thông qua nồng độ vết mùi pheromone nhân tạo.

Để khắc phục nhược điểm rơi vào điểm tối ưu cục bộ của các thuật toán Heuristic truyền thống, tác giả tích hợp lý thuyết hệ thống hỗn loạn (Chaotic System) và phương pháp học đối diện (Opposition-based Learning - OBL) vào khâu khởi tạo quần thể ban đầu. Ba khái niệm cốt lõi định hình mô hình bao gồm: hàm mục tiêu tối thiểu hóa tổng chi phí vận chuyển luân chuyển vật tư, ma trận khoảng cách Euclid giữa các tọa độ, và hệ số bay hơi vết mùi pheromone được thiết lập trong khoảng từ 0.1 đến 0.5 kết hợp thuật toán tìm kiếm cục bộ 2-opt.

Phương pháp nghiên cứu

Nghiên cứu sử dụng phương pháp mô phỏng số học kết hợp kiểm chứng thực nghiệm từ tháng 02 năm 2019 đến tháng 06 năm 2019. Nguồn dữ liệu sơ cấp và thứ cấp được trích xuất từ bản vẽ thiết kế thi công, bảng thống kê khối lượng và định mức vận chuyển vật tư của một công trình xây dựng thực tế. Cỡ mẫu nghiên cứu thực nghiệm bao gồm 11 hạng mục công trình tạm trọng yếu được phân bổ vào 11 vị trí không gian xác định trước, với kích thước quần thể thiết lập 30 cá thể kiến và thực hiện 500 vòng lặp cho mỗi kịch bản thử nghiệm.

Phương pháp chọn mẫu có chủ đích được áp dụng nhằm chọn lọc các hạng mục có tần suất lưu thông luân chuyển lớn như kho xi măng, xưởng gia công cốt thép, tháp cẩu và văn phòng điều hành. Lý do lựa chọn thuật toán lai ACO kết hợp tìm kiếm cục bộ là nhờ khả năng xử lý bài toán NP-khó vượt trội, giảm thiểu không gian tìm kiếm từ cấp số nhân xuống thời gian tính toán dưới 60 giây trên máy tính cá nhân. Quá trình tính toán được lập trình tự động hóa trên môi trường phần mềm kỹ thuật, đảm bảo độ lặp lại và kiểm soát sai số phương sai dưới 0.5% qua 50 lần chạy độc lập.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Quá trình mô phỏng thực nghiệm trên bài toán bố trí mặt bằng thi công đã mang lại bốn phát hiện khoa học mang tính đột phá:

Thứ nhất, thuật toán ACO đề xuất đã giảm 28.6% tổng chi phí vận hành và trung chuyển nội bộ so với phương án bố trí truyền thống dựa trên kinh nghiệm hiện trường, đồng thời tiết kiệm hơn 12.4% chi phí logistics so với thuật toán Di truyền (GA) kinh điển.

Thứ hai, tốc độ hội tụ của thuật toán lai cải tiến vượt bậc khi đạt đến nghiệm tối ưu toàn cục chỉ sau 85 vòng lặp, rút ngắn 42.3% thời gian xử lý so với thuật toán đàn ong nhân tạo (yêu cầu trung bình 148 vòng lặp) và nhanh hơn 35.1% so với thuật toán bầy đàn hạt (PSO).

Thứ ba, tổng quãng đường di chuyển vật tư và thiết bị giảm đáng kể từ 14.520 mét mỗi ca làm việc xuống còn 10.380 mét mỗi ca, tương ứng mức giảm 28.5% cự ly vận chuyển không sinh lời.

Thứ tư, trong bài toán quy hoạch mặt bằng động qua 3 giai đoạn thi công, chi phí tháo dỡ và tái định vị các cơ sở phụ trợ được cắt giảm tới 31.8% nhờ chiến lược phân bổ vị trí thông minh của thuật toán.

Thảo luận kết quả

Sự vượt trội của mô hình bắt nguồn từ cơ chế cân bằng động giữa khai thác thông tin cục bộ và khám phá không gian tìm kiếm toàn cục. Việc tích hợp hệ thống hỗn loạn đã ngăn ngừa hiện tượng sớm hội tụ vào nghiệm cục bộ sai lệch mà thuật toán nguyên bản thường gặp phải. Khi so sánh với các công bố quốc tế của Ning và Liu hoặc kết quả từ nhóm nghiên cứu của Gharaie, giải pháp lai của luận văn đạt sai số phương sai cực tiểu chỉ 0.08%, chứng minh độ tin cậy cơ bản trong việc hỗ trợ ra quyết định kỹ thuật.

Để trực quan hóa các phát hiện này trong báo cáo chuyên môn, dữ liệu nên được cấu trúc qua hai hình thức trình bày chuyên sâu. Biểu đồ đường đa trục mô tả đường cong hội tụ hàm mục tiêu chi phí qua 500 thế hệ lặp sẽ làm nổi bật tốc độ bắt kịp nghiệm tối ưu giữa ACO, GA và PSO. Song song đó, bảng ma trận đối chiếu cự ly tương tác trước và sau tối ưu hóa cùng biểu đồ nhiệt (Heatmap) mật độ di chuyển sẽ minh họa trực quan sự giải phóng các nút thắt giao thông nội bộ, giúp ban chỉ huy công trường dễ dàng thẩm định tính khả thi trên mặt bằng thực địa.

Đề xuất và khuyến nghị

Nhằm chuyển hóa kết quả nghiên cứu thành giá trị thực tiễn, bốn giải pháp quản lý thi công trọng tâm được đề xuất:

1. Chuẩn hóa quy trình số hóa mặt bằng công trường: Ban giám đốc doanh nghiệp xây dựng cần ban hành quy trình mô hình hóa thông tin công trình (BIM) kết hợp thuật toán ACO ngay trong quý 1 năm 2020, đặt mục tiêu cắt giảm 100% việc bố trí mặt bằng dựa trên cảm tính chủ quan và tiết kiệm tối thiểu 15% tổng chi phí phụ trợ thi công.
2. Tích hợp phần mềm tối ưu hóa vào hệ thống quản trị dự án: Phòng Kỹ thuật và Công nghệ thông tin chịu trách nhiệm phát triển công cụ tự động hóa tính toán logistics trên nền tảng máy tính trong thời hạn 6 tháng, hướng tới mục tiêu giảm 80% thời gian lập bản vẽ tổng mặt bằng thi công (từ 5 ngày xuống dưới 1 ngày làm việc).
3. Đào tạo nâng cao năng lực cho đội ngũ chỉ huy trưởng: Bộ phận Nhân sự và Ban điều hành dự án cần tổ chức các khóa huấn luyện chuyên sâu về ứng dụng trí tuệ nhân tạo và thuật toán Meta-heuristic trong quản lý thi công định kỳ 6 tháng một lần, đảm bảo 100% cán bộ kỹ thuật chủ chốt nắm vững phương pháp đánh giá hàm mục tiêu chi phí trước quý 3 năm 2020.
4. Thiết lập hệ thống giám sát và cập nhật mặt bằng động theo chu kỳ thi công: Chỉ huy trưởng công trường và Đội ngũ an toàn lao động phải tiến hành rà soát, tái cấu trúc vị trí kho bãi và thiết bị tạm thời sau mỗi 90 ngày hoặc khi chuyển đổi giai đoạn từ thi công cọc sang kết cấu thân, cam kết duy trì giảm trên 25% chi phí luân chuyển vật tư và giảm 30% xung đột giao thông nội bộ xuyên suốt vòng đời dự án.

Đối tượng nên tham khảo luận văn

Công trình nghiên cứu mang lại giá trị ứng dụng thiết thực cho bốn nhóm đối tượng chuyên môn:

1. Giám đốc điều hành và Ban quản lý dự án xây dựng: Tiếp cận phương pháp luận khoa học để kiểm soát ngân sách, giảm từ 20% đến 50% chi phí vận hành phụ trợ công trường thông qua việc chuẩn hóa quy hoạch tổng mặt bằng ngay từ giai đoạn đấu thầu.
2. Chỉ huy trưởng và Kỹ sư hiện trường: Ứng dụng mô hình tính toán tọa độ cơ sở vật chất tạm thời để giải quyết bài toán xung đột không gian thực tế, cắt giảm 28.5% quãng đường vận chuyển vật tư trong các dự án nhà cao tầng có diện tích đất hạn chế dưới 5.000 mét vuông.
3. Chuyên gia tư vấn và Kỹ sư lập biện pháp thi công: Sử dụng cấu trúc thuật toán ACO lai ghép như một công cụ tự động hóa thuyết minh biện pháp thi công, giúp rút ngắn 40% thời gian thiết kế hồ sơ kỹ thuật phục vụ thẩm định dự án.
4. Học viên cao học và Nhà nghiên cứu ngành Quản lý xây dựng: Kế thừa khung lý thuyết tối ưu hóa tổ hợp và thuật toán Meta-heuristic để phát triển các đề tài mở rộng trong việc giải quyết bài toán cân bằng Thời gian - Chi phí (TCO) hoặc quy hoạch an toàn công trường theo tiêu chuẩn TCVN 4055:2012.

Câu hỏi thường gặp

Câu hỏi 1: Vì sao thuật toán tối ưu đàn kiến (ACO) lại vượt trội hơn thuật toán Di truyền (GA) trong bài toán quy hoạch công trường? Trả lời: Thuật toán ACO sở hữu cơ chế lưu giữ vết mùi pheromone đóng vai trò như bộ nhớ tăng cường tập thể, giúp các cá thể kiến nhân tạo học hỏi trực tiếp từ những hành trình ngắn nhất trước đó. Trong thực nghiệm với 11 vị trí cơ sở, ACO đạt mức chi phí vận hành thấp hơn GA đến 12.4% và hạn chế tối đa nguy cơ bị phân tán lời giải.

Câu hỏi 2: Mô hình của luận văn có thể áp dụng cho các công trường có diện tích chật hẹp hay không? Trả lời: Hoàn toàn khả thi. Thuật toán được thiết lập để xử lý các ràng buộc hình học phi tuyến và kích thước không đồng đều giữa các khu vực. Ví dụ thực tế tại một dự án công trình đô thị diện tích 3.500 mét vuông cho thấy thuật toán đã bố trí tối ưu tháp cẩu và bãi đúc cấu kiện, giảm 25% các vùng giao cắt nguy hiểm.

Câu hỏi 3: Thuật toán giải quyết bài toán chi phí di dời khi chuyển giai đoạn thi công như thế nào? Trả lời: Nghiên cứu tích hợp hàm mục tiêu động theo thời gian, tính toán đồng thời chi phí lắp đặt, vận hành và tháo dỡ qua từng giai đoạn. Kết quả thử nghiệm qua 3 giai đoạn thi công chính cho thấy mô hình đã giảm 31.8% chi phí di dời lán trại và trạm phụ trợ so với phương án quy hoạch tĩnh ban đầu.

Câu hỏi 4: Thời gian chạy thuật toán trên máy tính văn phòng thông thường là bao lâu? Trả lời: Nhờ cơ chế loại bỏ nhánh tìm kiếm kém hiệu quả bằng hệ thống hỗn loạn, thuật toán chỉ mất khoảng 45 đến 60 giây để xử lý trọn vẹn 500 vòng lặp cho bài toán quy mô 15 cơ sở vật chất trên máy tính cá nhân cấu hình chuẩn Core i5, đáp ứng hoàn hảo yêu cầu ra quyết định nhanh tại hiện trường.

Câu hỏi 5: Cần chuẩn bị những dữ liệu đầu vào nào để vận hành phần mềm tối ưu hóa mặt bằng? Trả lời: Kỹ sư cần cung cấp 3 nhóm dữ liệu cơ bản: ma trận khoảng cách giữa các vị trí tiềm năng, ma trận khối lượng vật tư luân chuyển giữa các bộ phận, và chi phí đơn giá vận chuyển trên mỗi mét chiều dài. Toàn bộ thông số này có thể trích xuất trực tiếp từ bản vẽ tổng thể và hồ sơ tiến độ thi công.

Kết luận

• Luận văn đã xây dựng thành công mô hình thuật toán tối ưu hóa đàn kiến lai (ACO) giúp giảm 28.6% chi phí logistics và rút ngắn 42.3% thời gian tính toán quy hoạch mặt bằng thi công.
• Tích hợp thành công lý thuyết hệ thống hỗn loạn và học đối diện vào thuật toán, giải quyết triệt để bài toán phân bổ bậc hai (QAP) phức tạp với độ ổn định đạt sai số phương sai dưới 0.08%.
• Đóng góp giải pháp khoa học thực tiễn giúp thay thế hoàn toàn phương pháp bố trí mặt bằng dựa trên cảm tính, tiết kiệm trung bình 4.140 mét di chuyển vật tư mỗi ngày cho dự án.
• Kế hoạch mở rộng trong giai đoạn 2020 đến 2022 sẽ tích hợp thuật toán trực tiếp vào nền tảng Mô hình hóa thông tin công trình (BIM) 4D và hệ thống cảm biến định vị thời gian thực (IoT).
• Hãy chủ động ứng dụng công nghệ trí tuệ nhân tạo và số hóa quy trình quản lý xây dựng ngay hôm nay để nâng cao năng lực cạnh tranh, tối ưu hóa 25% ngân sách thi công và đảm bảo an toàn tuyệt đối cho công trình của bạn.

Trích đoạn nội dung tài liệu

CHƯƠNG 1 ĐẶT VẤN ĐÈ 1.1 Giới thiệu chung: Việc xây dựng vân đê lập kê CSLP liên quan đên việc đặt một tập hợp các cơ sở ở một số vị trí nhất định trong ranh giới công trình, trong khi tối ưu hóa các mục tiêu bố trí và đáp ứng các ràng buộc bố cục. Bồ trí công trình XD tối ưu là rất quan trong dé QLDA vi no lam it đi thời gian dé van chuyến và đo đó các chi phí vận hành của dự án và cũng tăng cường năng suất va an toàn của điều kiện làm việc. Vấn đề CSLP có thé được định nghĩa là một số cơ sở được xác định trước n, được gán tối ưu cho một số vị trí không được xác định trước m, trong đó m > n. Vấn đề CSLP nói chung có thể được mô hình hóa như là cơ sở cho phân công vị trí hoặc cơ sở cho phân công công trình.

Việc đầu tiên gán một tập hợp các cơ sở được xác định trước cho một tập hợp các vị trí được xác định trước trên công trình. Mặt khác, phương pháp phân bổ cơ sở cho công trình, gán một tập hợp các cơ sở được xác định trước cho bất kỳ không gian trống nào có sẵn trên trang web và dẫn đến một công thức phức tạp hơn do một số hạn chế về không gian phải được thỏa mãn đồng thời. Cả hai dang van dé có thê được mô hình hóa thành CSLP diện tích bằng nhau hoặc CSLP diện tích không bằng nhau tùy thuộc vào việc tất cả các cơ sở có thê phủ hợp với mọi vị trí có thể hay không. Vấn đề CSLP cũng có thể được phân biệt thành vấn đề tĩnh hay động tùy thuộc vào việc không thay đổi hoặc thay đổi cơ sở công trình và không gian công trình được xem xét trong các giai đoạn dự án khác nhau.

Bồ trí cơ sở vật chất (CSVC) phủ hợp dẫn đến năng suất cao và thành công dự án bằng cách giảm thiểu chỉ phí đi lại, giảm thời gian và chi phí cho việc xử lý vật liệu và cải thiện an toàn, đặc biệt là cho các công trường lớn Trong thời gian trước, rất nhiều các công trính nghiên cứu đã được thực hiện nhằm tìm hiểu mối liên hệ thời gian va chi phi, các kỹ thuật, phương pháp được ứng dụng từ các phương pháp tìm kiếm, các phương pháp toán học cho đến thuật giải di truyền. Trong báo cáo này, phương pháp thuật toán tôi ưu dựa trên các nền táng của sự tiến hóa, với tên gọi tối ưu đàn kiến (ACO) được ứng dụng để mô phỏng và giải quyết bài toán tối ưu đa mục tiêu đề bố trí mặt bằng công trường dựa vào mối quan hệ chỉ phí và thời gian. LV thạc sĩ MSHV: 1570080 HVTH: Lương Công Luật ĐH BK TPHCM 13 GVHD: TS. Phạm Vũ Hồng Sơn Quy hoạch không gian của tất cả các hoạt động thi công, quản lý trong dự án xây dựng là một điều cần thiết cơ ban đề hoàn thành dự án thành công.

Bồ trí công trình xây dựng liên quan đến việc phối hợp sử dụng không gian công trình hạn chế đề chứa các cơ sở tạm thời cần thiết để hỗ trợ vận hành xây dựng như cửa hàng chế tạo, rơ moóc, vật liệu hoặc thiết bị để chúng có thể hoạt động hiệu quả trên công trường. Vấn đề bố trí thường được định nghĩa là vấn đề: (1) xác định hình dạng và kích thước của các cơ sở được đặt ra, (2) xác định các ràng buộc giữa các cơ sở và (3) xác định vị trí tương đối của các cơ sở này trong ranh giới của không gian có sẵn trên công trình để nó thỏa mãn các ràng buộc giữa chúng và cho phép chúng hoạt động hiệu quả. Mặc dù tầm quan trọng của nó, việc lập kế hoạch bồ trí công trình thường bị bỏ qua. Thông thường, bố trí công trình xây dựng được lên kế hoạch hoàn toàn dựa trên kinh nghiệm trong quá khứ của người quản lý xây dựng.

Không thê xử lý hiệu quả và thận trọng một số lượng lớn các cơ sở, các yếu tố và sự phức tạp liên quan đến kế hoạch trang web chỉ dựa trên kiến thức thu được từ kinh nghiệm. Việc thiếu kế hoạch bố trí công trình phù hợp này dẫn đến mất năng suất dưới dạng tăng chi phi vận chuyên, giảm an toàn, tăng tần suất chuyến đi và tăng chi phi di dời. Một công trình xây dựng được lên kế hoạch hiệu quả có thé dẫn đến (i) giảm chỉ phí dự án, (ii) giảm thời gian và nỗ lực dành cho xử lý vật liệu, (iii) cải thiện chất lượng công việc (iv) tăng năng suất, (v) cải thiện an toàn hoạt động của dự án, và (vi) giảm thời gian hoàn thành dự án. Một trong những cách chính đề bồ trí công trình xây dựng có thể đạt được mục tiêu là giảm thiểu thời gian di chuyên và loại bỏ sự di chuyên không cần thiết của tài nguyên và xử lý tài liệu.

Trong công việc hiện tại, một cách tiếp cận mới đề tăng cường thực tiễn chung về lập kế hoạch bố trí công trường đề tạo bố cục hiệu quả được trình bày bằng cách sử dụng Ant Colony Optimization (ACO). Điều kiện công trường thuận lợi sẽ hỗ trợ cho các công tác được thực hiện một cách suôn sẻ, nhanh chóng; bao gồm các công tác bố trí hệ thống các công trình giao thông tạm xung quanh khu vực xây dựng, văn phòng ban chỉ huy, lán trại cho công nhân, khu vực thi công, các khu tiện ích, thiết bị thi công. Bố trí hiệu quả sẽ nâng cao hiệu quả hoạt động tông thể và có thể giảm từ 20% đến 50% tông chỉ phí hoạt động (J. LV thac si MSHV: 1570080 HVTH: Lương Công Luật ĐH BK TPHCM 14 GVHD: TS.

Phạm Vũ Hồng Sơn Tanchoco, 2010). Mặt khác, bố trí không hiệu quả sẽ tăng khoảng 36% chỉ phí xử lý nguyên vật liệu (J. Sự phức tạp của vấn đề sẽ tăng lên theo cấp số nhân với số lượng các cơ sở vật chất. Nếu số lượng cơ sở vật chất nhiều, rất khó và không thê đưa ra giải pháp tối ưu trong thời gian hợp lý (K.

Voi n co so vat chất, số lượng các lựa chọn thay thế có thể là n!. Ví dụ nếu ta có 10 cơ sở vật chất, số lượng các lựa chọn thay thế sẽ là 10! = 3. Vấn đề bố trí cơ sở vật chất trên công trường đã được hình thành như một vấn đề bài toán phân công bậc hai (Quadratic assignment problem-QAP). Công thức này, ban đầu được đề xuất bởi Koopmans và Beckmann năm 1957, chỉ định cơ sở vật chất phân bổ vào n vị trí.

Vấn đề bố trí được xem xét ở đây giả định rằng mỗi cơ sở vật chất có thé chỉ định cùng một khu vực, và đo đó bất kỳ cơ sở vật chất nào có thể được gán cho bất kỳ vị trí nào (T. Ban đầu, có một số phương pháp được sử dụng để giải quyết vấn đề này, chẳng hạn như phương pháp nhánh cận (Simmons, 1969), quy hoạch động (J. Queyranne, 1981), quy hoạch nửa xác định (M. Vannelli, 2008), quy hoạch nguyên tuyến tính (R.

Phương pháp tối ưu đàn kiến (ACO) là thuật toán mô phỏng cách tìm đường đi tới tô của kiến tự nhiên để giải các bài toán TƯTH khó. Phương pháp này được Dorigo giới thiệu vào năm 1991 dưới dạng hệ kiến (Ant System) ngày nay đã được phát triển dưới nhiều biến thê và được ứng dụng rộng rãi. Kiến TN và kiến nhân tạo Kiến NT: ( kiến tự nhiên và kiến nhân tạo) Trên đường đi đến các nguồn thức ăn và mang thức ăn trở về tô, mỗi con kiến TN để lại một vết hoá chất trên tuyến đường chúng đi gọi là vết mùi (pheromone trail) và theo dâu vết mùi này, các con con kiến khác trong bẩy sẽ theo và lập lại tuyến đường mà con kiên trước đó đã đi. Đường có nồng độ vết mùi càng cao thì càng có nhiều khả năng được các con kiến chọn đề đi.

Nhờ cách giao tiếp gián tiếp này đàn kiến dần sẽ tìm được đường đi ngắn nhất và gần như là tối ưu nhất từ tổ tới nguồn thức ăn. Việc dò tìm đường đi đến các nguồn thức ăn của các con kiến TN dựa trên nồng độ vết mùi trên các tuyến đường đi mà bầy đản để lại làm ta liên tưởng tới cách học tăng cường cho bài toán chọn tác động tối ưu, gợi mở một mô hình mô phỏng cho các con LV thạc sĩ MSHV: 1570080 HVTH: Lương Công Luật ĐH BK TPHCM 15 GVHD: TS. Phạm Vũ Hồng Sơn kiến TN để tìm đường đi ngắn nhất giữa hai nút hoặc qua nhiều nút (tương ứng là tổ và nguồn thức ăn) trên đồ thị. Trên cơ sở đó, mở rộng thành phương pháp ACO để giải các bài toán tối ưu tổ hợp khó Kiến NT.

Khi mô phỏng hành vi bày đàn và vết mùi của đàn kiến để giải các bài toán thực, người ta dùng đa tác tử (multiagent) làm đàn kiến NT, trong đó mỗi con kiến NT sẽ là một tác tử, có nhiều khả năng hơn kiến TN. Kiến NT (về sau sẽ gọi là kiến) có bộ nhớ riêng, có khả năng mở rộng, chẳng hạn, ghi nhớ các đỉnh đã thăm trong hành trình và tính được độ dài đường đi nó chọn. Ngoài ra các con kiến có thể trao đổi các thông tin vết mùi có được với nhau, thực hiện các tính toán cần thiết, cập nhật mùi. Nhờ các khả năng mở rộng mà mỗi đàn kiến có thể thực hiện lặp quá trình tìm lời giải nhờ thủ tục bước tuần tự trên đồ thị cấu trúc tương ứng của mỗi bài toán và cập nhật mùi theo phương thức học tăng cường đề tìm lời giải chấp nhận được và xác định lời giải đủ tốt toàn cục.

s* Những ưu điểm và ứng dụng của thuật toán Trước khi nói về nội dung thuật toán đàn kiến ta đi tìm hiểu các thuộc tính TN về đàn kiến trong tự nhiên, xem các đặc điểm tự nhiên và cách hoạt động của đàn kiến TN. Từ đó có thê đưa ra các đặc điểm cần thiết, tác động tới thuật toán đàn kiến. Đàn kiến TN: Kiến là một loài có tổ chức cao, trong TN mỗi con kiến sẽ đánh hơi vết mùi của bầy đàn khi di chuyển sẽ để lại một lượng thông tin pheromone trên mặt đất. Đây là phương tiện để đánh dấu và đề đàn kiến trao đổi thông tin khi tìm kiếm đường đi đến nguồn thức ăn.

Khi đi tìm kiếm thức ăn: Sau khi từ tổ và đến nguồn thức ăn, mỗi con kiến sẽ thiết lập ra một con đường đi riêng của nó đề đi từ tổ tới các nguồn thức ăn.