Chương 1 giới thiệu chung đề tài đang nghiên cứu • Chương 2 giới thiệu bài toán sắp lịch cho kênh mua sắm truyền hình, tình hình nghiên cứu và các công trình nghiên cứu liên quan • Chương 3 giới thiệu các cơ sở lý thuyết về mô hình dự báo, giải thuật tính toán được áp dụng cho luận văn • Chương 4 mô hình hóa toán học bài toán sắp lịch, chứng minh bài toán thuộc lớp bài toán NP − complete • Chương 5 đề xuất giải pháp để giải quyết bài toán sắp lịch bao gồm quy trình sắp lịch đề xuất, các giải thuật heuristic và giải thuật di truyền • Chương 6 thể hiện các kết quả thực nghiệm khi áp dụng các giải thuật đề xuất trên dữ liệu 3 Chương 2 Tổng quan Công ty tham gia kinh doanh trong lĩnh vực mua sắm trên sóng truyền hình thực hiện việc quảng bá và kích thích khách hàng mua sản phẩm thông qua các chương trình quảng cáo. Mỗi chương trình được thiết kế để giới thiệu một cách sinh động các tính năng mà sản phẩm cung cấp, đi kèm những khuyến mãi hấp dẫn. Một kênh truyền hình được thuê để phục vụ việc trình chiếu liên tục các quảng cáo về mặt hàng công ty cung cấp. Người xem sẽ đánh giá sản phẩm và từ đó ra quyết định mua hàng.
Quy trình hoạt động này được biểu diễn như hình 2.Trong đó, đài truyền hình sẽ yêu cầu lịch chiếu các chương trình từ phía công ty theo chu kỳ. Vì vậy công ty cần có một đội ngũ chuyên gia am hiểu nghiệp vụ, thị trường, cũng như nhu cầu của khách hàng để sắp lịch chiếu một cách hợp lý nhất. sản phẩm Làm chương trình Chương trình Quyết định mua Lập lịch Khách hàng Phát sóng Lịch chiếu Hình 2.1: Quy trình vận hành nghiệp vụ 4 Các công việc chính mà chuyên gia sắp lịch cần thực hiện là tổng hợp dữ liệu bán hàng của từng sản phẩm đã được quảng cáo. Với số liệu doanh số bán và lượng hàng tồn kho họ tính ra được nhu cầu của thị trường cũng như nguồn cung từ công ty để cân đối việc quảng cáo như hình 2.
Nhằm mục đích tránh tình trạng một mặt hàng công ty đã sắp hết hàng thì được quảng cáo quá nhiều, khách hàng sẽ liên tục mua mà công ty không đáp ứng được. Trong khi có những mặt hàng khác bị tồn kho không được quảng cáo đủ để người xem biết và tiêu thụ. Như vậy sẽ làm lãng phí tài nguyên không hiệu quả cho cả người xem và công ty.2: Số liệu sản lượng bán hàng hằng ngày Sau khi đã có được số liệu thống kê về doanh số bán hàng của các sản phẩm trong một chu kỳ, chương trình quảng cáo cho chúng sẽ được đánh giá độ hiệu quả thông qua một công thức tính trung bình sẽ được nói chi tiết trong phần 5. Các số liệu thống kê chính được tổng hợp để hỗ trợ sắp lịch được thể hiện như hình 2.3: Số liệu được tổng hợp theo chu kỳ Với những dữ liệu thống kê từ chu kỳ trước đó, người sắp lịch kết hợp với kinh nghiệm do tìm hiểu thị trường sẽ ra quyết định chương trình quảng cáo nào sẽ được chiếu bao nhiêu lần một ngày và được chiếu vào những khung giờ nào.
Lịch chiếu được hình thành và chuyển đến đài truyền hình. Lịch chiếu ở đây là lịch chiếu theo ngày, nghĩa là các ngày tiếp theo sẽ chiếu giống nhau. Thời gian này gọi là một chu kỳ chiếu. Kết thúc chu kỳ chiếu, lịch chiếu mới sẽ được tạo để cập nhật với thị trường.
Nội dung lịch chiếu như hình 2.4: Lịch phát sóng Tóm tắt quy trình sắp lịch hiện tại của công ty mà nghiên cứu đang thực hiện như hình 2. Thống kê Chỉ số hiệu quả Lập lịch Sản lượng bán hàng Lịch phát sóng Phát sóng Hình 2.5: Quy trình sắp lịch hiện tại Từ quy trình sắp lịch hiện tại, công ty có như cầu muốn cải thiện chất lượng sắp lịch thông qua việc tự động hóa các bước sắp lịch. Để thực hiện được công việc này đòi hỏi các bước cải thiện sau: 7 • Đề xuất quy trình lập lịch mới nhằm nâng cao khả năng dự báo, nắm bắt sự thay đổi của thị trường. • Áp dụng các giải thuật tiên đoán để tìm ra độ hiệu quả của các chương trình trong tương lai gần mà ở đây là chu kỳ kế tiếp.
• Thiết kế giải thuật để sắp lịch dựa trên thông số độ hiệu quả dự báo. • Hiệu chỉnh mô hình dự báo theo thời gian khi có dự liệu mới được cập nhật để đảm bảo tính thích ứng theo thị trường. Bài toán dự báo và hiệu chỉnh độ hiệu quả cho các chương trình quảng cáo Để có thể biết được một lịch chiếu đã đạt hiệu quả cần dựa vào doanh thu mà lịch chiếu mang lại. Trong đó mỗi quảng cáo sẽ đóng góp riêng phần một phần doanh thu cho toàn bộ lịch chiếu.
Chính vì tính chất này nên chỉ số hiệu quả của các chương trình quảng cáo sẽ đánh giá doanh thu mà chúng mang lại và mức tiêu hao tài nguyên thời gian. Với chỉ số hiệu quả này người sắp lịch có thể đánh giá nhanh chất lượng của quảng cáo và mặt hàng mà nó đang quảng cáo. Vì vậy độ hiệu quả là một thông số quan trọng hàng đầu cần chú ý khi sắp lịch. Để biết được độ hiệu quả của chương trình trong chu kỳ kế tiếp cần phải thực hiện một quá trình dự báo.
Hiện nay các công ty đang áp dụng mô hình dự báo sử dụng dữ liệu trong một thời gian ngắn trước đó (1 đến 2 chu kì trước) để thống kê và áp dụng cho chu kỳ kế tiếp. Đề tài muốn kiểm tra độ hiệu quả của các cách làm này bằng so sánh với một số mô hình dự báo thông dụng khác. Kết quả của qúa trình dự báo sẽ là dữ liệu đầu vào cho bài toán sắp lịch sau đó. Bài toán sắp lịch Bài toán sắp lịch được miêu tả cơ bản như sau: công ty có một danh sách các sản phẩm cần được bán.
Ứng với mỗi sản phẩm sẽ có một chương trình quảng cáo cho nó. Các chương trình quảng cáo được lượng giá độ hiệu quả thông qua một chỉ số gọi là độ hiệu quả. Từ đó, các chương trình này được chia thành các nhóm chương trình dựa trên ngưỡng hiệu quả định trước. Mỗi nhóm chương trình lại được quy định tổng thời lượng phát sóng trong một ngày.
Dựa vào mức độ hàng tồn kho, xu hướng mua hàng mà mỗi chương trình được giới hạn số lần phát tối đa trong một ngày. Đồng thời, mỗi chương trình sẽ được quy định cụ thể các khung giờ mà chúng 8 có thể được trình chiếu dựa trên kinh nghiệm của chuyên gia sắp lịch. Họ chia thời gian chiếu một ngày ra thành các khung giờ liên tiếp dựa trên lượng người xem, và lượng mua hàng. Lịch chiếu cần phải thỏa mãn nhiều ràng buộc như: thời gian chiếu, khung giờ được phép chiếu, thời lượng chiếu của nhóm, các chương trình không được chiếu chồng lấp lên nhau, một chương trình được chiếu lại không quá gần lần chiếu trước (chi tiết các ràng buộc sẽ được trình bày ở chương 3).
Luận văn sẽ đề xuất quy trình sắp lịch cho kênh mua sắm trên sóng truyền hình. Dựa vào quy trình đã đề xuất, đưa ra những giải quyết cụ thể cho từng bước trong quy trình bao gồm: dự báo, lập lịch và hiệu chỉnh. Luận văn sẽ mô hình hóa toán học bài toán lập lịch và đưa ra lời giải cho bài toán tối ưu. Tình hình nghiên cứu Hiện nay có nhiều nghiên cứu sắp lịch cho quảng cáo trên truyền hình [1, 3], quảng cáo trên tạp chí, báo [5], hay trên các trang mạng [15].
Với mỗi loại hình quảng cáo thì các nguyền tài nguyên chính cần quan tâm là không gian và thời gian. Đối với quảng cáo trên sóng truyền hình thời gian luôn được ưu tiên xem xét. Đài truyền hình cần tính toán để sắp lịch các quảng cáo như thế nào để đạt doanh thu cao nhất. Bởi vì nguồn thu nhập chính của các đài truyền hình xuất phát từ phát sóng quảng cáo.
Một bài toán đặt ra đối với họ là sắp xếp các quảng cáo theo yêu cầu của khách hàng vào các khung giờ quảng cáo một cách hợp lý để thu được doanh thu tối đa. Alaei và cộng sự [1] đã áp dụng chiến lược đấu giá nhiều món hàng (multi-unit combinatorial auction) kết hợp với giải thuật tiến hóa để giải quyết bài toán này. Nghiên cứu của họ cho thấy giải thuật di truyền (GA) đề xuất có độ chính xác gần như không đổi khi tăng kích thước bài toán thực. Một yếu tố thường được chú ý trong sắp lịch quảng cáo truyền hình truyền thống là tỉ lệ người xem (audience ratings).
Các nhà quảng cáo trả tiền để tăng lượng người xem cho các quảng cáo của mình. Một nghiên cứu ở Trung Quốc giải quyết bài toán sắp lịch quảng cáo cho các quảng cáo dựa vào hai yếu tố là tỉ lệ người xem và độ dài quảng cáo để tối đa hóa doanh thu cho đài truyền hình. Ru Bai và Jinxing Xie [3] đã mô hình hóa bài toán theo mô hình quy hoạch nguyên (interger programming model), lấy tích số giữa tỉ lệ người xem mà nhà quảng cáo yêu cầu và thời lượng quảng cáo làm giá trị đo doanh thu cho mỗi quảng cáo. Tác giả đã đưa ra ba giải thuật heuristic để giải quyết bài toán NP −Complete này.
Kết quả thực nghiệm cho thấy giải thuật hiệu quả với dữ liệu giả lập. Trong khi đó quảng cáo trên báo, tạp chí và trang mạng, yếu tố không gian để đặt quảng cáo luôn được tối ưu hóa để thu hút dược người đọc nhưng tiết kiệm diện tích. 9 Nghiên cứu về cách đăng tải quảng cáo hợp lý vào các vị trí nhất định trên website áp dụng giữa giải thuật heuristic đề xuất và giải thuật di truyền thiết kế riêng cho bài toán sao cho quảng cáo có được số lượng người xem trung bình thỏa mãn yêu cầu khách hàng đồng thời tăng doanh thu quảng cáo. Kumar [15] và đồng nghiệp đã cho thấy được sự cải tiến đáng kể khi thử nghiệm giải thuật lai giữa giải thuật di truyền và giải thuật heuristic tự đề xuất dựa trên giải thuật bin-packing so với một giải thuật heuristic đã tồn tại trước đó.
Kết quả thực nghiệm cho thấy giải thuật mới cải thiện trên 87% so với giải thuật đã đề xuất trước đó. Điều này giúp cho doanh thu của quảng cáo trên trang mạng được tối đa hóa.
