Ứng dụng giải thuật di truyền vào bài toán vận tải tuyến tính

Nguyễn Thu Huyền và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 106(06): 81 - 84

81

ỨNG DỤNG GIẢI THUẬT DI TRUYỀN VÀO BÀI TOÁN

VẬN TẢI TUYẾN TÍNH

Nguyễn Thu Huyền

1*, Vũ Mạnh Xuân2

, Lương Sỹ Ước

3

1

Trường Đại học Công nghệ Thông tin và Truyền thông- ĐH Thái Nguyên

2

Trường Đại học Sư phạm- ĐH Thái Nguyên

3

Trường Cao đẳng Kinh tế- Kĩ thuật- ĐH Thái Nguyên

TÓM TẮT

Bài toán vận tải là một trong những bài toán điển hình và có nhiều ứng dụng của quy hoạch tuyến

tính. Bài toán này không có gì phức tạp nếu mạng lưới giao thông tương đối đơn giản và số địa

điểm cung cấp, tiêu thụ không nhiều lắm. Tuy nhiên, với những mạng lưới giao thông phức tạp thì

bằng kinh nghiệm và trực giác khó có thể tìm ra được phương án tối ưu. Bài báo này nghiên cứu

ứng dụng Giải thuật di truyền giải bài toán vận tải tuyến tính, kết quả thử nghiệm được so sánh với

một số phương pháp đã có.

Từ khóa: Giải thuật di truyền, bài toán vận tải tuyến tính.

ĐẶT VẤN ĐỀ*

Giải thuật di truyền (GAs-Genetic

Algorithms) là giải thuật tìm kiếm, chọn lựa

các giải pháp tối ưu để giải quyết các bài toán

thực tế khác nhau, dựa trên cơ chế chọn lọc

của tự nhiên: từ tập lời giải ban đầu, thông

qua nhiều bước tiến hoá, hình thành tập lời

giải mới phù hợp hơn, và cuối cùng dẫn đến

lời giải tối ưu toàn cục. GAs là một công cụ

hữu ích giúp giải quyết các bài toán tối ưu,

đặc biệt là bài toán tối ưu có không gian tìm

kiếm lớn [2]. Bài toán vận tải tuyến tính là

một trong những bài toán điển hình và có

nhiều ứng dụng trong quy hoạch tuyến tính.

Khi mạng lưới giao thông phức tạp, số địa

điểm cung cấp và nhận lớn thì việc tìm ra

được phương án tối ưu là rất khó khăn. Vì

vậy, GAs có thể là một thuật giải phù hợp để

giải quyết bài toán này.

Bài báo này tập trung nghiên cứu ứng dụng

Gas vào giải bài toán vận tải tuyến tính. Kết

quả thử nghiệm được so sánh, đối chiếu với

các phương pháp khác như phương pháp tìm

phương án cực biên ban đầu, phương pháp

Vôghen để thấy được hiệu quả của đề xuất.

Bài báo có cấu trúc như sau: Sau phần đặt vấn

đề là phần giới thiệu về nội dung và mô hình

toán học bài toán vận tải tuyến tính. Phần kế

*

Tel: 0904.012.478; Email: [email protected]

tiếp trình bày về GAs và cách chọn các tham

số trong ứng dụng của GAs vào bài toán vận

tải tuyến tính. Cuối cùng là kết quả thử

nghiệm và thảo luận.

BÀI TOÁN VẬN TẢI TUYẾN TÍNH [1]

Nội dung bài toán

Giả sử cần vận chuyển một loại hàng thuần

nhất (vật tư, lương thực…) từ m địa điểm

cung cấp (điểm phát) A1, A2…Am đến n địa

điểm tiêu thụ (điểm thu) B1, B2…Bn biết rằng:

- Số lượng hàng có ở Ai

là ai

(i=1..m)

- Số lượng hàng cần ở Bj là bj (j=1..n)

- Chi phí vận chuyển một đơn vị hàng từ Ai

đến Bj

là cij (i=1..m, j=1..n).

Vấn đề đặt ra: Lập kế hoạch vận chuyển hàng

từ các địa điểm cung cấp đến các địa điểm

tiêu thụ sao cho tổng chi phí vận chuyển là

nhỏ nhất và thỏa mãn nhu cầu thu phát. Bài

toán vận tải là tuyến tính nếu chi phí tỉ lệ với

số lượng hàng vận tải.

Mô hình toán học của bài toán

Gọi xij là số lượng hàng cần vận chuyển từ Ai

đến Bj

. Ta có:

∑i=1

m∑j=1

n

cijxij : tổng chi phí vận chuyển

∑j=1

n

xij : số lượng hàng chở đi từ Ai

. i = 1..m.

∑i=1

m

xij : số lượng hàng chở tới từ Bj

. j = 1.. n.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn