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

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:31

Thêm vào BST

Báo xấu

33
lượt xem 6
download

Download Vui lòng tải xuống để xem tài liệu đầ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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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 là KHDV 2018 – Chương 6 - Trang 10
* Mô hình định vị giải tích KHDV 2018 – Chương 6 - Trang 11
Xác định số lượng cơ sở phục vụ ➢Giải pháp ❖ Giá mỗi cơ sở là f đơn vị tiền tệ ❖ Chi phí cung cấp dịch vụ đáp ứng nhu cầu mỗi dặm: c, ❖ Mật độ nhu cầu là p theo từng dặm vuông, ❖ Tổng chi phí là một hàm theo N ❖ Số lượng các cơ sở tối ưu được tính từ hàm mục tiêu (4.1) ❖ Nếu đưa đạo hàm của (4.1) tới 0 thì số lượng tối ưu các phương tiện là (4.2) ❖ Thế (4.2) vào (4.1) ta có (4.3) KHDV 2018 – Chương 6 - Trang 12
Biểu diễn đồ thị ➢ Nhận xét ❖ Phương trình (4.2): Số lượng tối ưu các phương tiện phục vụ tăng tuyến tính theo diện tích khu vực phục vụ; Số lượng tối ưu giảm theo chi phí đơn vị cơ sở ❖ Phương trình (4.3): Tổng chi phí tối ưu tăng tuyến tính theo diện tích khu vực phục vụ; Tổng chi phí tăng theo mật độ nhu cầu dịch vụ ❖ Hình 4.3 KHDV 2018 – Chương 6 - Trang 13
Mô hình định vị giải tích: Ví dụ ➢ Giới thiệu ❖ Phân bố dịch vụ cho các bang nước Mỹ: Mỗi trạm 1 triệu USD, giá nhu cẫu mỗi dặm là 0.1 USD ❖ Phương án phân bố đồng nhất nhu cầu không phù hợp ❖ Trung bình 89 người/dặm vuông: 5 người ở Wyoming, trung bình 160 người, cao 965 người ở New Jersey. ❖ Bảng dưới cho thấy tác động của giả định này KHDV 2018 – Chương 6 - Trang 14
Mô hình định vị giải tích: Ví dụ ➢ Dòng đầu ❖ Dòng đầu: Toàn nước Mỹ như một khu vực DV duy nhất ❖ 3,11 triệu dặm vuông với 280 triệu người ❖ Mô hình toàn bộ: 514 cơ sở với chi phí 1,541 tỷ USD ❖ Phân bổ trạm không phù hợp tới các khu vực do mật độ không đồng đều. Quá nhiều trạm, tổng chi phí quá dự toán ➢Các dòng khác ❖ Chia khu vực phục vụ ba vùng: thấp, trung bình, cao. Phù hợp hơn song vẫn thô. ❖ Mô hình định vị giải tích chưa chính xác song cho hiểu biết quan trọng về định vị. KHDV 2018 – Chương 6 - Trang 15
* Mô hình định vị liên tục ➢ Giới thiệu ❖ Tên “liên tục” song giả thiết nhu cầu được đặt “rời rạc”, ❖ Mô hình làm nhẹ đi giả thiết mạnh của mô hình giải tích ❖ Nhu cầu thường tập trung tại một số điểm ❖ Giả thiết phù hợp thực tiễn ➢Phân tích sơ bộ ❖ Các cơ sở đặt bất kỳ nơi nào: hạn chế khả năng ứng dụng thực tiễn ❖ Giải pháp: kỹ thuật tối ưu phi tuyến liên tục. Thủ tục số ❖ Bài toán Weber là điển hình cho mô hình định vị liên tục KHDV 2018 – Chương 6 - Trang 16
Bài toán Weber ➢Bài toán ❖ Cho ❖ Cho n điểm nhu cầu: 1, 2, …, j, …, n ❖ Điểm j định vị tại (xj, yj), Nhu cầu tại điểm j là hj; ❖ Yêu cầu ❖ Tìm vị trí (Xo, Yo) tối thiểu tổng khoảng cách với trọng số nhu cầu giữa cơ sở và các điểm nhu cầu (4.5) ➢Phân tích ❖ Trực quan: miếng gỗ dán, tại mỗi điểm nhu cầu: khoan một lỗ và đặt một ròng rọc ma sát; đưa một sợi chỉ xuyên mỗi lỗ với một trọng lượng tỷ lệ với nhu cầu ❖ Mọi sợi chỉ gắn trên ròng rọc tương ứng và gắn vào một vòng duy nhất ❖ Vị trí vòng cân bằng là định vị Weber KHDV 2018 – Chương 6 - Trang 17
Giải bài toán Weber ➢Thủ tục ❖ Giải bằng thủ tục lặp Weiszfeld ❖ Thủ tục tính toán một dãy lời giải ❖ Thủ tục lặp là giá trị (Xo, Yo) tại bước k: (4.6) (4.7) ❖ Trong đó  là số dương rất nhỏ, tham số đầu vào. ➢Phân tích ❖ Sử dụng  để tránh chia cho 0, ❖ Hội tụ nhanh với hầu hết trường hợp KHDV 2018 – Chương 6 - Trang 18
Giải bài toán Weber: ví dụ lời giải ➢Giới thiệu ❖ Yêu cầu tìm vị trí cơ sở cực tiểu hóa khoảng cách theo trọng số yêu cầu từ cơ sở tới 67 quận của bang Pennsylvania. ❖ Nhu cầu ở các điểm thoi, độ lớn nhu cầuđộ lớn thoi ❖ P/án xuất phát (80.5,42), hội tụ nhanh về (76,403, 40,355) ❖ Nhạy cảm với phương án xuất phát KHDV 2018 – Chương 6 - Trang 19
* Mô hình định vị mạng và rời rạc ➢Trả lời các câu hỏi ❖ Có bao nhiêu cơ sở cần phải đặt? ❖ Nơi nào từng cơ sở được đặt? ❖ Mỗi cơ sở nên có kích thước, quy mô ra sao? ❖ Nhu cầu dịch vụ mà mỗi cơ sở cần đáp ứng ra sao? Mark S. Daskin. Network and Discrete Location: Models, Algorithms, and Applications. John Wiley & Sons, 2013 KHDV 2018 – Chương 6 - Trang 20