基于二次清運的回收車輛路徑研究*

李志滔，方雄發，吳雪菲，許家瑋，張智聰

（東莞理工學院機械工程學院，廣東東莞 523808）

0 引言

隨著城鎮化的快速發展，一些城市出現了智能垃圾回收機柜，機柜垃圾的清運問題也日益突出，規劃車輛行駛路徑成為了公司降低經營成本的重要途徑之一。在車輛回收垃圾的過程中，若機柜的回收量達到其容量前還沒有被清運時，就不能及時為居民提供服務，會降低居民對服務的滿意度；若回收車輛到達的時間早于機柜達到標準垃圾量的時間，車輛就得等待或者提前清理垃圾，如果等待時間過長，則不利于公司的運營，如果清理時間過早，則會影響后面的工作安排。當前，大多數公司的清運策略是員工憑借對道路的熟悉度來確定清運路徑[1]，而經過科學規劃的路徑可以減少車輛行駛的總路程，降低經營成本。因此，科學的路徑規劃是解決清運成本與清理機柜準時性的重要任務。

資源回收的車輛調度是現代化物流系統的重要環節之一，是指調度中心根據不同地方資源的產生量，及時派送車輛對該地方的資源進行回收并回到起點的過程。VRPTW問題的求解方法大體可分為精確算法和啟發式算法，許多學者對VRP問題的復雜性進行分析，得出幾乎所有類型的VRP問題都是NP－hard問題[2]。賈定芳[3]在硬時間窗的前提下，構建以車輛行駛路徑最短為目標的模型，解決配送服務，平衡配送成本和顧客滿意度這兩個目標解決了生鮮外賣配送路徑規劃問題[4]；陳婷[5]改進遺傳算法對快遞的VRPTW模型進行求解；陳梅[6]在計算遺傳算法的過程中使用禁忌搜索算法對城市環衛車調度進行優化求解；牛群[7]針對帶硬時間窗車輛路徑問題，提出了一種改進型煙花算法進行求解，該算法能夠利用信息交互進行資源分配；在二次調度問題的研究上，李沖等[8]研究了貨物配送中在保證時間窗的前提下，需要同一輛車進行二次或多次配送；楊天杰[9]優化成品油二次物流配送車輛調度問題，減少配送成本。

本文以車輛行駛的總路程為目標進行優化，結合第二次回收車輛調度的特點，在硬時間窗的約束下，建立綜合考慮兩次清運的混合整數規劃模型進行求解。

1 數學模型構建

1.1 問題假設

數學模型構建的問題假設如下。

（1）回收車輛在兩機柜間行駛時間與距離具有一定的線性關系，忽略堵車等特殊情況。

（2）每個機柜的回收量與時間具有一定的線性關系，忽略節日、惡劣天氣等特殊情況。

（3）兩機柜間距離和所需的行駛時間以高德地圖推薦的路線為依據。

（4）每輛回收車輛的型號相同、油量充足。

（5）具體清運過程的時間忽略。

1.2 二次清運分析

根據歷史數據顯示，每個機柜的回收量與時間成強正相關，在數學模型的建立過程中可以認為回收量與時間具有線性關系。當機柜被清運完成一次后，其回收量在本工作日內再次達到最大回收量時，必須安排車輛對該機柜進行第二次清運。第一次回收車輛調度模型是一個帶時間窗的VRP模型，其局限性是沒有考慮全局的車輛調度情況，以至于在整個工作日內所有車輛的總里程極大可能不是最優的。因此，綜合分析第一次和第二次回收車輛調度，才能在整個車輛調度中找到車輛總里程的最小值。

在模型建立的過程中，需要求出第一次實際清運的時間，需二次清運機柜的時間窗是該機柜第一次清運時間窗與第一次實際清運時間之和，第二次清運模型的約束建立與第一次的模型具有相似性?；厥哲囕v調度模型簡圖如圖1所示。

圖1 回收車輛調度模型

1.3 問題描述

清運中心C共有K輛回收車輛，每輛車的最大載重為Q kg，其負責的片區共需清運L次，包括第一次和第二次清運。第一次回收車輛必須在機柜達到標準回收量的時刻t1i和最大回收量的時刻t2i之間到達機柜；第二次回收車輛必須在機柜第二次達到標準回收量時刻s1i和最大回收量時刻s1i之間到達?；厥哲囕v統一從清運中心C出發，在達到最大載重Q前返回清運中心卸掉可回收資源。每條清運路徑的總回收量應小于或等于回收車輛的最大載重。

1.4 參數與符號定義

（1）符號定義

i(1≤i≤L)為機柜序號（包括第一次和第二次清運時機柜的序號，其中第一次清運的機柜序號在前，緊接是第二次清運的機柜序號，同一機柜的二次清運序號相差L－N）；j(1≤j≤J)為機柜在其回收車輛j所清運的所有機柜中的排序號（需要事先估算J值，J值為每輛車清運的機柜數量的最大值）；k(1≤k≤K)為車輛序號（K值為可能使用車輛的最大數目，需要事先估算K值）；Q為回收車輛的最大載重；J為每輛車清運的機柜的最大數目；K為可能使用車輛的最大數目；N為需要進行第二次清運機柜的數量；ai、bi分別為回收量與時間線性方程的斜率和截距；di1,i2為機柜間距離；gi為從清運中心去到各個機柜的距離；fi為從各個機柜回到清運中心的距離；Ti1,i2為前往下一個機柜需要行走的時間；t1i、t2i分別為機柜垃圾量到達標準回收量和最大容量的時刻；M為一個很大的數（比如100 000）。

（2）定義決策變量

定義決策變量為：

例如，x2,3,5＝1為第2輛車清運的第3個機柜是機柜5。

s1i、s2i分別為二次清運機柜垃圾量到達標準回收量和最大容量的時刻；sk,j為第k輛車到達第j個清運位置（機柜）的時刻；yk,i為車輛k清運回收柜的數量。

1.5 模型建立

（1）目標函數

目標函數如下：

從清運中心出發，回收車輛完成收集后再回到清運中心的總里程最短。

（2）約束條件

約束條件如下：

式（1）～（2）為所有機柜都要被清運。

式（3）為清運路程中所有機柜回收量之和不超過回收車輛的最大載重量。

式（4）為每輛車每個清運排序號最多只能清運一個機柜。

式（5）保證不能出現車輛最后的一個機柜還安排了一個機柜的情況。式（6）保證了車輛k清運的第j個、第j＋1個機柜分別為i1、i2。

式（7）～（8）判斷第k輛車的第j個機柜是否是終點。

式（9）為第k輛車到達第j機柜的時間不大于第k輛車到達第j＋1機柜的時間。

式（10）保證車輛k清運的第j個、第j＋1個機柜不是i1、i2（i1＝i2）。

式（11）為第一次清運的時間窗約束：車輛到達第j個、第j＋1個機柜時，必須在機柜回收量到達標準回收量的時刻與到達最大容量的時刻之間到達。

式（12）～（13）分別為二次清運機柜垃圾量到達標準回收量和最大容量的時刻。

式（14）～（15）為第二次清運的時間窗約束：車輛到達第j個、第j＋1個機柜時，必須在機柜回收量到達標準回收量的時刻與到達最大容量的時刻之間到達。

1.6 非線性約束向線性約束的轉化

日常生活中的優化問題普遍是非線性規劃問題。非線性規劃問題是指目標方程或約束中存在至少的非線性函數的最優化規劃問題。大多數約束最優化的方法可通過將有約束問題轉化為無約束問題求解。馮迎春[10]介紹了解決約束優化問題的算法主要有可行方向法、L－N法、逐步二次規劃法等。

在運籌優化中，通過引入大M法把非線性約束轉化為線性約束的方法，是解決非線性問題的常用方法。非線性規劃向線性規劃轉化的模型可以較大地減少求解模型最優解的時間。

數學模型中非線性約束向線性約束的轉化如下。

式（3）轉化為

式（12）轉化為

式（13）轉化為

2 實例分析

本文以東莞某環?？萍脊緸檠芯繉ο?，選取該公司所負責松山湖片區附近的23個清運機柜進行路線規劃，該片區有1個清運中心和7輛可供使用的回收車輛，回收車輛的最大載重為250 kg，在達到最大載重時必須返回清運中心卸掉垃圾，機柜的標準回收量為40 kg，最大容量為50 kg。

2.1 實例數據處理

通過對該公司歷史數據的處理，得到23個機柜間的行駛路程、清運中心與機柜間的行駛路程、回收車輛在機柜間的行駛時間、機柜回收量達到40～50 kg的預測時間點和回收量與時間的回歸方程的斜率和截距。再根據回歸方程計算出需要進行二次清運的機柜，在原數據基礎上，對其進行相似的處理。在機柜編號的過程中，需二清運機柜的第一次編號分別為1，2，…，7，緊接的是不需二次清運機柜的編號為8，9，…，23，再接著的是需二清運機柜的第二次編號為24，25，…，30，即編號1～7與編號24～30的7個機柜對應著的是同一個機柜。

2.2 實驗結果分析

ILOG OPL軟件編程求解結果顯示，在硬時間約束下，清運中心只需6輛回收車輛就能完成包括二次清運在內的工作，每輛車分配的任務均勻，而多出的一輛車可以減少一位駕駛員，降低雇傭成本。實驗所求出的結果如表1所示，表中括號內外的編號表示同一個機柜。

表1 實驗結果分析表

3 結束語

本文研究了硬時間窗約束下回收車輛調度問題，以多車輛的兩次清運為研究對象，以行駛路程最短為目標，構建混合整數規劃數學模型，實現了對回收車輛的系統性調度。實驗運行過程中，非線性約束向線性約束的轉化，較大地節省了求解時間。結果表明，松山湖片區的清運路徑得到系統化的規劃，同時確定了最優回收車輛數量和滿足時間約束條件下的最短行駛路徑。而對于大規模數據的處理方面，可以繼續開展智能算法方面的研究。