Chương 1 Các bài toán 1.1 Bài toán người du lịch (TSP) 1.1 Giới thiệu và phát biểu bài toán Bài toán người du lịch (Travelling salesman problem viết tắt là TSP) là một bài toán tối ưu tổ hợp thuộc lớp NP-hard ([8]). Bài toán người du lịch rất quan trọng trong khoa học máy tính và vận trù học bởi nó có rất nhiều ứng dụng. Bài toán người du lịch được phát biểu như sau: Cho một danh sách các thành phố cùng khoảng cách giữa chúng. Nhiệm vụ của bài toán TSP là tìm một đường đi ngắn nhất xuất phát từ một thành phố, thoả mãn đi qua mỗi thành phố một lần và quay lại thành phố ban đầu.2 Một số phương pháp giải Có rất nhiều phương pháp được thiết kế cho bài toán TSP, bao gồm các nhóm sau: 1.
Các giải thuật chính xác: giải thuật quy hoạch động, giải thuật nhánh cận, quy hoạch nguyên, phương pháp mặt phẳng cắt [8] 2. Các phương pháp tìm kiếm cục bộ: 2-Opt [6], 3-Opt [9] 3. Các giải thuật lấy cảm hứng từ tự nhiên: giải thuật di truyền (GA) [1], giải thuật luyện kim (SA) [20], giải thuật bầy đàn (PSO) [15], giải 3 thuật đàn kiến (ACO) [4], giải thuật đàn ong (ABC) [7],. Trong đó, các phương pháp chính xác chỉ áp dụng được cho bài toán vừa và nhỏ vì có độ phức tạp thời gian lớn.
Các thuật toán tìm kiếm cục bộ có thể nhanh chóng cải thiện lời giải nhưng lại bị giới hạn ở điểm tối ưu cục bộ. Các giải thuật lấy cảm hứng từ tự nhiên được sử dụng rộng rãi hơn cả vì có nhiều ưu điểm: có thời gian chạy hợp lý, có thể áp dụng cho cả bài toán có kích thước lớn, là các thuật toán tối ưu toàn cục nên có tiềm năng tìm được điểm tối ưu toàn cục hơn so với các giải thuật tìm kiếm cục bộ. Hơn nữa các giải thuật lấy cảm hứng từ tự nhiên có thể dễ dàng kết hợp với các phương pháp tìm kiếm cục bộ để tăng hiệu quả. [7] dùng 3-opt để cải thiện lời giải cuối cùng.
[11] và [12] kết hợp 2-opt với thuật toán sói xám (GWO) cho kết quả tốt.2 Bài toán thiết kế chuỗi cung ứng 1.1 Giới thiệu bài toán Bài toán thiết kế chuỗi cung ứng là một bài toán thực tế. Giả sử một doanh nghiệp có chuỗi cung ứng theo mô hình ba cấp như sau: hàng hoá được chuyển từ các nhà cung cấp đến các kho trung chuyển, tại các kho này người ta đóng gói thành kiện hàng chuyển đến các điểm bán hàng. Các điểm bán hàng và nhà cung cấp là cho trước, yêu cầu bài toán là lựa chọn trong các địa điểm tiềm năng và quy mô cho trước để xây dựng các kho trung chuyển này sao cho tổng chi phí là nhỏ nhất. Các chi phí này bao gồm chi phí vận chuyển, xây dựng và duy trì.
Mỗi điểm bán hàng được cung cấp bởi một kho trung chuyển duy nhất. Mỗi loại hàng hóa đến từ một nhà cung cấp, tuy nhiên mỗi nhà cung cấp có thể có nhiều địa điểm. Kho trung chuyển sau khi được xây dựng sẽ nhận từ địa điểm gần nhất của nhà cung cấp. Bài toán có các ràng buộc là quy mô của kho trung chuyển phải lớn hơn hoặc bằng tổng cầu của các điểm bán hàng nhận từ kho trung chuyển đó và mỗi điểm bán hàng chỉ nhận từ một kho trung chuyển.
4 Để đơn giản hóa bài toán ta đưa ra các giả định rằng mỗi kiện hàng được giao từ kho trung chuyển đến điểm bán hàng là như nhau, nhu cầu của mỗi điểm bán hàng cũng được tính theo số kiện hàng này. Chi phí vận chuyển được tính như nhau cho mỗi kiện hàng, bỏ qua các yếu tố như chọn xe, chọn đường đi. Quy mô của kho trung chuyển được tính theo số kiện hàng giao đi mỗi tuần, chọn một trong các mức cho trước như sau: [500, 2500, 4000, 10000].2 Phát biểu bài toán Các điểm bán hàng và địa điểm tiềm năng được đánh chỉ số như sau: • Điểm bán hàng r ∈ R = {1, 2, · · · , m} • Các địa điểm tiềm năng để xây dựng kho trung chuyển là d ∈ D = {1 , 2 , · · · , n } • Quy mô của kho trung chuyển là h ∈ H = {1, 2, · · · µ} Ký hiệu: 1 nếu xây một kho trung chuyển tại địa điểm d với quy mô h, xhd = 0 nếu ngược lại, 1 nếu điểm bán hàng r được cung cấp bởi kho trung chuyển d, ydr = 0 nếu ngược lại, Ta có x = {x hd : d ∈ D, h ∈ H } và y = {y dr : d ∈ D, r ∈ R} là các biến của bài toán đều là biến nhị phân. Các ràng buộc của bài toán được mô hình như sau: • Mỗi kho trung chuyển được xây với 1 quy mô nhất định nên h X x d ≤ 1 ∀d ∈ D h∈ H Vì x hd chỉ nhận giá trị 0 hoặc 1 nên P h∈H x hd = 0 tương ứng với kho trung chuyển không được xây dựng tại địa điểm d.
5 • Mỗi điểm bán hàng được cung cấp bởi một kho trung chuyển nên có ràng buộc X ydr = 1 ∀r ∈ R d∈ D • Gọi p r số kiện hàng điểm bán hàng r cần được giao, c h là số kiện hàng mà quy mô h có thể đáp ứng được. Quy mô của kho trung chuyển phải đủ để cung cấp cho các điểm bán hàng nên ta có ràng buộc sau h h X pr ydr ≤ X c xd ∀d ∈ D r ∈R h∈ H Hàm mục tiêu của bài toán sẽ là tổng các chi phí tính theo mỗi tuần, bao gồm 4 loại chi phí. • Chi phí cố định: gồm chi phí xây dựng phụ thuộc vào quy mô và chi phí thuê đất phụ thuộc vào địa điểm và quy mô. Ký hiệu bh là chi phí xây dựng một kho trung chuyển có quy mô h, l hd là chi phí thuê đất tại địa điểm d để xây kho có quy mô h.
Chi phí cố định được tính như sau: h h h h C 1 (x ) = X b X x d + X X l d x d h∈ H d∈ D h∈ H d∈ D • Chi phí biến đổi: là chi phí vận hành kho trung chuyển tính theo số kiện hàng được giao. Ký hiệu vh là chi phí trung bình tính theo mỗi kiện hàng của kho trung chuyển có quy mô h. Nhận xét rằng kho trung chuyển có quy mô càng lớn thì chi phí này càng rẻ. C2 (x, y ) = X vh X xhd X pr ydr h∈ H d∈ D r ∈R • Chi phí vận chuyển: vận chuyển từ nhà cung cấp đến kho trung chuyển và từ kho trung chuyển đến các điểm bán hàng.
Ký hiệu ω là chi phí vận chuyển mỗi kiện hàng từ kho đến điểm bán hàng mỗi km, ωs là chi phí vận chuyển mỗi kiện hàng từ nhà sản xuất s đến kho mỗi km (Vì mỗi nhà sản xuất cung cấp loại hàng hoá khác nhau nên chi phí 6 vận chuyển khác nhau). Ký hiệu kdr là quãng đường từ kho ở vị trí d đến điểm bán hàng r. C 3(y ) = ω X X pr kdr ydr d∈ D r ∈ R C4 (y ) = X X X ωs ρ s ǩdr pr ydr s∈ S d ∈ D r ∈ R 1.3 Một số phương pháp giải Phần này trình bày các mô hình tham khảo từ [2] để so sánh. Các ký hiệu trong phần này cũng được dùng cho các phần sau.1 Mô hình BQP Nhận thấy C2 (x, y ) = P h∈H vh P d∈D x hd P r ∈R pr ydr là hàm toàn phương.
Ta có mô hình toàn phương sau, ký hiệu là mô hình BQP(Binary Quadratic Program) Min C (x, y ) = C 1 (x) + C 2 (x, y ) + C 3 (y ) + C 4 (y ) h v.k X x d ≤ 1 ∀d ∈ D, h∈ H X ydr = 1 ∀r ∈ R, d∈ D h h X pr ydr ≤ X c x d ∀d ∈ D, r ∈R h∈ H h x d ∈ {0, 1} ∀d ∈ D, ∀h ∈ H, ydr ∈ {0, 1} ∀d ∈ D, ∀r ∈ R 1.2 Nới lỏng bài toán Mô hình toàn phương BQP hầu như không thể giải được với bài toán có kích thước lớn nên người ta nới lỏng để đưa về bài toán có thể giải được theo hai cách sau 1. Phân cụm và nới lỏng điều kiện của biến y : nhóm các điểm bán hàng thành nhiều cụm. Coi mỗi cụm như một điểm tại trung tâm của cụm 7 đó. Tuy nhiên việc phân cụm này có thể tạo ra một cụm quá lớn dẫn đến vi phạm ràng buộc của bài toán.
Để tránh vấn đề này người ta kết hợp với nới lỏng điều kiện của biến y , cho biến y là số thực thuộc đoạn [0, 1]. Việc phân cụm vừa làm giảm số biến của bài toán, nới lỏng điều kiện của biến y cũng làm giảm số biến nguyên nên giúp giảm đáng kể thời gian tính toán. Tuyến tính hoá: C 2(x, y ) = P h∈H vh P d∈D x hd P r ∈R pr ydr là hàm toàn phương. Ta tuyến tính hoá bằng cách tính chi phí thay đổi mỗi kho trung chuyển theo quy mô thay vì theo số lượng kiện hàng vận chuyển.
Như vậy có thể thay hàm toàn phương C2(x, y ) bằng hàm tuyến tính C2L (x) = P h∈H vh ch P d∈D x hd .3 Mô hình BLP Tuyến tính hoá bằng cách thay hàm toàn phương C2 (x, y ) bằng hàm tuyến tính C 2L (x) = P h∈H vh c h P d∈D x hd ta được mô hình tuyến tính với biến nhị phân sau, ký hiệu là mô hình BLP(Binary Linear Program) Min C (x, y ) = C 1(x) + C 2L (x) + C 3 (y ) + C 4(y ) h v.k X x d ≤ 1 ∀d ∈ D, h∈ H X ydr = 1 ∀r ∈ R, d∈ D h h X pr ydr ≤ X c x d ∀d ∈ D, r ∈R h∈ H x hd ∈ {0, 1} ∀d ∈ D, ∀h ∈ H, ydr ∈ {0, 1} ∀d ∈ D, ∀r ∈ R 8 1.4 Mô hình CMBQP Phân cụm và nới lỏng điều kiện của biến y ta có mô hình sau, ký hiệu là CMBQP (Cluster Mixed Binary Quadratic Program) Min C (x, y ) = C 1 (x) + C 2(x, y ) + C 3cl (y ) + C 4cl (y ) h v.