MỞ ĐẦU Lập trình ràng buộc (Constraint Programming -CP) là một sự phát triển mạnh của ngôn ngữ lập trình trong thập kỷ gần đây. Nó được xây dựng trên cơ sở lý thuyết toán học vững chắc, đang phát triển và đặc biệt thu hút sự quan tâm mạnh mẽ trong việc áp dụng vào nhiều lĩnh vực kinh tế xã hội. Hiện nay, lập trình ràng buộc đã trở thành phương pháp mô hình hoá cho nhiều bài toán tối ưu, cụ thể là trong các ràng buộc có sự hỗn tạp và các bài toán tìm kiếm có tính tổ hợp. Lập trình ràng buộc khắc phục được những khó khăn của những ngôn ngữ trước, nó hỗ trợ ràng buộc và tích hợp triệt để vào ngôn ngữ lập trình, cho phép người lập trình làm việc với bài toán ở mức độ cao hơn, trong khi đó các kỹ thuật thực thi ở mức dưới cũng sử dụng kỹ thuật tích hợp cho ràng buộc.
Việc ra đời các ngôn ngữ lập trình ràng buộc thế hệ mới có khả năng đáp ứng được những yêu cầu đối với số lượng lớn các ứng dụng nhằm giải quyết các bài toán thực tế đặt ra trong đời sống xã hội. Trong điều kiện về hạ tầng giao thông trên cả nước hiện nay, các sự cố về ùn ứ, ách tắc giao thông đang xảy ra hàng ngày ở các vùng đô thị lớn và những tuyến đường giao thông huyết mạch. Các sự cố này đã gây nhiều tổn thất nặng nề cho sự phát triển của nền kinh tế, ảnh hưởng nhiều đối với các hoạt động kinh tế xã hội, làm mất mỹ quan đô thị, ảnh hưởng xấu môi trường… Chính vì thế, việc nghiên cứu ứng dụng tiến bộ khoa học công nghệ để phục vụ cho việc nhận biết, đánh giá mức độ của các sự cố giao thông để có biện pháp xử lý và phòng tránh là điều cần thiết và cấp bách thực hiện. Vấn đề đặt ra là làm cách nào để có thể nhận biết trước nguy cơ có thể dẫn đến sự cố giao thông? Nếu có sự cố về giao thông xảy ra, việc xử lý phân luồng, điều tiết giao thông như thế nào để đem lại hiệu quả tốt nhất cho các 2 nhà quản lý cũng như cho người tham gia giao thông? Vì vậy, việc nghiên cứu cơ sở lý thuyết toán học về cách mô tả các điều kiện ràng buộc và giải các hệ phương trình ràng buộc đó, kết hợp ứng dụng qua các thuật toán, kỹ thuật lập trình tiên tiến là một hướng đi khả quan để giải quyết được các vấn đề mà xã hội đang đặt ra hiện nay.
Trên nền tảng kiến thức được truyền đạt từ Nhà trường, từ các giáo viên Khoa Công nghệ thông tin, kết hợp sự hướng dẫn, tạo điều kiện thuận lợi của Giáo viên hướng dẫn, Tôi đã xác định chọn cho mình lĩnh vực nghiên cứu với đề tài: “Lập trình ràng buộc với bài toán hỗ trợ phân luồng giao thông”. Hy vọng rằng, đề tài nghiên cứu này sẽ đóng góp thêm một giải pháp mới để các cơ quan quản lý, các doanh nghiệp. lựa chọn sử dụng đáp ứng yêu cầu của thực tế xã hội. Đối tượng nghiên cứu là các cơ sở lý thuyết về lập trình ràng buộc, thuật toán giải quyết bài toán thõa mãn ràng buộc, bài toán đặt ra đối với hệ thống hạ tầng giao thông đường bộ hiện nay; đối tượng, phương tiện tham gia giao thông đường bộ; các bộ quy tắc, điều kiện ràng buộc liên quan đến hoạt động giao thông vận tải đường bộ.
Phạm vi nghiên cứu: ứng dụng lý thuyết lập trình ràng buộc, các thuật toán giải quyết bài toán thỏa mãn ràng buộc; thu thập các thông tin, dữ liệu chuyên môn liên quan đến lĩnh vực giao thông vận tải đường bộ trên địa bàn tỉnh Bình Định; phân tích, xử lý và đưa ra kết quả xử lý đạt hiệu quả tối ưu. Giới thiệu Trong thực tế xã hội hiện nay, để đạt được mục tiêu đề ra, con người phải thực hiện việc thu thập các thông tin, dữ kiện cần thiết để xử lý, tính toán và đưa ra các quyết định thực thi một cách nhanh chóng, chính xác. Việc xử lý, tính toán và đưa ra quyết định cuối cùng xét về bản chất là việc giải bài toán thực tế để tìm ra bộ nghiệm sao cho thõa mãn, đáp ứng tất cả các yêu cầu, điều kiện ràng buộc đặt ra và được gọi là bài toán thõa mãn ràng buộc (Constrains Satisfation Problem -CSP). Những loại bài toán này được ứng dụng rất nhiều trong các hoạt động, lĩnh vực thực tế như: thiết kế, phân bổ tài nguyên, lập kế hoạch, điều khiển hệ thống.
Lập trình ràng buộc được phát triển khá sớm so với những ngôn ngữ lập trình phổ biến hiện nay như Java (1990s). Vào thập niên 60, 70, những ý tưởng đầu tiên về lập trình ràng buộc có thể được tìm thấy trong lĩnh vực nghiên cứu trí tuệ nhân tạo (AI) mà cụ thể là ngôn ngữ lập trình Prolog (Alain Colmerauer, 1972). Một số ứng dụng đầu tiên của ngôn ngữ này đã đạt được những thành tựu đáng kể như: hệ thống tương tác đồ họa Sketchpad của Ivan Sutherland (1963), hệ thống ThingLab của Alan Borning (1981). Tuy nhiên, phải đến dòng ngôn ngữ lập trình logic ràng buộc (Constrain Logic Programming -CLP) mới đánh dấu bước phát triển chính của lập trình ràng buộc.
CLP được phát triển bởi hai nhà khoa học Jaffar và Lassez (1987), dựa trên nền tảng lập tình logic, kết hợp cả hai khía cạnh khai báo của lập trình logic với giải quyết các ràng buộc. Tiếp sau đó, một số dòng ngôn ngữ lập trình ràng buộc lần lượt được phát triển, có thể kể ra như: Concurrent Logic Programming (1980s), Concurrent Constraint Programming (1990s). Lập trình logic ràng buộc là một sự tổng quát hóa lập trình logic. Trong quan điểm của CLP về lập trình logic, các ngôn ngữ lập trình logic chuẩn chỉ 4 cung cấp một loại ràng buộc đơn thuần, các câu lệnh có cú pháp giống nhau được giải quyết triệt để.
Tuy nhiên, điều đó cũng còn khá nhiều hạn chế và cũng là lý do thúc đẩy cho sự ra đời của các nghiên cứu lập trình logic vào đầu những năm 1980 dành cho phát triển và chuẩn hóa các ngôn ngữ lập trình logic. Những hạn chế của việc lựa chọn chữ cố định đã được sớm áp dụng trong việc phát triển các ngôn ngữ lập trình logic. Absys -một tiền thân của Prolog- cung cấp lịch trình động cũng như các ngôn ngữ lập trình logic IC- Prolog, Prolog-II và MU-Prolog. Do đó trong các khai báo đợi MU-Prolog có thể được sử dụng để xác định rằng việc đánh giá một vị từ cụ thể phải "đợi" cho đến khi các đối số của nó không biến đổi.
Dựa trên điều này, MU-Prolog cung cấp các sự cân bằng cú pháp và các biến vị ngữ số học, cung cấp giải pháp ràng buộc đơn giản bằng cách sử dụng các kỹ thuật khởi tạo biến cục bộ. Mô hình CLP, trong đó có các ràng buộc tùy ý là sự phân tích tự nhiên của hai hướng nghiên cứu này. Thuật ngữ thực tế Constraint Logic Programming được đặt ra bởi Jaffar và Lassez vào năm 1986 và họ đưa ra một lược đồ và ngữ nghĩa cho lớp ngôn ngữ CLP. Đây là một phần mở rộng của họ trên lược đồ ngữ nghĩa cho các chương trình logic và ngữ nghĩa logic cho bất phương trình.
Với những người khác, họ đã phát triển ngôn ngữ CLP (R) một ngôn ngữ mở rộng Prolog bằng cách cung cấp các ràng buộc số học, sử dụng một thuật toán phức tạp để giải quyết các ràng buộc tuyến tính và các ràng buộc số học phi tuyến tính đầy đủ. Các tiện ích của CLP (R) đã được chứng minh bằng cách sử dụng nó trong lĩnh vực tài chính và một loạt các ứng dụng kỹ thuật. Colmeraur và nhóm của ông đã phát triển Prolog II vào đầu những năm 1980 và sau đó là Prolog III vào cuối những năm 1980. Prolog II cung cấp các phương trình và bất phương trình trên các cây tỷ lệ và là ngôn ngữ lập trình logic đầu tiên được mô tả rõ ràng như sử dụng các constraints.
Prolog III là một ngôn ngữ CLP thực sự tiên tiến so với Prolog II bằng cách cung cấp các 5 ràng buộc kiểu booleans, số học tuyến tính trên các số hữu tỷ và các ràng buộc trên các danh sách (chuỗi). Nhóm nghiên cứu tại ECRC (đáng chú ý là Dincbas, Van Hentenryck và Simonis) đã phát triển CHIP trong giai đoạn 1985-1988. Nó được phát triển để giải quyết các vấn đề tối ưu hóa tổ hợp cho ngành công nghiệp bằng cách kết hợp với phương pháp tìm kiếm quay lui (backtracking) của Prolog với các công nghệ xuyên suốt từ nghiên cứu trí tuệ nhân tạo. Đó là ngôn ngữ CLP đầu tiên cung cấp một cách rõ ràng ràng buộc miền hữu hạn.
Các ứng dụng giới thiệu bao gồm chẩn đoán mạch, lập lịch và phân tích các vấn đề về chứng khoán. CLP là khởi nguồn cho các ý tưởng lập trình logic liên quan xuất hiện trong trí tuệ nhân tạo cộng đồng nghiên cứu. SKETCHPAD của Sutherland là một trong những hệ thống máy tính đầu tiên sử dụng các ràng buộc; đáng chú ý đối với CLP bao gồm nghiên cứu tại MIT về các ngôn ngữ và hệ thống để giải quyết ràng buộc, ví dụ ngôn ngữ CONSTRAINTS được nghiên cứu ứng dụng trong việc phân tích và thiết kế mạch điện [18]. Steele được xem là người đầu tiên chỉ ra sự tương đồng về khái niệm giữa giải quyết ràng buộc và lập trình logic.
Việc giải quyết ràng buộc được xử lý bằng sự nhất quán của các hàm thập phân cũng như bằng cách lý luận về các hàm trừu tượng. Các ngôn ngữ mô hình toán học như AMPL và các gói thao tác đại số tượng trưng như MATLAB cũng chia sẻ một số điểm tương đồng với ngôn ngữ CLP, cho phép xử lý một vấn đề xác định bằng phương pháp toán học (sử dụng bộ giải từ bên ngoài trong trường hợp ngôn ngữ modeling; sử dụng phương pháp giải toán đại số và số được hỗ trợ bởi các gói đại số). Khái niệm các bài toán thỏa mãn điều kiện ràng buộc (Constraint Satisfaction Problems - CSPs) cũng được chính thức công nhận bởi cộng đồng trí tuệ nhân tạo (AI). Họ cũng chỉ ra những khái niệm cơ bản của tính nhất quán cục bộ (local consistency) và các thuật toán để giải chúng.
Một 6 cách độc lập, nhiều phương pháp khác nhau cũng đã được hình thành, ví dụ như phương pháp tìm kiếm quay lui (backtracking) được đưa ra từ thế kỷ 19, trong khi khái niệm nhánh cận (branch and bound) được đưa ra trong tính toán tối ưu tổ hợp.