Luận văn: Nghiên cứu lý thuyết hàng đợi và mô phỏng bãi gửi xe tại Siêu thị Big C Hà Nội

Nghiên cứu lý thuyết hàng đợi và mô phỏng bãi gửi xe tại siêu thị Big C Hà Nội. Phân tích hiệu quả hoạt động, đề xuất giải pháp tối ưu hóa thời gian chờ.

• Tác giả: Vũ Tuấn Doanh
• Trường học: Đại học Thái Nguyên
• Đề tài: Nghiên cứu lý thuyết hàng đợi và mô phỏng bãi gửi xe tại siêu thị Big C – Hà Nội
• Loại tài liệu: Luận văn thạc sĩ
• Năm xuất bản: 2015
• Địa điểm: Thái Nguyên

Tóm tắt

I. Tổng quan về lý thuyết hàng đợi và mô phỏng bãi xe Big C Hà Nội

Lý thuyết hàng đợi là một lĩnh vực toán học ứng dụng. Nó nghiên cứu các hệ thống phục vụ khách hàng theo nguyên tắc đến trước, phục vụ trước. Các tham số chính bao gồm tốc độ khách đến và tốc độ phục vụ. Mô phỏng sử dụng các công cụ như GPSS để mô hình hóa thực tế. Bãi xe ô tô tại siêu thị Big C Hà Nội là một ví dụ điển hình. Hệ thống này có xe ô tô liên tục ra vào. Quản lý hiệu quả bãi xe giúp giảm thời gian chờ đợi. Nghiên cứu này áp dụng lý thuyết hàng đợi để phân tích dòng xe. Mô phỏng cho phép thử nghiệm các kịch bản khác nhau. Kết quả giúp đánh giá hiệu suất và tìm giải pháp tối ưu. Công trình này đóng góp vào hiểu biết về ứng dụng lý thuyết trong đời sống.

1.1. Lý thuyết hàng đợi và các khái niệm cốt lõi

Lý thuyết hàng đợi định nghĩa một hệ thống với khách hàng đến ngẫu nhiên. Khách hàng chờ đợi trong hàng nếu tất cả các kênh phục vụ bận. Các tham số đặc trưng là phân phối thời gian giữa các lần đến và thời gian phục vụ. Mô hình Kendall được sử dụng để phân loại hệ thống, ví dụ như M/M/k. Mô hình này giả định quá trình đến Poisson và thời gian phục vụ mũ. Các khái niệm này cung cấp nền tảng để xây dựng mô hình toán học cho bãi xe.

1.2. Vai trò của mô phỏng trong quản lý bãi xe siêu thị

Mô phỏng là một công cụ mạnh để nghiên cứu các hệ thống phức tạp như bãi xe. Nó cho phép tạo ra mô hình máy tính mô phỏng hoạt động thực tế. Công cụ GPSS thường được sử dụng để mô phỏng hàng đợi. Mô phỏng giúp dự đoán thời gian chờ trung bình và số xe bị từ chối. Nó cũng hỗ trợ trong việc thiết kế quy trình phục vụ hiệu quả hơn. Áp dụng mô phỏng giúp tránh các thí nghiệm tốn kém và nguy hiểm trong thực tế.

II. Phân tích bài toán bãi xe tại siêu thị Big C Hà Nội

Bài toán bãi xe tại siêu thị Big C Hà Nội đặt ra nhiều thách thức. Xe ô tô đến theo các mô hình ngẫu nhiên, thường theo phân phối Poisson. Thời gian phục vụ bao gồm tìm chỗ đỗ và trả vé. Hệ thống có số lượng làn đỗ giới hạn, tạo ra hàng đợi vào giờ cao điểm. Nghiên cứu cần xác định mô hình hàng đợi phù hợp. Mô hình M/M/k có thể áp dụng nếu có nhiều làn đỗ. Các yếu tố như thời gian đậu xe trung bình và tỷ lệ xe đến phải được ước lượng. Phân tích giúp hiểu rõ nguyên nhân gây ùn tắc. Bài toán cũng xem xét trường hợp xe đến quá nhiều bị mất. Kết quả phân tích là cơ sở để xây dựng mô hình mô phỏng.

2.1. Các thách thức trong hoạt động của bãi xe

Hoạt động bãi xe phải đối mặt với dòng xe không đồng đều. Giờ cao điểm thường có số lượng xe đến tăng đột biến. Số lượng làn đỗ cố định dẫn đến giới hạn về dung lượng. Thời gian tìm kiếm chỗ đỗ của lái xe cũng biến đổi. Quản lý cần cân bằng giữa chi phí và chất lượng dịch vụ. Thách thức là tối ưu hóa sử dụng không gian và giảm thời gian chờ đợi.

2.2. Xác định mô hình hàng đợi phù hợp cho bãi xe

Lựa chọn mô hình hàng đợi phụ thuộc vào đặc điểm của bãi xe. Nếu có nhiều làn đỗ và xe đến ngẫu nhiên, mô hình M/M/k là phù hợp. Tham số k đại diện cho số lượng làn đỗ hoạt động. Nếu chỉ có một làn đỗ, mô hình M/M/1 được áp dụng. Cần thu thập dữ liệu thực tế để xác định tốc độ đến λ và tốc độ phục vụ μ. Mô hình phù hợp sẽ cung cấp kết quả phân tích chính xác hơn.

III. Giải pháp mô phỏng bãi xe bằng lý thuyết hàng đợi

Giải pháp đề xuất sử dụng mô phỏng GPSS để nghiên cứu bãi xe. GPSS là ngôn ngữ mô phỏng sự kiện, thích hợp cho hệ thống hàng đợi. Mô hình GPSS bao gồm các khối tạo xe ô tô và xử lý chúng. Các tham số như thời gian giữa các lần đến được thiết lập dựa trên dữ liệu. Mô phỏng cho phép chạy thử nghiệm trong thời gian dài chỉ trong vài phút. Kết quả bao gồm thống kê về thời gian chờ và số xe được phục vụ. Phương pháp này giúp đánh giá các kịch bản cải tiến. Ví dụ, tăng số làn đỗ hoặc thay đổi quy trình thanh toán. Mô phỏng là công cụ hiệu quả để ra quyết định dựa trên dữ liệu.

3.1. Phương pháp mô phỏng GPSS và nguyên lý hoạt động

GPSS hoạt động dựa trên nguyên lý mô phỏng sự kiện tiếp theo. Nó sử dụng các đối tượng như GENERATE, ADVANCE và TERMINATE. Các khối này đại diện cho quá trình tạo xe, thời gian đậu xe và rời bãi. Mô hình có thể tích hợp các hàm phân phối xác suất. GPSS tự động thu thập dữ liệu thống kê trong quá trình mô phỏng. Người dùng có thể điều chỉnh tham số để thử nghiệm các giả thuyết khác nhau.

3.2. Xây dựng mô hình mô phỏng và chạy thử nghiệm

Xây dựng mô hình GPSS bắt đầu bằng việc định nghĩa các tham số. Số lượng làn đỗ được đặt làm hằng số trong chương trình. Thời gian giữa các lần đến sử dụng phân phối mũ. Thời gian phục vụ được mô hình hóa dựa trên dữ liệu khảo sát. Mô phỏng được chạy với thời gian giả lập đủ dài để có kết quả ổn định. Kết quả đầu ra bao gồm đồ thị và bảng thống kê về hiệu suất hệ thống.

IV. Kết luận và ứng dụng của nghiên cứu hàng đợi trong bãi xe

Nghiên cứu đã áp dụng thành công lý thuyết hàng đợi để mô phỏng bãi xe. Kết quả cho thấy mô phỏng GPSS có độ chính xác cao khi so sánh với lý thuyết. Sai lệch giữa mô phỏng và lý thuyết ở mức chấp nhận được. Công trình xác định các yếu tố then chốt ảnh hưởng đến hiệu suất bãi xe. Ứng dụng thực tiễn bao gồm thiết kế bãi xe mới hoặc cải tiến quy trình. Quản lý có thể sử dụng mô hình để dự báo nhu cầu và tối ưu hóa tài nguyên. Nghiên cứu cũng mở ra hướng phát triển cho các siêu thị khác. Công cụ mô phỏng giúp giảm chi phí thử nghiệm và nâng cao chất lượng dịch vụ.

4.1. Đánh giá kết quả mô phỏng và so sánh với lý thuyết

Kết quả mô phỏng được so sánh với các công thức lý thuyết của hàng đợi M/M/k. Đại lượng đánh giá là số xe ô tô được phục vụ và thời gian chờ trung bình. Độ sai lệch tính toán giữa mô phỏng và lý thuyết dao động nhỏ theo thời gian. Điều này chứng minh tính tin cậy của mô hình GPSS. Biểu đồ phụ thuộc độ sai lệch giúp trực quan hóa sự phù hợp. Đánh giá này cung cấp cơ sở để áp dụng mô hình trong thực tế.

4.2. Hướng ứng dụng thực tế và đề xuất cải tiến

Kết quả nghiên cứu có thể ứng dụng trực tiếp vào quản lý bãi xe Big C Hà Nội. Đề xuất cải tiến bao gồm tăng số làn đỗ vào giờ cao điểm. Điều chỉnh thời gian phục vụ tại quầy vé cũng giúp giảm ùn tắc. Mô hình mô phỏng có thể tái sử dụng để thử nghiệm các kịch bản khác nhau. Ứng dụng rộng rãi hơn là áp dụng cho các bãi xe công cộng tương tự. Nghiên cứu nhấn mạnh tầm quan trọng của dữ liệu thực tế trong mô phỏng.

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

LỜI MỞ ĐẦU Những năm gần đây, việc ứng dụng công nghệ thông tin vào các hoạt động trong đời sống, xã hội là rất cần thiết. Trong thực tế, chúng ta bắt gặp rất nhiều các hệ thống đƣợc thiết lập bởi các yêu cầu (của khách hàng), trong đó các thời điểm xuất hiện đƣợc xem nhƣ một đại lƣợng ngẫu nhiên, còn nhu cầu đƣợc đặc trƣng bằng khối lƣợng các công việc phải làm để phục vụ, thứ tự ƣu tiên trƣớc sau, thời gian hoàn thành công việc và toàn bộ công việc. Đó là những hệ thống nhƣ: Mạng điện thoại, mạng máy tính, hệ thống phục vụ sử dụng phòng máy thực hành, hệ thống các quầy thu ngân trong siêu thị, hệ thống bán vé tự động, sân bay… Những hệ thống này đƣợc biết đến với tên gọi hệ thống phục vụ đám đông (hay hệ thống hàng đợi). Nhìn chung các hệ thống phục vụ đám đông là hệ thống phức tạp, việc vận hành và tính toán các đặc trƣng của hệ thống để tƣ vấn cho nhà quản lý là một vấn đề hết sức cần thiết.

Trong quá khứ, có rất nhiều dự án xây dựng hệ thống phục vụ phức tạp dựa trên hàng chờ (Queue) không thành công vì đã không đặc tả đƣợc chính xác bài toán thực tiễn. Việc xây dựng mô hình toán học cho mỗi hệ thống là rất cần thiết để giảm chi phí tối đa cho các hoạt động đặc tả nó. Khi đó tính chất đầy đủ của các mô hình mô phỏng cần đạt đƣợc việc mô phỏng quá trình làm việc của mỗi phần tử trong hệ thống với việc đảm bảo logic, quy tắc của sự tƣơng tác và phát triển của chúng, cả trong không gian và trong thời gian. Các câu hỏi đƣợc đặt ra là: Làm thế nào để mô phỏng một hệ thống phức tạp dƣới dạng đơn giản nhƣng chính xác? Phƣơng pháp nào là khả thi nhất, tối ƣu nhất?.

Có rất nhiều phƣơng pháp đã đƣợc đƣa ra để giải quyết bài toán trên nhƣ: Tính toán bằng các công thức toán học, xây dựng hệ thống phục vụ bằng các ngôn ngữ lập trình (Pascal, C++…), mô phỏng bằng các công cụ mô phỏng (Matlab, Petri Network…)… Để xây dựng mô hình mô phỏng bằng cách sử dụng các ngôn ngữ lập trình truyền thống là Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.vn 2 khá phức tạp, khó khăn do khi lập trình chúng ta phải quản lý các sự kiện theo một mô hình nhiều sự kiện xảy ra đồng thời (song song) với việc xây dựng hàm tạo ngẫu nhiên các sự kiện (random) cũng không hề đơn giản , chính vì vậy đã xuất hiện nhƣ̃ng ngôn ngữ mô phỏng chuyên dụng. Một trong những ngôn ngữ chuyên dụng mô phỏng hệ thống phức tạp, rời rạc có hiệu quả và phổ biến nhất hiện nay là General Purpose Simulation System (GPSS), ngôn ngữ này thuộc về lớp ngôn ngữ hƣớng vấn đề. Lĩnh vực áp dụng chính của GPSS là hệ thống phục vụ đám đông. Đối tƣợng của ngôn ngữ này đƣợc sử dụng tƣơng tự nhƣ: Thành phần chuẩn của một hệ thống phục vụ đám đông ; các yêu cầu , thiết bị phục vụ , hàng đợi… Tập hợp đầy đủ nhƣ̃ng thành phần nhƣ vậy cho phép xây dựng các mô phỏng phức tạp trong khi đảm bảo những thuật ngữ thông thƣờng của hệ thống phục vụ đám đông.

Trên thế giới nói chung và ở Liên bang Nga nói riêng, việc nghiên cứu và ứng dụng của GPSS rất phổ biến và phát triển. Tuy nhiên việc triển khai và ứng dụng công cụ mô phỏng GPSS trong giải quyết các bài toán hệ thống phục vụ đám đông vẫn là mới ở Việt Nam. Chính vì vậy, yêu cầu lựa chọn, so sánh, đánh giá các công cụ dựa trên định hƣớng xây dựng mô phỏng hệ thống phục vụ đám đông là một đề tài mang ý nghĩa khoa học và thực tiễn cao. Với lý do đó, tôi lựa chọn đề tài “Nghiên cứu lý thuyết hàng đợi và mô phỏng bãi gửi xe tại siêu thị Big C – Hà Nội” cho luận văn tốt nghiệp Thạc sĩ của mình.

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.vn 3 Chƣơng 1 CƠ SỞ LÝ THUYẾT VỀ HÀNG ĐỢI 1. Các khái niệm cơ bản 1. Định nghĩa hàng đợi Hàng đợi là hệ thống bao gồm các thành phần : khách hàng vào/ ra hệ thống (input/output), hệ thống phục vụ (server), hàng đợi(queue). Hàng đợi Sự kiện đến Server Sự kiện đi Hình 1.1: Mô hình chung của hệ thống hàng đợi Khách hàng vào hệ thống đƣợc đƣa vào hàng đợi, đến lƣợt thì đƣợc phục vụ ở server, sau khi đƣợc phục vụ xong thì ra khỏi hệ thống.

Khi dùng hàng đợi ta hiểu là toàn bộ hệ thống xếp hàng bao gồm các yêu cầu đợi phục vụ và các yêu cầu đang đợi phục vụ và các yêu cầu đang đƣợc phục vụ [2]. Hệ thống đƣợc mô hình hoá dƣới dạng hàng đợi nhƣ sau:  Mỗi loại tài nguyên của hệ thống tƣơng ứng với một trung tâm dịch vụ (server center).  Mỗi giao dịch yêu cầu tài nguyên thứ i sẽ là một khách hàng trong hàng đợi Qi tƣơng ứng với loại tài nguyên đó. Các tham số đặc trƣng của một hàng đợi - Tính chất của dòng khách hàng đến hàng đợi hay phân bố xác suất khoảng thời gian giữa các yêu cầu hàng đợi.

- Phân bố xác suất khoảng thời gian dịch vụ cho mỗi yêu cầu trong hàng đợi. - Số các server tại hàng đợi. - Dung lƣợng bộ đệm hay dung lƣợng lƣu trữ tại hàng đợi. Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.vn 4 - Tổng số các yêu cầu hiện đang có mặt tại hàng đợi.

- Các kiểu dịch vụ. Theo kí pháp của Kendall một hệ thống xếp hàng đƣợc phân loại qua các kí hiệu của bộ mô tả kendall tổng quát có dạng //m//N/Q. : phân bố xác suất của khoảng thời gian yêu cầu để phục vụ các khách hàng trong hệ thống xếp hàng. : phân phối xác suất trong khoảng thời gian yêu cầu để phục vụ các khách hàng trong hệ thống xếp hàng : kích thƣớc bộ đệm hoặc dung lƣợng lƣu trữ tại hệ thống xếp hàng.

N : số lƣợng khách hàng đƣợc phép chuyển qua hệ thống. Q: phƣơng thức phục vụ. Một số các phân bố xác suất đƣợc sử dụng để biểu diễn các đại lƣợng đặc trƣng của hệ thống xếp hàng nhƣ sau:  Phân bố xác định (D-Deterministic): Khoảng thời gian giữa hai khách hàng đến hay rời hệ thống liên tiếp là bằng nhau: 1 p ( n)  0 ( x  ).   Phân bố mũ(M-exponential): Khoảng thời gian giữa hai lần khách hàng đến hệ thống liên tiếp là hoàn toàn độc lập với khoảng thời gian đến trƣớc đó.

Biến ngẫu nhiên mô tả quá trình có phân phối mũ: p(n)  .  Phân phối erlang-r ( E r ): Trung tâm dịch vụ đƣợc biểu diễn bằng một dãy các giai đoạn trễ mỗi giai đoạn có cùng thời gian dịch vụ trung bình và có phân phối mũ. Không có các hàng đợi tại bất kì giai đoạn phục vụ nào vì yêu cầu tiếp theo sẽ không đƣợc đáp ƣng nều yêu cầu trƣớc đó chƣa đƣợc hoàn thành: Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.vn 5 r  (r  x)  e r  x p ( x)  (r  1)!  Phân phối Hypexponential ( H r ): Mỗi giai đoạn trễ trong mô hình E r có các thời gian dịch vụ khác nhau với các giai đoạn đƣợc phục vụ song song R R p(n)   i i e  x ( i ) i i i 1 i 1  Phân phối tổng quát(G-General): p( x) là một hàm bất kỳ. Các phương thức phục vụ khách hàng bao gồm :  LIFO(Last In First Out): các khách hàng tới gần đây nhất sẽ đƣợc phục vụ hoặc phải đợi.

 LIFO PR (LIFO with PRe-emptive): khi khách hàng tới gần đây nhất ngay lập tức đƣợc thế chỗ cho khách hàng đƣợc phục vụcho đến khi nó đƣợc phục vụ xong thì dịch vụ có thể tiếp tục đối với một khách hàng bị thế chỗ ngay nơi mà nó bị ngắt trƣớc đó.  RR(Round Robin): Thời gian tại một tài nguyên (đĩa , CPU… )đƣợc phân chia thành một số các thông số trong khoảng nhỏ có độ dài cố định đƣợc gọi là các lƣợng tử. Một khách hàng tới tham gia vào hàng đợi và chờ để đƣợc lên đầu hàng theo nguyên tắc FCFS và cuối cùng khách hàng nhận đƣợc một lƣợng tử cho quá trình phục vụ khi lƣợng tử này hết mà khách hàng vẫn chƣa đƣợc phục vụ thì khách hàng đó phải quay lại hàng đợi cho đến khi khách hàng đó đƣợc phục vụ xong.  PS(Processor Shariny) : Trong hệ thống này các bộ vi xử lý đóng vai trò nhƣ server có tốc độ phục vụ cố định.

Nó có thể phân phối khả năng phục vụ bằng nhau cho các khách hàng trong hệ thống có nghĩa là không có hàng đợi nào trong hệ thống cả. Mỗi khách hàng đến lập tức đƣợc phục vụ. Một số khách hàng đƣợc quyền ƣu tiên hơn những ngƣời khác và đƣợc phục vụ trƣớc. Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.

Các thông số hiệu năng thƣờng dùng khi phân tích hệ thống sử dụng mô hình mạng xếp hàng A - Tốc độ đến của các khách hàng () [3]:  = T Trong đó A - số các khách hàng đến hệ thống. T-Thời gian quan sát (hay thời gian đó). Trong khi A đếm số các yêu cầu đến hàng đợi thì  biểu diễn tốc độ mà các yêu cầu đó đến. Đơn vị đo của tốc độ là : khách hàng đơn vị thời gian.

Ví dụ, nếu một hệ điều hành đƣợc cung cấp các công cụ để mà đếm số yêu cầu về phục vụ một số tài nguyên (CPU, đĩa.) thì tổng số lần đếm trong một đơn vị thời gian chính là tốc độ đến. - Thông lƣợng (throughput) của hệ thống xếp hàng hay là tốc độ trung C bình các khách hàng chuyển qua hệ thống : X = T Trong đó C là số các khách hàng hoàn thành dịch vụ. Đại lƣợng này cũng biểu thị tốc độ. Do nó là một đại lƣợng có thể đo tốc độ hoàn thành dịch vụ một cách trực tiếp, giống nhƣ tốc độ đến.

Trong một số trƣờng hợp ta sẽ thấy tốc độ đến hệ thống của các khách hàng  sẽ bằng với thông lƣợng X.  Dạng biểu diễn khác: Throughput  Y    (n) Pn , (khách hàng /giây), n 1 trong đó Pn là xác suất trạng thái cân bằng khi hệ thống có n khách hàng trong hệ thống. Thông lƣợng trung bình là trung bình trọng số của các tốc độ dịch vụ (n) còn các xác suất trạng thái cân bằng Pn đƣợc dùng nhƣ các trọng số.