課程設(shè)計(jì)---有時(shí)間窗的車輛調(diào)度優(yōu)化問題

1、<p><b>　　目錄</b></p><p><b>　　目錄1</b></p><p>　　第一章 課程設(shè)計(jì)的目的及意義2</p><p>　　第二章 課程設(shè)計(jì)的題目及要求2</p><p>　　2.1 配送車輛調(diào)度問題的描述2</p><p>　　

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

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

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

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

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

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

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

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

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

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

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

13、站、港口等。 在某配送系統(tǒng)中，物流中心的數(shù)量可以只有一個(gè)，也可以有一個(gè)以上；物流中心的位置可以是確定的，也可以是不確定的。對(duì)于某個(gè)物流中心，其供應(yīng)的貨物可能有一種，也可能有多種；其供應(yīng)的貨物數(shù)量可能能夠滿足全部客戶的需求，也可能僅能滿足部分客戶的需求。 （4）客戶。也稱為用戶，包括分倉庫、零售商店等。客戶的屬性包括需求（或供應(yīng)）貨物的數(shù)量、需求（或供應(yīng)）貨物的時(shí)間、需求（或供應(yīng)）貨物的次</p><p>　　

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

42、列表示連接后線路的總?cè)蝿?wù)量，若大于車輛容量，則在第6列中劃×。第4列表示點(diǎn)i與點(diǎn)j連接后的。第5列為或，若，則計(jì)算；若，則計(jì)算。根據(jù)、（或），若滿足時(shí)間約束，則第6列表示線路i→j或j→i，否則劃×。第7列表示i與j連接后，j后面的各任務(wù)的新的開始時(shí)間。</p><p>　　當(dāng)一個(gè)點(diǎn)不在線路上時(shí)，認(rèn)為點(diǎn)i與車場(chǎng)單獨(dú)構(gòu)成線路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>　　顯然各任務(wù)的開始時(shí)間均滿足時(shí)間窗約束。如表4-4中，對(duì)5-7，滿足,有5→7

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

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

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

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

48、等待懲罰和延遲懲罰的處理方法，設(shè)計(jì)了算法的實(shí)施程序，并應(yīng)用實(shí)例進(jìn)行了分析說明。該方法應(yīng)用性好，可在連接點(diǎn)對(duì)時(shí)，同時(shí)考慮其他的約束。</p><p><b>　　附錄一 代碼設(shè)計(jì)</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("各任務(wù)的貨

54、運(yùn)量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("各任務(wù)的裝貨（或卸貨）時(shí)間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("各任務(wù)的開始執(zhí)行的時(shí)間范圍[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("車場(chǎng)0與各任務(wù)點(diǎn)間的距離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("點(diǎn)對(duì)之間連接的費(fèi)用節(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("各路線的總?cè)蝿?wù)量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("各路線的新的開始時(shí)間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&