Bài giảng Khoa học dịch vụ - Chương 6: Bài toán định vị và phân bố trong dịch vụ

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 (x_j, y_j), Nhu cầu tại điểm j là h_j;

❖ Yêu cầu

❖ Tì m vị trí (X_o, Y_o) 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ị (X_o, Y_o) 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

Bài giảng Khoa học dịch vụ - Chương 6: Bài toán định vị và phân bố trong dịch vụ - Hà Quang Thụy