Bài giảng Khoa học dịch vụ: Chương 6

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 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.

❖ 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 :

❖ 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

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

❖ 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

cầu FEMA

❖ Quận được chia thành 6600 lô với 3900 lô đáp ứng yêu

❖ 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

readers: AMR)

❖ Bài toán cốt lõi: Định vị bộ thu công tơ (automated meter

➢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

(4.2)

phương tiện là

❖ 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.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ụ

❖ 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ở

❖ 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

USD, giá nhu cẫu mỗi dặm là 0.1 USD

❖ Phân bố dịch vụ cho các bang nước Mỹ: Mỗi trạm 1 triệu

❖ 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

đều. Quá nhiều trạm, tổng chi phí quá dự toán

❖ 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

➢Các dòng khác

❖ Chia khu vực phục vụ ba vùng: thấp, trung bình, cao. Phù

❖ Mô hình định vị giải tích chưa chính xác song cho hiểu biết

hợp hơn song vẫn thô.

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ộ

dụng thực tiễn

❖ Các cơ sở đặt bất kỳ nơi nào: hạn chế khả năng ứng

❖ 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)

❖ Trong đó  là số dương rất nhỏ, tham số đầu vào.

(4.7)

➢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

* Mô hình định vị mạng ➢ Giới thiệu

❖ Giả thiết: Tồn tại mạng nền cho bài toán ❖ Ví dụ: đường cao tốc, đường trục, đường cục bộ trong thành phố;

Mạng hệ thống quốc lộ; Mạng cung cấp nước

❖ Định vị mạng thường yêu cầu tìm lời giải đa thức theo kích thước bài

toán

❖ Phổ biến định vị mạng theo cấu trúc đặc biệt: Cây ❖ Sơ đồ 10 t/phố lớn nhất Mỹ: nhu cầu/dân số nút (mầu xanh) và

khoảng cách.

732

103

278

340

96

159

101

111

94

163 KHDV 2018 – Chương 6 - Trang 21

Mô hình định vị mạng

➢ Trọng số nhu cầu

❖ Tổng nhu cầu = 2188. Ma trận đường đi ngắn nhất

732 159

103

278

101

163

94

98

349

111

❖ Bài toán: Tìm một thành phố trên cây để tổng khoảng cách với trọng số nhu cầu nhỏ nhất → tích vô hướng vector trên bảng với vector trọng số.

❖ NY: 159*1373+103*468+278*706+101*1505+163*1729+94*1757+

982604+3492970+111*2901. Tổng 2.675.502

KHDV 2018 – Chương 6 - Trang 22

Mô hình định vị mạng

❖ Thuật toán Goldman (1971): 1. X nút lá bất kỳ trên cây 2. Nếu nhu cầu (X)  nửa tổng nhu cầu thì X là nút cần

chọn,

(Y)+ nhu cầu (X). Loại bỏ X và cung (X,Y) Tính ví dụ: Chọn Chicago. Tính đúng đắn ?

3. ngược lại, gọi Y là nút kết nối X: nhu cầu (Y) nhu cầu

KHDV 2018 – Chương 6 - Trang 23

Mô hình định vị mạng

KHDV 2018 – Chương 6 - Trang 24

* Mô hình định vị rời rạc

➢ Giới thiệu

❖ Nhu cầu rời rạc, định vị rời rạc → vùng dịch vụ được chia thành các tiểu vùng. Ví dụ, xe cứu thương: 358 tiểu vùng ❖ Tiểu vùng → điểm, có “lỗi” nhỏ, các cư dân ở tiểu vùng có

khác biệt khoảng cách

thương: Số cuộc gọi quá khứ, số người già v.v.

❖ Nhu cầu tiểu vùng gắn với tiểu vùng. Ví dụ xe cứu

❖ Phục vụ có thể tọa lạc tại các tiểu vùng. ❖ Khoảng cách (tiểu vùng, tọa lạc) do người dùng chọn. ❖ Tồn tại nhiều độ đo khoảng cách trong nhiều bài toán ❖ Trong định vị địa lý: khoảng cách chu trình lớn, khoảng

cách cao tốc, thời gian di chuyển, giá thành v.v.

KHDV 2018 – Chương 6 - Trang 25

Định vị rời rạc: Phân loại

➢ Các loại định vị rời rạc

❖ Phụ thuộc dạng hàm mục tiêu

KHDV 2018 – Chương 6 - Trang 26

Định vị rời rạc: khoảng cách

➢ Cuốn sách The Numerati của StephenBaker:

2008

❖ Stephen Baker. The Numerati. Houghton Mifflin Harcourt,

❖ Ứng dụng toán học nhằm xác định đặc điểm người lao

động, người tiêu dùng, cử tri

❖ Cá nhân  gắn các đặc trưng: tuổi, giới tính, vị trí nhà, đi làm hay không, thu nhập, sở hữu/thuê nhà, số lượng xe ô-tô, khi đi du lịch nước ngoài.

❖ “Khoảng cách”: độ khác biệt các đặc trưng nói trên. ❖ Tìm 10 cá nhân “đại diện” cho toàn tiểu vùng. ❖ Bài toán định vị

KHDV 2018 – Chương 6 - Trang 27

4. Mô hình phủ tập

➢ Giới thiệu

❖ Mô hình phủ: Covering model (CM) ❖ Mô hình phủ tập (Set CM): dạng cơ bản của mô hình phủ ❖ Phát biểu đơn giản song rất khó giải ❖ Yêu cầu mọi nút yêu cầu cần được đáp ứng ❖ Hai mô hình đơn giản cố định số lượng nhà cung cấp p là

một giá trị đầu vào người dùng

số yêu cầu được phủ.

❖ Mô hình phủ cực đại (maximal covering model): cực đại

❖ Mô hình trung tâm p (p-center model): cực tiểu khoảng

cách phủ/thời gian yêu cầu phủ mọi yêu cầu

thời gian, giá thành, v.v.

❖ Ngầm định: Phủ theo khoảng cách. Chuyển dạng sang