課程設計---有時間窗的車輛調度優(yōu)化問題

1、<p><b>　　目錄</b></p><p><b>　　目錄1</b></p><p>　　第一章 課程設計的目的及意義2</p><p>　　第二章 課程設計的題目及要求2</p><p>　　2.1 配送車輛調度問題的描述2</p><p>　　

2、2.2任務的特征及要求5</p><p>　　第三章 題目分析6</p><p>　　3.1一般VSP模型6</p><p>　　3.2 時間窗VSP模型8</p><p>　　3.3 關于時間窗的寬度8</p><p>　　第四章 計算原理及流程圖9</p><p><b&g

3、t;　　4.1算法原理9</b></p><p>　　4.2 流程圖11</p><p>　　第五章 計算過程11</p><p>　　5.1計算各點對間連接的費用節(jié)約值11</p><p>　　5.2構造線路12</p><p>　　第六章 算法的總結與分析15</p><

4、p>　　6.1處理其他的約束15</p><p>　　6.2算法的進一步討論15</p><p>　　6.3算法的推廣15</p><p><b>　　6.4結論16</b></p><p>　　附錄一 代碼設計18</p><p>　　第一章 課程設計的目的及意義</p&

5、gt;<p>　　《運輸組織學》是交通運輸類專業(yè)的一門必修專業(yè)課，通過理論教學環(huán)節(jié)，是同學們了解公路運輸?shù)幕纠碚摵突痉椒?，并可以初步掌握公路運輸企業(yè)生產(chǎn)組織管理的基本理論、基本方法，使同學們具備進行公路運輸企業(yè)組織管理的基本知識。</p><p>　　課程設計是理論教學環(huán)節(jié)的延伸。是對學生們的一次實戰(zhàn)演練，通過課程設計，以檢驗和提高學生運用所學理論知識解決實際問題的能力，使學生較全面和系統(tǒng)的實踐

6、交通運輸組織的基本理論，方法和技能，初步具備運用現(xiàn)代化科學方法進行公路運輸生產(chǎn)組織管理的能力，完成培養(yǎng)公路運輸業(yè)高級管理人才所需的運輸組織管理方面的專業(yè)知識和技能的基本訓練。</p><p>　　當前，現(xiàn)代物流已被公認為是企業(yè)在降低物質消耗、提高勞動生產(chǎn)率以外創(chuàng)造利潤的第三個重要源泉，也是企業(yè)降低生產(chǎn)經(jīng)營成本，提高產(chǎn)品市場競爭力的重要途徑[1]。配送是物流系統(tǒng)中的一個重要環(huán)節(jié)，它是指按客戶的訂貨要求，在物流中心進

7、行分貨、配貨工作，并將配好的貨物及時送交收貨人的物流活動。在配送業(yè)務中，配送車輛調度問題的涉及面較廣，需要考慮的因素較多，對配送企業(yè)提高服務質量、降低物流成本、增加經(jīng)濟效益的影響也較大。該問題包括集貨線路優(yōu)化、貨物配裝及送貨線路優(yōu)化等，是配送系統(tǒng)優(yōu)化的關鍵。 國外將配送車輛調度問題歸結為VRP（Vehicle Routing Problem，即車輛路徑問題）、VSP（Vehicle Scheduling Problem，即車輛調度問題）

8、和MTSP（Multiple Traveling Salesman Problem，即多路旅行商問題）。該問題于1959年由Dantzig和Ramser提出后[2]，很快便引起運籌學、應用數(shù)學、組合數(shù)學、圖論與網(wǎng)絡分析、物流科學、計算機應用等學科的專家以及運輸計劃制定者的極大重視，并一直是運籌學與組合優(yōu)化領域的前沿與熱點問題。在現(xiàn)實生產(chǎn)和</p><p>　　第二章 課程設計的題目及要求</p>&

9、lt;p>　　2.1 配送車輛調度問題的描述 </p><p>　　配送車輛調度問題可以描述為：在一個存在供求關系的系統(tǒng)中，有若干臺車輛、若干個物流中心和客戶，要求合理安排車輛的行車路線和出行時間，從而在給定的約束條件下，把客戶需求的貨物從物流中心送到客戶，把客戶供應的貨物從客戶取到物流中心，并使目標函數(shù)取得優(yōu)化。 配送車輛調度問題可歸結為如下的一般網(wǎng)絡模型[3]：設G=（V，E，A）是一

10、個連通的混合網(wǎng)絡，V是頂點集（表示物流中心、客戶、停車場等），E、A分別為無向的邊集和有向的弧集，E中的邊和A中的弧均被賦權（可以表示配送的距離、時間或費用），V’、E’、A’分別為V、E、A的子集，求滿足約束條件（包括客戶的貨物需求或供應數(shù)量約束、需求或供應時間約束、配送車輛一次配送的最大行駛距離約束、車輛的最大載重量約束等），并包含V’、E’、A’的一些巡回路線，使目標函數(shù)取得優(yōu)化，目標函數(shù)可以取配送總里程最短、 2 配送車輛總噸位

11、公里數(shù)最少、配送總費用最低、配送總時間最少、使用的配送車輛數(shù)最少、配送車輛的滿載率最高等。 3 配送車輛調度問題的構成要素分析 配送車輛調度問題主要包括貨物、車輛、物流中心、客戶、運輸網(wǎng)絡、約束條件和目標函數(shù)等要</p><p>　　車輛的裝載量是指車輛的最大裝載重量和最大裝載容積，是進行車輛裝載決策的依據(jù)。在某配送系統(tǒng)中，車輛的裝載量可以相同，也可以不同。 對每臺車輛一次配送的行駛距離的要求可

12、分為以下幾種情況：①無距離限制；②有距離限制；③有距離限制，但可以不遵守，只是不遵守時需另付加班費。 車輛在配送前的停放位置可以在某個停車場、物流中心或客戶所在地。 車輛完成配送任務后，對其停放位置的要求可分為以下幾種情況：①必須返回出發(fā)點；②必須返回某停車場；③可返回到任意停車場；④可停放在任何停車場、物流中心或客戶所在地。 （3）物流中心。也稱為物流基地、物流據(jù)點，是指進行集貨、分貨、配貨、配裝、送貨作業(yè)的配送中心、倉庫、車

13、站、港口等。 在某配送系統(tǒng)中，物流中心的數(shù)量可以只有一個，也可以有一個以上；物流中心的位置可以是確定的，也可以是不確定的。對于某個物流中心，其供應的貨物可能有一種，也可能有多種；其供應的貨物數(shù)量可能能夠滿足全部客戶的需求，也可能僅能滿足部分客戶的需求。 （4）客戶。也稱為用戶，包括分倉庫、零售商店等?？蛻舻膶傩园ㄐ枨螅ɑ蚬┴浳锏臄?shù)量、需求（或供應）貨物的時間、需求（或供應）貨物的次</p><p>　　

14、某客戶對需求（或供應）貨物的滿足程度的要求可分為兩種情況：①要求全部滿足；②可以部分滿足，但不滿足時要受到懲罰。 （5）運輸網(wǎng)絡。運輸網(wǎng)絡是由頂點（指物流中心、客戶、停車場）、無向邊和有向弧組成的。邊、弧的屬性包括方向、權值和交通流量限制等。 </p><p>　　某運輸網(wǎng)絡中可能僅有無向邊；也可能僅有有向??；還可能既有無向邊，又有有向弧。 </p><p>　　運輸網(wǎng)絡中邊或弧的權值可

15、以表示距離、時間或費用。邊或弧的權值變化分為以下幾種</p><p>　　情況：①固定，即不隨時間和車輛的不同而變化；②隨時間不同而變化；③隨車輛的不同而變化；④既隨時間不同而變化，又隨車輛不同而變化。對運輸網(wǎng)絡權值間的關系可以要求其滿足三角不等式，即兩邊之和大于第三邊；也可以不加限制。 對運輸網(wǎng)絡中頂點、邊或弧的交通流量要求分為以下幾種情況：①無流量限制；②邊、弧限制，即每條邊、弧上同時行駛的車輛數(shù)有限；

16、③頂點限制，即每個頂點上同時裝、卸貨的車輛數(shù)有限；④邊、弧、頂點都有限制。 （6）約束條件。配送車輛調度問題應滿足的約束條件主要包括：①滿足所有客戶對貨物品種、規(guī)格、數(shù)量的要求；②滿足客戶對貨物發(fā)到時間范圍的要求；③在允許通行的時間進行配送（如有時規(guī)定白天不能通行貨車等）；④車輛在配送過程中的實際載貨量不得超過車輛的最大允許裝載量；⑤在物流中心現(xiàn)有運力范圍內。 （7）目標函數(shù)。對配送車輛調度問題，可以只選用一個目標，也可以選用多個目

17、標。經(jīng)常選用的目標函數(shù)主要有： ①配送總里程最短。配送里程與配送車輛的耗油量、磨損程度以及司機疲勞程度等直接相關，它直接決定運輸?shù)某杀荆瑢ε渌蜆I(yè)務的經(jīng)濟效益有很大影響。由于配送里程計算簡便，它是確定配送路線時用得最多</p><p>　　在日常生活和生產(chǎn)實際當中，如有一個中心貨場，需要向幾個顧客運送貨物，每個顧客丟貨有一定的要求，運送貨物的車輛在貨場裝滿貨后發(fā)出，把貨物送到各顧客處，完成任務后返回貨場，如何確定

18、滿足客戶需要的費用最小的車輛行駛路線，即配送貨車優(yōu)化調度。</p><p>　　許多類似的問題都可以歸結為集貨或送貨非滿載車輛優(yōu)化調度問題，一般描述為：有一個車場，擁有容量為Q的車輛，現(xiàn)在又L項勻速任務需要完成，以1，········，L表示，已知任務i的貨運量為（i=1，·····&

19、#183;··，L），且<q,要求滿足貨運需求的費用最小的車輛行駛路線。</p><p>　　無論送貨車輛優(yōu)化調度或者集貨車輛優(yōu)化調度，其實質是相同的，只有裝貨任務或者只有卸貨任務。在貨物量較少的情況下，用一輛車完成一項任務，車輛不能滿載，這樣車輛的利用率較低，浪費車輛資源，因此可考慮用一輛車完成多項任務。VSP中若每項任務還要求在一定的時間范圍內完成，則問題就成為有時間窗的車輛優(yōu)化調度

20、問題。</p><p>　　2.2任務的特征及要求</p><p><b>　　點之間的距離</b></p><p><b>　　第三章 題目分析</b></p><p>　　本小組課程設計研究物流配送車輛優(yōu)化調度問題，即VSP （Vehicle Routing Problem和Vehicle Sc

21、heduling Problem）。該問題一般定義為：對一系列裝貨點和（或）卸貨點，組織適當?shù)男熊嚶肪€，使車輛有序的通過它們，在滿足一定的約束條件（如貨物需求量、發(fā)送量、交發(fā)貨時間、車輛容量限制、行駛里程限制、時間限制等）下，達到一定的目標（如路程最短、費用最少等）。本小組選題為時間窗約束下的物流車輛優(yōu)化調度方案，即在一般VSP模型的約束條件中考慮時間要求后安排路線（稱車輛調度問題，Vehicle Scheduling Problem）

22、。</p><p>　　利用C—W節(jié)約啟發(fā)式算法，能有效地解決有時間窗約束的集貨或送貨的非滿載VSP問題，實現(xiàn)有約束情況下的最優(yōu)解，在滿足任務要求的前提下有力的節(jié)省了成本。通過對有時間窗約束的集貨或送貨的非滿載VSP問題的求解，盡力熟悉和熟練運用C—W節(jié)約啟發(fā)式算法，鍛煉了學生實際動手和理解運用能力，有利于學生解決生產(chǎn)生活的實際問題。</p><p>　　3.1一般VSP模型</p&

23、gt;<p>　　為構造數(shù)學模型，將車場編號為0，任務編號為,任務及車場均以點i來表示。定義變量如下：</p><p>　　1 點i的任務由車輛k完成；</p><p><b>　　0 否則。</b></p><p>　　1 車輛k從點i行駛到j點；</p><p><b>　　0

24、 否則。</b></p><p>　　則可得到車輛優(yōu)化調度數(shù)學模型如下：</p><p>　　模型中，表示從i點到j點的運輸成本，它的含義可以是距離、費用、變量、時間等，一般根據(jù)實際情況確定，可同時考慮車輛數(shù)和運行費用，如下確定：</p><p>　　當i為車場時，包括固定費用和運行費用</p><p>　　當i為任務時，只有運行

25、費用，即</p><p>　　其中，為相對于運行時間的費用系數(shù)；為車輛的固定費用，即增加一車輛的邊際費用。一般認為，派出一輛車的固定費用遠遠高于車輛的行駛費用，因此該模型在極小化車輛數(shù)的前提下，再極小化運行費用。減小的值將會是使用的車輛數(shù)增多，而線路長度縮短。若令，則模型目標是使用的車輛數(shù)最少。</p><p>　　3.2 時間窗VSP模型</p><p>　　設完

26、成任務i需要時間（裝貨或卸貨）表示為，又設任務i的開始時間需在一定時間范圍內，其中為任務i所允許的最早開始時間，為任務i所允許的最遲開始的時間。如果車輛到達i的時間早于，則車輛需在i處等待，如果車輛到達的時間晚于，任務i要延遲進度。求滿足貨物需求的費用最少的車輛行駛路線。此問題稱之為有時間窗的車輛優(yōu)化調度問題。</p><p>　　以表示車輛到達點i的時間，表示車輛由i行駛到點j的時間，一般應有以下關系式：<

27、;/p><p><b>　　硬時間窗VSP</b></p><p>　　硬時間窗VSP指每項任務必須在要求的時間范圍內完成，即必須滿足上式。若超出這個時間范圍，則得到的解為不可行解。</p><p><b>　　軟時間窗VSP</b></p><p>　　軟時間窗VSP指如果某項任務不能在要求的時間范圍

28、內完成，則給與一定的懲罰。</p><p>　　若車輛在之前到達點j，則車輛在此等待，發(fā)生了機會成本損失。</p><p>　　若車輛在之后達到點j，則服務被延誤，須支付一定罰金。</p><p>　　3.3 關于時間窗的寬度</p><p>　　對時間窗VSP的時間特性進行分析，給出以下定義。</p><p>　　定

29、義1 對任務i，要求其在時間范圍內執(zhí)行，則 稱為任務i的時間窗寬度。</p><p>　　定義2 對項貨物運輸任務，每項任務均要求在各自的時間窗內執(zhí)行，則平均時間窗寬度與平均時間的比值</p><p><b>　?。ǎ?lt;/b></p><p>　　稱為該問題的時間窗系數(shù)。</p><p>　　當TW在不同的范圍內，問題

30、有不同的特征：</p><p>　　TW=0，即每項任務有確定的開始時間。</p><p>　　TW>2，這段時間的時間窗約束放松，可能存在時間可行的回路，時間約束一般能夠滿足，問題的空間性支出與支配地位，一般來說，根據(jù)問題情況安排路線即可。</p><p>　　0<TW<2，這是時間窗約束較緊，時間可行的回路較少或沒有，問題的時間性質與空間性質相

31、比更可能屬于支配地位，在進行車輛調度時，必須考慮時間約束。</p><p>　　第四章 計算原理及流程圖</p><p><b>　　4.1算法原理</b></p><p>　　這里對旅行商問題的算法進行修正，用來求解有時間要求的硬時窗車輛優(yōu)化</p><p><b>　　調度問題。</b><

32、/p><p>　　符號說明同前，以C表示車輛從點i行駛到點j的費用，由C-W算法，得到點i</p><p>　　和點J連接在一條線路上費用節(jié)約值</p><p>　　S(i.j）=C+C-C</p><p>　　當不考慮時間約束時。其算法與c-w算法類似.只是在連接點對時.需考慮車輛</p><p>　　的量約束，即一條線

33、路上各任務的貨運量之和應不大于車輛的容量。</p><p>　　若各項任務要求在一定的時間范圍內完成，按費用節(jié)約值，S（i，j）連接點i與j</p><p>　　時.可能會使j后面的任務的執(zhí)行不滿足時間要求。當連接點i和點j所在線路時.若</p><p>　　車輛到達j點的時間比原線路上j點任務的開始時問提前。則車輛在j后面的任務處有</p><

34、p>　　可能需要等待;若連接后到達j點的時間比原線路上j點任務的開始時間推遲，則j后</p><p>　　面的任務在執(zhí)行時可能會發(fā)生延遲。</p><p>　　以EF表示連接點i和點j所在的線路后，車輛到達j點的時間比原線路上車輛到</p><p>　　達j點時間的推遲(或提前量).則EF可如下得到</p><p>　　EF=S+T+t

35、-S</p><p>　　顯然，EF<0時，車輛到達j點任務的時間提前;EF=0時.到達時間不變;EF</p><p>　　>0時.到達時間推遲。</p><p>　　為說明問題方便，定義參數(shù)如下:</p><p>　　?j—車輛在線路上j點后面的任務處均不需要等待的j點的到達時間的最大可</p><p>

36、<b>　　以提前量</b></p><p>　　?j—線路上j點后面的任務不違反時間窗約束的j點的到達時間的最大允許推遲</p><p><b>　　量。</b></p><p>　　?j和?j可分別按下式什算</p><p>　　?j={S-ET} ?j={LT-S}</p

37、><p>　　當考慮連接點i和點j所在的線路時.需檢查是否違反時間窗約束。</p><p>　　(1}當EF<0時，若有|EF|≤?j，車輛在j后面的任務處不需要等待.否則，要</p><p><b>　　等待;</b></p><p>　?。?}當EF>0時，若有EF≤?j，.則j后面的任務的執(zhí)行不會延遲，否則

38、，要延</p><p><b>　　遲進行。</b></p><p>　　由于時間約束的引入.在對稱的費用情況下，連接點j和點i與連接點i和點j已不</p><p><b>　　再相同。</b></p><p><b>　　4.2 流程圖</b></p><

39、p><b>　　第五章 計算過程</b></p><p>　　5.1計算各點對間連接的費用節(jié)約值</p><p>　　例如，連接點1和點2時，有</p><p>　　類似的，可得到連接其他各點對時的費用節(jié)約值，從大到小的順序示于表4-3中。</p><p>　　表4-3 點對之間連接的費用節(jié)約值</p>

40、<p>　　由于距離為對稱距離，因此有</p><p>　　故表中所示的，也可以表示為。</p><p><b>　　5.2構造線路</b></p><p>　　根據(jù)表4-3所示的的順序，逐項考察對應的i-j，點對之間的連接過程示于表4-4中。</p><p>　　表中第一列表示根據(jù)表4-3的順序考察的i-

41、j，若兩點均不在線路上，則考察i→j和j→i；若一點不在線路上，一點是外點，則考察i→j（i不在線路上、j是線路的起點，或i是線路的終點、j不在線路上）或者j→i（j不在線路上、i是線路的起點，或j是線路的終點、i不在線路上）；若兩點都是線路上的外點，則根據(jù)點的位置關系，構造成終點（一條線路）→起點（另一條線路）的順序；第二列表示考察的兩點的位置，若不滿足位置關系，顯然不能連接，不在考察其他各項，在第6列劃×，轉其他點對。第3

42、列表示連接后線路的總任務量，若大于車輛容量，則在第6列中劃×。第4列表示點i與點j連接后的。第5列為或，若，則計算；若，則計算。根據(jù)、（或），若滿足時間約束，則第6列表示線路i→j或j→i，否則劃×。第7列表示i與j連接后，j后面的各任務的新的開始時間。</p><p>　　當一個點不在線路上時，認為點i與車場單獨構成線路0—i—0。</p><p>　　由表4-4，得

43、到最終的線路為：</p><p><b>　　0→8→5→7→0</b></p><p><b>　　0→6→4→0</b></p><p><b>　　0→3→1→2→0</b></p><p>　　顯然各任務的開始時間均滿足時間窗約束。如表4-4中，對5-7，滿足,有5→7

44、，經(jīng)檢驗滿足,即不可能存在7→5，故無時間可行的回路，表中只表示了一種情況。</p><p>　　表4-4 點對之間的連接過程</p><p>　　第六章 算法的總結與分析</p><p>　　6.1處理其他的約束</p><p>　　算法還可以處理其他約束，如線路的長度約束，則考慮連接點對時，需檢查是否違反線路的長度限制?？傊?，約束越多，

45、考慮的因素越多，問題就越復雜，求解起來就越困難。</p><p>　　6.2算法的進一步討論</p><p>　　若允許車輛在任務處等待，也允許任務延遲進行，但要計等待損失費用和延遲罰款，即時間窗約束為軟時間窗約束，這時可對原費用節(jié)約值進行修正，得到：</p><p>　　式中，，分別為等待時間和延遲時間的相對費用系數(shù)，為連接點和點所在線路時，車輛在后面任務處的等待

46、時間，為任務開始執(zhí)行的延遲時間。和分別由下式得到：</p><p>　　顯然時，計算；時，計算。計算完所有后，根據(jù)連接點對。需要注意的是，每當連接一項后，各量可能會發(fā)生變化，因此需要重新計算，在考慮連接。</p><p><b>　　6.3算法的推廣</b></p><p>　　若每項任務都有各自的集貨點或送貨點與卸貨點，即集貨與送貨一體化車輛

47、優(yōu)化調度問題，這時，用表示從任務的集貨點至送貨點的時間，表示從任務的卸貨點到任務的裝貨點間的時間，則算法也可適用于該種情況。</p><p><b>　　6.4結論</b></p><p>　　有時間窗約束的由于它的強特性，使求解起來很困難，本節(jié)提出了求解該問題的啟發(fā)式算法，以的算法為基礎，構造了連接點對時對線路上點的最大允許提前時間或最大允許延遲時間的檢查約束，以及

48、等待懲罰和延遲懲罰的處理方法，設計了算法的實施程序，并應用實例進行了分析說明。該方法應用性好，可在連接點對時，同時考慮其他的約束。</p><p><b>　　附錄一 代碼設計</b></p><p>　　#include<stdio.h></p><p>　　#include<math.h></p>&

49、lt;p>　　#include<stdlib.h></p><p>　　int main()</p><p><b>　　{</b></p><p>　　float min(float,float);</p><p>　　int i,j,s[9][9]={0},n=8,L[9]={0},Q=8,Ln=0

50、,M[4]={0},jb=0,ib=0,a=0,b=0,N[5]={0},x=0,y=0;</p><p>　　float t[9][9]={0},DERTAa1,DERTAa2,DERTAb1,DERTAb2,k[9],EF[100],qq=0,q[8]={0};</p><p>　　float g[9]={0,2,1.5,4.5,3,1.5,4,2.5,3};</p>&

51、lt;p>　　float T[9]={0,1,2,1,3,2,2.5,3,0.8};</p><p>　　float ET[9]={0,1,4,1,4,3,2,5,1.5};</p><p>　　float LT[9]={0,4,6,2,7,5.5,5,8,4};</p><p>　　int d[9][9]={0,40,60,75,90,200,100,160

52、,80,40,</p><p>　　0,65,40,100,50,75,110,100,60,65,</p><p>　　0,75,100,100,75,75,75,75,40,75,</p><p>　　0,100,50,90,90,150,90,100,100,100,</p><p>　　0,100,75,75,100,200,50,1

53、00,50,100,</p><p>　　0,70,90,75,100,75,75,90,75,70,</p><p>　　0,70,100,160,110,75,90,75,90,70,</p><p>　　0,100,80,100,75,150,100,75,100,100,0};</p><p>　　printf("各任務的貨

54、運量g[i]如下：\n");</p><p>　　for (i=1;i<=n;i++)</p><p>　　{printf("g%d=%-5.1f",i,g[i]);</p><p><b>　　}</b></p><p>　　printf("\n\n\n");&l

55、t;/p><p>　　printf("各任務的裝貨（或卸貨）時間T[i]為：\n");</p><p>　　for (i=1;i<=n;i++)</p><p>　　{printf("T%d=%-5.1f",i,T[i]);</p><p><b>　　}</b></p&g

56、t;<p>　　printf("\n\n\n");</p><p>　　printf("各任務的開始執(zhí)行的時間范圍[ETi,LTi]為：\n");</p><p>　　for (i=1;i<=n;i++)</p><p>　　{printf("[ET%d,LT%d]=[%-3.1f,%-3.1f]

57、\n",i,i,ET[i],LT[i]);</p><p><b>　　}</b></p><p>　　printf("\n\n\n");</p><p>　　printf("車場0與各任務點間的距離d[i][j]為：\n"); </p><p>　　for(i=0;

58、i<=8;i++)</p><p>　　{for(j=0;j<=8;j++)</p><p>　　{printf("%5d",d[i][j]);}</p><p>　　printf("\n");</p><p><b>　　}</b></p><p&

59、gt;　　printf("\n\n");</p><p>　　printf("點對之間連接的費用節(jié)約值s[i][j]為：\n");</p><p>　　for(i=1;i<=8;i++)</p><p>　　{for(j=i+1;j<=8;j++)</p><p>　　{ s[i][j]=d

60、[i][0]+d[0][j]-d[i][j];</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　for(i=1;i<=8;i++)</p><p>　　{for(j=i+1;j<=8;j++)</p><p>　

61、　{printf("s[%d][%d]=%-5d",i,j,s[i][j]);}</p><p>　　printf("\n");</p><p><b>　　}</b></p><p>　　printf("\n");</p><p>　　for(i=0;i<

62、;=8;i++)</p><p>　　{for(j=0;j<=8;j++){t[i][j]=(float)d[i][j]/50;}}</p><p>　　for(i=0;i<=8;i++)</p><p>　　{if ((t[0][i]>=ET[i])&&(t[0][i]<=LT[i]))</p><p&g

63、t;　　{k[i]=t[0][i];}</p><p>　　if (t[0][i]<ET[i])</p><p>　　{k[i]=ET[i];}}</p><p><b>　　while (1)</b></p><p>　　{ ib=0;jb=0;</p><p>　　for(i=1;i&l

64、t;=8;i++)</p><p>　　{ for(j=i+1;j<=8;j++)</p><p>　　{if (s[i][j]>s[a][b]) {a=i;b=j;}} </p><p><b>　　}</b></p><p>　　if (s[a][b]==0) break;</p>

65、<p>　　N[1]=0;N[2]=M[1];N[3]=M[1]+M[2];N[4]=M[1]+M[2]+M[3];</p><p>　　for(i=0;i<8;i++)</p><p>　　{if (L[i]==a) {ib=1;x=i;}}</p><p>　　for(j=0;j<8;j++)</p><p>　　

66、{if (L[j]==b) {jb=1;y=j;}}</p><p>　　if (ib==0&&jb==0)</p><p>　　{qq=g[a]+g[b];if (qq>Q) {s[a][b]=0;continue;}</p><p>　　EF[b]=k[a]+T[a]+t[a][b]-k[b];</p><p>　　

67、EF[a]=k[b]+T[b]+t[a][b]-k[a];</p><p>　　DERTAb1=LT[b]-k[b];</p><p>　　DERTAb2=k[b]-ET[b];</p><p>　　DERTAa1=LT[a]-k[a];</p><p>　　DERTAa2=k[a]-ET[a];</p><p>　　

68、if (((EF[b]>=0)&&(DERTAb1>=EF[b]))||((EF[b]<0)&&(DERTAb2>=(0-EF[b]))))</p><p>　　{L[N[4]]=a;</p><p>　　L[N[4]+1]=b;</p><p><b>　　Ln=Ln+1;</b><

69、;/p><p><b>　　q[Ln]=qq;</b></p><p>　　k[b]=k[b]+EF[b];</p><p>　　s[a][b]=0;</p><p>　　M[Ln]=M[Ln]+2;</p><p>　　continue;}</p><p>　　else if

70、 ((EF[a]>=0&&DERTAa1>=EF[a])||(EF[a]<0&&(DERTAa2>=(0-EF[a]))))</p><p>　　{L[N[4]]=b;</p><p>　　L[N[4]+1]=a;</p><p><b>　　Ln=Ln+1;</b></p>

71、<p><b>　　q[Ln]=qq;</b></p><p>　　k[a]=k[a]+EF[a];</p><p>　　s[a][b]=0;</p><p>　　M[Ln]=M[Ln]+2;</p><p>　　continue;}</p><p><b>　　}</

72、b></p><p>　　if (ib==0&&jb==1)</p><p>　　{i=a;a=b;b=i;x=y;ib=1;jb=0;}</p><p>　　if (ib==1&&jb==0)</p><p>　　{if (x==N[1]||x==N[2]||x==N[3])</p>&l

73、t;p>　　{i=a;a=b;b=i;}</p><p>　　for(i=1;i<=3;i++)</p><p>　　{if (x==N[i])</p><p>　　{qq=q[i]+g[a];</p><p>　　if (qq>Q) {s[a][b]=0;s[b][a]=0;continue;}</p>&l

74、t;p>　　EF[b]=k[a]+T[a]+t[a][b]-k[b];</p><p>　　if (EF[b]>0) </p><p>　　{DERTAb1=min(LT[L[x]]-k[L[x]],LT[L[x+1]]-k[L[x+1]]);</p><p>　　if (EF[b]>DERTAb1) {s[a][b]=0;s[b][a]=0;co

75、ntinue;}}</p><p>　　if (EF[b]<0)</p><p>　　{DERTAb2=min(k[L[x]]-ET[L[x]],k[L[x+1]]-ET[L[x+1]]);</p><p>　　if ((0-EF[b])>DERTAb2) {s[a][b]=0;s[b][a]=0;continue;}}</p><p

76、>　　for(j=6;j>=x;j--)</p><p>　　{L[j+1]=L[j];}</p><p><b>　　L[x]=a;</b></p><p>　　k[L[x+1]]=k[L[x+1]]+EF[L[x+1]];</p><p>　　k[L[x+2]]=k[L[x+2]]+EF[L[x+1]];

77、</p><p><b>　　q[i]=qq;</b></p><p>　　M[i]=M[i]+1;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　for(i=1;i<=3;i++)</p

78、><p>　　{if (x==N[i+1]-1)</p><p>　　{qq=q[i]+g[b];</p><p>　　if (qq>Q) {s[a][b]=0;s[b][a]=0;continue;}</p><p>　　EF[b]=k[a]+T[a]+t[a][b]-k[b];</p><p>　　if (EF[

79、b]>=0) </p><p>　　{DERTAb1=LT[b]-k[b];</p><p>　　if (EF[b]>DERTAb1) {s[a][b]=0;s[b][a]=0;continue;}}</p><p>　　if (EF[b]<0)</p><p>　　{DERTAb2=k[b]-ET[b];</p>

80、;<p>　　if ((0-EF[b])>DERTAb2) {s[a][b]=0;s[b][a]=0;continue;}}</p><p>　　for(j=6;j>=x;j--)</p><p>　　{L[j+2]=L[j+1];L[x+1]=b;}</p><p>　　k[L[x+1]]=k[L[x+1]]+EF[L[x+1]];<

81、;/p><p>　　M[i]=M[i]+1;</p><p><b>　　q[i]=qq;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p>

82、;<p>　　s[a][b]=0;s[b][a]=0;</p><p><b>　　}</b></p><p>　　printf("得到的最終的路線為：\n");</p><p>　　for(i=1;i<=3;i++)</p><p>　　{printf("0->&

83、quot;);</p><p>　　for(j=N[i];j<N[i+1];j++){printf(" %d -> ",L[j]);}</p><p>　　printf("0");</p><p>　　printf("\n\n");</p><p><b>　　

84、}</b></p><p>　　printf("\n\n");</p><p>　　printf("各路線的總任務量Q[i]為：\n");</p><p>　　for(i=1;i<=3;i++){printf("Q[%d]=%3.1f\n",i,q[i]);}</p><

85、;p>　　printf("\n\n");</p><p>　　printf("各路線的新的開始時間s[i]為：\n");</p><p>　　for(i=1;i<=8;i++){printf("s[%d]=%3.1f\n",i,k[i]);}</p><p>　　printf("\n\

86、n");</p><p>　　system ("pause");</p><p>　　return(0);</p><p><b>　　}</b></p><p>　　float min(float x,float y)</p><p>　　{float z;z=x&