Nghiên cứu mô hình và thuật toán tối ưu lựa chọn địa điểm trong điều kiện bất định

Tìm hiểu mô hình tối ưu mạnh giúp lựa chọn địa điểm hiệu quả trong điều kiện bất định, ứng dụng thực tế và phương pháp giải quyết tối ưu.

• Tác giả: Đàm Tiến Thành
• Người hướng dẫn: TS. Tạ Thúy Anh
• Trường học: Đại học Phenikaa
• Chuyên ngành: Khoa học máy tính
• Đề tài: Nghiên cứu mô hình tối ưu mạnh và thuật toán cho một lớp các bài toán lựa chọn địa điểm trong điều kiện bất định
• Loại tài liệu: Luận văn thạc sĩ
• Năm xuất bản: 2023
• Địa điểm: Hà Nội

Tóm tắt

I. Khái Niệm Mô Hình Tối Ưu Mạnh Trong Lựa Chọn Địa Điểm

Mô hình tối ưu mạnh là một phương pháp tiên tiến trong lĩnh vực lựa chọn địa điểm khi đối mặt với bất định dữ liệu. Khác với các mô hình tối ưu truyền thống, mô hình tối ưu mạnh không giả định các tham số mô hình RUM (Random Utility Maximization) là cố định mà coi chúng có thể thay đổi trong các tập bất định lồi. Điều này giúp các nhà quản lý ra quyết định một cách thận trọng hơn, đảm bảo lựa chọn địa điểm có thể chịu được những biến động không lường trước được trong hành vi khách hàng. Phương pháp này kết hợp với mô hình GEV (Generalized Extreme Value) để mô hình hóa chính xác hơn sự lựa chọn của người tiêu dùng trong thị trường cạnh tranh.

1.1. Định Nghĩa Và Đặc Điểm Của Mô Hình Tối Ưu Mạnh

Mô hình tối ưu mạnh là phương pháp tối ưu hóa xem xét các kịch bản xấu nhất trong điều kiện bất định. Nó đảm bảo giải pháp có tính đơn điệu và submodular, cho phép sử dụng thuật toán tham lam đơn giản với xấp xỉ (1 − 1/e). Đặc điểm chính là không yêu cầu dữ liệu chính xác tuyệt đối mà vẫn đưa ra quyết định tối ưu trong các điều kiện bất định.

1.2. Ứng Dụng Trong Bối Cảnh Kinh Doanh Hiện Đại

Trong thị trường cạnh tranh, các doanh nghiệp sử dụng mô hình tối ưu mạnh để quyết định mở cửa hàng ở vị trí nào nhằm tối đa hóa lợi nhuận. Mô hình này đặc biệt hữu ích khi dữ liệu khách hàng thay đổi liên tục, giúp giảm thiểu rủi ro khi dự báo không chính xác.

II. Mô Hình RUM Và GEV Trong Lựa Chọn Địa Điểm

Mô hình Random Utility Maximization (RUM) là nền tảng của lựa chọn địa điểm tối ưu mạnh. Theo mô hình này, mỗi khách hàng lựa chọn một địa điểm dựa trên tối đa hóa độ khả dụng (utility) của họ. Mô hình GEV (Generalized Extreme Value) mở rộng khả năng này bằng cách cho phép các mối tương quan phức tạp giữa các lựa chọn địa điểm. Khi kết hợp với mô hình tối ưu mạnh, GEV giúp doanh nghiệp hiểu rõ hơn cách khách hàng phân bổ nhu cầu của họ giữa các địa điểm khác nhau. Đặc biệt, mô hình Multinomial Logit (MNL) - một trường hợp đặc biệt của GEV - cho thấy tính lõm của hàm mục tiêu, điều này cho phép sử dụng phương pháp tối ưu hóa lồi hiệu quả.

2.1. Nguyên Tắc Hoạt Động Của Mô Hình RUM

Mô hình RUM giả định khách hàng chọn địa điểm có độ khả dụng cao nhất. Trong mô hình tối ưu mạnh, các thành phần của RUM không cố định mà nằm trong tập bất định lồi, cho phép xem xét nhiều kịch bản khác nhau về hành vi khách hàng.

2.2. Vai Trò Của Mô Hình GEV Và MNL

Mô hình GEV cung cấp sự linh hoạt trong mô hình hóa hành vi chọn lựa phức tạp. Mô hình MNL đơn giản hơn nhưng vẫn hiệu quả, với tính lõm của hàm mục tiêu giúp giải quyết bài toán tối ưu mạnh đến mức tối ưu toàn cục bằng phương pháp outer-approximation.

III. Thuật Toán Tham Lam Và Phương Pháp Tối Ưu Hóa

Một trong những đóng góp quan trọng của mô hình tối ưu mạnh là chứng minh rằng tính submodular được duy trì từ bài toán lựa chọn địa điểm ban đầu. Điều này cho phép sử dụng thuật toán tham lam (greedy algorithm) đơn giản để tìm kiếm giải pháp gần tối ưu với xấp xỉ (1 − 1/e) so với giải pháp tối ưu toàn cục. Thuật toán này hoạt động bằng cách lặp lại chọn địa điểm mới có lợi nhuận gia tăng tối đa, cho đến khi đạt được số lượng cơ sở mong muốn. Ngoài ra, đối với mô hình MNL, phương pháp xấp xỉ bao lồi (outer-approximation) được sử dụng để giải mô hình tối ưu mạnh đến mức tối ưu hoàn toàn, cung cấp giải pháp chính xác hơn khi cần thiết.

3.1. Thuật Toán Tham Lam Với Tính Submodular

Thuật toán tham lam tận dụng tính submodular để đảm bảo giải pháp xấp xỉ (1 − 1/e). Thuật toán này đơn giản, nhanh chóng và đặc biệt phù hợp cho các bài toán lựa chọn địa điểm quy mô lớn trong điều kiện bất định dữ liệu.

3.2. Phương Pháp Outer Approximation Cho Mô Hình MNL

Phương pháp outer-approximation tận dụng tính lõm của hàm mục tiêu trong mô hình MNL để giải mô hình tối ưu mạnh đến mức tối ưu toàn cục. Phương pháp này hiệu quả hơn khi yêu cầu giải pháp chính xác thay vì xấp xỉ.

IV. Kết Quả Thực Nghiệm Và Ứng Dụng Thực Tế

Các thử nghiệm so sánh mô hình tối ưu mạnh với các phương pháp lấy mẫu và tất định khác đã chứng minh rõ ràng những lợi thế của phương pháp này. Kết quả cho thấy mô hình tối ưu mạnh giúp tối đa hóa lợi nhuận trong trường hợp xấu nhất, tránh được các kết quả tệ khi dữ liệu thay đổi hoặc không chính xác. So với các phương pháp truyền thống, mô hình tối ưu mạnh cung cấp một cách tiếp cận an toàn hơn, cho phép các nhà quản lý tự tin hơn khi lựa chọn địa điểm mở cửa hàng mới. Các thử nghiệm sử dụng các phiên bản từ các mô hình lựa chọn riêng biệt khác nhau, mô phỏng các tình huống thực tế khác nhau trong thị trường cạnh tranh.

4.1. So Sánh Hiệu Suất Với Các Phương Pháp Khác

Các thử nghiệm cho thấy mô hình tối ưu mạnh vượt trội hơn các phương pháp lấy mẫu thông thường khi đối mặt với bất định dữ liệu. Mô hình này cung cấp giải pháp xấp xỉ chất lượng cao với chi phí tính toán thấp, làm cho nó trở thành lựa chọn tối ưu cho các doanh nghiệp.

4.2. Ứng Dụng Trong Quản Lý Chuỗi Bán Lẻ

Trong quản lý chuỗi bán lẻ, mô hình tối ưu mạnh giúp các công ty lựa chọn địa điểm mở cửa hàng mới sao cho tối đa hóa lợi nhuận ngay cả khi dự báo khách hàng không chính xác. Điều này giảm rủi ro kinh doanh và cải thiện khả năng thích ứng với thị trường biến động.

Trích đoạn nội dung tài liệu

BỘ GIÁO DỤC VÀ ĐÀO TẠO ĐÀM TIẾN THÀNH TRƯỜNG ĐẠI HỌC PHENIKAA LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH ĐÀM TIẾN THÀNH NGHIÊN CỨU MÔ HÌNH TỐI ƯU MẠNH VÀ THUẬT TOÁN CHO MỘT LỚP CÁC BÀI TOÁN LỰA CHỌN ĐỊA ĐIỂM TRONG ĐIỀU KIỆN BẤT ĐỊNH LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH HÀ NỘI -2023 HÀ NỘI – 2023 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC PHENIKAA ĐÀM TIẾN THÀNH NGHIÊN CỨU MÔ HÌNH TỐI ƯU MẠNH VÀ THUẬT TOÁN CHO MỘT LỚP CÁC BÀI TOÁN LỰA CHỌN ĐỊA ĐIỂM TRONG ĐIỀU KIỆN BẤT ĐỊNH Ngành: Khoa học máy tính Mã số: 8480101 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. Tạ Thúy Anh HÀ NỘI - 2023 Lời cam đoan Tôi xin cam đoan tuân thủ quy định về liêm chính học thuật và các quy định hiện hành của pháp luật về sở hữu trí tuệ, việc sử dụng hoặc trích dẫn kết quả nghiên cứu của người khác đã được dẫn nguồn đầy đủ, rõ ràng tại vị trí trích dẫn và tại danh mục tài liệu tham khảo. Kết quả nghiên cứu trong luận văn là kết quả lao động của chính tôi, chưa được người khác công bố trong bất cứ một công trình nghiên cứu nào. Hà Nội, ngày … tháng … năm 202… (Học viên ký, ghi rõ họ và tên) Lời cảm ơn Trước hết, tôi không biết phải bày tỏ lòng biết ơn như thế nào cho đủ đối với người hướng dẫn luận văn của tôi, TS.

Tạ Thúy Anh và TS. Mai Anh Tiến. Trong quá trình hơn một năm học tập tại ngôi trường đại học Phenikaa, hai thầy cô đã cho tôi rất nhiều động lực, những ý tưởng hay, sự nhiệt tình, sự cầu tiến và nghiêm túc trong công việc đã truyền cho tôi rất nhiều cảm hứng để học tập, làm việc và cũng như là hoàn thành được tốt luận văn này. Hai thầy cô cũng cho tôi rất nhiều cơ hội được học tập và làm việc ở nước ngoài để tôi được cải thiện kỹ năng tiếng Anh, khả năng làm việc trong môi trường nước ngoài.

Không chỉ thế, hai thầy cô cũng giúp tôi được trao đổi, gặp mặt, chia sẻ công việc với những nhà nghiên cứu nổi bật trong ngành để tôi được tiếp thu thêm nhiều những ý tưởng hay, thú vị để góp phần hoàn thiện tốt hơn luận văn này. Hơn nữa, hai thầy cô còn quan tâm, giúp đỡ tôi trong cả cuộc sống hàng ngày, động viên tôi những lúc khó khăn hoặc mất năng lượng. Với tôi, hai thầy cô không chỉ là những nhà nghiên cứu, người hướng dẫn đơn thuần mà còn là người anh, người chị thân thiết vậy. Tất cả những gì hai thầy cô đã làm cho tôi không chỉ đóng góp trực tiếp vào công việc được trình bày trong luận án này, mà còn là cả con đường nghiên cứu sau này của tôi nữa.

Tôi rất biết ơn TS. Hà Minh Hoàng, trưởng nhóm nghiên cứu ORlab – nơi tôi làm việc, đã luôn động viên, hỗ trợ tôi hoàn thành các môn học cũng như là đưa ra cho tôi những lời khuyên bổ ích để tôi định hướng cho con đường nghiên cứu sau này của mình. Tôi cũng xin gửi lời cảm ơn đến PGS. Nguyễn Trung Thành.

Thầy đã hỗ trợ tôi rất nhiều trong việc nắm rõ được khung chương trình đào tạo, hoàn thiện các thủ tục, giấy tờ và tạo điều kiện tốt nhất cho tôi để tôi có thể hoàn thành thuận lợi các môn học và luận văn này. Tôi rất cảm ơn tập thể nhóm nghiên cứu ORlab đã cho tôi một môi tường năng động để làm việc, sáng tạo và cũng như là giúp tôi rèn luyện sức khỏe để có thể duy trì tốt được công việc và học tập. Tôi rất biết ơn đối với bố, mẹ, hai chị và anh rể tôi vì đã luôn là một hậu phương vững chắc giúp đỡ cho tôi có những bữa ăn hàng ngày đầy đủ, ngon miệng, giúp tôi được nghỉ ngơi, thoải mái, tạo điều kiện hết mức cho tôi có một không gian riêng tư để làm việc và học tập. Tóm tắt Chúng tôi nghiên cứu một phiên bản mạnh (robust) của bài toán lựa chọn địa điểm để khai thác tối đa lợi nhuận trong thị trường cạnh tranh, giả định rằng mỗi khách hàng chọn địa điểm để đến trong số tất cả các địa điểm có sẵn theo mô hình tối đa hóa độ khả dụng (random utility maximization - RUM).

Chúng tôi sử dụng họ mô hình giá trị cực trị tổng quát (generalized extreme value - GEV) và giả định rằng các thành phần của mô hình RUM không được đưa ra chính xác mà thay đổi và nằm trong các tập bất định lồi. Bài toán yêu cầu xác định một tập các địa điểm để mở cơ sở mới sao cho tối đa hóa lợi nhuận thu được từ khách hàng trong trường hợp xấu nhất. Trong nghiên cứu này, chúng tôi chỉ ra rằng mô hình mạnh của chúng tôi vẫn duy trì tính đơn điệu và tính submodular từ bài toán lựa chọn địa điểm ban đầu, và điều đó cho phép một phương pháp tìm kiếm tham lam đơn giản có thể đảm bảo đưa ra giải pháp xấp xỉ (1 − 1/𝑒) so với giải pháp tối ưu. Chúng tôi cũng chỉ ra độ lõm của hàm mục tiêu theo mô hình logit đa thức cổ điển (multinomial logit - MNL), từ đó cho thấy rằng có thể sử dụng phương pháp xấp xỉ bao lồi (outer-approximation) để giải mô hình tối ưu mạnh theo mô hình lựa chọn MNL đến mức tối ưu.

Chúng tôi tiến hành các thử nghiệm so sánh mô hình tối ưu mạnh của chúng tôi với các phương pháp lấy mẫu và tất định khác, sử dụng các phiên bản từ các mô hình lựa chọn riêng biệt khác nhau. Kết quả của chúng tôi chứng minh rõ ràng những lợi thế của mô hình tối ưu mạnh của chúng tôi trong việc giúp người ra quyết định tránh được các kết quả tệ khi dữ liệu thay đổi. ABSTRACT This study investigates a robust approach to the facility location problem in a competitive market, where a new firm enters the market and has to select a set of locations to open new facilities so as to maximize the captured customer demand. The captured customer demand is estimated by the generalized extreme value (GEV) family of models, which is based on a ran- dom utility maximization (RUM) framework.

We consider that the RUM model parameters lie in convex variability sets. In robust settings, the objective is to find the locations of new facilities that maximize the worst-case captured user demand. Surprisingly, our robust model preserves its deterministic counterpart’s monotonicity and submodularity properties, enabling a simple greedy heuristic to yield a (1 − 1/e) approximation solution. We also demonstrate the concavity of the objective function under the classical multinomial logit (MNL) model, indicating that an outer-approximation algorithm can optimally solve the robust model under MNL.

We perform experiments using instances from various discrete choice models and com- pare our robust method to other deterministic and sampling-based approaches. Our findings highlight the benefits of our robust model in safeguarding against worst-case scenarios. Key words: Facilities planning and design, maximum capture, random utility maximization, robust optimization, local search, outer-approximation. i CONTENTS List of Figures v List of Tables viii List of Abbreviations ix 1 Introduction 1 1.1 Problem, Motivation, and Objectives.

7 2 Background: Deterministic MCP under RUM 9 2.1 Discrete choice models .1 The RUM Framework .2 The GEV family .3 The estimation of choice models .2 The Deterministic MCP .1 Robust MCP under GEV models .2 Robust MCP under MNL .1 Local Search for GEV-based Robust MCP .2 Outer-Approximation for the Robust MCP under MNL .1 Constructing Uncertainty Sets .2 Baseline Approaches and Other Settings .2 Comparison with Mehmanchi’s robust approach .3 Nested Logit Instances .4 Percentile Ranks of the RO’s Worst-case Objective Values .4 Computing Time Comparison. 56 6 Conclusion 62 iii Bibliography 64 A Proofs 73 A.1 Proof of Lemma 1 .2 Proof of Proposition 2 .3 Proof of Proposition 3 .1 Comparing across the MNL and Nested Logit Models .2 Objective Value Distributions. 80 iv LIST OF FIGURES 5.1 The value of robustness for instances using the MNL model; the per- formances of DET1 and DET2 are nearly indistinguishable.2 Price of robustness for instances using the MNL model.3 The results of the captured demand distributions obtained from solu- tions of the RO, SA, DET1, and DET2 methods are compared under the MNL model for instances with a size of |I| = 100 and m = 50 and different uncertainty level ϵ.4 The value of robustness for instances using the nested logit model; the performances of DET1 and DET2 are nearly indistinguishable.5 Price of robustness for instances using the nested logit model. The results of the captured demand distributions obtained from so- lutions of the RO, SA, DET1, and DET2 methods are compared under the nested logit model for instances with a size of |I| = 100 and m = 50 and different uncertainty level ϵ.7 The percentile ranks of the RO’s worst-case values in the distribu- tions given by the SA, DET1 and DET2 solutions under the MNL and nested choice models for instance of |I| = 100 and m = 50.1 Comparison of the distributions of the nested-logit objective values given by solutions from the MNL and the nested logit model for in- stance of |I| = 100 and m = 50.2 The results of the captured demand distributions obtained from solu- tions of the RO, SA, DET1, and DET2 methods are compared under the MNL model for instances with a size of |I| = 100 and m = 100 and different uncertainty level ϵ.3 The results of the captured demand distributions obtained from so- lutions of the RO, SA, DET1, and DET2 methods are compared un- der the nested logit model for instances with a size of |I| = 100 and m = 100 and different uncertainty level ϵ.4 The percentile ranks of RO worst value in the distributions given by the SA, DET1, and DET2 solutions under the MNL choice model for instance with |I| = 100 and m = 100.5 The results of the captured demand distributions obtained from solu- tions of the RO, SA, DET1, and DET2 methods are compared under the MNL model for instances with a size of |I| = 200 and m = 100 and different uncertainty level ϵ.6 The results of the captured demand distributions obtained from so- lutions of the RO, SA, DET1, and DET2 methods are compared un- der the nested logit model for instances with a size of |I| = 200 and m = 100 and different uncertainty level ϵ.7 The percentile ranks of RO worst value in the distributions given by the SA, DET1, and DET2 solutions under the nested logit choice model for instance with |I| = 200 and m = 100.8 The results of the captured demand distributions obtained from solu- tions of the RO, SA, DET1, and DET2 methods are compared under the MNL model for instances with a size of |I| = 1000 and m = 100 and different uncertainty level ϵ.