1、灑水車路線優(yōu)化問題鍵入文檔副標(biāo)題參賽學(xué)校：上師大附中成員：丁偉東、湯申嘉、毛鈺潤(rùn)2011/7/31課題摘要隨著夏天天氣逐漸炎熱，灑水車對(duì)路面的降溫越來(lái)越重要，如何合理運(yùn)用不同型號(hào)的灑水車進(jìn)行路面降溫工作正是本小組所研究的目標(biāo)。為了方便計(jì)算與路線設(shè)計(jì)，我們建立模型：假設(shè)大車與小車的速度、耗油量等全部相等。為了達(dá)到最大限度的優(yōu)化，我們考慮大車與小車對(duì)不同路段的灑水效率差異和邊緣地帶只允許順時(shí)針單側(cè)完成任務(wù)的條件，將主干道全部分給大車完成并利用外側(cè)綠線進(jìn)行連接，將內(nèi)部非主干道部分交給小車完成。并且我們利用幾何畫板對(duì)所有路段進(jìn)行了分段與長(zhǎng)度測(cè)量，以極小的誤差將大車和小車的路線長(zhǎng)度分為了相等的兩部分，使

2、大車和小車在最短的時(shí)間內(nèi)完成全部的路段工作量。以下展示大車小車分別的路線和任務(wù)路段。(左圖為大車行車路線，右圖為小車行車路線。)問題提出1、如何合理使用兩種不同的灑水車對(duì)三種不同的路段進(jìn)行灑水作業(yè)，使得灑水車在最短的時(shí)間內(nèi)完成灑水作業(yè)，并且盡量使得兩車作業(yè)時(shí)間相等，工作量最??？2、如何設(shè)計(jì)路線，使灑水車在完成任務(wù)后恰好回到停車場(chǎng)（即如何完成兩個(gè)歐拉圈）？3、如何設(shè)計(jì)路線，使大小兩車的路線既不重疊也不遺漏？模型假設(shè)A、 灑水車在路上的運(yùn)作與行駛問題1、 灑水車在路上一切運(yùn)作正常，無(wú)堵車與紅綠燈問題。2、 灑水車單程在同一條車道上行駛，不考慮切換車道導(dǎo)致的路線總長(zhǎng)增加。3、 不考慮灑水車作業(yè)中水量

3、減少使車重變輕和速度變快的問題。4、 不考慮任何因素對(duì)車的影響，假設(shè)灑水車完全地勻速前進(jìn)。B、 兩輛灑水車的行駛比較1、 假設(shè)大小兩車的行駛速度相同。2、 假設(shè)大小兩車的油耗等成本相同。3、 假設(shè)大小兩車的灑水效果相同。C、 灑水車的路線問題1、 不考慮灑水車的水量補(bǔ)給問題。2、 根據(jù)實(shí)際情況，保證灑水車在最終回到停車場(chǎng)內(nèi)。3、 利用路程估算灑水作業(yè)的工作量。4、 忽略比例尺的誤差和路面的高低路況。5、 將路口視作一點(diǎn)進(jìn)行計(jì)算。6、 不考慮內(nèi)外側(cè)車道的長(zhǎng)度差，全部取路段中間長(zhǎng)的平均值。模型建立原題分析：本題兩車的路線往返，即考慮到現(xiàn)實(shí)中上下行不同車道問題。來(lái)回兩次必須確保反向，使得兩邊車道都能

4、灑到水。由于外圈只需順時(shí)針方向?yàn)⑺?，也就可以理解成外圈只需在?nèi)測(cè)路道灑水（即靠近城鎮(zhèn)的一半車道），所以外圈以一個(gè)順時(shí)針單圈進(jìn)行考慮。原圖：簡(jiǎn)化模型（弊端在于只注重線路簡(jiǎn)化，失去了比例。方便了線路連接和歐拉圖的構(gòu)造，但無(wú)法利用這張圖進(jìn)行均衡分配和優(yōu)化。）：不同路段分離圖（便于測(cè)量計(jì)算各種路段的長(zhǎng)度，為線路的優(yōu)化鋪墊基礎(chǔ)）：（由于電腦顯示屏尺寸不同問題，以下比例尺的標(biāo)準(zhǔn)與原圖不同，但完全按照原圖比例進(jìn)行了放縮并且以下圖片的比例相同，只影響到倍率，但不影響計(jì)算以及線路規(guī)劃。）主干道（總長(zhǎng)：89.14CM）：主要道路（82.82cm）：一般道路（81.03cm）：（以上為基礎(chǔ)模型）矩形圖模型：矩形圖更

5、加簡(jiǎn)潔明朗，對(duì)題意的初步理解和初步規(guī)劃有很大的幫助。利用簡(jiǎn)潔的矩形圖，直接對(duì)圖進(jìn)行分析。因?yàn)榉秸木匦巫屇愕谝徊骄蜎Q定讓外圈連接成一個(gè)完整的圈，并連接內(nèi)部分支，組成最終的歐拉圈。然而，便于觀察的矩形圖，比例不正確，無(wú)法進(jìn)一步計(jì)算。分離圖：將原圖分離開，更加便于分配，不同路段應(yīng)由不同車輛完成。并且對(duì)每一個(gè)路段進(jìn)行了同比例測(cè)量，有了準(zhǔn)確的數(shù)據(jù)，可以把矩形圖的大概思想進(jìn)一步轉(zhuǎn)化為精確的定量關(guān)系可以進(jìn)一步優(yōu)化?？梢栽谠鹊幕A(chǔ)上考慮一些內(nèi)部小分支的分配，利用數(shù)據(jù)達(dá)到平衡。小結(jié)：矩形圖和分離圖的兩步法，先從淺層的基本分配快速入手，再通過數(shù)據(jù)，精準(zhǔn)地完全分配完畢。兩步法可以在短時(shí)間內(nèi)完成相對(duì)優(yōu)化的方案制定

6、?？梢?，此模型是相對(duì)成功的。模型求解大車路線：由于大車在主干道上只需要來(lái)回工作一次，而小車需要來(lái)回四次，其工作效率顯而易見，所以決定利用大車對(duì)主干道進(jìn)行灑水作業(yè)。然后結(jié)合題目中要求的邊緣部分只允許順時(shí)針方向進(jìn)行灑水和紅線的來(lái)回原則，所以只有外圈邊緣部分需要調(diào)整使邊緣成為歐拉圈，而圈內(nèi)部分每條邊全部是來(lái)回一次即每個(gè)點(diǎn)都是偶點(diǎn)，成為了歐拉圈的充要條件。外圈需要成為單向的歐拉圈，根據(jù)歐拉環(huán)游的條件，必須組成一個(gè)完整的圈。所以最終決定利用邊緣的綠線將紅線連成一個(gè)完整的圈。最后大車環(huán)繞邊緣走一圈，并且在繞圈的同時(shí)進(jìn)入內(nèi)部部分紅線綠線進(jìn)行灑水，總計(jì)行車216.26cm。小車路線：為了便于達(dá)到歐拉環(huán)游的目的

7、，所以讓小車往返走各條非主干型道路，因?yàn)樾≤嚨木€路全部為偶點(diǎn)，所以小車能夠不重復(fù)不遺漏地走完大車不會(huì)走過的道路（具體線路正好覆蓋整個(gè)路線，但方法較多，不作單一走法。）且以歐拉環(huán)游的方式回到停車場(chǎng)。經(jīng)過幾何畫板的測(cè)量與計(jì)算，小車行進(jìn)路線長(zhǎng)218.84cm。大車小車的路線正好覆蓋了整個(gè)區(qū)域，并且以歐拉圈的形式回到了停車場(chǎng)，沒有遺漏也沒有重復(fù)，達(dá)到了優(yōu)化的目標(biāo)。另外兩輛車的工作量幾乎相等，可以在最短的時(shí)間內(nèi)同時(shí)完成任務(wù)，避免出現(xiàn)一輛車空著另一輛還有一大段任務(wù)的情況，在相對(duì)性上進(jìn)一步優(yōu)化。求解小結(jié)：大車開216.26cm，小車218.84cm。兩輛車在最短時(shí)間內(nèi)同時(shí)完成灑水任務(wù)。模型驗(yàn)證根據(jù)已建立的模

8、型，我們將各個(gè)路口之間的距離量化。經(jīng)過計(jì)算得出整個(gè)街道總長(zhǎng)為cm，由于題設(shè)中假設(shè)大、小型灑水車的速度完全相同，兩車行車路線的最優(yōu)化安排的關(guān)鍵便在于如何安排量車型車總距離相同且盡可能不重復(fù)；又由于兩車最終需回到停車場(chǎng)（即起點(diǎn)），問題的關(guān)鍵又轉(zhuǎn)化到建立兩個(gè)盡可能不重復(fù)的歐拉圓。由于兩種型號(hào)的車輛工作效率不同暫時(shí)假設(shè)由大型車完成所有的主干道灑水工作。由此建立模型A，經(jīng)過計(jì)算得到主干道部分總長(zhǎng)為cm，即大型車至少需完成cm路段（不考慮往返）的工作量，但顯然在這種情況下無(wú)法完成一個(gè)歐拉圓，且大、小兩車的行車路程相差極大。因此需要分配部分非主要道路給大型車完成。由于單行的話會(huì)出現(xiàn)奇點(diǎn)，無(wú)法完成歐拉環(huán)游，所

9、以大型車不能走一般道路，所有的一般道路都必須由小型車完成。因此小型車至少需完成cm（不考慮往返）的工作量。此時(shí)大、小兩車的工作量相差為cm（不考慮往返）。又由于以上方案全部為往返車程（除邊緣部分），內(nèi)部全部為歐拉圈，總灑水長(zhǎng)度為435.1cm，所以要想辦法合理分配主要道路，使得兩車行駛的總長(zhǎng)度幾乎相等（兩車分別接近217cm）。往返灑水已經(jīng)確保小車行駛部分必然是歐拉圈。所以要保證大車行進(jìn)的是歐拉圈，必然要保證邊緣部分成為一個(gè)完整的圈，即一輛車去灑水，所以整個(gè)邊緣有大車負(fù)責(zé)，組成歐拉圈。之后進(jìn)一步對(duì)剩余路段進(jìn)行再次分配并達(dá)到平衡。在基本確定路線后，刪去所有的一般道路、必經(jīng)的主要道路以及所有的主干

10、道，得到模型2，這一部分即為大型車和小型車共同分擔(dān)的部分。結(jié)合基本模型與模型2，不難發(fā)現(xiàn)任何一部分一般道路只與模型2中的主要道路相通，得到模型3，即模型3中的主要道路為符合上述要求的部分，這些主要道路必須由小型車完成。通過幾何畫板的測(cè)量，得到小型車必須完成的部分，發(fā)現(xiàn)剛好與總路程的一半相接近（誤差僅為2cm），且滿足完成兩個(gè)歐拉圓的要求。由此得出結(jié)論，所設(shè)的路線即為最優(yōu)化方案。模型2：模型3：模型優(yōu)缺點(diǎn)：優(yōu)點(diǎn)：1、 運(yùn)用工具簡(jiǎn)單，便于操作。2、 計(jì)算簡(jiǎn)單，能夠快速按一定步驟制定優(yōu)化的計(jì)劃。3、 分為路線制定（矩形圖）和路線計(jì)算（原圖分離版），兩步能夠更加精確地計(jì)算出最優(yōu)路線。缺點(diǎn)：1、 將路線分成多段直線，雖然很接近，必然有誤差。2、 忽略了車速的各種影響，與現(xiàn)實(shí)有一定差距。3、 大小兩種車型油耗必然不同，由于方便計(jì)算與應(yīng)用，忽略了成本的差異。4、 沒有考慮到水的補(bǔ)給問題，應(yīng)該在路線上設(shè)定供給點(diǎn)。5、 此模型是優(yōu)化的一種，不一定為最優(yōu)情況。6、 只考慮一條道路全部分給同一輛車完成，不考慮兩車同時(shí)完成的情況。小結(jié)：由于此模型與現(xiàn)實(shí)的差距存在，并且忽略了部分影響因素，導(dǎo)致會(huì)有一定誤差