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

NGUYỄN THỊ QUỲNH VINH
THUẬT TOÁN DI TRUYỀN SONG SONG GIẢI BÀI TỐN
LỘ TRÌNH VẬN CHUYỂN VỚI HẠN CHẾ VỀ THỜI GIAN
(VRPTW)
LUẬN VĂN THẠC SĨ KHOA HỌC
CHUYÊN NGÀNH: XỬ LÝ THÔNG TIN VÀ TRUYỀN
THÔNG

NGƯỜI HƯỚNG DẪN KHOA HỌC:

Hà Nội - 2009


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

NGUYỄN THỊ QUỲNH VINH

THUẬT TOÁN DI TRUYỀN SONG SONG GIẢI BÀI TỐN LỘ
TRÌNH VẬN CHUYỂN VỚI HẠN CHẾ VỀ THỜI GIAN (VRPTW)

LUẬN VĂN THẠC SĨ KHOA HỌC
CHUYÊN NGÀNH: XỬ LÝ THÔNG TIN VÀ TRUYỀN THÔNG

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

Hà Nội - 2009


1

Lời cam đoan
Tôi xin cam đoan luận văn: "Thuật toán di truyền song song giải bài toán lộ
trình vận chuyển với hạn chế thời gian (VRPTW)" là công trình nghiên cứu riêng
của tôi dưới sự hướng dẫn của PGS.TS Nguyễn Đức Nghĩa. Các kết quả nghiên cứu
được trình bày trong luận văn là trung thực, không phải là sao chép toàn văn của bất
kỳ một công trình nào khác. Mọi trích dẫn và tài liệu tham khảo trong luận văn đều
được chỉ rõ nguồn gốc.
Hà Nội, ngày ... tháng ... năm 2009
Tác giả luận văn

Nguyễn Thị Quỳnh Vinh
Xác nhận của giáo viên hướng dẫn về mức độ hoàn thành của luận văn tốt nghiệp và
cho phép bảo vệ.
Hà Nội, ngày ... tháng ... năm 2009
Giáo viên hướng dẫn

PGS.TS Nguyễn Đức NghÜa


2

Tóm tắt
Bài toán lộ trình vận chuyển với hạn chế về thời gian là một bài toán mở rộng
của bài toán lộ trình vận chuyển nổi tiếng. Sử dụng thuật toán di truyền để giải bài

toán VRPTW đà nhận được nhiều sự quan tâm trong những năm gần đây. Trong
VRPTW, một đội xe được khởi hành từ kho chứa tới phục vụ một số khách hàng tại
các vị trí khác nhau trong các khung thời gian xác định và quay trở về kho chứa.
Luận văn này đà đưa ra một phương pháp giải bài toán VRPTW sử dụng thuật toán
di truyền song song. Thuật toán sử dụng một chuỗi số nguyên để biểu diễn vị trí các
khách hàng trong các lộ trình và quần thể ban đầu được khởi tạo bằng thuật toán
chèn heuristic (Push Forard Insertion Heuristic). Bên cạnh đó, luận văn đà trình bày
ba mô hình song song cho thuật giải di truyền: Master-Slave, Island và Cellular, và
sử dụng mô hình Master-Slave để giải bài toán VRPTW. Cuối cùng, thuật toán
đà được thực nghiệm trên 56 bài toán chuẩn của Solomon và được so sánh với các
lời giải tốt nhất hiện nay theo phương pháp heuristic.
Từ khoá: lộ trình vận chuyển, thuật toán di truyền, thuật toán di truyÒn song song


3

Abstract
The Vehicle Routing Problem with Time Windows is an extensive of the
well-known Vehicle Routing Problem (VRP). Using genetic algorithm to solve
Vehicle Routing Problem with Time Windows (VRPTW) has received considerable
attention in recent years. In the VRPTW, a fleet of verhicles set-off from a depot to
serve a number of customers at defferent geographic locations with various demands
within specific time windows before returning to the depot eventually. This thesis
proposes an approach for the solving VRPTW using a parallel genetic algorithm.
The algorithm uses an integer representation in which a string of customer
identifiers represents the sequence of deliveries covered by each of the vehicles and
the initial population is initialized using Push Forard Insertion Heuristic (PFIH). In
addition, the thesis has presented three main parallelization models for genetic
algorithms: master-slave, island and cellular, and uses a master-slave model to
solve the VRPTW problem. At the end, the algorithm has been tested on the

VRPTW benchmarks proposed by Solomon, which includes 56 problem instances,
and compared with the best known solutions identified by heuristics.
Keywords: Vehicle routing, Genetic algorithms, Parallel Genetic Algorithms


4

Lời cảm ơn
Tôi xin chân thành cám ơn các tổ chức, cá nhân đà giúp đỡ tôi về mặt nội
dung của luận văn. Sự giúp đỡ đó đà giúp tôi vượt qua nhiều khó khăn để hoàn thành
luận văn nghiên cứu của mình.
Tôi xin trân trọng cảm ơn:
-

Viện đào tạo Sau đại học - Trường Đại học Bách Khoa Hà Nội

-

Các thầy, cô giáo trong Viện Công nghệ thông tin và Truyền thông, và
trong bộ môn Khoa học máy tính cùng toàn thể các bạn đồng nghiệp.

Và đặc biệt, tôi xin chân thành cám ơn thầy giáo, PGS. TS. Nguyễn Đức
Nghĩa người đà trực tiếp hướng dẫn và cho tôi những ý kiến quý báu để tôi có được
thành quả hôm nay.
Trong một khoảng thời gian ngắn, những nội dung được trình bày trong luận
văn chắc chưa đầy đủ và còn thiếu sót. Nội dung của luận văn sẽ còn được tiếp tục
nghiên cứu, hy vọng tiếp tục nhận được những ý kiến đóng góp của mọi người để
luận văn được hoàn thiện hơn trong thời gian tới.
Hà Nội, ngày ... tháng ... năm 2009
Tác giả luận văn


Nguyễn Thị Quỳnh Vinh


5

Mơc lơc
Mơc lơc ......................................................................................................... 5
GIíI THIƯU ..................................................................................................... 7
DANH MơC C¸C THUậT NGữ .................................................................... 9
DANH MụC HìNH Vẽ và bảng............................................................... 11
Chương 1 TổNG QUAN Về BàI TOáN VRP ............................................. 13
1.1 Giới thiƯu ................................................................................................... 13
1.2 C¸c biÕn thĨ cđa VRP................................................................................ 16
1.2.1 VRP với hạn chế về trọng tải (CVRP) ............................................... 16
1.2.2 VRP víi h¹n chÕ vỊ thêi gian (VRPTW) ........................................... 19
1.2.3 VRP nhập xuất hàng kết hợp (VRPB) ............................................... 20
1.2.4 VRP nhập xuất hàng đồng thời (VRPPD). ......................................... 21
1.3 Bài toán VRP với hạn chế về thời gian (VRPTW) .................................... 22
1.3.1 Mô hình toán học của bài toán VRPTW ............................................ 22
1.3.2 Các VRPTW mở rộng ........................................................................ 24
Chương 2 CáC PHƯƠNG PHáP GIảI BàI TOáN VRP ............................. 27
2.1 Các thuật toán giải đúng ............................................................................ 27
2.1.1 Thuật toán nhánh và cận..................................................................... 27
2.2.2 Thuật toán nhánh và cắt ..................................................................... 28
2.2 Các thuật toán xấp xỉ ................................................................................. 29
2.3 Các thuật toán heuristic cổ điển ................................................................ 29
2.3.1 Heuristic kiến thiết ............................................................................. 30
2.3.2 Heuristic hai giai đoạn ....................................................................... 33
2.3.3 Heuristic cải tiến ................................................................................ 34

2.4 Thuật toán metaheristic ............................................................................. 38
2.4.1 Thuật toán mô phỏng luyện kim (Simulated Annealing) ................... 38
2.4.2 Thuật toán tìm kiếm Tabu .................................................................. 41
2.4.3 Thuật toán di truyền (GA) .................................................................. 46
2.4.3.1 Thuật toán di truyền đơn giản ..................................................... 47
2.4.3.2 ứng dụng thuật toán di truyền cho các bài toán sắp xếp chuỗi ... 48
2.4.3.3 ứng dụng thuật toán di truyền cho bài toán VRP ....................... 49
2.4.4 Thuật toán bầy kiến (AS). .................................................................. 51
2.4.5 Mạng nơron ........................................................................................ 53
Chương 3 THUậT TOáN DI TRUYềN ........................................................ 56
3.1 Tổng quan vỊ tht to¸n di trun ............................................................. 56
3.1.1 C¸c tham sè cđa tht to¸n di trun ................................................. 56
3.1.2 C¸c to¸n tư di truyền .......................................................................... 57
3.1.3 Mô hình thuật toán di truyền .............................................................. 59


6

3.2 Các mô hình song song hoá giải thuật di truyền ....................................... 60
3.2.1 Mô hình Master-slave......................................................................... 61
3.2.2 Mô hình Island. .................................................................................. 62
3.2.3 Mô hình Cellular ................................................................................ 64
Chương 4 ......................................................................................................... 67
Thuật toán di truyền song song CHO BàI TOáN VRPTW .... 67
4.1 Giíi thiƯu ................................................................................................... 67
4.1 M· hãa lêi gi¶i .......................................................................................... 67
4.2 Khởi tạo quần thể ban đầu ......................................................................... 68
4.3 Chọn läc .................................................................................................... 70
4.3.1 Hµm thÝch nghi (fitness) ..................................................................... 70
4.3.2 Chän lọc theo bánh xe roulette........................................................... 71

4.4.3 Chọn lọc cạnh tranh (tournament)...................................................... 73
4.5 Lai ghÐp ..................................................................................................... 73
4.5.1 Thao t¸c lai dùa trên chuỗi khách hàng (SBX)................................... 74
3.2.4.2 Thao tác lai dựa trên lộ trình (RBX)................................................ 76
4.6 Đột biến ..................................................................................................... 78
3.2.5.1 Đột biÕn mét møc (1M) .................................................................. 78
3.2.5.2 §ét biÕn hai møc (2M) .................................................................... 79
3.2.5.3 Đột biến dựa trên sự tối ưu hãa cơc bé (LSM) ................................ 80
4.7 Tht to¸n GA song song cho bài toán VRPTW ...................................... 80
Chương 5 CàI ĐặT Và CHạY THựC NGHIệM ........................................ 83
5.1 Cài đặt hệ thống......................................................................................... 83
5.1.1 Các kiến trúc lập trình song song ....................................................... 83
5.1.2 Môi trường cài đặt .............................................................................. 84
5.3 Dữ liệu thực nghiệm .................................................................................. 85
5.4 KÕt qu¶ thùc nghiƯm ................................................................................. 88
KÕT LN ..................................................................................................... 97
Tài liệu tham khảo ............................................................................... 99
Phụ lục ...................................................................................................... 101


7

GIớI THIệU
Trong những thập niên gần đây, sử dụng các gói phần mềm tối ưu để quản lý
hiệu quả quá trình cung cấp hàng hóa và dịch vụ trong hệ thống phân phối ngày
càng tăng. Phần lớn các ứng dụng thực tế đà chỉ ra rằng, máy tính hóa những thủ tục
cho quá trình lập kế hoạch phân phối sản phẩm tiết kiệm được chi phí đáng kể
(thông thường từ 5% tíi 20%) trong toµn bé chi phÝ vËn chun. Dễ dàng thấy tác
động của khoản tiết kiệm này đến chi phí sản xuất sản xuất nói chung và giá thành
sản phẩm nói riêng là không nhỏ.

Bài toán lộ trình vận chuyển (VRP) được đưa ra đầu tiên bởi Danzig và
Ranser (1959), với ứng dụng phân phối xăng dầu cho nhà ga, đà dành được sự quan
tâm rất lớn của nhiều nhà khoa học. ĐÃ có hàng trăm các mô hình và thuật toán
khác nhau cho các phiên bản của VRP. HiƯn nay, mét biÕn thĨ cđa VRP, VRP víi
h¹n chế thời gian (VRPTW), được nghiên cứu và ứng dụng kh¸ nhiỊu trong thùc tÕ,
nh­ c¸c øng dơng dän dĐp đường phố, định hướng lộ trình xe bus, chuyên chở người
khuyết tật, lập lịch quá trình phân phối hàng hoá cho người bán hàng... Với những ý
nghĩa thực tiễn đó của bài toán, tôi chọn đề tài luận văn tốt nghiệp là:
"Thuật toán di truyền song song giải bài toán lộ trình vận chuyển với hạn
chế thời gian (VRPTW)"
Nội dung của luận văn được trình bày như sau:
Chương 1: "Tổng quan về bài toán lộ trình vận chuyển (VRP)" trình bày các khái
niệm và các biến thể cơ bản của bài toán VRP nói chung và bài toán VRP với hạn
chế thời gian (VRPTW) nói riêng, một biến thể của bài toán VRP mà hiện nay được
nghiên cứu và ứng dụng khá nhiều trong thực tế. Trong đó, chúng ta sẽ đi tìm hiểu
chi tiết về mô hình toán học và các bài toán mở rộng của VRPTW.
Chương 2: "Các phương pháp giải bài toán VRP" trình bày sơ lược về các phương
pháp giải bài toán VRP bao gồm: các phương pháp giải đúng (thuật toán nhánh và
cận, thuật toán nhánh và cắt) và các phương pháp giải gần đúng (thuật toán heuristic
cổ điển và thuật toán metaheuristic ).


8

Chương 3: "Thuật toán di truyền" trình bày các khái niệm cơ bản về thuật toán di
truyền và tìm hiểu ba mô hình song song cho thuật toán di truyền: mô hình Masterslave, mô hình Island và mô hình Cenllular.
Chương 4: "Thuật toán di truyền song song cho bài toán VRPTW" trình bày thuật
toán di truyền cho bài toán VRPTW và áp dụng mô hình master-slave cho thuật toán
di truyền khi giải bài toán VRPTW
Chương 5: "Cài đặt và chạy thực nghiệm". Chương này trình bày kiến trúc của hệ

thống máy tính được sử dụng để cài đặt chương trình và trình bày hệ thống chương
trình sẽ được chạy thực nghiệm trên bộ dữ liệu của Solomon. Đây là bộ dữ liệu phổ
biến thường được sử dụng cho các bài toán VRP. Sau đó, tổng hợp các kết quả
đà đạt được của thực nghiệm và thực hiện so sánh kết quả đạt được của chương trình
với các lời giải được biÕt lµ tèt nhÊt hiƯn nay.


9

DANH MụC CáC THUậT NGữ
STT

Thuật ngữ tiếng anh

Nghĩa tiếng việt

1

Vehicle Routing Problem (VRP)

Bài toán lộ trình vận chuyển

2

Capacitated VRP (CVRP)

Bài toán VRP với hạn chế về trọng tải

3


Distance VRP ( DVRP)

Bài toán VRP với hạn chế về khoảng
cách

4

VRP with Time Windows (VRPTW)

Bài toán VRP với hạn chế về thời gian

5

VRP with Backhauls (VRPB)

Bài toán VRP nhập xuất hàng kết hợp

6

VRP with Pickup and Delivery

Bài toán VRP nhập xuất hàng đồng thời

(VRPPD)
7

Asymmetric CVRP (ACVRP)

Bài toán CVRP bất đối xứng


8

Symmetric CVRP (SCVRP)

Bài toán bài toán đóng thùng

9

Bin Packing Problem (BPP)

Bài toán CVRP đối xứng

10

Traveling Salesman Problem

Bài toán người du lịch

11

Distance-Constrained VRP(DCVRP)

Bài toán VRP với hạn chế khoảng cách
và trọng tải

12

TSP with Time Windows (TSPTW)

Bài toán TSP với hạn chế về thời gian


13

VRP with Pickup and Deliveries and

VRP nhËp xuÊt ®ång thêi cã hạn chế về

Time Windows (VRPPDTW)

thời gian

14

Branch and Bound

Thuật toán nhánh cận

15

Branch and Cut

Thuật toán nhánh cắt

16

Linear programming (LP)

Bài toán quy hoạch tuyến tính

17


Integer linear program (IP)

Bài toán quy hoạch tuyến tính nguyên

18

Generalized Assignment Problem

Bài toán phân công mở rộng

19

Simulated Annealing (SA)

Thuật toán luyện kim

20

Tabu Search (TS)

Thuật toán tìm kiếm tabu

21

Genetic Algorithms (GA)

Thuật toán di truyền

22


Ant Systems (AS)

Thuật toán bầy kiến


10

23
24

Neural Networks (NN)

Mạng nơron

Roulette-wheel selection

Phương pháp chọn lọc theo bánh xe
roullete

25

Tournament selection

Phương pháp chọn lọc cạnh tranh


11

DANH MụC HìNH Vẽ và bảng

Hình 1.1 Các lớp bài toán VRP
Hình 2.1: Minh họa quá trình rẽ nhánh của thuật toán nhánh và cận
Hình 2.2: Minh họa thủ tục cải tiến của Thompson and Psaraftis 3-chu trình, 2- di
chuyển
Hình 2.3 Minh họa thủ tục lai chuỗi của Van Breedam
Hình 2.4 Minh họa thủ tục trao đổi của Van Breedam.
Hình 2.5 Minh họa thủ tục định vị lại chuỗi Van Breedam.
Hình 2.6: Minh họa thao tác định vị lại khách hàng của Kinderwater và Savelsbergh
Hình 2.7: Minh họa tác lai ghép của Kinderwater và Savelsbergh
Hình 2.8: Minh họa thao tác hoán đổi khách hàng của Kinderwater và Savelsbergh
Hình 2.9 Tạo một phần lời giải mới theo thủ tục bộ nhớ thích nghi của Rochat và
Taillard
Hình 2.10: Lai ghép1 điểm
Hình 2.11: Lai ghép theo thứ tự
Hình 2.12: Đột biến RAR
Hình 2.13: Biểu diễn lời giải VRP
Hình 2.14: : Quá trình mở réng cđa mét khung biÕn ®ỉi mÉu trong (a), (b), (c) và
thu được lời giải cuối cùng (d) trong thuật toán mạng nơron
Hình 3.1 Sơ đồ tổng quát của thuật toán di truyền
Hình 3.2: Mô hình Master-slave
Hình 3.3: Mô hình Island
Hình 3.4: Mô hình Cellular và cấu trúc vùng lân cận
Hình 4.1: Biểu diễn lời giải của bài toán VRPTW
Hình 4.2: Minh họa quá trình chọn lọc theo bánh xe roullete
Hình 4.3: Minh họa thao tác lai dựa trên chuỗi khách hàng
Hình 4.4: Minh họa thao tác sữa lỗi lời giải
Hình 4.5: Minh họa thao tác lai theo lộ trình
Hình 4.6: Minh họa thao tác đột biến một mức (1M)



12

Hình 4.7: Minh họa thao tác đột biến hai mức (2M)
Hình 4.8:Sơ đồ thuật toán GA song song cho bài toán VRPTW
Hình 5.1: Kết quả lời giải thu được tốt nhất của thuật toán đối với bài toán c101.txt
Hình 5.2: Kết quả lời giải thu được tốt nhất của thuật toán đối với bài toán r101.txt
Hình 5.3: Kết quả lời giải thu được tốt nhất của thuật toán đối với bài toán rc101.txt
Hình 5.4: So sánh tổng khoảng cách đi của lời giải thu tốt nhất thu được với lời giải
tốt nhất được biết hiện nay
Hình 5.5: So sánh số lộ trình của lời giải thu tốt nhất thu được với lời giải tốt nhất
được biết hiện nay
Hình 5.6: So sánh thời gian thực hiện chương trình
Hình 5.7: So sánh chất lượng lời giải
Bảng 5.1: Bảng tập hợp các kết quả tốt nhất thu được của chương trình và các lêi
gi¶i heuristic tèt nhÊt hiƯn nay.


13

Chương 1

TổNG QUAN Về BàI TOáN VRP

1.1 Giới thiệu
Bài toán lộ trình vận chuyển (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 một lộ trình được thực hiện bằng một
phương tiện vận tải bắt đầu và kết thúc tại kho chứa, đáp ứng tất cả các yêu cầu của
khách hàng và thoả mÃn mọi điều kiện ràng buộc sao cho chi phí vận tải là cực tiểu.
Trong phần này, chúng ta sẽ tìm hiểu một số đặc trưng điển hình của bài toán định
tuyến và lập lịch bằng cách xét các thành phần chính: khách hàng, kho chứa, phương

tiện vận chuyển, người điều khiển, và các điều kiện ràng buộc khác có thể sẽ ảnh
hưởng tới cấu trúc của các lộ trình, và các mục tiêu cần đạt được trong quá trình tối
ưu. Hệ thống các lộ trình được sử dụng cho quá trình vận chuyển hàng hóa, thường
được biểu diễn bởi một đồ thị, mỗi cung đại diện cho một đoạn đường và mỗi đỉnh
tương ứng với vị trí kho chứa hoặc vị trí của khách hàng trong hệ thống. Các cung có
thể có hướng hoặc không, tùy thuộc vào việc chúng có thể đi qua theo một hướng
hoặc hai hướng. Mỗi một cung được gán với một chi phí, thường là chiều dài của nó
hoặc là thời gian của hành trình, phụ thuộc vào phương tiện vận chuyển hoặc thời
gian đi qua cung đó.
Các đặc trưng về khách hàng:
-

Vị trí khách hàng hoặc kho chứa được biểu diễn bởi các đỉnh của đồ thị.

-

Số lượng hàng hóa (theo yêu cầu), có thể khác nhau về chủng loại, được giao
hoặc nhận tại mỗi vị trí khách hàng.

-

Khung thời gian, là khoảng thời gian có thể phục vụ một khách hàng


14

-

Thời gian yêu cầu, là thời gian cần thiết để thực hiện yêu cầu giao hoặc nhận
hàng hóa tại vị trí của mỗi khách hàng (tương ứng với thời gian dỡ hàng hoặc

bốc hàng).

-

Số lượng xe sẵn có mà có thể được sử dụng để phụ vụ khách hàng (có thể hạn
chế quyền truy cập hoặc các yêu cầu bốc, dỡ hàng).
Đôi khi không thể đáp ứng hoàn toàn yêu cầu của từng khách hàng. Trong

trường hợp đó, số lượng sẽ được giao hoặc được nhận tại mỗi vị trí khách hàng có
thể bị giảm xuống, hoặc một nhóm khách hàng có thể không được phục vụ. Để giải
quyết các trường hợp này, có thể gán các mức ưu tiên hoặc các mức phạt khác nhau
ứng với mỗi khách hàng.
Các lộ trình được thực hiện để phục vụ khách hàng bắt đầu và kết thúc tại
một hoặc nhiều kho hàng, được định vị bởi các đỉnh của đồ thị đường. Mỗi kho được
đặc trưng bởi số lượng xe, loại xe và sức chứa hàng hóa của kho. Trong trường hợp,
một lộ trình được bắt đầu từ một kho và quay trở lại kho đó ở cuối mỗi lộ trình thì
bài toán VRP có thể được tách thành nhiều bài toán con độc lập, mỗi bài toán được
kết hợp với một kho chứa khác nhau. Quá trình vận chuyển hàng hóa được thực hiện
bằng cách sử dụng một đội xe có kích thước cố định.
Các đặc trưng của xe:
-

Trọng tải của xe, được biểu diễn bởi khối lượng lớn nhất mà xe có thể tải.

-

Khả năng chia nhỏ xe thành các ngăn hàng, mỗi phần được đặc trưng bởi
trọng tải và loại hàng hóa mà nó có thể chở.

-


Các thiết bị sẵn có cho các thao tác bốc và dỡ hàng.

-

Tập con các cung của đồ thị đường mà xe có thể đi qua.

-

Chi phí liên quan đến việc sử dụng xe (trên một đơn vị khoảng cách, trên một
đơn vị thời gian, ..)
Các đặc trưng của người lái xe thường liên quan đến một số các điều kiện

ràng buộc được đưa ra trong bản hợp đồng và các quy định của công ty (ví dụ như
khoảng thời gian làm việc trong ngày, số lượng và khoảng thời gian nghỉ giữa các
dịch vụ, thời gian tối đa cho một lần lái, thời gian làm thêm giờ...).


15

Tùy thuộc vào từng bài toán cụ thể mà lộ trình cần phải thoả mÃn một số các
điều kiện ràng buộc, phụ thuộc vào chất lượng của mức dịch vụ cung cấp, các đặc
trưng của khách hàng và loại xe được sử dụng. Chẳng hạn như một số các điều kiện
ràng buộc về trọng tải dọc theo mỗi lộ trình, khối lượng tải hiện tại của xe không thể
vượt quá trọng tải của xe; các điều kiện ràng buộc về yêu cầu của khách hàng được
phục vụ trên một lộ trình: có thể chỉ yêu cầu giao hàng hoặc nhận hàng, hoặc tồn tại
cả hai; điều kiện ràng buộc về khung thời gian phục vụ khách hàng: trong đó mỗi
khách hàng được gán với một khung thời gian (time windows) và trong khoảng thời
gian đó khách hàng này sẽ được phục vụ; và các ràng buộc về mức ưu tiên liên quan
đến thứ tự khách hàng được phục vụ trên mỗi lộ trình.

Để tính tổng chi phí của các lộ trình và kiểm tra các điều kiện ràng buộc, đồ
thị ban đầu được biến đổi thành một đồ thị đầy đủ và các đỉnh của đồ thị tương ứng
là vị trí của các khách hàng và kho chứa. Với một cặp đỉnh i, j của một đồ thị đầy đủ,
ta ®Þnh nghÜa chi phÝ cđa cung (i,j), ký hiƯu ci,j, là chi phí của đường đi ngắn nhất từ
i đến j trong đồ thị, tij là tổng thời gian đi của các cung thuộc đường đi ngắn nhất từ i
đến j trên đồ thị đường đi. Khi đó, thay vì xét đồ thị cơ bản ban đầu chúng ta xét đồ
thị đầy đủ tương ứng có thể có hướng hoặc không có hướng phụ thuộc vào ma trận
chi phí (hoặc ma trận thời gian) của hành trình là tuyến tính hay không tuyến tính.
Một số mục tiêu trong bài toán VRP:
-

Cực tiểu chi phí vận chuyển, phụ thuộc vào khoảng cách của lộ trình (hoặc
thời gian vận chuyển) và các chi phí cố định liên quan đến phương tiện được
sử dụng (hoặc liên quan đến người lái).

-

Cực tiểu hóa số lượng xe (hoặc số lượng lái xe) được yêu cầu để phục vụ tất
cả các khách hàng.

-

Cân bằng thời gian đi và trọng tải của xe giữa các lộ trình.

-

Cực tiểu hóa các hình phạt liên quan đến các phần dịch vụ của khách hàng


16


1.2 Các biến thể của VRP
Trong mục này, chúng ta sẽ tìm hiểu tổng quan về các lớp bài toán VRP cơ
bản: VRP với hạn chế về trọng tải (CVRP), VRP với hạn chế về khoảng cách
(DVRP), VRP với hạn chÕ vỊ thêi gian (VRPTW), VRP nhËp xt hµng kÕt hợp
(VRPB), VRP nhập xuất hàng đồng thời (VRPPD).

Hình 1.1 Các lớp bài toán VRP
Hình 1.1 minh họa các lớp bài toán chính của VRP, mũi tên từ bài toán A sang B có
nghĩa B là một bài toán mở rộng của A.

1.2.1 VRP với hạn chế về trọng tải (CVRP)
Trong CVRP, tất cả các yêu cầu giao hàng của khách hàng là cố định, được
biết trước và không thể phân chia. Một tập các phương tiện là đồng nhất và được đặt
tại một kho trung tâm, có giới hạn về trọng tải. Mục tiêu của bài toán là cực tiểu
tổng chi phí phục vụ tất cả khách hàng. Bài toán CVRP được trình bày theo lý thuyết
đồ thị như sau:
Cho G=(V,A) là một đồ thị đầy đủ


17

Trong đó:
-

V={0,...,n}: là tập các đỉnh
o Các đỉnh i=1, 2, ...n : là các đỉnh khách hàng
o Đỉnh i=0: là đỉnh kho

-


A: là tập các cung.

-

cij : Chi phí đi từ đỉnh i đến đỉnh j, được gán cho cung (i,j). Thường không
sử dụng cung tròn (i,i) (cii=+ với mọi i V ).

-

di: được gán với một yêu cầu phân phối không âm của khách hàng i (yêu
cầu của kho d0=0). Cho một tập các đỉnh S V , d S = iS d i là tổng yêu
cầu của các khách hàng trên tập S

-

K: số xe được sử dụng. Trong đó Kmin là số lượng xe nhỏ nhất cần thiết để
phục vụ tất cả khách hàng

-

C: trọng t¶i cđa xe (di ≤ C víi i=1,...,n)

L­u ý:
-

NÕu G là đồ thị có hướng thì ma trận chi phí c là không đối xứng, bài toán
tương ứng được gọi là CVRP bất đối xứng (ACVRP). Khi đó, A là tập các
cạnh của đồ thị có hướng G được xác định bởi các đỉnh đầu mút của nó
(i, j ) i, j ∈ V .


-

NÕu cij=cji víi mäi (i, j ) A thì bài toán tương ứng được gọi là CVRP đối
xứng (SCVRP), và tập các cung A được thay thế bởi tập các cạnh không có
hướng E.
o Với mỗi e E , a(e) và (e) để chỉ các đỉnh đầu mút của cạnh e.

o Với mỗi tập ®Ønh S ⊆ V , δ(S) ®Ĩ chØ tËp c¹nh e E mà chỉ có một

đỉnh đầu mút nằm trong S. E(S) để chỉ tập cạnh e E có cả hai đỉnh

đầu mút nằm trong S
-

Cho một đỉnh i,
o +(i) để chỉ tập các đỉnh j có cung (i, j ) A

o -(i) để chỉ tập các ®Ønh j cã cung ( j , i ) ∈ A ,.


18

Khi chi phí đường đi ngắn nhất của một cung thuộc đồ thị bằng chi phí đi
giữa các điểm đầu mút của nó, thì ma trận chi phí thoả mÃn bất đẳng thức tam giác.
(1.1)

cik + ckj cij với mọi i, j , k V

Khi các đỉnh được gán với các điểm trong hệ tọa độ phẳng thì chi phí cij, với

mỗi cung (i, j ) A , được định nghĩa bởi khoảng cách Euclid giữa hai điểm tương
ứng với hai đỉnh i và j. Trong trường hợp này ma trận chi phí là đối xứng và thoả
mÃn bất đẳng thức tam giác.
Giá trị của Kmin có thể được xác định bằng lời giải của bài toán đóng thùng
(Bin Packing Problem-BPP), bài toán yêu cầu xác định số lượng tối thiểu các thùng
hàng, mỗi thùng có thể chứa một khối lượng là C, được yêu cầu để chứa tất cả n
món hàng, mỗi món hàng có khối lượng di, i=1,..,n. và di không âm.
Cho một tập S ⊆ V \ {0} , r(S) lµ sè xe tèi thiểu để phục vụ các khách hàng trong tập
S, tức là r(S) là giá trị lời giải tối ưu của bài toán BPP kết hợp với một tập S sản
phẩm (r(V\{0})=Kmin). Thường r(S) được thay thế bởi cận dưới của bài toán BPP
(1.2)

d ( S ) / C

Mục tiêu của bài toán CVRP là tìm kiếm một tập K lộ trình có chi phí tối thiểu sao
cho:
(i)

Mỗi lộ trình phải thăm đỉnh kho.

(ii)

Mỗi khách hàng phải được thăm bởi chính xác một lộ trình.

(iii)

Tổng yêu cầu của các đỉnh được thăm bởi một lộ trình không vượt quá C,
trọng tải của xe.

CVRP được biết là NP-khó và là bài toán mở rộng của bài toán người du lịch (TSP),

yêu cầu xác định chi phí tối thiểu của một mạch đơn thăm tất cả các đỉnh thuộc G và
C d(V), K=1.
Biến thể đầu tiên của CVRP là VRP với hạn chế về khoảng cách (DVRP),
trong đó điều kiện ràng buộc về trọng tải trong mỗi lộ trình được thay thế bởi điều
kiện ràng buộc về chiều dài (hoặc thời gian) tối đa. Tức là, với cung (i, j ) ∈ A (hc


19

cạnh e E ) được gán với tij (hoặc te) không âm, là chiều dài của cung (i,j), và tổng
chiều dài các cung trên một lộ trình không vượt quá chiều dài cực đại T cho trước.
Khi chiều dài của cung được xem như thời gian di chuyển trên cung đó thì ta có thể
gán thời gian phục vụ si cho mỗi khách hàng i, là khoảng thời gian phải dừng tại
khách hàng đó.
Thường ma trận chi phí trùng víi ma trËn thêi gian, cij=tij víi mäi (i, j ) ∈ A
(hc ce=te víi mäi e ∈ E ). Do đó, mục tiêu của bài toán là tối thiểu hóa tổng chiều
dài (hoặc thời gian) của các lộ trình, khi tính đến thời gian phục vụ và thời gian đi
trên mỗi lộ trình. Trong truờng hợp, bài toán có giới hạn cả về trọng tải của xe và
khoảng cách cực đại lộ trình thì bài toán được gọi là bài toán CVRP với hạn chế về
thời gian và khoảng cách (DCVRP: Distance-Constrained CVRP).

1.2.2 VRP với hạn chế về thời gian (VRPTW)
VRP với hạn chế về thời gian (VRPTW) là một bài toán mở rộng của CVRP
và mỗi khách hàng i được kết hợp với một khoảng thời gian [ai, bi], được gọi là
khung thời gian (time window). Trong khoảng thời gian đó, khách hàng i sẽ được
phục vụ với thời gian si. Vì vậy, trong trường hợp phương tiện đến trước khung thời
gian đó thì nó phải đợi cho đến thời gian ai để bắt đầu dịch vụ tại khách hàng i. Với
mỗi cung (i, j ) A (hoặc te với e E ), thời gian đi trên cung (i,j) bằng thời gian đi
từ i tới j và cộng với thời gian (si) phục vụ khách hàng i.
Th­êng ma trËn chi phÝ trïng víi ma trËn thêi gian đi, và thời gian đi được

xác định bằng cách giả sử rằng tất các các phương tiện rời khỏi kho tại thời điểm 0.
Hơn nữa, các điều kiện về khung thời gian đem lại một sự định hướng ẩn cho mỗi lộ
trình ngay cả khi ma trận chi phí đối xứng. Do đó VRPTW thường được mô hình
như hóa một bài toán bất đối xứng.
VRPTW yêu cầu tìm kiếm mét tËp K lé tr×nh cã tỉng chi phÝ tèi thiểu sao cho:
(i)

Mỗi lộ trình phải thăm đỉnh kho.

(ii)

Mỗi đỉnh khách hàng phải được thăm bởi chính xác bởi một lé
tr×nh.


20

(iii)

Tổng yêu cầu của các đỉnh được thăm bởi một lộ trình không vượt
quá trọng tải của xe C.

(iv)

Với mỗi khách hàng i, dịch vụ được bắt đầu trong khung thời gian
[ai, bi] và được phục vụ với thời gian si.

VRPTW là NP-khó, được khái quát hóa từ CVRP khi ai = 0 bi = ∞, víi
i ∈ V \ {0} . Hơn nữa TSP với hạn chế về thời gian (TSPTW) là trường hợp đặc biệt


của VRPTW khi K=1 và Cd(V).

1.2.3 VRP nhập xuất hàng kết hợp (VRPB)
VRP nhập xuất hàng kết hợp là một mở rộng của CVRP trong đó tập khách
hàng V\{0} được chia thành hai tập con L và B. Tập L chứa n khách hàng yêu cầu
nhập hàng và tập B chứa m khách hàng yêu cầu xuất hàng. Khách hàng được đánh
số sao cho L={1,..,n} và B={n+1,...,n+m}
Trong VRPB tồn tại một ràng buộc về mức ưu tiên giữa khách hàng yêu cầu
nhập hàng và khách hàng yêu cầu xuất hàng, tất cả khách hàng nhập phải được phục
vụ trước khách hàng yêu cầu xuất. Mỗi khách hàng i được kết hợp với một yêu cầu
không âm di và kho chứa được kết hợp với một yêu cầu ảo d0=0. Bài toán VRPB yêu
cầu tìm kiÕm mét tËp K lé tr×nh víi chi phi cùc tiểu, và sao cho:
(i)

Mỗi lộ trình phải thăm đỉnh kho.

(ii)

Mỗi đỉnh khách hàng được thăm bởi chính xác bởi một lộ trình

(iii)

Tổng các yêu cầu của khách hàng yêu cầu nhập hàng và khách hàng yêu
cầu xuất hàng được thăm bởi một lộ trình không vượt quá C, trọng tải của
xe

(iv)

Trong một lộ trình tất cả các khách hàng yêu cầu nhập hàng phải đứng
trước khách hàng yêu cầu xuất hàng, nếu có.


Cho KL và KB là số lượng xe nhỏ nhất cần phục vụ cho tất cả khách hàng yêu
cầu nhập và yêu cầu xuất tương ứng. Những giá trị này có thể thu được bằng cách
giải bài toán đóng thùng (BPP) kết hợp với hai tập con khách hàng tương ứng. Để


21

đảm bảo tính khả thi, chúng ta giả sử rằng K không nhỏ hơn số lượng xe nhỏ nhất
cần thiết để phục vụ tất cả khách hàng, tức là Kmax{KL, KB}.
VRPB là NP-khó, được khái quát từ bài toán CVRP khi B=ỉ.

1.2.4 VRP nhập xuất hàng đồng thời (VRPPD).
Trong bài toán VRP nhập xuất hàng đồng thời (VRP with Pickup and
Delivery-VRPPD), mỗi khách hàng i được kết hợp với di và pi tương ứng với yêu cầu
xuất hàng và yêu cầu nhập hàng của khách hàng i. Đôi khi, chỉ có một yêu cầu
di=di-pi được dùng cho khách hàng i, chỉ ra sự khác nhau giữa yêu cầu xuất hàng và
yêu cầu nhập hàng (có thể âm).
Chúng ta giả sử rằng tại mỗi vị trí của khách hàng, yêu cầu nhập hàng được
thực hiện trước yêu cầu xuất hàng trên mỗi lộ trình; khi đó, trọng tải hiện tại của
một chiếc xe trước khi đến một vị trí cho trước được xác định bằng trọng tải ban đầu
của nó trừ đi tất cả các yêu cầu nhập hàng đà được thực hiện cộng với tất cả các yêu
cầu xuất hàng đà được thực hiện
VRPPD yêu cầu tìm kiếm một tập K lộ trình có chi phí vận tải là cực tiểu sao cho:
(i)

Mối lộ trình phải thăm đỉnh kho.

(ii)


Mỗi đỉnh khách hàng phải được thăm bởi chính xác bởi một lộ trình.

(iii)

Trọng tải hiện tại của xe dọc theo một lộ trình phải là không âm và không
bao giờ vượt quá C, trọng tải của xe.

(iv)

Với mỗi một khách hàng i, thì yêu cầu nhập hàng sẽ được thực hiện trước
yêu cầu xuất hàng.

VRPPD là NP-khó. Chúng khái được quát hóa từ CVRP khi pi=0 với mỗi
i V . Hơn nữa, TSP nhập xuất hàng kết hợp là trường hợp đặc biệt của VRPPD khi

K=1. Trường hợp VRPPD với hạn chế về thời gian được gọi là bài toán VRP nhập
xuất hàng đồng thời với hạn chế về thời gian (VRPPDTW : VRP with Pickup and
Deliveries and Time Windows).


22

1.3 Bài toán VRP với hạn chế về thời gian (VRPTW)
Như đà trình bày ở trên, VRP với hạn chế về thời gian là một mở rộng của
CVRP trong đó dịch vụ tại mỗi khách hàng phải bắt đầu trong mét khung thêi gian.
Cã hai lo¹i khung thêi gian, khung thêi gian cøng vµ khung thêi gian mỊm. Trong
khi khung thời gian mềm có thể vi phạm ràng buộc về thời gian, thì khung thời gian
cứng không cho phép một phương tiện nào đến một khách hàng sau một khoảng thời
gian đà cho trước. Trong trường hợp, nếu nó đến trước khi khách hàng sẵn sàng để
bắt đầu dịch vụ, thì nó phải đợi. VRPTW là NP-khó, được nghiên cứu đầu tiên bởi

Pullen và Webb, Knight và Hofer. Ngày nay, các nghiên cứu về bài toán này chủ
yếu tập trung vào thiết kế các heuristic để giải các bài toán có kích thước thực và
phát triển các phương pháp tiếp cận tối ưu có hiệu quả.

1.3.1 Mô hình toán học của bài toán VRPTW
Bài toán VRPTW được trình bày theo lý thuyết đồ thị như sau:
Cho G=(V,A) là một đồ thị đầy đủ
Trong đó:
-

V={0,...,n}: là tập các đỉnh
o Các đỉnh i=1, 2, ...n : là các đỉnh khách hàng
o Đỉnh i=0: là đỉnh kho

-

A: là tập các cung.

-

cij : Chi phí đi từ đỉnh i đến đỉnh j, được gán cho cung (i,j). Thường không
được sử dụng cung tròn (i,i) (cii=+ với mọi i V ).

-

di: được gán với một yêu cầu phân phối không âm của khách hàng i (mặc
định yêu cầu tại kho d0=0). Cho một tập các đỉnh S V , d S = iS di là
tổng yêu cầu của các các khách hàng trên tập S

-


K: số xe được sử dụng. Trong đó Kmin là số lượng xe nhỏ nhất cần thiết để
phục vụ tất cả khách hàng

-

C: trọng tải của xe (di C víi i=1,...,n)


23

-

[ai,bi]: là khung thời gian phục vụ khách hàng i, ai là thời gian đến sớm
nhất và bi là thời gian đến muộn nhất tại khách hàng i. Tại nút kho [a0,b0]
= [E,L] trong đó E và L là thời gian khëi hµnh sím nhÊt vµ thêi gian kÕt
thóc mn nhất có thể của mỗi lộ trình bắt đầu và kết thúc tại kho chứa.

Lưu ý:
-

Số lộ trình trong hệ thống bằng số phương tiện được sử dụng trong bài toán.

-

Bài toán chỉ tồn tại lời giải khả khi và chØ khi a 0 = E ≤ min i∈V \{0} bi − t 0i vµ
bn +1 = L ≥ min i∈V \{0} ai + si + t 0i .

-


Cung (i, j ) A có thể bị loại bỏ nếu ai+si+tij>bj (do hạn chế về thời gian),
hoặc nếu di+dj > C (do hạn chế về trọng tải).

Mô hình toán học cho VRPTW được phát biểu như sau:

(1.1)

(VRPTW ) min

c x

k∈K ( i , j )∈A

víi ®iỊu kiƯn

ij ijk