長沙星沙主城區(qū)環(huán)衛(wèi)灑水車最優(yōu)行走路線模型＊

劉明艷，曾玲玲，李 群，柳藝嬌，劉 芳

（1.長沙師范學(xué)院數(shù)學(xué)科學(xué)學(xué)院，湖南 長沙 410100；2.長沙師范學(xué)院圖書館，湖南 長沙 410100）

為了美化城市環(huán)境，減少城市空氣中的飛塵，給人們提供一個優(yōu)良的生活環(huán)境，在炎熱干燥的天氣為市區(qū)路面灑水是環(huán)衛(wèi)灑水車的一項必不可少的工作。但是城市的街道縱橫交錯，路網(wǎng)復(fù)雜，如果不科學(xué)規(guī)劃設(shè)計灑水車的行走路線，不但會造成公共資源的浪費，而且會加重本來就很辛苦的環(huán)衛(wèi)工人的工作負(fù)擔(dān)。因此，如何對環(huán)衛(wèi)灑水車的行車路線科學(xué)規(guī)劃、合理安排，不但是一個理論問題，而且是一個有用的實際問題。本文以長沙市長沙縣星沙主城區(qū)為例，研究城市環(huán)衛(wèi)灑水車最優(yōu)行走路線模型。

1 問題的提出

長沙縣星沙主城區(qū)的主要交通地圖（來自百度）如圖1所示，長沙縣星沙主城區(qū)中有星沙大道、開元路、東升路、濱湖路、漓湘路等道路。

圖1 星沙主城區(qū)街道地圖

問題一：如何設(shè)計路線使得灑水車在最短時間內(nèi)完成灑水任務(wù)？

問題二：如何設(shè)計路線使得灑水車完成所有道路灑水任務(wù)后恰好回到原點？

對問題一、問題二進(jìn)行聯(lián)合考慮，做出星沙主城區(qū)環(huán)衛(wèi)灑水車最優(yōu)行走路線模型。

2 問題分析

忽略道路網(wǎng)的形狀、寬度，將其合理簡化并轉(zhuǎn)化為圖論模型，道路抽象為邊，交匯處抽象為點，道路長度為權(quán)，則圖1 就可以轉(zhuǎn)化圖2。圖2 中，將星沙大道、開元路、東升路、濱湖路、漓湘路、東四路、黃興大道車流和人流密集以及路面灰塵大的道路轉(zhuǎn)化為圖論的邊，將其的交匯點轉(zhuǎn)化為點A、B、C、D、E、F、G、H、I、J、K、L。

圖2 加權(quán)圖

首先根據(jù)星沙主城區(qū)的實際情況和灑水車運(yùn)行起點的注意事項，選擇最佳灑水車運(yùn)行起點為D點。然后將問題一、問題二進(jìn)行聯(lián)合考慮，可以轉(zhuǎn)化為中國郵遞員問題模型進(jìn)行求解。

中國郵遞員問題是由中國數(shù)學(xué)家管梅谷先生在1962 年提出的。在中國郵遞員問題中，奇偶點圖上作業(yè)法是求最優(yōu)郵遞路線的一種方法。在一個有奇點的圖中，要求增加一些重復(fù)邊，使新圖不含奇點，并且重復(fù)邊的總權(quán)為最小。

使新圖不含奇點而增加重復(fù)邊的可行方案，被簡稱為可行（重復(fù)邊）方案；使總權(quán)最小的可行方案被稱為最優(yōu)方案。

3 模型的建立

多重歐拉圖如圖3 所示。

圖3 多重歐拉圖

4 模型求解

由圖2 可看出，具有奇數(shù)度的結(jié)點有6 個：B、D、F、G、I、K。所以V=｛B，D，F(xiàn)，G，I，K｝。然后求出V中每對結(jié)點對間的距離，需要考慮對結(jié)點，得到：d（B，D）=4.6，d（B，F(xiàn)）=4.3，d（B，G）=6.2，d（B，I）=6.0，d（B，K）=5.2，d（D，F(xiàn)）=3.9，d（D，G）=1.6，d（D，I）=5.1，d（D，K）=4.9，d（F，G）=5.2，d（F，I）=1.7，d（F，K）=5.7，d（G，I）=3.5，d（G，K）=3.3，d（I，K）=4.0。

因此，使距離和最小的配對方法應(yīng)為B、K，D、G以及F、I，因為d（B，K）+d（D，G）+d（F，I）=8.5 是包含V所有結(jié)點的最小距離和。將分別連接結(jié)點對B、K，D、G以及F、I的最短路的邊加入到圖2 中，得到圖3 所示多重歐拉圖，然后將圖3 中添了邊的圖形不重復(fù)地一筆畫出即得最優(yōu)行走路線，因此找出起點為D點的回路總權(quán)數(shù)是40.6 km 的行走最優(yōu)線路為D→A→B→C→F→I→L→K→J→G→D→E→F→I→H→E→B→E→H→K→H→G→D。

5 結(jié)論

以中國郵遞員問題為基礎(chǔ)，利用奇偶點圖上作業(yè)法，建立星沙主城區(qū)環(huán)衛(wèi)灑水車最優(yōu)行走路線模型，得到了最優(yōu)行走線路D→A→B→C→F→I→L→K→J→G→D→E→F→I→H→E→B→E→H→K→H→G→D，其具體行走路線方案為：星沙大道和濱湖路的交匯點→濱湖路→東升路→漓湘路→黃興大道→濱湖路→星沙大道→漓湘路→東四路→開元路→開元路→開元路→東四路→濱湖路。