MỘT GIẢI PHÁP TIẾP CẬN BÀI TOÁN THIẾT LẬP LỊCH TRÌNH
VẬN TẢI TỐI ƯU ĐỐI VỚI MẠNG GIAO THÔNG CÔNG CỘNG
CÓ NHIỀU TRUNG TÂM ĐIỀU HÀNH

PHẠM HUY ĐIỂN và PHẠM XUÂN HINH

TÓM TẮT. Chúng tôi nghiên cứu bài toán xây dựng lịch trình vận tải tối
ưu cho mạng giao thông công cộng với nhiều trung tâm điều hành và đề
xuất một giải pháp khả thi dựa trên phương pháp phân rã kết hợp với một
quá trình lặp. Mỗi vòng lặp bao gồm hai bước, trong đó mỗi bước là một
bài toán tối ưu giải được.

I. Đặt vấn đề
Mục tiêu cao nhất của một mạng giao thông công cộng thành phố là đáp ứng được
các yêu cầu vận tải hành khách do cơ quan quản lý giao thông đô thị đặt ra, trên cơ sở
khảo sát nhu cầu đi lại trong thực tế. Yêu cầu này thường được thể hiện dưới dạng một tập
hợp các hành trình nối các nút giao thông cơ bản trong thành phố (với tần suất xác định,
trong một khoảng thời gian được đặt ra theo kế hoạch). Trong quá trình thực hiện các hành
trình này, xe thường phải thực hiện một số hành trình khác không có trong yêu cầu (ví dụ
như là đoạn đường từ bãi để xe cho đến điểm đầu của hành trình phục phụ đầu tiên, hay là
đoạn đường xe chạy từ điểm cuối một hành trình vừa thực thi xong cho đến điểm đầu của
hành trình khác cần thực thi tiếp theo,v.v ). Đây là phần chi phí không sinh lợi, và một
trong những mục tiêu quan trọng trong ngành giao thông là giảm thiểu các chi phí này,
dựa trên việc sắp xếp hợp lý các lịch trình và việc phân bổ các tuyến về cho các trung tâm
điều hành.
Trong thực tế, mạng lưới xe bus của một thành phố được hình thành và phát triển
qua nhiều giai đoạn, song song với sự phát triển của chính thành phố đó. Cho dù ngay từ
ban đầu nó có thể được thiết kế một cách "tối ưu", nhưng trong quá trình vận hành, với sự
mở rộng của đô thị và sự tăng trưởng không ngừng của các lực lượng tham gia giao thông,
mạng sẽ không thể giữ nguyên cấu trúc "tối ưu" ban đầu, do việc phải bổ sung thêm các
hành trình mới (xuất phát từ yêu cầu thực tế). Khi ấy, một yêu cầu tự nhiên được đặt ra là

d
.
d
+
−
Tập tất cả các trung tâm phục vụ cho mạng xe bus thành phố được ký hiệu là
D
, và
tập tất cả các điểm xuất bến và điểm nhập bến của các trung tâm này ký hiệu lần lượt là

{
}
{
}
/, /D ddD D ddD
++ −−
=∈ =∈.
Như đã nói, dựa trên kết quả khảo sát nhu cầu đi lại của dân cư trong thực tế, các cơ
quan quản lý giao thông thành phố định ra yêu cầu phục vụ đối với mạng giao thông công
cộng dưới dạng một tập hợp các hành trình chở khách cần phải thực hiện trong thành phố
(sau này còn được gọi là các hành trình bắt buộc). Mỗi hành trình như vậy, được ký hiệu
là , có điểm xuất phát (điểm đỗ đầu tiên) với thời gian khởi hành là ,và có điểm đỗ
cuối cùng là t với thời gian đến là . Ta ký hiệu
T
là tập tất cả các hành trình bắt buộc,
còn
T
(T , tương ứng) là tập hợp tất cả các điểm xuất phát (điểm đỗ cuối) của các hành
trình t . Như vậy,
t

(
)
Gt D⊆ và gọi nó là nhóm các trung tâm có thể phục vụ được
cho hành trình t . Ngược lại, mỗi trung tâm điều hành có khả năng đưa xe đi phục vụ
cho nhiều hành trình, cho nên ta có tập các hành trình có thể được phục vụ bởi xe của
trung tâm điều hành
d
, ký hiệu là . Như vậy
T∈
d
T
()
{
}
d
TtTdGt=∈ ∈ .
Liên quan đến khái niệm này, ta có
{
}
d
TtTtT
−−
=∈ ∈
d
là tập hợp các điểm xuất
phát của các hành trình trong tập , còn
d
T
{
}

d
tT∈
−
t
- Cung nhập bến nối điểm nhập bến
d
với điểm đỗ cuối cùng của một hành trình
bắt buộc nào đó. Tương tự như trên ta có khái niệm hành trình nhập bến và kèm theo
là giả thiết về sự tồn tại các hành trình nhập bến phù hợp cho mỗi hành trình bắt buộc.
−
t
+
- Cung liên kết nối điểm cuối của một hành trình (tức là ) với điểm xuất phát
của một hành trình khác
q
(tức là
q
). Trên cung đường này người ta cần phải
thực hiện một "hành trình chuyển tiếp" nếu như muốn thực thi hành trình
q
sau khi đã
thực thi hành trình , bằng chính chiếc xe đã thực hiện hành trình này. Điều này là
khả thi khi cặp hai hành trình là tương thích. Cụ thể, ta ký hiệu là
khoảng thời gian cần thiết để đi từ tới
q
. Khi thì ta nói rằng hai
hành trình và
q
là tương thích, và khi ấy ta có thể tạo ra một hành trình liên kết
(giữa hai hành trình này) có điểm xuất phát là (với thời điểm xuất phát là ) và

Δ≥
p
+
−
,pq q p
seΔ≤−
p
p
+
p
e
−
q
s
p
pp
+
=
−
se−
)
qp
,pq
Δ=∞
- Cung nối điểm nhập bến của trung tâm điều hành
d
với điểm xuất bến của nó, tức là
, được sử dụng để cho xe chạy trở lại điểm xuất bến sau khi đã thực hiện
xong một lịch trình và về nhập bến, thường được gọi là cung ngược. Các hành trình
trên cung ngược sẽ được gọi là các hành trình nội bộ. Giả thiết về sự tồn tại các các

đoạn đường nào đó để đến với điểm đỗ đầu của hành trình bắt buộc cần thực thi đầu tiên,
tức là nó phải thực thi một hành trình xuất bến. Sau khi thực thi hành trình bắt buộc, nếu
muốn thực thi tiếp một hành trình bắt buộc khác (tương thích với hành trình vừa qua) nó
sẽ phải thực thi hành trình liên kết giữa hai hành trình này. Khi thực thi xong hành trình
bắt buộc cuối cùng thì xe phải quay trở lại trung tâm, tức là đi từ điểm đỗ cuối của hành
trình này về điểm nhập bến của trung tâm, hay cũng chính là thực thi một hành trình nhập
bến. Muốn cho xe tiếp tục đi làm việc vào ngày hôm sau thì xe phải thực hiện một hành
trình từ điểm nhập bến đến điểm xuất bến của trung tâm, tức là thực hiện một hành trình
nội bộ. Một lần quay vòng xe như vậy sẽ được gọi là một lịch trình chạy xe.
Dựa vào thực tế nêu trên, ta đưa ra khái niệm lịch trình triển khai là một chuỗi các
hành trình liên tiếp kề nhau, trong đó các hành trình không tải và các hành trình bắt buộc
được bố trí đan xen nhau, khởi đầu bằng một hành trình xuất bến và kết thúc bằng một
hành trình nhập bến. Sau này, để cho gọn, ta cũng thường gọi lịch trình triển khai là lịch
trình. Khi một lịch trình được bổ sung thêm hành trình nội bộ thì ta có một chu trình. Lịch
trình được xem là hợp lệ, hay là chấp nhận được, khi có ít nhất một hành trình thuộc tập
và tồn tại một trung tâm
d
có thể phục vụ cho tất cả các hành trình có trong lịch trình
này. Mỗi lịch trình như vậy có thể được thực thi bởi một xe của trung tâm đã nói. Sau này,
khi nói rằng một hành trình thuộc (hay được phủ bởi) một lịch trình của trung tâm
d
thì
cũng có nghĩa là có một xe của trung tâm
d
thực thi hành trình đó trong khuôn khổ lịch
trình này. Khi ấy ta cũng nói rằng hành trình đó được thực thi theo lịch trình này. Từ đây
ta chỉ xét những lịch trình hợp lệ cho nên ta sẽ luôn hiểu lịch trình được đề cập tới là hợp
lệ.
T
Mỗi hành trình được gán một trọng số (hay chi phí) phụ thuộc khoảng cách, thời

=
d
∈ là tập hợp tất cả các cung đường cần thực hiện (đặt ra trong
kế hoạch của cơ quan quản lý giao thông), có thể được phục vụ bởi trung tâm
d
.
-
()
{
}
,
xuat
d
Adtt
+−
=
d
T∈ là tập hợp tất cả các cung xuất bến (từ trung tâm
d
). Tập
các hành trình có thể trên các cung này (ứng với các thời điểm khác nhau) được gọi là
tập các hành trình xuất bến (của trung tâm
d
) và được ký hiệu là .
ht x
d
A
−
-
()

pqq
≤ là tập hợp tất cả các cung chuyển tiếp
giữa các cặp hành trình tương thích trong tập . Tập các hành trình liên kết (có thể
thực hiện trên các cung này) sẽ được ký hiệu là . Lưu ý rằng, giữa hai hành trình
tương thích chỉ có duy nhất một hành trình liên kết (như đã nói ở trên), còn trên một
cung chuyển tiếp có thể có nhiều hành trình liên kết (được thực hiện vào các thời điểm
khác nhau).
d
T
ht lk
d
A
−
Như vậy, tập các hành trình không tải mà trung tâm
d
có thể thực hiện là
{
}
0
:
ht kt ht x ht n ht lk
dddd
AAAA
−−−−
=∪∪∪d
q
d
d
p
d

p p
ht
d
A
d
K
ht ht
d
AA×
ht
d
pA∈
() p
Để hình dung về cấu trúc mạng giao thông, ta có thể thiết lập đồ thị của nó dựa trên
các tập cung đường đã định nghĩa ở trên. Trước hết, ta lập đồ thị của mạng do trung tâm
quản lý, đó là đồ thị có hướng , với
d
()
,
dd
DVA=
{
}
,
dd
d
VddTT
+− − +
=∪∪ là tập hợp các đỉnh,
(

=
i
∪
i
∪
Thông thường, người ta thường xây dựng đồ thị cho từng trung tâm riêng. Để cho dễ
phân biệt 2 loại hành trình bắt buộc và không tải, người ta thường biểu diễn các hành trình
bắt buộc bằng các cung song song với nhau (cùng hướng) và được nối với điểm nhập bến
(hay điểm xuất bến) bằng các cung nhập bến (tương ứng, cung xuất bến) trông giống như
hình rẽ quạt. Các cung liên kết chính là các cung "nối chéo" từ đuôi hành trình bắt buộc
này sang đầu hành trình bắt buộc khác.
Đồ thị cho nhiều trung tâm được ghép từ nhiều đồ thị của từng trung tâm độc lập
(xem ví dụ trong hình vẽ, trong đó phía bên phải là đồ thị của từng trung tâm r và g , còn ở
phía bên trái là đồ thị của toàn mạng với hai trung tâm).
Mỗi hành trình bắt buộc t mà có thể được phục vụ bởi nhiều trung tâm (ví dụ như là
ở trong hình vẽ trên) thì sẽ được biểu diễn bởi nhiều cung song song trên đồ thị
toàn mạng (với số lượng cung đúng bằng số lượng trung tâm có thể phục vụ
cho nó, tức là
(, )aa
−+
(
,DVA=
()Gt
).
2. Bài toán thiết lập lịch trình vận tải trong mạng giao thông với nhiều
trung tâm điều hành
Hàm mục tiêu
Hàm mục tiêu (hàm chi phí) được thiết lập trên cơ sở nhận xét sau đây. Với mỗi
hành trình không tải ta cho tương ứng với một trọng số , là chi phí vận
hành của hành trình

có được một hành trình như vậy tại mỗi trung tâm có thể phục vụ nó). Tuy nhiên, cách này là
"không ổn" vì chi phí của hành trình bắt buộc này sẽ bị "mất hút" khi hành trình nhập bến của nó
không được thực thi trong lịch trình. Tình huống này thường xảy ra với các hành trình bắt buộc có
hành trình kế tiếp là một hành trình liên kết và do đó sẽ không về "nhập bến" qua hành trình nhập

6
bến của chính mình. Khi ấy, trong cả dãy các hành trình bắt buộc và các hành trình liên kết (đan
xen nhau) thì chỉ có chi phí của hành trình bắt buộc cuối cùng liền kề với hành trình nhập bến là
được tính đến, còn chi phí của các hành trình bắt buộc khác đều bị bỏ qua. Như vậy, chi phí được
tính theo cách này đã không phản ánh đúng chi phí thật
].
Mô hình toán học
Trong thực tế triển khai, chu kỳ lập lịch vận tải của mạng giao thông công cộng trong
thành phố thường là một ngày và tập các hành trình bắt buộc đưa ra trong kế hoạch chính
là tập các hành trình cần thực hiện trong một ngày. Bài toán đặt ra là thiết lập tập các lịch
trình cho mỗi trung tâm điều hành hoạt động trong một ngày. Khái niệm lịch trình đã nêu
cho phép loại trừ khả năng lịch trình chỉ gồm có một hành trình duy nhất, vì vậy ta có điều
cần lưu ý sau đây.
Chú ý 1. Một khi hành trình được thực thi (trong khuôn khổ một lịch trình nào đó) thì phải
có ít nhất một trong số các hành trình kề với nó (hoặc là tiền bối hoặc là kế cận của nó)
cũng được thực thi (trong cùng lịch trình đó).
Một phương án triển khai là một tập hợp các lịch trình, sao cho mỗi hành trình bắt
buộc (trong tập
T
) phải được thực thi đúng một lần và lịch trình thuộc về trung tâm nào sẽ
phải thỏa mãn các ràng buộc đặt ra tại trung tâm đó (thường là về số lượng đầu xe phục
vụ). Một phương án triển khai như vậy sẽ được gọi là phương án chấp nhận được. Phương
án tối ưu là phương án có tập lịch trình với tổng chi phí thực thi nhỏ nhất trong số các
phương án chấp nhận được.
Trong một phương án triển khai, việc mỗi hành trình bắt buộc chỉ được thực hiện

d
ij K∈ 0
d
ij
X =
d
ij
C
j
dd
ij i j
Ccc=+
d
. (1)
()
,
min
d
dd
ij ij
dDij K
CX
∈∈
∑∑
Với điều kiện các biến chỉ có thể nhận một trong hai giá trị, 0 hoặc 1, ta thấy
rằng điều kiện cần và đủ để một hành trình
i được thực thi đúng một lần sẽ là:
d
ij
X

kA kA
XX
∈∈
−=
∑∑
,
d
jT d D∀∈ ∀ ∈
Chứng minh. Từ điều (*) ta có
1
, và từ đây suy ra (3). Ta chỉ
còn phải chứng minh điều ngược lại. Do điều kiện (2), với m
d
T
chỉ có 2 khả năng
xảy ra là

ht ht
dd
dd
kj jk
kA kA
XX
∈∈
==
∑∑
ột
∈
:
jA

trình với bất cứ một hành trình nào kế cận với nó (mà thuộc về trung tâm
d
). Từ (i) và
điều kiện (3) lại suy ra , và điều này có nghĩa là không có hành trình nào
trong số các tiền bối của (mà thuộc miền phục vụ của ) có thể được thực thi trong
cùng lịch trình với nó. Như vậy bản thân hành trình không thể được thực thi (bởi trung
tâm
d
) vì nếu ngược lại thì phải có ít nhất một trong các hành trình liền kề với nó được
thực thi, như đã nói trong Chú ý 1. (Lưu ý rằng việc không được thực thi bởi trung tâm
là không có gì mâu thuẫn với việc và phải được thực thi 1 lần, bởi vì chỉ là
tập hành trình mà
d
có thể phục vụ, chứ không phải là tập hành trình mà
d
bu c phải thực
thi.)
j
0
ht
d
d
jk
kA
X
∈
=
∑
j
d

tâm được thể hiện như sau:
0
ht x
d
d
dj
jA
X
−
∈
∑
, . (4)
0
ht x
d
d
ddj
d
κ
Điều kiện nguyên 0 hoặc 1 của biến quyết định được viết lại là
. (5)
{}
0, 1 , , ,
d
ij d
XdDij∈∀∈∀∈

8
Như vậy, một phương án triển khai là chấp nhận được thì các điều kiện (2)-(5) phải
được thỏa mãn. Bài toán tìm phương án tối ưu chính là bài toán tìm phương án chấp nhận

. Như đã nói, Điều kiện (3) có
nghĩa là tồn tại duy nhất một hành trình là tiền bối của
a
và được thực thi trong cùng
lịch trình với . Lặp lại quá trình tương tự như vậy với cả và ta sẽ tìm ra các hành
trình tiền bối của
l
và kế cận của cùng ở trong một lịch trình với Cứ tiếp tục quá
trình này cho đến khi ta gặp một hành trình nhập bến và một hành trình xuất bến. Điều
này có nghĩa là ta đã tìm ra một lịch trình chứa hành trình
a
đã nêu. Ta ký hiệu lịch trình
này là . Tiếp tục, lấy một hành trình
b
khác trong tập
T
(nằm ngoài lịch trình vừa
nói), và làm tương tự như trên ta sẽ tìm ra một lịch trình khác. Điều kiện (2) cho thấy
rằng các lịch trình này không thể có chung một hành trình. Vì tập
T
là hữu hạn cho nên
sau một số lần hữu hạn ta sẽ vét hết tập
T
và có nghĩa là tìm ra tất cả các lịch trình. Mệnh
đề được chứng minh xong. 
d
T∈
ht
d
jA∈

trình xuất bến (hay nhập bến) cũng có thể được xem như là hành trình liên kết giữa hành
trình bắt buộc và hành trình nội bộ và do vậy cũng được xác định từ cặp gồm một hành
trình bắt buộc và một hành trình nội bộ.
ht
d
A
d
T
,ij
d
T
ht
d
A
k
i j
k
j
i
k
,ij
d
T k
,
d
ij T∈
,
d
ij T∈
0

gọn thì mọi hành trình bắt buộc đều có tiền bối và kế cận của mình.
,
d
ij T∈

1
d
ij
X = )ij
)ij
j j i
Chi phí cho quá trình thực hiện hành trình tiếp theo hành trình i có thể được xem
là chi phí cho hành trình liên kết trên cung liên kết nối hai hành trình và sẽ được ký
hiệu là . Như đã nói ở trên, nó có thể bao hàm cả chi phí của hành trình i (khi ta muốn
chuyển chi phí từ hành trình bắt buộc sang cho các hành trình không tải). Khi thì
chính là chi phí của hành trình xuất bến. Như đã nói, nó thường bao hàm cả chi phí
thực tế trên cung xuất bến lẫn trọng số sử dụng đầu xe (để điều tiết số lượng xe sử dụng tại
trung tâm đang xét: khi trọng số này càng lớn thì kết quả cho số đầu xe sử dụng càng ít).
Bây giờ, mục tiêu giảm thiểu tổng chi phí triển khai sẽ là
j
,ij
d
ij
C
0
id=
0
d
dj
C

∑

T∈
Như đã nói ở trên, mỗi hành trình bắt buộc ở trong một chu trình (thu gọn) nào đó đều có
hành trình kế cận và hành trình tiền bối ở trong chu trình này. Trong khuôn khổ của ràng
buộc (7), lập luận như trong Mệnh đề 1, ta biết điều này được thể hiện như sau
, . (8)
0
dd
dd
kj jk
kT kT
XX
∈∈
−=
∑∑

,
d
jT d D∀∈ ∀ ∈
Lưu ý rằng, số lượng xe đi phục vụ tại một trung tâm phải bằng số hành trình xuất bến
được thực thi, được tính bằng , và cũng phải bằng số lượng hành trình nhập
bến được thực thi, tức là bằng , cho nên điều kiện (8) cũng được thỏa mãn tại
, tức là với mọi .
0
ht x
d
d
dk
kA

jA
Xλ
−
∈
≤≤
∑
dD∀∈
jT∈
Tóm lại, bài toán tìm tập lịch trình tối ưu với các ràng buộc đã nêu có thể được mô tả
bởi (6) - (9) kết hợp với điều kiện nguyên 0 hoặc 1 của biến quyết định, tức là
. (10)
{}
0, 1 , , ,
d
ij d
XdDi∈∀∈∀

Sau này, để cho gọn, ta sẽ gọi nó là Bài toán (MD1).
Tương tự như trên, ta có mệnh đề sau.
MỆNH ĐỀ 3. Với mỗi phương án triển khai chấp nhận được, ta có vectơ giá trị biến quyết
định thỏa mãn các điều kiện (7)-(10). Ngược lại, từ mỗi vectơ giá trị
biến quyết định thỏa mãn các điều kiện (7)-(10) ta có thể thiết lập
được một phương án triển khai chấp nhận được.
,,
()
d
d
ij
dDijT
XX

là không khả thi trong thực tiễn. Trong tình huống như thế này người ta có thể nghĩ tới
một trong số những giải pháp siêu cảm tính đang ngày càng thể hiện tính hiệu quả trong
thực tiễn triển khai (xem [6], [11], và các tài liệu trong đó), hoặc tìm cách đơn giản hóa
bài toán (dựa trên các điều kiện thực tế cho phép), để hy vọng có được một lời giải đủ tốt
thay vì đi tìm kiếm một lời giải tối ưu chính xác theo lý thuyết mà việc tính toán là không
khả thi.
Ở đây, chúng tôi đề xuất một cách "đơn giản hóa" bài toán, làm cho nó trở nên dễ
giải hơn, và đồng thời lời giải thu được vẫn có được ý nghĩa thực tiễn rõ rệt.
Đơn giản hóa điều kiện ràng buộc
Việc có nhiều chủng loại xe tham gia hoạt động trên cùng một mạng giao thông công cộng
là thực tế hiện hữu, và thậm chí là không tránh khỏi. Tuy nhiên việc đưa thêm tập và
các tập ràng buộc liên quan tới nó như sẽ làm cho bài toán phức tạp lên rất nhiều. Có lẽ
ta nên tránh sự "phức tạp hóa" này bằng cách giả thiết sử dụng một chủng loại xe (loại phổ
()Gt
d
T

11
biến nhất). Sau khi giải xong bài toán, người quản lý có thể dùng phép "quy đổi" sang
chủng loại xe khác trên một số tuyến đường cụ thể, kèm theo việc tăng hay giảm tần suất
chạy xe sao cho phù hợp với lưu lượng hành khách cần phục vụ. Thông thường, việc "quy
đổi" là không "tương đương", cho nên giải pháp này không bảo toàn "tính tối ưu" của lời
giải. Tuy nhiên, nếu việc "quy đổi" là hợp lý thì lời giải cũng có thể chấp nhận được về
mặt thực tiễn.
Trong điều kiện đồng nhất về chủng loại xe thì chi phí trên các hành trình không
còn phụ thuộc vào đặc thù kỹ thuật tại trung tâm điều hành, mà chỉ còn phụ thuộc vào
quãng đường chạy xe, hay quy đổi tương đương thành ra thời gian xe chạy trên các hành
trình. Như vậy, có thể xem như chi phí sẽ không còn phụ thuộc vào
d
mà chỉ còn phụ

D
dD∈
- .
,
ht lk ht lk
d
AA d
−−
=∀
-
{
}
0
ht kt ht x ht n ht lk
ddd
AA , . AA d
−−−−
=∪∪∪
)
d
A=
ht ht kt
dd
ATA
−
=∪
Đồ thị của trung tâm
d
là
DV

d
d
ij ij
dD
ij A
CX
∈
∈
→
∑∑

với ràng buộc
,
1
ht
d
d
ij
dDjA
X
∈∈
=
∑
, iT∀∈ ,
0
ht ht
dd
dd
ij jk
iA kA

d
ij
X j
Tương tự như vậy, với ký hiệu
{
}
0d
TT , ta có thể viết lại Bài toán (MD1)
dưới dạng sau đây
d=∪


12
.
,
min
d
d
ij ij
dD
ij T
CX
∈
∈
→
∑∑

với ràng buộc
, i .
,

ddj
d
κ
jA
Xλ
−
∈
≤≤
∑
dD∀∈
jT∈

{}
0, 1 , , ,
d
ij d
XdDi∈∀∈∀

.
(MD1*)
trong đó, với , biến quyết định cho biết cặp hành trình bắt buộc có là
tương thích và được thực thi trong cùng một lịch trình của trung tâm d hay không.
,
d
ij T∈

d
ij
X (, )ij
Phân rã thành 2 bài toán đơn giản hơn

các lịch trình thu được sau việc giải D bài toán trên cho ta một lời giải chấp nhận được
của bài toán tổng quát ban đầu, vì rằng tất cả các hành trình bắt buộc đều đã được phân bổ

13
về cho các trung tâm (theo Bài toán thứ nhất), và mỗi hành trình chỉ được thực hiện đúng
một lần (theo Bài toán thứ hai).
Quá trình làm tốt thêm nhờ các vòng lặp
Lời giải nói trên có thể đã là tốt về mặt thực tiễn (nhờ hai lần thực hiện phép cực
tiểu hóa) nhưng nói chung chưa phải là lời giải tối ưu theo lý thuyết, và do vậy có khả
năng "làm tốt thêm". Cụ thể, với tập lời giải chấp nhận được đã nói ở trên, với mỗi lịch
trình đóng vai trò một tuyến xe, ta thực hiện việc tái phân bổ các tuyến về cho các trung
tâm (tức là giải Bài toán thứ 1 như đã xét trong [12]). Lời giải của bài toán này sẽ là một
cách phân bổ mới cho các tuyến về các trung tâm, nói chung là khác trước và cho giá trị
hàm mục tiêu tốt hơn (do quá trình làm cực tiểu hóa khi tái phân bổ).
Lời giải nêu trên không làm thay đổi cấu trúc của các lịch trình, mà chỉ thay đổi
trung tâm điều hành nó. Điều này có nghĩa là tập các hành trình bắt buộc được "phủ" bởi
từng trung tâm đã được thay đổi. Nói cách khác, nếu cho "phân rã" các lịch trình mới được
phân về từng trung tâm và lấy lại tập các hành trình bắt buộc có trong các lịch trình này, ta
sẽ có dữ liệu mới cho bài toán thiết lập tập lịch trình tối ưu (cho từng trung tâm riêng biệt).
Nếu giải bài toán này ta sẽ nhận được kết quả là một lời giải tốt hơn hẳn phương án trước
khi phân rã (vì nó sẽ là lời giải tối ưu thực sự cho bài toán với một trung tâm, trong khi
phương án trước khi phân rã chỉ là một phương án chấp nhận được mà thôi).
Như vậy qua một vòng lặp gồm hai bước, ta nhận được kết quả mới với chất lượng
tốt hơn.
Quy trình nêu trên có thể được lặp đi lặp lại nhiều lần, và sau mỗi vòng lặp kết quả
sẽ được cải thiện. Tuy nhiên, như đã nói từ đầu, việc thực hiện thêm vòng lặp chỉ có ý
nghĩa khi kết quả vòng sau thực sự tốt hơn đáng kể so với vòng trước. Việc thực hiện liên
tiếp nhiều vòng lặp chỉ có thể được áp dụng khi ta thiết lập mới hay tiến hành "cải tổ"
mạng giao thông một cách toàn diện (chỉ một lần trong khoảng thời gian rất dài).
Trong thực tế triển khai, người ta không nhất thiết phải áp dụng cả một vòng với 2

ij ij
ij A
CX
∈
∑
với các ràng buộc
, , 1
ht
ij
jA
X
∈
=
∑
iT∀∈
, , 0
ht ht
ij jk
jA kA
XX
∈∈
−=
∑∑
ht
iA∀∈
,
0
ht x
ij
jA

d=∪

jT∈
.
,
min
ij ij
ij T
CX
∈
→
∑

với ràng buộc
, i . 1
ij
jT
X
∈
=
∑

T∈
, . 0
kj jk
kT kT
XX
∈∈
−=
∑∑


15
TÀI LIỆU DẪN
[1] Ahuja R.K., Magnanti T.L., Orlin J.B., Network Flows: Theory, Algorithms and
Applications, Prentice-Hall, Inc., Englewood Cliffs, New Jersey, 1993.
[2] Bertossi A.A., Carraresi P., Gallo G., On some matching problems arising in
vehicle scheduling models, Networks, 17 (1987), pp. 271-281.
[3] Bianco L., Mingozzi A., Ricciardelli S., A set partitioning approach to the
multiple-depot vehicle scheduling problem, Optimization: Methods and Software, 7
(1994), pp. 163-194.
[4] Bokinge U., Hasselstrom D., Improved vehicle scheduling in public transport
through systematic changes in the time-table, European Journal of Operational
Research, 5 (1980), pp. 388-395.
[5] Branco I., Costa A., Paixão J., Vehicle scheduling problem with multiple type of
vehicles and a single depot, in Daduna, Branco and Paixão [1995], pp. 115-129.
[6] Dell'Amico M., Fischetti M., Toth P., Heuristic algorithms for multiple depot
vehicle scheduling problem, Management Science, N1, Vol. 39 (1993), pp. 115-125.
[7] Freling R., Wagelmans A., Paixão J., Models and Algorithms for Single-Depot
Vehicle Scheduling, Transportation Science, Vol. 35, No. 2, 2001, pp. 165–180.
[8] Kokott A., Loebel A., Lagrangean relaxation and subgradient methods for
multiple-depot vehicle scheduling problem, .
[9] Larsen A., Madsen O.B.G., Solving the multiple vehicle scheduling problem in a
major scandinavian city, Technical Report IMM-REP-1997-10, Technical
University of Denmark.
[10] Loebel A., Optimal Vehicle Scheduling in Public Transit, (PhD Thesis), 1997.
[11] Mesquita M., Paixão J., Multiple-depot vehicle scheduling problem: A new
heuristic based on quasi-assignment algorithms, in Desrochers and Rousseau (eds),
Computer-Aided Transit Scheduling, Lecture Notes in Economics and
Mathematicals Systems 386, Springer Verlag, Berlin, Heidelberg, 1992, pp.181-195.
[12] Phạm Xuân Hinh, Nguyễn Quang Minh, Phân bổ hợp lý các trung tâm điều hành