基于多車(chē)輛路徑問(wèn)題模型的信通機(jī)房巡檢路線(xiàn)優(yōu)化

摘 要：對(duì)信通機(jī)房巡檢路線(xiàn)進(jìn)行優(yōu)化，利用巡檢路線(xiàn)優(yōu)化問(wèn)題具有帶容量約束的多車(chē)輛路徑問(wèn)題特點(diǎn)，以巡檢總天數(shù)最少、總巡檢工作時(shí)間最短為目標(biāo)，建立信通機(jī)房巡檢路線(xiàn)規(guī)劃問(wèn)題優(yōu)化模型，并利用改進(jìn)粒子群算法對(duì)優(yōu)化模型進(jìn)行求解。通過(guò)海寧地區(qū)一個(gè)巡檢路線(xiàn)優(yōu)化實(shí)例進(jìn)行驗(yàn)證，結(jié)果表明，所提改進(jìn)粒子群算法能有效求解優(yōu)化問(wèn)題，應(yīng)用該優(yōu)化模型可以縮短巡檢天數(shù)，提高巡檢工作時(shí)間利用效率。

關(guān)鍵詞：車(chē)輛路徑問(wèn)題；粒子群算法；數(shù)學(xué)模型；路線(xiàn)規(guī)劃

中圖分類(lèi)號(hào)：TP301.6" " 文獻(xiàn)標(biāo)志碼：A" " 文章編號(hào)：1671-0797（2023）18-0012-04

DOI：10.19514/j.cnki.cn32-1628/tm.2023.18.003

0" " 引言

車(chē)輛路徑問(wèn)題（VRP）是1959年由G. Dantzig等人提出來(lái)的[1]，這個(gè)問(wèn)題一般可以描述為：根據(jù)一系列發(fā)貨點(diǎn)和/或收貨點(diǎn)，合理組織行車(chē)路線(xiàn)，使車(chē)輛有序地通過(guò)所有點(diǎn)，并在滿(mǎn)足一定約束條件（車(chē)輛容量限制、行駛距離限制等）的情況下，最終達(dá)到預(yù)期目標(biāo)（總路程最短、使用車(chē)輛最少）[2]。由此可以看出，多旅行商問(wèn)題（MTSP）是多車(chē)輛路徑問(wèn)題的一個(gè)特例。在MTSP問(wèn)題中，多個(gè)旅行商從初始點(diǎn)出發(fā)，訪(fǎng)問(wèn)所有的目的點(diǎn)，每個(gè)目的點(diǎn)只到達(dá)一次，最后都返回初始點(diǎn)，需要為多個(gè)旅行商確定目的點(diǎn)訪(fǎng)問(wèn)順序，并使總旅行路徑長(zhǎng)度最短[3]。

自車(chē)輛路徑問(wèn)題提出以來(lái)，在眾多不同領(lǐng)域?qū)＜业呐ο?，目前已?jīng)出現(xiàn)了很多不同的解決算法，例如節(jié)約算法[4]、動(dòng)態(tài)規(guī)劃算法[5]、粒子群算法[6]、禁忌搜索算法[7]等。其中，粒子群算法是由社會(huì)性動(dòng)物行為及群理論發(fā)展出來(lái)的新型智能優(yōu)化算法，它首先在可行解域里隨機(jī)得到一組初始解，再根據(jù)適應(yīng)度函數(shù)計(jì)算每個(gè)粒子的適應(yīng)度值。每個(gè)粒子在空間自由運(yùn)動(dòng)時(shí)，都由一個(gè)速度向量決定其運(yùn)動(dòng)方向和速率，在每次運(yùn)動(dòng)過(guò)程中各粒子始終跟隨種群最優(yōu)粒子，并不斷更新自身及種群最優(yōu)粒子信息。

目前，供電公司信通運(yùn)維部門(mén)管轄范圍內(nèi)分布著大量的信通機(jī)房，例如在各供電所、營(yíng)業(yè)廳、倉(cāng)庫(kù)等地都至少有一個(gè)大型機(jī)房。信通運(yùn)維部門(mén)在日常工作中，常常需要對(duì)所有機(jī)房的設(shè)備進(jìn)行專(zhuān)項(xiàng)維護(hù)，于是需要對(duì)這些機(jī)房安排巡檢計(jì)劃，直到所有機(jī)房都巡檢一遍才結(jié)束工作。在制定巡檢計(jì)劃時(shí)，一般將機(jī)房按所在行政片區(qū)進(jìn)行劃分，常常用一至兩天的時(shí)間完成一塊區(qū)域所有機(jī)房的巡檢。在這種情況下，會(huì)出現(xiàn)在一些區(qū)域要連續(xù)加班、另一些區(qū)域要提早返回的情況，而且巡檢周期較長(zhǎng)。

1" " 信通機(jī)房巡檢路線(xiàn)問(wèn)題

1.1" " 信通機(jī)房巡檢路線(xiàn)問(wèn)題描述

在公司管轄范圍的各生產(chǎn)場(chǎng)所分布著大量的信通機(jī)房，信通運(yùn)維部門(mén)對(duì)所有機(jī)房進(jìn)行專(zhuān)項(xiàng)巡檢、設(shè)備消缺時(shí)，需要盡快完成所有工作。如果以機(jī)房所在行政片區(qū)作為巡檢計(jì)劃安排依據(jù)，有的片區(qū)機(jī)房多就容易出現(xiàn)加班的情況，有的片區(qū)機(jī)房少則容易出現(xiàn)提早返回的情況。

在信通機(jī)房巡檢時(shí)，工作人員早上從公司大樓出發(fā)，巡檢幾個(gè)機(jī)房后在下班前返回公司大樓，可支配的工作時(shí)間有限。巡檢工作結(jié)果是：到達(dá)所有的機(jī)房站點(diǎn)，并且不重復(fù)去任何一個(gè)機(jī)房。巡檢路線(xiàn)安排的目標(biāo)是：總巡檢天數(shù)最少，總巡檢計(jì)劃的工作時(shí)間最短。

在某一天進(jìn)行巡檢工作時(shí)，假設(shè)是從圖1中的初始點(diǎn)出發(fā)去地點(diǎn)一、地點(diǎn)二、地點(diǎn)三并返回初始點(diǎn)，由于各地點(diǎn)間的距離不同，行程時(shí)間不同，機(jī)房巡檢方式也就有很多種。于是可知，巡檢地點(diǎn)一、地點(diǎn)二、地點(diǎn)三的計(jì)劃有表1所示幾種情況。

以巡檢方式1為例，假設(shè)一天可支配的工作時(shí)間為T(mén)0，地點(diǎn)一、地點(diǎn)二、地點(diǎn)三對(duì)應(yīng)機(jī)房K1、K2、K3，從初始點(diǎn)到K1點(diǎn)需要用時(shí)為T(mén)11，從K1到K2需要用時(shí)為T(mén)12，從K2到K3需要用時(shí)為T(mén)23，從K3返回至初始點(diǎn)需要用時(shí)為T(mén)33，單個(gè)機(jī)房的巡檢工作耗時(shí)為W0，則一天的巡檢工作用時(shí)t為：

1.2" " 信通機(jī)房巡檢路線(xiàn)問(wèn)題優(yōu)化模型

在對(duì)所有機(jī)房進(jìn)行巡檢路線(xiàn)規(guī)劃時(shí)，設(shè)總計(jì)劃天數(shù)為n（i=1，2，…，n）；每天巡檢計(jì)劃用時(shí)為ti，一天可用的工作時(shí)間為T(mén)0；巡檢機(jī)房編號(hào)為k（k=1，2，…，K）；機(jī)房m、j之間的路程時(shí)間為T(mén)mj（m，j=1，2，…，K，m=j表示從該點(diǎn)往返初始點(diǎn)的情況），并假設(shè)Tmj=Tjm；每個(gè)機(jī)房巡檢工作耗時(shí)為W0。定義機(jī)房巡檢變量如下：

對(duì)于某個(gè)機(jī)房k在整個(gè)巡檢過(guò)程中應(yīng)滿(mǎn)足如下約束：

假設(shè)第i天巡檢機(jī)房個(gè)數(shù)為yi，則有：

令第i天巡檢機(jī)房編號(hào)集合為Yi，集合Yi里的第p個(gè)機(jī)房編號(hào)為Yip，定義變量如下：

對(duì)于所有機(jī)房在巡檢過(guò)程中應(yīng)滿(mǎn)足如下約束：

第i天巡檢工作用時(shí)如下：

優(yōu)化目標(biāo)是總巡檢天數(shù)最少，總巡檢計(jì)劃時(shí)間利用率最高，則目標(biāo)函數(shù)為：

2" " 優(yōu)化算法設(shè)計(jì)

粒子群算法是一種進(jìn)化優(yōu)化算法[8]，每個(gè)粒子代表解空間中的一個(gè)可行解，迭代過(guò)程中粒子始終跟蹤自身歷史最優(yōu)位置和種群歷史最優(yōu)位置，并根據(jù)種群信息不斷調(diào)整自身的運(yùn)動(dòng)方向和速度。

機(jī)房巡檢路線(xiàn)規(guī)劃其實(shí)就是對(duì)機(jī)房編號(hào)進(jìn)行分組并排序，優(yōu)化結(jié)果是幾組離散、有邊界、元素不重復(fù)的整數(shù)。在優(yōu)化計(jì)算時(shí)，需要對(duì)常規(guī)粒子群算法進(jìn)行適當(dāng)?shù)母倪M(jìn)，以便更有效地進(jìn)行優(yōu)化。由于機(jī)房間的路程時(shí)間不同，機(jī)房巡檢順序不同，當(dāng)天巡檢時(shí)間就不同。在優(yōu)化過(guò)程中可以記錄機(jī)房的安排順序，并對(duì)機(jī)房順序進(jìn)行統(tǒng)計(jì)，再將統(tǒng)計(jì)結(jié)果反饋到優(yōu)化進(jìn)程中，就可以有效提高優(yōu)化效率。

以圖1為例，知道機(jī)房巡檢范圍后，先計(jì)算巡檢工作用時(shí)最少的巡檢方式。假設(shè)表1中方式1巡檢用時(shí)最少，可以將巡檢計(jì)劃按如下方式進(jìn)行切片處理：切片成地點(diǎn)一至地點(diǎn)二、地點(diǎn)二至地點(diǎn)三。于是，可對(duì)粒子群算法進(jìn)行以下改進(jìn)：在種群優(yōu)化過(guò)程中，記錄每次新得到的種群最優(yōu)粒子信息，對(duì)種群最優(yōu)粒子進(jìn)行巡檢計(jì)劃切片處理。先讓種群迭代到指定代數(shù)，再統(tǒng)計(jì)這些切片數(shù)據(jù)，根據(jù)切片情況生成新的粒子群，最后繼續(xù)迭代一定代數(shù)獲得最優(yōu)解。

假設(shè)在一個(gè)n維的目標(biāo)搜索空間中，有m個(gè)粒子組成一個(gè)種群，第i個(gè)粒子在n維空間里的位置為Xi=（xi1，xi2，…，xin）T，速度為Vi=（vi1，vi2，…，vin）T，適應(yīng)度目標(biāo)函數(shù)為fi=f（Xi）。優(yōu)化步驟如下：

1）初始化粒子群。隨機(jī)生成m個(gè)粒子，得到對(duì)應(yīng)的位置、速度信息。

2）根據(jù)目標(biāo)函數(shù)計(jì)算每個(gè)粒子的適應(yīng)度，種群最優(yōu)適應(yīng)度值滿(mǎn)足設(shè)定目標(biāo)就轉(zhuǎn)至步驟8），否則轉(zhuǎn)至步驟3）。

3）更新粒子歷史最優(yōu)位置和種群歷史最優(yōu)位置。

4）如果得到新的種群最優(yōu)位置，則對(duì)巡檢計(jì)劃進(jìn)行切片處理并存儲(chǔ)。

5）對(duì)所有粒子根據(jù)種群歷史最優(yōu)位置和粒子歷史最優(yōu)位置調(diào)整運(yùn)動(dòng)速度，得到新的位置信息。

6）檢查終止條件。未達(dá)到指定迭代次數(shù)返回步驟2），達(dá)到最大迭代次數(shù)轉(zhuǎn)至步驟8），否則轉(zhuǎn)至步驟7）。

7）根據(jù)切片統(tǒng)計(jì)結(jié)果，生成一組新的粒子群，返回步驟2）。

8）優(yōu)化結(jié)束。

3" " 計(jì)算實(shí)例和結(jié)果

下面以海寧地區(qū)為例進(jìn)行分析。海寧市供電公司信通運(yùn)維部門(mén)負(fù)責(zé)管轄范圍內(nèi)23處信通機(jī)房的日常運(yùn)維工作，這些機(jī)房分布在各街道、鄉(xiāng)鎮(zhèn)，機(jī)房間行程時(shí)間簡(jiǎn)化如表2所示。

一般情況下，去除工作準(zhǔn)備時(shí)間，一天可用的巡檢工作時(shí)間為330 min，假設(shè)機(jī)房?jī)?nèi)的巡檢工作需要60 min，常用的一種巡檢工作安排如表3所示，在這種情況下，巡檢周期為9天。

用普通的粒子群算法進(jìn)行優(yōu)化時(shí)，設(shè)最大迭代數(shù)為100，粒子群規(guī)模為30，巡檢計(jì)劃的優(yōu)化結(jié)果如表4所示。

在這種情況下，巡檢周期只縮短了一天，優(yōu)化結(jié)果不是很理想。采用文中所述改進(jìn)粒子群算法后，設(shè)指定迭代次數(shù)為30，最大迭代次數(shù)為100，粒子群規(guī)模為30，巡檢計(jì)劃的優(yōu)化結(jié)果如表5所示。

巡檢計(jì)劃優(yōu)化過(guò)程中，種群最優(yōu)粒子的迭代過(guò)程如表6所示。

由表5、表6可知，利用文中所述優(yōu)化方法，每天的巡檢時(shí)間得到充分利用，巡檢周期也縮短了兩天，優(yōu)化結(jié)果符合預(yù)期。

4" " 結(jié)束語(yǔ)

機(jī)房巡檢路線(xiàn)規(guī)劃問(wèn)題具有多車(chē)輛路徑的特點(diǎn)，文中在進(jìn)行路線(xiàn)優(yōu)化時(shí)建立了類(lèi)似多車(chē)輛路徑問(wèn)題的數(shù)學(xué)模型。巡檢路線(xiàn)規(guī)劃是將機(jī)房編號(hào)進(jìn)行分組排序，優(yōu)化結(jié)果是一系列離散、有邊界、元素不重復(fù)的整數(shù)。對(duì)于這種非連續(xù)變量的優(yōu)化問(wèn)題，文中對(duì)基本粒子群算法進(jìn)行了適當(dāng)?shù)母倪M(jìn)，并通過(guò)海寧地區(qū)的機(jī)房巡檢路線(xiàn)規(guī)劃實(shí)例驗(yàn)證了改進(jìn)粒子群算法能有效解決優(yōu)化問(wèn)題。

[參考文獻(xiàn)]

[1] DANTZIG G B，RAMSER J H.The truck dispatching problem[J].Management Science，1959，6（1）：80-91.

[2] 劉云忠，宣慧玉.車(chē)輛路徑問(wèn)題的模型及算法研究綜述[J].管理工程學(xué)報(bào)，2005，19（1）：124-130.

[3] 馮洪奎，鮑勁松，金燁.混合粒子群優(yōu)化算法求解多車(chē)輛拖動(dòng)貨物問(wèn)題[J].計(jì)算機(jī)集成制造系統(tǒng)，2010，16（7）：1427-1436.

[4] 朱曉蘭，趙一飛.C-W節(jié)約算法在裝配企業(yè)采購(gòu)物流中的應(yīng)用[J].上海交通大學(xué)學(xué)報(bào)，2007，41（9）：1420-1424.

[5] 王亞楠，閆軍，丁鑫培，等.淺論動(dòng)態(tài)規(guī)劃在我國(guó)物流產(chǎn)業(yè)的應(yīng)用研究[J].物流科技，2016，39（6）：31-33.

[6] 盧岑岑，吳跨宇，王曉茹.基于PSO算法的直流有功功率調(diào)制參數(shù)優(yōu)化研究[J].浙江電力，2016，35（1）：1-5.

[7] 袁建清.求解動(dòng)態(tài)車(chē)輛調(diào)度問(wèn)題的混合禁忌搜索算法[J].計(jì)算機(jī)應(yīng)用與軟件，2012，29（4）：148-150.

[8] 溫惠英，孫博.基于離散粒子群算法的協(xié)同車(chē)輛路徑問(wèn)題[J].公路交通科技，2011，28（1）：149-153.

收稿日期：2023-05-30

作者簡(jiǎn)介：王曉明（1989—），男，河南信陽(yáng)人，碩士，工程師，從事電力通信新技術(shù)研究、優(yōu)化算法分析工作。