2022年電工杯數(shù)學(xué)建模

B題 5G網(wǎng)絡(luò)環(huán)境下應(yīng)急物資配送問(wèn)題

原題再現(xiàn)：

??一些重特大突發(fā)事件往往會(huì)造成道路阻斷、損壞、封閉等意想不到的情況，對(duì)人們的日常生活會(huì)造成一定的影響。為了保證人們的正常生活，將應(yīng)急物資及時(shí)準(zhǔn)確地配送到位尤為重要。伴隨著科技水平的提升及 5G 網(wǎng)絡(luò)的逐漸普及，無(wú)人機(jī)的應(yīng)用越來(lái)越廣泛，“配送車輛+無(wú)人機(jī)”的配送模式已經(jīng)漸漸成為一種新的有效的配送方式。
??“配送車輛+無(wú)人機(jī)”的配送模式是指：在物資配送過(guò)程中，配送車輛對(duì)某地點(diǎn)進(jìn)行配送的同時(shí)，無(wú)人機(jī)也可向周圍可行的地點(diǎn)進(jìn)行配送，并于配送完成后返回配送車輛重新裝載物資、更換電池。這種配送模式可以大大提高應(yīng)急物資的配送效率，也可以解決復(fù)雜路況下的物資配送，避免次生災(zāi)害對(duì)人員的二次傷害。
??在應(yīng)急物資配送過(guò)程中，配送車輛可在某地點(diǎn)釋放無(wú)人機(jī)，再前往其它地點(diǎn)配送。配送車輛可先于無(wú)人機(jī)到達(dá)某地點(diǎn)等待接收無(wú)人機(jī)，也可比無(wú)人機(jī)晚到某地點(diǎn)再回收無(wú)人機(jī)。無(wú)人機(jī)在一次飛行過(guò)程中可對(duì)一個(gè)地點(diǎn)進(jìn)行配送，也可根據(jù)實(shí)際情況對(duì)多個(gè)地點(diǎn)進(jìn)行配送。無(wú)人機(jī)完成一次飛行后可返回配送車輛換裝電池，然后再次進(jìn)行配送。配送車輛和無(wú)人機(jī)合作完成所有地點(diǎn)應(yīng)急物資配送任務(wù)，返回到出發(fā)地點(diǎn)，此時(shí)稱為完成一次整體配送。
??完成一次整體配送所需要的時(shí)間是配送人員主要考慮的因素，按照配送車輛和無(wú)人機(jī)從出發(fā)開(kāi)始至全部返回到出發(fā)地點(diǎn)的時(shí)間來(lái)計(jì)算。在配送過(guò)程中，不考慮配送車輛及無(wú)人機(jī)裝卸物資的時(shí)間，同時(shí)不考慮配送車輛和無(wú)人機(jī)在各個(gè)配送點(diǎn)的停留時(shí)間。
??為了盡快完成物資配送任務(wù)，請(qǐng)根據(jù)附件所給數(shù)據(jù)解決以下幾個(gè)問(wèn)題：
??1.圖 1 給出 14 個(gè)地點(diǎn)，其中實(shí)線代表各地點(diǎn)之間的路線情況。若目前所有應(yīng)急物資集中在第 9 個(gè)地點(diǎn)，配送車輛的最大載重量為 1000 千克，采取配送車輛（無(wú)人機(jī)不參與）的配送模式。請(qǐng)結(jié)合附件 1，建立完成一次整體配送的數(shù)學(xué)模型，并給出最優(yōu)方案。
??2.圖 2 中實(shí)線代表車輛和無(wú)人機(jī)都可以走的路線，虛線代表只有無(wú)人機(jī)可以走的路線。應(yīng)急物資仍然集中在第 9 個(gè)地點(diǎn)，配送車輛的最大載重量為 1000 千克，采取“配送車輛+無(wú)人機(jī)”的配送模式。請(qǐng)結(jié)合附件 2，建立完成一次整體配送的數(shù)學(xué)模型，并給出最優(yōu)方案。
??3.若問(wèn)題 2 中的配送車輛的最大載重量為 500 千克，其他條件不變。請(qǐng)結(jié)合附件 2，建立完成一次整體配送的數(shù)學(xué)模型，并給出最優(yōu)方案。
??4.圖 3 中有 30 個(gè)地點(diǎn)，計(jì)劃設(shè)置兩個(gè)應(yīng)急物資集中地點(diǎn)，若配送車輛的最大載重量為 500 千克，采取“配送車輛+無(wú)人機(jī)”的配送模式。請(qǐng)結(jié)合附件 3，建立完成一次整體配送的數(shù)學(xué)模型，確定兩個(gè)應(yīng)急物資集中地點(diǎn)的最佳位置。
??注：
??1.假設(shè)應(yīng)急物資配送前 5G 網(wǎng)絡(luò)能夠覆蓋整個(gè)配送區(qū)域。
??2.忽略無(wú)人機(jī)自身重量的影響，無(wú)人機(jī)的最大載重量為 50 千克；配送車輛行駛平均速度為 50 公里/小時(shí)，無(wú)人機(jī)飛行平均速度為 75 公里/小時(shí)；無(wú)人機(jī)單次最長(zhǎng)飛行時(shí)間為 70 分鐘。
??3.每個(gè)應(yīng)急物資集中地點(diǎn)限一輛配送車輛，只能攜帶一架無(wú)人機(jī)。
??4.在論文附錄中提供所有數(shù)學(xué)模型的可運(yùn)行程序。

整體求解過(guò)程概述(摘要)

??隨著無(wú)人機(jī)的應(yīng)用越來(lái)越廣泛，配送車輛 + 無(wú)人機(jī)的配送模式已經(jīng)漸漸成為一種新型有效的配送方式。本文主要研究在這種配送方式下的應(yīng)急配送問(wèn)題，建立了基于混合蟻群算法的 VRPD問(wèn)題模型，利用蟻群算法，迭代局部搜索算法，聚類分析等方法進(jìn)行求解。
??對(duì)于問(wèn)題一只有配送車輛配送這一模式，建立 VRP 問(wèn)題，首先通過(guò) floyd 算法驗(yàn)證各地點(diǎn)間的最短距離即為直線距離，將問(wèn)題轉(zhuǎn)換為最佳 H 圈問(wèn)題；之后采用蟻群算法對(duì)這問(wèn)題進(jìn)行迭代求解，得到配送車輛一次整體配送的最短路徑和為 582（公里），一次整體配送的最短時(shí)間為 11.64（小時(shí)），并且發(fā)現(xiàn)收斂時(shí)迭代次數(shù)基本小于 10 次。
??對(duì)于問(wèn)題二，在問(wèn)題一的基礎(chǔ)上新增無(wú)人機(jī)配送的模式，首先對(duì) 14 個(gè)地點(diǎn)進(jìn)行聚類，發(fā)現(xiàn)它們屬于同一個(gè)類；其次在類中進(jìn)行分區(qū)，考慮到無(wú)人機(jī)的飛行約束，利用橢圓的幾何性質(zhì)最終分為 5 個(gè)飛行區(qū)；之后采用迭代局部搜索的方式對(duì)各飛行區(qū)中的點(diǎn)進(jìn)行重分配，找到最優(yōu)的配送路線；最后，采用蟻群算法對(duì)路線進(jìn)行迭代求解，得到一次整體配送的最短時(shí)間為 6.32（小時(shí)），相較問(wèn)題一時(shí)間縮短了近 50%。
??對(duì)于問(wèn)題三，在問(wèn)題二的基礎(chǔ)上增加了配送車的容量限制，這使得配送車不得不中途回到物資集中點(diǎn)裝載貨物后再次送貨，這會(huì)使得車輛在路徑圖中需要經(jīng)歷兩個(gè)回路。我們?cè)趩?wèn)題二求出的最優(yōu)路徑上將無(wú)人機(jī)配送的物資需求點(diǎn)記錄到配送車釋放無(wú)人機(jī)的節(jié)點(diǎn)上，這將我們的問(wèn)題從帶容量約束的無(wú)人機(jī) + 配送車問(wèn)題轉(zhuǎn)化為帶容量的車輛路徑問(wèn)題。利用蟻群算法求解該問(wèn)題，得到最短配送時(shí)間為 6.8 小時(shí)，這個(gè)時(shí)間只比單一回路的問(wèn)題二增加了 7.6%。
??對(duì)于問(wèn)題四，要求我們?cè)?30 個(gè)應(yīng)急物資需求點(diǎn)中選取兩個(gè)作為物資集中地點(diǎn)，對(duì)于這類選址問(wèn)題，我們采用多種聚類方案將這 30 個(gè)點(diǎn)聚為兩類，以每個(gè)類的中心點(diǎn)作為物資集中點(diǎn)，利用問(wèn)題二三設(shè)計(jì)的算法計(jì)算各種聚類方式下的物資配送時(shí)間，最終我們以質(zhì)心為條件進(jìn)行 k-meams 聚類，得到使得物資中心配送時(shí)間最短的兩個(gè)地點(diǎn)為第 8 與第 23 個(gè)地點(diǎn)，即為應(yīng)急物資集中點(diǎn)的最佳地點(diǎn)。
??最后對(duì)本文所建立的模型進(jìn)行了討論和分析，總結(jié)其優(yōu)缺點(diǎn)，綜合評(píng)價(jià)模型。

模型假設(shè)：

??1. 從配送中心出發(fā)的車輛必須返回配送中心；
??2. 所有距離都用歐式距離來(lái)表示；
??3. 卡車和無(wú)人機(jī)均以題目給出的數(shù)據(jù)勻速行駛，且其行駛速度不隨其載重改變；
??4. 5G 網(wǎng)絡(luò)已經(jīng)覆蓋我們需要配送的整個(gè)區(qū)域；
??5. 不考慮配送車輛和無(wú)人機(jī)裝載和卸貨的時(shí)間；
??6. 不考慮無(wú)人機(jī)在配送車上更換電池的時(shí)間；
??7. 每個(gè)配送點(diǎn)有且只有一輛車或一個(gè)無(wú)人機(jī)進(jìn)行配送服務(wù)；
??8. 假設(shè)題目給出的所有路徑都是雙向路徑。

問(wèn)題分析：

??問(wèn)題一的分析
??問(wèn)題一結(jié)合附件 1 給出了各地點(diǎn)之間的距離和所需物資量，通過(guò)附件 1 我們可以很明顯算出總物資需求量為 762 千克，遠(yuǎn)遠(yuǎn)小于配送車輛的最大載重量 1000 千克，所以我們只需要考慮求解配送車輛在圖 1 中經(jīng)歷一次回路的最短路徑，即最佳推銷員回路問(wèn)題，也即 NP-完全問(wèn)題?？紤]到最佳推銷員回路問(wèn)題的求解方法，考慮將其轉(zhuǎn)換為最佳 H 圈問(wèn)題，利用兩者在加權(quán)圖中的權(quán)值是相同的這一定理來(lái)求解。通過(guò) Floyd 算法證明各地點(diǎn)之間的直線距離即為它們的最短距離，則說(shuō)明該問(wèn)題可以轉(zhuǎn)換為最佳 H 圈問(wèn)題，其次根據(jù)得到的各地點(diǎn)距離形成的完備加權(quán)圖，最終將在加權(quán)圖中尋求最佳推銷員回路問(wèn)題轉(zhuǎn)化為在一個(gè)完備加權(quán)圖中尋求最佳 H 圈問(wèn)題，也稱為 TSP 問(wèn)題。本題中車輛路徑的規(guī)劃問(wèn)題（VSP 問(wèn)題），作為 TSP 問(wèn)題的一個(gè)推廣可以通過(guò)蟻群算法進(jìn)行對(duì)該 VRP 問(wèn)題的求解，得到從物資集中的第九個(gè)地點(diǎn)開(kāi)始配送直到最后回到該地點(diǎn)的路線圖以及一次整體配送的最短路徑長(zhǎng)度。
??問(wèn)題二的分析
??問(wèn)題二在問(wèn)題一的基礎(chǔ)上，增加了無(wú)人機(jī)配送物資的形式，所以我們的模型求解是在問(wèn)題一的基礎(chǔ)上進(jìn)行優(yōu)化改進(jìn)的。首先我們對(duì)圖二中的 14 個(gè)地點(diǎn)進(jìn)行聚類，找到超過(guò)無(wú)人機(jī)載重需求或者不在無(wú)人機(jī)配送范圍內(nèi)的地點(diǎn)，這些地點(diǎn)只能由配送車輛進(jìn)行配送，所以作為停靠點(diǎn)，針對(duì)該題我們采用并查集進(jìn)行分類；分類后對(duì)其中的地點(diǎn)進(jìn)行分區(qū)，通過(guò)對(duì)無(wú)人機(jī)的可達(dá)地點(diǎn)進(jìn)行分析，找到在以兩個(gè)?？奎c(diǎn)為焦點(diǎn)形成的橢圓范圍內(nèi)無(wú)人機(jī)可以配送的范圍，作為一個(gè)可飛行區(qū)，以此為基礎(chǔ)對(duì)分好的類進(jìn)行分割，找到所有的可飛行區(qū)；之后對(duì)各可飛行區(qū)中的地點(diǎn)節(jié)點(diǎn)進(jìn)行重分配，找到最合適的無(wú)人機(jī)和配送車輛要配送的地點(diǎn)。我們通過(guò)采用迭代局部搜索的啟發(fā)式搜索算法找到最優(yōu)解；最后將以上得到的所有路徑進(jìn)行連接，連接的過(guò)程與 TSP 問(wèn)題較為相似，因此我們?nèi)圆捎脝?wèn)題一中的蟻群算法進(jìn)行求解得出完整的連接路徑，實(shí)現(xiàn)一次整體配送，此時(shí)得到的即為時(shí)間最短路徑。
??問(wèn)題三的分析
??問(wèn)題三在問(wèn)題二的基礎(chǔ)上增加了對(duì)配送車的容量限制，這使得配送車必須在送貨途中回到 9號(hào)節(jié)點(diǎn)進(jìn)行補(bǔ)貨才能把物資運(yùn)送完，及由原來(lái)的尋找一條最短回路的問(wèn)題轉(zhuǎn)變?yōu)樾枰獌蓷l回路訪問(wèn)圖中所有的節(jié)點(diǎn)?？紤]在問(wèn)題二求得的最短路徑上進(jìn)行優(yōu)化，由于將各個(gè)飛行區(qū)的配送需求壓縮到無(wú)人機(jī)起飛的停靠點(diǎn)上，這樣就將問(wèn)題簡(jiǎn)化為帶容量約束的 VRP 問(wèn)題，再使用蟻群算法尋找?guī)萘考s束的 VRP 問(wèn)題的最優(yōu)路徑。
??問(wèn)題四的分析
??我們首先對(duì)第四問(wèn)的圖以歐式距離為度量，進(jìn)行 K-means 聚類，在 30 個(gè)應(yīng)急物資需求點(diǎn)中選取兩個(gè)作為物資集中地點(diǎn)，對(duì)于這類選址問(wèn)題，我們采用多種聚類方案將這 30 個(gè)點(diǎn)聚為兩類，以每個(gè)類的中心點(diǎn)作為物資集中點(diǎn)，利用問(wèn)題二三設(shè)計(jì)的算法計(jì)算各種聚類方式下的物資配送時(shí)間，最終我們以質(zhì)心為條件進(jìn)行 k-meams 聚類方法，得到使得物資中心配送時(shí)間最短的兩個(gè)地點(diǎn)，即為應(yīng)急物資集中點(diǎn)的最佳地點(diǎn)。

模型的建立與求解整體論文縮略圖

全部論文請(qǐng)見(jiàn)下方“ 只會(huì)建模 QQ名片” 點(diǎn)擊QQ名片即可

程序代碼：

部分程序如下:

1 # 以下為floyd算法的實(shí)現(xiàn)代碼
2 from math import *
3 import numpy as np
4 #創(chuàng)建節(jié)點(diǎn)字典
5 set_nodes={"v1":0,"v2":1,"v3":2,"v4":3,"v5":4,"v6":5,"v7":6,"v8":7,"v9":8,"v10":9,"v11":10,"v12"
:11,"v13":12,"v14":13}
6 INF = 999
7 #創(chuàng)建初始化距離矩陣
8 dis = np.array([[0, INF, INF, INF, 54, INF, 55, INF, INF, INF, 26, INF, INF, INF],
9 [INF, 0, 56, INF, 18, INF, INF, INF, INF, INF, INF, INF, INF, INF],
10 [INF, 56, 0, INF, 44, INF, INF, INF, INF, INF, INF, INF, INF, INF],
11 [INF, INF, INF, 0, INF, 28, INF, INF, INF, INF, INF, INF, INF, INF],
12 [54, 18, 44, INF, 0, 51, 34, 56, 48, INF, INF, INF, INF, INF],
13 [INF, INF, INF, 28, 51, 0, INF, INF, 27, 42, INF, INF, INF, INF],
14 [55, INF, INF, INF, 34, INF, 0, 36, INF, INF, INF, 38, INF, INF],
15 [INF, INF, INF, INF, 56, INF, 36, 0, 29, INF, INF, 33, INF, INF],
16 [INF, INF, INF, INF, 48, 27, INF, 29, 0, 61, INF, 29, 42, 36],
17 [INF, INF, INF, INF, INF, 42, INF, INF, 61, 0, INF, INF, INF, 25],
18 [26, INF, INF, INF, INF, INF, INF, INF, INF, INF, 0, 24, INF, INF],
19 [INF, INF, INF, INF, INF, INF, 38, 33, 29, INF, 24, 0, INF, INF],
20 [INF, INF, INF, INF, INF, INF, INF, INF, 42, INF, INF, INF, 0, 47],
21 [INF, INF, INF, INF, INF, INF, INF, INF, 36, 25, INF, INF, 47, 0]])
22 num = 14
23 #初始化一個(gè)矩陣 記錄父節(jié)點(diǎn) 先令父節(jié)點(diǎn)為終點(diǎn)本身
24 parent=[[i for i in range(14)] for j in range(14)]
25
26 #核心代碼
27 #i為中間節(jié)點(diǎn)
28 for i in range(num):
29 #j為起點(diǎn)
30 for j in range(num):
31 #k為終點(diǎn)
32 for k in range(num):
33 #更新最短距離
34 dis[j][k]= min(dis[j][k],dis[j][i]+dis[i][k])
35 parent[j][k]=parent[j][i]
36
37 #測(cè)試代碼
38 if __name__ == ’__main__’:
39 for i in range(num):
40 # j為起點(diǎn)
41 print("[")
42 for j in range(num):
43 print(","+ str(dis[i][j]),end=’’)
44 print("],")

1 # 以下為第一問(wèn)的蟻群算法的求解代碼
2 import random
3 import copy
4 import time
5 import sys
6 import math
7 import tkinter # //GUI模塊
8 import threading
9 from functools import reduce
10 import matplotlib.pyplot as plt
11
12 (ALPHA, BETA, RHO, Q) = (1.0, 2.0, 0.5, 100.0)
13 # 城市數(shù)，蟻群
14 (city_num, ant_num) = (14, 50)
15 distance_x = [78, 278, 600, 700, 330, 550, 230, 380, 450, 720, 150, 330, 532, 700]
16 distance_y = [170, 100, 78, 151, 200, 220, 280, 300, 305, 300, 500, 550, 525, 500]
17 # 城市距離和信息素
18 distance_graph = [[0, 72, 98, 133, 54, 105, 55, 83, 79, 140, 26, 50, 121, 115],
19 [72, 0, 56, 97, 18, 69, 52, 74, 66, 111, 98, 90, 108, 102],
20 [98, 56, 0, 123, 44, 95, 78, 100, 92, 137, 124, 116, 134, 128],
21 [133, 97, 123, 0, 79, 28, 113, 84, 55, 70, 108, 84, 97, 91],
22 [54, 18, 44, 79, 0, 51, 34, 56, 48, 93, 80, 72, 90, 84],
23 [105, 69, 95, 28, 51, 0, 85, 56, 27, 42, 80, 56, 69, 63],
24 [55, 52, 78, 113, 34, 85, 0, 36, 65, 126, 62, 38, 107, 101],
25 [83, 74, 100, 84, 56, 56, 36, 0, 29, 90, 57, 33, 71, 65],
26 [79, 66, 92, 55, 48, 27, 65, 29, 0, 61, 53, 29, 42, 36],
27 [140, 111, 137, 70, 93, 42, 126, 90, 61, 0, 114, 90, 72, 25],
28 [26, 98, 124, 108, 80, 80, 62, 57, 53, 114, 0, 24, 95, 89],
29 [50, 90, 116, 84, 72, 56, 38, 33, 29, 90, 24, 0, 71, 65],
30 [121, 108, 134, 97, 90, 69, 107, 71, 42, 72, 95, 71, 0, 47],
31 [115, 102, 128, 91, 84, 63, 101, 65, 36, 25, 89, 65, 47, 0]]
32 pheromone_graph = [[1.0 for col in range(city_num)] for raw in range(city_num)]
33 x = []
34 y = []
35
36 # ----------- 螞蟻 -----------
37 class Ant( object):
38 # 初始化
39 def __init__(self, ID):
40 self.ID = ID # ID
41 self.__clean_data() # 隨機(jī)初始化出生點(diǎn)
42
43 # 初始數(shù)據(jù)
44 def __clean_data(self):
45 self.path = [] # 當(dāng)前螞蟻的路徑
46 self.total_distance = 0.0 # 當(dāng)前路徑的總距離
47 self.move_count = 0 # 移動(dòng)次數(shù)
48 self.current_city = -1 # 當(dāng)前停留的城市
49 self.open_table_city = [True for i in range(city_num)] # 探索城市的狀態(tài)
50 city_index = random.randint(0, city_num - 1) # 隨機(jī)初始出生點(diǎn)
51 self.current_city = city_index
52 self.path.append(city_index)
53 self.open_table_city[city_index] = False
54 self.move_count = 1
55
56 # 選擇下一個(gè)城市
57 def __choice_next_city(self):
58 next_city = -1
59 select_citys_prob = [0.0 for i in range(city_num)] # 存儲(chǔ)去下個(gè)城市的概率
60 total_prob = 0.0
61 # 獲取去下一個(gè)城市的概率
62 for i in range(city_num):
63 if self.open_table_city[i]:
64 try:
65 # 計(jì)算概率：與信息素濃度成正比，與距離成反比
66 select_citys_prob[i] = pow(pheromone_graph[self.current_city][i], ALPHA) *
pow(
67 (1.0 / distance_graph[self.current_city][i]), BETA)
68 total_prob += select_citys_prob[i]
69 except ZeroDivisionError as e:
70 print(’Ant ID: {ID}, current city: {current}, target city: {target}’.
format(ID=self.ID,current=self.current_city,target=i))
71 sys.exit(1)
72 # 輪盤選擇城市
73 if total_prob > 0.0:
74 # 產(chǎn)生一個(gè)隨機(jī)概率,0.0-total_prob
75 temp_prob = random.uniform(0.0, total_prob)
76 for i in range(city_num):
77 if self.open_table_city[i]:
78 # 輪次相減
79 temp_prob -= select_citys_prob[i]
80 if temp_prob < 0.0:
81 next_city = i
82 break
83 # 未從概率產(chǎn)生，順序選擇一個(gè)未訪問(wèn)城市
84 # if next_city == -1:
85 # for i in range(city_num):
86 # if self.open_table_city[i]:
87 # next_city = i
88 # break
89 if (next_city == -1):
90 next_city = random.randint(0, city_num - 1)
91 while ((self.open_table_city[next_city]) == False): # if==False,說(shuō)明已經(jīng)遍歷過(guò)了
92 next_city = random.randint(0, city_num - 1)
93 # 返回下一個(gè)城市序號(hào)
94 return next_city
95
96 # 計(jì)算路徑總距離
97 def __cal_total_distance(self):
98 temp_distance = 0.0
99 for i in range(1, city_num):
100 start, end = self.path[i], self.path[i - 1]
101 temp_distance += distance_graph[start][end]
102 # 回路
103 end = self.path[0]
104 temp_distance += distance_graph[start][end]
105 self.total_distance = temp_distance
106
107 # 移動(dòng)操作
108 def __move(self, next_city):
109 self.path.append(next_city)
110 self.open_table_city[next_city] = False
111 self.total_distance += distance_graph[self.current_city][next_city]
112 self.current_city = next_city
113 self.move_count += 1
114
115 # 搜索路徑
116 def search_path(self):
117 # 初始化數(shù)據(jù)
118 self.__clean_data()
119 # 搜素路徑，遍歷完所有城市為止
120 while self.move_count < city_num:
121 # 移動(dòng)到下一個(gè)城市
122 next_city = self.__choice_next_city()
123 self.__move(next_city)
124 # 計(jì)算路徑總長(zhǎng)度
125 self.__cal_total_distance()
126
127
128 # ----------- TSP問(wèn)題 -----------
129 class TSP( object):
130 def __init__(self, root, width=800, height=600, n=city_num):
131 # 創(chuàng)建畫布
132 self.root = root
133 self.width = width
134 self.height = height
135 # 城市數(shù)目初始化為city_num
136 self.n = n
137 # tkinter.Canvas
138 self.canvas = tkinter.Canvas(
139 root,
140 width=self.width,
141 height=self.height,
142 bg="#EBEBEB", # 背景白色
143 xscrollincrement=1,
144 yscrollincrement=1
145 )
146 self.canvas.pack(expand=tkinter.YES, fill=tkinter.BOTH)
147 self.title("蟻群算法(n:初始化 e:開(kāi)始搜索 s:停止搜索 q:退出程序)")
148 self.__r = 5
149 self.__lock = threading.RLock() # 線程鎖
150 self.__bindEvents()
151 self.new()
152 # 計(jì)算城市之間的距離
153
154 # 按鍵響應(yīng)程序
155 def __bindEvents(self):
156 self.root.bind("q", self.quite) # 退出程序
157 self.root.bind("n", self.new) # 初始化
158 self.root.bind("e", self.search_path) # 開(kāi)始搜索
159 self.root.bind("s", self.stop) # 停止搜索
160
161 # 更改標(biāo)題
162 def title(self, s):
163 self.root.title(s)
164
165 # 初始化
166 def new(self, evt=None):
167 # 停止線程
168 self.__lock.acquire()
169 self.__running = False
170 self.__lock.release()
171 self.clear() # 清除信息
172 self.nodes = [] # 節(jié)點(diǎn)坐標(biāo)
173 self.nodes2 = [] # 節(jié)點(diǎn)對(duì)象
174 # 初始化城市節(jié)點(diǎn)
175 for i in range(city_num):
176 # 在畫布上隨機(jī)初始坐標(biāo)
177 x = distance_x[i]
178 y = distance_y[i]
179 self.nodes.append((x, y))
180 # 生成節(jié)點(diǎn)橢圓，半徑為self.__r
181 node = self.canvas.create_oval(x - 15,
182 y - 15, x + 15, y + 15,
183 fill="#FFFFE0", # 填充黃色
184 outline="#ff0000", # 輪廓紅色
185 tags="node",
186 )
187 self.nodes2.append(node)
188 # 顯示坐標(biāo)
189 self.canvas.create_text(x, y, # 使用create_text方法在坐標(biāo)（302，77）處繪制文字
190 text=i + 1, # 所繪制文字的內(nèi)容
191 fill=’black’ # 所繪制文字的顏色為灰色
192 )
193 # 順序連接城市
194 # self.line(range(city_num))
195 # 初始城市之間的距離和信息素
196 for i in range(city_num):
197 for j in range(city_num):
198 pheromone_graph[i][j] = 1.0
199 self.ants = [Ant(ID) for ID in range(ant_num)] # 初始蟻群
200 self.best_ant = Ant(-1) # 初始最優(yōu)解
201 self.best_ant.total_distance = 1 << 31 # 初始最大距離
202 self. iter = 1 # 初始化迭代次數(shù)
203
204 # 將節(jié)點(diǎn)按order順序連線
205 def line(self, order):
206 # 刪除原線
207 self.canvas.delete("line")
208
209 def line2(i1, i2):
210 p1, p2 = self.nodes[i1], self.nodes[i2]
211 self.canvas.create_line(p1, p2, fill="#000000", tags="line")
212 return i2
213
214 # order[-1]為初始值
215 reduce(line2, order, order[-1])
216
217 # 清除畫布
218 def clear(self):
219 for item in self.canvas.find_all():
220 self.canvas.delete(item)
221
222 # 退出程序
223 def quite(self, evt):
224 self.__lock.acquire()
225 self.__running = False
226 self.__lock.release()
227 self.root.destroy()
228 print(u"\n程序已退出...")
229 sys.exit()
230
231 # 停止搜索
232 def stop(self, evt):
233 self.__lock.acquire()
234 self.__running = False
235 self.__lock.release()
236 plt.rcParams[’font.sans-serif’] = [’SimHei’] # 指定默認(rèn)字體
237 plt.rcParams[’axes.unicode_minus’] = False # 解決保存圖像是負(fù)號(hào)’-’顯示為方塊的問(wèn)題
238 plt.plot(x,y) # 當(dāng)輸入s停止搜索后，顯示變化圖像
239 plt.xlabel("迭代次數(shù)")
240 plt.ylabel("一次整體配送所花時(shí)間")
241 plt.show()
242
243 # 開(kāi)始搜索
244 def search_path(self, evt=None):
245 # 開(kāi)啟線程
246 self.__lock.acquire()
247 self.__running = True
248 self.__lock.release()
249 while self.__running:
250 # 遍歷每一只螞蟻
251 for ant in self.ants:
252 # 搜索一條路徑
253 ant.search_path()
254 # 與當(dāng)前最優(yōu)螞蟻比較
255 if ant.total_distance < self.best_ant.total_distance:
256 # 更新最優(yōu)解
257 self.best_ant = copy.deepcopy(ant)
258 # 更新信息素
259 self.__update_pheromone_gragh()
260 print(u"迭代次數(shù)：", self. iter, u"最佳路徑總距離：",
int(self.best_ant.total_distance))
261 time = self.best_ant.total_distance/50
262 print("一次整體配送所花時(shí)間為：{:.4f}". format(time))
263 x.append(self. iter)
264 y.append(time)
265 # 連線
266 self.line(self.best_ant.path)
267 # 設(shè)置標(biāo)題
268 self.title("TSP蟻群算法(n:隨機(jī)初始 e:開(kāi)始搜索 s:停止搜索 q:退出程序) 迭代次數(shù): %d" %
self.
iter)
269 # 更新畫布
270 self.canvas.update()
271 self. iter += 1
272
273 # 更新信息素
274 def __update_pheromone_gragh(self):
275 # 獲取每只螞蟻在其路徑上留下的信息素
276 temp_pheromone = [[0.0 for col in range(city_num)] for raw in range(city_num)]
277 for ant in self.ants:
278 for i in range(1, city_num):
279 start, end = ant.path[i - 1], ant.path[i]
280 # 在路徑上的每?jī)蓚€(gè)相鄰城市間留下信息素，與路徑總距離反比
281 temp_pheromone[start][end] += Q / ant.total_distance
282 temp_pheromone[end][start] = temp_pheromone[start][end]
283 # 更新所有城市之間的信息素，舊信息素衰減加上新迭代信息素
284 for i in range(city_num):
285 for j in range(city_num):
286 pheromone_graph[i][j] = pheromone_graph[i][j] * RHO + temp_pheromone[i][j]
287
288 # 主循環(huán)
289 def mainloop(self):
290 self.root.mainloop()
291
292
293 # ----------- 程序的入口處 -----------
294 if __name__ == ’__main__’:
295 TSP(tkinter.Tk()).mainloop()

全部論文請(qǐng)見(jiàn)下方“ 只會(huì)建模 QQ名片” 點(diǎn)擊QQ名片即可