BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
----------------------------------------------

LUẬN VĂN THẠC SĨ KHOA HỌC
Giải bài toán lập lịch thi đấu thể thao bằng
các kĩ thuật dựa trên ràng buộc
LÊ HỘI QUANG


Chuyên ngành: Khoa học máy tính

Giảng viên hướng dẫn:

TS. Phạm Quang Dũng

Viện:

Công nghệ Thông tin và Truyền thông

HÀ NỘI, 5/2022

Chữ ký của GVHD


CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM
Độc lập – Tự do – Hạnh phúc

BẢN XÁC NHẬN CHỈNH SỬA LUẬN VĂN THẠC SĨ
Họ và tên tác giả luận văn: Lê Hội Quang
Đề tài luận văn: Giải bài toán lập lịch thi đấu thể thao bằng các kĩ thuật

dựa trên ràng buộc
Chuyên ngành: Khoa học máy tính
Mã số SV: CB190216

Tác giả, Người hướng dẫn khoa học và Hội đồng chấm luận văn xác nhận tác giả
đã sửa chữa, bổ sung luận văn theo biên bản họp Hội đồng ngày 28/04/2022 với
các nội dung sau:
Viết lại luận văn với các chú ý về dàn bài:
Chương 1: Giới thiệu chung. Giới thiệu về đề tài nghiên cứu, mục tiêu nghiên
cứu rõ ràng, các phương pháp và tóm tắt các phần của bài luận văn
Chương 2: Cơ sở lý thuyết. Nêu lên cơ sở lý thuyết về bài toán tối ưu tổ hợp, bài
toán Lập lịch thi đấu thể thao, các hướng tiếp cận giải bài toán Lập lịch thi đấu
thể thao là quy hoạch ràng buộc, tìm kiếm cục bộ.
Chương 3: Các phương pháp giải bài toán Lập lịch thi đấu thể thao. Trình bày
các phương pháp tiếp cận bài tốn, mơ tả rõ ràng thuật toán sử dụng, nêu lên sự
khác nhau trong cài đặt giải bài toán.
Chương 4: Kết quả thực nghiệm. Đưa ra các kết quả thực nghiệm với các phương
pháp tiếp cận. Thống kê số liệu, so sánh giữa các phương pháp.
Chương 5: Kết luận. Tổng hợp các công việc đã làm được và các hướng pháp
triển trong tương lai.
- Chỉnh sửa lại bố cục nội dung rõ ràng, cẩn thận
- Chỉnh sửa phần tham chiếu thuật ngữ chính xác


- Chỉnh sửa phần dẫn nguồn luận văn chính xác
- Chỉnh sửa lại văn phong khoa học hơn
- Chỉnh sửa các lỗi chính tả trong tồn bài luận văn
Ngày 25 tháng 5 năm 2022
Giáo viên hướng dẫn


Tác giả luận văn

CHỦ TỊCH HỘI ĐỒNG


Lời cảm ơn
Để hoàn thành luận văn tốt nghiệp “Giải bài toán lập lịch thi đấu thể thao bằng
các kĩ thuật dựa trên ràng buộc”, lời đầu tiên em xin gửi lời cảm ơn sâu sắc tới
TS. Phạm Quang Dũng đã hướng dẫn và chỉ bảo em tận tình trong suốt thời gian
thực hiện đề tài.
Em xin chân thành cảm ơn đội ngũ thầy cô giáo Trường Công nghệ thông tin và
truyền thông, Đại học Bách Khoa Hà Nội đã truyền đạt những kiến thức, kĩ năng
bổ ích trong nghề nghiệp.
Em xin chân thành cảm ơn Ban giám hiệu, gia đình và bạn bè trong lớp cao học
Khoa học máy tính khóa 2019B đã tạo mọi điều kiện giúp đỡ, động viên, chia sẻ
để em có thể hồn thành được bản luận văn này.

Hà Nội, ngày 25 tháng 05 năm 2022
HỌC VIÊN

LÊ HỘI QUANG


Tóm tắt nội dung luận văn
Luận văn nghiên cứu về bài toán “Lập lịch thi đấu thể thao” bằng cách tiếp cận
giải bằng các kĩ thuật dựa trên ràng buộc. Từ đó đánh giá các vấn đề cịn hạn chế
và nghiên cứu thêm một cách tiếp cận khác là sử dụng thuật toán Luyện thép
(Simulated Annealing) để giải bài toán này. Luận văn được thực hiện với phương
pháp tìm hiểu các tài liệu, bài báo khoa học, dữ liệu được tổng hợp trên thế giới
và thư viện Or-Tools hỗ trợ giải bài toán tối ưu tổ hợp dựa trên ràng buộc. Qua

đó tái tạo giải thuật trên ngơn ngữ lập trình Python, tổng hợp số liệu và đưa ra
các đánh giá chi tiết. Kết quả của luận văn thể hiện được hiện tại việc áp dụng
cơng cụ Or-Tools cịn hạn chế trong việc giả bài toán “Lập lịch thi đấu thể thao”.
Thay vào đó, giải thuật Luyện thép thể hiện kết quả khả quan hơn và là nền tàng
để tiếp tục phát triển và giải bài toán này trong tương lai với việc kết hợp với các
chiến lược tìm kiếm khác.

Hà Nội, ngày 25 tháng 05 năm 2022
HỌC VIÊN

LÊ HỘI QUANG


Lời cam đoan
Em xin cam đoan và chịu trách nhiệm về nội dung, sự trung thực trong luận văn
tốt nghiệp Thạc sĩ của mình.

Hà Nội, ngày 25 tháng 05 năm 2022
HỌC VIÊN

LÊ HỘI QUANG


MỤC LỤC
CHƯƠNG 1. GIỚI THIỆU CHUNG ................................................................. 2
1.1

Lý do chọn đề tài ........................................................................................ 2

1.2


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

1.3

Đối tượng và phạm vi nghiên cứu .............................................................. 2

1.4

Hướng nghiên cứu của đề tài ..................................................................... 3

1.5

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

1.6

Ý nghĩa khoa học của đề bài ...................................................................... 3

1.7

Nội dung bài luận văn ................................................................................ 3

CHƯƠNG 2. CƠ SỞ LÝ THUYẾT .................................................................... 4
2.1

Bài toán tối ưu tổ hợp ................................................................................. 4

2.2


Bài toán lập lịch thi đấu thể thao................................................................ 8

2.3

2.2.1

Yêu cầu của bài toán ................................................................... 9

2.2.2

Dạng dữ liệu đầu vào của bài toán .............................................. 9

Lý thuyết về quy hoạch ràng buộc và tìm kiếm cục bộ ............................. 9
2.3.1

Phương pháp quy hoạch ràng buộc ............................................. 9

2.3.2

Tìm kiếm cục bộ ....................................................................... 16

CHƯƠNG 3. CÁC PHƯƠNG PHÁP GIẢI BÀI TOÁN LẬP LỊCH THI
ĐẤU THỂ THAO ............................................................................................... 21
3.1

3.2

Phương pháp Quy hoạch ràng buộc ......................................................... 21
3.1.1


Mơ hình hóa bài tốn TTP ........................................................ 21

3.1.2

Cài đặt chương trình giải bài tốn TTP sử dụng OR-Tools ...... 22

Phương pháp tìm kiếm cục bộ với thuật toán SA .................................... 24
3.2.1

Ý tưởng của phương pháp SA trong bài tốn TTP ................... 24

3.2.2

Mơ hình bài tốn TTP trong phương pháp SA ......................... 25

3.2.3

Các phép biến đổi tìm kiếm giải pháp lân cận .......................... 25

3.2.4

Biểu đồ hoạt động thuật toán SA giải TTP ............................... 28

CHƯƠNG 4. KẾT QUẢ THỰC NGHIỆM ..................................................... 34
4.1

Các tiêu chí thực nghiệm.......................................................................... 34
4.1.1

Mục tiêu thực nghiệm ............................................................... 34


4.1.2

Phạm vi thực nghiệm ................................................................ 34

4.1.3

Kịch bản thực nghiệm ............................................................... 34

4.1.4

Dữ liệu thực nghiệm.................................................................. 34

4.1.5

Môi trường thực nghiệm ........................................................... 34


4.2

kết quả khi áp dụng Or-Tools giải bài toán TTP ..................................... 35

4.3

Kết quả khi áp dụng giải thuật SA giải bài toán TTP .............................. 36

CHƯƠNG 5. KẾT LUẬN ................................................................................. 40
5.1

Kết luận .................................................................................................... 40


5.2

Hướng phát triển của đồ án trong tương lai ............................................. 40

TÀI LIỆU THAM KHẢO ................................................................................. 41


DANH MỤC HÌNH VẼ
Hình 2.1 Bài tốn TSP biểu diễn dưới dạng đồ thị ................................................ 5
Hình 2.2 Ví dụ một tập dữ liệu cho bài tốn BCA................................................. 7
Hình 2.3 Mẫu dữ liệu cho kích thước bài tốn 4 đội (n=4) ................................... 9
Hình 2.4 Ví dụ bài tốn thỏa mãn ràng buộc ....................................................... 10
Hình 2.5 Mã giả thuật tốn Arc Consistency ....................................................... 12
Hình 2.6 Liệt kê các giá trị cho biến quyết định được lựa chọn đầu tiên ............ 13
Hình 2.7 Cắt nhánh các miền ............................................................................... 14
Hình 2.8 Tìm kiếm quay lui và cho kết quả. Sơ đồ tổng quan của các bước tìm
kiếm. ..................................................................................................................... 14
Hình 2.9 Bài tốn tìm kiếm cục bộ với không gian trạng thái và hàm mục tiêu . 17
Hình 3.1 Một lời giải cho bài tốn TTP với kích thước n = 6 ............................. 25
Hình 3.2 Trước khi biến đổi SwapHomes(S, T2, T4) ........................................... 26
Hình 3.3 Sau khi biến đổi SwapHomes(S, T2, T4) ............................................... 26
Hình 3.4 Trước khi biến đổi SwapRounds(S, R3, R5) .......................................... 26
Hình 3.5 Sau khi biến đổi SwapRounds(S, R3, R5) .............................................. 26
Hình 3.6 Trước khi biến đổi SwapTeams(S, T2, T4) ............................................ 27
Hình 3.7 Sau khi biến đổi SwapTeams(S, T2, T4)................................................ 27
Hình 3.8 Trước khi biến đổi PartialSwapRounds(S, T2, R2, R9) .......................... 27
Hình 3.9 Sau khi biến đổi PartialSwapRounds(S, T2, R2, R9) ............................. 28
Hình 3.10 Trước khi biến đổi PartialSwapTeams(S, T2, T4, R9) ......................... 28
Hình 3.11 Sau khi biến đổi PartialSwapTeams(S, T2, T4, R9) ............................. 28

Hình 3.12 Thuật tốn đệ quy khởi tạo giải pháp ban đầu ngẫu nhiên ................. 29
Hình 3.13 Biểu đồ hoạt động thuật toán khởi tạo giải pháp khả thi ban đầu cho
bài tốn TTP ......................................................................................................... 29
Hình 3.14 Thuật tốn SA điển hình ..................................................................... 30
Hình 3.15 Thuật tốn SA áp dụng cho TTP ......................................................... 31
Hình 3.16 Biểu đồ hoạt động của thuật tốn SA cho bài tốn TTP ..................... 32
Hình 4.1 Thơng số thiết bị thực nghiệm .............................................................. 34
Hình 4.2 Biểu đồ thống kê tốc độ hội tụ hàm mục tiêu với dữ liệu NL12 .......... 37
Hình 4.3 So sánh tốc độ hội tụ của bài tốn TTP có ràng buộc chặt và khơng có
.............................................................................................................................. 37


DANH MỤC BẢNG BIỂU
Bảng 4.1 Kết quả và thời gian thực nghiệm khi sử dụng Or-Tools ..................... 35
Bảng 4.2 Kết quả thực nghiệm khi sử dụng SA cho bài toán TTP ...................... 36
Bảng 4.3 Các tham số được chọn khi sử dụng SA cho bài toán TTP .................. 37
Bảng 4.4 So sánh kết quả thực nghiệm với kết quả của bài báo đề xuất ............. 38
Bảng 4.5 Tác động của các thành phần TTSA đến chất lượng giải pháp (12 đội)
.............................................................................................................................. 38
Bảng 4.6 Các tham số đầu vào phép thử tác động thành phần. ........................... 39


DANH SÁCH THUẬT NGỮ VÀ KÍ HIỆU VIẾT TẮT
Kí hiệu

Các thuật ngữ

Ý nghĩa

TTP


Traveling Tournament Problem

Bài toán lập lịch giải đấu
thể thao

TSP

Traveling Salesman Problem

Bài toán người du lịch

Backtracking

Đệ quy quay lui

Branching

Phân nhánh

Search tree

Cây tìm kiếm

Constraint Programing

Quy hoạch ràng buộc

Constraint propagation


Lan truyền ràng buộc

Constraint Satisfaction Problem

Bài toán tối ưu tổ hợp

Hamilton

Tên của một loại chu trình
trong lý thuyết đồ thị

Traveling Salesman Problem

Bài tốn người bán hàng

CP
CSP

TSP
BCA

Bài tốn phân cơng giảng
dạy

CNTT

Cơng nghệ thơng tin

TTNT


Trí tuệ nhân tạo

AC

Arc Consistency

Thuật tốn Arc Consistency

Hill climbing

Giải thuật leo đồi

Random walk

Di chuyển ngẫu nhiên

Depth-First Search

Tìm kiếm theo chiều sâu

DC

Domain Consistent

Toàn vẹn miền giá trị

FC

Forward Checking Consistent


Toàn vẹn kiểm tra tiến

Best Improvement Hill climbing

Leo đồi sang trạng thái tốt
nhất

state-of-the art algorithms

Thuật tốn hiện đại nhất

Mixed-Integer Programing

Chương trình tối ưu hóa số
nguyên hỗn hợp

Stochastic Hill Climbing

Leo đồi ngẫu nhiên

Reheat

Kĩ thuật làm nóng lại của
thuật tốn SA

Satisiability

Một phương pháp giải bài
tốn tối ưu hóa nguyên hỗn
hợp của OR-Tools


MIP

SAT

1


CHƯƠNG 1. GIỚI THIỆU CHUNG
1.1 Lý do chọn đề tài
Các bài toán thuộc lớp các bài toán tối ưu tổ hợp xuất hiện trong nhiều lĩnh vực
quan trọng của cuộc sống: Công nghệ thông tin, lập lịch, sản xuất, kinh tế, chính
trị, quốc phịng,… Có thể kể đến các bài toán kinh điển trong lớp bài toán này:
Bài toán người du lịch (TSP), bài tốn n-queens, bài tốn tơ màu đồ thị, bài toán
xếp lịch trự y tá, bài toán tìm tập phủ đỉnh của đồ thị, bài tốn lập lịch thi đấu thể
thao. Việc giải quyết tốt các bài toán như vậy là rất quan trọng, bởi những vấn đề
liên quan trực tiếp đến cuộc sống của con người khi được giải quyết tốt sẽ giúp
chất lượng sống của chúng ta trở nên tốt hơn: việc xếp lịch được tối ưu giúp cho
công sức làm việc mọi người bỏ ra hiệu quả hơn, tránh được những xung đột hay
rắc rối bởi sự chồng chéo; hiệu năng thiết bị tốt hơn đảm bảo khả năng sử dụng
máy móc bền bỉ hơn, lâu dài hơn, đỡ tốn nhiên liệu hơn; công việc sản xuất được
tối ưu giúp cho chi phí sản xuất thấp dẫn đến giá thành sảm phẩm giảm xuống, có
lợi cho tồn bộ người tiêu dùng;… Rất nhiều ví dụ trong cuộc sống có thể liên
kết được để thể hiện được tầm quan trọng của việc giải bài toán tối ưu tổ hợp là
lớn như thế nào.
Bài toán lập lịch thi đấu thể thao (TTP) thuộc lớp bài toán tối ưu tổ hợp, khi kích
thước bài tốn trở nên lớn dần, tập khơng gian tìm kiếm trở nên bùng nổ, khơng
thể sử dụng các phương pháp tìm kiếm thơng thường để xem xét tất cả trạng thái
trong thời gian cho phép. Tìm kiếm cục bộ được thiết kế cho bài tốn tìm kiếm
với khơng gian trạng thái rất lớn và cho phép tìm kiếm trạng thái tương đối tốt

với thời gian tìm kiếm chấp nhận được. Tuy nhiên phương pháp này vẫn cịn
những nhược điểm. Khi kích thước khơng gian tìm kiếm thực sự rất lớn, thời
gian tìm kiếm vẫn cịn dài, thuật tốn khơng thể tìm ra giải pháp tối ưu, có thể
dẫn tới bế tắc, tối ưu cục bộ, số lượng ràng buộc lớn dẫn đến phức tạp trong giải
thuật.
Với những thách thức đó, việc tiếp cận với các giải pháp khác như tabu search,
tìm kiếm giải pháp tốt nhất có thể trong thời gian chấp nhận được là một phương
án hay để giải quyết bài toán “Lập lịch thi đấu thể thao” dựa trên ràng buộc.
Trong khuôn khổ của luận văn, chúng tôi tập trung giải bài toán “Lập lịch thi đấu
thể thao” (TTP)[1] bằng các cách tiếp cận xử lý dựa trên ràng buộc và
metaheuristic là Simulated Annealing. Từ đó đánh giá tương quan giữa các giải
pháp cho bài tốn này.
1.2 Mục tiêu nghiên cứu
• Tìm hiểu các giải thuật tìm kiếm cục bộ dựa trên ràng buộc giải bài tốn TTP.
• Nghiên cứu giải thuật Simulated Annealing (SA) giải bài tốn TTP.
• Đánh giá được hiệu quả của giải thuật khi thay đổi các tham số, đưa ra hướng
phát triển trong tương lai.
1.3 Đối tượng và phạm vi nghiên cứu

2


Nghiên cứu tìm hiểu về lý thuyết và các kĩ thuật giải tốn của Quy hoạch ràng
buộc và Tìm kiếm cục bộ, áp dụng giải bài toán lập lịch thi đấu thể thao. Qua đó
đánh giá được hiệu quả từng phương pháp.
1.4 Hướng nghiên cứu của đề tài
• Tìm hiểu các thuật tốn tìm kiếm cục bộ cho bài tốn TTP.
• Tìm hiểu các cơng cụ giải bài tốn TTP dựa trên ràng buộc.
• Sử dụng thuật tốn SA để giải bài toán TTP, đánh giá và so sánh hiệu quả của
giải pháp này với việc sử dụng Constraint Programing (CP) để giải TTP.

1.5 Phương pháp nghiên cứu
• Tìm hiểu bài tốn TTP và các biến thể của nó được các nhà khoa học đề xuất
và nghiên cứu.
• Nghiên cứu tài liệu khoa học về các phương pháp tìm kiếm cục bộ.
• Tìm hiểu, sử dụng các cơng cụ giải bài tốn bằng kĩ thuật quy hoạch ràng
buộc.
• Nghiên cứu các tài liệu khoa học về giải bài tốn TTP.
• Sử dụng thuật toán SA cài đặt giải bài toán TTP.
• Đánh giá hiệu quả việc áp dụng thuật tốn SA so với sử dụng công cụ ORTools giải bài toán TTP.
1.6 Ý nghĩa khoa học của đề bài
Sử dụng các nghiên cứu về việc sử dụng thuật toán SA giải bài tốn TTP và sử
dụng cơng cụ hỗ trợ OR-Tools giải đúng cho bài toán TTP bằng quy hoạch ràng
buộc để kiểm chứng và so sánh kết quả của các phương pháp này khi thực
nghiệm. Từ đó có thể lựa chọn hướng giải quyết tốt hơn để sử dụng và kết hợp
với các phương pháp khác cho việc giải bài toán TTP trong tương lai.
1.7 Nội dung bài luận văn
Chương 1: Giới thiệu chung.
Chương 2: Cơ sở lý thuyết.
Chương 3: Các phương pháp giải bài toán lập lịch thi đấu thể thao.
Chương 4: Kết quả thực nghiệm.
Chương 5: Kết luận.

3


CHƯƠNG 2. CƠ SỞ LÝ THUYẾT
2.1 Bài toán tối ưu tổ hợp
Như đã trình bày ở phần 1.1, TTP là bài toán thuộc lớp bài toán tối ưu tổ hợp,
vậy nên ở phần này chúng tôi sẽ đề cập đến những định nghĩa, khái niệm sẽ được
áp dụng trong việc giải một bài tốn tối ưu tổ hợp nói chung và giải TTP nói

riêng.
Bài tốn tối ưu hóa tổ hợp (Combinatorial Optimizatoin) [2] liên quan đến việc
tìm giá trị cho các biến số rời rạc như lời giải tối ưu mà có lưu ý tới hàm đánh giá
cho trước. Bài tốn có thể là bài tốn tìm cực đại hoặc tìm cực tiểu. Một cách
thơng thường, bài tốn tối ưu hóa tổ hợp được cho dưới dạng bộ ba (S, f, Ω ).
Trong đó:
• S là tập các lời giải ứng cử viên.
• F là hàm đánh giá (hàm này gán giá trị f(s) sao cho mỗi lời giải ứng
viên s ∈ S).
• Ω là tập các ràng buộc của bài toán
(Các lời giải thuộc tập S*⸦ S thỏa mãn ràng buộc Ω gọi là lời giải khả thi. Mục
tiêu bài tốn là tìm ra một lời giải s* với chi phí nhỏ nhất, nghĩa là f(s*) < f(s) với
mọi s ∈ S. và ngược lại với bài toán tối ưu hóa cực đại.)
Tối ưu hóa tổ hợp là lớp bài tốn có nhiều ứng dụng trên thực tế, một số bài toán
kinh điển trong lớp bài toán này là: Bài toán người du lịch, bàn toán n – queens,
bài tốn tơ màu đồ thị, bài tốn xếp lịch y tá…
Những khái niệm quan trọng trong một bài toán tối ưu tổ hợp:
• Biến quyết định (Decision variable)
Biến quyết định của một bài tốn tối ưu hóa tổ hợp là một biến nằm trong mơ
hình của bài tốn mà người ra quyết định có thể kiểm sốt được giá trị của biến
đó và cần xác định giá trị cho biến đó.
• Miền xác định của biến quyết định (Domain)
Miền giá trị của các biến quyết định là tập hợp tất cả các giá trị có thể gán cho
biến đó.
• Ràng buộc (Constraint)
Một ràng buộc của bài tốn tối ưu hóa tổ hợp là một điều kiện mà một tập các
biến quyết định của bài tốn cần thỏa mãn.
• Hàm mục tiêu của bài toán (Object function)
Hàm mục tiêu của bài tốn tối ưu hóa tổ hợp là một hàm được định nghĩa trên
một tập các biến quyết định và cần được tối ưu hóa (cực đại hóa hoặc cực tiểu

hóa).
• Lời giải của bài toán (Solution)
Một lời giải của bài tốn tối ưu hóa tổ hợp là một bộ giá trị xác định gán cho tập
các biến quyết định của bài toán.
4


• Lời giải chấp nhận được (Feasible Solution)
Một lời giải chấp nhận được của bài toán tối ưu tổ hợp là một lời giải thỏa mãn
mọi ràng buộc của bài tốn.
• Ví dụ 1: Bài tốn người bán hàng (TSP):
Có một người giao hàng cần đi giao hàng tại n thành phố. Anh ta xuất phát từ
một thành phố nào đó, đi qua các thành phố khác để giao hàng và trở về thành
phố ban đầu. Mỗi thành phố chỉ đến một lần, và khoảng cách từ một thành phố
đến thành phố khác đã được biết trước. Yêu cầu tìm một đường đi khép kín thỏa
mãn điều kiện trên để sao cho tổng quãng đường di chuyển của người bán hàng
là nhỏ nhất.
Input:
• n là số thành phố mà người bán hàng cần phải đi qua
• D là ma trận khoảng cách (n, n) giữa các thành phố
Output:
• Chu trình di chuyển của người bán hàng và tổng quãng đường di
chuyển nhỏ nhất.
Bài tốn TSP có thể được mơ tả trên một đồ thị vơ hướng có trọng số G = (V, E),
trong đó mỗi thành phố được biểu diễn bởi một đỉnh, cạnh nối hai đỉnh biểu diễn
cho đường đi giữa hai thành phố và trọng số của cạnh chính là khoảng cách giữa
hai thành phố. Một chu trình đi qua tất cả các đỉnh của đồ thị G đúng một lần
(Chu trình Hamilton) là một giải pháp của bài tốn. Vấn đề làm tìm một chu trình
Hamilton có tổng độ dài các cạnh đi qua là nhỏ nhất.


Hình 2.1 Bài toán TSP biểu diễn dưới dạng đồ thị

5


Bài tốn TSP thuộc lớp bài tốn NP-khó, thường có các nhiều cách tiếp cận khác
nhau. Thiết kế thuật toán tìm kiếm lời giải tối ưu thường hoạt động hiệu quả cho
những bài tốn có kích thước nhỏ. Thiết kết thuật tốn heuristic để tìm những lời
giải tốt nhưng có thể khơng tối ưu. Thiêt kế thuật tốn xấp xỉ để tìm những lời
giải khơng q lớn so với lời giải tối ưu. Có thể kể đến một số thuật toán thường
được áp dụng như phương pháp vét cạn, kĩ thuật tham ăn, giải thuật nhánh cận.
Bài tốn TSP có tính ứng dụng cao trong đời sống như cơng việc giao vận của
shipper, vận tải hàng hóa qua các thành phố, hay các quy trình có sự tương đồng
trong hoạt động của nhà máy, xí nghiệp.
• Ví dụ 2: Bài tốn phân cơng giảng dạy (BCA):
Trong một ngơi trường có M giáo viên 1, 2, …, M cần được phân công để giảng
dạy cho N môn học 1, 2, ..., N sao cho mỗi môn học được phân cho một giáo
viên. Mỗi giáo viên chỉ có thể phụ trách giảng dạy một số mơn học nào đó tùy
thuộc vào khả năng chuyên môn và được thể hiện bởi tập C(i) với C(i) ⸦ {1, …,
M}, i = 1, 2, …, M. Mỗi một mơn học i có số tiết là t(i). S là tập các cặp 2 môn
học không thể được phân cùng một giáo viên do 2 môn học này đã được xếp
cùng tiết trong thời khóa biểu được xác định từ trước. Ràng buộc của bài toán là
tổng số tiết phân cho mỗi giáo viên phải lớn hơn hoặc bằng α và bé hơn hoặc
bằng β. Mục tiêu của bài tốn là lịch phân cơng cho các giáo viên sao cho số tiết
nhiều nhất phân cho giáo viên phải ít nhất.
Input:
•
•
•
•

•
•

M là số giáo viên trong trường
N là số môn cần được giảng dạy
C là danh sách số mơn học có thể dạy bởi các giáo viên
t là danh sách tiết học của các môn
S là danh sách các cặp môn học trùng tiết
Hằng số α, β để ràng buộc số tiết học được phân công cho từng giáo
viên

Output:
• Chu trình di chuyển của người bán hàng và tổng quãng đường di
chuyển nhỏ nhất.

6


Hình 2.2 Ví dụ một tập dữ liệu cho bài tốn BCA

Đây là một bài tốn lập lịch điển hình chứa rất nhiều ràng buộc. Để giải quyết bài
toán này cũng có nhiều hướng tiếp cận. Một trong số đó là sử dụng quy hoạch
ràng buộc để giải bài toán với mơ hình ràng buộc được mơ tả dưới đây:
Biến input:
• N: Miền các giáo viên
• M: Miền các mơn học
• MH_GV[][]: Tập hợp các mơn học mà từng giáo viên được dạy
• T_MH: Tập hợp số tiết của các mơn học
• Cặp I, J là đơi một là các cặp mơn học tiên quyết.
Biến quyết định trong model:

• x[i][j] = {0, 1}. Với i ∈ N, j ∈ 𝑀𝑀: Quy định giáo viên i dạy mơn j.
• y[j][i] = {0,1}. Với i ∈ M, j ∈ 𝑁𝑁. Đảm nhận vị trí trung gian để xây dựng
các ràng buộc.
• maxT: Là biến ràng buộc hàm mục tiêu của bài toán.
Ràng buộc:
• 𝑥𝑥 [𝑖𝑖]�𝐼𝐼 [𝑗𝑗]� + 𝑥𝑥 [𝑖𝑖]�𝐽𝐽[𝑗𝑗]� ≤ 1.
• 𝑥𝑥 [𝑖𝑖][𝑗𝑗] = 0𝑖𝑖𝑖𝑖𝑖𝑖 ∉ 𝐺𝐺𝐺𝐺𝑀𝑀𝑀𝑀 [𝑖𝑖], 𝑥𝑥 [𝑖𝑖][𝑗𝑗] = 𝑦𝑦[𝑗𝑗][𝑖𝑖]
𝑁𝑁−1 [ ][ ]
• ∑𝑖𝑖=0
𝑦𝑦 𝑗𝑗 𝑖𝑖 = 1𝑗𝑗 ∈ 𝑀𝑀
𝑀𝑀−1 [ ][ ]
ã =0
ì _ [𝑗𝑗] ≤ 𝛽𝛽 ∀𝑖𝑖 ∈ 𝑁𝑁
• ∑𝑀𝑀−1
𝑗𝑗=0 𝑥𝑥 [𝑖𝑖 ][𝑗𝑗 ] × 𝑇𝑇_𝑀𝑀𝑀𝑀 [𝑗𝑗 ] ≤ 𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚∀𝑖𝑖 ∈ 𝑁𝑁

Hàm mục tiêu
F = Min(maxT).
Bài tốn BCA có tính ứng dụng cao trong việc phân công làm việc, giảng dạy
của các tập thể cơng ty, nhà trường hay thậm chí là lịch làm việc cho các hệ
thống máy móc trong chuỗi sản xuất cơng nghiệp.
Ngồi những ví dụ trên, cịn rất nhiều bài tốn tối ưu tổ hợp vẫn ln ln hiện
hữu trong cuộc sống của chúng ta. Việc nghiên cứu và giải quyết các bài toán tối
7


ưu tổ hợp là công việc vô cùng ý nghĩa và có tác động tích cực đến sự phát triển
của nền văn minh hiện đại.
2.2 Bài toán lập lịch thi đấu thể thao
TTP là một bài toán lập lịch biểu thi đấu cho các đội di chuyển trong một giải

đấu vịng trịn. Bài tốn được đề xuất từ bài báo “The Traveling Tournament
Problem Description and Benchmarks” bởi các tác giả Kelly Easton, George
Nemhauser, Michael A. Trick vào thời gian 01/01/2001. Vấn đề là dù với số đội
rất nhỏ thì việc tìm ra được kết quả tối ưu cho bài tốn là rất khó. Điều này đặt ra
một thách thức thú vị cho các kĩ thuật lập trình giải nguyên tuyến tính hay giải
ràng buộc. TTP thuộc lớp bài tốn NP-khó, khi n tăng dẫn đến khơng gian tìm
kiếm vơ cùng lớn, hiện chưa có lời giải chính xác trong thời gian đa thức. Bài
toán hiện vẫn đang là đề tài nghiên cứu trong lĩnh vực tối ưu hóa tổ hợp bởi
những thách thức và ứng dụng của nó đem lại. Các kết quả tốt hơn vẫn tiếp tục
được cập nhật và tổng hợp [3].
Phát biểu bài toán TTP bằng lời:
Cho n đội cùng tham gia vào một giải đấu. Trong đó, mỗi đội phải thi đấu với n-1
đội cịn lại theo thể thức lượt đi lượt về. Tức mỗi đội phải thi đấu với 1 đội khác
2 trận, 1 trên sân nhà và 1 trên sân khách. Mỗi tuần sẽ có n/2 trận đấu được diễn
ra. Như vậy suốt giải đấu sẽ có 2(n-1) trận đấu. Khoảng cách giữa các điểm thi
đấu được mô tả trong ma trận khoảng cách (n, n). Mục tiêu của bài toán là giảm
thiểu tổng chi phí di chuyển của tất cả các đội trong giải đấu.
Ràng buộc chặt của bài toán là 2 đội không được thi đấu với nhau trong 2 tuần
liên tiếp và không được thi đấu trên sân nhà (sân khách) quá 3 tuần liên tiếp.
Input:
• n, số đội tham gia giải đấu, n ln chẵn
• D là ma trận khoảng cách (n, n)
• L, U lần lượt là tham số chặn dưới và chặn trên của việc thi đấu liên tục
trên sân nhà (sân khách)
Output:
• Các lượt thi đấu liên tục trên sân nhà (sân khách) nằm trong khoảng L
và U
• Tổng quãng đường di chuyển của các đội là nhỏ nhất
Ngồi những ràng buộc cơ bản, bài tốn cịn có một số biến thể được đề cập và
nghiên cứu hiện nay như sau:

Nhân bản (Mirrored): Là một giải đấu mà phải có một lịch đấu vịng trịn ở n-1
lượt trận đầu tiên và lặp lại lịch trình đó ở n-1 lượt đấu cịn lại.
Khơng lặp (No Repeaters): Khơng có những đội i, j nào mà đội i đấu với đội j và
sau đó đội j lại đấu với đội i ở lượt đấu kế tiếp.
Bài toán TTP hiện nay vẫn chưa có lời giải chính xác với n = 6 trở lên.
8


Bài toán được mở rộng với nhiều biến thể, tuy nhiên ở đây chúng tơi tập trung
nghiên cứu bài tốn cơ sở TTP với các ràng buộc gốc, hạn chế tối đa số ràng
buộc chặt để giảm thiểu độ phức tạp của bài toán.
2.2.1 Yêu cầu của bài toán
Hai đội bất kì gặp nhau đúng 2 lần trong mùa giải. Hai đội bất kì đá với nhau
trong một trận sân nhà và một trận sân khách. Hàm mục tiêu của bài toán là tổng
quãng đường di chuyển của các đội là ngắn nhất.
2.2.2 Dạng dữ liệu đầu vào của bài toán
Dữ liệu đầu vào của bài toán sẽ là một ma trận khoảng cách giữa các sân vận
động của các đội tham gia trong giải đấu.
Ví dụ: 1 mẫu dữ liệu

Hình 2.3 Mẫu dữ liệu cho kích thước bài tốn 4 đội (n=4)

2.3 Lý thuyết về quy hoạch ràng buộc và tìm kiếm cục bộ
Một bài tốn tối ưu tổ hợp có rất nhiều cách tiếp cận để giải khác nhau với những
mục tiêu khác nhau như tối ưu về giá trị hàm mục tiêu, tối ưu thời gian tìm kiếm
cho kết quả chấp nhận được… Đối với bài toán TTP, chúng tôi lựa chọn tiếp cận
giải bằng hai phương pháp là Quy hoạch ràng buộc và Tìm kiếm cục bộ với thuật
toán Simulated Annealing.
2.3.1 Phương pháp quy hoạch ràng buộc
A. Tổng quan

Một trong những hướng tiếp cận tốt để giải các bài toán tối ưu tổ hợp là sử dụng
Quy hoạch ràng buộc (Constraint Programming - CP). Là một phương pháp giao
thoa giữa vận trù học (Operations Research), khoa học máy tính và trí tuệ nhân
tạo, CP được áp dụng nhiều trong việc giải các bài toán tối ưu có thể kể đến như
lập lịch (Scheduling) [4], lập thời khoá biểu (TimeTabling) [5], Lập tuyến điều
hành xe (Vehicle Routing) [6], phân công ca trực (Nurse Rostering) [7],… Phần
cơ bản của phương pháp này là tỉa khơng gian tìm kiếm (Constraint Propagation)
và phân nhánh (Branching). Thành phần tỉa không gian tìm kiếm sử dụng các
ràng buộc của bài tốn để loại bỏ các giá trị không thỏa mãn ra khỏi khơng gian
tìm kiếm. Thành phần phân nhánh phân hoạch miền khơng gian tìm kiếm của bài
tốn thành nhiều phần với các chiến lược khác nhau có thể áp dụng tùy vào từng
mơ hình của bài tốn. Việc phận nhánh thơng thường là thử lần lượt từng giá trị
còn lại trong miền giá trị của một biến nào đó và gán giá trị cho biến đó.
B. Định nghĩa bài tốn thỏa mãn ràng buộc
9


Định nghĩa về bài toán thỏa mãn ràng buộc (CSP) như sau. Một bài toán CSP
gồm 3 thành phần (X, D, C) với:

Hình 2.4 Ví dụ bài tốn thỏa mãn ràng buộc

• X là bộ biến quyết định (Variables) gồm n phần tử: X = (X1, X2,…, Xn).
• D là miền giá trị (Domans): D = (D1, D2, …, Dn) là tập các giá trị mà biến
quyết định X có thể nhận.
• C là ràng buộc (Constraints). Tập hợp tất cả các ràng buộc.
• f: Một số bài tốn sẽ có hàm mục tiêu này để tối ưu theo yêu cầu đề bài.
• Biến: X = {X1, X2, X3}
• Miền: D(X1) = {1, 2, 3, 4}; D(X2) = {1, 2, 3}; D(X3) = {1, 2, 3}
• Ràng buộc: 𝐶𝐶1 : 𝑋𝑋1 < 𝑋𝑋2 ; 𝐶𝐶2 : 𝑋𝑋3 = 𝑋𝑋1 + 𝑋𝑋2 ; 𝐶𝐶3 : 𝑋𝑋2 + 𝑋𝑋3 = 5


C. Dùng ràng buộc để tỉa khơng gian tìm kiếm
Loại bỏ các giá trị thừa ra khỏi miền giá trị của các biến, đưa về một bài toán
thoả mãn ràng buộc với miền giá trị nhỏ hơn.
Để đạt được ràng buộc tổng thể là rất khỏ và thời gian tính tốn lớn, do đó người
ta sử dụng các kĩ thuật tỉa với từng ràng buộc một cách cục bộ. Một số kĩ thuật
tỉa như sau:
i. Toàn vẹn miền giá trị (Domain Consistent - DC)
Cho bài toán thoả mãn ràng buộc CSP = (X, D, C), một ràng buộc c ∈ C được gọi
là domain consistent nếu với mỗi biến XI ∈ X(c), mỗi giá trị v ∈ D(Xi), tồn tại bộ
giá trị cho các biến ∈ X(c) \ {Xi} sao cho ràng buộc c được thảo mãn. Bài toán
CSP được gọi là domain consistent nếu c là domain consistent với mọi ràng buộc
c ∈ C.
Ví dụ: CSP = (X, D, C) trong đó:
• X = {X1, X2, X3, X4}
• D(X1) = {1,2,3,4}, D(X2) ={1,2,3,4,5,6,7}, D(X3) = {2,3,4,5}, D(X4) =
{1,2,3,4,5,6}

10


• C = {c1,c2,c3} với
c1: X1 + X2 ³ 5
c2: X1 + X3 ³ X4
c3: X1 + 3 ³ X3
CSP này là domain consistent
Khi phân nhánh, xét X1 = 1, thuật toán DC sẽ đưa CSP đã cho về CSP1 tương
đương các domain consistent với miền giá trị được thu hẹp như sau: D1(X1) =
{1}, D1(X2) = {4,5,6,7}, D1(X3) = {2,3,4}, D1(X4) = {1,2,3,4,5}.
Ví dụ: CSP = (X, D, C) trong đó:

• X = {X1, X2, X3}
• D(X1) = D(X2) = D(X3) = {0,1}
• c1: X1 ≠ X2, c2: X1 ≠ X3, c3: X1 ≠ X3
Rõ ràng CSP này là domain consistent nhưng lại khơng có lời giải chấp nhận
được (lời giải thoả mãn ràng buộc).
ii.Toàn vẹn kiểm tra tiến (Forward Checking - FC)

Kỹ thuật toàn vẹn FC loại bỏ được ít giá trị khơng hợp lệ hơn nên kỹ thuật
này yếu hơn kỹ thuật DC.
Một ràng buộc c ∈ C được gọi là toàn vẹn FC khi và chỉ khi hoặc có nhiều
hơn một biến trong c chưa được gán giá trị hoặc chỉ có duy nhất một biến
trong c chưa được gán giá trị và c là toàn vẹn miền giá trị.
Ví dụ: CSP = (X, D, C) trong đó:
• X = {X1, X2, X3, X4}
• D(X1) = {1,2,3,4}, D(X2) ={1,2,3,4,5,6,7}, D(X3) = {2,3,4,5}, D(X4) =
{1,2,3,4,5,6}
• C = {c1,c2,c3} với
c1: X1 + X2 ³ 5
c2: X1 + X3 ³ X4
c3: X1 + 3 ³ X3
CSP này là domain consistent
Lời giải bộ phận: X1 = 1, D1(X1) = 1, D2(X2) = {4, 5, 6, 7}, D3(X3) = {2, 3, 4},
D4(X4) = {1, 2, 3, 4, 5, 6}. N1 = (X, D1, C) là tồn vẹn FC vì giá trị 6 trong miền
giá trị của x4 không thỏa mãn ràng buộc của c2.
iii. Thuật toán Arc consistency (AC)

11


Hình 2.5 Mã giả thuật tốn Arc Consistency


Thuật tốn AC3(X,D,C) có một hàng đợi Q gồm tất cả các cặp (x,c) sao cho
ràng buộc c thuộc vào bộ các ràng buộc C và x thuộc vào bộ biến của ràng buộc c
(c). Khi đó vịng lặp sẽ chọn lần lượt các cặp (x, c) trong Q và gọi
Revise(x,c). Nếu D(x) rỗng, thuật toán trả về false. Trái lại, nếu D (x) được sửa
đổi thì sẽ có một giá trị cho một biến khác x’ đã thỏa mãn được ràng buộc c’. Do
đó tất cả các cặp (x’, c’) được đặt lại trong hàng đợi Q. Khi Q rỗng thuật toán trả
về true với đảm bảo rằng tất cả các miền đã được sửa đổi và tất cả các giá trị còn
lại của tất cả các biến thỏa mãn với mọi ràng buộc. Thuật toán ReviseAC3(x,c) là
thuật toán tỉa các giá trị không phù hợp của x nhờ vào ràng buộc c. Hàm Revise
(x, c) lấy lần lượt từng giá trị v trong D(x) và đối chiếu x(c) kiểm tra sự thỏa mãn
các ràng buộc của giá trị v. Nếu v khơng thỏa mãn các ràng buộc thì v bị loại
khỏi D(x) và miền giá trị D(x) thay đổi. Hàm sẽ trả về true nếu miền D(x) thay
đổi hay nói cách khác được rút gọn, miền giá trị giảm xuống, còn ngược lại hàm
sẽ trả về giá trị false.
D. Phân nhánh và tìm kiếm quay lui
Phương pháp tỉa khơng gian tìm kiếm có nhược điểm là khơng thể chắc chắn tìm
ra lời giải thỏa mãn cho tất cả các ràng buộc. Do đó, chúng ta cần kết hợp
phương pháp tỉa khơng gian tìm kiếm với tìm kiếm quay lui.
i. Quay lui (backtracking) [8]:
Quay lui là một kĩ thuật tìm kiếm lời giải thường xuyên được áp dụng trong việc
giải các bài toán thỏa mãn ràng buộc được thiết kế dựa trên đệ quy. Quay lui sẽ
tìm kiếm lời giải từng bước, trong mỗi bước sẽ chọn ra một lựa chọn thỏa mãn
ràng buộc và thực hiện đệ quy. Kĩ thuật này lần đầu được tạo ra từ nhà toán học
người Mỹ D. H. Lehmer vào những năm 1950.
Bản chất của kĩ thuật này vẫn là duyệt qua tất cả các khả năng trong khơng gian
nghiệm của bài tốn cho đến khi tìm thấy lời giải đúng. Q trình đó là q trình
tìm kiếm theo độ sâu (Depth-First Search). Quá trình tìm kiếm sẽ có hai trường
hợp xảy ra tại một điểm. Nếu chương trình gặp điểm thỏa mãn, nó sẽ tiếp tục
thực hiện đệ quy tiếp tục tìm kiếm các khả năng khác. Nếu chương trình gặp

điểm khơng thỏa mãn, nó sẽ quy lui lại điểm thỏa mãn trước đó và thử trường
hợp khác. Quá trình tìm kiếm sẽ dừng lại khi khơng cịn sự lựa chọn nào nữa.
12


Quá trình tìm kiếm như trên được cài đặt bằng một hàm đệ quy, mỗi lần thực
hiện đệ quy sẽ lựa chọn thêm một biến, lần lượt gán tất cả các giá trị có thể cho
biến đó. Sau đó lại gọi lại chuỗi đệ quy và thực hiện tìm giá trị cho các biến tiếp
theo. So với tìm kiếm theo độ sâu, kĩ thuật quy lui sử dụng ít bộ nhớ hơn vì nó
chỉ lưu trữ trạng thái của một lời giải hiện tại và cập nhật nó.
Ngồi ra, quay lui cịn có một số thủ thuật để tăng tốc trong quá trình tìm kiếm,
khi một biến được gán giá trị, trước khi thực hiện lời gọi đệ quy, thuật tốn
thường xóa bỏ giá trị đó khỏi khơng gian tìm kiếm của các biến có ràng buộc
chưa được gán giá trị (kiểm tra tiến - forward checking) và kiểm tra tất cả các giá
trị khác để tìm các giá trị vi phạm ràng buộc bởi giá trị vừa được gán (Lan truyền
ràng buộc - constraint propagation).
ii. Phân nhánh (Branching):
Chia không gian tìm kiếm thành các khơng gian con. Có một số chiến lược chia
khơng gian tìm kiếm như sau:
• Liệt kê các giá trị cho biến được lựa chọn
• Phân hoạch tập giá trị của mỗi biến được lựa chọn thành 2 hoặc nhiều tập con.
Việc tỉa khơng gian tìm kiếm (Propagation) khơng đủ để tìm ra lời giải tối ưu
thoả mãn ràng buộc. Cần thiết phải kết hợp giữa tỉa khơng gian tìm kiếm với
phân nhánh và tìm kiếm quay lui.
Phân ra bài toán CSP P0 ban đầu thành các CSP P1,…, PM.
• Tập các lời giải của P0 bằng hợp của tập các lời giải của P1,…,PM
• Miền giá trị mỗi biến trong P1, …, PM không lớn hơn miền giá trị P0
Cây tìm kiếm (Search Tree):
• Nút gốc của CSP P0 ban đầu
• Mỗi nút của cây là 1 CSP

• Nếu P1, …, PM là các nút con của P0 thì tập các lời giài của P0 sẽ bằng với hợp
của tập các lời giải của P1, …, PM
Nút lá:
• Một lời giải thoả mãn ràng buộc
• Failure (tồn tại biến của miền giá trị rỗng)

Hình 2.6 Liệt kê các giá trị cho biến quyết định được lựa chọn đầu tiên

13


Hình 2.7 Cắt nhánh các miền

Hình 2.8 Tìm kiếm quay lui và cho kết quả. Sơ đồ tổng quan của các bước tìm kiếm.

iii. Một số chiến lược tìm kiếm
Chiến lược chọn biến:
• Dom heuristic: chọn biến có miền giá trị nhỏ nhất
• Deg heuristic: chọn biến tham gia vào nhiều ràng buộc nhất
• Dom + deg heuristic: Áp dụng dom trước, sau đó áp dụng deg khi có nhiều
biến có cùng kích thước miền giá trị nhỏ nhất
• Dom/deg: chọn biến có tỉ số dom/deg nhỏ nhất (kích thước miền giá trị/số
ràng buộc mà biến tham gia vào)
Chiến lược chọn giá trị:
• Chọn giá trị theo thứ tự tăng dần
• Chọn giá trị theo thứ tự giảm dần
• Chọn giá trị ở giữa miền giá trị nhất.
iv. Một số bài tốn ví dụ CSP
Ví dụ 1: Bài tốn con hậu N-Queens
Cho bàn cờ kích thước n*n có n con hậu. Cách sắp xếp n con hậu trên bàn cờ sao

cho khơng có con nào có thể ăn lẫn nhau.

14


• Variables: X = {Xi | i ∈ [1, n]} một biến là đại diện cho một cột và ràng buộc
mỗi con hậu phải trên một cột khác nhau.
• Domains: Cho tất cả các biến Xi ∈ X, D(xi) = {1, 2, …, n}
• Constraints: Tập hợp các ràng buộc.
 2 con hậu không được cùng nằm trên một hàng.
𝑋𝑋𝑋𝑋 ≠ 𝑋𝑋𝑋𝑋∀1 ≤ 𝑖𝑖 < 𝑗𝑗 ≤ 𝑛𝑛
 Hai con hậu không được cùng nằm trên một đường chéo.
𝑋𝑋𝑋𝑋 − 𝑖𝑖 ≠ 𝑋𝑋𝑋𝑋 − 𝑗𝑗∀1 ≤ 𝑖𝑖 < 𝑗𝑗 ≤ 𝑛𝑛

𝑋𝑋𝑋𝑋 + 𝑖𝑖 ≠ 𝑋𝑋𝑋𝑋 + 𝑗𝑗∀1 ≤ 𝑖𝑖 < 𝑗𝑗 ≤ 𝑛𝑛
Ví dụ 2: Giải hệ phương trình, bất phương trình
• Variables: X = {X0, X1, X2, X3, X4}
• Domains: X0, X1, X2, X3, X4 ∈ {1, 2, 3, 4, 5}
• Constraints:
 𝐶𝐶1 : 𝑋𝑋2 + 3 ≠ 𝑋𝑋1
 𝐶𝐶2 : 𝑋𝑋3 ≤ 𝑋𝑋4
 𝐶𝐶3 : 𝑋𝑋2 + 𝑋𝑋3 = 𝑋𝑋0 + 1
 𝐶𝐶4 : 𝑋𝑋4 ≤ 3
 𝐶𝐶5 : 𝑋𝑋1 + 𝑋𝑋4 = 7
 𝐶𝐶6 : 𝑋𝑋2 = 1 ⇒ 𝑋𝑋4 ≠ 2
E. Thư viện OR-Tools hỗ trợ giải TTP

OR-Tools là phần mềm mã nguồn mở cho tối ưu tổ hợp [9]. Với việc tìm kiếm
lời giải tốt nhất cho một vấn đề trong không gian rộng lớn các lời giải thoả mãn.
Ở đây có một số ví dụ các bài tốn mà OR-Tools có thể giải:

• Vehicle routing: Tìm kiếm tối ưu đường đi cho phương tiện thoả mãn các ràng
buộc
• Scheduling: Tìm kiếm tối ưu lịch cho tập các công việc phức tạp, một số công
việc cần được thực hiện trước trên tập máy cố định hoặc các tài ngun khác
• Bin packing: Có nhiều đối tượng items với các dữ liệu kích thước khác nhau
cần được xếp vào bin. Tối ưu khả năng sắp xếp các items này vào trong bin
Trong hầu hết các trường hợp, các vấn đề giống như có rất nhiều giải pháp khả
thi. Để vượt qua điều đó, OR-Tools sử dụng state-of-the art algorithms để thu
hẹp khơng gian tìm kiếm, để tìm kiếm một giải pháp tối ưu.
OR-ools bao gồm các solvers cho:
• Constraint Programing: Một tập các kĩ thuật cho việc tìm kiếm giải pháp
khả thi cho một vấn đề được trình bày như các constraints. Ví dụ như trong
phịng không thể được sử dụng cho 2 sự kiện đồng thời, hoặc khoảng cách của
cây trồng phải bé hơn chiều dài của vịi tưới nước, hoặc khơng thể ghi hình
nhiều hơn 5 chương trình TV 1 lần.

• Linear and Mixed-Integer Programing: Trình tối ưu hố tuyến tính tìm
kiếm các giá trị tối ưu cho một hàm tuyên tính, đưa các bất đẳng thức tuyến
tính về dưới dạng ràng buộc.
15