垃圾運輸模組化論文

垃圾運輸問題

摘  要

我們就生活中垃圾運輸的問題的排程方案予以研究。本文通過對問題的分析和合理的假設，采用規劃的理論建立了單目标的非線性規劃的數學模型。，運用軟體得到了全局最優解，對此類問題的求解提供了一種較優的方案。

題中的問題（1）包含着垃圾量和運輸費用的累積計算問題，是以，文中以運輸車所花費用最少為目标函數，以運輸車載重量的大小、當天必須将所有垃圾清理完等為限制條件，以運輸車是否從一個垃圾站點到達另一個垃圾站點為決策變量，建立了使得運輸費用最小的單目标的非線性規劃模型。運用求解，得出了最優的運輸路線為10條，此時運輸所花費用為2335.77元。通過分析，發現隻需6輛運輸車（載重量為6噸）即可完成所有任務，且每輛運輸車的工作時間均在4個小時左右。具體結果見文中表3。

問題（2），建立了以運作路徑最短為目标的單目标非線性規劃模型。進而求出了使鏟車費用最少的3條運作路線，且各條路線的工作時間較均衡。是以，處理站需投入3台鏟車才能完成所有裝載任務，且求得鏟車所花費用為202.0元，三輛鏟車的具體運作路線見文中表4。文中，我們假定垃圾處理站的運輸工作從晚21：00開始，根據各鏟車的運輸路線和所花時間的大小，将鏟車和運輸車互相配合進行工作的時間做出了詳細的安排見表5。

問題（3），要求給出當有載重量為4噸、6噸、8噸三種運輸車時的最優的排程方案。基于第（1）問中的模型，修改載重量的限制條件，用和分别求解，得出兩種排程方案，但總的運輸費用不變，均為2326.17元；對于方案一，有9條路徑，分别需要4噸的運輸車1輛；6噸的運輸車2輛；8噸的運輸車5輛，各運輸車具體的運輸線路見文中表8。對于方案二，有10條路徑，分别需要4噸的運輸車1輛；6噸的運輸車1輛；8噸的運輸車4輛，各運輸車具體的運輸線路見文中表10。

最後，對模型的優缺點進行了分析，并給出了模型的改進意見，對解決實際問題具有一定的指導意義。

關鍵字： 垃圾運輸的排程；線性規劃；最優解

問題的分析

   這是一個便利問題，此問題的困難之處在于确定鏟車的行走路線，并使得運輸車工作時盡量不要等待鏟車，才能使得運輸車的工作時間滿足題目的要求——每日平均工作四小時，為此，應該使鏟車跟着運輸車跑完一條線路，也就是說，應該使鏟車鏟完一條線路後再接着鏟下一條線路。

第（1）問，對于運輸車排程方案的設計，不能僅僅考慮使運輸車的行走路線最短，因為此處還存在着垃圾的累積運輸的花費問題，是以，我們的目标函數應該是使得所有運輸的花費最少。在模組化過程中，我們無需考慮投入的運輸車台數，隻需對各條路徑所花費的時間進行和各運輸車載重量限制即可，至于投入的車輛數，在各條路徑确定後，計算出各路徑運輸所花費的時間，再根據題目中要求的每輛車平均工作時間為4小時左右進行計算即可。

第（2）問中，對于鏟車的排程方案，因其無累積計算問題，是以隻需要在已确定的各運輸路徑的基礎上，使得鏟車的行駛路徑為最短。在此方案中，我們将已确定的各條路徑看作為節點，建立使鏟車運費最少（亦即路徑最短）的非線性規劃模型，在此需注意的是，由于垃圾運輸為夜間運輸，是以每輛鏟車的工作時間也受到一定的限制，文中，我們假定鏟車的工作時間為從（晚21：00～早6：00），是以每輛鏟車的工作時間最多為9個小時，再由所有運輸車完成任務所需的總時間判定所需鏟車的台數，之後可以根據具體情況進行調整。同時應注意，由于運輸車有工作時間的限制，而鏟車沒有嚴格的限制（除工作時間不能超過9小時以外），是以，在确定鏟車出行的時間時，應保證隻可讓鏟車等待運輸車，而不能讓運輸車等待鏟車。

對于第（3）問，是在第一問的基礎上将對運輸車載重的限制條件從不大于6噸改為不大于8噸，在求得各條路線中，對于垃圾量不大于4噸的路線，調用4噸的運輸車；對于垃圾量在（4～6噸）之間的路線，調用6噸的運輸車；對于垃圾量在（6～8噸）之間的路線，調用8噸的運輸車。

一 模型假設

（1）假設各站點每天的垃圾量是不變的；

（2）假設各站點的垃圾都必須在當天清理完畢；

（3）不考慮運輸車和鏟車在行駛過程中出現的塞車、抛錨等耽誤時間的情況；

（4）不允許運輸車有超載現象；

（5）每個垃圾站點均位于街道旁，保證運輸車和鏟車行駛順暢；

二 模型的建立及求解

1 符号說明

   每天運輸前第個垃圾站點的垃圾量；

 第個垃圾站點向第個垃圾站點運輸的垃圾量；

 運輸車是否從第個垃圾站點向第個垃圾站點運輸的0-1變量；

第輛鏟車是否從第條路徑向第條路徑運輸的0-1變量；

 第個垃圾站點和第個垃圾站點之間的距離；

 第條路徑到第條路徑的有向距離；

   垃圾運輸車的機關量貨物每公裡的運輸費用；

   垃圾運輸車和鏟車每公裡的空載費用；

   鏟車通過第條路徑所需要的時間（包括在各垃圾站點裝車的時間）

   假設所需要的鏟車的台數 

2 模型的建立

2．1 運輸車排程方案的模型

對于運輸車的排程方案，我們建立單目标規劃的非線性模型使得運輸費用最小，模型如下。

2.1.1目标函數的建立

考慮使運輸費用最小時，目标函數包括兩個方面的費用：空載費用和重載費用。其中，空載費用為第37号站點直接到達的其他各點所花的費用；而重載費用為上一個點（除37号站點）到下一個點（包括37号站點）所花的費用，表示如下：   

：

2.1.2限制條件的确立

（1）對于各個垃圾站點，隻有一輛運輸車經過，即每個站點的運進點和運出點均是有且隻有一個，即：

其中，

（2）運輸車到達某個站點後，必須将此站點的所有垃圾帶走：

（3）不允許出現自己往自己站點運輸垃圾的現象,即當時有：

　（4）不允許從第37号站點（垃圾處理站）運出垃圾，即：

（5）各點的垃圾都必須在當天清理完畢，不允許有滞留：

（6）各垃圾運輸車不允許有超載現象，即每輛車的載重最多為6噸：

2．1.3單目标規劃模型

在給出了目标函數和限制條件後，即可得到一個使得運輸費用最小的單目标規劃模型如下：

：	（1）

2.2 鏟車排程方案的模型

此模型的建立基于上問模型的結果，從以上運輸車的排程方案得出共有10條路徑，在此模型中，我們将10條路徑分别看作10個節點，而把垃圾處理站看作為第11個節點（以下将各路徑均稱作節點），建立了使鏟車行駛所需費用最小的模型。在此需要說明的是，由于運輸車的路徑已經确定，我們隻能讓鏟車跟随着運輸車，而不能讓運輸車在垃圾站點等待鏟車。由此可以确定,鏟車必須跟随着運輸車行走完一條路徑，才能轉到其他路徑繼續工作。而對于各路徑，其行走方案已定，是以各路徑内的費用已經确定。是以，我們需要做的是，找出一種排程方案使鏟車在各路徑之間的行走所需的費用為最小。

2.2.1目标函數的建立

各路徑内的費用已定，是以我們建立以下使鏟車在各路徑之間行走所需費用最小的目标函數如下：

2.2.2 限制條件的确立：

（1）對于1到10号的每個節點，隻允許一輛鏟車通過，且隻通過一次：

（2）所有的鏟車必須從第11号節點（垃圾處理站）出發，并最終回到11号節點，即從11号節點發出的鏟車數和最終傳回11号節點的鏟車數均為N：

（3）為保證每輛鏟車均從11号節點出發最終回到11号節點，且不重複已走的路徑，則需控制鏟車所走路徑均為一個環，即對于每個節點，隻要有鏟車進入則必有鏟車出，不進則無出，進與出的狀态保持一緻：

（4）對于每個節點，不允許出現鏟車向自己節點運作的路徑：

（5）不允許出現鏟車的路徑為，除11号節點以外，在其他節點互相運作的路徑：

（6）由于垃圾的運輸均在夜間進行，則每輛鏟車的工作時間不能大于9個小時（即假定工作時間為從晚21：00～早6：00），另外，由于題目中沒有給定鏟車的運作速度，不妨假定其平均速度與運輸車的平均速度相同，為40公裡/小時，的限制條件為：

2.2.3鏟車規劃模型

在給出了目标函數和限制條件後，即可得到一個使得鏟車運作費用最小的單目标規劃模型如下：

（2）

2.3 載重量不同的運輸車排程方案模型

此問在第一問的基礎上，通過改變垃圾運輸車載重量的大小，進而得到垃圾處理廠在擁有不同載重量的運輸車時，采用怎樣的運輸方案使得所花運輸費用最少。此模型的目标函數與第一問中的運輸車排程方案模型相同，隻是在限制條件上将第（6）個限制條件中的載重最多為6噸變成最多為8噸，

：	（3）

進而可求出在擁有不同載重量運輸車的情況下，各運輸車的排程方案。

模型的求解

3 運輸車排程方案模型的求解

利用LINGO10程式設計，對運輸車排程方案的模型（1）進行求解,求得各垃圾站點的運輸方案如表2所示，此時，求得将所有垃圾運回到37号站點運輸車所需費用為2335.77元。

表2：各運輸路徑所包含的垃圾站點、運輸量及所需時間

路徑	包含的站點	運輸垃圾總量	每條線路所需時間
1	37—30—29—27—37	5.3噸	3小時46分鐘
2	37—28—26—21—25—19—37	5.7噸	3小時02分鐘
3	37—36—23—33—32—37	5.5噸	2小時46分鐘
4	37—24—18—35—20—37	5.2噸	2小時22分鐘
5	37—34—17—16—2—37	5.0噸	2小時7分鐘
6	37—15—13—7—4—37	5.6噸	2小時4分鐘
7	37—14—31—5—6—37	5.85噸	1小時46分鐘
8	37—22—10—37	3.3噸	1小時23分鐘
9	37—12—8—3—37	5.55噸	1小時30分鐘
10	37—11—9—1—37	4.0噸	1小時30分鐘

  從上表可以看出，對于這10條路徑上的垃圾總量，有8條都超過了5噸，另兩條也超過了載重量的一半，運輸車得到了充分地利用，結果非常好。

各運輸路徑以圖示表示如下：

圖1：運輸車行走路線圖

由圖1可以看出，10條路徑中隻有2條路徑有交叉點，其他路徑各自互不幹擾，結果很理想。

由題目可知，每台運輸車的平均工作時間為4小時，根據此條件對以上10條路徑進行規劃，發現用6台運輸車即可按要求行走完10條路徑，是以，處理站隻需投入6台垃圾運輸車即可完成任務。各運輸車行走的路徑分别表示如下：

表3：各運輸車的行走路徑、具體路線及所需時間

運輸車編号	路徑編号	行走路線	所需時間
第一輛	2	37—28—26—21—25—19—37	3小時02分鐘
第二輛	1	37—30—29—27—37	3小時46分鐘
第三輛	8	37—22—10—37	4小時9分鐘
3	37—36—23—33—32—37
第四輛	9	37—12—8—3—37	3小時37分鐘
5	37—34—17—16—2—37
第五輛	4	37—24—18—35—20—37	3小時52分鐘
10	37—11—9—1—37
第六輛	6	37—15—13—7—4—37	3小時50分鐘
7	37—14—31—5—6—37

    由上表可發現，每輛運輸車的運輸時間均在4個小時左右，相差很少，很好地達到了時間上的要求，且結果很理想。

3.1鏟車排程方案模型的求解

利用LINGO10程式設計，對鏟車排程方案模型（2）進行求解，得到了使鏟車運費最少的行走路線。此時，需要投入的鏟車數為3台，且所有鏟車完成任務所需費用為202.0元，各鏟車的具體行駛路線及所花費的時間如下表.

表4：各鏟車的具體行駛路線及所花費的時間

鏟車	行走路徑	具體路線	所需時間
第一台	8，9， 6，5	37—22—10—12—8—3—15—13—7—4—34—17—16—2—37	5小時22分
第二台	1，3，10	37—30—29—27—36—23—33—32—11—9—1—37	5小時50分
第三台	2，4，7	37—28—26—21—25—19—24—18—35—20—14—31—5—6—37	5小時36分

   由上表可以看出3台鏟車的工作時間均為5個多小時，相差不大，工作配置設定地非常合理。

各鏟車的行駛路線表示在圖上如圖2所示：

圖2：各鏟車的具體行駛路線圖

3.2鏟車及運輸車排程方案的具體時間安排

在問題的分析中，我們提到，由于垃圾運輸是在夜間進行，是以，我們假定運輸車及鏟車的工作時間從晚21：00～早6：00，對于運輸車排程方案，由于第三輛～第六輛都要運輸兩條路徑上的垃圾，是以，需要确定這4輛運輸車具體先行駛哪條路徑，而此方案的确定依賴于鏟車的行走方案。根據以上求得的各鏟車和運輸車工作所需時間的多少及鏟車應配合運輸車進行工作的原則，對他們的工作時間進行安排如下表所示。

表5：鏟車及運輸車互相配合的具體時間安排

鏟車1：

運輸路線	8	9	6	5
包含站點	22—10	12—8—3	15—13—7—4	34—17—16—2
時間及 車号	到達 時間	車輛 編号	到達 時間	車輛 編号	到達 時間	車輛 編号	到達 時間	車輛 編号
鏟車	21:31	1	22:11	1	23:26	1	0:58	1
運輸車	21:31	4	22:11	3	23:26	6	0:58	4

鏟車2：

運輸路線	1	3	10
包含站點	30—29—27	36—23—33—32	11—9—1
時間	到達 時間	車輛 編号	到達 時間	車輛 編号	到達 時間	車輛 編号
鏟車	22:09	2	23:12	2	1:30	2
運輸車	22:09	2	0:20	3	1:50	5

鏟車3：

運輸路線	2	4	7
包含站點	28—26—21—25—19	24—18—35—20	14—31—5—6
時間	到達 時間	車輛 編号	到達 時間	車輛 編号	到達 時間	車輛 編号
鏟車	22:06	3	23:42	3	0:49	3
運輸車	22:06	1	23:42	5	1:23	6

以上時間安排均是基于工作時間從晚21：00開始，從上表3和表4可以看出，每輛運輸車和每台鏟車的工作時間都不超過6個小時，是以，垃圾處理站可根據實際情況将工作開始的時間向前或向後推相應的時間即可。

由表5的時間安排可以确定出各運輸車的具體行駛路線及出發、傳回時間如表6所示.

表6:運輸車的行走路線

運輸車編号	從37号站點 出發時間	行走路線	傳回37号 站點時間
第一輛	21:00	37—28—26—21—25—19—37	00:02
第二輛	21:00	37—30—29—27—37	00:46
第三輛	21:11	37—12—8—3—37	22:41
22:47	37—36—23—33—32—37	01:33
第四輛	21:00	37—22—10—37	22:23
0:15	37—34—17—16—2—37	02:22
第五輛	22:51	37—24—18—35—20—37	01:13
01:15	37—11—9—1—37	02:45
第六輛	22:44	37—15—13—7—4—37	0:48
0:50	37—14—31—5—6—37	02:36

3.3 載重量不同的運輸車的排程方案

3.3.1 方案一

運用LINGO對模型（3）進行求解可以得到以下9條運輸路徑，以問題分析中運輸車選擇的原則即：對于垃圾量不大于4噸的路線，調用4噸的運輸車；對于垃圾量在（4～6噸）之間的路線，調用6噸的運輸車；對于垃圾量在（6～8噸）之間的路線，調用8噸的運輸車來為各路徑選擇運輸車，具體資料如表7所示。此情況下求得的運輸費用為2326.17元。

表7：方案一的各運輸各路徑、運輸的總垃圾量及運輸所需時間

運輸路徑	包含的垃圾站點	運輸總垃圾量	運輸所需時間
1	12，10	4.2 噸	1.33小時
2	13，8	4.1 噸	1.38小時
3	16	1.5 噸	1.07小時
4	18，14，31，5，6	7.35 噸	2.23小時
5	24，17，3，1	4.45 噸	2.37小時
6	28，26，21，25，19，9	7.1 噸	3.20小時
7	30，29，27，15，11	7.8 噸	3.13小時
8	34，35，20，7，4，2	7.2 噸	2.45小時
9	36，23，33，32，22	7.3 噸	2.93小時

由以上各條路徑上的垃圾總量的大小來對運輸車輛進行選擇，根據各路徑運輸所需時間的大小，對各輛運輸車的行駛方案進行規劃，得到結果如下表。

表8：不同載重量的運輸車對應的方案一的線路安排

車輛 編号	車輛 選擇	經過 路徑	經過的節點	運輸總 時間
第一輛	4噸	3	37 －16－37	1.07小時
第二輛	6噸	1，2	37－12－10－37－13－8－37	2.72小時
第三輛	6噸	5	37－24－17－3－1－37	2.37小時
第四輛	8噸	4	37－18－14－31－5－6－37	2.23小時
第五輛	8噸	6	37－28－26－21－25－19－9－37	3.20小時
第六輛	8噸	7	37－30－29－27－15－11－37	3.13小時
第七輛	8噸	8	37－34－35－20－7－4－2－37	2.45小時
第八輛	8噸	9	37－36－23－33－32－22－37	2.93小時

根據以上資料可得，當有載重量為4噸、6噸、8噸三種運輸車時，需要各類載重的運輸車輛分别為：對于4噸的運輸車，需要1輛；對于6噸的運輸車，需要3輛；對于8噸的運輸車，需要5輛。

畫出此時各運輸車的行走路線圖如圖3所示。

圖3：方案一中不同載重量情況下各運輸車行走的路線圖

3.3.2方案二

運用MATLAB程式設計對模型（3）求解，可以得到另外一種排程方案，共有10條運輸路徑，所花費用與LINGO求解相同，為2326.17元。各路徑的垃圾總量、運輸所需時間分别表示如下：

表9：方案二的各路徑包含的垃圾站點、垃圾總量及運輸所需時間

運輸路徑	包含的垃圾站點	運輸的總垃圾量	運輸所需時間
1	30，29，27，15	6.7	2.97小時
2	28，26，21，25，19，14	7.5	3.2小時
3	36，23，33，32，22	7.3	2.93小時
4	24，18，35，20，31	7.1	2.53小時
5	34，17，16，6，	4.35	2.12小時
6	13，7，4，2	5.7	1.72小時
7	12，8，3，1	7.05	1.67小時
8	11，10	2.6	1.33小時
9	5	1.3	0.87小時
10	9	1.4	0.77小時

同方案一，可根據各路徑的垃圾總量選擇運輸車輛，根據各路徑運輸所花時間對運輸車的行走路徑進行安排。得到具體的結果如下表10所示：

表10：方案二各運輸車的線路安排

車輛 編号	車輛 選擇	經過 線路	經過節點	運輸所 需時間
第一輛	4噸	8	37－11－10－37－5－37－9－37	3.02小時
第二輛	6噸	5，6	37－34－17－16－6－37－13－ 4－2－37	3.84小時
第三輛	8噸	1	37－30－29－27－15－37	2.97小時
第四輛	8噸	2	37－28－21－25－19－14－37	3.2小時
第五輛	8噸	3	37－36－23－33－32－22－37	2.93小時
第六輛	8噸	4，7	37－24－18－35－20－31－37－ 12－8－3－1－37	4.2小時

對于方案二，由以上資料可得：當有載重量為4噸、6噸、8噸三種運輸車時，需要各類載重的運輸車輛分别為：對于4噸的運輸車，需要2輛；對于6噸的運輸車，需要1輛；對于8噸的運輸車，需要4輛。相比較來說，對于兩種方案，方案二的結果較好，雖然運輸路徑較方案一多一條，但是需要的車輛數卻比方案一要少一輛，且運輸車的使用率較高。

相應的各輛運輸車的行走路線圖如下：

圖4：方案二中不同載重量情況下各運輸車行走的路線圖

四 結果分析

由于題目中沒有給出司機的工資額，是以文中隻考慮了垃圾的運輸費用。但實際生活中，對于垃圾處理站來說，垃圾的運輸所需花費不僅包括運輸費用還包括付給司機的工資。運輸路徑越長，運輸所需要的時間就越長，所需要的運輸車輛越多，進而需要更多的司機，因而花費更大。是以，在給出了司機工資額的情況下，目标函數中還包括付給司機的工資。另外，此時目标函數不再是單目标函數，而是雙目标函數。第二個目标函數是使得運輸車行駛的路徑最短。

五 模型評價

模型的優點

（1）此問題為典型的NP難問題，規劃模型的規模較大，共有2000多個變量，直接求解比較困難。由于在設計算法時采用了一些技巧，将變量減少到800多個，進而求出了最優的結果。

（2）模型中将各限制條件均考慮在内，對問題的了解較全面，是以求出的結果為最優。

（3）克服了NP難問題中很難得到最優解的問題，通過對算法的技巧性設計，使得此問題得以圓滿的解決

模型的缺點

此問題在模組化中存在很多難點，是以模型中隻考慮了，對于一個垃圾站點，一旦有運輸車到此運輸，則必須将所有垃圾帶走，而不能分批次運輸，進而導緻第8和第10條路徑的總垃圾量分别為3.3和4噸，運輸量太少的情況，運輸車不能得到充分地利用。

六 參考文獻

韓中庚.數學模組化競賽·獲獎論文精選與點評.北京：科學出版社，2007.

謝金星，薛毅.優化模組化與LINDO/LINGO軟體.北京：清華大學出版社.2006.

Winston,W.L.運籌學·應用範例與解法.北京：清華大學出版社.2006.

9.附錄

附件1：運輸車排程方案的程式

sets:

jiedian/1..37/:s,m;

link1(jiedian,jiedian):x,u,d;

endsets

data:

a=0.4;

b=1.8;

s=?;

d=?;

enddata

min=F;

!運輸費用;

F=@sum(jiedian(t)|t#le#36:a*d(37,t)*u(37,t))+@sum(link1(i,j):b*x(i,j)*d(i,j));

!運輸時間;

[email protected](link1(i,j):d(i,j)*u(i,j)/40)+1/6*@sum(link1(t,k)|t#le#36:u(t,k))[email protected](jiedian(t)|t#le#36:d(37,t)*@sum(jiedian(i):u(t,i)-u(i,t)))/40;

!37号節點沒有垃圾運出;

@for(jiedian(j):x(37,j)=0);

!最終垃圾全部被運到37号節點;

@sum(jiedian(i)|i#le#36:x(i,37))=51;

!定義0-1變量;

@for(link1:@bin(u));

!不允許各節點自己往自己運輸垃圾;

@for(jiedian(i)|i#le#36:x(i,i)=0);

!每個站點隻允許一輛車在此處運出垃圾;

@for(jiedian(i)|i#le#36:@sum(jiedian(j):u(i,j))=1);

!每個站點隻允許一輛車在此處運進垃圾;

@for(jiedian(i)|i#le#36:@sum(jiedian(j):u(j,i))=1);

!運出量等于運進來的加上該站點原有的垃圾量;

@for(link1(t,i)|t#le#36:x(t,i)=u(t,i)*(@sum(jiedian(j):x(j,t))+s(t)));

!每輛車的載重不超過6噸;

@for(link1(i,j)|i#le#36:x(i,j)<=6);

@for(jiedian(i)|i#le#36:u(1,i)=0);

@for(jiedian(i)|i#le#36:x(1,i)=0);

@for(jiedian(i)|i#le#36:u(2,i)=0);

@for(jiedian(i)|i#le#36:x(2,i)=0);

@for(jiedian(i)|i#le#36#and#i#ne#1:u(3,i)=0);

@for(jiedian(i)|i#le#36#and#i#ne#1:x(3,i)=0);

@for(jiedian(i)|i#le#36#and#i#ge#3:u(4,i)=0);

@for(jiedian(i)|i#le#36#and#i#ge#3:x(4,i)=0);

@for(jiedian(i)|i#le#36#and#i#ge#3#and#i#ne#6:u(5,i)=0);

@for(jiedian(i)|i#le#36#and#i#ge#3#and#i#ne#6:x(5,i)=0);

@for(jiedian(i)|i#le#36:u(6,i)=0);

@for(jiedian(i)|i#le#36:x(6,i)=0);

@for(jiedian(i)|i#le#36#and#i#ge#5#and#i#ne#6:u(7,i)=0);

@for(jiedian(i)|i#le#36#and#i#ge#5#and#i#ne#6:x(7,i)=0);

@for(jiedian(i)|i#le#36#and#i#ge#4:u(8,i)=0);

@for(jiedian(i)|i#le#36#and#i#ge#4:x(8,i)=0);

@for(jiedian(i)|i#le#36#and#i#ge#2:u(9,i)=0);

@for(jiedian(i)|i#le#36#and#i#ge#2:x(9,i)=0);

@for(jiedian(i)|i#le#36:u(10,i)=0);

@for(jiedian(i)|i#le#36:x(10,i)=0);

@for(jiedian(i)|i#le#36#and#i#ge#2#and#i#ne#9#and#i#ne#10:u(11,i)=0);

@for(jiedian(i)|i#le#36#and#i#ge#2#and#i#ne#9#and#i#ne#10:x(11,i)=0);

@for(jiedian(i)|i#le#36#and#i#ge#4#and#i#ne#9#and#i#ne#10#and#i#ne#8:u(12,i)=0);

u(13,5)=0;x(13,5)=0;

@for(jiedian(i)|i#le#36#and#i#ge#4#and#i#ne#9#and#i#ne#10#and#i#ne#8:x(12,i)=0);

@for(jiedian(i)|i#le#36#and#i#ge#10:u(13,i)=0);

@for(jiedian(i)|i#le#36#and#i#ge#10:x(13,i)=0);

@for(jiedian(i)|i#le#36#and#i#ge#10#and#i#ne#31:u(14,i)=0);

@for(jiedian(i)|i#le#36#and#i#ge#10#and#i#ne#31:x(14,i)=0);

@for(jiedian(i)|i#le#36#and#i#ge#14:u(15,i)=0);

u(15,5)=0;x(15,5)=0;

@for(jiedian(i)|i#le#36#and#i#ge#14:x(15,i)=0);

@for(jiedian(i)|i#le#36#and#i#ge#7:u(16,i)=0);

@for(jiedian(i)|i#le#36#and#i#ge#7:x(16,i)=0);

@for(jiedian(i)|i#le#5#and#i#ne#2:u(16,i)=0);

@for(jiedian(i)|i#le#5#and#i#ne#2:x(16,i)=0);

@for(jiedian(i)|i#le#36#and#i#ge#7:u(17,i)=0);

@for(jiedian(i)|i#le#36#and#i#ge#7:x(17,i)=0);

@for(jiedian(i)|i#le#36#and#i#ge#10#and#i#ne#14#and#i#ne#16#and#i#ne#20#and#i#ne#31:u(18,i)=0);

@for(jiedian(i)|i#le#36#and#i#ge#10#and#i#ne#14#and#i#ne#16#and#i#ne#20#and#i#ne#31:x(18,i)=0);

@for(jiedian(i)|i#le#36#and#i#ge#8:u(20,i)=0);

@for(jiedian(i)|i#le#36#and#i#ge#8:x(20,i)=0);

@for(jiedian(i)|i#le#36#and#i#ne#10:u(22,i)=0);

@for(jiedian(i)|i#le#36#and#i#ne#10:x(22,i)=0);

!;

@for(jiedian(i)|i#le#36#and#i#ge#11:u(19,i)=0);u(19,11)=0;

@for(jiedian(i)|i#le#36#and#i#ge#11:x(19,i)=0);x(19,11)=0;

@for(jiedian(i)|i#le#36#and#i#ge#21#and#i#ne#25#and#i#ne#35:u(21,i)=0);u(21,15)=0;u(21,17)=0;u(21,18)=0;

@for(jiedian(i)|i#le#36#and#i#ge#21#and#i#ne#25#and#i#ne#35:x(21,i)=0);x(21,15)=0;x(21,17)=0;x(21,18)=0;

@for(jiedian(i)|i#le#36#and#i#ge#14#and#i#ne#15#and#i#ne#22#and#i#ne#32#and#i#ne#33:u(23,i)=0);u(23,5)=0;   @for(jiedian(i)|i#le#36#and#i#ge#14#and#i#ne#15#and#i#ne#22#and#i#ne#32#and#i#ne#33:x(23,i)=0);x(23,5)=0;

@for(jiedian(i)|i#le#36#and#i#ge#21#and#i#ne#25#and#i#ne#31#and#i#ne#35:u(24,i)=0);u(24,15)=0;u(24,11)=0;    @for(jiedian(i)|i#le#36#and#i#ge#21#and#i#ne#25#and#i#ne#31#and#i#ne#35:x(24,i)=0);x(24,15)=0;x(24,11)=0;

@for(jiedian(i)|i#le#36#and#i#ge#15#and#i#ne#19#and#i#ne#20#and#i#ne#31:u(25,i)=0);u(25,11)=0;   @for(jiedian(i)|i#le#36#and#i#ge#15#and#i#ne#19#and#i#ne#20#and#i#ne#31:x(25,i)=0);x(25,11)=0;

@for(jiedian(i)|i#le#36#and#i#ge#22#and#i#ne#25#and#i#ne#31#and#i#ne#35:u(26,i)=0);u(23,17)=0;  @for(jiedian(i)|i#le#36#and#i#ge#22#and#i#ne#25#and#i#ne#31#and#i#ne#35:x(26,i)=0);x(23,17)=0;

@for(jiedian(i)|i#le#36#and#i#ge#16#and#i#ne#19#and#i#ne#22#and#i#ne#31:u(27,i)=0);

@for(jiedian(i)|i#le#36#and#i#ge#16#and#i#ne#19#and#i#ne#22#and#i#ne#31:x(27,i)=0);

u(28,29)=0;u(28,23)=0;u(28,30)=0;u(28,33)=0;u(28,36)=0;

u(29,17)=0;u(29,18)=0;u(29,23)=0;u(29,24)=0;u(29,26)=0;u(29,28)=0;u(29,30)=0;u(29,34)=0;u(29,36)=0;

u(30,24)=0;u(30,28)=0;u(30,34)=0;u(30,36)=0;

@for(jiedian(i)|i#le#36#and#i#ge#7:u(31,i)=0);

@for(jiedian(i)|i#le#36#and#i#ge#7:x(31,i)=0);

@for(jiedian(i)|i#le#36#and#i#ge#4#and#i#ne#9#and#i#ne#10#and#i#ne#11#and#i#ne#22:u(32,i)=0);   @for(jiedian(i)|i#le#36#and#i#ge#4#and#i#ne#9#and#i#ne#10#and#i#ne#11#and#i#ne#22:x(32,i)=0);

@for(jiedian(i)|i#le#36#and#i#ge#13#and#i#ne#22#and#i#ne#32:u(33,i)=0);@for(jiedian(i)|i#le#7#and#i#ge#5:u(33,i)=0);     @for(jiedian(i)|i#le#36#and#i#ge#13#and#i#ne#22#and#i#ne#32:x(33,i)=0);@for(jiedian(i)|i#le#7#and#i#ge#5:x(33,i)=0);

@for(jiedian(i)|i#le#36#and#i#ge#9#and#i#ne#16#and#i#ne#17#and#i#ne#20#and#i#ne#31#and#i#ne#35:u(34,i)=0);

@for(jiedian(i)|i#le#36#and#i#ge#9#and#i#ne#16#and#i#ne#17#and#i#ne#20#and#i#ne#31#and#i#ne#35:x(34,i)=0);

@for(jiedian(i)|i#le#36#and#i#ge#9#and#i#ne#20#and#i#ne#31:u(35,i)=0);

@for(jiedian(i)|i#le#36#and#i#ge#9#and#i#ne#20#and#i#ne#31:x(35,i)=0);

@for(jiedian(i)|i#le#36#and#i#ge#16#and#i#ne#19#and#i#ne#22#and#i#ne#23#and#i#ne#31#and#i#ne#32#and#i#ne#33:u(36,i)=0);

for(jiedian(i)|i#le#36#and#i#ge#16#and#i#ne#19#and#i#ne#22#and#i#ne#23#and#i#ne#31#and#i#ne#32#and#i#ne#33:x(36,i)=0);

附件2：鏟車排程方案的程式

model:

data:

N=3;

enddata

sets:

number/1..N/:tt;

jiedian/1..11/:t;

luojing(jiedian,jiedian):d;

variable(jiedian,jiedian,number):u;

link(jiedian,number);

endsets

data:

t=?;

d=?;

enddata

!目标函數;

min=@sum(variable(i,j,k):d(i,j)*u(i,j,k));

!除11号節點外每個圈隻有一個入點;

@for(jiedian(j)|j#ne#11:@sum(link(i,k):u(i,j,k))=1);

!除11号節點外每個圈隻有一個出點;

@for(jiedian(i)|i#ne#11:@sum(link(j,k):u(i,j,k))=1);

!每個圈都以11号節點為起點;

@for(number(k):@sum(jiedian(j):u(11,j,k))=1);

!每個圈都以11号節點為終點;

@for(number(k):@sum(jiedian(i):u(i,11,k))=1);

!每個圈中任一點都不從自身到自身;

@for(link(i,k):u(i,i,k)=0);

!每個圈所用時間不超過9小時;

@for(number(k):@sum(luojing(i,j):d(i,j)*u(i,j,k)/40)+@sum(luojing(i,j):t(j)*u(i,j,k))<9);

!變量u為(0-1)變量;

@for(variable:@bin(u));

!閉和路徑限制;

@for(number(k):@for(jiedian(t):@sum(jiedian(j):u(t,j,k))=@sum(jiedian(i):u(i,t,k))));

!輸出每個圈所需時間時間;

@for(number(k):tt=@sum(luojing(i,j):d(i,j)*u(i,j,k)/40)+@sum(luojing(i,j):t(j)*u(i,j,k)));

@for(variable(t,i,k)|t#ne#11#and#i#ne#11:u(i,t,k)+u(t,i,k)<=1);