Bài toán tìm tuyến đường đi tối ưu về tiêu thụ nhiên liệu và phát thải khí giữa hai điểm trong mạng lưới đường giao thông

Tóm tắt: Bài báo trình bày nội dung bài toán tìm tuyến đường đi giữa hai điểm bất kỳ trong mạng lưới đường giao thông theo mục tiêu tối ưu về phát thải khí và tiêu thụ nhiên liệu.

Từ khóa: Quy hoạch giao thông đô thị, khí thải và nhiên liệu.

 Abstract: This paper presents the content problem of road connection in the theoretic plan of road network in order to get the smallest total emissions and fuel consumption to reduce the  climate change.

Keywords: Urban transport planning, emissions and fuel.

1. Đặt vấn đề

Giảm thiểu khí thải giao thông và sử dụng nhiên liệu hiệu quả là vấn đề vô cùng quan trọng, góp phần giảm thiểu biến đổi khí hậu cũng như phục vụ phát triển GTVT bền vững. Trong công tác quy hoạch mạng lưới đường, tác giả đã trình bày các bài toán quy hoạch mạng lưới đường lý thuyết theo tiêu chí tối ưu về nhiên liệu tiêu thụ và phát thải khí ở Tạp chí Cầu đường [1,2] và ở báo cáo tham gia hội thảo Hạ tầng giao thông Việt Nam với phát triển bền vững [3]. Song đối với mạng lưới đường có sẵn, với giá thành nhiêu liệu (xăng, dầu) ngày càng đắt đỏ thì một vấn đề đặt ra đối với người tham gia giao thông là cần xác định tuyến đường đi trong mạng lưới sao cho tiêu thụ nhiên liệu và phát thải khí ít nhất. Mục tiêu này cũng góp phần giảm chi phí đi lại, giảm tiêu hao nhiên liệu, giảm khí thải của các phương tiện giao thông, qua đó góp phần giảm nhẹ biến đổi khí hậu cũng như phục vụ mục tiêu giao thông vận tải bền vững.

2. Giới thiệu bài toán tìm đường đi ngắn nhất trong lý thuyết đồ thị

2.1. Nội dung bài toán

Cho đồ thị G (V,E) là đồ thị có trọng số a và z là 2 đỉnh của đồ thị. Hãy tìm đường đi có tổng trọng số nhỏ nhất từ a đến z.

2.2. Ý tưởng chung của các thuật toán tìm đường đi ngắn nhất

Các giải thuật được phát triển để giải bài toán dạng này tiêu biểu là các thuật toán: Dijkstra, Bellman-Ford.

- Dò tìm bằng cách đi qua các điểm trung gian;

- Nếu phát hiện đường đi qua các điểm trung gian ngắn hơn đường đi hiện tại thì sẽ cập nhật đường đi mới, đồng thời chỉnh sửa các thông tin liên quan;

- Sử dụng 2 mảng để lưu trữ tạm thời:

+ Mảng D[v]: Lưu trữ độ dài đường đi ngắn nhất hiện tại từ điểm a đến điểm v;

+ Mảng T[v]: Lưu trữ điểm nằm trước điểm v trên đường đi ngắn nhất hiện tại.

2.3. Thuật toán Bellman-Ford [6]

 Giải bài toán nguồn đơn trong trường hợp trọng số cạnh có thể có giá trị âm. Áp dụng được cho mọi trường hợp, lượng tính toán lớn.

2.4. Thuật toán Dijkstra [7] 

Giải bài toán nguồn đơn nếu tất cả các trọng số cạnh đều không âm. Do không có cạnh âm nên tại mỗi bước sẽ có một điểm mà thông tin về nó sẽ không đổi về sau. Tại mỗi bước, ta không cần phải kiểm tra qua tất cả các điểm trung gian mà chỉ thực hiện chọn một điểm u có giá trị D[u] nhỏ nhất, chọn u làm điểm trung gian để xác định các bước kế tiếp.

Theo Cơ quan Năng lượng quốc tế [4], khí phát thải và nhiên liệu tiêu thụ của các phương tiện giao thông có quan hệ tỷ lệ thuận nên có thể sử dụng tiêu chí tối ưu về tổng khí thải và nhiên liệu tiêu thụ làm hàm mục tiêu. Mặt khác, do nhiên liệu tiêu thụ và khí thải của phương tiện giao thông di chuyển giữa các điểm là các số không âm nên thuật toán Dijkstra phù hợp để giải quyết bài toán với hàm mục tiêu là tối ưu về tiêu thụ nhiên liệu và phát thải khí. 

3. Ứng dụng thuật toán Dijkstra để giải bài toán tìm đường đi tối ưu tiêu thụ nhiên liệu và phát thải khí giữa 2 điểm trong mạng lưới đường giao thông

3.1. Nội dung bài toán

Một mạng lưới đường có n điểm thuộc tập V, biết chiều dài và vận tốc trung bình khi di chuyển trên tuyến đường nối giữa các điểm trong mạng lưới. Tìm đường đi từ điểm a đến điểm z trong mạng lưới đường giao thông để phương tiện tham gia giao thông tiêu thụ nhiên liệu và phát sinh khí thải ít nhất.

3.2. Các bước của thuật toán Dijkstra

Theo Dijkstra [7], các bước của thuật toán Dijkstra như sau:

Gọi: L[u,v]- Chiều dài tuyến đường nối từ điểm u đến điểm v (km);

S[u,v]- Vận tốc trung bình khi di chuyển trên tuyến đường nối từ điểm u đến điểm v (km/h).

Ở mỗi điểm v, thuật toán Dijkstra xác định 3 thông tin: Chon_v, D_v và truoc_v.

Chon_v - Mang giá trị true hoặc false để xác định trạng thái được chọn của điểm v.

Khởi tạo tất cả các điểm v chưa được chọn, nghĩa là: Chon_v = false, "_v ∈V.

D_v - Tổng nhiên liệu tiêu thụ và khí phát thải cho đến thời điểm đang xét khi đi từ điểm a đến điểm v. Khởi tạo, D_v = ∞, "_v ∈V \{a}, D_a = 0.

Truoc_v- Điểm trước của điểm v trên đường đi tối ưu về nhiên liệu và khí thải khi đi từ a đến z. Đường đi tối ưu về nhiên liệu và khí thải từ a đến z có dạng {a ,..., truoc_v, v,..., z}. Khởi tạo, truoc_v = null, "_v ∈V.

Bước 1:Khởi tạo: Đặt chon_v:= false "_v ∈V; D_v:= ∞, "_v ∈V \ {a}, D_a:=0.

Bước 2:Chọn v  V sao cho chon_v = false  và D_v = min {D_t / t∈ V, chon_t = false}.

Nếu D_v =  thì kết thúc, không tồn tại đường đi từ a đến z.

Bước 3:Đánh dấu điểm v, chon_v:= true.

Bước 4:Nếu v = z thì kết thúc và D_zlà tổng khí thải và nhiên liệu tiêu thụ ít nhất khi đi từ a đến z.

Ngược lại, nếu v ≠ z sang Bước 5.

Bước 5:Với mỗi điểm v kề với u mà chon_v = false, kiểm tra.

Nếu D_v > D_u + L(u,v).[518,257 – 8,88657.S(u,v)+ 0,059146.S(u,v)²]

thì D_v= D_u + L(u,v).[518,257 – 8,88657.S(u,v)+ 0,059146.S(u,v)²].

Ghi nhớ điểm v: truoc_v:= u. Quay lại Bước 2.       

Trong đó:

518,257 - 8,88657.V+ 0,059146.V²  là phương trình tính tổng khí thải và tiêu thụ nhiên liệu quy đổi sang CO₂ (gCO₂/km) của ô tô con theo mô hình tính khí thải Copert III [5] khi xe di chuyển với vận tốc V (km/h).

3.3. Cài đặt thuật toán Dijkstra tìm đường đi tối ưu về nhiên liệu tiêu thụ và khí phát thải giữa 2 điểm trong mạng lưới đường giao thông bằng ngôn ngữ lập trình Pascal

Dữ liệu được lấy từ tệp Dulieu.txt có cấu trúc: Sau khi lấy dữ liệu, chương trình sẽ xác định có tồn tại đường đi tối ưu về nhiên liệu tiêu thụ và phát thải khí hay không, nếu có tồn tại thì tìm đường đi đó đồng thời tìm đường đi ngắn nhất để so sánh kết quả. Sau đó lưu kết quả vào tệp Ketqua.txt có cấu trúc:

Dòng 1: KHÔNG CÓ TUYẾN ĐƯỜNG ĐI  (nếu không tồn tại tuyến đường đi)

Dòng 1: TUYẾN ĐƯỜNG TỐI ƯU VỀ NHIÊN LIỆU VÀ KHÍ THẢI (nếu tồn tại)

Dòng 2: Tổng phát thải khí và tiêu thụ nhiên liệu là: F1(z) g

Dòng 3: Tổng chiều dài là: D1(z) km

Dòng 4: Đi theo thứ tự như sau: a => z₁ => z₂ =>  … z_­n => z

Dòng 5 : TUYẾN ĐƯỜNG NGẮN NHẤT

Dòng 6: Tổng phát thải khí và tiêu thụ nhiên liệu là: F2(z2) g

Dòng 7: Tổng chiều dài là: D2(z2) km

Dòng 8: Đi theo thứ tự như sau: a => z₁ => z₂ => … z_­n => z

3.4. Ví dụ

Tìm đường đi từ điểm 1 đến điểm 7 sao cho nhiên liệu tiêu thụ và phát thải khí ít nhất, biết chiều dài, vận tốc trung bình, hướng đi các cạnh nối giữa các điểm cho như sơ đồ ở Hình 3.1.

Hình 3.1: Sơ đồ minh họa mạng lưới đường giao thông

File dữ liệu đầu vào: (Dulieu.txt)

10 1 7

1 2 1 50

1 5 3 80

1 9 3 20

1 10 2 60

2 3 4 50

2 5 1 40

5 3 2 60

3 4 1 50

6 3 2 60

4 7 5 50

4 8 3 80

5 6 5 60

5 9 5 80

4 6 1 70

6 7 3 20

8 7 4 50

9 6 5 50

9 8 3 30

10 9 6 60

File kết quả: (Ketqua.txt)

* TUYẾN ĐƯỜNG TỐI ƯU VỀ NHIÊN LIỆU VÀ KHÍ THẢI:

- Tổng phát thải khí và tiêu thụ nhiên liệu là: 2206 g CO₂

- Tổng chiều dài là: 10,0km

- Đi theo thứ tự như sau: 1=> 2 => 5 => 3 => 4 => 7

* TUYẾN ĐƯỜNG ĐI NGẮN NHẤT:

- Tổng phát thải khí và tiêu thụ nhiên liệu là: 2376 g CO₂

- Tổng chiều dài là: 9,0km

- Đi theo thứ tự như sau: 1 => 2 => 5 => 3 => 4 => 6 => 7

4. Ví dụ bài toán thực tế

Ví dụ cho kết quả nghiên cứu bài toán này, tác giả lấy TP. Hà Nội để minh họa. Bài toán: Tìm tuyến đường tiêu thụ nhiên liệu và phát thải khí ít nhất đi từ Trường Đại học Điện Lực (235 Hoàng Quốc Việt, Hà Nội) đến Trường Đại học Xây dựng (55 Giải Phóng, Hà Nội).

Tiến hành khảo sát và xây dựng cơ sở dữ liệu các tuyến đường gồm 2 thông số: Chiều dài (km) và vận tốc trung bình ô tô di chuyển trên tuyến đường trong giờ cao điểm (km/h).

Kết hợp phần mềm Google Map ta tìm được các phương án khả thi cho ô tô đi từ Trường Đại học Điện lực đến Trường Đại học Xây dựng Hà Nội ta có kết quả như sau:

TUYẾN ĐƯỜNG ĐI NGẮN NHẤT

- Tổng chiều dài là: 9,7km

- Tổng khí thải và nhiên liệu tiêu thụ: 3419g

- Đi theo lộ trình:

Trường Đại học Điện lực

=> Hoàng Quốc Việt                  (0,4km; 25km/h)

=> Phạm Văn Đồng                     (0,02km; 20km/h)

=> Hoàng Quốc Việt                  (0,95km; 25km/h)

=> Nguyễn Phong Sắc                (0,66km; 20km/h)

=> Trần Đăng Ninh                    (0,8km; 20km/h)

=> Cầu Giấy                                (1,15km; 15km/h)

=> La Thành                                (2,7km; 15km/h)

=> Hoàng Cầu                             (0,56km; 35km/h)

=> Xã Đàn                                   (1,7km; 30km/h)

=> Giải Phóng                              (0,73km; 30km/h)

=> Trường Đại học Xây dựng

* TUYẾN ĐƯỜNG TÔÍ ƯU VỀ NHIÊN LIỆU VÀ KHÍ THẢI:

- Tổng chiều dài là: 12,7km

- Tổng khí thải và nhiên liệu tiêu thụ: 3367g

- Đi theo lộ trình:

Trường Đại học Điện lực

=> Hoàng Quốc Việt               (0,4km; 25km/h)

=> Phạm Văn Đồng                  (0,7km; 20km/h)

=> Phạm Hùng                            (0,9km; 40km/h)

=> Đường trên cao                    (5,4km; 70km/h)

=> Nguyễn Trãi                           (2,2km; 25km/h)

=> Trường Chinh                         (2,3km; 25km/h)

=> Giải Phóng                              (0,8km; 30km/h)

=> Trường Đại học Xây dựng

Nhận xét: Tuyến đường ngắn nhất (9,7km) ngắn hơn tuyến đường tối ưu về khí thải và nhiên liệu (12,7km) tới 3km nhưng lại phát thải và tiêu thụ nhiên liệu nhiều hơn.

5. Kết luận

Qua cùng một ví dụ số liệu đầu vào như trên nhưng khi tìm lộ trình tuyến đường ta thấy có sự khác nhau giữa tuyến đường ngắn nhất và tuyến đường có khí thải tiêu thụ và phát thải khí ít nhất. Như vậy, có thể thấy kết quả của việc tìm tuyến đường đi ngắn nhất chưa chắc đã đảm bảo đi theo lộ trình đó thì nhiên liệu tiêu thụ và phát thải khí là ít nhất.

Nếu thay đổi số liệu đầu vào sao cho trên các tuyến đường ngắn cho phép di chuyển với vận tốc cao hơn vận tốc ở các tuyến đường dài thì kết quả của bài toán tìm tuyến đường ngắn nhất sẽ trùng với kết quả với bài toán tìm tuyến đường tối ưu về nhiên liệu tiêu thụ và phát thải khí.

Các hãng cung cấp các phần mềm và dịch vụ bản đồ số có thể áp dụng ý tưởng bài toán tìm tuyến đường tối ưu về nhiên liệu tiêu thụ và phát thải khí vào trong sản phẩm của hãng mình để phục vụ người sử dụng được tốt hơn. Đặc biệt, các công ty vận tải nên đặc biệt lưu ý tới bài toán này nhằm giảm bớt chi phí vận tải và tăng lợi nhuận cho doanh nghiệp.

Do tuyến đường đi tối ưu về khí thải và nhiên liệu tiêu thụ sẽ thay đổi theo tình trạng lưu thông (tốc độ) của tuyến đường nên để có thể cập nhật liên tục tuyến đường tối ưu về khí thải và tiêu thụ nhiên liệu thì tác giả kiến nghị cần nghiên cứu xây dựng hệ thống theo dõi tình trạng giao thông của các tuyến phố theo thời gian thực. Trên cơ sở dữ liệu thời gian thực, các hãng cung cấp dịch vụ bản đồ số có thể liên tục cập nhật tình trạng lưu thông trên các tuyến đường để có thể tìm ra tuyến đường đi tối ưu về nhiên liệu và khí thải.

 Tài liệu tham khảo

[1]. Phạm Đức Thanh, Nguyễn Quang Đạo (5/2013), Nghiên cứu bài toán đường nối trong quy hoạch mạng lưới đường lý thuyết nhằm giảm thiểu BĐKH, Tạp chí Cầu đường.

[2]. Phạm Đức Thanh, Nguyễn Quang Đạo (9/2013), Nghiên cứu bài toán lưới đường có quan hệ vận tải gồm nhiều điểm trong quy hoạch mạng lưới đường lý thuyết nhằm giảm thiểu BĐKH, Tạp chí Cầu đường.

[3]. Phạm Đức Thanh, Nguyễn Quang Đạo, Phạm Cao Thăng (17/8/2013), Nghiên cứu giảm thiểu khí nhà kính và sử dụng năng lượng hiệu quả phục vụ mục tiêu GTVT bền vững, Hội thảo quốc gia Hạ tầng giao thông Việt Nam với phát triển bền vững, Đà Nẵng, NXB. Xây dựng, ISBN 978-604-82-0019-0.

[4]. International Energy Agency (2012), CO₂ Emissions from fuel combustion highlights.

[5]. European Environment Agency (2000), COPERT III Computer programme to calculate emissions from road transport.

[6]. Bellman, Richard (1958), On a routing problem, Quarterly of Applied Mathematics, vol. 16, pp. 87-90.

[7]. Dijkstra.E (1959), A note on two problems in connection with graphs, Numerische Mathematik, Vol.1.