Bài giảng Khoa học dịch vụ: Chương 6 - PGS.TS. Hà Quang Thụy

Chương 6 - Bài toán định vị và phân bố trong dịch vụ. Những nội dung chính được trình bày trong chương gồm có: Cung cấp ví dụ cho bài toán định vị, giới thiệu các loại bài toán định vị, các mô hình phủ, các mô hình khoảng cách trung bình theo trọng số, mô hình đa mục tiêu: kết hợp hai dòng mô hình, mô hình phân bố, mô hình nhượng quyền thương mại.
Nội dung trích xuất từ tài liệu:
Bài giảng Khoa học dịch vụ: Chương 6 - PGS.TS. Hà Quang Thụy NHẬP MÔN KHOA HỌC DỊCH VỤ CHƯƠNG 6. BÀI TOÁN ĐỊNH VỊ VÀ PHÂN BỐ TRONG DỊCH VỤ PGS. TS. HÀ QUANG THỤY HÀ NỘI 09-2018 TRƯỜNG ĐẠI HỌC CÔNG NGHỆ ĐẠI HỌC QUỐC GIA HÀ NỘI 1 Nội dung chương ➢Giới thiệu ➢ Một số ví dụ ➢ Phân loại các bài toán định vị ➢ Vấn đề phủ ➢ Vấn đề định vị: Cực tiểu khoảng cách trung bình trọng số nhu cầu Mark S. Daskin. Network and Discrete Location Models, Algorithms, and Applications (2nd edition). John Wiley & Sons, 2013 KHDV 2018 – Chương 6 - Trang 2 1. Giới thiệu ➢ Bài toán định vị và phân bố ❖ Thường gặp trong cung cấp dịch vụ ❖ Quyết định mở rộng phạm vi: Thuyết phục về độ hiệu quả ❖ Ràng buộc: trong một tài nguyên hạn chế. ❖ Có bổ sung ngân sách ? ➢Nội dung của chương ❖ Cung cấp ví dụ cho bài toán định vị ❖ Giới thiệu các loại bài toán định vị ❖ Các mô hình phủ ❖ Các mô hình khoảng cách trung bình theo trọng số ❖ Mô hình đa muc tiêu: kết hợp hai dòng mô hình ❖ Mô hình phân bố ❖ Mô hình nhượng quyền thương mại KHDV 2018 – Chương 6 - Trang 3 2. Ví dụ 1: định vị xe cấp cứu ➢ Dịch vụ xe cấp cứu tại Austin ❖ Thành phố Austin, bang Texas, Mỹ ❖ Là dịch vụ thứ ba: sau DV cảnh sát và DV cứu hỏa ➢Hiện trạng ❖ Một đội xe cấp cứu thường trực 24 giờ/nghỉ 24 giờ ❖ Cần căn hộ có thể ăn, ngủ, thư giãn ❖ Xe cấp cứu: trang bị y tế đắt tiền, phải đưa lên căn hộ ❖ Thời gian đưa trang bị mất 1-2 phút ➢Yêu cầu ❖ Cần định vị ví trí đặt xe cấp cứu: có ngay xe, an toàn ❖ Một số câu hỏi : ❖ Cần bao nhiêu cơ sở đặt xe cứu thương? ❖ Vị trí cụ thể của các cơ sở đặt xe ? ❖ Loại mức xe hoạt động tại mỗi cơ sở ? Hai loại: Thường/cao cấp. ❖ Mục tiêu: Một mục tiêu đã nói trước đây KHDV 2018 – Chương 6 - Trang 4 Ví dụ 2: Định vị trạm phục hồi thảm họa ➢ Giới thiệu ❖ Yêu cầu của Cơ quan quản lý thảm họa (The Federal Emergency Management Agency: FEMA) ❖ Mỗi quận cần thành lập Trạm phục hồi thảm họa ❖ Diện tích  2000 feet vuông, hệ thống sưởi, điều hòa, điện thoại và fax, không bị ngập lụt, + các tiêu chuẩn khác ❖ FEMA yêu cầu quận Alachua đặt ít nhất 3 trạm ➢Một số mục tiêu ❖ Cực tiểu khoảng cách trung bình cư dân phải đi tới trạm gần nhất ❖ Cực tiểu khoảng cách cực đại mà mọi cư dân phải đi tới trạm gần nhất ❖ Cực tiểu số trung tâm cần thiết đảm bảo mọi cư dân nằm trong khoảng cách cho trước tới trạm gần nhất ❖ Cực đại xác suất có 1 trạm làm việc khi thảm họa xảy ra KHDV 2018 – Chương 6 - Trang 5 Ví dụ: Định vị trạm phục hồi thảm họa ➢ Một số nội dung ❖ Quận được chia thành 6600 lô với 3900 lô đáp ứng yêu cầu FEMA ❖ Giao cho nhóm sinh viên: Vượt quá khả năng ➢ Hướng giải quyết sơ bộ ❖ Sử dụng phần mềm thương mại ❖ Tạo thành 198 điểm yêu cầu với 162 định vị ứng viên ❖ Chia hai giai đoạn ❖ Giai đoạn 1: Mô hình toán học tìm ra ba điểm mà hầu như dân cư ở khoảng cách  20 dặm ❖ Giai đoạn 2: Tìm kiếm nghiệm thực sự yêu cầu FEMA KHDV 2018 – Chương 6 - Trang 6 Hệ thống Công tơ mét tự động ➢ Giới thiệu ❖ Công ty Shlumberger cung cấp công tơ khí đốt, điện, nước tự động toàn cầu ❖ Bài toán cốt lõi: Định vị bộ thu công tơ (automated meter readers: AMR) ➢Nội dung ❖ Bộ thu thường đặt ở cột điện thoại ❖ Phạm vi bộ thu: một hàm theo chiều cao cột, môi trường ❖ Mỗi bộ thu quản lý nhiều nhất khoảng cách 540 m, tuy nhiên, thực tiễn nhỏ hơn đáng kể ❖ Mục tiêu: Cực tiểu số bộ thu cần để đọc được mọi công tơ trong một vùng lãnh thổ & đảm bảo giới hạn bộ thu ❖ Công ty làm việc với HTTT địa lý. Rất chậm, cần cải tiến ❖ Phát triển 116.000 địa điểm khách hàng và hơn 20.000 cột điện thoại KHDV 2018 – Chương 6 - Trang 7 Ví dụ 4: Định vị mồi cho Brachytherapy ➢ Giới thiệu ❖ Ung thư tiền liệt tuyến 225.000 ở Mỹ và nửa triệu thế giới ❖ Brachytherapy thủ tục điều trị phổ biến mà đặt khoảng 60-150 hạt phóng xạ nhỏ ở tuyến liệt để tấn công khối u ❖ Bài toàn: bao nhiêu mồi và nơi đặt chúng ? ❖ Phương pháp truyền thống xác định mồi: đòi hỏi siêu âm hoặc cắt lớp. Bác sỹ xác định vị trí đặt hạt. Nhiều điểm hạn chế. ➢Phương pháp cải tiến ❖ Mục tiêu: 95% các điểm ảnh ba chiều (voxel) nhận được lượng phóng xạ cần thiết ❖ Định vị các mồi để tối đa hóa các điểm đáp ứng yêu cầu quy định hoặc tối thiểu hóa sai lệch so với yêu cầu ❖ PP mới cải thiện định vị hạt giống, làm giảm đáng kể thời gian lập kế hoạch phẫu thuật. KHDV 2018 – Chương 6 - Trang 8 3. Phân loại các bài toán định vị 19/10/18 ➢ Giới thiệu ❖ Một số cách phân loại bài toán định vị ❖ Theo giả định, nhu cầu nơi đặt v.v. hướng tối ưu hóa. ❖ Một phân loại điển hình là theo “không gian” ❖ Hình vẽ: các mô hình giải tích, liên tục, mạng và rời rạc KHDV 2018 – Chương 6 - Trang 9 * Mô hình định vị giải tích ➢ Giới thiệu ❖ Là mô hình đơn giản nhất: “phương pháp giải tích” ! ❖ Giả định mạnh: về bản chất nhu cầu và vị trí đặt ❖ Ví dụ: Nhu cầu là đồng nhất lan trong toàn khu vực DV ❖ Tính đồng nhất có hạn chế trong thực tiễn ➢Giải pháp ❖ Mô hình định vị phân tích dễ giải ❖ Giả sử khu vực cần dịch là hình vuông diện tích a ❖ Mỗi cơ sở (cung cấp) dịch vụ: một hình thoi (vuông) cung cấp dịch vụ tại cơ sở đó ❖ Nếu có N cơ sở thì diện tích mỗi vùng là a/N và khoảng cách trung bình giữa một điểm yêu cầu tới tâm của vùng ...