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