Bài toán điều phối giao vận trong thời gian thực

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

Thêm vào BST

Báo xấu

1
lượt xem 0
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài viết này chỉ giới thiệu một kết quả nhỏ trong việc ứng dụng CNTT vào việc ra quyết định điều phối giao hàng của hệ thống cửa hàng Jolibee tại Việt Nam nhằm tăng cường chất lượng dịch vụ của công ty.

Chủ đề:

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

Lưu

Nội dung Text: Bài toán điều phối giao vận trong thời gian thực

Tuyển tập Hội nghị Khoa học thường niên năm 2015. ISBN : 978-604-82-1710-5 BÀI TOÁN ĐIỀU PHỐI GIAO VẬN TRONG THỜI GIAN THỰC Trương Xuân Nam Đại học Thủy lợi, email: truongxuannam@gmail.com 1. GIỚI THIỆU CHUNG (chẳng hạn: quận, huyện,…) phụ trách, khách hàng thuộc khu vực phụ trách của Bài toán điều phối vận chuyển hàng là bài cửa hàng nào sẽ được cửa hàng đó (tạm gọi toán trung tâm của lĩnh vực hậu cần là cửa hàng phụ trách) giao hàng mà không (logistics), một thuật ngữ chung để chỉ việc quan tâm tới các dữ liệu thực tế khác hoạch định, thực hiện và kiểm soát sự lưu (chẳng hạn như có cửa hàng khác gần khách thông và tích trữ một cách hiệu quả các loại hơn, cửa hàng hiện tại đang quá tải vì nhiều hàng hóa, nguyên nhiên vật liệu. Việc quản khách trực tiếp,…). lý vận chuyển hàng hóa (transportation management logistics) áp dụng trong rất nhiều lĩnh vực của cuộc sống, từ quân sự, Khách Đặt hàng Website vận tải đường biển, đường không,… và phát hàng đặt hàng triển bùng nổ cùng với việc bán hàng trực tuyến. Xác nhận Bài báo này chỉ giới thiệu một kết quả nhỏ xác Chuyển trong việc ứng dụng CNTT vào việc ra quyết Đặt hàng định điều phối giao hàng của hệ thống cửa Giao hàng Tổng đài hàng Jolibee tại Việt Nam nhằm tăng cường chất lượng dịch vụ của công ty. 2. PHƯƠNG PHÁP NGHIÊN CỨU Chuyển 2.1. Vấn đề Cửa hàng đơn địa phương hàng Jolibee là một doanh nghiệp thức ăn nhanh của Phillipines ra đời năm 1978, hiện nay có khoảng trên 2000 cửa hàng khắp thế giới và Hình 1: Sơ đồ hoạt động đặt hàng trực tuyến trên 60 cửa hàng tại Việt Nam. và qua điện thoại Jolibee bắt đầu triển khai việc đặt hàng trực tuyến và đặt hàng qua điện thoại từ năm Ưu điểm của hệ thống hiện tại: hệ thống 1999. Khách hàng có thể tra cứu danh mục đơn giản, không phụ thuộc nhiều vào hệ đồ ăn và đặt hàng với điện thoại viên hoặc thống thông tin, có khả năng thích ứng cao đặt hàng qua trang web (sau đó điện thoại với những diễn biến bất ngờ (hỏng hóc hệ viên sẽ liên hệ lại với khách để xác nhận thống, sự thay đổi nhân lực,…). đơn hàng). Các vấn đề của hệ thống hiện tại: Việc quyết định đơn hàng được xử lý bởi a. Không tận dụng tốt thông tin địa lý cửa hàng nào dựa trên phân cấp hành chính của khách hàng: do đặc điểm điều phối của hệ thống cửa hàng Jolibee; tức là mỗi theo vị trí hành chính, sẽ có những đơn cửa hàng sẽ được phân định trước khu vực hàng được giao bởi cửa hàng ở xa hơn. 118
Tuyển tập Hội nghị Khoa học thường niên năm 2015. ISBN : 978-604-82-1710-5 b. Không tận dụng tốt nguồn lực của các g. Thời điểm hoàn thành đơn hàng (giao cửa hàng: nếu một cửa hàng bị quá tải hàng và nhận tiền). thì các khách hàng đặt trực tuyến phải h. Thời điểm nhân viên giao hàng về báo chờ lâu hơn trong khi có thể có nhiều danh. cửa hàng xung quanh có thể phục vụ Ngoài ra, còn có một số dữ liệu về các ngay thì lại không được giao khách để cửa hàng địa phương như địa điểm của các phục vụ. cửa hàng, số quầy, số nhân viên phục vụ, số nhận viên giao hàng… 2.2. Bài toán cụ thể 2.4. Xử lý dữ liệu thô Jolibee muốn xây dựng hệ thống điều phối giao vận tự động với mục tiêu chính là giảm Một số thông tin không có nghĩa trong tối đa số lần vi phạm cam kết với khách việc ra quyết định hoặc khó sử dụng sẽ bị hàng (đơn hàng được cam kết sẽ giao trong loại bỏ. Chẳng hạn như thông tin về món vòng 30 phút). hoặc giá tiền. Ngoải ra, các mục tiêu khác liên quan tới Các thông tin về đơn hàng trực tuyến và tối ưu hóa hoạt động của hệ thống cũng được trực tiếp được tách thành hai khối. Thông tin đặt ra: đặt hàng trực tiếp cho phép ước lượng trạng a. Ước lượng thời gian chờ đợi của thái quá tải phục vụ của cửa hàng nếu có. khách trong tình huống quá tải. Thông tin đặt hàng trực tuyến là đầu vào cho b. Giảm thời gian chờ đợi tối đa của hệ thống ra quyết định điều phối giao vận. khách. c. Giảm thời gian đi lại trung bình của bộ phận giao hàng (tăng năng suất giao hàng). d. Dự đoán số nhân viên phải thuê thêm theo giờ trong mỗi cửa hàng để xử lý vấn đề quá tải phục vụ. e. Gom nhiều chuyến giao hàng làm một trong tình huống đi chung tuyến đường hoặc ở các khu cư dân gần nhau. 2.3. Dữ liệu thử nghiệm Hình 2: Số khách đến theo giờ cho phép ước lượng trạng thái phục vụ hiện tại Dữ liệu thử nghiệm bao gồm toàn bộ đơn Quyết định điều phối tối ưu? hàng (cả trực tuyến và trực tiếp) của tất cả các cửa hàng ở Hà Nội và Thành phố Hồ Chí Minh Bài toán điều phối tối ưu có yếu tố thời trong vòng 1 tháng (hơn 820000 đơn hàng). gian là bài toán NP-khó [1]. Nếu loại bỏ yếu Thông tin chi tiết của mỗi đơn hàng gồm: tố thời gian, tức là biết trước thời điểm và a. Các loại đồ ăn và đồ uống được đặt nhu cầu giao hàng, có thể xây dựng lời giải hàng, kèm theo yêu cầu riêng của điều phối tối ưu dựa trên thuật toán ghép cặp khách. có cải biên [2]. b. Số tiền thanh toán. Trong lời giải tối ưu có thể xuất hiện tình c. Địa điểm giao hàng. huống bỏ qua một đơn hàng đến trước để có d. Thời điểm nhận đơn hàng (của tổng đài thể xử lý nhiều đơn hàng đến sau; điều này trực tuyến). không thể xuất hiện trong những hệ thống ra e. Thời điểm nhận đơn hàng (của cửa quyết định theo thời gian thực. Tuy nhiên, lời hàng địa phương). giải tối ưu này cho ra một ước lượng cận trên f. Thời điểm bắt đầu đi giao hàng. khi đánh giá các kết quả ra quyết định dựa trên những thuật toán khác nhau. 119
Tuyển tập Hội nghị Khoa học thường niên năm 2015. ISBN : 978-604-82-1710-5 3. KẾT QUẢ NGHIÊN CỨU Thử nghiệm kết quả trên phần mềm mô Phần mềm mô phỏng phỏng cho thấy có thể giảm khoảng 32% số Để có thể đánh giá hoạt động của hệ thống lần vi phạm cam kết khách hàng. ra quyết định giao vận, phải sử dụng một phần mềm mô phỏng hoạt động của hệ thống thay vì sử dụng một hàm đánh giá. Lý do là vì các điều kiện của việc ra quyết định sau ảnh hưởng bởi những quyết định trước. Một ví dụ minh hoạt thực tế này: một đơn hàng A trong điều kiện thực tế chỉ có thể giao hàng từ 10h, vì trước đó không còn nhân viên giao hàng; nhưng do tối ưu việc ra quyết định trước đó, đơn hàng A trong thử nghiệm có thể giao từ 9h45; hệ quả là việc đánh giá đơn hàng A có giao theo cam kết hay không còn Hình 3: Số lỗi tích lũy trong một tháng theo phụ thuộc vào trạng thái hệ thống trước đó từng phương pháp ra quyết định chứ không phải chỉ phụ thuộc vào các dữ liệu trong đơn hàng. 4. KẾT LUẬN Chúng tôi tiến hành xây dựng một phần Bài báo này chỉ giới thiệu một kết quả hết mềm mô phỏng bằng C#. Phần mềm nhận sức nhỏ của việc áp dụng các thuật toán hợp lệnh điều vận của module ra quyết định, mô lý vào việc ra quyết định điều phối giao vận. phỏng hoạt động và báo cáo số lần vi phạm Kết quả thử nghiệm mô phỏng trên dữ cam kết khách hàng tích lũy trong một tháng. liệu thực của một tháng cho ta hình dung khả 3.2. Kết quả thử nghiệm một số phương năng áp dụng công nghệ vào thực tế sẽ nâng pháp ra quyết định cao năng suất và chất lượng dịch vụ như thế Tham khảo trên một số tài liệu [3], chúng nào. Nó cũng mở ra khả năng áp dụng vào tôi thử nghiệm 4 chiến lược ra quyết định nhiều vấn đề tương tự trong các bài toán giao khác nhau: vận đơn hàng hoặc điều phối hoạt động cứu (i) Ưu tiên cửa hàng theo khoảng cách trợ thiên tai. địa lý: cửa hàng nào gần khách hàng nhất thì nhận được đơn hàng. (ii) Ưu tiên cửa hàng theo khoảng cách 5. TÀI LIỆU THAM KHẢO địa lý, nhưng chỉ xét những cửa hàng [1] Hoong Chilin Lau and Qi Zhang Liu; 2000; còn nhân viên có thể phục vụ. Collaborative Model and Algorithms for (iii) Xét N cửa hàng gần nhất (*), chọn Supporting Real-Time Distribution Logistics cửa hàng còn nhiều nhân viên giao Systems; Electronic Notes in Discrete hàng nhất. Mathematics, volume 4, pp 17-31. (iv) Xét N cửa hàng gần nhất (*), chọn [2] J.K. Lenstra, A.H.G. Rinnooy Kan, A. cửa hàng có tỉ lệ nhân viên giao hàng Schrijver, ed.; History of Mathematical còn rảnh rỗi nhất cao nhất. Programming --- A Collection of Personal (*) Nguyên tắc chọn N cửa hàng như sau: Reminiscences; CWI, Amsterdam and loại bỏ những cửa hàng hết nhân viên giao North-Holland, Amsterdam, pp 32–54. hàng hoặc quá xa (thời gian giao quá 30 [3] David Simchi-Levi, Xin Chen, Julien phút), xếp tăng dần xét theo khoảng cách địa Bramel; The Logic of Logistics: Theory, lý, nếu cửa hàng phụ trách thuộc top 3 thì Algorithms, and Applications for Logistics and Supply Chain Management, 2nd ed. chọn N = 3, nếu không thì chọn 3 cửa hàng Springer 2005, pp 293-318. gần nhất và cửa hàng phụ trách (N = 4). 120