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

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

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

0 引言

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

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

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

1 數(shù)學模型構建

1.1 問題假設

數(shù)學模型構建的問題假設如下。

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

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

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

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

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

1.2 二次清運分析

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

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

圖1 回收車輛調(diào)度模型

1.3 問題描述

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

1.4 參數(shù)與符號定義

（1）符號定義

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

（2）定義決策變量

定義決策變量為：

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

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

1.5 模型建立

（1）目標函數(shù)

目標函數(shù)如下：

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

（2）約束條件

約束條件如下：

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

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

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

式（5）保證不能出現(xiàn)車輛最后的一個機柜還安排了一個機柜的情況。式（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 非線性約束向線性約束的轉(zhuǎn)化

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

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

數(shù)學模型中非線性約束向線性約束的轉(zhuǎn)化如下。

式（3）轉(zhuǎn)化為

式（12）轉(zhuǎn)化為

式（13）轉(zhuǎn)化為

2 實例分析

本文以東莞某環(huán)保科技公司為研究對象，選取該公司所負責松山湖片區(qū)附近的23個清運機柜進行路線規(guī)劃，該片區(qū)有1個清運中心和7輛可供使用的回收車輛，回收車輛的最大載重為250 kg，在達到最大載重時必須返回清運中心卸掉垃圾，機柜的標準回收量為40 kg，最大容量為50 kg。

2.1 實例數(shù)據(jù)處理

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

2.2 實驗結果分析

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

表1 實驗結果分析表

3 結束語

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