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

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

中圖分類號：TP301.6文獻標(biāo)志碼： A文章編號：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 引言

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

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

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

1 問題描述

1.1 問題介紹

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

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

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

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

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

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

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

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

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

性質(zhì)1

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

證明

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

性質(zhì)2

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

證明

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

性質(zhì)3

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

證明

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

性質(zhì)4

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

證明

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

性質(zhì)5

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

證明

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

性質(zhì)6

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

證明

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

性質(zhì)7

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

證明

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

性質(zhì)8

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

證明

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

性質(zhì)9

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

證明

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

性質(zhì)10

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

證明

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

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

證明

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

性質(zhì)12

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

證明

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

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

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

2.1 分配子算法

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

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

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

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

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

（a）構(gòu)建超級源點S和超級匯點T。

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

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

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

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

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

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

示例1的分配過程簡述如下：

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

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

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

2.2 上界子算法

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

a）初始化集合Fup={}，同時滿足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進行更新。

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 下界子算法

求解該問題的下界，選取任何一個可行解對應(yīng)的目標(biāo)函數(shù)值即可作為該問題的下界。本文使用1.4節(jié)所提出的數(shù)學(xué)性質(zhì)，先對該問題進行降階，再根據(jù)提出的下界子算法求得問題的下界，混合使用數(shù)學(xué)性質(zhì)和貪心算法所得到的下界優(yōu)于絕大部分可行解。下界子算法具體步驟如下：a）初始化集合Flow ={}，同時滿足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判斷此時是否無解，若無解則下界暫定為+∞，下界子算法結(jié)束；使用性質(zhì)2進行更新。

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

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

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

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

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

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

j） 檢查集合Flow，若在集合Flow中存在中轉(zhuǎn)設(shè)施fj有N（fj）=，則將該中轉(zhuǎn)設(shè)施加入集合F5；在優(yōu)化完成后計算下界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ì)對問題中回收中轉(zhuǎn)設(shè)施的開設(shè)情況進行判斷，減小問題規(guī)模。降階算法步驟如下：

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

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

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

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

2.5 回溯子算法

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

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

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

c）執(zhí)行FF5= FF5＼fj，F(xiàn)F1= FF1∪fj，利用性質(zhì)1、7和11判斷此情況下是否無解，若無解則進行左子樹剪枝，轉(zhuǎn)至步驟d）；否則調(diào)用上界子算法計算上界ub。當(dāng)滿足ub≠None且ub≥lb， 此時表明可能存在優(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的條件，若無解則進行右子樹剪枝，轉(zhuǎn)至步驟f）；否則調(diào)用上界子算法計算當(dāng)前節(jié)點處上界ub，當(dāng)滿足ub≠None且ub≥lb，此時表明可能存在優(yōu)于當(dāng)前下界的解，使用性質(zhì)6得出加入集合FF0中的中轉(zhuǎn)設(shè)施集合Ftemp_1，使用性質(zhì)4得出一定開設(shè)的中轉(zhuǎn)設(shè)施集合Ftemp_2，將已分配完全的產(chǎ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é)束時，目標(biāo)函數(shù)最優(yōu)值best_q即為問題的最優(yōu)解，F(xiàn)best為對應(yīng)的回收中轉(zhuǎn)設(shè)施點集合。

2.6 主算法

a）根據(jù)垃圾產(chǎ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)用降階子算法，對問題進行降階；若降階子算法結(jié)束后F＼F5發(fā)生變化，則轉(zhuǎn)至d）重新計算下界，并使用性質(zhì)2進行更新；否則轉(zhuǎn)至f）。

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

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

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

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

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

3 示例分析

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

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

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

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

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對問題進行降階，返回懸掛點并執(zhí)行F1 ={ f4}，F(xiàn)5=F ＼F1 ={ f1，f2，f3，f5，f6，f7}。

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

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

（d）使用性質(zhì)9對該問題進行降階，當(dāng)計算至設(shè)施f6時，求得上界值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對圖進行更新。

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 隨機算例分析

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

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

3.3 算法對比分析

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

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

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

3.4 案例研究

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

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

4 結(jié)束語

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

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

參考文獻：

［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］李海君， 張耀文， 楊月巧. 考慮回收—補償約束的衛(wèi)星城鎮(zhèn)生活垃圾中轉(zhuǎn)站選址研究［J］. 運籌與管理， 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］李夢琦， 耿秀麗. 基于兩階段方法的垃圾中轉(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］楊帆， 陶蘊哲. “雙 M”導(dǎo)向下城市垃圾中轉(zhuǎn)站選址的經(jīng)濟與生態(tài)二維評估——以長沙市為例［J］. 生態(tài)經(jīng)濟， 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］韓曉冬， 孫也. 基于惡臭氣體擴散數(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］賈傳興， 彭緒亞， 劉國濤，等. 城市垃圾中轉(zhuǎn)站選址優(yōu)化模型的建立及其應(yīng)用［J］. 環(huán)境科學(xué)學(xué)報， 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］. 計算機應(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］錢頌迪. 運籌學(xué)［M］. 北京：清華大學(xué)出版社， 2012： 318－320. （Qian Songdi. Operations research［M］. Beijing：Tsinghua University Press， 2012： 318－320.）

［15］夏正冬， 卜天明， 張居陽. SPFA算法的分析及改進［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)濟信息化委，市商務(wù)委，市農(nóng)業(yè)農(nóng)村委， 市文化旅游局， 市市場監(jiān)管局， 市綠化市容局， 市機管局， 市郵政管理局關(guān)于印發(fā)《上海市關(guān)于進一步加強塑料污染治理的實施方案》的通知［J］. 上海市人民政府公報， 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］張木喜， 孫曉杰， 王亞搏，等. 廣東省生活垃圾處理方式變化趨勢及其原因［J］. 環(huán)境工程學(xué)報， 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］孫智勇， 寧愛兵， 傅湯毅，等. 最小費用充電站選址問題的分支定界算法［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基金項目：國家自然科學(xué)基金資助項目（71401106）；上海市“管理科學(xué)與工程”高原學(xué)科建設(shè)項目

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