掃雪問題之最短時間

陳興婉

一、問題重述

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

二、問題分析

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

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

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

三、問題假設與符號說明

（一）問題假設

1.掃雪車在作業的過程中不會出現突發狀況使其停止工作；

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

3.掃雪車在拐彎處不進行特殊的掃雪處理；

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

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

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

7.假設掃雪車經過路面一次即把該單向路面清掃徹底；

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

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

10.兩掃雪車功率一樣且作業過程以勻速進行；

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

（二）符號說明

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

四、模型建立與求解

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

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

根據計算，可知該掃雪區域每一節點的度數至少為2，因此可以在圖上尋找一條主要干道，使得剩下的道路組合成為樹形區域。

Step1:令兩掃雪車相向而行，將該城鎮橫向主干道走完，直到到達彼此的出發點。同時此路線將該掃雪區域劃分為幾個樹形圖。

Step2:兩車近似相等分工合作，將剩下的區域進行遍歷，因為所得樹形圖不連通，因此需要用到高速公路出入口走完所有樹。這里不考慮掃雪車在高速公路上所用時間。(結果如圖2)

圖2

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

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

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

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

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

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

圖3

圖4

五、模型優缺點分析

模型優點：首先將城鎮主要干道清理完畢，更加適合實際情況；將復雜的圖轉化為樹。

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

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

[2](美)KennethH.Rosen.離散數學及其應用[M].北京：機械工業出版社，2007

[3]朱振元，朱承.數據結構——C++語言描述[M].北京：清華大學出版社，2007