二級(jí)垃圾回收中轉(zhuǎn)設(shè)施選址問題的降階回溯算法

摘 要：隨著我國(guó)城市化進(jìn)程的加快和經(jīng)濟(jì)的高速發(fā)展，城市中因生產(chǎn)生活所產(chǎn)生的垃圾廢料量日益增加，如何有效地建立回收中轉(zhuǎn)設(shè)施是當(dāng)前社會(huì)需要解決的問題。對(duì)二級(jí)垃圾回收設(shè)施選址問題進(jìn)行研究，其實(shí)質(zhì)為組合優(yōu)化中的NP－h(huán)ard問題。首先根據(jù)實(shí)際情況對(duì)二級(jí)垃圾回收中轉(zhuǎn)設(shè)施選址問題進(jìn)行數(shù)學(xué)建模，研究該問題的數(shù)學(xué)性質(zhì)并給予證明，利用這些性質(zhì)減小問題規(guī)模，降低求解難度；然后設(shè)計(jì)符合該問題的分配子算法、上下界子算法，基于以上算法提出一種可以在減小問題規(guī)模的同時(shí)得到精確解的降階回溯算法；最后通過分析和模擬若干個(gè)示例進(jìn)一步闡述該算法的原理及執(zhí)行過程，結(jié)果表明該算法能通過減小問題規(guī)模，降低問題求解的難度。

關(guān)鍵詞：垃圾中轉(zhuǎn)設(shè)施選址問題； 精確算法； 降階算法； 上下界子算法； 回溯算法

中圖分類號(hào)：TP301.6文獻(xiàn)標(biāo)志碼： A文章編號(hào)：1001－3695（2024）04－021－1104－08

doi：10.19734/j.issn.1001－3695.2023.08.0363

Backtracking algorithm with reduction for location problem of second levelwaste recycling and transfer facilities

Liu Shu’ao， Ning Aibing， Lin Daohan， Liu Ruishi， Zhang Huizhen

Abstract：Because of China’s rapid urbanization and economic growth， the amount of waste generated from production and city life is increasing daily. Establishing effective recycling and transfer facilities is a critical problem in today’s society. This paper studied the problem of finding locations for secondary waste recycling facilities， the essence of which was the NP－h(huán)ard problem in combinatorial optimization. Firstly， to solve the problem， the paper made a mathematical model based on the actual situation and then studied the problem’s mathematical properties to provide a proof and simplify the problem， reducing its scale and difficulty. Then， this paper designed the allocation sub－algorithm and the upper and lower bound sub－algorithms for the problem. Based on the above algorithms，it proposed a reduced－order backtracking algorithm to obtain an accurate solution while still reducing the problem size. Finally， the algorithm’s principles and execution process were further elaborated through analyzing and simulating several examples. The results show that the algorithm successfully reduces the problem’s difficulty by reducing the problem size.

Key words：site selection of waste transfer facilities; exact algorithm; reduction algorithm; upper and lower bound algorithms; backtracking algorithm

0 引言

隨著城市化進(jìn)程的加快和人口的快速增長(zhǎng)，近些年來生活垃圾的產(chǎn)生量呈現(xiàn)快速增長(zhǎng)的趨勢(shì)，據(jù)國(guó)家統(tǒng)計(jì)局公布的數(shù)據(jù)顯示，2022年全國(guó)城市生活垃圾清運(yùn)量約為1.9億噸，處理量約為1.88億噸，這給我國(guó)垃圾分類工作帶來了巨大的挑戰(zhàn)。垃圾回收設(shè)施作為分類處理的關(guān)鍵一環(huán)，可以接收來自不同區(qū)域產(chǎn)生的生活垃圾。先對(duì)已收集的垃圾進(jìn)行初步的分類，將不同類型的垃圾分開，為后續(xù)的處理和回收提供便利，再對(duì)垃圾進(jìn)行壓縮處理，便于轉(zhuǎn)運(yùn)至下一級(jí)別的處理站進(jìn)行后續(xù)處理［1］。方法與流程如圖1所示。作為垃圾處理的重要一環(huán)，垃圾回收中轉(zhuǎn)設(shè)施的建設(shè)和發(fā)展已成為政府和社會(huì)的重要議題，也是我國(guó)城市化建設(shè)之中的重要任務(wù)，準(zhǔn)確高效地確定設(shè)施選址的位置，可以有效提高垃圾的回收利用率，降低運(yùn)輸成本，并最大程度地減少對(duì)周邊居民和環(huán)境的不良影響。因此，解決垃圾回收中轉(zhuǎn)設(shè)施選址問題具有重要的理論意義和實(shí)際價(jià)值。

垃圾回收設(shè)施選址是不受歡迎選址問題（obnoxious facility site selection problem） ［2］中的一個(gè)重要研究方向。該問題是一種非特殊的設(shè)施選址問題，是一個(gè)NP難題，除非P=NP，否則不存在多項(xiàng)式時(shí)間的精確算法。目前有很多學(xué)者對(duì)垃圾回收設(shè)施選址問題進(jìn)行了研究：李海君等人［3］使用改進(jìn)的位置集合覆蓋問題（location set covering problem，LSCP）模型對(duì)多目標(biāo)情況下的選址方案進(jìn)行求解，并使用Lingo優(yōu)化軟件進(jìn)行兩階段優(yōu)化求解；李夢(mèng)琦等人［4］研究了使用兩階段法定性定量地考慮選址因素，其中第一階段對(duì)各個(gè)關(guān)系間的權(quán)重進(jìn)行考量，進(jìn)行初步選址，第二階段基于0－1規(guī)劃構(gòu)建運(yùn)輸成本最小化模型對(duì)問題進(jìn)行求解；楊帆等人［5］研究了以長(zhǎng)沙市垃圾中轉(zhuǎn)設(shè)施為案例的選址方案，通過建立二重標(biāo)準(zhǔn)分析的選址評(píng)價(jià)體系，最終利用GIS技術(shù)對(duì)結(jié)果進(jìn)行可視化處理；劉明輝［6］研究了解決農(nóng)村垃圾分類回收的問題，通過建立一個(gè)基于負(fù)效應(yīng)和分類關(guān)系的數(shù)學(xué)模型，使用K－means聚類分析法和遺傳算法對(duì)中轉(zhuǎn)設(shè)施選址問題進(jìn)行求解；Teran－Somohano等人［7］提出 了一個(gè)在歐幾里德平面上考慮多容量的不受歡迎設(shè)施選址模型，通過雙目標(biāo)進(jìn)化策略算法對(duì)問題進(jìn)行求解，并將其應(yīng)用于消防站和固體廢物轉(zhuǎn)運(yùn)站的選址問題；韓曉冬等人［8］研究考慮了中轉(zhuǎn)設(shè)施產(chǎn)生大氣污染物的擴(kuò)散性，建立了CFD模型，采用基于計(jì)算流體力學(xué)CFD方法進(jìn)行數(shù)值模擬，根據(jù)影響程度提供選址方案；Kalczynski等人［9］設(shè)計(jì)了一種用于非線性求解器的特殊初始解，以此來提供更好的目標(biāo)值，并在更短的運(yùn)行時(shí)間內(nèi)解決，同時(shí)尋求在滿足最小距離要求的前提下最小化系統(tǒng)的運(yùn)營(yíng)成本；Drezner等人［10］研究了在滿足目標(biāo)為設(shè)施之間的最小距離要求的前提下，最大化設(shè)施與給定社區(qū)之間的最小距離，并提出了基于Voronoi圖和二進(jìn)制線性規(guī)劃的啟發(fā)式算法；Drezner等人［11］研究了在平面網(wǎng)絡(luò)中選擇設(shè)施位置，最小化對(duì)網(wǎng)絡(luò)或從網(wǎng)絡(luò)產(chǎn)生的干擾解決方案，并提出了一種近似算法對(duì)問題進(jìn)行求解；賈傳興等人［12］通過研究逆向物流系統(tǒng)選址的方法，先對(duì)選址位置進(jìn)行初步篩選，再用整數(shù)規(guī)劃的思想構(gòu)建模型進(jìn)行二次優(yōu)化求解；張晨等人［13］研究了具有上層獎(jiǎng)勵(lì)機(jī)制的雙層規(guī)劃模型，通過遺傳算法進(jìn)行求解。

上述研究涵蓋了啟發(fā)式算法、近似算法、數(shù)值模擬法等多類算法，但這些算法得出的方案無法保證解的質(zhì)量，一般無法得到最優(yōu)解。關(guān)于垃圾回收中轉(zhuǎn)設(shè)施的選址問題暫未有精確算法求解的公開出版文獻(xiàn)，本文旨在提出一種結(jié)合數(shù)學(xué)性質(zhì)的降階回溯算法的解決方案，以解決垃圾回收中轉(zhuǎn)設(shè)施選址問題。通過引入降階策略，本文算法能夠在保證計(jì)算效率的同時(shí)，尋找屬于當(dāng)前情況的最優(yōu)解決方案。通過對(duì)該算法的分析和實(shí)驗(yàn)驗(yàn)證，可以為城市垃圾管理部門提供科學(xué)決策支持，促進(jìn)城市垃圾處理和回收工作的可持續(xù)發(fā)展。

1 問題描述

1.1 問題介紹

現(xiàn)代化城市的建設(shè)過程中，垃圾的處理和回收是必不可少的環(huán)節(jié)，但是合理的設(shè)施選址方案卻是一個(gè)復(fù)雜的問題。中國(guó)目前的垃圾處理方式已轉(zhuǎn)變?yōu)橐苑贌秊橹?、填埋為輔、生物處理為補(bǔ)的新格局［14］，其中垃圾回收中轉(zhuǎn)設(shè)施在實(shí)現(xiàn)環(huán)境可持續(xù)發(fā)展和城市清潔的目標(biāo)中扮演著不可或缺的角色。一級(jí)設(shè)施為每個(gè)垃圾產(chǎn)生點(diǎn)本身，如社區(qū)內(nèi)的垃圾站或?qū)W校內(nèi)的垃圾投放點(diǎn)，二級(jí)垃圾回收中轉(zhuǎn)設(shè)施的作用是將周邊垃圾產(chǎn)生點(diǎn)，如居民區(qū)、商圈、飯店、學(xué)校等，通過轉(zhuǎn)運(yùn)設(shè)備運(yùn)輸?shù)皆O(shè)施內(nèi)進(jìn)行分揀、壓縮處理等操作，這可大大提升最終的處理效率。合理的選址方案不僅可以減少處理過程中帶給周邊區(qū)域的影響，還可以降低運(yùn)輸成本，提升經(jīng)濟(jì)效益。

1.2 數(shù)學(xué)符號(hào)與說明

數(shù)學(xué)符號(hào)與說明如表1所示。

服務(wù)的范圍界定：小于x則無法建立（會(huì)影響產(chǎn)生點(diǎn)），大于x小于y時(shí)為可服務(wù)范圍（其中［x，z］為產(chǎn)生影響的服務(wù)范圍hij=dij，［z，y］為不產(chǎn)生影響的服務(wù)范圍hij=0），大于y為不可服務(wù)范圍，其中x、y、z均表示為已設(shè)定的距離參數(shù)（單位km），根據(jù)實(shí)際情況可調(diào)整參數(shù)輸入。

1.3 數(shù)學(xué)模型

本文使用二分圖來構(gòu)建二級(jí)垃圾回收中轉(zhuǎn)設(shè)施的選址問題：將E和F中的元素分別作為二分圖的兩個(gè)頂點(diǎn)子集E和F，對(duì)于給定的回收中轉(zhuǎn)設(shè)施備選點(diǎn)的覆蓋半徑取值［D′，D］，若E中ei至F中fj的距離dij屬于取值［D′，D］，則確定兩者之間存在的路徑。

將符合條件的所有路徑放入集合中，構(gòu)成一個(gè)二分圖G=（V，X）?；?.2節(jié)提出的數(shù)學(xué)符號(hào)，模型如下：

目標(biāo)函數(shù)式（1） 表示在產(chǎn)生最小影響的前提下，最大化回收中轉(zhuǎn)設(shè)施分配給垃圾產(chǎn)生點(diǎn)處理量。其中α、β為判定重要性的權(quán)重系數(shù)，且有α，β∈（0，1］。針對(duì)實(shí)際情況，對(duì)當(dāng)前權(quán)重系數(shù)進(jìn)行調(diào)整。 式（2）表示最多開設(shè)H個(gè)回收設(shè)施。式（3）表示每個(gè)開設(shè)的回收設(shè)施所覆蓋垃圾產(chǎn)生點(diǎn)的每日產(chǎn)出量不能超過該設(shè)施備選點(diǎn)的處理能力。式（4）將所有垃圾分配到已有的收集設(shè)施中時(shí)，其運(yùn)輸成本不應(yīng)該超過總成本上限。式（5）表示每個(gè)垃圾產(chǎn)生點(diǎn)的所有產(chǎn)出均可被處理。式（6）表示垃圾產(chǎn)生點(diǎn)和回收中轉(zhuǎn)設(shè)施備選點(diǎn)之間的距離閾值。式（7）為0－1變量約束。

1.4 數(shù)學(xué)性質(zhì)

性質(zhì)1

在算法的執(zhí)行過程中，當(dāng)|FF5 |≠0時(shí)，若回收設(shè)施開設(shè)數(shù)量|F1∪FF1|＞H，則此情況下無解；當(dāng)| FF5 |＝0時(shí)，有|F1∪FF1|［L，H］，則此情況下無解。

證明

在執(zhí)行回溯算法的過程中，初始搜索階段回收中轉(zhuǎn)設(shè)施的數(shù)量可能小于L，所以應(yīng)分情況判斷。兩種情況均為回收中轉(zhuǎn)設(shè)施的數(shù)量不在計(jì)劃開設(shè)數(shù)量范圍內(nèi)，故無解。

性質(zhì)2

在算法執(zhí)行過程中，若有垃圾產(chǎn)生點(diǎn)ei且其ki =0，則在圖中刪除該產(chǎn)生點(diǎn)及其關(guān)聯(lián)邊；若有回收中轉(zhuǎn)設(shè)施fj且其剩余處理能力t′j-∑ ei∈N（fj） yij=0，則在圖中刪除該設(shè)施點(diǎn)及其關(guān)聯(lián)邊。

證明

當(dāng)產(chǎn)生點(diǎn)需求被全部滿足或回收中轉(zhuǎn)設(shè)施的處理能力已分配完成時(shí)，刪除滿足需求的點(diǎn)以簡(jiǎn)化圖，刪除圖中節(jié)點(diǎn)和邊的操作不會(huì)影響最終目標(biāo)函數(shù)的取值。

性質(zhì)3

對(duì)于回收中轉(zhuǎn)設(shè)施集合（F1∪FF1∪FF5），若存在∑ fj∈F1∪FF1∪FF5 t′j＜∑ m/i=1 pi·produce，則此時(shí)該問題無可行解。

證明

表示回收中轉(zhuǎn)設(shè)施備選點(diǎn)的總處理量小于相連垃圾產(chǎn)生點(diǎn)的總產(chǎn)出量，故無可行解。

性質(zhì)4

檢查垃圾產(chǎn)生點(diǎn)ei，若存在滿足條件|N（ei）|=1的點(diǎn)，則該垃圾產(chǎn)生點(diǎn)ei的所有垃圾都必須由唯一可處理該垃圾的設(shè)施fj來處理，當(dāng)FF0∪FF1=時(shí)，設(shè)施fj一定開設(shè)，加入集合F1中；當(dāng)FF0∪FF1≠時(shí)，該情況下設(shè)施fj一定開設(shè)，加入集合FF1中。

證明

反證法。未開設(shè)fj，無法保證服務(wù)所有產(chǎn)生點(diǎn)，未開設(shè)未優(yōu)先分配則導(dǎo)致該孤立節(jié)點(diǎn)所產(chǎn)生的垃圾無法被處理，無法滿足約束式（5），故得證。

性質(zhì)5

對(duì)于集合F＼F1＼F0中任意兩個(gè)回收中轉(zhuǎn)設(shè)施備選點(diǎn)fj和fh，若N（fh） N（fj），∑ ei∈N（fj） ki≤tj，zj＞zh，且對(duì)于任一ei∈N（fh），都有wij＞wih，Oij＜Oih，則稱備選點(diǎn)fj相較于fh具有相對(duì)優(yōu)勢(shì)，若此時(shí)|FF0∪FF1|=0，則fh一定不開設(shè)，加入集合F0，fj是否開設(shè)無法確定，加入集合F5。

證明

替代法。在集合F＼F1＼F0中表示算法尚未處于二叉樹搜索中，若選擇開設(shè)fh，在同樣開設(shè)一個(gè)回收設(shè)施的情況下，存在一個(gè)更加有優(yōu)勢(shì)的備選點(diǎn)，無法滿足解的最優(yōu)性；設(shè)施fj的開設(shè)情況無法確定，可能存在更加有優(yōu)勢(shì)的備選點(diǎn)。

性質(zhì)6

對(duì)于集合F＼F1＼F0＼FF1＼FF0中任意兩個(gè)回收中轉(zhuǎn)設(shè)施備選點(diǎn)fj和fh，若N（fh）N（fj），∑ ei∈N（fj） ki≤tj，zj＞zh，且對(duì)于任一ei∈N（fh），都有wij＞wih，Oij＜Oih，則稱備選點(diǎn)fj相較于fh具有相對(duì)優(yōu)勢(shì)，若此時(shí)|FF0∪FF1|＞0，則fh在當(dāng)前情況下一定不開設(shè)，加入集合FF0，fj是否開設(shè)無法確定，加入集合FF5。

證明

替代法。在集合F＼F1＼F0＼FF1＼FF0中表示算法當(dāng)前處于二叉樹的回溯搜索中，若選擇開設(shè)fh，在同樣開設(shè)一個(gè)回收設(shè)施的情況下，存在一個(gè)更加有優(yōu)勢(shì)的備選點(diǎn)，無法滿足解的最優(yōu)性；設(shè)施fj的開設(shè)情況無法確定，可能存在更加有優(yōu)勢(shì)的備選點(diǎn)。

性質(zhì)7

在當(dāng)前的圖G中檢查所有回收中轉(zhuǎn)設(shè)施關(guān)聯(lián)懸掛產(chǎn)生點(diǎn)ei的個(gè)數(shù)Q，若存在中轉(zhuǎn)設(shè)施fj，且滿足∑t′jlt;∑ ei∈N（fj）且N（ei）=1 pi·produce ，則該情況下無可行解。

證明

當(dāng)圖G中存在孤立的一個(gè)產(chǎn)生節(jié)點(diǎn)ei時(shí)，中轉(zhuǎn)設(shè)施會(huì)將處理能力進(jìn)行優(yōu)先分配，當(dāng)懸掛點(diǎn)的總需求處理量已經(jīng)大于該設(shè)施的最大處理能力t′j時(shí)，則存在產(chǎn)生點(diǎn)的產(chǎn)出量無法被完全處理，故無解。

性質(zhì)8

假設(shè)一個(gè)回收中轉(zhuǎn)設(shè)施fj∈F5開設(shè)，即此時(shí)FF1= {fj}，F(xiàn)F0={}，若此時(shí)ub=None或者上界ub小于下界lb，則確定在fj處一定不開設(shè)且不在最優(yōu)解中，將fj加入集合F0。

證明

當(dāng)出現(xiàn)ub=None或者上界ub小于下界lb時(shí)，無法取得當(dāng)前目標(biāo)函數(shù)值的最優(yōu)解，所以fj處不應(yīng)開設(shè)設(shè)施。

性質(zhì)9

假設(shè)一個(gè)回收中轉(zhuǎn)設(shè)施fj∈F5不開設(shè)，即FF0={fj}，F(xiàn)F1={}，若此時(shí)ub=None或者上界ub小于下界lb，則確定在fj處一定開設(shè)且存在于最優(yōu)解中，將fj加入集合F1。

證明

當(dāng)出現(xiàn)ub=None或者上界ub小于下界lb時(shí)，無法取得當(dāng)前目標(biāo)函數(shù)值的最優(yōu)解，所以fj處應(yīng)開設(shè)設(shè)施。

性質(zhì)10

在算法開始執(zhí)行前，將所有回收中轉(zhuǎn)設(shè)施按照每日處理能力從大到小進(jìn)行降序排序，從f1開始進(jìn)行累加求和，當(dāng)?shù)谝淮卫奂拥絝l時(shí)，若滿足∑ l/j=1 tj≥∑ m/i=1 pi·produce，則可知當(dāng)前最少開設(shè)數(shù)量為L(zhǎng)，進(jìn)而得出開設(shè)回收中轉(zhuǎn)設(shè)施數(shù)量的取值為L(zhǎng)≤∑ n/j=1 xj≤H。

證明

在處理能力滿足所有垃圾產(chǎn)生點(diǎn)需求的同時(shí)對(duì)所有垃圾產(chǎn)生點(diǎn)全覆蓋，則存在一種理想情況，即所有的回收中轉(zhuǎn)設(shè)施{f1，f2，…， fl}均被充分利用，屬于集合|F1∪FF1|=L，得到最優(yōu)開設(shè)數(shù)量L，此時(shí)得出的解即為理想情況下的最優(yōu)解，故得證。 性質(zhì)11

在回溯算法執(zhí)行前，若有∑ fj∈FF5 tj＜∑ ei∈E3∪E5 pi·produce，則該問題無解。在回溯執(zhí)行過程中，若有∑ fj∈FF5 tj＜∑ ei∈E3∪E5 pi·produce，則該分支對(duì)應(yīng)的情況下無解。

證明

表示在未確定是否開設(shè)回收中轉(zhuǎn)設(shè)施fj的集合中，所有回收中轉(zhuǎn)設(shè)施的處理能力無法滿足剩余未分配、未分配完成和存疑的產(chǎn)生點(diǎn)ei的產(chǎn)生總量。|FF5|≠0時(shí)表示處于回溯搜索之中，滿足上述條件；|FF5|＝0時(shí)處于葉子節(jié)點(diǎn)，表示還有產(chǎn)生點(diǎn)的產(chǎn)出量尚未被處理。

性質(zhì)12

在回溯過程中，若在集合E3∪E5中存在產(chǎn)生點(diǎn)有|N（ei）|=0，則表明此時(shí)存在孤立的產(chǎn)生點(diǎn)ei，此情況下無解；當(dāng)搜索到葉子節(jié)點(diǎn)時(shí)，執(zhí)行分配子算法之后（詳見2.1節(jié)），若集合（E3∪E5）≠，則該葉子節(jié)點(diǎn)無可行解。

證明

初始條件表示在回溯過程中無回收中轉(zhuǎn)設(shè)施fj可以處理孤立產(chǎn)生點(diǎn)ei的產(chǎn)生量；判斷條件表示在所有回收中轉(zhuǎn)設(shè)施的開設(shè)情況均已確定時(shí)，存在產(chǎn)生點(diǎn)ei的產(chǎn)生量未被處理或處理不完全，兩種情況下該問題均無解。

2 算法設(shè)計(jì)與分析

如圖2所示，本文設(shè)計(jì)的算法主要分為回溯前降階處理階段和回溯搜索階段。在第一階段，使用上下界子算法得出此時(shí)問題的上下界，使用降階子算法對(duì)問題進(jìn)行初始的規(guī)?？s減；第二階段，使用回溯子算法處理降階后的問題，當(dāng)處于葉子節(jié)點(diǎn)時(shí)，調(diào)用分配子算法對(duì)當(dāng)前情況下的分配方案進(jìn)行求解。

2.1 分配子算法

由于本文研究的選址問題中的每個(gè)產(chǎn)生點(diǎn)和中轉(zhuǎn)設(shè)施的需求處理量和處理能力有所不同，從而導(dǎo)致從垃圾產(chǎn)生點(diǎn)分配到中轉(zhuǎn)設(shè)施的量存在不同方案，所以需要在多項(xiàng)式時(shí)間內(nèi)找到一種最優(yōu)的分配方案，進(jìn)而得到該情況下的最優(yōu)解。因?yàn)楫a(chǎn)生點(diǎn)與中轉(zhuǎn)設(shè)施構(gòu)成了一個(gè)二分圖，所以本文設(shè)計(jì)了一個(gè)針對(duì)二分圖的最小費(fèi)用最大流算法［14］的分配子算法程序，算法內(nèi)部使用了SPFA算法 （shortest path faster algorithm）［15］求解最短路徑。

分配子算法具體步驟如下：

a）初始化葉子節(jié)點(diǎn)處的開設(shè)設(shè)施集合Ft=F1∪FF1。

b）將集合Ft內(nèi)的中轉(zhuǎn)設(shè)施fj與所有產(chǎn)生點(diǎn)相互對(duì)應(yīng)的路徑矩陣信息（存儲(chǔ)d′ij信息的矩陣形式）導(dǎo)入最小費(fèi)用最大流求解器中；其中在d′ij矩陣中兩點(diǎn)不相連，則將矩陣中的數(shù)值更改為inf。

c）使用最小費(fèi)用最大流求解器對(duì)導(dǎo)入矩陣進(jìn)行處理，得到最終的最優(yōu)分配矩陣，具體操作如下：

（a）構(gòu)建超級(jí)源點(diǎn)S和超級(jí)匯點(diǎn)T。

（b） 從超級(jí)源點(diǎn) S向集合E中的產(chǎn)生點(diǎn)連接一條邊，其中邊的容量為對(duì)應(yīng)產(chǎn)生點(diǎn)的剩余需求處理量ki，初始化距離為0。

（c） 從Ft中的每個(gè)中轉(zhuǎn)設(shè)施向超級(jí)匯點(diǎn)T連接一條邊，其中邊的容量為對(duì)應(yīng)中轉(zhuǎn)設(shè)施的剩余處理能力tj，初始化距離為0。

（d）產(chǎn)生點(diǎn)與中轉(zhuǎn)設(shè)施之間的距離為路徑矩陣中對(duì)應(yīng)的數(shù)值，每條邊的容量為產(chǎn)生點(diǎn)的剩余需求處理量ki。

（e）調(diào)用程序求解該網(wǎng)絡(luò)流圖。若得到的最優(yōu)分配矩陣中，所有元素之和小于產(chǎn)生點(diǎn)的需求處理量之和，則表明產(chǎn)生點(diǎn)未得到完全分配，該情況下無解，分配子算法結(jié)束；否則得到一個(gè)最優(yōu)分配矩陣，調(diào)用程序中求解目標(biāo)函數(shù)之和的方法得到當(dāng)前Ft對(duì)應(yīng)的目標(biāo)函數(shù)值。

為了清楚地解釋分配子算法的過程，給出如下示例說明。

示例1如圖3所示的垃圾回收中轉(zhuǎn)設(shè)施問題，現(xiàn)有3個(gè)已暫定新建的垃圾回收中轉(zhuǎn)設(shè)施F={f1，f2，f3}，以及7個(gè)垃圾產(chǎn)生點(diǎn)E={e1，e2，e3，e4，e5}，每個(gè)設(shè)施上方和產(chǎn)生點(diǎn)下方標(biāo)注的數(shù)值為中轉(zhuǎn)設(shè)施剩余處理能力tj和產(chǎn)生點(diǎn)需求處理量ki，產(chǎn)生點(diǎn)與中轉(zhuǎn)設(shè)施之間存在連線即表示為中轉(zhuǎn)設(shè)施可以服務(wù)該產(chǎn)生點(diǎn)，連線處標(biāo)注的數(shù)值為設(shè)施點(diǎn)與產(chǎn)生點(diǎn)間的直線距離dij。

示例1的分配過程簡(jiǎn)述如下：

a）分別在產(chǎn)生點(diǎn)下方和中轉(zhuǎn)設(shè)施上方設(shè)置一個(gè)超級(jí)源點(diǎn)S和超級(jí)匯點(diǎn)T。

b）將超級(jí)源點(diǎn)S與所有的產(chǎn)生點(diǎn)相連，所有的中轉(zhuǎn)設(shè)施連接到超級(jí)匯點(diǎn)T，每條邊的數(shù)值均標(biāo)記為0；其中設(shè)定超級(jí)源點(diǎn)S與產(chǎn)生點(diǎn)相連邊的容量為產(chǎn)生點(diǎn)需求處理量ki，中轉(zhuǎn)設(shè)施與超級(jí)匯點(diǎn)T相連邊的容量為設(shè)施剩余處理能力tj。

c）使用最小費(fèi)用最大流算法（圖4）對(duì)該圖進(jìn)行求解，得到在該葉子節(jié)點(diǎn)的目標(biāo)函數(shù)值。

2.2 上界子算法

通過設(shè)計(jì)一個(gè)上界子算法求解該問題的初始上界，盡可能滿足目標(biāo)函數(shù)最大化的要求。在上界子算法中，先使用1.4節(jié)提出的數(shù)學(xué)性質(zhì)對(duì)問題進(jìn)行降階處理，多次使用排序算法對(duì)集合中符合要求的元素進(jìn)行篩選，將目標(biāo)函數(shù)分解為a、b和c三部分，視作（a+b）/c格式，最后通過貪婪算法求得a、b部分的最大值，c的最小值，計(jì)算問題的上界。上界子算法具體步驟如下：

a）初始化集合Fup={}，同時(shí)滿足E5=E＼E1＼E3，F(xiàn)F5=F＼F1＼F0＼FF0＼FF1始終成立。

b）由性質(zhì)4判斷集合FF5中一定開設(shè)的中轉(zhuǎn)設(shè)施，加入集合FF1；由性質(zhì)6找出集合FF5中一定不開設(shè)的中轉(zhuǎn)設(shè)施fj，加入集合FF0，使用性質(zhì)3判斷當(dāng)前解的情況；若無解則返回ub=None，上界子算法結(jié)束；使用性質(zhì)2進(jìn)行更新。

c）對(duì)于集合FF5中所有中轉(zhuǎn)設(shè)施fj，按與水源距離qj進(jìn)行降序排列，取前H-|F1∪FF1|個(gè)中轉(zhuǎn)設(shè)施fj并加入集合Fw，執(zhí)行Fup=Fup∪Fw，計(jì)算b′=∑ fj∈Fw βqjxj，得出b=b′+∑ fj∈F1∪FF1 βqjxj。

d）將集合Fr=F＼（F0∪FF0）中的中轉(zhuǎn)設(shè)施按照處理能力tj降序排列，從大到小依次處理。

e）選取集合中第一個(gè)元素；若集合Fr=，則使用性質(zhì)2更新并轉(zhuǎn)至步驟h）。

f）對(duì)于選中的中轉(zhuǎn)設(shè)施fj，將N（fj）相連的所有產(chǎn)生點(diǎn)ei按閾值hij進(jìn)行降序排列并加入集合Etemp，調(diào)用步驟g）對(duì)集合Etemp與選中設(shè)施fj進(jìn)行處理，處理完成時(shí)執(zhí)行Fr=Fr＼fj 并轉(zhuǎn)至步驟 e）。

g）（a）判斷兩集合中的第一個(gè)元素，若fj可以完全處理ei的全部產(chǎn)出，轉(zhuǎn)至步驟（b）；否則轉(zhuǎn)至步驟（c）。

（b）執(zhí)行（E3∪E5）＼ei，E1∪ei，刪除產(chǎn)生點(diǎn)集合ei中的第一個(gè)元素，并更新中轉(zhuǎn)設(shè)施的處理能力；若tj=0，有Fup=Fup∪fj，轉(zhuǎn)至步驟（d）；否則返回步驟（a）。

（c） 將fj剩余處理能力分配給產(chǎn)生點(diǎn)ei，更新產(chǎn)生點(diǎn)的剩余產(chǎn)出量ki=ki-yij，執(zhí)行Fup=Fup∪fj，E3= E3∪ei，轉(zhuǎn)至步驟（d）。

（d）刪除中轉(zhuǎn)設(shè)施fj集合中的第一個(gè)元素，若兩集合其中一個(gè)為空集，則終止步驟g）；否則返回步驟（a）。

h）對(duì)集合Etemp=（E3∪E5）中的每個(gè)元素依次處理，將選定產(chǎn)生點(diǎn)N（ei）相連的中轉(zhuǎn)設(shè)施加入集合Ftemp中，將Ftemp按照hij大小按降序排列，調(diào)用步驟g）進(jìn)行處理，每處理完成一個(gè)產(chǎn)生點(diǎn)ei時(shí)執(zhí)行Ftemp=，當(dāng)Etemp=時(shí)表明處理完畢。

i） 根據(jù)集合Lij的所有數(shù)據(jù)進(jìn)行計(jì)算，則a=∑ ei∈E1 ∑ fj∈Fup α hij/pi xj，執(zhí)行Lij=。

j）對(duì)于集合Etemp=（E3∪E5），按照產(chǎn)生點(diǎn)的產(chǎn)生量進(jìn)行降序排列，對(duì)每一個(gè)產(chǎn)生點(diǎn)依次進(jìn)行處理。

k） 對(duì)于選中的產(chǎn)生點(diǎn)，將N（ei）相連的所有中轉(zhuǎn)設(shè)施fj按路徑距離d′ij升序加入集合Ftemp中，調(diào)用步驟g）對(duì)集合Ftemp進(jìn)行處理，每處理完成一個(gè)產(chǎn)生點(diǎn)ei時(shí)執(zhí)行Ftemp=，當(dāng)Etemp=時(shí)表明處理完畢。

l） 根據(jù)集合Lij的所有數(shù)據(jù)進(jìn)行計(jì)算，則 c=∑ ei∈E1∑ fj∈Fup R·yij·d′ij計(jì)算上界，ub= ∑ ei∈E1∑ fj∈Fup wij+∑ fj∈Fup zj/∑ ei∈E1∑ fj∈Fup oij =（a+b）/c，此時(shí)得到問題上界，上界子算法結(jié)束。

2.3 下界子算法

求解該問題的下界，選取任何一個(gè)可行解對(duì)應(yīng)的目標(biāo)函數(shù)值即可作為該問題的下界。本文使用1.4節(jié)所提出的數(shù)學(xué)性質(zhì)，先對(duì)該問題進(jìn)行降階，再根據(jù)提出的下界子算法求得問題的下界，混合使用數(shù)學(xué)性質(zhì)和貪心算法所得到的下界優(yōu)于絕大部分可行解。下界子算法具體步驟如下：a）初始化集合Flow ={}，同時(shí)滿足E5=E＼E1＼E3，F(xiàn)5=F＼F1＼F0始終成立。

b）由性質(zhì)5找出一定不開設(shè)的中轉(zhuǎn)設(shè)施fj，加入集合F0；使用性質(zhì)3判斷當(dāng)前解的情況，若存在∑ fj∈F tj＜∑ m/i=1 pi·produce，則下界子算法無解，下界暫定為+∞，下界子算法結(jié)束；否則轉(zhuǎn)至步驟c）。

c）由性質(zhì)4判斷一定開設(shè)的中轉(zhuǎn)設(shè)施，加入集合F1，使用性質(zhì)1判斷此時(shí)是否無解，若無解則下界暫定為+∞，下界子算法結(jié)束；使用性質(zhì)2進(jìn)行更新。

d）定義集合Ftemp=（F1∪F5），檢查Ftemp中的所有設(shè)施，若對(duì)相連的產(chǎn)生點(diǎn)存在N（fj）=，則執(zhí)行Ftemp=Ftemp/fj。

e）將集合Ftemp中剩余回收設(shè)施fj，按照剩余處理能力tj-∑ ei∈N（fj）yij 進(jìn)行降序排列，從大到小依次對(duì)每個(gè)中轉(zhuǎn)設(shè)施進(jìn)行處理。

f）將集合Ftemp中第一個(gè)設(shè)施設(shè)定為選中設(shè)施fj。

g）對(duì)于選定中轉(zhuǎn)設(shè)施，將其服務(wù)范圍內(nèi)N（fj）的所有產(chǎn)生點(diǎn)的產(chǎn)生量進(jìn)行降序排列，加入集合Etemp，依次與中轉(zhuǎn)設(shè)施相關(guān)聯(lián)并加入集合E1，當(dāng)累加到某一產(chǎn)生點(diǎn)ei時(shí)存在∑ ei∈N（fj） yij≥tj，停止當(dāng)前產(chǎn)生點(diǎn)的關(guān)聯(lián)，更新集合Etemp=Etemp＼ei，將關(guān)聯(lián)關(guān)系存入集合Lij，并使用性質(zhì)2進(jìn)行更新。

h） 向下搜索集合Etemp，若有產(chǎn)生點(diǎn)ei滿足ki≤tj-∑ ei∈N（fj） yij， 則將該產(chǎn)生點(diǎn)加入集合E1中，重復(fù)步驟h）直至集合E3中無符合要求的點(diǎn)，然后將中轉(zhuǎn)設(shè)施fj加入集合Flow，并執(zhí)行Ftemp=Ftemp/fj，將關(guān)聯(lián)關(guān)系存入集合Lij，最后轉(zhuǎn)至步驟i）；若無符合要求的產(chǎn)生點(diǎn)ei，則直接執(zhí)行Ftemp=Ftemp/fj，并轉(zhuǎn)至步驟i）。

i）判斷產(chǎn)生點(diǎn)處理情況，若E3∪E5=則轉(zhuǎn)至步驟j），若E3∪E5≠則返回至步驟e）。

j） 檢查集合Flow，若在集合Flow中存在中轉(zhuǎn)設(shè)施fj有N（fj）=，則將該中轉(zhuǎn)設(shè)施加入集合F5；在優(yōu)化完成后計(jì)算下界lb= ∑ ei∈E1∑ fj∈Ftemp wij+∑ fj∈Ftemp zj/∑ ei∈E1∑ fj∈Ftemp oij ，F(xiàn)best=Flow，得到問題下界，下界子算法結(jié)束。

2.4 降階子算法

降階算法通過1.4節(jié)提出的數(shù)學(xué)性質(zhì)對(duì)問題中回收中轉(zhuǎn)設(shè)施的開設(shè)情況進(jìn)行判斷，減小問題規(guī)模。降階算法步驟如下：

a）使用性質(zhì)4和5對(duì)問題進(jìn)行降階處理；若F0發(fā)生變化則使用性質(zhì)1、3和12判斷問題是否無解；使用性質(zhì)2進(jìn)行更新。

b）當(dāng)F0發(fā)生變化時(shí)，調(diào)用下界子算法對(duì)問題下界lb進(jìn)行優(yōu)化，得到此時(shí)開設(shè)設(shè)施集合Flow、對(duì)應(yīng)目標(biāo)函數(shù)值best_q。

c）對(duì)于集合F5中的所有中轉(zhuǎn)設(shè)施，使用性質(zhì)8對(duì)問題進(jìn)行降階處理；若集合F0中元素發(fā)生變化，使用性質(zhì)3和12判斷問題是否無解，使用性質(zhì)2進(jìn)行更新。

d）使用性質(zhì)9對(duì)問題進(jìn)行降階處理；若集合F1中的元素發(fā)生變化，使用性質(zhì)1和3判斷問題是否無解，使用性質(zhì)2進(jìn)行更新。

2.5 回溯子算法

本文的回溯子算法從根節(jié)點(diǎn)出發(fā)，以深度優(yōu)先的方式對(duì)解空間二叉樹進(jìn)行搜索。當(dāng)搜索至任意節(jié)點(diǎn)時(shí)，先使用數(shù)學(xué)性質(zhì)進(jìn)行處理，然后計(jì)算當(dāng)前節(jié)點(diǎn)的上界ub，如果上界ub=None或者ub小于當(dāng)前下界lb，則進(jìn)行剪枝，否則對(duì)集合FF5中的第一個(gè)元素進(jìn)行處理：假設(shè)該點(diǎn)開設(shè)可以得到可行解，則執(zhí)行左子樹搜索；否則執(zhí)行右子樹搜索?；厮葑铀惴╞acktracking（cur_i）的具體步驟如下：

a）若FF5=，則到達(dá)葉子節(jié)點(diǎn)，此時(shí)得到一個(gè)對(duì)應(yīng)的解集合Fn=（F1∪FF1），利用性質(zhì)1和11判斷此情況下是否無解，并調(diào)用分配子算法判斷是否有解。當(dāng)存在解時(shí)，若計(jì)算當(dāng)前目標(biāo)函數(shù)值q_n＞best_q，則更新下界lb與當(dāng)前最優(yōu)解集Fbest，返回上一層。

b）若FF5≠，分兩種情況進(jìn)行處理：a）假設(shè)FF5中的第一個(gè)中轉(zhuǎn)設(shè)施fj開設(shè)，轉(zhuǎn)至步驟c）；（b）假設(shè)FF5中的第一個(gè)中轉(zhuǎn)設(shè)施fj不開設(shè)，轉(zhuǎn)至步驟e）。

c）執(zhí)行FF5= FF5＼fj，F(xiàn)F1= FF1∪fj，利用性質(zhì)1、7和11判斷此情況下是否無解，若無解則進(jìn)行左子樹剪枝，轉(zhuǎn)至步驟d）；否則調(diào)用上界子算法計(jì)算上界ub。當(dāng)滿足ub≠None且ub≥lb， 此時(shí)表明可能存在優(yōu)于當(dāng)前下界的解，調(diào)用backtracking（cur_i+1）繼續(xù)向下搜索；若ub=None且ub＜lb，左子樹剪枝，轉(zhuǎn)至d）。

d） 返回二叉樹的上一層前執(zhí)行FF1=FF1＼fj，F(xiàn)F5= FF5∪fj。

e）初始化集合Ftemp_1=Ftemp_2=Etemp=，假設(shè)選中的中轉(zhuǎn)設(shè)施fj不開設(shè)，執(zhí)行FF5=FF5＼fj，F(xiàn)F0=FF0∪fj；檢查是否滿足性質(zhì)7、11和12的條件，若無解則進(jìn)行右子樹剪枝，轉(zhuǎn)至步驟f）；否則調(diào)用上界子算法計(jì)算當(dāng)前節(jié)點(diǎn)處上界ub，當(dāng)滿足ub≠None且ub≥lb，此時(shí)表明可能存在優(yōu)于當(dāng)前下界的解，使用性質(zhì)6得出加入集合FF0中的中轉(zhuǎn)設(shè)施集合Ftemp_1，使用性質(zhì)4得出一定開設(shè)的中轉(zhuǎn)設(shè)施集合Ftemp_2，將已分配完全的產(chǎn)生點(diǎn)加入集合E temp中，執(zhí)行FF0=FF0∪Ftemp_1，F(xiàn)F1= FF1∪Ftemp_2，F(xiàn)F5=FF5＼Ftemp_1＼Ftemp_2，E5=E1＼Etemp，E1=E1∪Etemp，調(diào)用backtracking（cur_i+1）繼續(xù)向下搜索更優(yōu)解；若ub=None且ub＜lb，右子樹剪枝，轉(zhuǎn)至f）。

f）返回二叉樹上一層前，執(zhí)行FF0=FF0＼Ftemp_1＼fj，F(xiàn)F1=FF1＼Ftemp_2，E1=E1＼Etemp，E5=E1∪Etemp，F(xiàn)F5=FF5∪Ftemp_1∪Ftemp_2∪fj。

g）當(dāng)算法結(jié)束時(shí)，目標(biāo)函數(shù)最優(yōu)值best_q即為問題的最優(yōu)解，F(xiàn)best為對(duì)應(yīng)的回收中轉(zhuǎn)設(shè)施點(diǎn)集合。

2.6 主算法

a）根據(jù)垃圾產(chǎn)生點(diǎn)集合E和回收中轉(zhuǎn)設(shè)施集合F構(gòu)建二分圖G=（V，X），其中V=E∪F。

b）初始化集合：F0=F1=FF0=FF1=Fbest={}，初始化best_q=0，調(diào)用性質(zhì)10求得當(dāng)前最小值。

c）根據(jù)性質(zhì)3、11判斷該問題是否無解。

d）調(diào)用下界子算法，求得問題的下界lb。

e）調(diào)用降階子算法，對(duì)問題進(jìn)行降階；若降階子算法結(jié)束后F＼F5發(fā)生變化，則轉(zhuǎn)至d）重新計(jì)算下界，并使用性質(zhì)2進(jìn)行更新；否則轉(zhuǎn)至f）。

f）調(diào)用回溯子算法backtrack（1），獲取問題的最優(yōu)解Fbest及目標(biāo)函數(shù)最優(yōu)值best_q。

2.7 算法時(shí)間復(fù)雜度分析

針對(duì)本文求解的回收設(shè)施選址問題，設(shè)定候選設(shè)施的數(shù)量為H，在搜索解空間二叉樹中最多產(chǎn)生2H個(gè)葉子節(jié)點(diǎn)，計(jì)算該問題的時(shí)間復(fù)雜度為O（2H）。本文通過設(shè)計(jì)一種降階回溯算法，對(duì)該問題進(jìn)行降階處理，使用數(shù)學(xué)性質(zhì)與降階子算法最終得到進(jìn)入二叉樹搜索前的回收中轉(zhuǎn)設(shè)施集合F5，令N=|F5|，因此算法在最壞情況下的時(shí)間復(fù)雜度為O（2N），其中N≤H。

對(duì)于求解不受歡迎選址問題的其他方法有近似算法、啟發(fā)式算法、分析和決策方法，聚類分析、蒙特卡羅模擬、模糊邏輯等均無法保證求得解的最優(yōu)性。本文算法是精確算法，求得的解一定是全局最優(yōu)解。

本文為一種改進(jìn)的精確算法，首先通過研究問題性質(zhì)，在算法進(jìn)行之前利用數(shù)學(xué)性質(zhì)降低問題規(guī)模，只需要處理其中一部分中轉(zhuǎn)設(shè)施，降低了算法的時(shí)間復(fù)雜性；其次，設(shè)計(jì)了上下界子算法在二叉樹搜索過程中進(jìn)行剪枝，只對(duì)部分解子樹進(jìn)行搜索，提高了算法的求解速度；最后，在搜索的過程中利用數(shù)學(xué)性質(zhì)批量地確定某些一定開設(shè)或一定不開設(shè)的中轉(zhuǎn)設(shè)施，從而更快地通過求解空間二叉樹來確定目標(biāo)最優(yōu)值。

3 示例分析

3.1 小規(guī)模示例分析

通過求解一個(gè)小規(guī)模示例來對(duì)本文算法及執(zhí)行過程進(jìn)行說明，其中常規(guī)參數(shù)設(shè)定如下：a）根據(jù)上海市綠化和市容管理局公布數(shù)據(jù)［16］，將每人每天產(chǎn)生的垃圾量produce設(shè)定為1.2 kg，每噸垃圾每公里運(yùn)輸成本R為0.026 k/（t·km）；b）綜合考慮交通情況和地理?xiàng)l件，將最大覆蓋半徑D設(shè)定為6 km；c）參考Luxen等人［17］研究了路徑距離與直線距離比值的結(jié)果，取值1.4計(jì)算設(shè)施與產(chǎn)生點(diǎn)間的路徑距離，設(shè)定初始參數(shù)值α=β=1。

示例2 如圖5所示的初始狀態(tài)，現(xiàn)有7個(gè)垃圾回收中轉(zhuǎn)設(shè)施F={f1，f2，…，f7}，以及9個(gè)垃圾產(chǎn)生點(diǎn)E={e1，e2，…，e9}，相較示例1新增條件H=5、設(shè)施距離水源距離qj和區(qū)域人口數(shù)量pi。備選點(diǎn)基本信息如表2所示。

調(diào)用主算法進(jìn)行求解，具體步驟如下：

a）初始化集合：F0=F1=FF0=FF1= Fbest ={}，初始化best_q=0。

b） 調(diào)用性質(zhì)10求得當(dāng)前情況下最少開設(shè)設(shè)施數(shù)目，K=4。

c）該問題不滿足性質(zhì)3及11，當(dāng)前階段該問題有界。

d）執(zhí)行下界子算法，求得該問題的初始下界，初始下界為lb=49895，具體求解方法見2.3節(jié)。

e）執(zhí)行降階子算法，求解過程如下：

（a）使用性質(zhì)4對(duì)問題進(jìn)行降階，返回懸掛點(diǎn)并執(zhí)行F1 ={ f4}，F(xiàn)5=F ＼F1 ={ f1，f2，f3，f5，f6，f7}。

（b）使用性質(zhì)5對(duì)問題進(jìn)行降階，得到一個(gè)劣勢(shì)點(diǎn)f7，執(zhí)行F0={ f7}，F(xiàn)5=F ＼F1 ={ f1，f2，f3，f5，f6}。

（c）因F0發(fā)生變化，執(zhí)行判斷操作，不滿足，故該問題有解；使用性質(zhì)2對(duì)圖進(jìn)行更新。

（d）使用性質(zhì)9對(duì)該問題進(jìn)行降階，當(dāng)計(jì)算至設(shè)施f6時(shí)，求得上界值ub=49730，當(dāng)前下界為lb=49895，滿足ub＜lb，表示設(shè)施f6一定開設(shè)，執(zhí)行F1 ={ f4，f6}，F(xiàn)5={ f1，f2，f3，f5}；調(diào)用性質(zhì)1和3，不滿足，故該問題有解；性質(zhì)8的執(zhí)行方式同性質(zhì)9，處理完畢后F0未發(fā)生變化，無須執(zhí)行判斷操作。

（e）降階子算法結(jié)束，返回降階后的設(shè)施集合，使用性質(zhì)2對(duì)圖進(jìn)行更新。

f）更新集合：F1 ={ f4，f6}，F(xiàn)F1={}，F(xiàn)F5=F5={ f1，f2，f3，f5}，調(diào)用回溯子算法backtracking（cur_i=1），回溯子算法詳細(xì)求解過程如圖6所示。

g）回溯子算法求解結(jié)束，輸出最優(yōu)開設(shè)設(shè)施集合為Fbest={ f2，f3，f4，f5，f6}，最優(yōu)目標(biāo)值為best_q=54501。

3.2 隨機(jī)算例分析

為驗(yàn)證本文設(shè)計(jì)的降階回溯算法在求解時(shí)的有效性，本文使用 Python3.7實(shí)現(xiàn)程序，運(yùn)行環(huán)境為Windows 10操作系統(tǒng)，Intel CoreTM i7－12700H CPU2.4 GHz。采用隨機(jī)策略生成20個(gè)數(shù)據(jù)集，各產(chǎn)生點(diǎn)人口數(shù)量pi∈［500，1500］，各中轉(zhuǎn)設(shè)施的處理能力tj∈［2000，3500］，按照3.1節(jié)設(shè)定的produce、R和距離比值進(jìn)行取值，各產(chǎn)生點(diǎn)的產(chǎn)生量ki=produce·pi。求解各數(shù)據(jù)集，其中r_n為降階子算法結(jié)束后進(jìn)入回溯子算法的問題規(guī)模測(cè)試結(jié)果，如表3所示。

由表3可以看出，本文算法能夠通過數(shù)學(xué)性質(zhì)在回溯搜索前對(duì)問題進(jìn)行降階處理，減少進(jìn)入回溯的設(shè)施個(gè)數(shù)。在回溯搜索中，通過數(shù)學(xué)性質(zhì)、上下界及問題本身的約束，大量減少不必要的搜索分支，從而加快算法的求解速度。

3.3 算法對(duì)比分析

為驗(yàn)證本文算法的科學(xué)性，將本文設(shè)計(jì)的降階回溯算法（backtracking algorithm with reduction，BAR）與同屬精確算法的優(yōu)先隊(duì)列式分支定界法［19］（branch and bound algorithm，BBA）進(jìn)行對(duì)比。因BBA在計(jì)算過程中需要使用上界和下界，所以為了保證結(jié)果合理性，使用與本文相同的上下界子算法進(jìn)行求解。

使用3.2節(jié)中的1～20號(hào)測(cè)試用例作為測(cè)試集，由于兩者均為精確算法，均可保證求得全局最優(yōu)解，故僅對(duì)兩種算法在求解過程中二叉樹實(shí)際搜索葉子節(jié)點(diǎn)的數(shù)量n_l與求解時(shí)間time（s）進(jìn)行對(duì)比實(shí)驗(yàn)，其中程序運(yùn)行時(shí)間超過60 s則不進(jìn)行統(tǒng)計(jì)。實(shí)驗(yàn)結(jié)果如表4所示。

由表4可看出，在計(jì)算20個(gè)測(cè)試用例時(shí)，降階回溯算法BAR訪問葉子節(jié)點(diǎn)的個(gè)數(shù)均小于優(yōu)先隊(duì)列式分支定界法，同時(shí)在求解時(shí)間上也優(yōu)于BBA，由此可說明BAR在二叉樹搜索時(shí)的剪枝效率明顯好于BAR，并且擁有更好的求解效率。

3.4 案例研究

為進(jìn)一步說明本文研究問題的現(xiàn)實(shí)意義及求解算法的可行性，現(xiàn)求解上海市楊浦區(qū)的一個(gè)案例，該案例包含18個(gè)備選垃圾中轉(zhuǎn)設(shè)施開設(shè)地和30個(gè)垃圾產(chǎn)生點(diǎn)。該案例設(shè)定數(shù)據(jù)如下：a）根據(jù)上海市楊浦區(qū)人民政府網(wǎng)站于2023年4月公布的第七次人口普查數(shù)據(jù)并結(jié)合《2022上海市楊浦區(qū)國(guó)民經(jīng)濟(jì)和社會(huì)發(fā)展統(tǒng)計(jì)公報(bào)》內(nèi)數(shù)據(jù)，得到楊浦區(qū)備選中轉(zhuǎn)設(shè)施及周邊各區(qū)域人口數(shù)量，位置分布圖如圖7所示；b）根據(jù)3.1節(jié)中設(shè)定的常量數(shù)值，將每人每天產(chǎn)生的垃圾量produce設(shè)定為1.2 kg，每噸垃圾每公里運(yùn)輸成本R為0.026 k/（t·km）；c）通過在三維直角坐標(biāo)系中利用向量?jī)?nèi)積來計(jì)算兩點(diǎn)之間的直線距離，使用式（8）進(jìn)行計(jì)算。其中R為地球半徑，兩點(diǎn)間的經(jīng)緯度坐標(biāo)表示為A（θ1，φ1）， B（θ2，φ2）。

使用本文提出的降階回溯算法對(duì)該案例進(jìn)行求解，求解結(jié)果如表5所示。在降階處理階段，使得問題規(guī)模由18個(gè)減少至14個(gè)，降階率為22.22%；進(jìn)入回溯搜索階段時(shí)，通過數(shù)學(xué)性質(zhì)、上下界比較和問題約束本身進(jìn)行剪枝，剪枝率為84.33%。綜上所述，此案例再次驗(yàn)證了本文算法在問題規(guī)?？s減與剪枝方面的有效性，同時(shí)也驗(yàn)證了該算法應(yīng)用于實(shí)際場(chǎng)景的可行性。

4 結(jié)束語

本文對(duì)垃圾回收中轉(zhuǎn)設(shè)施的選址問題進(jìn)行研究，首先根據(jù)實(shí)際情況對(duì)二級(jí)垃圾回收中轉(zhuǎn)設(shè)施選址問題進(jìn)行數(shù)學(xué)建模；其次證明一些問題相關(guān)的數(shù)學(xué)性質(zhì)，通過使用這些性質(zhì)在求解問題前和解二叉樹的過程中對(duì)問題進(jìn)行減小規(guī)模和剪枝操作，降低問題的求解難度，同時(shí)這些數(shù)學(xué)性質(zhì)也可用于設(shè)計(jì)該類型問題的其他算法；然后設(shè)計(jì)出分配子算法和上下界子算法；最后利用設(shè)計(jì)出的數(shù)學(xué)性質(zhì)和子算法構(gòu)建一個(gè)能減小問題規(guī)模且求得最優(yōu)解的降階回溯算法。

從理論分析可以看出，采用本文算法進(jìn)行求解時(shí)，不僅可以求得問題的最優(yōu)解，同時(shí)還可以在求解前降低問題的處理規(guī)模，加快求解速度。在示例2中，通過使用降階子算法在進(jìn)入二叉樹搜索前將待判斷的中轉(zhuǎn)設(shè)施數(shù)量由7個(gè)降到4個(gè)，時(shí)間復(fù)雜度由27下降到24；通過隨機(jī)算例分析驗(yàn)證本文算法在求解時(shí)的有效性，并通過算法對(duì)比分析進(jìn)一步驗(yàn)證本文算法的科學(xué)性；最后通過求解一個(gè)實(shí)際案例，體現(xiàn)出算法在實(shí)際應(yīng)用時(shí)的價(jià)值。本文設(shè)計(jì)的算法在回溯搜索時(shí)，相較于一般的精確算法，可以在回溯搜索的過程中對(duì)二叉樹進(jìn)行大量的剪枝，由此降低了時(shí)間復(fù)雜度，進(jìn)一步加快了問題的求解速度，同時(shí)也為使用精確算法求解該類問題提供了求解思路和方法。

參考文獻(xiàn)：

［1］Chen Yujin， Luo Anneng， Cheng Mengmeng， et al. Classification and recycling of recyclable garbage based on deep learning［J］.Journal of Cleaner Production ， 2023，414 ： 137558.

［2］Tamir A. Obnoxious facility location on graphs［J］.SIAM Journal on Discrete Mathematics，1991，4 （4）： 550－567.

［3］李海君， 張耀文， 楊月巧. 考慮回收—補(bǔ)償約束的衛(wèi)星城鎮(zhèn)生活垃圾中轉(zhuǎn)站選址研究［J］. 運(yùn)籌與管理， 2020， 29 （4）： 30－35. （Li Haijun， Zhang Yaowen， Yang Yueqiao. A study on the site selection of satellite urban domestic waste transfer stations considering recycling compensation constraints［J］.Operations Research and Management ， 2020， 29 （4）： 30－35.）

［4］李夢(mèng)琦， 耿秀麗. 基于兩階段方法的垃圾中轉(zhuǎn)站選址研究［J］. 軟件導(dǎo)刊， 202 20 （6）： 166－172. （Li Mengqi， Geng Xiuli. A study on the site selection of waste transfer stations based on a two stage method［J］.Software Guide ， 202 20 （6）： 166－172.）

［5］楊帆， 陶蘊(yùn)哲. “雙 M”導(dǎo)向下城市垃圾中轉(zhuǎn)站選址的經(jīng)濟(jì)與生態(tài)二維評(píng)估——以長(zhǎng)沙市為例［J］. 生態(tài)經(jīng)濟(jì)， 2020， 36 （5）： 80－84.（Yang Fan， Tao Yunzhe. Economic and ecological two dimensional evaluation of the site selection of urban waste transfer stations under the “dual M”guidance－taking Changsha city as an example［J］.Ecological Economy ， 2020，36 （5）： 80－84.）

［6］劉明輝. L縣農(nóng)村垃圾分類回收路徑優(yōu)化及中轉(zhuǎn)站選址研究［D］. 北京： 北京交通大學(xué)， 2021. （Liu Minghui. Research on the optimization of rural garbage classification and recycling paths and the location of transfer stations in L county［D］. Beijing： Beijing Jiaotong University， 2021.）

［7］Teran－Somohano Smith A E. Locating multiple capacitated semi－obnoxious facilities using evolutionary strategies［J］.Computers amp; Industrial Engineering ， 2019， 133 ： 303－316.

［8］韓曉冬， 孫也. 基于惡臭氣體擴(kuò)散數(shù)值模擬的垃圾中轉(zhuǎn)站選址［J］. 環(huán)境工程， 2021，39 （3）： 130－135. （Han Xiaodong， Sun Ye. Site selection of waste transfer stations based on numerical simulation of odor gas diffusion［J］.Environmental Engineering ， 202 39 （3）： 130－135.）

［9］Kalczynski P， Drezner Z. The obnoxious facilities planar p－median problem with variable sizes［J］.Omega ， 2022，111 ： 102639.

［10］Drezner Z， Kalczynski P， Salhi S. The planar multiple obnoxious facilities location problem： a Voronoi based heuristic［J］.Omega ， 2019，87 ： 105－116.

［11］Drezner T， Drezner Z， Scott C H. Location of a facility minimizing nuisance to or from a planar network［J］.Computers amp; Operations Research ， 2009， 36 （1）： 135－148.

［12］賈傳興， 彭緒亞， 劉國(guó)濤，等. 城市垃圾中轉(zhuǎn)站選址優(yōu)化模型的建立及其應(yīng)用［J］. 環(huán)境科學(xué)學(xué)報(bào)， 2006，26 （11）： 1927－1931. （Jia Chuanxing， Peng Xuy Liu Guotao， et al. Establishment and application of an optimization model for the location of urban waste transfer stations［J］.Journal of Environmental Science，2006，26 （11）： 1927－1931.）

［13］張晨， 劉勤明， 葉春明，等. 雙層規(guī)劃下考慮環(huán)境侵害的垃圾分揀中心選址研究［J］. 計(jì)算機(jī)應(yīng)用研究， 2020， 37 （12）： 3645－3649. （Zhang Chen， Liu Qinming， Ye Chunming， et al. A study on the site selection of garbage sorting centers considering environmental impact under double layer planning［J］.Application Research of Computers ， 2020， 37 （12）： 3645－3649.）

［14］錢頌迪. 運(yùn)籌學(xué)［M］. 北京：清華大學(xué)出版社， 2012： 318－320. （Qian Songdi. Operations research［M］. Beijing：Tsinghua University Press， 2012： 318－320.）

［15］夏正冬， 卜天明， 張居陽. SPFA算法的分析及改進(jìn)［J］. 計(jì)算機(jī)科學(xué)， 2014，41 （6）： 180－184，213. （Xia Zhengdong， Bu Tianming， Zhang Juyang. Analysis and improvement of SPFA algorithm［J］.Computer Science ， 2014，41 （6）： 180－184，213.）

［16］上海市發(fā)展改革委，市生態(tài)環(huán)境局，市經(jīng)濟(jì)信息化委，市商務(wù)委，市農(nóng)業(yè)農(nóng)村委， 市文化旅游局， 市市場(chǎng)監(jiān)管局， 市綠化市容局， 市機(jī)管局， 市郵政管理局關(guān)于印發(fā)《上海市關(guān)于進(jìn)一步加強(qiáng)塑料污染治理的實(shí)施方案》的通知［J］. 上海市人民政府公報(bào)， 2020 （24）： 9－14. （Notice of Shanghai Development and Reform Commission， Ecological Environment Bureau， Economic Information Techno－logy Commission， Commerce Commission， Agriculture and Rural Commission， Culture and Tourism Bureau， Market Supervision Bureau， Greening City Appearance Bureau， Machinery Management Bureau， Postal Administration Bureau on Issuing the“Implementation Plan for Further Strengthening Plastic Pollution Control in Shanghai”［J］.Shanghai Municipal Government Gazette ， 2020（24）： 9－14.）

［17］Luxen D， Vetter C. Real－time routing with OpenStreetMap data［C］//Proc of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York：ACM Press， 2011： 513－516.

［18］張木喜， 孫曉杰， 王亞搏，等. 廣東省生活垃圾處理方式變化趨勢(shì)及其原因［J］. 環(huán)境工程學(xué)報(bào)， 2021，15 （11）： 3651－3659. （Zhang Muxi， Sun Xiaojie， Wang Yabo， et al. Trends and causes of changes in domestic waste treatment methods in Guangdong province［J］.Journal of Environmental Engineering ， 202 15 （11）： 3651－3659.）

［19］孫智勇， 寧愛兵， 傅湯毅，等. 最小費(fèi)用充電站選址問題的分支定界算法［J］. 計(jì)算機(jī)應(yīng)用研究， 2022， 39 （1）： 80－83. （Sun Zhiyong， Ning Aibing， Fu Tangyi， et al. Branch and bound algorithm for minimum cost charging station location problem［J］.Application Research of Computers ， 2022， 39 （1）： 80－83.）

收稿日期：2023－08－17；修回日期：2023－10－11基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目（71401106）；上海市“管理科學(xué)與工程”高原學(xué)科建設(shè)項(xiàng)目

作者簡(jiǎn)介： 劉書傲（1999—），男，遼寧大連人，碩士研究生，主要研究方向?yàn)樗惴?、系統(tǒng)工程；寧愛兵（1972—），男，湖南邵東人，副教授，碩導(dǎo)，博士，主要研究方向?yàn)樗惴ㄔO(shè)計(jì)、系統(tǒng)工程（nab2022@126.com）；林道晗（1999—），男，山東淄博人，碩士研究生，主要研究方向?yàn)樗惴?、系統(tǒng)工程；劉睿石（2003—），男，河北石家莊人，本科生，主要研究方向?yàn)楣芾砜茖W(xué)；張惠珍（1979—），女，山西人，副教授，碩導(dǎo)，博士，主要研究方向?yàn)閮?yōu)化算法．