BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƢỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
---------------------------------------

HÀ TRỌNG SỸ

BÀI TOÁN ĐỊNH TUYẾN
CHO MẠNG PHƢƠNG TIỆN GIAO THƠNG

LUẬN VĂN THẠC SĨ KHOA HỌC
TỐN HỌC

Hà Nội – 2016


BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƢỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
---------------------------------------

HÀ TRỌNG SỸ

BÀI TOÁN ĐỊNH TUYẾN
CHO MẠNG PHƢƠNG TIỆN GIAO THƠNG

Chun ngành : Cơ sở tốn cho tin học

LUẬN VĂN THẠC SĨ KHOA HỌC
TOÁN HỌC

NGƢỜI HƢỚNG DẪN KHOA HỌC:
TS. TẠ ANH SƠN

Hà Nội – 2016


Mục lục
Lời cam đoan

3

Danh mục các kí hiệu, chữ viết tắt

4

Danh sách các bảng

5

Danh sách các hình vẽ

6

Mở đầu

7

1 Bài
1.1
1.2
1.3


tốn giao vận thơng qua nhiều trạm
Mơ tả bài tốn . . . . . . . . . . . . . . . . . . .
Mơ hình tốn học . . . . . . . . . . . . . . . . . .
Phương pháp giải . . . . . . . . . . . . . . . . . .
1.3.1 Thuật giải chính xác - Exact algorithm . .
1.3.2 Thuật giải gần đúng - Heuristic algorithm

2 Thuật giải cho bài toán MDPDPT
2.1 Thuật toán Tabu Search . . . . . . . . . . . . . .
2.1.1 Cấu trúc tổng quát . . . . . . . . . . . . .
2.1.2 Khởi tạo . . . . . . . . . . . . . . . . . . .
2.1.3 Phương án lân cận - Neighborhood . . . .
2.1.4 Tabu list . . . . . . . . . . . . . . . . . . .
2.2 Thuật toán DCA-CUT . . . . . . . . . . . . . . .
2.2.1 Thuật toán DCA . . . . . . . . . . . . . .
2.2.2 Thuật toán DCA-CUT giải bài toán MIP .
3 Kết quả thử nghiệm
3.1 Dữ liệu . . . . . . . . . . . . . .
3.2 Kết quả . . . . . . . . . . . . .
3.2.1 Thuật toán Tabu Search
3.2.2 Thuật toán DCA-CUT .
1

.
.
.
.

.
.

.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.

.
.

.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.


.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.

14
14
17
22
22
23

.
.
.
.
.
.
.
.

24

24
25
27
29
30
31
31
33

.
.
.
.

38
38
40
40
42


Kết luận

44

2


Lời cam đoan
Tôi xin cam đoan Luận văn thạc sĩ "Bài tốn định tuyến trong mạng

phương tiện giao thơng" là cơng trình nghiên cứu của riêng tơi. Các số
liệu, kết quả nêu trong Luận văn là trung thực và chưa từng được ai
cơng bố trong bất kỳ cơng trình nào khác. Tôi xin cam đoan rằng mọi sự
giúp đỡ cho việc thực hiện Luận văn này đã được cảm ơn và các thơng
tin trích dẫn trong Luận văn đã được chú thích nguồn gốc rõ ràng, minh
bạch.
Tơi xin hồn tồn chịu trách nhiệm về lời cam đoan trên.
Học viên thực hiện Luận văn
Hà Trọng Sỹ

3


Danh mục các kí hiệu, chữ viết tắt
VRP

Vehicle Routing Problem - bài toán định
tuyến xe

MDPDPT

Multi-depot Pickup and Delivery problem
with Transfering - bài tốn giao vận qua
nhiều trạm, có trung chuyển

B&B

Branch and Bound - thuật toán nhánh cận

B&P


Branch and Price

B&C

Branch and Cut

TS

thuật tốn tìm kiếm Tabu

depot

trạm giao nhận

neighborhood

phương án lân cận

move

bước di chuyển

|N |

số phần tử của tập hợp N

MIP

Mixed Integer Problem - bài toán quy

hoạch nguyên hỗn hợp

4


Danh sách bảng
3.1

Dữ liệu thử nghiệm . . . . . . . . . . . . . . . . . . . . .

40

3.2

Kết quả thử nghiệm Tabu Search . . . . . . . . . . . . .

41

3.3

Kết quả thử nghiệm DCA-CUT . . . . . . . . . . . . . .

43

5


Danh sách hình vẽ
1.1


Ví dụ bài tốn MDPDPT . . . . . . . . . . . . . . . . .

15

1.2

Luồng hàng trong MDPDPT . . . . . . . . . . . . . . . .

16

1.3

Tuyến xe trong MDPDPT . . . . . . . . . . . . . . . . .

17

2.1

Bài toán MDPDPT với 5 đơn hàng, 2 trạm . . . . . . . .

28

2.2

Phương án khởi tạo ban đầu . . . . . . . . . . . . . . . .

28

2.3


Di chuyển đỉnh sang tuyến khác (move) . . . . . . . . . .

29

3.1

Bài toán MDPDPT với c = 20, d = 3 . . . . . . . . . . .

39

3.2

Bài toán MDPDPT với c = 20, d = 3 . . . . . . . . . . .

39

3.3

Nghiệm bài toán MDPDPT với c = 20, d = 3 từ thuật
toán TS . . . . . . . . . . . . . . . . . . . . . . . . . . .

42

6


Mở đầu
Lý do chọn đề tài
Ngày nay, bài toán vận tải đóng vai trị vơ cùng quan trọng trong
cuộc sống hàng ngày của chúng ta. Đối với các nước phát triển như Mỹ

và Nhật, các ngành liên quan đến vận tải hàng hóa và dịch vụ có thể
đóng góp khoảng 10% GDP. Đối với những nước kém phát triển thì tỷ lệ
này có thể hơn 30%. Ở Việt Nam, các dịch vụ liên quan vận tải, logistic
có quy mơ khoảng 20 tỷ USD/năm, chiếm khoảng 20% GDP. Trong đó
khâu quan trọng nhất là vận tải, logistic chiếm khoảng 40% chi phí. Từ
đó, việc tiết kiệm chi phí vận tải, thậm chí chỉ một vài phần trăm, cũng
trở nên vơ cùng quan trọng. Bên cạnh đó, cùng với sự phát triển của giao
thơng vận tải, lượng khí thải cũng gia tăng nhanh chóng gây ảnh hưởng
tiêu cực đến mơi trường cũng như khí hậu tồn cầu. Bởi vậy, nghiên
cứu về bài tốn định tuyến (VRP - Vehicle Routing Problem) nói chung
khơng chỉ giúp giảm chi phí vận tải, mà cịn đóng góp vào việc bảo vệ
mơi trường.
Trong thời đại cơng nghệ thông tin hiện nay, một trong những nghành
phát triển nhanh nhất đồng thời mang lại lợi nhuận khổng lồ là thương
mại điện tử. Người tiêu dùng ngày nay có thể đặt mua hàng ngay từ
chiếc máy tính, điện thoại của mình, sau đó hàng sẽ được giao tới tận
nơi ở trong một khoảng thời gian hẹn trước. Các công ty trong lĩnh vực
thương mại điện tử phần lớn có chiến lược vận chuyển hàng hóa từ nhà
cung cấp tới khách hàng thông qua các trạm hay trung tâm giao vận.
Họ không lưu trữ một lượng hàng sẵn của các nhà cung cấp trong kho,
chỉ khi nào phát sinh đơn hàng từ khách hàng thì họ mới lấy hàng từ
nhà cung cấp về kho hoặc trạm của họ trước khi giao khách hàng, điều
7


này giúp giảm phần lớn chi phí kho bãi cho cơng ty. Do đó cơng việc
vận chuyển hàng hóa tới tay khách hàng cũng là công việc quan trọng
nhất trong ngành thương mại điện tử. Việc xây dựng một mô hình vận
tải hợp lý và tối ưu hóa chi phí vận chuyển ảnh hưởng rất lớn đến lợi
nhuận của công ty. Một trong những mơ hình hiện đang được áp dụng

tại nhiều công ty thương mại điện tử ở Việt Nam được mơ tả trong luận
văn này.
Mơ hình vận tải được xem xét ở đây là một dạng cụ thể của bài
toán định tuyến, thuộc lớp các bài toán lấy và giao hàng - Pickup and
Delivery Problem (PDP). Nhìn chung, yêu cầu cơ bản trong lớp các bài
toán này là: có một tập các đơn hàng cần được xử lý bằng cách vận
chuyển hàng từ nhà cung cấp đến khách hàng. Mục tiêu của bài tốn
là tìm tuyến đường tối ưu cho từng xe để đi lấy hàng hoặc giao hàng
sao cho vừa thỏa mãn các ràng buộc về khoảng cách, thời gian hay tải
trọng, vừa tối ưu được chi phí vận hành. Mơ hình ta quan tâm đến ở
đây được mơ tả và có các u cầu cụ thể như sau:
• Bài tốn thiết lập trên một vùng lãnh thổ, khách hàng và nhà cung
cấp đều thuộc trong lãnh thổ này.
• Có N đơn hàng cần xử lý, mỗi đơn hàng cần được xử lý vận chuyển
từ nhà cung cấp (nơi bán) đến khách hàng.
• Có S trung tâm xử lý đơn hàng được thiết lập sẵn, ta gọi là trạm
giao nhận (depot). Đơn hàng luôn được thông qua trạm giao nhận
trước khi đến tay khách hàng.
• Mỗi trạm có một số lượng xe phục vụ cơng việc lấy hàng và giao
hàng.
• Mỗi nhà cung cấp hoặc khách hàng sẽ được trạm giao nhận gần
nhất phụ trách, tức là công việc lấy hàng hoặc giao hàng sẽ do xe
xuất phát từ trạm đó đến xử lý.
• Nếu trong một đơn hàng, nhà cung cấp và khách hàng do hai trạm
khác nhau phụ trách, thì đơn hàng sẽ được trung chuyển từ trạm
phụ trách lấy hàng sang trạm phụ trách giao hàng.
Bài tốn tối ưu tuyến xe cho mơ hình này được gọi là Bài toán giao
8



vận thông qua nhiều trạm - Multi-depots Pickup and Delivery Problem
with Transferring (MDPDPT). Tổng qt, bài tốn MDPDPT mơ tả
như sau:
1. Đầu vào:
• Vị trí tọa độ của N cặp nhà cung cấp - khách hàng, S trạm
giao nhận.
• Ma trận chi phí đi lại giữa các điểm ở trên.
• Danh sách số lượng hàng hóa mỗi khách hàng yêu cầu.
2. Đầu ra: Tập các tuyến xe, lộ trình của từng tuyến xe đi qua lần lượt
những điểm nào, xử lý những đơn hàng nào.
Bài toán này là một bài tốn tối ưu tổ hợp thuộc lớp các bài tốn
NP-khó. Một số thuật tốn có thể tìm chính xác nghiệm tối ưu của bài
toán này. Tuy nhiên chúng chỉ hạn chế cho bài tốn kích thước nhỏ vì
thời gian chạy thuật toán thường rất lớn. Trong thực tế, ta thường phải
xử lý hàng trăm hoặc thậm chí tới hàng nghìn đơn hàng, nên các thuật
tốn giải chính xác thường khó thể áp dụng được. Trong khi đó, các
thuật tốn heuristic có thể cung cấp một lời giải gần với nghiệm tối
ưu với thời gian chạy chấp nhận được. Những năm gần đây, các thuật
toán heuristic đã được áp dụng thành cơng vào rất nhiều bài tốn định
tuyến với quy mơ lớn trong thực tế. Trong đó, thuật tốn Tabu Search
dần được đề cử là thuật toán tốt nhất giải các bài tốn VRP nói chung.
Trong luận văn này, thuật tốn Tabu Search được áp dụng và chỉnh sửa
cho phù hợp với bài tốn MDPDPT và hi vọng có thể áp dụng kết quả
vào thực tế.
Bên cạnh đó, thuật tốn DCA-CUT ([1]) sẽ được áp dụng để cải
thiện kết quả thu được từ thuật toán Tabu Search. Thuật toán này đã
được thử nghiệm trên bài toán quy hoạch nguyên hỗn hợp 0 - 1 (MIP)
và cho kết quả khả quan. Trong luận văn này, bài tốn MDPDPT sẽ
được mơ hình hóa dưới dạng một bài tốn MIP, từ đó ta có thể dễ dàng
áp dụng thuật toán DCA-CUT.


9


Lịch sử nghiên cứu
Bài toán MDPDPT được giới thiệu trong đề tài này là một biến thể
mới trong bài toán định tuyến và thuộc lớp các bài toán lấy và giao
hàng (Pickup and Delivery Problem - PDP). Bài toán MDPDPT xem
xét việc giao nhận hàng thông qua nhiều trạm (multi-depot), mỗi món
hàng cần đi qua trạm trước khi được giao (cross-docking), có sự trung
chuyển hàng giữa các trạm và đồng thời cân nhắc đến khung thời gian
giao nhận (time windows).
Đã có rất nhiều những nghiên cứu trên các biến thể khác nhau của
bài toán PDP từ khoảng ba thập kỷ trở lại đây. Dựa trên phương thức
phục vụ khách hàng, Paragh et al. (2008a,b) đã chia các bài toán dạng
này thành hai lớp con: lớp đầu tiên là các bài tốn vận chuyển hàng hóa
từ điểm lấy đến trạm và từ trạm đến khách hàng, trong khi đó lớp thứ
2 gồm cái bài tốn vận chuyển hàng hóa trực tiếp từ điểm lấy đến điểm
giao. Đặc điểm chung của các bài tốn dạng này là giai đoạn lấy hàng
ln phải thực hiện trước khi bắt đầu thực hiện giao hàng. Bài toán
MDPDPT được xét đến trong luận văn này thuộc về lớp con thứ nhất.
Bài tốn có độ tương quan gần nhất với bài toán MDPDPT được xét
đến ở đây là bài toán lấy và giao hàng qua trạm (Pickup and Delivery
Problem with Cross-Docking - PDPCD ). Bài toán PDPCD tổng quát
miêu tả việc vận chuyển hàng hóa từ một tập các nhà cung cấp đến một
tập các khách hàng tương ứng thơng qua một trạm (cross-dock). Trong
bài tốn này, hàng hóa sẽ được lấy về trạm qua một tập các phương tiện,
được sắp xếp và phân phối lại tại trạm, tiếp tục đi giao cho khách hàng
ngay lập tức bằng các phương tiện đó. Những năm gần đây cũng đã có
nhiều nghiên cứu trên các mơ hình cụ thể được đưa ra. Thơng kê gần

đây có các nghiên cứu: Sung and Song (2003), Gumus and Bookbinder
(2004), Lim et al. (2005), Chen et al. (2006), Lee et al. (2006), Wen et al.
(2008), Liao et al. (2010), Miao et al. (2010), Musa et al. (2010), Soltani
and Sadjadi (2010), Ma et al. (2011). Trong số đó, bài tốn được xét đến
trong Lee et al. (2006), Wen et al. (2008) và Liao et al. (2010) có mơ
hình tương quan nhất với bài tốn của chúng ta, mỗi phương tiện thực
hiện việc lấy hàng và giao hàng theo từng giai đoạn riêng rẽ.

10


Trong Lee et al. (2006), Lee, Jung and Lee đã giải bài toán với thiết
lập một trạm cross-dock duy nhất, nhiều nhà cung cấp và nhiều khách
hàng, thời gian phục vụ được xét đến ràng buộc cho khách hàng. Mỗi
phương tiện được sử dụng cho việc lấy hàng và giao hàng một cách riêng
rẽ. Các tác giả đã mơ hình bài toán dưới dạng một bài toán quy hoạch
nguyên hỗn hợp (mixed integer programming - MIP) và đề xuất một
thuật toán gần đúng dựa trên thuật toán tabu search.
Wen et al. (2008) cũng đã phát triển một mơ hình quy hoạch nguyên
hỗn hợp để giải bài toán VRP với cross-docking và thời gian phục vụ tại
các điểm được ràng buộc. Mục tiêu bài toán là giảm thiểu tổng thời gian
di chuyển của các phương tiện. Các tác giả đã giải bài toán bằng thuật
toán tabu search kết hợp với một thủ tục được gọi là adaptive memory
procedure (AMP). Trong thủ tục AMP, tập các tuyến xe đã được thực
hiện bởi các xe được lưu trữ lại trong bộ nhớ (adaptive memory) và khởi
tạo một lời giải ban đầu bằng cách kết hợp các tuyến xe. Trong thủ tục
tìm kiếm lân cận neighborhood search, các tác giả đã đề xuất hai cách
tiếp cận: small neighborhood search và large neighborhood search. Thuật
toán tabu search đã được các tác giả cải tiến bằng cách kết hợp hai cách
tìm kiếm lân cận ở trên để đạt được kết quả tốt hơn. Luận văn này cũng

sẽ áp dụng thuật toán kết hợp trên cho bài toán MDPDPT.
Liao et al. (2010) đã mở rộng kết quả của Lee et al. (2006) và cũng
đề xuất thuật toán dựa trên tabu search, với mục tiêu giảm thời gian
thực thi và giảm số lượng xe được sử dụng. Các tác giả đã trình bày kết
quả với hiệu suất được cải tiến hơn so với Lee et al. (2006), với cùng
tham số đầu vào và so sánh thời gian thực thi.

Mục đích nghiên cứu
Mục đích của Luận văn là mơ hình hóa cho một bài tốn giao vận
thực tế, tìm cách áp dụng giải thuật Tabu Search và thuật toán DCACUT để tìm lời giải cho bài tốn. Đánh giá kết quả đạt được và khả năng
áp dụng vào thực tế để giảm chi phí vận hành cho các cơng ty đang sử
dụng mơ hình giao vận này.

11


Đối tượng và phạm vi nghiên cứu
• Nghiên cứu mơ hình giao vận thơng qua nhiều trạm, có sự trung
chuyển hàng hóa giữa các trạm.
• Tìm hiểu giải thuật Tabu Search, nghiên cứu cách triển khai cho bài
tốn MDPDPT.
• Ứng dụng thuật toán DCA-CUT vào giải bài toán MDPDPT và cải
thiện kết quả thu được từ Tabu Search.
• Đánh giá kết quả thuật toán trên các bộ dữ liệu trong khoảng 200
điểm, tương ứng 100 cặp nhà cung cấp - khách hàng.

Các kết quả chính của luận văn
Luận văn trình bài các kết quả chính sau:
• Đề xuất mơ hình toán học cho bài toán MDPDPT dưới dạng một
bài toán MIP.

• Áp dụng thuật tốn Tabu Search được đề xuất bởi Min Wen (2009)
([9]) cho bài toán MDPDPT. Kết quả thử nghiệm thu được trên các
bộ dữ liệu kích thước trong khoảng 200 điểm, tương ứng 100 cặp
nhà cung cấp - khách hàng, cho thấy tính khả thi của thuật tốn
nếu áp dụng vào thực tế.
• Thuật tốn DCA-CUT cũng được trình bày và áp dụng cho bài
tốn MDPDPT. Thuật tốn DCA-CUT giải bài tốn MIP đã được
trình bày trong báo cáo "Solving Relaxation Orienteering Problem
using DCA-CUT" tại hội nghị MCO 2015 (Conference on Modelling, Computation and Optimization in Information Systems and
Management Sciences) [1]. Trong báo cáo trên, thuật toán DCACUT đã được áp dụng cho bài toán "Orienteering Problem", đây
cũng là một dạng của bài toán định tuyến, thuật toán đã cho thấy
sự hiệu quả bước đầu của thuật toán. Trong luận văn này, thuật
toán DCA-CUT được áp dụng với điểm xuất phát là lời giải lấy từ

12


kết quả chạy thuật toán Tabu Search. Kết quả cho thấy DCA-CUT
đã cải thiện được lời giải, cho ta kết quả tốt hơn.
Luận văn được trình bày theo bố cục sau: Chương 1 mơ tả bài tốn
MDPDPT và trình bày mơ hình tốn học của bài tốn này dưới dạng
một bài tốn MIP. Chương 2 trình bày hai thuật giải được áp dụng cho
bài toán này: thuật toán Tabu Search và thuật tốn DCA-CUT. Chương
3 trình bày các kết quả thử nghiệm và đánh giá khả năng áp dụng thực
tế của thuật tốn.

Phương pháp nghiên cứu
• Nghiên cứu tài liệu khoa học về các bài tốn VRP, các mơ hình tốn
học.
• Nghiên cứu tổng quan về các thuật giải đã được áp dụng cho các

bài tốn VRP.
• Nghiên cứu lý thuyết và cách áp dụng thuật tốn Tabu Search.
• Nghiên cứu thuật toán DCA-CUT và áp dụng cho bài toán MDPDPT.

13


Chương 1

Bài tốn giao vận thơng qua nhiều
trạm
Trong chương này, bài tốn MDPDPT sẽ được mơ hình hóa thành
một bài toán quy hoạch nguyên hỗn hợp (MIP). Cách thức xây dựng mơ
hình tốn học cho bài tốn này được tham khảo từ các bài tốn VRP
with Cross-Docking có mơ hình gần tương tự trong Wen et al. (2008) và
từ tài liệu [9], sau đó bổ sung thêm các biến và ràng buộc cho phù hợp
với bài tốn.

1.1

Mơ tả bài tốn

Bài tốn MDPDPT dựa trên mơ hình giao vận nhằm vận chuyển
hàng hóa từ một tập các nhà cung cấp đến các khách hàng tương ứng
thông qua một tập các trạm giao nhận trên một vùng cụ thể. Mỗi một
đơn hàng được định nghĩa là một yêu cầu mua hàng từ một nhà cung
cấp đến một khách hàng, khách hàng có thể mua nhiều đơn hàng khác
nhau. Vùng được chia thành các khu vực riêng rẽ, mỗi khu vực được
thiết lập một trạm giao nhận, trạm này sẽ phụ trách tất cả các địa điểm
trong khu vực của nó, bao gồm việc lấy hàng từ nhà cung cấp và giao

hàng tới khách hàng trong khu vực. Với mỗi một đơn hàng như vậy, gói
hàng tương ứng sẽ được lấy hàng bởi trạm giao nhận gần nhất và được
giao bởi trạm giao nhận trong khu vực mà khách hàng ở. Nếu trạm lấy
14


Hình 1.1: Ví dụ bài tốn MDPDPT

hàng và trạm giao hàng khác khu vực, gói hàng sẽ được trung chuyển từ
trạm lấy đến trạm giao trước khi được trạm giao mang đi giao.
Một ví dụ nhỏ của bài tốn MDPDPT được minh họa như trong
hình 1.1. Trong ví dụ này, ta xét 5 yêu cầu mua hàng, tập các đỉnh {1,
..., 5} biểu diễn cho các nhà cung cấp hay là nơi cung cấp hàng, và các
đỉnh {1’, ..., 5’} đại diện cho các khách hàng tương ứng. Mười đỉnh này
chia ra thuộc 3 khu vực khác nhau và do 3 trạm tương ứng phụ trách
việc lấy hàng và giao hàng.
Hình 1.2 minh họa đường đi của 2 luồng hàng cơ bản: cùng trạm và
khác trạm. Trong luồng hàng cùng trạm, ví dụ ở đây là đơn hàng số 1,
hàng được xe của trạm H1 lấy về rồi sau đó được giao luôn cho khách
hàng. Trong luồng khác trạm, đơn hàng số 2 như trong hình, hàng được
trạm H1 lấy về, trung chuyển đến trạm H2 và được trạm H2 đi giao.
Mơ hình giao vận trên có các điều kiện ràng buộc như sau:
• Mỗi một xe và một tuyến tương ứng chỉ phục vụ 1 trong 3 việc sau:
lấy hàng từ các nhà cung cấp, trung chuyển hàng giữa các trạm,
15


Hình 1.2: Luồng hàng trong MDPDPT

hoặc đi giao hàng cho một trạm cụ thể.

• Mỗi một xe và một tuyến tương ứng đều xuất phát và kết thúc tại
cùng một trạm.
• Mỗi đỉnh phải có duy nhất một xe đi đến và phục vụ (lấy hàng hoặc
giao hàng).
• Xe vận chuyển đơn hàng của một trạm sẽ mang hàng từ trạm nó
phụ trách đến trạm đích của các đơn hàng, đồng thời tại đó lấy về
các đơn hàng mà có trạm đích là trạm mà xe xuất phát.
• Mỗi xe khơng được mang lượng hàng q sức chứa của nó.
• Mỗi đơn hàng được lấy hàng về trạm cần có một khoảng thời gian
tối thiểu cố định trước lưu lại để làm các thủ tục nghiệp vụ trong
trạm.
Hình 1.3 mơ tả một phương án phân tuyến theo yêu cầu trên phục
vụ cho 3 đơn hàng đầu tiên. Tuyến v1 thực hiện việc lấy hàng từ các
nhà cung cấp 1 và 2, tuyến v2 lấy hàng từ nhà cung cấp 3. Tuyến v3
thực hiện trung chuyển hàng cho đơn hàng số 3 và đơn hàng số 2 về
16


Hình 1.3: Tuyến xe trong MDPDPT

đúng trạm đích của nó. Tuyến v4, v5 và v6 thực hiện đi giao hàng cho
các khách hàng {2’, 3’, 1’}.

1.2

Mơ hình tốn học

Biểu diễn tập các điểm lấy hàng hay các nhà cung cấp là P =
{1, ..., n} và tập các điểm giao hàng hay các khách hàng là D = {n +
1, ..., 2n}. Các trạm giao nhận được biểu diễn bởi tập các điểm H =

{2n + 1, ..., 2n + m}. Định nghĩa N = P ∪ H ∪ D.
Mỗi yêu cầu mua hàng i được biểu diễn bởi một bộ (i, i + n, hi , hi+n ),
trong đó i ∈ P và i+n ∈ D, hi ∈ H là trạm gần điểm i nhất và hi+n ∈ H
là trạm gần điểm i + n nhất, hi và hi+n có thể trùng nhau. Gọi K là tập
các phương tiện vận chuyển. Kí hiệu P ∗ = {i ∈ P : hi = hi+n } là tập
các đơn hàng cần trung chuyển, trạm lấy khác trạm giao.
Gọi E là tập các cạnh khả dụng (có thể đi được từ một đỉnh tới
17


một đỉnh khác). Xét trong bài tốn này, chỉ có đường đi từ một trạm
đến các điểm lấy hàng và giao hàng mà trạm đó phụ trách và đường đi
từ trạm này sang trạm khác. Hai điểm i và j được gọi là "nội vùng"
nếu 2 điểm i và j là các điểm lấy giao hàng thuộc cùng một khu vực
do một trạm phụ trách, hoặc một điểm là một trạm và điểm cịn lại
thuộc vùng do trạm đó phụ trách. Ta có thể định nghĩa tập E như sau
E = {(i, j) : i, j ∈ N, i = j, i và j là nội vùng} ∪ {(i, j) : i, j ∈ H, i = j}.
Định nghĩa các tham số như sau:
cij : thời gian di chuyển giữa điểm i và điểm j ((i, j) ∈ E);
mi : số đơn vị hàng hóa mà đơn hàng i yêu cầu;
Q : số đơn vị hàng hóa tối đa mà một phương tiện có thể
mang theo được;
A : thời gian xử lý đơn hàng tối thiểu ở trong mỗi trạm;
sk : trạm xuất phát và kết thúc của phương tiện k ∈ K.
Ta định nghĩa các biến như sau:
1 nếu xe k đi từ điểm i đến điểm j (i, j ∈ N ),
xkij =
0 nếu khác;
yik =


tki =
Lki =

1 nếu đơn hàng i được trung chuyển bời xe k (i ∈ P, k ∈ K),
0 nếu khác;
thời điểm xe k dời điểm i (i ∈ N, k ∈ K),
số đơn vị hàng hóa trên xe k thời điểm rời khỏi điểm i (i ∈
N, k ∈ K),

ui =

thời điểm đơn hàng i nhập trạm lấy (i ∈ P ),

vi =

thời điểm đơn hàng i xuất trạm giao (i ∈ P ),

wk =

thời điểm xe k về trạm giao nhận (k ∈ K)

Bên cạnh đó, ta định nghĩa M là một hằng số rất lớn.
Bài tốn ở trên có thể được mơ hình hóa như sau:

18


cij xkij

min


(1.1)

(i,j)∈E k∈K

với điều kiện
xkij = 1,

∀i ∈ P ∪ D

(1.2)

xkij = 1,

∀j ∈ P ∪ D

(1.3)

k∈K j:(i,j)∈E

k∈K i:(i,j)∈E

xkij =
i:(i,j)∈E

xkji ,

∀j ∈ N, k ∈ K

(1.4)


i:(i,j)∈E

xkij ≤ 1,

∀j ∈ N, k ∈ K

(1.5)

i:(i,j)∈E

xkhi ≤ 1,

∀k ∈ K

(1.6)

i∈P ∪D,h∈H,(h,i)∈E

xkij − M
i∈P ∪D,(i,j)∈E

xkhi ≤ 0,

∀k ∈ K

(1.7)

xkhi ) ≤ 0,


∀k ∈ K

(1.8)

i∈P ∪D,h∈H,(h,i)∈E

xkhl − M (1 −
i∈P ∪D,h∈H,(h,i)∈E

h,l∈H

yik = 1,

∀i ∈ P : hi = hi+n

(1.9)

k∈K

yik −

xkhi l ≤ 0,

∀i ∈ P : hi = hi+n , k ∈ K

(1.10)

l∈H

yik −


xklhi+n ≤ 0,

∀i ∈ P : hi = hi+n , k ∈ K

l∈H
19

(1.11)




Lki −
mr yrk +
mr yrk = Lkj



∗
∗
r∈P :hr+n =j
r∈P :hr =j



∀k ∈ K, P ∗ = {r ∈ P : hr = hr+n }
xkij = 1 ⇒



Lki + mj = Lkj
∀k ∈ K




 Lk − m = Lk
∀k ∈ K
i

j

j

Lki ≤ Q

nếu j ∈ P,
nếu j ∈ D
(1.12)

∀k ∈ K, i ∈ N

tki + cij − M (1 − xkij ) ≤ tkj

∀(i, j) ∈ E, k ∈ K

xkij ) ≤ ui

wk − M (1 −


nếu i, j ∈ H,

(1.13)

(1.14)

∀i ∈ P, k ∈ K

(1.15)

∀k ∈ K

(1.16)

j:(i,j)∈E

wk = tksk +

cij xkij
(i,j)∈E

∀i ∈ P ∗ , k ∈ K

tkhi+n + A − M (1 − yik ) ≤ vi
ui + A ≤ vi

∀i ∈ P

xk(i+n)j ) ≤ tksk


vi − M (1 −

∀i ∈ P, k ∈ K

(1.17)

(1.18)

(1.19)

j∈D

ui + A − M (1 − yik ) ≤ tksk
xkij ∈ {0, 1}
yik ∈ {0, 1}

∀i ∈ P ∗ , k ∈ K

(1.20)

∀(i, j) ∈ E, k ∈ K

(1.21)

∀i ∈ P, k ∈ K

(1.22)

20



tki , Lki , wk ≥ 0

∀i ∈ N, k ∈ K

ui , vi ≥ 0

∀i ∈ P

(1.23)

(1.24)

Hàm mục tiêu (1.1) là tối thiểu hóa tổng thời gian di chuyển của các
xe. Các ràng buộc theo sau gồm ba phần: ràng buộc định tuyến đường
đi ((1.2) đến (1.11)), ràng buộc đảm bảo sức tải của mỗi xe ((1.12) đến
(1.13)) và ràng buộc thời gian ((1.14) đến (1.20)).
Ràng buộc (1.2) và (1.3) đảm bảo mỗi điểm lấy hàng và giao hàng
được phục vụ một lần bởi một xe nào đó. Ràng buộc (1.4) bảo toàn
đường đi của một xe, nếu xe k đi vào điểm j thì phải đi ra khỏi điểm j.
Ràng buộc (1.5) đảm bảo mỗi xe không đi qua một điểm quá một lần.
Ràng buộc (1.6) đảm bảo mỗi xe k chỉ có thể xuất phát từ một trạm đi
ra các điểm lấy giao hàng một lần. Trong khi đó, ràng buộc (1.7) đảm
bảo nếu xe k đi lấy hoặc giao hàng thì nó phải xuất phát từ trạm. Ràng
buộc (1.8) đảm bảo mỗi xe k chỉ đi theo một trong hai tuyến đường:
lấy/giao hàng (xuất phát tại một trạm và đi qua các điểm lấy hoặc giao
hàng rồi trở về trạm ban đầu), hoặc trung chuyển hàng (chỉ đi qua các
trạm giao nhận). Các ràng buộc (1.9), (1.10) và (1.11) đảm bảo mỗi đơn
hàng cần trung chuyển sẽ được duy nhất một xe trung chuyển từ trạm
lấy đến trạm giao.

Ràng buộc (1.12) mô tả sự thay đổi lượng hàng hóa mỗi xe trên
đường đi. Ràng buộc (1.13) đảm bảo lượng hàng hóa trên xe tại mọi
thời điểm khơng vượt q sức chứa của nó.
Các ràng buộc từ (1.14) đến (1.20) là các ràng buộc về thời gian di
chuyển của các xe. Ràng buộc (1.14) thể hiện thời gian di chuyển giữa
hai điểm nếu chúng được cùng một xe đi qua. Ràng buộc (1.15) mô tả
điều kiện thời gian một đơn hàng bất kì dời trạm lấy phải lớn hơn thời
gian xe lấy hàng về trạm. Ràng buộc (1.16) tính tốn thời gian về trạm
của mỗi xe. Ràng buộc (1.17) đảm bảo thời gian đơn hàng dời trạm phải
lớn hơn thời gian đơn hàng đó được nhập trạm lấy. Ràng buộc (1.18)
đảm bảo thời gian đi lấy hàng không lớn hơn thời gian đi giao. Ràng
buộc (1.19) đảm bảo thời gian dời trạm của đơn hàng i không lớn hơn
21


thời gian xe phụ trách đơn hàng đó dời trạm. Ràng buộc (1.20) đảm bảo
thời gian dời trạm của đơn hàng i để trung chuyển không lớn hơn thời
gian xe phụ trách đơn hàng đó dời trạm.

1.3

Phương pháp giải

Bài tốn định tuyến (VRP) nói chung có thể được giải sử dụng các
thuật giải chính xác hoặc các thuật giải gần đúng cho nghiệm xấp xỉ.
Trong phần này ta sẽ xem xét tổng quan một số thuật giải có thể áp
dụng để tìm nghiệm tối ưu cho bài tốn VRP và bài tốn cụ thể ở trên.

1.3.1


Thuật giải chính xác - Exact algorithm

Một trong những kĩ thuật quan trọng nhất và cũng nổi tiếng nhất
để giải các bài toán tối ưu tổ hợp là thuật toán nhánh cận (Branch and
Bound - B&B). Thuật toán này cũng là cơ sở cho phần lớn các thuật
tốn giải chính xác cho bài tốn VRP, chẳng hạn như thuật toán Branch
& Price (B&P) hay Branch & Cut (B&C). Ý tưởng chính của thuật tốn
B&B là chia khơng gian cần tìm kiếm thành các khơng gian con (nhánh
- branching), sau đó đánh giá cận trên và cận dưới cho những khơng
gian đó (cận - bounding). Nếu một nhánh được xác định là không chứa
nghiệm tối ưu thì ta loại bỏ nhánh đó, ngược lại ta tiếp tục chia nó
thành các nhánh nhỏ hơn và tiếp tục đánh giá cận.
Phương pháp chung để đánh giá cận dưới là đi giải bài toán nới lỏng.
Bài toán nới lỏng có thể được tạo ra từ bài tốn ban đầu bằng một số
phương pháp, chẳng hạn như nới lỏng tuyến tính, nới lỏng Lagrange ...
Dựa theo phương pháp được sử dụng để đánh giá cận dưới, B&B có
thể được mở rộng thành B&P hay B&C. Ví dụ về thuật tốn B&P có
thể xem trong Agarwal et al. (1989) và Hadjiconstantinou et al. (1995).
Thuật toán B&C chủ yếu được phát triển bởi Baldacci et al. (2004) và
Lysgaard et al. (2004), và nó cũng được cải tiến nhiều tới ngày nay.
Thuật tốn chính xác cho một lớp bài tốn VRP gần đây nhất được đưa
ra bởi Jonathan Oesterle & Thomas Bauernhansl (2015).
22


1.3.2

Thuật giải gần đúng - Heuristic algorithm

Bài toán VRP đã được chứng minh thuộc lớp bài tốn NP-khó, và

các thuật giải chính xác đã đưa ra từ trước đến nay mới chỉ giải được
bài toán VRP với số đỉnh tới khoảng 150. Thuật giải gần đúng đóng vai
trị quan trọng trong giải các bài tốn VRP quy mơ lớn một cách nhanh
chóng, đồng thời đưa ra nghiệm gần tối ưu hoặc thậm chí là nghiệm tối
ưu. Các thuật giải gần đúng có thể xem như những thủ tục tìm kiếm,
trong đó phương án được sinh ra và đánh giá ở mỗi bước lặp. Do đó
làm thế nào để tìm được phương án tốt ở mỗi bước lặp một cách nhanh
chóng và hiệu quả chính là chìa khóa cho sự thành cơng của thuật tốn.
Các thuật giải gần đúng được chia thành ba nhóm: constructive
heuristics, improvement heuristics và metaheuristics.
Các thuật tốn constructive heuristics thường thử xây dựng một
phương án dựa theo các quy tắc nào đó. Các giải thuật này thường rất
hiệu quả về mặt thời gian, nhưng lời giải được đưa ra thường khơng tốt.
Trong khi đó, thuật giải improvement heuristics bắt đầu từ những
phương án đã có và cố gẳng đi cải thiện chúng từng bước bằng cách
áp dụng một chuỗi các chỉnh sửa. Những chỉnh sửa này thường rất đơn
giản. Những thuật giải này cũng có thể được xem như những thủ tục cải
tiến hoặc tìm kiếm địa phương (local search).
Metaheuristics là một dạng phức tạp hơn, chú trọng vào tìm kiếm
rộng trong tập tồn bộ các phương án. Các giải thuật dạng này cho phép
biến đổi phương án theo chiều hướng xấu đi, thậm chí tạm thời trở thành
một phương án không chấp nhận được. Metaheuristics đã trở thành một
lĩnh vực nghiên cứu phổ biến trong vòng 30 năm gần đây và đã đưa
ra nhiều kết quả ấn tượng. Một số thuật tốn metaheuristics điển hình
như: Genetic Algorithm (GA), Simulated Annealing (SA), Tabu Search
(TS).
Thuật toán Tabu Search được chọn để giải bài tốn MDPDPT đã
mơ tả ở trên và sẽ được đề cập chi tiết ở phần tiếp theo.

23