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

Nguyễn Việt Hân

THUẬT TOÁN DI TRUYỀN SONG SONG GIẢI BÀI TOÁN
VRP (VEHICLE ROUTING PROBLEM) VỚI HẠN CHẾ
THỜI GIAN

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

Hà Nội – Năm 2009


BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
--------------------------------------NGUYỄN VIỆT HÂN

Nguyễn Việt Hân

THUẬT TOÁN DI TRUYỀN SONG SONG GIẢI BÀI
TOÁN VRP (VEHICLE ROUTING PROBLEM) VỚI
HẠN CHẾ THỜI GIAN

LUẬN VĂN THẠC SĨ KHOA HỌC
CHUYÊN NGÀNH: CÔNG NGHỆ THÔNG TIN

2007 - 2009
Hà nội
2009

NGƯỜI HƯỚNG DẪN KHOA HỌC:
TS. NGUYỄN ĐỨC NGHĨA

Hà Nội – Năm 2009


2

Lời cảm ơn
Trước tiên, em xin gửi lời cảm ơn chân thành đến Thầy PGS. TS. Nguyễn Đức
Nghĩa đã định hướng nghiên cứu và góp ý cho em để có được luận văn hoàn chỉnh.
Em xin cảm ơn Quý Thầy cơ trong Khoa, với lịng nhiệt huyết, đã vun đắp nền tảng
tri thức vững chắc cho các thế hệ học viên. Đây sẽ là hành trang vô giá cho chúng
em trên con đường nghiên cứu khoa học.
Nhân đây, con xin gửi lời biết ơn đến cha mẹ đã vất vả ni nấng và tạo mọi điều
kiện để con có được như ngày hôm nay. Xin cảm ơn em, người vợ luôn lo lắng, chia
sẻ và động viên anh vượt qua những khó khăn, thử thách.
Sau cùng, khơng thể thiếu lời cảm ơn đến các anh chị đồng nghiệp đã trao đổi,
khích lệ và dành thời gian nhiều hơn cho tơi để hoàn thành tốt luận văn.


3

Mục lục
Lời cảm ơn ................................................................................................................. 2
Mục lục ....................................................................................................................... 3
Chương 1: Giới thiệu ............................................................................................. 9
1.1


Đặt vấn đề ..................................................................................................... 9

1.2

Giới thiệu về VRP ...................................................................................... 10

1.3

Các tiêu chuẩn phân loại bài toán VRP ...................................................... 12

1.4

Một số dạng chính của bài tốn VRP ......................................................... 13

1.4.1

VRP với hạn chế khả năng chở hàng hóa ...........................................13

1.4.2

VRP với hạn chế thời gian ..................................................................14

1.4.3

VRP với nhiều kho hàng hóa ..............................................................15

1.4.4

VRP định kỳ ........................................................................................16


1.4.5

VRP mở...............................................................................................17

1.4.6

VRP tách phân phối ............................................................................17

1.4.7

VRP với khả năng chuyên chở về .......................................................17

1.4.8

VRP với khả năng nhặt và phân phối .................................................18

1.5

Tối ưu tổ hợp .............................................................................................. 19

Chương 2: Bài toán VRP với hạn chế thời gian ................................................ 20
2.1

Định nghĩa .................................................................................................. 20

2.2

Mơ hình tốn học........................................................................................ 20

2.3


Các cấu trúc vùng lân cận........................................................................... 23

2.4

Các phương pháp chính tiếp cận giải bài tốn ........................................... 26

2.4.1

Các phương pháp chính xác ................................................................26

2.4.1.1 Dựa trên quy hoạch động ................................................................26
2.4.1.2 Dựa trên phát sinh cột .....................................................................26
2.4.1.3 Dựa trên phân rã Lagrange ..............................................................26
2.4.1.4 Dựa trên K-Tree ..............................................................................27


4

2.4.2

Các phương pháp heuristic .................................................................27

2.4.2.1 Nguyên lý ........................................................................................27
2.4.2.2 Heuristic xây dựng lộ trình..............................................................28
2.4.2.3 Heuristic cải thiện lộ trình ...............................................................29
Chương 3: Thuật toán di truyền song song ....................................................... 35
3.1

Giới thiệu về thuật tốn di truyền ............................................................... 35


3.2

Các phép tốn chính của thuật toán di truyền ............................................ 36

3.2.1

Phép chọn ............................................................................................36

3.2.2

Phép lai................................................................................................37

3.2.3

Phép đột biến.......................................................................................39

3.3

Các mơ hình song song .............................................................................. 40

3.3.2

Song song dạng chủ tớ ........................................................................41

3.3.3

Song song dạng đa quần thể con có di trú ..........................................42

3.3.4


Song song dạng quần thể con chồng lấp, không di trú .......................44

3.3.5

Thuật toán di truyền song song khối lớn ............................................45

3.3.6

Song song dạng các nhóm cá thể động ...............................................45

3.3.7

Thuật tốn song song trạng thái ổn định .............................................46

3.3.8

Thuật toán song song hỗn tạp .............................................................46

3.3.9

Các phương pháp lai ...........................................................................46

Chương 4: Thuật toán di truyền song song giải bài toán VRP với hạn chế thời
gian

............................................................................................................. 48

4.1


Heuristic xây dựng lộ trình ......................................................................... 48

4.2

Thuật tốn di truyền giải bài toán VRPTW................................................ 52

4.2.1

Biểu diễn nhiễu sắc thể .......................................................................52

4.2.2

Tạo quần thể ban đầu ..........................................................................53

4.2.3

Đánh giá tính thích nghi ......................................................................54

4.2.4

Các thao tác di truyền .........................................................................55

4.2.4.1 Chọn lọc ..........................................................................................55
4.2.4.2 Tái tổ hợp ........................................................................................56


5

4.2.5
4.3


Tạo thế hệ mới ....................................................................................57

Thuật toán di truyền song song giải bài toán VRPTW .............................. 59

Chương 5: Hiện thực và đánh giá chương trình ............................................... 63
5.1

Các vấn đề hiện thực .................................................................................. 63

5.1.1

Cấu trúc dữ liệu biểu diễn lộ trình và lời giải .....................................63

5.1.2

Hai chiến lược khởi tạo quần thể ban đầu...........................................64

5.1.3

Một số kỹ thuật song song hóa ...........................................................65

5.2

Đánh giá kết quả ......................................................................................... 67

5.2.1

Phương pháp đánh giá.........................................................................67


5.2.2

Kết quả thực hiện ................................................................................68

5.2.3

Các nhận xét ........................................................................................76

Chương 6: Kết luận và hướng phát triển ........................................................... 77
6.1

Các kết luận ................................................................................................ 77

6.2

Hướng phát triển......................................................................................... 77

Tài liệu tham khảo .................................................................................................. 78
Tóm tắt ..................................................................................................................... 82
Abstract .................................................................................................................... 83


6

Danh sách các từ viết tắt
GA

Genetic Algorithm

PGA


Parallel Genetic Algorithm

MIMD

Multiple Instruction Multiple Data

VRP

Vehicle Routing Problem

VRPTW

Vehicle Routing Problem with Time Window

PFIH

Push-Forward Insertion Heuristic

LSD

λ-Interchange Local Search Descent

TSP

Travelling Salesman Problem

ACS

Ant Colony System


ACO

Ant Colony Optimization

MACS-

Multiple Ant Colony System for Vehicle Routing Problems with

VRPTW

Time Windows

PMX

Partially Mapped Crossover


7

Danh sách các hình
Hình 1.1 Lời giải với 2 lộ trình của một thể hiện VRP 12 khách hàng .................11
Hình 1.2 Ví dụ VRP với hạn chế khả năng có 3 lộ trình .......................................14
Hình 1.3 Ví dụ VRP với 3 kho hàng hóa ...............................................................16
Hình 1.4 Ví dụ VRP với khả năng nhặt và phân phối ...........................................18
Hình 2.1 Ví dụ về một trao đổi Or-Opt .................................................................23
Hình 2.2 Ví dụ về một trao đổi 2-Opt*..................................................................24
Hình 2.3 Minh họa thao tác relocate......................................................................24
Hình 2.4 Minh họa thao tác trao đổi (exchange) ...................................................25
Hình 2.5 Kiến trúc của MACS-VRPTW ...............................................................33

Hình 3.1 Các khái niệm cơ bản của thuật tốn di truyền.......................................35
Hình 3.2 Vịng quay lựa chọn cá thể .....................................................................36
Hình 3.3 Thao tác trao đổi chéo một điểm cắt.......................................................38
Hình 3.4 Thao tác trao đổi chéo nhiều điểm cắt ....................................................38
Hình 3.5 Một số loại đột biến thường gặp .............................................................39
Hình 3.6 Phân loại các thuật tốn di truyền song song .........................................41
Hình 3.7 Mơ hình song song dạng chủ tớ ..............................................................42
Hình 3.8

Lược đồ thuật tốn di truyền song song kết mịn. Lớp thuật tốn này có

một quần thể được phân tán từng phần và được hiện thực rất hiệu quả trên các máy
tính song song lớn. ....................................................................................................44
Hình 3.9 Các hình thức kết hợp phân cấp .............................................................46
Hình 4.1 Chọn cá thể theo vịng thi đấu ................................................................56
Hình 4.2 Mơ hình giải thuật song song dạng chủ tớ..............................................60
Hình 5.1 Minh họa cấu trúc danh sách liên kết biểu diễn một lộ trình .................63
Hình 5.2 Minh họa cấu trúc dữ liệu lời giải cho VRPTW.....................................64
Hình 5.3 Hệ thống cluster thử nghiệm ..................................................................69
Hình 5.4 Biểu đồ biểu diễn giá trị Speedup theo số tiến trình trong từng phân
nhóm

................................................................................................................75


8

Danh sách các bảng
Bảng 5.1


Bảng so sánh kết quả trung bình từ các kết quả tốt nhất giữa các

phương pháp và kết quả tốt nhất được biết ...............................................................70
Bảng 5.2

Bảng chi tiết so sánh thời gian trung bình khi thực thi tuần tự so với

thời gian trung bình khi thực thi song song ứng với số tiến trình khác nhau và theo
từng tập tin mẫu.........................................................................................................71
Bảng 5.3

Bảng tổng hợp so sánh thời gian trung bình thực thi tuần tự và song

song trong mỗi nhóm dữ liệu ....................................................................................74
Bảng 5.4

Bảng Speedup trung bình của chương trình thực thi song song tính

theo từng nhóm mẫu..................................................................................................74


9

Chương 1: Giới thiệu
1.1 Đặt vấn đề
VRP là bài toán xác định các lộ trình tối ưu cho đội xe vận chuyển nhằm phục vụ
các khách hàng ở các vị trí khác nhau. Đây là bài tốn có nhiều ứng dụng trong thực
tế từ khâu cung cấp nguyên liệu thô đến khâu phân phối thành phẩm trong các nhà
máy sản xuất, các công ty dịch vụ vận chuyển như bưu phẩm, hành khách, … Rõ
ràng, chi phí vận chuyển sẽ giảm nếu các xe di chuyển theo các lộ trình tối ưu, từ đó

giúp giảm giá thành hàng hóa. Trong thời đại kinh tế xã hội ngày càng phát triển,
các yêu cầu của khách hàng ngày càng khắt khe hơn. Tiêu biểu như yêu cầu phải
được đáp ứng trong một khoảng thời gian xác định; các công ty hoạt động theo một
thời gian biểu chính xác, … Chính vì vậy, vấn đề lập lộ trình VRP với hạn chế thời
gian (viết tắt là VRPTW) ngày càng được quan tâm hơn. Luận văn đặt nghiên cứu
trên bài toán VRPTW phù hợp với xu thế phát triển.
Hơn thế, VRP là một dạng bài tốn NP-khó, do đó, VRPTW cũng thuộc NP-khó.
Mục tiêu của VRPTW là tối thiểu số xe vận chuyển và tổng khoảng cách di chuyển
khi phục vụ các khách hàng mà không vi phạm các ràng buộc về khả năng chuyên
chở của các xe và các cửa sổ thời gian đáp ứng. Để tìm lời giải khả thi cho bài toán,
nhiều thuật toán đã được nghiên cứu và ứng dụng như các thuật toán dựa trên quy
hoạch động, các thuật toán dựa trên sự nới lỏng Lagrange, các thuật toán dựa trên
heurictic, ... Trong đó, các thuật tốn heuristic được quan tâm nhiều nhất. Luận văn
tiếp cận giải thuật di truyền giải quyết bài toán VRPTW. Đây là giải thuật dựa trên
heuristic được ứng dụng rộng rãi trong nhiều bài toán tối ưu thực tế thuộc nhiều lĩnh
vực khác nhau.
Các thuật toán dựa trên heuristic thường cho các lời giải có tính khả thi cao, gần với
lời giải tối ưu của bài toán. Tuy nhiên, giải thuật phải lặp qua nhiều vịng lặp với
nhiều tính tốn địi hỏi nhiều năng lực tính tốn của máy tính. Tiêu biểu như thuật
tốn di truyền phải lặp qua nhiều thế hệ, các thao tác tính tốn thực hiện trên từng


10

cá thể của tồn bộ quần thể. Vì thế, thời gian thực hiện các thuật toán heuristic khá
lâu và tiêu tốn nhiều năng lực tính tốn của máy tính. Do đó, bên cạnh việc nghiên
cứu và áp dụng thuật tốn di truyền vào giải bài toán VRP với hạn chế thời gian,
luận văn cũng tập trung phát triển thuật toán di truyền song song nhằm nổ lực rút
ngắn thời gian tìm lời giải cho bài tốn.


1.2 Giới thiệu về VRP
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, các nguyên liệu thô phải được vận chuyển đến nhà máy từ nhiều nhà cung cấp
khác nhau; kế đến, các thành phẩm thường được vận chuyển đến các kho ở các vị trí
địa lý khác nhau; Sau đó, từ các kho trung tâm này, các hàng hóa được phân phối
đến các khách hàng và thậm chí có thể lấy về các hàng hóa được trả về từ 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 lập lộ trình xe vận chuyển - VRP.
Bài tốn lập lộ trình đơn giải và nổi tiếng nhất là bài toán người bán hàng
(Traveling Salesman Problem - TSP). Người bán hàng phải ghé thăm một số thành
phố và sau đó trở về vị trí xuất phát ban đầu. Một lộ trình phải được xây dựng sao
cho tối ưu khoảng cách di chuyển. Mở rộng bài toán TSP, m người bán hàng xuất
phát tại cùng một địa điểm và phải ghé thăm tất cả thành phố được cho. Mỗi thành
phố phải được thăm chính xác một lần bởi một người bán hàng nào đó. Bài tốn
cũng tối ưu tổng khoảng cách của các lộ trình. VRP chính là bài tốn m-TSP với
một đòi hỏi được liên kết với mỗi thành phố và mỗi xe có một khả năng vận chuyển
xác định.


11

Hình 1.1 Lời giải với 2 lộ trình của một thể hiện VRP 12 khách hàng
(Trong Hình 1.1, ơ vng thể hiện kho hàng trung tâm, các vòng tròn thể hiện các
khách hàng được đánh số thứ tự, các mũi tên có hướng thể hiện hướng đi của các lộ
trình).
Bài toán VRP là dạng bài toán ra quyết định, nhằm tìm các lộ trình tối ưu cho đội xe
vận chuyển hàng hóa đến các khách hàng ở các địa điểm khác nhau. Mục tiêu của

bài toán thường là tối thiểu tổng khoảng cách hoặc thời gian di chuyển với nhiều
ràng buộc cụ thể như khả năng chuyên chở của xe, khoảng thời gian mong muốn
được đáp ứng của khách hàng, ...
Bài tốn VRP thường bao gồm ít nhất hai bài tốn con liên quan nhau:
• Bài tốn phân hoạch: nhằm phân chia tập khách hàng thành các tập con sao
cho mỗi tập con chỉ được phục vụ bởi một xe nào đó.
• Bài tốn định tuyến: nhằm tìm ra lộ trình tối ưu cho mỗi xe vận chuyển.
VRP là một vấn đề rộng và có thể bao gồm nhiều vấn đề con ứng với các tình
huống và các ràng buộc khác nhau. Do đó, để đơn giản khi giải quyết bài toán VRP,
tùy theo mục tiêu mà người ta thường cụ thể hóa một số ràng buộc phụ. Ví dụ mục
tiêu phục vụ khách hàng cao là phải phân phát chính xác, nghĩa là phân phát đúng
số lượng, đúng chất lượng, đúng thời gian tại một địa điểm chính xác.


12

1.3 Các tiêu chuẩn phân loại bài toán VRP
Như đã trình bày trên, VRP có nhiều mục tiêu và các ràng buộc khác nhau. Vì thế,
trong thực tế có rất nhiều lớp bài toán VRP tùy theo mục tiêu và sự nới lỏng hoặc
thêm các ràng buộc. Các tiêu chuẩn sau đây được sử dụng để phân biệt các dạng bài
tốn VRP khác nhau:
Đặc tính

STT
1

Số mục tiêu

Tùy chọn
− Đơn mục tiêu

− Đa mục tiêu
− Tất cả các nhu cầu của khách hàng đều
được đáp ứng.

2

Ràng buộc nhu cầu

− Xác định một số khách hàng nên được
phục vụ.
− Cho phép tách các phân phối hay
không.
− Không cửa sổ thời gian.

3

Ràng buộc thời gian

− Cửa sổ thời gian một bên hoặc hai bên,
cửa sổ thời gian cứng hoặc mềm.
− Một xe phục vụ một lộ trình.

4

Đa sử dụng xe

− Một xe có thể phục vụ nhiều hơn một lộ
trình.

5


Thuộc tính của đồn xe

− Đoàn xe vận chuyển đồng nhất.
− Đoàn xe vận chuyển không đồng nhất.

6

Số kho

− Một kho trung tâm chứa hàng hóa.
− Nhiều kho hàng hóa.


13

Đặc tính

STT
7

Tùy chọn
− Lộ trình đóng

Loại lộ trình

− Lộ trình mở
− Khoảng thời gian phân phối đơn
8


− Xác định khách hàng nào nên được

Thời gian hoạch định

phục vụ tại thời điểm nào của hoạch
định.
− Kiểu phục vụ đơn: hoặc phân phối hoặc
9

lấy và mang hàng hóa trở về.

Kiểu phục vụ

− Kiểu phục vụ hỗn hợp: vừa có phân
phối, vừa có mang về.

1.4 Một số dạng chính của bài tốn VRP
1.4.1 VRP với hạn chế khả năng chở hàng hóa
VRP với hạn chế khả năng chở hàng hóa của xe (Capaciated vehicle routing
problem – CVRP) là một dạng bài toán VRP nhưng có thêm ràng buộc mỗi xe đều
có khả năng chuyên chở như nhau đối với một hàng hóa đơn nào đó và tổng tải của
mỗi xe khơng vượt q khả năng của nó.
Mục tiêu của bài tốn CVRP là tối thiểu số xe và tổng thời gian di chuyển, đồng
thời tổng số lượng hàng hóa được gán cho mỗi lộ trình khơng vượt q khả năng
của xe phục vụ lộ trình đó. Như vậy, lời giải cho bài tốn CVRP giống như lời giải
của bài tốn VRP nhưng có thêm hạn chế tổng nhu cầu của tất cả khách hàng cần
được phục vụ trên lộ trình Rt khơng vượt quá khả năng xe Q .
m

∑d

i =1

Trong đó:

i

≤Q


14

m: tổng số khách hàng được gán trên lộ trình Rt.
di: nhu cầu của khách hàng thứ i trên lộ trình.
Q : khả năng của xe.

Hình 1.2 Ví dụ VRP với hạn chế khả năng có 3 lộ trình

1.4.2 VRP với hạn chế thời gian
VRP với hạn chế thời gian (vehicle routing problem with time windows – VRPTW)
là mở rộng của bài toán CVRP bằng cách đưa thêm ràng buộc cửa sổ thời gian. Cửa
sổ thời gian của một khách hàng là khoảng thời gian mong muốn được đáp ứng của
khách hàng đó.
Cửa sổ thời gian [ei, li] của khách hàng thứ i qui định rằng xe vận chuyển:
• Phải không đến địa điểm khách hàng thứ i trước thời điểm ei hoặc phải chờ
nếu nó đến ở thời điểm ti < ei.
• Phải khơng đến địa điểm khách hàng thứ i sau thời điểm li ≥ ei.
Bài toán VRPTW là dạng bài toán xác định nhiều mục tiêu, bao gồm:
1.

Tối thiểu số lộ trình hay số xe.


2.

Tối thiểu tổng khoảng cách di chuyển.

3.

Tối thiểu tổng thời gian cần cho các xe, kể cả thời gian chờ.


15

Tùy theo giá trị ei, li trong cửa sổ thời gian [ei, li], có một số dạng cửa sổ thời gian
sau:
• Cửa sổ thời gian hai bên nếu 0 < ei ≤ li < ∞.
• Cửa sổ thời gian một bên nếu ei = -∞ hoặc li = ∞.
• Cửa sổ thời gian hai bên cứng nếu một lời giải được xem là không khả thi
trong trường hợp một xe đến trước thời điểm ei hoặc sau thời điểm li tại nút i.
• Cửa sổ thời gian một bên cứng nếu một xe không đến trễ hơn li tại nút i hoặc
phải chờ nếu nó đến sớm hơn thời điểm ei tại nút i.
• Cửa sổ thời gian mềm nếu thời điểm đến của xe khơng ảnh hưởng đến tính
khả thi của lời giải, nhưng bị phạt bằng cách cộng thêm một giá trị vào hàm
mục tiêu.
ρ e max{0, ei − ti } + ρl max{0, ti − li }

Với ρe ≥ 0 và ρl ≥ 0 là các hằng số giá trị phạt cho trước.

1.4.3 VRP với nhiều kho hàng hóa
VRP với nhiều kho hàng hóa (multi-depot vehicle routing problem – MDVRP)
cũng là mở rộng của CVRP bằng cách xem xét nhiều kho hàng hóa chứ khơng phải

chỉ một kho trung tâm như các dạng trên. Ngoài việc gán các khách hàng tới các xe
vận chuyển và xác định các lộ trình cho các xe, bài tốn có thêm một mức xác định
nữa là gán các lộ trình (hoặc các khách hàng) đến các kho.


16

Hình 1.3 Ví dụ VRP với 3 kho hàng hóa

1.4.4 VRP định kỳ
VRP định kỳ (periodic vehicle routing problem – PVRP) là mở rộng bài toán VRP
bằng cách mở rộng thời gian hoạch định thành vài ngày, một tuần, ... thay vì chỉ
một ngày. Trong khoảng thời gian chính xác này, mỗi khách hàng phải được ghé
thăm ít nhất một lần. Như vậy, bài toán cần phải xác định thêm những khách hàng
nào nên được đáp ứng vào những ngày nào để tối ưu tổng chi phí (bao gồm số xe,
tổng thời gian và tổng khoảng cách).
Mỗi khách hàng cho biết trước tần số phục vụ f i (số lần) và nhu cầu di > 0 cho mỗi
lần phân phối hàng hóa. Vấn đề bài tốn là tạo ra một nhóm các lộ trình cho mỗi
ngày sao cho các ràng buộc liên quan được thỏa mãn và tổng chi phí được tối ưu.
PVRP được xem như bài toán tối ưu tổ hợp đa mức:
• Mức thứ nhất: mục tiêu tạo ra một nhóm các lựa chọn khả thi (các tổ hợp)
cho mỗi khách hàng. Ví dụ: nếu khoảng thời gian hoạch định là t = 3 ngày
{d1, d2, d3} thì các tổ hợp có thể là 0000; 1001; 2010;
3011;4100; 5101; 6110; 7111. Nếu khách hàng đòi hỏi ghé thăm
hai lần thì khách hàng này có các lựa chọn lịch ghé thăm sau: {d1, d2}, {d1,
d3}, {d2, d3}.


17


• Mức thứ hai: chọn ra một trong các lựa chọn cho mỗi khách hàng sao cho
các ràng buộc theo ngày được thỏa mãn. Vì vậy, cần chọn ra các khách hàng
phải được ghé thăm mỗi ngày.
• Mức thứ ba: giải bài toán VRP cho mỗi ngày.

1.4.5 VRP mở
VRP mở (Open vehicle routing problem – OVRP) giả định một lộ trình kết thúc
ngay khi khách hàng cuối cùng trên lộ trình đó đã được phục vụ. Bài tốn OVRP dễ
dàng chuyển đổi thành bài toán CVRP bằng cách gán các khoảng cách từ mỗi khách
hàng trở về kho bằng 0.

1.4.6 VRP tách phân phối
VRP tách phân phối (Split Delivery vehicle routing problem - SDVRP) là sự nới
lỏng bài toán VRP bằng cách cho phép một khách hàng có thể được phục vụ bởi các
xe khác nhau nếu điều này làm giảm chi phí tổng thể. Sự nới lỏng này rất quan
trọng khi nhu cầu của một khách hàng lớn hơn khả năng chở của xe.
Một lời giải khả thi nếu tất cả các ràng buộc của VRP thỏa mãn ngoại trừ một khách
hàng có thể được cung cấp bởi nhiều hơn một xe vận chuyển. Rõ ràng, bài toán cần
phải xác định thêm phần chia sẻ yir ∈ [0, 1] của nhu cầu di của khách hàng i được
phân phối trên lộ trình r. Bất lợi của phương pháp phân phối này là khách hàng
thường khơng thích nhu cầu của họ được đáp ứng nhiều lần.

1.4.7 VRP với khả năng chuyên chở về
VRP với khả năng chuyên chở một số hàng hóa trở về (VRP with backhauling –
VRPB) phân biệt hai nhóm khách hàng N1 và N2. Mỗi khách hàng i ∈ N1 đòi hỏi
phải được phân phối một số lượng hàng hóa cho trước từ kho. Trong khi đó, mỗi
khách hàng i ∈ N2 yêu cầu mang một số lượng hàng hóa cho trước tại khách hàng
đó trở về kho. Một giả định quan trọng là mỗi lộ trình đầu tiên phải phục vụ những
khách hàng thuộc nhóm N1 và sau đó có thể phục vụ các khách hàng thuộc nhóm N2



18

trên đường trở về kho. Việc trộn lẫn các khách hàng thuộc hai nhóm với nhau là
khơng được phép, nghĩa là đầu tiên phục vụ khách hàng i ∈ N1, kế đến phục vụ
khách hàng j ∈ N2, sau đó phục vụ khách hàng t ∈ N1, ... trên một lộ trình đơn. Bởi
vì điều này có thể dẫn đến tiêu tốn thời gian và quá tải cho phép của xe, tức là các
ràng buộc của VRP có thể bị vi phạm.

1.4.8 VRP với khả năng nhặt và phân phối
VRP với khả năng nhặt và phân phối (VRP with pickup and delivery – VRPPD) giả
định rằng mỗi khách hàng cũng là một yêu cầu vận chuyển. Mỗi yêu cầu vận
chuyển i ∈ N được đặc trưng bởi:
• Vị trí lấy hàng hóa i+ và vị trí phân phối i-;
• Số lượng hàng hóa di phải được lấy tại i+ và được phân phối tại i- ;
• Các cửa sổ thời gian [ei , li ] và [ei , li ] tại vị trí nhặt và phân phối hàng hóa.
+

+

−

−

Hình 1.4 Ví dụ VRP với khả năng nhặt và phân phối
Các ràng buộc của VRPPD thường là:
• Các ràng buộc thứ tự trước sau bởi vì bên địi hỏi vận chuyển phải được
viếng thăm trước bên phân phối trong cùng một lộ trình.
• Vị trí nhặt i+ và vị trí phân phối i- của mỗi đòi hỏi phải nằm trên cùng một lộ
trình.



19

• Tải của xe khơng vượt q khả năng của nó.
• Thao tác nhặt và phân phối phải diễn ra trong khoảng thời gian cho phép của
cửa sổ thời gian.
Mô hình nhặt và phân phối này thường được sử dụng trong trường hợp vận chuyển
hành khách. Khi đó, VRPPD có tính động cao và các địi hỏi vận chuyển đến động
theo thời gian.

1.5 Tối ưu tổ hợp
Bài toán tối ưu có thể hình thức hóa như là tìm giá trị nhỏ nhất hoặc lớn nhất của
hàm mục tiêu f . Các biến xi với i ∈ [1, k ] , thường viết x = ( x1 , x2 ,..., xk ) gọi là các

biến quyết định. Một số ràng buộc xác định tập lời giải khả thi S. S được gọi là
khơng gian lời giải. Bài tốn tối ưu được phát biểu như sau:
min f ( x)

với giả thuyết x ∈ S
Tập lời giải S được mô tả bằng tập hợp các phương trình và bất phương trình. Ứng
với một bài tốn tối ưu cho trước, có nhiều cách khác nhau để hình thức hóa tương
ứng hàm mục tiêu, các biến quyết định và đặc tả không gian lời giải. Chính điều này
làm nảy sinh các thuật tốn khác nhau để giải quyết vấn đề và hệ quả kéo theo là
hiệu quả tính tốn cũng như chất lượng lời giải có thể khác nhau.
Các bài tốn tối ưu tổ hợp là các bài toán tối ưu với tập lời giải khả thi là xác định
nhưng thường rất lớn. Các thuật toán hiệu quả chỉ tồn tại cho một số bài tốn, trong
khi phần lớn chỉ có thể giải bằng những phương pháp đòi hỏi thời gian theo hàm số
mũ. Các bài tốn thuộc dạng chỉ có thể giải bằng những phương pháp đòi hỏi độ
phức tạp thời gian theo hàm số mũ được gọi là bài tốn NP-khó.



20

Chương 2: Bài toán VRP với hạn chế thời gian
2.1 Định nghĩa
Theo định nghĩa của Thangiah[4], VRP với hạn chế thời gian (ký hiệu là VRPTW)
liên quan đến một đội xe vận chuyển có các khả năng và thời gian di chuyển giới
hạn, xuất phát từ một kho trung tâm đến các khách hàng ở các vị trí khác nhau; mỗi
khách hàng có nhu cầu và cửa sổ thời gian cụ thể, biết trước. Cửa sổ thời gian có thể
là một phía hoặc hai phía. Trong trường hợp một phía, hạn chót đáp ứng thường
được quan tâm. Cửa sổ thời gian là hai phía, nghĩa là một khách hàng phải được
phục vụ tại hoặc sau thời điểm bắt đầu và phải trước thời điểm kết thúc của cửa sổ
thời gian liên kết với khách hàng đó. Xe sẽ phải chờ nếu đến một khách hàng sớm
hơn thời điểm bắt đầu phục vụ và sẽ bị trễ nếu đến sau thời điểm kết thúc của cửa
sổ.

2.2 Mơ hình tốn học
Bài tốn VRPTW được biểu diễn bởi một tập hợp V các xe giống nhau, một nút đặc
biệt gọi là kho hàng hóa, một tập hợp C bao gồm các khách hàng cần đáp ứng và
một mạng có hướng kết nối kho với các khách hàng. Giả sử có K xe vận chuyển, ký
hiệu V = {0, 1, 2, …, K-1} và N+1 khách hàng, ký hiệu C = {0, 1, 2, …, N}. Để
đơn giản, kho trung tâm được đề cập như là khách hàng thứ 0.
Một lộ trình bắt đầu từ kho, đi qua một số khách hàng và kết thúc tại kho xuất phát.
Số lộ trình trong mạng giao thơng cũng chính bằng số xe vận chuyển được sử dụng,
K. Mỗi cạnh trong mạng có mang giá trị chi phí cij và thời gian di chuyển tij . Mỗi
khách hàng có một nhu cầu mi khác nhau và phải được ghé thăm duy nhất một lần
bởi một xe nào đó. Do trọng tải của xe qk có giới hạn nên qk phải lớn hơn hoặc
bằng tổng tất cả các nhu cầu của các khách hàng trong lộ trình di chuyển của nó.
Hơn nữa, mỗi khách hàng phải được phục vụ trong một khoảng thời gian định

trước, bị giới hạn bởi thời gian đến sớm nhất và thời gian đến trễ nhất. Nếu các xe


21

vận chuyển đến trễ hơn thời điểm trễ nhất này thì sẽ bị phạt, trong khi đó các xe đến
sớm hơn thời điểm sớm nhất phải tạm ngừng để chờ đợi. Các xe phải hồn thành
các lộ trình của mình trong tổng thời gian lộ trình cho phép (thời gian qui định của
kho).
Mơ hình tốn học của bài tốn như sau:
Đặt:
• K: tổng số xe vận chuyển
• N: tổng số khách hàng cần phục vụ
• Ci: khách hàng thứ i, với i = 1, 2, …, N.
• C0: kho hàng trung tâm
• cij: chi phí đi từ nút i đến nút j.
• tij: thời gian di chuyển giữa nút i và nút j.
• mi: nhu cầu của nút i.
• ui: biến xác định hư cấu cho nút i.
• qk: khả năng của xe k.
• ti: thời điểm đến tại nút i.
• ei: thời điểm sớm nhất có thể phục vụ tại nút i.
• li: thời điểm trễ nhất cịn được phép phục vụ tại nút i.
•

f i : thời gian phục vụ tại nút i.

•

wi : thời gian chờ tại nút i.


•

rk : thời gian lộ trình lớn nhất được phép cho xe k.


22

Mục tiêu:
N

N K −1

Min∑∑∑ cij xijk
i =0 j =0 k =0

Trong đó: xijk = 1 nếu có cạnh nối giữa nút i và nút j và xijk = 0 nếu ngược lại.
Các ràng buộc:
K −1 N

∑∑ x

ijk

k = 0 j =1

K −1

=K


N

∑ ∑x
k = 0 j = 0, j ≠ i

=1

ijk

N

∑ xihk −

i = 0,i ≠ h

N

∑x

j = 0, j ≠ h

hjk

=0

i =0

N

i = 0 j = 0, j ≠ i


ijk

với ∀h ∈ [1, N ];

k ∈ [0, K − 1]

(2.3)

(2.5)

(tij + f i + wi ) ≤ rk với ∀k ∈ [0, K − 1]

(2.6)

j = 0, j ≠ i

N

(2.2)

với ∀k ∈ [0, K − 1]

N

∑ ∑x

với i = 1, 2, …, N

(2.4)


∑m ∑ x
i

(2.1)

với i = 1, 2, …, N; j = 1, 2, …, N; i ≠ j

ui − u j + Nxij ≤ N − 1
N

với i = 0

ijk

≤ qk

t0 = 0

(2.7)

ti + xijk (tij + f i + wi ) ≤ t j

với i, j ∈ [1, N ]; i ≠ j ; k ∈ [0, K − 1]

(2.8)

ei ≤ ti ≤ li

với i ∈ [1, N ]


(2.9)

Ràng buộc (2.1) nhằm đảm bảo có chính xác K lộ trình đi ra khỏi kho. Ràng buộc
(2.2) và (2.3) đảm bảo chỉ một xe vận chuyển vào và ra tại một khách hàng. Ràng
buộc (2.4) đảm bảo khơng có các lộ trình con trong lời giải. Khả năng của xe thể
hiện ở ràng buộc (2.5) trong khi đó thời gian di chuyển lớn nhất cho mỗi xe được
đảm bảo trong (2.6). Cuối cùng, các phương trình (2.7), (2.8), (2.9) thể hiện các
ràng buộc thời gian.


23

Mơ hình hóa bài tốn VRPTW được nghiên cứu bởi nhiều tác giả và được trình bày
khá chi tiết trong các bài báo [4], [13], [16].

2.3 Các cấu trúc vùng lân cận
Phần nền tảng của các heuristic, đặc biệt là các heuristic cải thiện lộ trình[1][5] là
khái niệm vùng lân cận. Vùng lân cận của một lời giải S là một tập N(S) các lời giải
được tạo ra bằng cách thay đổi S. Việc kiểm tra một số hay tất cả các lời giải trong
vùng lân cận có thể phát hiện ra các lời giải tốt hơn đối với một hàm mục tiêu cụ
thể. Ý tưởng này có thể được lặp lại với lời giải tốt hơn vừa tìm được. Tại một điểm
nào đó, nếu khơng có bất kỳ lời giải tốt hơn nào được tìm thấy thì lời giải tối ưu đã
đến. Nhưng đây có thể là tối ưu cục bộ hoặc có thể là tối ưu tồn cục. Thuật tốn
này được gọi là tìm kiếm cục bộ. Các meta-heuristic[26][16] đều dựa trên tìm kiếm
cục bộ nhưng có các phương thức mới được thêm vào nhằm hướng dẫn thoát khỏi
một tối ưu cục bộ để kiểm tra các phần khác của khơng gian lời giải có thể chứa các
lời giải tốt hơn.

Hình 2.1 Ví dụ về một trao đổi Or-Opt

Một trong các heuristic cải tiến được sử dụng rộng rãi nhất trong lập lộ trình và lập
lịch là heuristic r-Opt. Theo đó, r cung được xóa ra và được thay thế bởi r cung
khác. Một lời giải thu được từ việc sử dụng vùng lân cận r-Opt và không thể được
cải tiến thêm được gọi là r-tối ưu. Năm 1995, Potvin và Rosseau[27] đã trình bày
hai biến thể mới là 2-Opt* và Or-Opt mà vẫn duy trì được hướng của lộ trình. Theo
Or-Opt, một phân đoạn của lộ trình gồm l khách hàng liên tục nhau được di chuyển
đến nơi khác trên lộ trình. Hình 2.1 trình bày một ví dụ về Or-Opt, hình vng nhỏ


24

thể hiện kho hàng hóa. Hình bên trái thể hiện lộ trình trước khi áp dụng Or-Opt và
hình bên phải là lộ trình sau khi đã thực hiện trao đổi. Hướng của các khách hàng từ
i1 tới il vẫn duy trì khơng đổi.

Hình 2.2 Ví dụ về một trao đổi 2-Opt*
2-Opt* là thao tác trao đổi một phân đoạn của một lộ trình này với một phân đoạn
của một lộ trình khác. Hình 2.2 minh họa 2-Opt*, hình vng nhỏ biểu diễn kho
hàng hóa, hình bên trái và hình bên phải lần lượt thể hiện các lộ trình trước và sau
khi thực hiện trao đổi. Phần sau cùng của lộ trình này sẽ trở thành phần sau cùng
của lộ trình kia. Chú ý rằng nếu (i, is ) là cung đầu tiên trên một lộ trình và ( j , js ) là
cung sau cùng của một lộ trình khác thì hai lộ trình này sẽ được trộn thành một.

Hình 2.3 Minh họa thao tác relocate
Toán tử relocate di chuyển một khách hàng từ một lộ trình này đến một lộ trình
khác, được minh họa trong Hình 2.3. Ở đây, các cạnh (i p , i ) , (i, is ) và ( j , js ) được
thay thế bởi (i p , is ) , ( j , i ) và (i, js ) .