Thứ Hai, 4 tháng 8, 2014

Khoa học: Xếp hàng như thế nào là tối ưu nhất?

Thử tưởng tượng bạn đang mua hàng trong một siêu thị, sau khi chọn được món hàng mong muốn, bạn vội ra quầy thanh toán. Liếc một lượt tất cả các quầy tính tiền với hàng dài người chờ phía sau, bạn chọn cho mình một hàng có vẻ như là nhanh nhất? Nhưng, bạn nhanh chóng nhận ra mình đã sai! Hàng bên cạnh có những người dù xếp hàng sau bạn nhưng lại được thanh toán và ra về trước bạn. Tại sao sự bất công đó lại xảy ra với bạn? Đúng vậy, đó là một sự không công bằng và chính toán học đã chống lại bạn.

Khi bạn phải lựa chọn 1 trong số vài hàng chờ tính tiền trong siêu thị, chi phí cơ hội trở nên bất lợi đối với bạn. Rất có khả năng là hàng khác thực sự nhanh hơn hàng bạn đã chọn. Dưới góc độ khoa học, các nhà toán học đã thực hiện nhiều nghiên cứu về hành vi xếp hàng và hình thành nên một lý thuyết: Lý thuyết xếp hàng. Cụ thể, các nhà nghiên cứu đã dùng những dãy số để biểu thị và chứng minh cho hiện tượng thú vị này. Trên thực tế, hiện tượng trên đã xuất hiện từ những năm 1900 của thế kỷ trước...

Từ vấn đề viễn thông đến Lý thuyết xếp hàng

nhan_vien_tong_dai.
Một nhân viên tổng đài điện thoại tại Mỹ vào những năm 1900​

Sự việc đã diễn ra tại tổng đài điện thoại thành phố Copenhagen, Đan Mạch. Vào đầu những năm 1900, một kỹ sư trẻ có tên Agner Krarup Erlang đã tìm cách tính toán số đường dây điện thoại tối ưu cho tổng đài điện thoại tại thành phố Copenhagen. Vào thời điểm bấy giờ, khi muốn thực hiện cuộc gọi, người ta phải cắm jack cắm vào một mạch điện dẫn tới tổng đài và chờ đợi. Việc kết nối 2 đầu dây lại với nhau để thực hiện cuộc gọi sẽ được thực hiện thủ công bởi nhân viên trực tại tổng đài.

Nhằm tiết kiệm lao động và cơ sở hạ tầng, Erlang muốn biết chính xác số đường dây tối thiểu cần thiết để tất cả tất cả các cuộc gọi đều được kết nối nhanh nhất. Nếu đối với các tổng đài nhỏ và cần chi phí thấp nhất, người ta chỉ trang bị 1 đường dây duy nhất và người ta phải xếp hàng rất lâu mới tới lượt cuộc gọi của họ được kết nối. Do đó, cần phải tính số đường dây ít nhất để tiết kiệm nhưng vẫn đảm bảo hàng nghìn người trong thành phố không phải chờ đợi quá lâu.

erlang_1.
Agner Krarup Erlang (1878-1929), người đã đề xuất phương trình tính toán số lượng kết nối tối ưu và khai sinh ra Lý thuyết xếp hàng​

Một thí dụ đơn giản. Nếu tổng đài Copenhagen phải xử lý trung bình 2 cuộc gọi mỗi giờ thì rõ ràng chỉ cần 2 đường dây là đủ. Nhưng điều này hoàn toàn khác với thực tế do sẽ có những giờ cao điểm với hàng loạt người muốn gọi điện cùng một lúc. Giả sử vào giờ cao điểm, tổng đài phải tiếp nhận cùng lúc 5 yêu cầu kết nối tại cùng một thời điểm.

Nếu chỉ có 2 đường dây thì chỉ cung cấp được 2 cuộc gọi đáp ứng 2 khách hàng và những người còn lại phải chờ. Chưa hết, nếu những người chờ đợi xui xẻo sẽ gặp phải những khách hàng thích tám chuyện khiến họ đợi chờ hàng giờ đồng hồ. Khi đó, số lượng người chờ vẫn tiếp tục tăng lên và nếu bạn đến sau thì việc thực hiện cuộc gọi dường như là không thể.

Để khắc phục điều đó, Erlang nghĩ ra một phương trình (còn được gọi là phương trình Erlang) nhằm tính ra được số cuộc gọi trung bình trong các giờ định trước và khoảng thời gian trung bình của mỗi cuộc gọi. Áp dụng phương trình của mình vào thí dụ đơn giản trên, tổng đài điện thoại Copenhagen đã tìm ra được rằng, nếu họ trang bị 7 đường dây thì 99% cuộc gọi sẽ được kết nối ngay lập tức tại bất cứ lúc nào. Vào năm 1909, Erlang đã công bố phát hiện của ông và khai sinh ra một nhánh mới của toán học mang tên "Lý thuyết xếp hàng".

Khoa học của việc xếp hàng

sieu_thi.

Trở lại tình huống chọn hàng tính tiền trong siêu thị, chắc có lẽ các bạn cũng thấy được điểm tương đồng của việc này với vấn đề cuộc gọi mà Erlang từng giải quyết. Lý thuyết xếp hàng đã giải thích tại sao bạn (có vẻ) không thể nào chọn được hàng nhanh nhất? Nói cách khác là tại sao hàng của bạn chọn dường như luôn chậm hơn những hàng khác. Dĩ nhiên là mỗi siêu thị đều cố gắng trang bị đủ nhân viên tính tiền để phục vụ khách hàng trong thời gian nhanh nhất. Nhưng đôi khi, trong những ngày cuối tuần, toàn bộ các quầy thanh toán đều trong tình trạng quá tải.

Rõ ràng, việc thuê thêm nhân viên tính tiền hay xây dựng thêm các quầy thu ngân là một lựa chọn khá lãng phí thậm chí là bất khả thi. Đồng thời, việc chậm trễ còn bị gây ra bởi một số khách hàng đặc biệt hay các món hàng xảy ra vấn đề... Tất cả đều gây ra sự chờ đợi cho những người đang xếp hàng phía sau.

Nếu một siêu thị có 3 quầy thanh toán, việc chậm trễ có thể xảy ra ngẫu nhiên tại mỗi quầy khác nhau. Giờ hãy cùng suy nghĩ xác suất xảy ra chậm trễ tại mỗi quầy. Xác suất để hàng mà bạn chọn tính tiền trở thành hàng nhanh nhất là 1/3. Điều này có nghĩa là bạn có 2/3 cơ hội không xếp vào hàng nhanh nhất. Do đó, khả năng bạn chọn nhầm hàng chậm hơn có thể xảy ra cao hơn. Nói cách khác, không phải chỉ trong cảm giác của bạn mà thật sự, bạn khó có thể chọn được hàng nhanh nhất.

Xếp hàng thế nào là tối ưu và công bằng?

full-serpentine-lines.

Và bây giờ, lý thuyết xếp hàng sẽ cung cấp một giải pháp tối ưu cho vấn đề này: Chỉ cần tất cả các khách hàng đều đứng vào cùng 1 đường gấp khúc (serpentine line) và mỗi người đầu tiên trong hàng sẽ được phục vụ bởi 1 người thu ngân. Vậy nếu chúng ta có 3 người thu ngân tại điểm cuối, phương pháp này sẽ nhanh hơn gấp 3 lần so với phương pháp xếp 3 hàng độc lập như truyền thống. Nếu chú ý, bạn sẽ thấy phương pháp này thường được sử dụng tại một số bệnh viên, các trung tâm vui chơi lớn,...

Với dạng xếp 1 hàng gấp khúc, việc chậm trễ gây ra bởi 1 người thu ngân sẽ không bị ảnh hưởng tới những người khác đang đợi trong hàng do nếu có 3 người thu ngân, 1 người chậm lại thì 2 người khác vẫn có thể phục vụ người tiếp theo. Đồng thời, kỹ thuật trên giúp cho mỗi người xếp trong hàng đều có được cơ hội như nhau và hoàn toàn công bằng. Vấn đề đã được tiết giảm tới mức chờ đợi cuối cùng là đến sớm hay trễ và dĩ nhiên, mỗi người sẽ chậm hơn một chút nhưng đảm bảo được sự công bằng. Sự chậm trễ tại mỗi quầy không còn ảnh hưởng đến cả một hàng dài nữa.

Có thể áp dụng phương pháp trên ở tất cả mọi nơi?

xep_hang_mua_sam.

Vậy tại sao tất cả mọi nơi đều áp dụng phương pháp xếp 1 hàng gấp khúc nói trên? Đó là tính toán toán học, vấn đề còn phụ thuộc vào yếu tố tâm lý khách hàng. Tâm lý con người thường nghĩ rằng mỗi người phải được làm chủ cuộc sống của chính họ và nếu có cơ hội, con người luôn muốn tự lựa chọn cách mà họ cho là nhanh nhất. Do đó, vấn đề ở đây là không phải khách hàng nào cũng thoải mái tuân theo nguyên tắc nói trên. Bên cạnh đó, các nhà nghiên cứu đã chỉ ra rằng sẽ xuất hiện trường hợp những người trong hàng cũng có khả năng gây cản trở khiến thời gian xếp hàng lâu hơn so với truyền thống.

Không chỉ áp dụng cho việc xếp hàng mà lý thuyết trên còn được áp dụng rộng rãi cho các vấn đề trong thế giới hiện đại như thiết kế giao thông, thiết kế nhà máy hoặc cơ sở hạ tầng internet,... Ngày nay, lý thuyết xếp hàng đã phát triển vượt ra khỏi một mô hình toán học và kết hợp thêm với các khía cạnh tâm lý học để làm dịu sự chờ đợi khi xếp hàng.

Đây cũng là nguyên nhân vì sao ở bên ngoài một số thang máy thường có lắp những tấm gương kéo dài từ sàn lên trần nhằm giảm bớt sự nhàm chán khi chờ đợi lượt tiếp theo. Hiện nay, vấn đề đợi chờ cũng được phần nào giải quyết bởi các thiết bị di động. Người ta có hể giết thời gian chờ đợi bằng cách đọc tin tức, chơi game, check facebook,... trong quá trình chờ đợi.

Kết

xep_hang.
Nếu các bạn có dịp đi du lịch vào mùa hè này, các bạn sẽ thấy tại một số khu du lịch cũng được áp dụng kỹ thuật nói trên! Cách đây không lâu, mình cũng có dịp bắt gặp được kỹ thuật xếp 1 hàng theo đường gấp khúc khi chờ cáp treo tại Đà Lạt và cũng có thắc mắc rằng cách xếp hàng như vậy có tác dụng chính là gì? Thì ra đó chính là bắt nguồn từ lý thuyết xếp hàng, một vấn đề thực tế thực tế được giải quyết dưới góc nhìn toán học.

Hy vọng rằng bài viết có thể cung cấp một số thông tin nhỏ nhưng khá thú vị xoay quanh vấn đề xếp hàng. Do đó, nếu trong tương lai các bạn có cảm thấy hàng mình chọn chậm hơn so với các hàng khác cũng đừng quá băn khoăn bởi lẽ, đó là điều hiển nhiên có thể lý giải bằng toán học và cũng có rất nhiều người khác trên khắp thế giới cũng có cảm giác như các bạn. Cám ơn các bạn đã theo dõi bài viết. Chúc vui.