Cải thiện lộ trình vận chuyển cho một công ty phân phối sữa
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (1.37 MB, 103 trang )
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC BÁCH KHOA
---------------o0o---------------
LUẬN VĂN TỐT NGHIỆP
CẢI THIỆN LỘ TRÌNH VẬN CHUYỂN
CHO MỘT CÔNG TY PHÂN PHỐI SỮA
SVTH: NGUYỄN THỊ TƯỜNG VY
MSLV: ISE-16-49
Thành Phố Hồ Chí Minh, tháng 07 năm 2020
1
BỘ GIÁO DỤC VÀ ĐÀO TẠO
CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM
ĐHQG TP.HCM – TRƯỜNG ĐH BÁCH KHOA
Độc lập – Tự do – Hạnh phúc
--------------------------------------------
KHOA CƠ KHÍ
BỘ MÔN KỸ THUẬT HỆ THỐNG CÔNG NGHIỆP
NHIỆM VỤ LUẬN VĂN TỐT NGHIỆP
Họ và tên: NGUYỄN THỊ TƯỜNG VY
1. Đầu đề luận văn: Cải thiện lộ trình vận chuyển cho một công ty phân phối sữa
2. Nhiệm vụ:
-
Tìm hiểu tổng quan hoạt điều phối xe của công ty, từ đó xác định bài toán phù hợp
Mô hình hóa bài toán thực tế của công ty
Xây dựng chương trình giải bài toán điều phối xe.
Đánh giá hiệu quả của chương trình so với kết quả điều phối hiện tại.
3. Ngày giao nhiệm vụ luận văn: 30/03/2020
4. Ngày hoàn thành nhiệm vụ: 22/07/2020
5. Họ và tên người hướng dẫn:
Phần hướng dẫn
TS. Phan Thị Mai Hà
Toàn phần
Nội dung và yêu cầu LVTN đã được thông qua Bộ môn
Ngày_____tháng_____năm_____
CHỦ NHIỆM BỘ MÔN
NGƯỜI HƯỚNG DẪN CHÍNH
_____________________
__________________________
PHẦN DÀNH CHO KHOA, BỘ MÔN:
Người duyệt (chấm sơ bộ):______________________________________________
Đơn vị:______________________________________________________________
Ngày bảo vệ:_________________________________________________________
Điểm tổng kết:________________________________________________________
Nơi lưu trữ luận văn:__________________________________________________
2
LỜI CẢM ƠN
Luận văn “Cải thiện lộ trình vận chuyển cho một công ty phân phối sữa” được hoàn thành
với sự giúp đỡ tận tình của các thầy cô giáo Bộ môn Kỹ Thuật Hệ thống Công nghiệp, trường
Đại học Bách Khoa - Đại học Quốc gia TP. Hồ Chí Minh, sự động viên từ gia đình, bạn bè và
sự nỗ lực của bản thân trong suốt quá trình học tập và thực hiện luận văn.
Đầu tiên, em xin gửi lời cảm ơn chân thành nhất đến cô Phan Thị Mai Hà, người đã có
những định hướng giúp em hoàn thành luận văn tốt nghiệp của mình. Trong suốt thời gian
thực hiện cô đã tận tình chỉ dẫn, giúp đỡ và cung cấp cho em những kiến thức, tài liệu cần
thiết để hoàn thành luận văn này.
Xin được gửi lời cảm ơn đến các anh chị trong công ty Abbott đã nhiệt tình giúp đỡ, tạo
điều kiện thuận lợi cho em trong suốt quá trình học tập và làm việc tại công ty.
Cuối cùng, em xin gửi lời cảm ơn tới gia đình, bạn bè đã tin tưởng, giúp đỡ, động viên em
trong suốt quá trình làm luận văn tốt nghiệp.
Do thời gian và kiến thức có hạn chắc chắn luận văn cũng không thể tránh khỏi những
thiếu sót, hạn chế. Kính mong nhận được sự chỉ bảo và góp ý của quý Thầy, Cô
Xin chúc mọi người luôn mạnh khỏe, đạt được nhiều thành tích trong công tác, học tập và
nghiên cứu khoa học.
Em xin chân thành cảm ơn!
Tp. Hồ Chí Minh, tháng 7 năm 2020
Sinh viên thực hiện
3
TÓM TẮT LUẬN VĂN
Luận văn tập trung nghiên cứu và giải quyết một bài toán định tuyến xe (Vehicle Routing
Problem-VRP) thực tế, bắt nguồn từ nhu cầu cải tiến hoạt động điều phối các xe giao hàng
của công ty sữa Abbott Nutrition Việt Nam (Abbott), với mục đích đề ra là giảm 15% chi phí
vận tải cho công ty.
Bài toán vận tải của công ty là một dạng kết hợp của nhiều biến thể của bài toán VRP với
những đặc điểm đặc trưng như:
-
Có một kho hàng
-
Đồ thị biểu diễn đường đi là đồ thị bất đối xứng.
-
Đội xe có nhiều loại phương tiện có sức chứa khác nhau
-
Cho phép xe thực hiện nhiều chuyển trong một ngày.
-
Điểm giao hàng có ràng buộc loại xe được phép đến giao hàng
Để giải quyết bài toán này, luận văn sử dụng Phần mềm Visual Studio Code với sự hỗ trợ
của công cụ giải OR-Tools viết bằng ngôn ngữ lập trình Python dựa trên “giải thuật tiết
kiệm”. Giải thuật được thử nghiệm trên 24 bộ dữ liệu thực tế trong tháng 9/2019, kết quả sau
đó được so sánh với kết quả khi sử dụng giải thuật mô phỏng tôi luyện và kết quả điều phối
thực tế từ công ty.
Kết quả thu được cho thấy “giải thuật tiết kiệm” cho kết quả tốt hơn giải thuật mô phỏng
tôi luyện ở 14/24 bộ dữ liệu, đồng thời kết quả từ “giải thuật tiết kiệm” cũng cho chi phí vận
tải thấp hơn ở tất cả các bộ dữ liệu so với kết quả điều phối hiện tại trong thực tế, giúp giảm
17.56 % chi phí vận tải, hoàn toàn đáp ứng được mục đích đặt ra ban đầu.
4
MỤC LỤC
TRANG BÌA
NHIỆM VỤ LUẬN VĂN TỐT NGHIỆP.......................................................................................ii
LỜI CẢM ƠN....................................................................................................................................iii
TÓM TẮT LUẬN VĂN....................................................................................................................iv
DANH MỤC HÌNH ẢNH...............................................................................................................vii
DANH MỤC BẢNG BIỂU............................................................................................................viii
DANH MỤC CÁC TỪ VIẾT TẮT.................................................................................................ix
Chương 1 GIỚI THIỆU....................................................................................................................1
1.1
Lý do thực hiện đề tài........................................................................................................1
1.2
Mục đích và mục tiêu đề tài...............................................................................................2
1.3
Phạm vi và đối tương nghiên cứu......................................................................................2
1.4
Cấu trúc luận văn...............................................................................................................2
Chương 2 CƠ SỞ LÝ THUYẾT VÀ PHƯƠNG PHÁP LUẬN...................................................4
2.1
Cơ sở lý thuyết...................................................................................................................4
2.1.1
Khái niệm mô hình hóa [1].........................................................................................4
2.1.2
Tổng quan về bài toán VRP........................................................................................4
2.1.3
Bài toán VRP với nhiều chuyến (Vehicle routing problem with multiple tripsVRPMT)....................................................................................................................................9
2.1.4
Giải thuật tiết kiệm...................................................................................................10
2.1.5
Giải thuật mô phỏng tôi luyện..................................................................................11
2.1.6
Các công cụ hỗ trợ....................................................................................................11
2.2
Phương pháp luận............................................................................................................13
Chương 3 PHÂN TÍCH HIỆN TRẠNG VÀ XÁC ĐỊNH VẤN ĐỀ..........................................15
3.1
Giới thiệu đối tượng nghiên cứu......................................................................................15
3.1.1
Giới thiệu chung.......................................................................................................15
3.1.2
Sản phẩm dinh dưỡng của Abbott tại Việt Nam.......................................................15
3.1.3
Cơ cấu tổ chức của công ty......................................................................................16
3.2
Tổng quan về bộ phận vận tải..........................................................................................17
3.2.1
Kho hàng..................................................................................................................17
3.2.2
Khách hàng...............................................................................................................17
3.2.3
Hàng hóa...................................................................................................................17
3.2.4
Đội xe.......................................................................................................................17
3.2.5
Quy trình vận hành hiện tại......................................................................................18
5
3.2.6
3.3
Yêu cầu, ràng buộc trong giao hàng.........................................................................20
Phân tích hiện trạng.........................................................................................................20
3.3.1
Trong thuê xe............................................................................................................20
3.3.2
Trong vận hành thực tế.............................................................................................23
3.4
Phân tích nguyên nhân gây rớt đơn trong vận hành........................................................24
Chương 4 XÂY DỰNG MÔ HÌNH BÀI TOÁN..........................................................................28
4.1
Mô hình bài toán gốc.......................................................................................................28
4.2
Xây dựng mô hình bài toán của công ty..........................................................................30
4.2.1
Khái quát..................................................................................................................30
4.2.2
Thiết lập mô hình......................................................................................................31
4.3
Giải mô hình....................................................................................................................33
4.3.1
Dữ liệu đầu vào........................................................................................................33
4.3.2
Tính toán các tham số...............................................................................................37
4.3.3
Giải mô hình.............................................................................................................40
Chương 5 KIỂM TRA VÀ ĐÁNH GIÁ KẾT QUẢ....................................................................47
5.1
Kiểm tra kết quả...............................................................................................................47
5.2
Đánh giá kết quả..............................................................................................................50
Chương 6 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN..................................................................55
6.1
Kết luận............................................................................................................................55
6.2
Hướng phát triển..............................................................................................................55
TÀI LIỆU THAM KHẢO...................................................................................................................
PHỤ LỤC A: BẢNG BIỂU............................................................................................................A1
PHỤ LỤC B: CODE LẬP TRÌNH................................................................................................B1
6
DANH MỤC HÌNH ẢNH
Hình 2.1 Giải pháp hoạch định tuyến đường cho 15 điểm giao hàng với 4 xe...............................5
Hình 2.2 Biểu đồ thể hiện mối quan hệ giữa các loại VRP.............................................................8
Hình 2.3 Phương pháp luận...........................................................................................................14
Hình 3.1 Một số sản phẩm công ty Abbott ở Việt Nam.................................................................16
Hình 3.2 Cơ cấu tổ chức................................................................................................................16
Hình 3.3 Quy trình vận hành hiện tại............................................................................................19
Hình 3.4 Biểu đồ nguyên nhân việc giao hàng trễ.........................................................................25
Hình 4.1 Kết quả phân chuyến......................................................................................................46
Hình 5.1 Kết quả sử dụng xe tăng cường......................................................................................54
7
DANH MỤC BẢNG BIỂU
Bảng 3.1 Thông tin nhóm xe, loại xe.............................................................................................18
Bảng 3.2 Hiện trạng sử dụng xe tháng 9/2019..............................................................................21
Bảng 3.3 Chi phí thuê xe...............................................................................................................22
Bảng 3.4 Thống kê số lượng đơn hàng rớt tháng 9/2019..............................................................24
Bảng 3.5 Lý giải các nguyên nhân gây giao hàng trễ....................................................................25
Bảng 3.6 Thống kê kết quả thu nhập.............................................................................................27
Bảng 4.1 Danh sách đơn hàng ngày 3/9/2019...............................................................................33
Bảng 4.2 Dữ liệu kho.....................................................................................................................34
Bảng 4.3 Danh sách các cửa hàng.................................................................................................34
Bảng 4.4 Dữ liệu xe.......................................................................................................................36
Bảng 4.5 Ma trận khoảng cách giữa nút i và nút j.........................................................................37
Bảng 4.6 Ma trận thời gian di chuyển giữa nút i và nút j..............................................................38
Bảng 4.7 Kết quả phân chuyến......................................................................................................45
Bảng 5.1 Kiểm tra tải trọng, thời gian, khoảng cách.....................................................................47
Bảng 5.2 Kiểm tra ràng buộc.........................................................................................................49
Bảng 5.3 Kết quả thực nghiệm......................................................................................................50
Bảng 5.4 Kết quả sử dụng xe53
8
DANH MỤC CÁC TỪ VIẾT TẮT
STT
Từ viết tắt
Tên tiếng Anh
Ý nghĩa
1
AVRP
Asymmetric VRP
Bài toán VRP với khoảng cách bất đối
xứng
2
CVRP
Capacitated
Constrained VRP
Bài toán VRP với ràng buộc sức chứa
3
DVRP
Distance-Constrained
VRP
Bài toán VRP với ràng buộc độ dài tối đa
của quãng đường mà xe được phép đi
4
MDVRP
Multi-Depot VRP
Bài toán VRP với nhiều kho hàng
5
MOVRP
Multi Objective VRP
Bài toán VRP đa mục tiêu
6
FMEA
Failure Modes and
Effects Analysis
phương pháp phân tích những phương
thức xảy ra sai lỗi và ảnh hưởng của nó
7
SA
Simulated Annealing
Thuật toán mô phỏng luyện kim
8
SDVRP
VRP with sitedependent
Bài toán VRP với yêu cầu loại xe phù hợp
9
RPN
Risk Priority Number
Rủi so ưu tiên số
10
VRP
Vehicle Routing
Problem
Bài toán định tuyến xe hàng
11
VRPB
VRP with Backhauls
Bài toán VRP nhập xuất hàng kết hợp
12
VRPPD
VRP with Pickup and
Delivery
Bài toán VRP nhập xuất hàng đồng thời
13
VRPMT
VRP with multiple
trips
Bài toán VRP cho phép một xe đi nhiều
chuyến
14
VRPTW
VRP with Time
Windows
Bài toán VRP với cửa sổ thời gian
9
Chương 1 GIỚI THIỆU
Chương này sẽ giới thiệu về lý do lựa chọn đề tài, mục tiêu nghiên cứu, đối tượng, phạm vi
và giới hạn đề tài cũng như tổng quan về cấu trúc luận văn, nhằm giúp người đọc có cái nhìn tổng
quan về nghiên cứu.
1.1
Lý do thực hiện đề tài
Trong những năm gần đây, bài toán định tuyến xe (Vehicle Routing Problem-VRP) thu hút
nhiều sự chú ý do sự quan tâm ngày càng tăng đối với các giải pháp vận tải và công nghệ khác
nhau cũng như việc sử dụng chúng trong hậu cần và vận chuyển. Ngày càng có nhiều công ty
đang cố gắng tổ chức việc giao hàng tốt hơn bằng cách sử dụng các giải pháp công nghệ được đề
xuất. Mỗi bài toán VRP thực tế thường có các ràng buộc đặc trưng riêng, nhưng nhìn chung tất cả
đều là bài toán NP-khó. Đề tài này tập trung nghiên cứu và giải quyết một bài toán VRP thực tế,
bắt nguồn từ nhu cầu cải tiến hoạt động điều phối các xe giao hàng của công ty sữa Abbott
Nutrition Việt Nam (Abbott), cơ sở Tp. Hồ Chí Minh.
Hiện nay, Abbott thực hiện việc điều phối xe giao hàng bằng tay với quy trình như sau: Hàng
ngày, kho R1_HCM của công ty Abbott thực hiện việc điều phối hàng hóa cho khoảng một trăm
cửa hàng trong thành phố. Vì số lượng đơn hàng lớn, địa điểm giao thay đổi mỗi ngày, cùng với
những yêu cầu ràng buộc khác nhau đặt ra trong quá trình giao hàng, nên hàng ngày phải tốn
nhiều thời gian cho việc sắp xếp các đơn hàng, cũng như khó có thể đảm bảo phương tiện được
sử dụng hợp lý, tuyến đường giao hàng ngắn, … dẫn đến chi phí vận tải cao. Bên cạnh đó thì việc
làm sao để đáp ứng nhu cầu ngày càng cao, cũng như số lượng cửa hàng ngày càng tăng mà vẫn
đạt được sự tin tưởng của khách hàng thông qua việc đáp ứng tốt nhu cầu là một yếu tố vô cùng
quan trọng. Do đó, công ty Abbott có nhu cầu cải thiện hoạt động điều phối vận chuyển hàng hóa
tại kho hàng R1_HCM. Đó chính là lý do hình thành đề tài “Cải thiện lộ trình vận chuyển cho
một công ty phân phối sữa”, với mong muốn áp dụng những kiến thức và những nghiên cứu vào
môi trường của doanh nghiệp. Từ đó góp phần vào sự phát triển của công ty thông qua việc giảm
thiểu chi phí vận tải. Ngoài ra, việc tổ chức điều phối các tuyến đường tốt hơn có thể ảnh hưởng
đến các khía cạnh sinh thái bằng cách làm giảm ô nhiễm, đây cũng là một vấn đề quan trọng cần
được quan tâm hiện nay.
1
Bài toán vận tải của công ty là một dạng kết hợp của nhiều biến thể của bài toán VRP. Luận
văn này đề nghị một thuật giải heuristic để giải quyết bài toán này, kết quả thực nghiệm sau đó
được so sánh với kết quả từ một thuật giải metaheuristics và kết quả điều phối được lấy từ thực
tế.
1.2
Mục đích và mục tiêu đề tài
Mục đích của luận văn này là đưa ra một giải pháp để giải quyết bài toán định tuyến xe với
kích thước lớn và giúp công ty giảm được 15% chi phí vận tải.
Để đạt được mục đích trên, các mục tiêu sau cần được thực hiện:
-
Tìm hiểu về bài toán định tuyến xe và các biến thể của nó.
-
Tìm hiểu hoạt động vận tải hiện tại của công ty, nắm được các yêu cầu ràng buộc trong
giao hàng, để từ đó xác định bài toán phù hợp cho trường hợp của công ty. Xây dựng
được mô hình bài toán.
-
Giải mô hình bài toán với sự hỗ trợ của phần mềm Visual Studio Code, công cụ giải ORTools bằng ngôn ngữ lập trình Python dựa trên “giải thuật tiết kiệm”.
1.3
Kiểm tra, đánh giá kết quả đạt được và đề xuất hướng phát triển.
Phạm vi và đối tương nghiên cứu
Luận văn tập trung vào nghiên cứu tình hình vận tải của công ty Abbott Nutrition và mạng
lưới phân phối trong nội thành Thành phố Hồ Chí Minh. Qua đó thấy được mức độ hiệu quả và
những khó khăn đang hiện diện trong quy trình làm việc hằng ngày của bộ vận vận tải, để từ đó
nêu ra được biện pháp để cải thiện hiện trạng hoạt động ban đầu. Các đối tượng nghiên cứu:
1.4
Các lý thuyết cơ bản về bài toán định tuyến xe.
Các biến thể của bài toán VRP liên quan đến bài toán thực tế của công ty.
Ngôn ngữ lập trình Python, công cụ giải OR-tools.
Cấu trúc luận văn
Nội dung của luận văn được trình bày trong 6 chương
Chương 1: Giới thiệu
2
Chương 1 trình bày lý do thực hiện đề tài “Cải thiện lộ trình vận chuyển cho một công ty
phân phối sữa”, mục đích, mục tiêu nghiên cứu, đối tượng, phạm vi và giới hạn đề tài cũng như
tổng quan về cấu trúc luận văn.
Chương 2: Cơ sở lý thuyết và phương pháp luận
Chương 2 trình bày phương pháp luận và những cơ sở lý thuyết liên quan. Các lý thuyết để hỗ
trợ giải bài toán phân phối, bao gồm các lý thuyết về bài toán VRP, “giải thuật tiết kiệm”. Phương
pháp luận sẽ bao gồm thu thập số liệu và phương pháp phân tích.
Chương 3: Phân tích hiện trạng và xác định vấn đề
Chương 3 giới thiệu chung về công ty bao gồm quy mô, sản phẩm, cơ cấu tổ chức. Phân tích
hoạt động phân phối hàng của công ty tại bộ phận vận tải. Tại chương này cũng đánh giá hiện
trạng vận hành của đội xe thông qua phân tích dữ liệu quá khứ để làm cơ sở thực hiện cải tiến
phương pháp điều phối vận tải.
Chương 4: Mô hình bài toán
Chương 4 trình bày mô hình bài toán gốc, xác định các biến thể của bài toán định tuyến xe
liên quan đến bài toán vận tải của công ty, sau đó trình bày mô hình bài toán định tuyến xe cho
phép một xe đi nhiều chuyến với các thay đổi phù hợp với bài toán thực tế của công ty dựa trên
mô hình bài toán gốc. Giải mô hình bài toán với sự hỗ trợ của phần mềm Visual Studio Code,
ngôn ngữ lập trình Python dựa trên “giải thuật tiết kiệm”.
Chương 5: Kiểm tra và đánh giá kết quả
Chương 5 tiến hành kiểm tra các kết quả thu được. Trình bày kết quả thực nghiệm khi áp
dụng thuật giải đã đề nghị lên một số bộ dữ liệu thực tế của công ty, so sánh kết quả với kết quả
thu được khi áp dụng giải thuật mô phỏng tôi luyện vào cùng bộ dữ liệu và so với kết quả xếp tay
từ công ty, đánh giá hiệu quả của giải thuật tiết kiệm.
Chương 6: Kết luận và hướng phát triển
Chương 6 trình bày kết luận và các hướng phát triển của đề tài
3
Chương 2 CƠ SỞ LÝ THUYẾT VÀ PHƯƠNG PHÁP LUẬN
Chương 2 sẽ trình bày cơ sở lý thuyết liên quan và phương pháp luận. Các lý thuyết để hỗ trợ
giải bài toán phân phối, bao gồm các lý thuyết về bài toán VRP, “giải thuật tiết kiệm”, một vài
công cụ hỗ trợ được sử dụng trong báo cáo.
2.1
Cơ sở lý thuyết
2.1.1
Khái niệm mô hình hóa [1]
Mô hình hóa (Modeling) là một quá trình thay thế hệ thống thực bằng một mô hình để nhằm
thu nhận các thông tin của hệ thống bằng cách tiến hành các thực nghiệm, tính toán trên mô hình.
Chúng ta chỉ có thể xây dựng được mô hình gần đúng với hệ thống thực. Mặc dù vậy mô hình
hóa luôn luôn là một phương pháp hữu hiệu để con người nghiên cứu hệ thống, nhận biết các quá
trình, các quy luật tự nhiên. Đặc biệt ngày nay nhờ có sự trợ giúp đắc lực của máy tính người ta
có thể phát triển các phương pháp mô hình hóa cho phép xây dựng các mô hình ngày càng gần
với hệ thống nghiên cứu, đồng thời việc thu nhận lựa chọn, xử lý các thông tin về mô hình rất
thuận tiện, nhanh chóng và chính xác.
Chính vì vậy mô hình hóa là một phương pháp nghiên cứu khoa học mà tất cả các kỹ sư phải
nghiên cứu và ứng dụng vào thực tiễn hoạt động của mình.
2.1.2
Tổng quan về bài toán VRP
a. Giới thiệu
Dịch vụ vận chuyển là một khâu quan trọng trong ngành công nghiệp sản xuất. Đầu tiên,
nguyên vật liệu được vận chuyển đến nhà máy từ nhiều nhà cung cấp khác nhau; sau đó thành
phẩm sẽ được vận chuyển đến các kho ở các vị trí khác nhau; cuối cùng, từ các kho trung tâm này
hàng hóa được phân phối đến các khách hàng. Cả hai qui trình cung cấp và phân phối đều đòi hỏi
khả năng quản lý các phương tiện vận chuyển một cách hiệu quả nhằm tiết kiệm tối đa chi tiêu.
Một trong các thước đo hiệu quả nhất cho việc quản lý này chính là hiệu quả của việc lập lộ trình
cho các xe vận chuyển. Yêu cầu tối ưu các lộ trình cho các xe với các ràng buộc khác nhau đã
phát sinh bài toán định tuyến xe hàng (VRP).
Bài toán định tuyến xe hàng (VRP) là một lớp các bài toán tối ưu hóa tổ hợp nhằm xác định
một tập các lộ trình tối ưu, mỗi lộ trình được thực hiện bởi một phương tiện vận tải (xe hàng) bắt
4
đầu và kết thúc tại kho, đáp ứng các yêu cầu của khách hàng và thỏa mãn mọi ràng buộc sao cho
chi phí là tối thiểu. Việc phân phối hàng hóa liên quan tới dịch vụ của một tập các khách hàng bởi
một tập các phương tiện giao thông trong một giai đoạn thời gian, được lái bởi một tập các lái xe
và thực hiện việc di chuyển bởi một mạng đường bộ thích hợp [2].
VRP được Dantzig và Ramser [5] đưa ra vào năm 1959 với bài toán ban đầu là việc phân phố
gas tới các trạm bán lẻ và hai ông cũng đã đề xuất được mô hình toán học, giải thuật đầu tiên cho
bài toán này. Kể từ đó cho tới nay, VRP đã được rất nhiều nhà nghiên cứu quan tâm, mở rộng,
đưa ra các giải pháp, ứng dụng vào thực tế. Mạng đường đi được sử dụng cho việc giao vận hàng
hóa thường được mô tả thông qua một đồ thị mà cạnh của nó biểu diễn đoạn đường còn các đỉnh
tương ứng với vị trí kho hàng hoặc khách hàng. Các cạnh là có hướng hoặc vô hướng tùy thuộc
vào việc có thể đi theo một chiều hoặc hai chiều. Mỗi cạnh được kết hợp với một chi phí, thường
biểu diễn độ dài và thời gian đi, hai yếu tố này có thể phụ thuộc vào loại xe hoặc thời gian đi qua
cung đó.
Hình 2.1 là ví dụ về giải pháp hoạch định tuyến đường cho 15 điểm giao hàng với 4 xe tải [4].
Hình 2.1 Giải pháp hoạch định tuyến đường cho 15 điểm giao hàng với 4 xe
Một số khái niệm chính của bài toán gồm: [3]
-
Xe (Vehicle): phương tiện được dùng để vận chuyển hàng hóa. Trong thực tế hầu như các
xe là không đồng nhất, chúng được phân loại dựa vào các đặc điểm như sức chứa của xe
5
(tức tải trọng hàng hóa tối đa xe có thể đáp ứng), loại hàng hóa mà xe có thể vận chuyển
(hàng hóa đông lạnh, hàng hóa khô…), chi phí vận chuyển (có hai loại chi phí thông
dụng: chi phí cố định- chi phí cần thiết ban đầu để xe có thể khởi hành, chi phí này không
phụ thuộc vào quãng đường mà xe phải đi; chi phí biến đổi- chi phí tiêu tốn trên từng đơn
vị quãng đường mà xe phải đi).
-
Kho hàng (Depot): là nơi cất trữ hàng hóa hay cũng có thể là địa điểm xuất phát/quay về
của các xe. Trong một số bài toán, hàng hóa cần giao có thể được cất trữ trong một vài
kho hàng.
-
Khách hàng (Customer): có thể đón hàng do xe giao tới hoặc chuyển hàng lên xe để vận
chuyển về kho hoặc cả hai. Mỗi khách hàng yêu cầu một lượng hàng hóa nhất định, có thể
đưa ra một số yêu cầu khác về thời gian cho phép xe đến giao hàng, thời gian cho phép
bốc dỡ hàng, …
-
Chuyến (Route- trip): mỗi hành trình bắt đầu đi từ điểm xuất phát rồi quay trở về điểm
ban đầu (kho hàng) của một xe được coi là một chuyến.
Những thông số cần được chú ý trong bài toán hoạch định tuyến đường: [4]
-
Thời gian và khoảng cách: thời gian tối đa xe phải giao xong hàng và khoảng cách tối đa
xe cần đi.
-
Tải trọng của xe: khả năng chuyên chở tối đa của xe là bao nhiêu, có chứa hết được sản
phẩm cần giao không.
-
Số xe cần có: số xe ít nhất có thể để có thể giao hết hàng.
-
Số nhân công cần có: tương tự, số nhân công tối thiểu để hoàn thành công việc.
-
Chất lượng dịch vụ: đảm bảo không có lỗi xảy ra khi giao hàng đến khách hàng.
-
Thời gian đóng mở cửa hàng: có cửa hàng chỉ nhận hàng trong một khoảng thời gian nhất
định.
6
-
Những vấn đề khác: số kho chứa hàng, điều kiện giao thông, loại hàng hóa, kích cỡ hàng
hóa, giờ cấm tải trong thành phố, ...
b. Mục tiêu chức năng của VRP
Mục tiêu chức năng của VRP có thể rất khác nhau tùy thuộc vào ứng dụng cụ thể, nhưng có
một số mục tiêu chính là:
-
Giảm thiểu chi phí vận chuyển tổng thể dựa trên khoảng cách di chuyển tổng thể (Hay
thời gian di chuyển) và chi phí cố định tương ứng với các xe được sử dụng.
-
Giảm thiểu số lượng xe cần thiết để phục vụ tất cả khách hàng.
-
Ít có biến động về thời gian đi lại và tải trọng xe.
c. Các biến thể quan trọng của bài toán định tuyến xe
Bài toán VRP có rất nhiều biến thể khác nhau dựa trên yêu cầu cụ thể của các bài toán thực tế.
Các biến thể này đã tạo thành các nhánh nghiên cứu khác nhau, tất nhiên các phương pháp giải
quyết các biến thể cũng có thể được chỉnh sửa để áp dụng qua lại lẫn nhau. Một số biến thể quan
trọng của bài toán VRP bao gồm: [3]
-
Bài toán VRP với khoảng cách bất đối xứng (Asymmetric VRP- AVRP): bài toán trong đó
đồ thị biểu diễn đường đi là một đồ thị có hướng. Hầu hết các bài toán VRP trong thực tế
đều thuộc dạng này.
-
Bài toán VRP với nhiều kho hàng (Multi-Depot VRP- MDVRP): bài toán với nhiều kho
hàng khác nhau, mỗi xe sẽ phụ thuộc vào một kho hàng duy nhất.
-
Bài toán VRP với ràng buộc sức chứa (Capacitated VRP-CVRP): mỗi loại xe có sức chứa
khác nhau.
-
Bài toán VRP với ràng buộc độ dài tối đa của quãng đường mà xe được phép đi
(Distance-Constrained VRP- DVRP): gắn với mỗi loại xe là một tham số thể hiện tổng độ
dài quãng đường tối đa mà mỗi xe được phép đi.
7
-
Bài toán VRP với ràng buộc khoảng thời gian (VRP with Time Windows- VRPTW): mỗi
khách hàng sẽ chỉ cho phép xe đến giao hàng trong một khoảng thời gian cho phép nhất
định.
-
Bài toán VRP với yêu cầu giao và nhận hàng (VRP Pickup and Delivery- VRPPD): bài
toán này cho phép xe thực hiện cả hai chức năng - lấy hàng từ một số khách hàng và đem
đi giao cho khách hàng khác.
-
Bài toán VRP với yêu cầu giao hàng trước (VRP with Backhauls- VRPB): tương tự
VRPPD, bài toán này cũng cho phép xe giao hàng và nhận hàng, nhưng có một chút khác
biệt về ràng buộc thứ tự gặp khách hàng: xe phải đi giao hàng cho tất cả các khách hàng
cần nhận trước, rồi sau đó mới đến gặp các khách hàng cần giao để lấy hàng đem về kho.
-
Bài toán VRP cho phép một xe đi nhiều chuyến (VRP with multiple trips- VRPMT) [6]:
trong bài toán này, mỗi xe có thể chạy nhiều hơn một chuyến
-
Bài toán VRP với yêu cầu loại xe phù hợp (VRP with site-dependent- SDVRP) [7]: trong
bài toán này, mỗi khách hàng chỉ chấp nhận một số loại xe nhất định.
-
Bài toán VRP cho phép chia nhỏ đơn hàng (Split Delivery Vehicle Routing Problem): mỗi
đơn đặt hàng được phép phân nhỏ ra với số lượng nhỏ hơn, khi đó, một khách hàng có thể
được giao hàng bởi nhiều hơn một xe.
-
Bài toán VRP đa mục tiêu (Multi Objective VRP- MOVRP): Trong bài toán này, ngoài
mục tiêu cực tiểu hóa tổng chi phí (thời gian) vận chuyển, còn có các mục tiêu khác.
Đây là một số bài toán VRP chính đang được nghiên cứu, mở rộng để ứng dụng vào thực tế.
Mối tương quan giữa chúng được thể hiện như trong hình 2.2.
Hình 2.2 mô tả mối quan hệ giữa các loại VRP, mũi tên đi từ bài toán A sang bài toán B có
nghĩa là B là bài toán mở rộng của A. Với mỗi bài toán, luôn có một bài toán cơ bản trước, sau đó
được các nhà nghiên cứu mở rộng thêm.
Tất nhiên, các biến thể trên của bài toán VRP có thể kết hợp lại với nhau để tạo nên các biến
thể mới cho phù hợp với bài toán thực tế cụ thể. Bài toán mà luận văn này giải quyết là một bài
8
toán VRP thực tế và cũng là một dạng biến thể kết hợp của các biến thể đã nêu trên nhưng được
bổ sung thêm một số yêu cầu đặc trưng khác. Cụ thể là sự kết hợp giữa bài toán VRP cho phép
một xe đi nhiều chuyến (VRP with multiple trips- VRPMT) và bài toán VRP với yêu cầu loại xe
phù hợp (VRP with site-dependent- SDVRP).
Hình 2.2 Biểu đồ thể hiện mối quan hệ giữa các loại VRP
d. Các hướng tiếp cận và ứng dụng của bài toán định tuyến xe
Bài toán định tuyến xe và các biến thể của nó được coi là bài toán tối ưu hóa tổ hợp có độ
phức tạp tính toán cao và được phân loại thuộc lớp NP- khó [8]. Các hướng tiếp cận cho bài toán
này được chia làm 4 nhóm chính [9]: nhóm các thuật toán chính xác, nhóm các thuật giải gần
đúng, nhóm các thuật giải heuristics cổ điển và nhóm các thuật giải metaheuristic.
-
Nhóm các thuật toán chính xác: Các phương pháp chính xác thường được áp dụng để đưa
ra lời giải tối ưu cho bài toán. Các phương pháp này chủ yếu áp dụng để giải quyết các bài
toán VRP có kích thước nhỏ và số ràng buộc ít do bị hạn chế về thời gian tìm kiếm lời
giải, bao gồm: thuật toán nhánh cận (brand and bound), thuật toán sinh cột, …
-
Nhóm các thuật giải gần đúng: Các phương pháp gần đúng gồm các thuật giải cho chất
lượng lời giải gần với lời giải tối ưu.
9
-
Nhóm các thuật giải heuristic cổ điển: Các giải thuật này được phát triển vào những năm
1960-1990. Đến nay, chúng thường được kết hợp với metaheuristic với nhiệm vụ sinh lời
giải khởi tạo hoặc cải thiện chất lượng lời giải sẵn có.
-
Nhóm các thuật giải metaheuristic: bắt đầu phát triển từ năm 1990, đây là nhóm các
hướng tiếp cận có nhiều triển vọng nhất hiện nay và thu hút được sự quan tâm của một
lượng lớn các nhà nghiên cứu. Trong nhiều trường hợp, các thuật giải metaheuristic cho
phép tìm được các lời giải tương đối tốt trong khoảng thời gian hợp lý cho các bài toán
với không gian tìm kiếm quá lớn mà các thuật toán chính xác hoặc các thuật toán xấp xỉ
không thể khả thi.
Luận văn này đề xuất sử dụng “giải thuật tiết kiệm” (Savings Algorithm), thuộc nhóm các
thuật giải heuristic cổ điển để đưa ra lời giải cho bài toán định tuyến xe.
2.1.3
Bài toán VRP với nhiều chuyến (Vehicle routing problem with multiple tripsVRPMT)
Vấn đề định tuyến xe với nhiều chuyến đi (VRPMT) [6] là một phần mở rộng của VRP tiêu
chuẩn. Trong VRP tiêu chuẩn, số lượng phương tiện thường được coi là vô hạn và mỗi phương
tiện chỉ có thể phục vụ một tuyến đường. Tuy nhiên, giả định là không hợp lý trong nhiều ứng
dụng thực tế. Một công ty phân phối sử dụng xe cho thuê để phục vụ khách hàng và phải chịu
một chi phí đáng kể cho mỗi chiếc xe được sử dụng. Bất cứ khi nào thời gian lập kế hoạch lớn
đối với thời gian vận hành và số lượng xe thực tế có hạn, khi đó mối quan tâm hàng đầu của công
ty là giảm thiểu số lượng phương tiện được sử dụng. Nên yêu cầu làm cho một chiếc xe có thể
phục vụ nhiều tuyến đường có thể là sự lựa chọn khả thi duy nhất. VRPMT có thể được mô tả
như sau:
Đặt
G N , A
A i, j | i, j �N
là một đồ thị có hướng, với
N 0,1,..., N
là tập hợp các
là tập hợp các cung. Thời gian di chuyển giữa 2 điểm
nút và
i, j �A là Tij . Nút 0
đại diện cho kho, gồm đội xe V gồm các phương tiện giống hệt nhau có tải trọng tối đa Q có
sẵn tại thời điểm 0 và phải được trả lại tại thời điểm
hàng được phục vụ, mỗi nút có nhu cầu
Qi
TH
. Các nút 1,..., N đại diện cho các khách
xác định. VRPMT yêu cầu xác định một tập hợp các
10
chuyến đi và chỉ định mỗi chuyến đi cho một phương tiện, sao cho thời gian di chuyển được
giảm thiểu và các điều kiện sau được thỏa mãn:
-
Mỗi chuyến đi bắt đầu và kết thúc tại kho
-
Mỗi khách hàng được truy cập chính xác một lần
-
Tổng nhu cầu của khách hàng trong bất kỳ chuyến đi nào không vượt quá Q
-
Tổng thời lượng của các chuyến đi được chỉ định cho cùng một phương tiện không vượt
quá
TH
(thời gian chuyến đi là tổng thời gian di chuyển trên các cung được sử dụng trong
chuyến đi)
2.1.4
Giải thuật tiết kiệm
Thuật toán đề xuất bởi Clarke và Wright [10] năm 1964, là một trong những thuật toán được
biết đến nhiều nhất cho VRP. Với hai lộ trình [0,, 0] và [0,, 0] thay vì sử dụng hai xe phục vụ cho
khách hàng và thì chúng ta kết hợp lại với nhau chỉ sử dụng một xe. Đối với mỗi cặp đường đi
được kết hợp, kết quả thu được sẽ tiết kiệm được cho chi phí hoặc độ dài của lộ trình. Khi đó kết
quả của việc tiết kiệm sẽ là = ( + + + ) − ( + + ) = + − . Hai lộ trình con chứa khách hàng và
có thể kết hợp nếu thoả điều kiện sau:
-
Cả hai điểm khách hàng và lần lượt là những điểm đều nối với trạm trung tâm.
-
Lộ trình được kết hợp sẽ chứa hai điểm khách hàng và sẽ có nhu cầu không vượt quá tải
trọng xe.
Các bước cơ bản của giải thuật:
-
Bước 1: Tính toán chỉ số tiết kiệm.
+ Tính toán chỉ số tiết kiệm = + − với
+ Tạo n chuyến xe [0,, 0], với =
+ Sắp xếp các chỉ số tiết kiệm theo thứ tự giảm dần
-
Bước 2: Kết hợp các tuyến đường ban đầu.
Từ chỉ số tiết kiệm cao nhất, xem xét:
+ Với mức tiết kiệm , xác định xem có tồn tại hai tuyến đường có thể hợp nhất hay không:
11
-
+ Tạo tuyến [0,, 0] sao vẫn thỏa các ràng buộc
Bước 3: Mở rộng tuyến đường.
+ Xem xét lần lượt từng tuyến [0,, 0]
+ Xem xét chỉ số tiết kiệm cao kế tiếp hoặc có thể được sử dụng một cách khả thi để hợp
nhất tuyến đường hiện tại với tuyến đường khác kết thúc bằng [, 0] hoặc bắt đầu bằng
[0, ]
+ Thực hiện hợp nhất và lặp lại thao tác này với tuyến đường hiện tại.
+ Nếu không tồn tại sự kết hợp nào, xem xét tuyến tiếp theo và áp dụng lại các bước
tương tự.
+ Kết thúc khi không còn sự kết hợp khả thi nào.
2.1.5
Giải thuật mô phỏng tôi luyện
Giải thuật mô phỏng tôi luyện (Simulated Annealing- SA) được đưa ra đầu tiên bởi
Kirkpatrick [11], tìm kiếm không gian lời giải bằng cách mô phỏng quá trình tôi luyện kim loại.
SA thực hiện nhảy tới các vùng trong không gian tìm kiếm ban đầu. Bước nhảy được giảm dần
theo thời gian hoặc khi nhiệt độ giảm xuống. Cuối cùng, quá trình sẽ trở thành tìm kiếm cục bộ.
Osman [12] ứng dụng SA để giải VRP bằng cách di chuyển một khách hàng từ một hành trình tới
hành trình khác hoặc hoán chuyển hai khách hàng từ hai lộ trình với nhau. Nói chung, SA là giải
thuật đơn giản, nhanh để giải bài toán VRP với kết quả gần tối ưu nhưng trong trường hợp nếu tối
ưu tổng thể là rất xa so với lời giải ban đầu thì có thể SA không đủ năng lượng để đi xa như vậy.
2.1.6
Các công cụ hỗ trợ
a. Biểu đồ xương cá
Biểu đồ xương cá sẽ giúp cho tác giả thực hiện được:
-
Hình dung xuyên suốt những nguyên nhân của một vấn đề, nó có thể bao gồm cả những
nguyên nhân gốc rễ mà không phải chỉ là các hiện tượng.
-
Phát triển các kế hoạch để xác nhận rằng những nguyên nhân tiềm ẩn là những nguyên
nhân thực sự.
-
Cung cấp cấu trúc cho nỗ lực xác định nguyên nhân.
Lợi ích:
12
-
Gợi mở ra các hiện tượng vượt ra ngoài giới hạn giúp tổ chức trong việc phát hiện các
nguyên nhân gốc rễ tiềm tàng.
-
Xác định những nguyên nhân mà tổ chức cho rằng đây là những nguyên nhân then chốt
nhất cho sự điều tra tiếp theo. Đồng thời, đánh dấu các nguyên nhân đó lại.
-
Làm sáng tỏ các nguyên nhân gốc rễ bằng một hoặc nhiều các cách sau:
+ Tìm các nguyên nhân mà xuất hiện lặp đi lặp lại tại các nhánh xương nguyên nhân
chính.
+ Tập hợp dữ liệu thông qua các checksheet hoặc những dạng khác để xác định mối quan
hệ thường xuyên của các nguyên nhân khác nhau.
b. Phân tích tác động và hình thức sai lỗi
Được giới thiệu vào năm 1949 bởi quân đội Mỹ để nghiên cứu vấn đề có thể phát sinh từ trục
trặc của hệ thống quân sự [13] và hiện nay được ứng dụng rộng rãi trong nhiều ngành nghề.
Khái niệm
Việc phân tích những phương thức xảy ra sai lỗi và ảnh hưởng của nó (Failure Models and
Effects Analysis – FMEA) là một hình thức để xác định và phân loại theo thứ tự ưu tiên đối với
các vấn đề tiềm tàng. Bằng cách tiến hành các hoạt động dựa vào việc công cụ FMEA, một nhà
quản lý, một đội cải tiến, hoặc người phụ trách quá trình có thể tập trung vào các kế hoạch ngăn
ngừa, giám sát và ứng phó, nơi có nhiều khả năng sự cố xảy ra.
Các lợi ích của FMEA
FMEA giúp cho nhà quản lý:
-
Xác định các hình thức sai lỗi tiềm tàng có thể xảy ra và mức độ tác động nghiêm trọng
của các lỗi này.
-
Đánh giá một cách khách quan khả năng xuất hiện các sai lỗi.
-
Phân loại các lỗi sản phẩm hay quá trình tiềm tàng có thể xảy ra.
13
-
Tập trung vào loại trừ các nguyên nhân gây ra các lỗi trọng yếu.
Đối với nhà sản xuất, FMEA thực sự là một công cụ hữu hiệu để thiết kế và cải thiện sản
phẩm và quá trình. FMEA giúp chúng ta giảm thời gian và chi phí thiết kế.
Sử dụng tiêu chuẩn RPN để tìm ra nguyên nhân nào gây ra lỗi nhiều nhất, từ đó đưa ra
phương án giải quyết các nguyên nhân đó trước.
2.2
Phương pháp luận
Phương pháp luận của luận văn được thể hiện như hình 2.3, với các bước được diễn giải cụ
thể sau đây:
Bước 1: Trình bày tổng quan về đề tài, bao gồm lý do hình thành đề tài, mục tiêu, nhiệm vụ
của đề tài này. Sau đó trình bày những lý thuyết công cụ đề cập trong luận văn.
Bước 2: Tìm hiểu hoạt động điều phối xe hiện tại của công ty, thu thập các dữ liệu liên quan:
hoạt động điều phối hiện tại của công ty, thu thập các dữ liệu về số lượng phương tiện, chi phí
thuê phương tiện, năng lực phương tiện, và các yêu cầu, ràng buộc trong giao hàng, … tìm hiểu
vấn đề, xác định những nguyên nhân có thể làm ảnh hưởng đến hiệu suất giao hàng từ đó xác
định hướng giải quyết vấn đề.
Bước 3: Tham khảo tài liệu và nghiên cứu các lý thuyết, bắt đầu xây dựng mô hình bài toán.
Mô hình hóa bài toán thực tế bằng các hàm mục tiêu và các ràng buộc.
Bước 4: Làm rõ các dữ liệu đưa vào. Sau đó trình bày cách thức giải mô hình toán, với mô
hình được xây dựng, ta áp dụng các giải thuật và phần mềm để tìm lời giải tốt nhất cho mô hình
đó như: giải thuật tiết kiệm, công cụ giải OR-Tools, phần mềm Visual Studio Code. Sau đó kiểm
tra kết quả có thỏa các yêu cầu đặt ra.
Bước 5: Một mô hình có giá trị khi thực hiện đúng chức năng, cho kết quả có nghĩa và chấp
nhận được. Sau khi mô hình đã được kiểm tra tính chính xác ở bước 4, ta so sánh với kết quả điều
phối lấy từ thực tế để từ đó đánh giá độ hiệu quả của phương pháp này so với phương pháp từ
kinh nghiệm.
14
Bước 6: Đánh giá mức độ hoàn thành mục tiêu đề tài đặt ra ban đầu. Trình bày những phương
hướng phát triển cho đề tài sau này.
Hình 2.3 Phương pháp luận
15
16
