掃雪問題之最短時間

陳興婉

一、問題重述

地圖中實(shí)線表示馬里蘭州 （Maryland）威克米克市（Wicomico）清除積雪區(qū)域雙行的道路，虛線是州高速公路。雪后，兩輛掃雪車從地圖*號標(biāo)出的兩點(diǎn)的每一地點(diǎn)以西約6.44（4mile）處出發(fā)清掃道路上的積雪。試為兩車找出有效的路徑。掃雪車可以通過高速公路進(jìn)出市內(nèi)道路。假定掃雪過程中車子不會損壞或停止，并且道路交叉處不需要附加掃雪程。

二、問題分析

要解決的問題是，為兩臺掃雪車設(shè)計出有效的路徑進(jìn)行威克米克市積雪道路的清掃工作。兩輛掃雪車從地圖*號標(biāo)出的兩點(diǎn)的每一地點(diǎn)以西約6.44km（4mile）處出發(fā)清掃道路上的積雪，市內(nèi)的道路均為雙向，掃雪車在道路的交叉點(diǎn)上可轉(zhuǎn)向行駛。把道路的交點(diǎn)作為頂點(diǎn)集V，道路作為邊集E，把所給地圖定義為有向圖,利用圖論的知識進(jìn)行分析，有向圖D是強(qiáng)連通的，且每個頂點(diǎn)的入度等于出度，即有向圖D是一個歐拉圖，圖中存在歐拉回路。

掃雪車遵守交通規(guī)則且靠右行駛，根據(jù)模型的假設(shè)，掃雪車經(jīng)過路面一次就能把該單行道徹底地清掃干凈，那么，掃雪車要完成任務(wù)就等于把所有的單向道路都至少行駛一遍。為了使掃雪車高效率地完成工作，考慮到兩臺掃雪車同時進(jìn)行工作，根據(jù)模型假設(shè)，兩掃雪車功率一樣且作業(yè)過程以勻速進(jìn)行，首先把地圖分為南、北兩個工作區(qū)，分別由兩輛掃雪車負(fù)責(zé)。在兩臺車工作量相等情況下，設(shè)想其中一臺掃雪車工作量減少一條道路，則另一臺掃雪車的工作量將增加一條道路，即工作時間增長一個單位，使得工作效率下降。所以，盡量使得兩工作區(qū)的工作量相近，即道路的總長相當(dāng)，兩掃雪車同時進(jìn)行工作，結(jié)束時間相近，縮短工作時間。

另外，掃雪車的工作時間是由兩部分組成的，即作業(yè)時間與空駕時間，工作時間即為掃雪用的時間，空駕時間即為行駛高速公路或清掃完畢的道路使用的時間之和。為了提高工作效率，實(shí)現(xiàn)掃雪車在完成任務(wù)的前提下，使得空駕時間最短。由于假定掃雪車是勻速行駛的，所以，要使得空駕時間最短就等于空駕的路程最短，盡量不走高速公路或清掃干凈的道路。為了實(shí)現(xiàn)掃雪車不重復(fù)行駛道路，即把問題轉(zhuǎn)化為圖的遍歷問題，經(jīng)過所有的邊一次且僅一次，經(jīng)過所有的頂點(diǎn)。

三、問題假設(shè)與符號說明

（一）問題假設(shè)

1.掃雪車在作業(yè)的過程中不會出現(xiàn)突發(fā)狀況使其停止工作；

2.掃雪車在開始工作到結(jié)束工作的過程中，燃油供應(yīng)足夠，不需要中途加油；

3.掃雪車在拐彎處不進(jìn)行特殊的掃雪處理；

4.掃雪車在拐彎處的路程忽略不計；

5.掃雪車在高速公路上行駛不計入工作量；

6.掃雪車可在高速公路上任意行駛且在高速公路與市內(nèi)公路接口處任意出入；

7.假設(shè)掃雪車經(jīng)過路面一次即把該單向路面清掃徹底；

8.掃雪車作業(yè)過程中，已經(jīng)停雪，清掃完的路面不會被落雪重新覆蓋，且不涉及融雪問題；

9.掃雪車遵守交通規(guī)則，靠右行駛；

10.兩掃雪車功率一樣且作業(yè)過程以勻速進(jìn)行；

11.假設(shè)高速公路上速度夠快，并且無需掃雪。

（二）符號說明

表示第個頂點(diǎn)；表示第條邊；表示頂點(diǎn)集；表示邊集；表示由頂點(diǎn)集和邊集組成的有向圖；表示路程；表示速度。

四、模型建立與求解

1.模型引入。本題考察馬里蘭州威考密科縣的雙行馬路有效掃雪問題，因此需要考慮車子如何行走路徑最短，同時兩車工作完的時間最短。

2.模型建立。該掃雪區(qū)域圖考慮到圖的復(fù)雜，除懸掛點(diǎn)外，每一點(diǎn)度數(shù)至少為2，因此，這里找出一條主干道，使得所有街道與其有關(guān)，并且用截斷的方法將該縣各街道轉(zhuǎn)換為樹的形式，再各自進(jìn)行遍歷，以得到該縣的行走路徑。為了使得掃雪路徑更加有效率，因此我們必須考慮時間最優(yōu)與路徑最優(yōu)。

根據(jù)計算，可知該掃雪區(qū)域每一節(jié)點(diǎn)的度數(shù)至少為2，因此可以在圖上尋找一條主要干道，使得剩下的道路組合成為樹形區(qū)域。

Step1:令兩掃雪車相向而行，將該城鎮(zhèn)橫向主干道走完，直到到達(dá)彼此的出發(fā)點(diǎn)。同時此路線將該掃雪區(qū)域劃分為幾個樹形圖。

Step2:兩車近似相等分工合作，將剩下的區(qū)域進(jìn)行遍歷，因?yàn)樗脴湫螆D不連通，因此需要用到高速公路出入口走完所有樹。這里不考慮掃雪車在高速公路上所用時間。(結(jié)果如圖2)

圖2

3.模型求解。Step1:兩輛掃雪車用在共同路徑，即主干道上的路程與時間分別為：

Step2:將剩余區(qū)域等分為兩段，使掃雪車共同工作時間最短。根據(jù)對圖路徑的計算，得知，當(dāng)分界線為：7-22-32-42-63-77-78-79-76-75-94時，兩邊工作區(qū)域近似相等，左邊掃雪車工作路程為：73.6英里，右邊掃雪車工作路程為73.2英里。

Step3:用在高速公路上的時間為：（以高速公路限速為例）

4.模型檢驗(yàn)。通過計算得到兩輛車的路徑分別為：

52-53-54-55-56-30-40-60-41-31-32-42-43-35-45-46-47-48-49-50-51-87-86-84-83-82-55-81-98-97-95-94-72-71-70-90-107-106-67-67-68-69-90-89-90-69-55-69-68-54-68-67-109-107-108-110-108-93-111-93-72-73-74-61-74-73-59-60-41-60-59-58-40-58-57-56-70-92-91-92-108-92-70-57-58-59-73-72-93-108-107-109-13-15-28-15-37-38-39-38-37-15-14-29-16-17-30-17-18-19-31-19-20-21-22-21-6-21-20-5-20-19-18-17-4-16-3-16-2-16-29-14-1-14-13

另一輛車的路徑為：

52-54-55-56-30-40-60-61-62-41-31-42-43-33-34-35-45-46-47-48-49-50-51-88-87-86-84-83-82-65-81-98-97-95-75-95-97-99-112-99-97-101-100-113-100-101-97-101-114-101-102-115-102-103-116-103-104-117-105-88-51-88-87-88-105-104-103-102-83-98-83-102-101-97-80-79-64-78-44-43-44-34-23-33-23-8-23-34-9-24-36-24-36-46-65-66-82-85-84-85-86-85-49-25-26-50-26-12-27-12-26-25-11-25-49-85-83-66-47-66-65-46-36-48-36-24-10-24-9-34-44-45-44-64-79-80-97-100-99-95-94-72-71-70-90-107-106

通過比較得到兩輛掃雪車的工作路徑不重復(fù)，如下圖所示。

圖3

圖4

五、模型優(yōu)缺點(diǎn)分析

模型優(yōu)點(diǎn)：首先將城鎮(zhèn)主要干道清理完畢，更加適合實(shí)際情況；將復(fù)雜的圖轉(zhuǎn)化為樹。

模型缺點(diǎn)：需要用到高速公路出入，使得路程加長。

[1]屈婉玲，耿素云，張立昂.離散數(shù)學(xué)[M].北京：高等教育出版社，2008

[2](美)KennethH.Rosen.離散數(shù)學(xué)及其應(yīng)用[M].北京：機(jī)械工業(yè)出版社，2007

[3]朱振元，朱承.數(shù)據(jù)結(jié)構(gòu)——C++語言描述[M].北京：清華大學(xué)出版社，2007