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

NGUYỄN CHÍ THANH

BÀI TOÁN GIAO THÔNG TAXI – BUS HÀ NỘI

Chuyên ngành : Công nghệ thông tin

LUẬN VĂN THẠC SĨ KỸ THUẬT
CÔNG NGHỆ THÔNG TIN

NGƢỜI HƢỚNG DẪN KHOA HỌC
:
TS. ĐỖ PHAN THUẬN

Hà Nội – Năm 2014


Bài toán giao thông taxi – bus Hà Nội

LỜI CAM ĐOAN
Tôi – Nguyễn Chí Thanh - Cam kết luận văn này là công trình nghiên cứu của bản
thân tôi dƣới sự hƣớng dẫn của TS. Đỗ Phan Thuận
Các kết quả nêu 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ỳ công trình nào khác.

3

Bài toán giao thông taxi – bus Hà Nội

LỜI CẢM ƠN
Trước hết, tôi xin gửi lời cảm ơn trân trọng nhất tới TS. Đỗ Phan Thuận, bộ môn
Khoa học máy tính, Viện Công nghệ thông tin và Truyền thông, trường Đại học
Bách Khoa Hà Nội, người đã hướng dẫn, tận tình chỉ bảo và hỗ trợ tôi trong suốt
quá trình làm đồ án tốt nghiệp.
Tôi xin gửi lời cám ơn tới các thầy cô trong Viện Công nghệ thông tin và Truyền
thông cùng toàn thể các thầy cô trường Đại học Bách Khoa Hà Nội đã cùng giúp
đỡ, hỗ trợ tôi trong suốt quá trình nghiên cứu và thực hiện luận văn này
Hà Nội, ngày 22 tháng 03 năm 2014

Học viên: Nguyễn Chí Thanh

4


Bài toán giao thông taxi – bus Hà Nội

MỤC LỤC
MỤC LỤC ....................................................................................................... 5
DANHMỤC HÌNHVẼ .................................................................................... 7
DANH MỤC CÁC BẢNG.............................................................................. 8
DANH MỤC CÁC TỪ VIẾT TẮT ................................................................ 9
CHƢƠNG 1: TỔNG QUAN HỆ THỐNG GIAO THÔNG TAXI BUS HÀ
NỘI ................................................................................................................ 10
1.1 Khảo sát và đánh giá thực trạng hệ thống hiện tại .............................. 10
1.2 Mục tiêu cho hệ thống mới .................................................................. 14
1.3 Ý tƣởng cho giải pháp mới có cân nhắc tính khả thi. .......................... 15
1.3.1 Phác họa giải pháp......................................................................... 15

1.3.2 Tính khả thi ................................................................................... 15
1.3.3 Kế hoạch dự án cùng với dự trù tổng quát. ................................... 20
CHƢƠNG 2: BÀI TOÁN ĐỊNH TUYẾN XE VRP .................................... 22
2.1 Giới thiệu bài toán ............................................................................... 22
2.2. Các biến thể của bài toán VRP. .......................................................... 23
2.3 Các hƣớng tiếp cận .............................................................................. 27
2.4 Bài toán giao thông taxi – bus Hà nội ................................................ 32
CHƢƠNG 3: PHÂN TÍCH HỆ THỐNG ...................................................... 36
3.1 Phân tích về chức năng .................................................................... 36
3.1.1 Biểu đồ phân cấp chức năng ......................................................... 36
3.1.2 Đặc tả các chức năng lá ................................................................. 37
3.2 Quy trình nghiệp vụ ............................................................................. 39
3.2.1 Biểu đồ luồng dữ liệu mức khung cảnh ........................................ 39
3.2.2 Biểu đồ luồng dữ liệu mức đỉnh .................................................... 39
3.2.3 Biểu đồ luồng dữ liệu mức dƣới đỉnh ........................................... 40
CHƢƠNG 4: THIẾT KẾ HỆ THỐNG ......................................................... 46
4.1 Thiết kế mô hình tổng thể .................................................................... 46
4.1.1 Hoàn chỉnh các DFD hệ thống ...................................................... 46
4.1.2 Kiến trúc hệ thống ......................................................................... 50
4.2 Thiết kế dữ liệu .................................................................................... 53
4.2.1 Thiết kế logic CSDL ..................................................................... 53
4.2.2 Thiết kế CSDL Vật lý.................................................................... 56
4.3 Thiết kế giao diện ................................................................................ 59
4.4 Thiết kế báo cáo ................................................................................... 60
CHƢƠNG 5: CÀI ĐẶT THỬ NGHIỆM HỆ THỐNG ................................ 60
5.1. Cài đặt hệ thống thử nghiệm ............................................................... 60
5.1.1 Cài đặt CSDL ................................................................................ 60
5.1.2 Cài đặt chƣơng trình ...................................................................... 64
5



Bài toán giao thông taxi – bus Hà Nội

5.1.2.1 Giải thuật phân nhóm khách hàng trƣớc của Fisher và Jakuma. 64
5.1.2.2 Giải thuật Tabu Search ............................................................... 65
5.2 Một số hình ảnh của hệ thống .............................................................. 66
CHƢƠNG 6: KẾT LUẬN ............................................................................ 68
6.1 Đã làm đƣợc ......................................................................................... 68
6.2 Hạn chế ................................................................................................ 68
6.3 Hƣớng phát triển .................................................................................. 68
TÀI LIỆU THAM KHẢO ............................................................................. 69

6


Bài toán giao thông taxi – bus Hà Nội

DANHMỤC HÌNHVẼ
Hình 1. Mô hình quản lý phƣơng tiện giao thông bằng GPS .............................. 16
Hình 2. Giao diện hệ thống thực tế gpsgiaothong.vn .......................................... 18
Hình 3. Báo cáo hoạt động của xe trên hệ thống thực tế ..................................... 19
Hình 4. Theo dõi lộ trình xe trên hệ thống thực tế ............................................... 19
Hình 5. Tìm kiếm thông tin của xe trong hệ thống thực tế .................................. 19
Hình 6. Biểu đồ phân cấp chức năng ................................................................... 37
Hình 7. Biểu đồ luồng dữ liệu mức khung cảnh .................................................. 39
Hình 8. Biểu đồ luồng dữ liệu mức đỉnh .............................................................. 40
Hình 9. Biểu đồ luồng dữ liệu chức năng quản lý khách hàng ............................ 41
Hình 10. Biểu đồ luồng dữ liệu chức năng quản lý bản đồ ................................. 42
Hình 11. Biểu đồ luồng dữ liệu chức năng quản lý xe......................................... 43
Hình 12. Biểu đồ luồng dữ liệu chức năng định tuyến xe ................................... 44

Hình 13. Biểu đồ luồng dữ liệu chức năng báo cáo ............................................. 45
Hình 14. Biểu đồ luồng hệ thống của chức năng quản lý khách hàng................. 46
Hình 15. Biểu đồ luồng hệ thống của chức năng quản lý bản đồ ........................ 47
Hình 16. Biểu đồ luồng hệ thống của chức năng quản lý xe ............................... 48
Hình 17. Biểu đồ luồng hệ thống chức năng của điều phối xe ............................ 49
Hình 18. Biểu đồ luồng hệ thống của chức năng bảo báo ................................... 50
Hình 19. Mô hình ứng dụng 3 lớp ........................................................................ 51
Hình 20. Sơ đồ ERD điều phối taxi - bus ............................................................ 55
Hình 21. Giao diện báo cáo của hệ thống ............................................................ 59
Hình 22. Mã thuật toán clustering ........................................................................ 65
Hình 23. Giao diện hệ thống thử nghiệm ............................................................. 66
Hình 24. Hiển thị thông tin điều xe ...................................................................... 67

7


Bài toán giao thông taxi – bus Hà Nội

DANH MỤC CÁC BẢNG
Bảng 1. Thống kê số lƣợng Taxi đang hoạt động kinh doanh ở Hà nội hiện nay 12
Bảng 2. Dự trù thiết bị của giải pháp ................................................................... 20
Bảng 3. Liên kết giữa các thực thể ....................................................................... 54
Bảng 4. Bảng in báo cáo ...................................................................................... 60

8


Bài toán giao thông taxi – bus Hà Nội

DANH MỤC CÁC TỪ VIẾT TẮT

Từ viết tắt

Chú giải

VTHKCC

Vận tải hành khách công cộng

VRP

Bài toán định tuyến xe (Vehicle Routing Problem)

DFD

Biểu đồ luồng dữ liệu (Data Flow Diagram)

CSDL

Cơ sở dữ liệu

GPS

Hệ thống định vị toàn cầu (Global Positioning System)

GPRS

Dịch vụ truyền tin qua sóng radio (General Packet Radio Service)

SMS


Dịch vụ thông báo tin ngắn (Short Message Services)

GIS

Hệ thống thông tin địa lý (Geographic Information System)

9


Bài toán giao thông taxi – bus Hà Nội

CHƢƠNG 1: TỔNG QUAN HỆ THỐNG GIAO THÔNG TAXI BUS HÀ
NỘI
1.1 Khảo sát và đánh giá thực trạng hệ thống hiện tại
Hà Nội hiện nay với tổng diện tích 922,8km 2 cùng với diện tích rất lớn đƣợc sáp
nhập từ tỉnh Hà Tây (cũ) trong đó nội thành là trên 70km 2 , gồm 9 Quận nội thành cũ,
quận Hà Đông, Bắc Từ Liêm, Nam Từ Liêm (mới) cùng thị xã Sơn Tây và nhiều
huyện ngoại thành khác. Dân số Hà Nội hiện nay khoảng trên 3,5 triệu ngƣời, ngoài
ra thƣờng xuyên còn có một lƣợng khách vãng lai và cƣ dân tại các tỉnh xung quanh
tập trung về Hà Nội làm ăn sinh sống đƣa dân số lên trên 4,2 triệu ngƣời. Với tốc độ
tăng trƣởng kinh tế bình quân 9,7% năm Hà Nội đang là một trung tâm chính trị, kinh
tế, văn hoá lớn xứng đáng Thủ đô của cả nƣớc.
Hơn nữa, lƣợng khách Quốc tế du lịch, công tác, thƣơng mại… vào Việt Nam ngày
càng tăng nhanh và số khách đến Hà Nội cũng không ngừng phát triển. Nhu cầu phát
triển Du lịch ngày càng tăng của cả nƣớc và xu thế hội nhập về hoạt động kinh doanh
du lịch trong khu vực cũng nhƣ trên thị trƣờng thế giới. Vận chuyển hành khách là một
dịch vụ cấu thành trong sản phẩm du lịch mà hoạt động du lịch không thể thiếu đƣợc.
Ngoài ra, trên địa bàn Thành phố Hà Nội có hơn 200 Giấy phép đầu tƣ, hàng trăm
văn phòng đại diện và Chi nhánh Ngân hàng nƣớc ngoài. Tỷ lệ gia tăng hàng năm của
số khách sạn và văn phòng đại diện trong các năm vừa qua tại Thành phố Hà Nội

khoảng 8% năm. Ngƣời nƣớc ngoài làm việc trong các cơ sở nàycó nhu cầu sử dụng
phƣơng tiện có sẵn trong nƣớc đi lại rất nhiều, thay vì sử dụng phƣơng tiện cá nhân, tự
trang bị có chi phí rất cao.
Tuy nhiên có một vấn đề đang làm cho không những chỉ riêng Hà Nội mà cả các
thành phố của các nƣớc đang phát triển cũng phải quan tâm: đó là do kinh tế tăng
trƣởng với tốc độ nhanh làm cho cơ sở hạ tầng không phát triển theo kịp. Nội thành Hà
Nội có hơn 400 đƣờng phố với tổng chiều dài hơn 300km. Nhƣng mạng lƣới đƣờng

10


Bài toán giao thông taxi – bus Hà Nội

phân bố không đều, chất lƣợng thấp, đƣờng hẹp đã ảnh hƣởng rất lớn đến hoạt động
giao thông mà đặc biệt là giao thông công cộng.
Qua nghiên cứu xu hƣớng phát triển “vận tải hành khách công cộng” (VTHKCC) ở
các thành phố của các nƣớc phát triển cũng nhƣ đang phát triển đều có chung một quan
điểm đó là: đối với một thành phố có số dân trên 4 triệu ngƣời nhƣ Hà Nội hiện nay, để
giải quyết đƣợc nhu cầu đi lại thì nhất thiết phải có 2 hệ thống VTHKCC chủ yếu: đó
là Tàu điện ngầm và xe Buýt công cộng. Nhƣng hiện nay Hà Nội chƣa có tàu điện
ngầm mà nếu có thì cũng phải trong tƣơng lai 10-15 năm nữa. Bởi vậy hệ thống
VTHKCC hiện nay chủ yếu vẫn dựa vào 1.000 xe buýt các loại và khoảng 2.650 xe
Taxi.
Xe Buýt Hà Nội hiện nay đang ngày một mở rộng các tuyến, chất lƣợng phục vụ
về cơ bản đã đƣợc nâng cao nhƣng vẫn còn rất nhiều hạn chế, không tiện lợi đối với
hầu hết ngƣời dân tham gia sử dụng phƣơng tiện vận tải công cộng. Các tuyến đƣờng
nhỏ, khu dân cƣ buôn bán và ngoài giờ phục vụ của các tuyến xe buýt nên không tránh
khỏi sự bất lợi khi tham gia sử dụng loại phƣơng tiện này. Ngoài ra do mạng lƣới
đƣờng phân bố không đều, chất lƣợng thấp, đƣờng hẹp. Số đƣờng phố có thể bố trí xe
Buýt chạy qua chiếm 60% nhƣng tập trung chủ yếu vào các tuyến đƣờng chính, khả

năng phát triển mạng lƣới xe buýt phủ khắp Hà Nội là không thể thực hiện đƣợc.
Trong một vài năm gần đây, Thành phố rất chú trọng đầu tƣ mở rộng và nâng cấp
cơ sở hạ tầng giao thông, tuy vậy khả năng phát triển các loại hình vận tải hành khách
công cộng có sức chuyên chở lớn trong khu vực nội thành là hết sức hạn chế. Do vậy
các phƣơng tiện vận tải công cộng nhƣ MINIBUS, Taxi đang có xu hƣớng phát triển
mạnh.
Giao thông taxi phục vụ cho các đối tƣợng có nhu cầu đi lại với yêu cầu cao về
thời gian và chất lƣợng phục vụ: nhanh chóng, an toàn, tiện nghi và vận chuyển hành
khách tại các tuyến đƣờng hẹp mà xe bus không thể vào đƣợc. Đối tƣợng chủ yếu sử

11


Bài toán giao thông taxi – bus Hà Nội

dụng taxi là cán bộ, công chức nhà nƣớc, khách du lịch, các doanh nghiệp vừa và nhỏ,
các thƣơng gia và một bộ phận dân cƣ có thu nhập trung bình trở lên.
Theo số liệu thống kê của Sở Giao thông vận tải Hà nội, hiện nay Hà nội có 114
doanh nghiệp đƣợc cấp phép và đang hoạt động kinh doanh vận tải bằng taxi với hơn
15.000 phƣơng tiện. Dƣới đây là một số hãng taxi đang hoạt động (xem bảng 1)
Bảng 1. Thống kê số lƣợng Taxi đang hoạt động kinh doanh ở Hà nộihiện nay
STT

Đơn vị

Số xe

1

Công ty xe Du lịch Hà nội


250

2

Công ty cổ phần Taxi Hà nội

250

3

Công ty Vận tải Du lịch Hà nội

40

4

Cty TNHH PTCN và TM

100

5

Cty cổ phần Mai linh Thủ đô

105

6

Cty Hƣơng lúa


50

7

Cty CP Mai linh Hà nội

120

8

Cty Thƣơng mại Hƣơng Nam

30

9

Cty TNHH VT-TM-DL Sài Gòn

80

10

Cty TNHH Triệu Quốc Đạt

50

11

Cty CP Thanh Nga


80

12

Cty CP Đại Phúc

50

13

Cty TNHH Thanh Xuân

30

14

Cty TNHH Hoàng Hợp

30

15

Cty TNHH Thành Hƣng

70

16

Cty dịch vụ hàng không Nội bài


80

17

Taxi Thăng Long

60

18

Cty TNHH Tân Hoàng Minh

120

19

Cty CP đầu tƣ & TM Vistar

130

12


Bài toán giao thông taxi – bus Hà Nội

20

Taxi VIC


70

21

Taxi Long Biên

80

22

Taxi Hùng Vƣơng

90

23

Taxi Phù Đổng

80

24

Taxi Vạn Xuân

100

25

Taxi Ba Sao


90

26

Taxi Mỹ Đình

80

Ngoài ra,toàn thành phố còn có khoảng 1200 xe ô tô tƣ nhân tham gia vận chuyển
khách theo hình thức: thuê chuyển, thuê tháng, hợp đồng vận chuyển khách du
lịch,…trên cơ sở thỏa thuận.
Mỗi hãng taxi có một tổng đài callcenter cho khách hàng gọi lên và yêu cầu xe,
một đội ngũ nhân viên điều phối xe và đội xe.
Để phục vụ khách hàng tại các khu vực khác nhau một cách nhanh chóng, mỗi
hãng xe có một số các điểm đỗ xe, tập kết tại các vị trí trong thành phố. Tài xế khi bắt
đầu công việc sẽ đƣợc nhận xe và chạy theo ca
Hoạt động của hệ thống hiện tại
Khi khách hàng có nhu cầu di chuyển trong thành phố, khách hàng gọi lên tổng đài
yêu cầu xe đến đón và cung cấp thông tin, tổng đài tiếp nhận yêu cầu của khách hàng
và thông báo cho khách hàng chờ, thông báo bằng bộ đàm cho các xe ở gần khách hàng
đến đón khách.
Tồn tại và yếu kém:
 Thông tin về khách hàng mới đƣợc thông báo với các tài xế của hãng thông qua
bộ đàm, tổng đài không chỉ định và biết đƣợc xe nào đến đón khách, dẫn tới
hiện tƣợng các tài xế tranh giành khách. Tại một thời điểm, nhiều xe có thể cùng
chạy đến một chỗ để đón khách, gây lãng phí trong khi nơi có khách cần lại

13



Bài toán giao thông taxi – bus Hà Nội

không có xe đến đón. Chƣa kể đến việc các tài xế phóng nhanh trên đƣờng đón
khách, có thể mang lại đe dọa về an toàn giao thông.
 Do việc điều phối không đƣợc chuẩn bị trƣớc, dẫn tới hiện tƣợng khách hàng
phải chờ taxi (hoặc không chờ đƣợc có thể bắt taxi của hãng khác), và cả trƣờng
hợp tài xế taxi phải chờ khách hàng, gây tổn thất kinh tế đối với khách hàng và
doanh nghiệp.
 Theo dõi hành trình xe chủ yếu qua các báo cáo của tài xế, hoặc qua phƣơng
tiện checkpoint không thực sự chính xác.
 Giá thành cao do mỗi hành khách đƣợc phục vụ riêng bởi một chiếc taxi. Có khi
một chiếc 7 chỗ chỉ có một khách đi
 Chính sách quản lýgặp nhiều khó khăn. Với phƣơng pháp dùng thiết bị liên lạc
radio thƣờng đƣợc áp dụng trên xe taxi, hệ thống này chỉ có thể xác định vị trí
xe và lộ trình xe thông qua báo cáo của ngƣời lái, nên ngƣời điều hành khó xác
minh đƣợc độ tin cậy của thông tin, cũng nhƣ khó bao quát đƣợc mật độ xe
trong từng khu vực. Phƣơng pháp thiết lập các trạm báo cáo chỉ có thể xác định
đƣợc vị trí và tình trạng xe khi xe có mặt tại trạm, và cũng tốn kém, ảnh hƣởng
không nhỏ đến chi phí vận tải. Còn phƣơng pháp quy định chuẩn thời gian vận
hành thì không có đƣợc sự mềm dẽo cần thiết trong quản lý, do không bám sát
đƣợc thực tế giao thông, nên gây ra không ít áp lực bất lợi cho ngƣời lái xe.
1.2 Mục tiêu cho hệ thống mới
Hệ thống giao thông taxi – bus tƣơng lai phải quản lý trƣớc đƣợc hành trình đón,
trả khách, các thông tin hoạt động của xe đƣợc gửi về, quản lý tốt thông tin khách
hàng, điều đúng và đủ xe đến đón khách, giảm chi phí khi chạy không khách, và thời
gian chờ khách, thời gian chờ của hành khách.
Để có thể thực hiện mục tiêu trên, hệ thống phải có khả năng phân tích dữ liệu
đƣờng phố, và dữ liệu xe để cung cấp các lộ trình chính xác, tính toán trƣớc các chi phí

14



Bài toán giao thông taxi – bus Hà Nội

1.3 Ý tƣởng cho giải pháp mới có cân nhắc tính khả thi.
1.3.1 Phác họa giải pháp
Theo quy định của bộ Giao thông vận tải, hầu hết các xe đã đƣợc trang bị hộp đen
GPS, gửi dữ liệu hoạt động của xe về một server chung.
 Giải pháp 1: Mỗi xe trang bị một hộp đen GPS, thông tin hành trình của xe đƣợc
lƣu lại tại một server chung phục vụ cho việc xem lại và phân tích kết quả, từ đó
tìm ra các đƣờng đi tối ƣu cho lần sau. Phƣơng pháp này tốn kém vì việc tính
toán thực hiện sau khi đã hoàn thành, việc tính toán là thủ công, trong khi các
tuyến xe đón, trả khách nhiều khi không cố định, khó khăn hơn.
 Giải pháp 2: Mỗi xe trang bị thêm một thiết bị dẫn đƣờng, rất khó thực hiện tối
ƣu việc đón nhiều hành khách nhất, với chi phí thấp nhất.
 Giải pháp 3: Tất cả các đƣờng đi đƣợc tính toán trƣớc tại một server trung tâm,
mỗi xe đƣợc điều phối sẽ thực hiện đón, trả khách theo kịch bản mà server gửi
về. Khách hàng có thể gọi điệntrƣớc lên tổng đài và đặt lịch đón
1.3.2 Tính khả thi
a. Giải pháp quản lý phƣơng tiện sử dụng hệ thống định vị tòan cầu
Giải pháp quản lý sử dụng hệ thống định vị toàn cầu (GPS) để quản lý phƣơng tiện
giao thông đang đƣợc coi là hiệu quả và đa dụng nhất hiện nay, cũng là phƣơng pháp
quản lý đƣợc áp dụng rộng rãi nhất trên thế giới.
Mô hình hoạt động cơ bản nhất của một hệ thống GPS Tracking gồm một thiết bị
liên lạc đƣợc gắn trên xe, đón nhận việc thu tín hiệu vệ tinh từ hệ thống định vị toàn
cầu GPS để xác định tọa độ chính xác của xe. Thiết bị cũng thu thập các thông tin hữu
ích khác nhƣ trạng thái tắt/mở của động cơ, tốc độ vận hành, hƣớng di chuyển của
xe,…

15



Bài toán giao thông taxi – bus Hà Nội

Những thông tin này đƣợc chuyển về trung tâm xử lý dữ liệu thông qua mạng điện
thọai GSM/CDMA hiện hành (sử dụng kết nối GPRS hoặc SMS). Tại đây thông tin
đƣợc kết hợp với hệ thống bản đồ để xác định vị trí thực tế của xe, đồng thời có thể
đƣợc xử lý và đƣa ra các báo cáo theo các yêu cầu khác nhau của các nhà quản lý.
Thông thƣờng, các thông tin sau khi xử lý sẽ đƣợc đƣa lên mạng internet hoặc intranet
để tiện cho việc quản lý nhanh chóng và chính xác.

Hình 1. Mô hình quản lý phƣơng tiện giao thông bằng GPS

16


Bài toán giao thông taxi – bus Hà Nội

Nhƣ vậy với tính liên tục của hệ thống định vị GPS và mạng điện thọai di động, việc
quản lý có thể đƣợc thực hiện mọi lúc mọi nơi, áp dụng đƣợc với bất kỳ vật thể chuyển
động nào.
b. Hệ thống đã triển khai gpsgiaothong.vn
Gpsgiaothong là hệ thống quản lý điều hành vận tải sử dụng hộp đen GPS kết hợp
với công nghệ truyền dữ liệu không dây (GPRS) và bản đồ số (GIS) giúp quản lý
phƣơng tiện và tài sản một cách dễ dàng, góp phần giải quyết hiệu quả bài toán chi phí
cho cá nhân và doanh nghiệp hoạt động trong các lĩnh vực liên quan đến hoạt động vận
tải. Địa chỉ:
Chức năng cung cấp:
 Xe ở đâu, vận tốc bao nhiêu, mức nhiên liệu, tình trạng đóng cửa, tình trạng sử
dụng điều hòa, hình ảnh chụp từ xe

 Xem lại lộ trình cũ của xe cùng với tất cả những thông tin chi tiết nhƣ trên
 Báo cáo thời điểm xe vƣợt quá tốc độ cho phép.
 Báo cáo các thời điểm, thời gian dừng đỗ.
 Báo cáo mức tiêu hao nhiên liệu, phát hiện các điểm tiêu hao nhiên liệu bất
thƣờng
 Cung cấp đầy đủ hình ảnh chụp từ xe
 Báo cáo thời gian lái xe của tài xế.
 Báo cáo thời điểm, thời gian, số lần xe vào/ra khỏi bến bãi, trạm dừng
Một số hình ảnh về hệ thống gpsgiaothong:

17


Bài toán giao thông taxi – bus Hà Nội

Hình 2. Giao diện hệ thống thực tế gpsgiaothong.vn
Chức năng báo cáo hoạt động của xe
Mọi thông tin về hoạt động của xe: vị trí, xăng dầu, tốc độ, trạng thái đƣợc hiển thị
trên trang báo cáo

18


Bài toán giao thông taxi – bus Hà Nội

Hình 3. Báo cáo hoạt động của xe trên hệ thống thực tế
Theo dõi lộ trình của xe

Hình 4. Theo dõi lộ trình xe trên hệ thống thực tế


Hình 5. Tìm kiếm thông tin của xe trong hệ thống thực tế

19


Bài toán giao thông taxi – bus Hà Nội

1.3.3 Kế hoạch dự án cùng với dự trù tổng quát.
Hệ thống gồm 04 thành phần chính:
Server điều phối xe thông minh: lƣu trữ dữ liệu khách hàng và luật điều phối xe. Mỗi
công ty taxi sẽ có server riêng.
Call center server: hệ thống server xử lý các cuộc gọi khách hàng (đã có).
Phần mềm điều xe: mỗi nhân viên điều xe sẽ có một phần mềm điều phối xe riêng
Phần mềm quản lý: trợ giúp cho công tác quản lý, đánh giá tình hình kinh doanh và hệ
thống bảng biểu báo cáo.
Dự trù thiết bị:
Bảng 2. Dự trù thiết bị của giải pháp
Số

STT Thiết bị

lƣợng

Đơn giá

Thành tiền

80.000.000

80.000.000


Server:
- CPU: 2 x Intel® Xeon® 6-Core
Processor

E5-2620,

2.0GHz,

15MB, 7.20GT/s QPI, LGA2011,
- RAM: 16GB(4x4GB) DDR3 1333
240-Pin DDR3 ECC Registered
(PC3
1

10666)

- HDD: 2 x Dell 500GB SATA
3Gb/s
-

7.2K
DVD:

- RAID:

RPM
DVD

Enterprise

Slim

Dell™ PERC H710

Integrated RAID Controller 512MB
Cache

Hardware

RAID

0,1,5,6,10,50,60

20

01


Bài toán giao thông taxi – bus Hà Nội

- NIC: Integrated Two Broadcom
5709C dual-port Gigabit Ethernet
(4port)
- Power Supply: Dual, Hot-plug,
Redundant Power Supply (1+1),
750W.
-

Supports


64-bit

Operating

Systems
Đƣờng truyền internet
2

3

-

1Gbs

-

1 Public IP

01

01

Firewall ASA5510-AIP10-K9

15,000,000/

15,000,000/

tháng


tháng

43.300.000
VNĐ

43.300.000 VNĐ

218.300.000

Tổng chi phí ban đầu:

VNĐ

21


Bài toán giao thông taxi – bus Hà Nội

CHƢƠNG 2: BÀI TOÁN ĐỊNH TUYẾN XE VRP
2.1Giới thiệu bài toán
Bài toán Vehicle Routing Problem - gọi tắt là VRP là bài toán mà trong đó ta có
sẵn một tập các xe và một tập các khách hàng, mỗi khách hàng yêu cầu một số lƣợng
hàng nhất định, yêu cầu của bài toán là phải phân phối hàng và tìm đƣờng đi cho các xe
dựa trên một số mục tiêu cho trƣớc sao cho tất cả các khách hàng đều phải đƣợc giao
hàng, một trong những mục tiêu phổ biến nhất là cực tiểu hóa tổng thời gian vận
chuyển của tất cả các xe. Bài toán quen thuộc ngƣời đƣa thƣ (Travelling Salesman
Problem - gọi tắt là TSP) chính là một trƣờng hợp đặc biệt của bài toán VRP với một
xe giao hàng duy nhất (chính là ngƣời đƣa thƣ).
Bài toán VRP và các biến thể của nó đều thuộc lớp các bài toán NP khó. Đây là
một trong những bài toán có ứng dụng thực tế rất rộng lớn và đã nhận đƣợc sự quan

tâm, nghiên cứu của rất nhiều nhà khoa học trên thế giới trong suốt 50 năm qua. Trong
bài toán này, các xe (vehicle) xuất phát từ các kho hàng (depot) và đi giao hàng cho các
khách hàng (customer), sau đó quay trở về lại kho hàng. Một số khái niệm chính của
bài toán gồm:
-

Xe (vehicle): các phƣơng tiện dùng để chuyên chở hàng, có thể có nhiều loại xe
khác nhau, chẳng hạn nhƣ xe tải nhỏ, xe tải lớn, xe gắn máy,... Các khái niệm
gắn liền với loại xe bao gồm: sức chứa của xe (capacity), chi phí vận chuyển
(gồm hai loại thông dụng: chi phí cố định - fixed cost - là chi phí cần thiết để xe
có thể khởi hành, nó không phụ thuộc vào độ dài quãng đƣờng mà xe phải đi;
chi phí động - variable cost là chi phí tiêu tốn trên từng đơn vị quãng đƣờng mà
xe phải đi), quãng đường tối đa mà xe có thể đi trong một ngày (route length),
loại mặt hàng (commodit type) mà xe có thể chở, …

-

Kho hàng (depot): là nơi chứa hàng hóa, các xe sẽ lấy hàng tại kho để đi giao
hàng cho các khách hàng, sau khi giao xong, xe sẽ quay trở về lại kho hàng

22


Bài toán giao thông taxi – bus Hà Nội

-

Khách hàng (customer): khách hàng có thể chỉ nhận hàng do xe giao tới, nhƣng
cũng có thể vừa nhận hàng (linehaul customer), vừa lấy hàng (backhaul
customer). Các khái niệm đi kèm với khách hàng gồm: số lượng hàng mà khách

yêu cầu (demand), loại mặt hàng mà khách yêu cầu (commodity type), khoảng
thời gian (time window) mà khách hàng cho phép xe đến giao hàng (ví dụ:
khoảng thời gian của khách hàng A là [2p.m, 4p.m] nghĩa là khách hàng A chỉ
cho phép xe đến giao hàng (hoặc lấy hàng) trong khoảng thời gian từ 2p.m đếm
4p.m, thời gian thực hiện việc giao (nhận) hàng (service time),...

-

Tuyến đường (route): tuyến đƣờng của một xe là một chu trình, với điểm xuất
phát và điểm kết thúc là kho hàng của xe, các điểm thành phần của chu trình
tƣơng ứng với các khách hàng mà xe ghé qua để giao (lấy) hàng.

2.2. Các biến thể của bài toán VRP.
Bài toán VRP có rất nhiều biến thể khác nhau dựa trên yêu cầu cụ thể của các bài
toán thực tế. Các biến thể này đã tạo thành các nhánh nghiên cứu khác nhau, tất nhiên
các phƣơng pháp giải quyết các biến thể cũng có thể đƣợc chỉnh sửa để áp dụng qua lại
lẫn nhau. Một số biến thể quan trọng của bài toán VRP bao gồm:
-

Bài toán VRP với khoảng cách bất đối xứng (Asymmetric VRP, gọi tắt là
AVRP): bài toán VRP mà trong đó, đồ thị biểu diễn đƣờng đi là một đồ thị có
hƣớng. Hầu hết các bài toán VRP trong thực tế đều thuộc dạng này.

-

Bài toán VRP với nhiều kho hàng (Multi-Depot VRP, gọi tắt là MDVRP): bài
toán với nhiều kho hàng khác nhau, mỗi xe sẽ phụ thuộc vào một kho hàng duy
nhất, đƣợc gọi là kho hàng chủ (home depot) của xe.

-


Bài toán VRP với ràng buộc sức chứa (Capacitated Vehicle Routing Problem,
gọi tắt là CVRP): trong bài toán này, mỗi loại xe có một sức chứa (capacity)
khác nhau, yêu cầu bài toán là phải tìm đƣờng đi cho các xe sao cho tổng lƣợng
hàng mà xe phải chở trong một tuyến đƣờng không đƣợc vƣợt quá sức chứa của

23


Bài toán giao thông taxi – bus Hà Nội

xe. Nếu thay ràng buộc sức chứa bằng ràng buộc về độ dài tối đa của quãng
đƣờng mà mỗi xe đi, ta có một biến thể khác, đó là bài toán DVRP (DistanceConstrained VRP): gắn với mỗi loại xe là một tham số thể hiện độ dài quãng
đƣờng tối đa mà mỗi xe có thể đi. Yêu cầu bài toán là phải tìm đƣờng đi cho các
xe sao cho tổng quãng đƣờng mà mỗi xe phải đi không đƣợc vƣợt quá tham số
này.
-

Bài toán VRP với ràng buộc khoảng thời gian (VRP with Time Windows, gọi tắt
là VRPTW): trong bài toán này, mỗi khách hàng sẽ chỉ cho phép xe đến giao
hàng trong một khoảng thời gian cho phép (time windows) nhất định, khoảng
thời gian này đƣợc biểu diễn bởi đoạn [ai, bi] (tƣơng ứng với khách hàng thứ i),
nếu xe đến giao hàng cho khách hàng thứ i vào trƣớc thời điểm ai, xe sẽ phải
đứng chờ cho đến thời điểm ai mới đƣợc giao hàng, đồng thời việc giao hàng
của xe cho khách hàng thứ i cần kết thúc trƣớc thời điểm bi.

-

Bài toán VRP với yêu cầu giao và nhận hàng (VRP Pickup and Delivery, gọi tắt
là VRPPD): bài toán này cho phép xe thực hiện cả hai chức năng - lấy hàng

(pickup) từ một số khách hàng và đem đi giao (delivery) cho khách hàng khác,
bài toán này thƣờng áp dụng cho các dịch vụ vận chuyển hàng, trong đó, khách
hàng sẽ yêu cầu xe đến chỗ mình để nhận hàng và giao đến cho ngƣời nhận (một
khách hàng khác). Khi đó, tất nhiên xe phải đến gặp khách hàng thứ nhất để lấy
hàng trƣớc, rồi mới có hàng để giao đến cho ngƣời nhận. Nhƣ vậy, trong bài
toán này sẽ có thêm một loại ràng buộc mới: ràng buộc thứ tự đến gặp khách
hàng (precedence constraint). Các xe phải tuân thủ thứ tự này, nghĩa là phải gặp
khách hàng đặt giao hàng trƣớc, rồi mới đƣợc đến gặp khách hàng cần nhận
hàng.

-

Bài toán VRP với yêu cầu giao hàng trước (VRP with Backhauls, gọi tắt là
VRPB): tƣơng tự nhƣ bài toán VRPPD, bài toán này cũng cho phép xe giao hàng
và nhận hàng, nhƣng có một chút khác biệt: xe không đến gặp khách hàng để

24


Bài toán giao thông taxi – bus Hà Nội

lấy hàng rồi giao cho khách hàng khác nữa mà ràng buộc thứ tự gặp khách hàng
ở đây sẽ là: xe phải đi giao hàng cho tất cả các khách hàng cần nhận (Linehaul
customers) trƣớc, rồi sau đó mới đến gặp các khách hàng cần giao (Backhaul
customers) để lấy hàng đem về kho. Wade và Salhi [10] đã đề nghị một biến thế
khác của bài toán VRPB, trong đó, xe không cần phải giao hết hàng rồi mới
đƣợc nhận hàng, mà có thể nhận hàng sớm hơn (tại một thời điểm nào đó trong
lúc giao hàng, thời điểm này đƣợc xác định dựa trên kinh nghiệm của tài xế,
trạng thái hàng của xe tại thời điểm đó,…).
-


Bài toán VRP cho phép một xe đi nhiều chuyến (bài toán này có rất nhiều tên gọi
khác nhau, bao gồm: VRP with multiple use of vehicles, VRP with multi-trips,
VRP with multiple trips, VRP with multiple vehicle trips, gọi tắt chung là
VRPM): trong bài toán này, mỗi xe có thể chạy nhiều hơn một tuyến đƣờng,
nghĩa là một chiếc xe có thể xuất phát từ kho hàng, đi giao hàng, quay trở về
kho hàng và lại lấy hàng đi giao tiếp cho đến khi tổng thời gian giao hàng của xe
chạm mức cho phép.

-

Bài toán VRP cho phép chia nhỏ đơn hàng (VRP with split delivery)[13]: trong
bài toán này, mỗi đơn đặt hàng của khách hàng đƣợc phép phân nhỏ ra thành
các đơn đặt hàng với số lƣợng nhỏ hơn, khi đó, một khách hàng có thể đƣợc
giao hàng bởi nhiều hơn một xe. Khi các đơn đặt hàng của các khách hàng có
kích thƣớc quá lớn, việc chia nhỏ các đơn đặt hàng này ra sẽ giúp tận dụng đƣợc
tối đa sức chứa của xe.

-

Bài toán VRP với nhiều loại xe khác nhau[11]: là bài toán với tập các loại xe có
sức chứa và chi phí vận chuyển khác nhau. Bài toán này có hai biến thể con,
gồm:
+ Bài toán VRP với đội xe cố định (Heterogeneous VRP, hoặc VRP with
Heterogeneous fleet of vehicles): Số lƣợng xe của mỗi loại là một hằng số.

25


Bài toán giao thông taxi – bus Hà Nội


+ Bài toán VRP với đội xe biến động (Mixed fleet and size VRP, Fleet Size and
Mix VRP): Số lƣợng xe của mỗi loại cũng là một biến số, nghĩa là ngoài việc
định tuyến, ta còn cần phải xác định đƣợc số lƣợng xe mỗi loại cần dùng sao
cho tốt nhất.
-

Bài toán VRP với yêu cầu loại xe phù hợp (VRP with site-dependence, gọi tắt là
SDVRP): trong bài toán này, mỗi khách hàng chỉ chấp nhận một số loại xe nhất
định, đây cũng là một yêu cầu rất thực tế, chẳng hạn nhƣ với các khách hàng
nằm trong hẻm nhỏ hoặc nằm ở đƣờng cấm xe tải lớn thì chỉ có các xe tải nhỏ
hoặc xe máy mới có thể giao hàng đến đƣợc.

-

Bài toán VRP với khách hàng được biểu diễn bởi các cung (Arc Routing
Problems )[12]: đây là một bài toán đặc biệt, khác với các bài toán VRP thông
thƣờng, trong đó, các khách hàng thay vì đƣợc biểu diễn bằng các điểm trong đồ
thị, thì sẽ đƣợc biểu diễn bằng các cung. Bài toán này xuất phát từ yêu cầu của
các bài toán thực tế, chẳng hạn nhƣ bài toán tìm đƣờng đi cho các xe dọn tuyết
trong mùa đông, rải muối, rải cát lên mặt đƣờng băng để hạn chế trơn trƣợt, khi
đó, các vị trí cần rải muối, cát hoặc lấy tuyết không còn là các điểm nữa, mà là
các đoạn đƣờng.

-

Bài toán VRP với đơn đặt hàng theo chu kì (Periodic VRP): trong bài toán này,
các xe giao hàng cho mỗi khách hàng trong nhiều ngày (gọi là một chu kì), mỗi
xe có thể gặp một khách hàng nhiều hơn một lần trong suốt chu kì. Mỗi khách
hàng sẽ có một tham số đi kèm, quy định số lần mà xe phải đến giao hàng cho

khách trong suốt chu kì. Một ứng dụng thực tế của bài toán này là bài toán thu
gom rác với khách hàng là các siêu thị, các cửa hàng tạp hóa,…, trong đó, các
siêu thị lớn thƣờng cần gom rác ngày một lần, trong khi các cửa hàng tạp hóa
nhỏ thì chỉ cần một tuần hai lần là đủ.

-

Bài toán VRP đa mục tiêu (Multi Objective VRP): đây là hƣớng bài toán mới
đƣợc phát triển trong những năm gần đây do nhu cầu xuất phát từ thực tế. Trong
26