Luận án Các phương pháp heuristics giải bài toán định vị và hướng lộ trong hậu cần đô thị

 hơn mô hình vận tải trực tiếp: tổng lợi nhuận cao hơn, tổng thời gian vận tải ít hơn và số lượng xe taxi sử dụng ít hơn.
Tổng lợi nhuận mô hình chia sẻ phương tiện cao hơn gấp 1,15 lần so với mô hình vận tải trực tiếp. Tất cả yêu cầu vận tải đều được phục vụ trong cả hai mô hình. Đặc biệt, số lượng yêu cầu vận tải thực hiện chia sẻ phương tiện chiếm 69,5% trên tổng số yêu cầu trong mô hình chia sẻ phương tiện. Điều này ảnh hưởng mạnh mẽ đến số lượng taxi sử dụng. Số lượng taxi sử dụng trong mô hình chia sẻ phương tiện giảm 0,47 lần so với mô hình trực tiếp. Vì số lượng yêu cầu chia sẻ lớn và số lượng taxi sử dụng ít hơn, tổng thời gian vận tải của mô hình chia sẻ phương tiện ít hơn 0,27 lần so với mô hình vận tải trực tiếp. 
Trong mô hình chia sẻ phương tiện, mô hình chia sẻ tĩnh có tổng lợi nhuận cao hơn mô hình chia sẻ động. Vì trong mô hình chia sẻ tĩnh, tất cả yêu cầu vận tải đều biết trước nên thuật toán có nhiều cơ hội để thực hiện chia sẻ phương tiện giữa hàng hóa hoặc với một hành khách trong cùng 1 xe taxi. Do đó, mô hình chia sẻ tĩnh sử dụng ít xe taxi hơn so với mô hình chia sẻ động. Có thể nhận xét rằng, số lượng yêu cầu vận tải hàng hóa càng nhiều thì mô hình chia sẻ tĩnh sẽ càng hiệu quả.
8 Bảng 2.8. Kết quả thực nghiệm bộ dữ liệu 1
Tiêu chí thực nghiệm
Mô hình
vận tải trực tiếp
Mô hình chia sẻ phương tiện
Mô hình
chia sẻ tĩnh
Mô hình
chia sẻ động
Tổng lợi nhuận
4.761,98
5.402,70
5.304,24
Doanh thu vận tải 
hành khách
164.348,40
164.336,42
162.325,88
Doanh thu bổ sung 
của vận tải hành khách
133,68
133,72
133,68
Doanh thu vận tải hàng hóa
211.226,88
211.206,68
211.226,88
Chi phí nhân công 
cho tài xế taxi
1253,70
934,32
944,82
Chi phí sử dụng taxi
251,50
89,33
172,17
Chi phí vận tải
338.473,20
252.242,55
255.079,92
Thời gian vận tải (giờ)
11.282,44
9.218,76
8.502,66
Số lượng hành khách vận tải
13.483
13.483
13.483
Số lượng hàng hóa vận tải
29.404
29.404
29.404
Số lượng yêu cầu vận tải 
chia sẻ phương tiện
0
29.802
29.740
Số lượng xe taxi 
tham gia vận tải
3.848
1.440
2.322
Thời gian thực thi 
thuật toán (giây)
1.594
9.784
4.613
9 Bảng 2.9. Kết quả thực nghiệm bộ dữ liệu 2
Tiêu chí thực nghiệm
Mô hình
vận tải trực tiếp
Mô hình chia sẻ phương tiện
Mô hình
chia sẻ tĩnh
Mô hình
chia sẻ động
Tổng lợi nhuận
5.019,32
5.710,87
5.601,77
Doanh thu vận tải 
hành khách
3.115,06
3.116,10
3.116,00
Doanh thu bổ sung 
của vận tải hành khách
138,10
138,10
138,10
Doanh thu vận tải hàng hóa
4.005,51
4.005,51
4.005,51
Chi phí nhân công 
cho tài xế taxi
1.523,23
972,94
990,45
Chi phí sử dụng taxi
251,50
89,33
172,17
Chi phí vận tải
662,62
486,47
495,23
Thời gian vận tải (giờ)
11.926,14
8.755,76
8.913,35
Số lượng hành khách vận tải
14.213
14.213
14.213
Số lượng hàng hóa vận tải
30.972
30.972
30.972
Số lượng yêu cầu vận tải 
chia sẻ phương tiện
0
31.622
31.362
Số lượng xe taxi 
tham gia vận tải
4.182
1.465
2.364
Thời gian thực thi 
thuật toán (giây)
1.712
10.526
5.439
10 Bảng 2.10. Kết quả thực nghiệm bộ dữ liệu 3
Tiêu chí thực nghiệm
Mô hình
vận tải trực tiếp
Mô hình chia sẻ phương tiện
Mô hình
chia sẻ tĩnh
Mô hình
chia sẻ động
Tổng lợi nhuận
4.059,70
4.772,88
4.683,51
Doanh thu vận tải 
hành khách
2.759,34
2.759,19
2.759,19
Doanh thu bổ sung của 
vận tải hành khách
81,73
81,73
81,37
Doanh thu vận tải hàng hóa
3.337,00
3.337,00
3.337,00
Chi phí nhân công 
cho tài xế taxi
1.244,59
877,14
881,50
Chi phí sử dụng taxi
251,50
89,33
172,17
Chi phí vận tải
622,29
438.57
440,75
Thời gian vận tải (giờ)
11.200,36
7.893,59
7.932,84
Số lượng hành khách vận tải
11.842
11.842
11.842
Số lượng hàng hóa vận tải
25.762
25.762
25.762
Số lượng yêu cầu vận tải 
chia sẻ phương tiện
0
25.819
25.895
Số lượng xe taxi 
tham gia vận tải
3.883
1.429
2.221
Thời gian thực thi 
thuật toán (giây)
1.357
7.915
4.108
11 Bảng 2.11. Kết quả thực nghiệm bộ dữ liệu 4
Tiêu chí thực nghiệm
Mô hình
vận tải trực tiếp
Mô hình chia sẻ phương tiện
Mô hình
chia sẻ tĩnh
Mô hình
chia sẻ động
Tổng lợi nhuận
3.073,46
3.655,42
3.565,09
Doanh thu vận tải 
hành khách
2.055,82
2.055,45
2.055,45
Doanh thu bổ sung của 
vận tải hành khách
75,98
75,98
75,98
Doanh thu vận tải hàng hóa
2.633,45
2.633,45
2.633,45
Chi phí nhân công 
cho tài xế taxi
960,18
680,08
685,08
Chi phí sử dụng taxi
251,50
89,33
172,17
Chi phí vận tải
480,09
340,04
342,54
Thời gian vận tải (giờ)
8.640,97
6.120,23
6.165,25
Số lượng hành khách vận tải
9.395
9.395
9.395
Số lượng hàng hóa vận tải
20.361
20.361
20.361
Số lượng yêu cầu vận tải 
chia sẻ phương tiện
0
20.396
20.386
Số lượng xe taxi 
tham gia vận tải
3.040
1.152
1.736
Thời gian thực thi 
thuật toán (giây)
1.218
7.142
3.705

Ngoài ra, các dữ liệu tích lũy theo các khung thời gian sẽ được biểu diễn trong các biểu đồ phân tích bao gồm: tổng lợi nhuận, thời gian vận tải và số lượng taxi bổ sung để thực hiện vận tải. Trong các biểu đồ này, đường đứt nét thể hiện kết quả của mô hình chia sẻ động, đường chấm tròn thể hiện kết quả của mô hình chia sẻ tĩnh và đường nét liền thể hiện kết quả của mô hình vận tải trực tiếp.
Hình 2.3 và hình 2.4 thể hiện biểu đồ số lượng xe taxi bổ sung theo khung thời gian để phục vụ các yêu cầu vận tải mới. Thống kê trong khoảng thời gian một ngày, số lượng xe taxi sử dụng trong mô hình vận tải trực tiếp tăng lên đáng kể theo thời gian. Theo các biểu đồ này, một số lượng xe taxi được bổ sung để phục vụ vận tải trong giờ cao điểm, đặc biệt là trong mô hình vận tải trực tiếp. Trong toàn bộ các khung thời gian, mô hình vận tải chia sẻ phương tiện sử dụng ít xe taxi hơn so với mô hình vận tải trực tiếp. Trong giờ cao điểm hoặc gần cao điểm, số lượng xe taxi tham gia vận tải trong mô hình chia sẻ tĩnh ít hơn so với mô hình chia sẻ động. Điều này cho thấy sử dụng mô hình chia sẻ tĩnh sẽ giúp giảm tắc nghẽn hiệu quả trong giờ cao điểm hoặc gần cao điểm.
Trong mô hình chia sẻ phương tiện, một số lượng lớn các yêu cầu vận tải được chia sẻ nên tổng thời gian vận tải giảm đáng kể. Điều này được thể hiện qua biểu đồ ghi nhận thời gian vận tải tích lũy hình 2.5, 2.6, 2.7 và hình 2.8.
Ngoài ra, chi tiết tổng lợi nhuận tích lũy theo từng 2 giờ của mô hình vận tải trực tiếp và mô hình vận tải chia sẻ phương tiện được thể hiện trong hình 2.9, 2.10, 2.11 và hình 2.12. Dựa vào các biểu đồ này cho thấy, tổng lợi nhuận tích lũy của mô hình chia sẻ luôn lớn hơn tổng lợi nhuận của mô hình vận tải trực tiếp. Chi tiết của tổng lợi nhuận theo khung thời gian được thể hiện trong hình 2.13, 2.14, 2.15 và hình 2.16.
Thời gian chạy thuật toán được thống kê trong bảng 2.8, 2.9, 2.10 và bảng 2.11. Thời gian chạy thuật toán chỉ ra tính khả thi của mô hình bài toán. Theo thống kê, mỗi yêu cầu vận tải được thuật toán xử lý trong thời gian trung bình 0,11 giây. Điều này cho thấy mô hình chia sẻ phương tiện có tính khả thi khi áp dụng vào thực tế. 
Hiện nay tại Việt Nam, hệ thống đặt xe và chia sẻ phương tiện được sử dụng thông dụng bao gồm: Grab, Be. Trong đó, hệ thống Grab chỉ cho phép chia sẻ phương tiện giữa hai hành khách đi cùng quãng đường thông qua dịch vụ GrabShare. Các dịch vụ này không thực hiện chia sẻ phương tiện giữa một hành khách và hàng hóa. Ngoài ra, các nhà cung cấp dịch vụ đặt xe, chia sẻ phương tiện như Grab và Be không cung cấp các dữ liệu thực tế. Trong trường hợp có những dữ liệu vận tải thực tế, mô hình bài toán có thể thực hiện thực nghiệm và đưa ra các đánh giá về hiệu năng và tính khả thi khi áp dụng thực tế. 
 (a) Bộ dữ liệu 1 (b) Bộ dữ liệu 2
 (c) Bộ dữ liệu 3 (d) Bộ dữ liệu 4
6 Hình 2.3. Số lượng taxi bổ sung theo khung thời gian để thực hiện vận tải
7 Hình 2.4. Biểu đồ thời gian vận tải tích lũy theo từng khoảng thời gian 2h của bộ dữ liệu 1
8 Hình 2.5. Biểu đồ thời gian vận tải tích lũy theo từng khoảng thời gian 2h của bộ dữ liệu 2
9 Hình 2.6. Biểu đồ thời gian vận tải tích lũy theo từng khoảng thời gian 2h của bộ dữ liệu 3
10 Hình 2.7. Biểu đồ thời gian vận tải tích lũy theo từng khoảng thời gian 2h của bộ dữ liệu 4
11 Hình 2.8. Biểu đồ lợi nhuận tích lũy theo từng khoảng thời gian 2h của bộ dữ liệu 1
12 Hình 2.9. Biểu đồ lợi nhuận tích lũy theo từng khoảng thời gian 2h của bộ dữ liệu 2
13 Hình 2.10. Biểu đồ lợi nhuận tích lũy theo từng khoảng thời gian 2h của bộ dữ liệu 3
14 Hình 2.11. Biểu đồ lợi nhuận tích lũy theo từng khoảng thời gian 2h của bộ dữ liệu 4
15 Hình 2.12. Biểu đồ lợi nhuận theo từng khoảng thời gian 2h của bộ dữ liệu 1
16 Hình 2.13. Biểu đồ lợi nhuận theo từng khoảng thời gian 2h của bộ dữ liệu 2
17 Hình 2.14. Biểu đồ lợi nhuận theo từng khoảng thời gian 2h của bộ dữ liệu 3
18 Hình 2.15. Biểu đồ lợi nhuận theo từng khoảng thời gian 2h của bộ dữ liệu 4
2.5. KẾT LUẬN CHƯƠNG
Chương này trình bày các nội dung chính sau: Thứ nhất, giới thiệu bài toán mở rộng của bài toán chia sẻ phương tiện SARP; Thứ hai, trình bày mô hình toán học biểu diễn bài toán. Thứ ba, xây dựng các thuật toán để giải quyết bài toán với mô hình vận tải trực tiếp, mô hình chia sẻ tĩnh và mô hình chia sẻ động. Thứ tư, trình bày về cách thức xây dựng dữ liệu thực nghiệm, thông số thực nghiệm từ dữ liệu taxi Tokyo-Musen và ghi nhận, phân tích kết quả thực nghiệm của mô hình chia sẻ phương tiện và mô hình vận tải trực tiếp. Kết quả thực nghiệm chứng minh tính ứng dụng của mô hình trong thực tiễn.
Kết quả chính của chương này đã được công bố tại tạp chí Data & Knowledge Engineering [3], hội thảo SOICT 2015 [1] và hội thảo KSE 2016 [2].
CHƯƠNG 3. VẤN ĐỀ ĐỊNH VỊ VÀ ĐỊNH TUYẾN TRONG BÀI TOÁN GIAO VÀ NHẬN ĐA LOẠI HÀNG HÓA, ĐA TUYẾN
Nghiên cứu mở rộng vấn đề định tuyến của mô hình hậu cần đô thị một mức được trình bày ở Chương 2, chương này trình bày vấn đề định vị và định tuyến trong hậu cần đô thị thông qua bài toán giao và nhận đa loại hàng hóa, đa tuyến. Cụ thể, vấn đề định vị và định tuyến trong hậu cần đô thị một mức được nghiên cứu thông qua bài toán giao và nhận đa loại hàng hóa, đa tuyến với khung thời gian và đồng bộ MTT-PDTWS (gọi tắt là bài toán MTT-PDTWS). Mở rộng bài toán MTT-PDTWS, vấn đề định vị và định tuyến trong hậu cần đô thị hai mức được nghiên cứu xây dựng và giải quyết bài toán giao và nhận đa loại hàng hóa, đa tuyến ở hai mức với khung thời gian và đồng bộ 2E-MTT-PDTWS (gọi tắt là bài toán 2E-MTT-PDTWS).
Phần đầu tiên của chương sẽ giới thiệu bài toán MTT-PDTWS và xây dựng bài toán 2E-MTT-PDTWS. Tiếp theo, thuật toán tìm kiếm lân cận lớn thích nghi ALNS (gọi tắt là thuật toán ALNS) được xây dựng để giải quyết bài toán MTT-PDTWS. Kết hợp thuật toán ALNS với thuật toán heuristic, luận án xây dựng thuật toán để giải quyết bài toán 2E-MTT-PDTWS. Phần cuối của chương sẽ trình bày thực nghiệm, phân tích và đánh giá hiệu quả của thuật toán.
3.1. TỔNG QUAN BÀI TOÁN GIAO VÀ NHẬN ĐA LOẠI HÀNG HÓA, ĐA TUYẾN 
Đa số các nghiên cứu về hậu cần đô thị hai mức tập trung nghiên cứu vận tải hàng hóa từ bên ngoài thành phố vào trong thành phố (hàng hóa e2c) và vận tải hàng hóa từ bên trong thành phố ra ngoài thành phố (hàng hóa c2e). Một trong các nghiên cứu về hàng hóa e2c được trình bày trong bài toán định tuyến xe đa vùng, đa tuyến phụ thuộc thời gian với khung thời gian TMZT-VRPTW. Trong bài toán TMZT-VRPTW, một đội xe tải nhỏ xuất phát từ một kho đỗ xe đến điểm trung chuyển nhận hàng và sau đó giao hàng hóa e2c đến khách hàng trong khung thời gian quy định. Các yêu cầu khách hàng trong bài toán này được chia thành các vùng theo các điểm trung chuyển. Do đó, mỗi vùng có thể được xem là một bài toán VRPTW. Tác giả Crainic và cộng sự là người đầu tiên đề xuất thuật toán heuristic dựa trên sự phân rã decomposition-based [2] và áp dụng để giải quyết bài toán trong nghiên cứu sau đó [39]. Ngoài ra, tác giả Nguyen và cộng sự đề xuất thuật toán tìm kiếm Tabu để giải quyết bài toán này trong nghiên cứu [57]. Sau đó, các tác giả tiếp tục mở rộng thuật toán tìm kiếm Tabu này để giải quyết một bài toán mới “Giao và nhận hàng hóa, đa tuyến với khung thời gian và đồng bộ MT-PDTWS” [58]. Bên cạnh thực hiện giao hàng hóa e2c tương tự bài toán TMZT-VRPTW, đội xe tải nhỏ trong bài toán MT-PDTWS cho phép nhận các hàng hóa c2e tại khách hàng và vận tải đến các điểm trung chuyển. Trong công trình [40], tác giả Crainic và cộng sự tổng quát hóa hai bài toán TMZT-VRPTW và MT-PDTWS, bằng một đề xuất cho bài toán mới “Giao và nhận đa loại hàng hóa, đa tuyến với khung thời gian và đồng bộ MTT-PDTWS”. Bài toán MTT-PDTWS nghiên cứu đồng thời ba loại hàng hóa: 
Hàng hóa e2c: hàng hóa chuyển từ ngoài thành phố vào trong thành phố;
Hàng hóa c2e: hàng chuyển từ trong thành phố ra ngoài thành phố;
Hàng hóa c2c: hàng hóa nhận từ khách hàng và giao cho khách hàng trong thành phố.
Để nghiên cứu vấn đề định vị và định tuyến ở hậu cần đô thị một mức, luận án nghiên cứu và xây dựng thuật toán ALNS để giải quyết bài toán MTT-PDTWS. Mở rộng bài toán MTT-PDTWS cho mô hình hậu cần đô thị hai mức, luận án xây dựng bài toán mới “Giao và nhận đa loại hàng hóa, đa tuyến ở hai mức với khung thời gian và đồng bộ”.
3.2. BÀI TOÁN GIAO VÀ NHẬN ĐA LOẠI HÀNG HÓA, ĐA TUYẾN VỚI KHUNG THỜI GIAN VÀ ĐỒNG BỘ
3.2.1. Phát biểu bài toán
Bài toán MTT-PDTWS sử dụng một đội xe tải nhỏ để vận tải các loại hàng hóa. Mỗi xe tải nhỏ có trọng tải Q, xuất phát từ một kho đỗ xe g và thực hiện các lộ trình giao và nhận hàng hóa với các loại hàng hóa khác nhau: hàng hóa e2c, hàng hóa c2e và hàng hóa c2c. Tính chất phụ thuộc thời gian của bài toán được mô hình hóa thông qua tính chất của yêu cầu vận tải và các khung thời gian giao và nhận hàng hóa.
Đối với loại hàng hóa e2c, hàng hóa sẽ được tập trung tại điểm trung chuyển và được xe tải nhỏ đến nhận và giao đến khách hàng. Ngược lại, xe tải nhỏ sẽ nhận các hàng hóa c2e từ khách hàng và chuyển đến các điểm trung chuyển. Trong mô hình bài toán MTT-PDTWS, mỗi điểm trung chuyển s∈S được quy định:
Xe tải nhỏ không được phép chờ tại điểm trung chuyển;
Khung thời gian hoạt động [ts-η,ts]: quy định thời điểm sớm nhất và trễ nhất cho phép xe tải nhỏ đến điểm trung chuyển. Trong trường hợp xe tải nhỏ đến trước thời điểm ts-η, xe tải nhỏ có thể đỗ tạm thời tại một trạm chờ w∈W trước khi di chuyển đến điểm trung chuyển s. Xe tải nhỏ không được phép đến điểm trung chuyển s sau thời điểm ts.
Một khách hàng có thể yêu cầu các dịch vụ vận tải hàng hóa khác nhau:
Nhận hàng hóa e2c từ các điểm trung chuyển tại các khung thời gian khác nhau;
Giao hàng hóa c2e đến một trong các điểm trung chuyển đăng ký trước;
Nhận và giao hàng hóa c2c đến khách hàng khác. 
Mỗi khách hàng được phép yêu cầu một hoặc nhiều dịch vụ vận tải hàng hóa nêu trên. Để đơn giản khi mô hình hóa, mỗi yêu cầu dịch vụ vận tải hàng hóa cụ thể nêu trên được xem là một yêu cầu vận tải hàng hóa của bài toán.
Các yêu cầu giao hàng hóa e2c được biểu diễn bởi tập hợp CD. Mỗi yêu cầu d∈CD bao gồm các các thông tin: 
Thông tin khách hàng nhận hàng và khung thời gian cho phép nhận hàng;
Điểm trung chuyển tập trung hàng hóa e2c tương ứng.
Tương tự, tập hợp CP là tập hợp của các yêu cầu nhận hàng hóa c2e từ khách hàng và chuyển đến điểm trung chuyển. Mỗi yêu cầu nhận hàng hóa c2e, p∈CP, bao gồm các thông tin: 
Thông tin khách hàng để lấy hàng và khung thời gian cho phép lấy hàng;
Danh sách các điểm trung chuyển (Sp) được phép chuyển hàng đến sau khi lấy hàng. 
Đối với hàng hóa c2e, việc lựa chọn một điểm trung chuyển thích hợp trong danh sách điểm trung chuyển đăng ký trước là một quyết định của bài toán. 
Ngoài ra, yêu cầu nhận và giao hàng hóa c2c được biểu diễn bởi tập hợp (p,q)∈R . Trong đó, tập hợp các yêu cầu nhận hàng hóa c2c, p∈Cc2cp, và yêu cầu giao hàng hóa c2c, q∈Cc2cq. Tổng quát, mỗi yêu cầu vận tải của khách hàng i∈{CD∪CP∪Cc2cP∪Cc2cD} sẽ được đại diện bởi bộ thông tin (i,qi,δi,[ei,li]) với:
qi>0: số lượng hàng hóa yêu cầu nhận hoặc yêu cầu giao. Với (p,q)∈R thì qp=-qd;
[ei,li]: khung thời gian cho phép nhận hoặc giao hàng;
δi: thời gian thực hiện nhận hoặc lấy hàng hóa.
Có thể thấy rằng, mỗi điểm trung chuyển s có thể phục vụ một số lượng hàng hóa chuyển ra ngoài thành phố CsP∈CP hoặc chuyển vào thành phố CsD∈CD hoặc cả hai. Tại mỗi điểm trung chuyển s, khoảng thời gian tương ứng để bốc và dỡ hàng hóa của một xe tải nhỏ là ∅(s) và ∅'(s). Để đơn giản hóa, thời gian bốc và dỡ hàng này không phụ thuộc vào số lượng hàng.
Để thuận tiện cho việc phát biểu bài toán, các định nghĩa sau được sử dụng:
Một lộ trình c2c: là một lộ trình của một xe tải nhỏ nhận và giao hàng hóa c2c theo trình tự vào sau ra trước (LIFO). Tức là, hàng hóa c2c nào mà xe tải nhận sau thì sẽ được xe tải thực hiện giao trước, nhờ đó lái xe không cần phải dỡ các hàng hóa c2c khác ra khỏi xe tải tại điểm giao hàng;
Một lộ trình c2e: là một lộ trình của một xe tải nhỏ nhận hàng hóa c2e từ các khách hàng và chuyển đến một điểm trung chuyển được phép;
Một lộ trình e2c: là một lộ trình của một xe tải nhỏ lấy hàng hóa e2c từ một điểm trung chuyển và giao hàng cho các khách hàng;
Một hành trình của một xe tải nhỏ: là các lộ trình được ghép nối từ các lộ trình c2e, lộ trình e2c và lộ trình c2c theo thứ tự bất kỳ, với điểm bắt đầu và kết thúc hành trình tại kho đỗ xe g. Hành trình của một xe tải nhỏ tuân thủ chiến lược Pseudo-Backhaul [79], tức là xe tải nhỏ phải hoàn thành lộ trình vận tải đang thực hiện trước khi bắt đầu thực hiện lộ trình vận tải tiếp theo.
Hình 3.1 minh họa tất cả các trường hợp bốc và dỡ hàng có thể xảy ra của xe tải nhỏ tại điểm trung chuyển s với đường nét đứt thể hiện xe tải nhỏ không tải. Hình 3.1a và 3.1b miêu tả trường hợp một xe tải nhỏ chỉ thực hiện dỡ hàng hóa c2e tại điểm trung chuyển và rời đi không tải. Điểm khác nhau giữa hai trường hợp trong hình này là trước khi đến điểm trung chuyển, xe tải nhỏ trong hình 1b chờ tại trạm chờ w1 để có thể đến điểm trung chuyển s trong khung thời gian hoạt động [ts-η,ts]. Hình 3.1c minh họa trường họa một xe tải nhỏ không tải đến điểm trung chuyển s. Sau đó, thực hiện bốc hàng hóa e2c và thực hiện lộ trình giao hàng hóa e2c ngay sau khi rời điểm trung chuyển. Hình 3.1d và 3.1e minh họa trường hợp xe tải nhỏ thực hiện tuần tự cả hai quá trình: dỡ hàng hóa c2e và bốc hàng hóa e2c tại điểm trung chuyển s. Trong trường hợp này, xe tải nhỏ phải hoàn thành quá trình dỡ hàng hóa c2e trước khi tiến hành bốc hàng hóa e2c.
19 Hình 3.1. Minh họa các hoạt động của xe tải nhỏ tại điểm trung chuyển
Hình 3.2 minh họa một hành trình của một xe tải nhỏ xuất phát và kết thúc tại kho đỗ xe g. Hành trình này gồm 6 lộ trình qua 3 điểm trung chuyển s1,s2,s3 và trạm chờ w1. Cs1D=d1,d2,,d5, Cs2P=p1,p2,,p5, Cs2D=d6,d7,,d11, Cs3P={p6,p7,,p10} và Cs3D={d12,d13,,d15} là tập hợp các yêu cầu chuyển hàng hóa vào hoặc chuyển hàng ra thành phố. Các yêu cầu nhận và giao hàng hóa trong thành phố (p1,d1), (p2,d2), (p3,d3), (p4,d4), (p5,d5)∈R với yêu cầu nhận hàng hóa c2c trong thành phố p1,,p5∈Cc2cP và yêu cầu giao hàng tương ứng d1,,d5∈Cc2cD. Đường nét đứt minh họa xe không tải. Hành trình vận tải của xe tải nhỏ bao gồm 6 lộ trình {r1,r2,,r6} với r1={s1,d1,d3,d4} và r2=s2,d6,d7,d9,d8 là các lộ trình e2c; r3=p1,p3,p4,w1,s2 và r4=p6,p8,p7,s3 là các lộ trình c2e; r5=p4,p3,d3,p5,d5,d4 và r6=p1,p2,d2,d1 là các lộ trình c2c. Xe tải nhỏ xuất phát không tải từ kho đỗ xe g và di chuyển đến điểm trung chuyển s1 để bốc hàng hóa. Sau khoảng thời gian bốc hàng ∅(s1), xe tải nhỏ rời điểm trung chuyển s1 để bắt đầu giao hàng hóa d1,d3,d4∈Cs1D và tiếp tục di chuyển không tải để nhận hàng hóa p1,p3,p4∈Cs2P. Sau khi nhận hàng hóa p4, xe tải nhỏ di chuyển đến và chờ tại trạm chờ w1 để có thể di chuyển đến điểm trung chuyển s2 trong khung thời gian hoạt động [ts2-η,ts2]. Giả sử xe tải nhỏ đến điểm trung chuyển s2 tại thời điểm t thì sẽ hoàn thành việc dỡ hàng tại thời điểm t+∅'(s2), và rời khỏi điểm trung chuyển tại thời điểm t+∅'s2+∅(s2) sau khi bốc hàng hóa (d6,d7,d9,d8)∈Cs2D trong khoảng thời gian ∅(s2). Sau khi giao hàng d8, xe thực hiện các yêu cầu giao nhận trong thành phố p3,d3,p4,d4,p5,d5 theo nguyên tắc LIFO với thứ tự giao nhận hàng p4,p3,d3,p5,d5,d4. Sau đó, xe tải nhỏ di chuyển không tải để nhận các hàng hóa p6,p8,p7∈Cs3P trước khi đến điểm trung chuyển s3. Tại điểm trung chuyển s3, quá trình dỡ hàng sẽ thực hiện trong khoảng t