基于遺傳灰狼算法的員工通勤合乘路徑優化

丁昱杰 張凱 張齡允 盧海鵬

摘? 要：為了緩解小汽車過多使用造成的城市道路擁堵，達到整合交通資源、提高道路利用率的目的，以職住兩地周圍的通勤居民為研究對象，對員工通勤合乘路徑進行研究。以通勤合乘路徑最短、用戶總出行成本最少為優化目標建立目標函數，在保留灰狼算法（GWO）參數少和收斂速度快等優點的基礎上，融合遺傳算法（GA）中精英個體的變異操作防止灰狼算法（GWO）后期陷入局部。結果表明：遺傳灰狼算法（GAGWO）優化后的合乘路徑能有效降低私家車的空駛率以及司機和乘客的出行成本。

關鍵詞：公共交通；路徑優化；遺傳算法；灰狼算法

中圖分類號：TP18 文獻標識碼：A? 文章編號：2096-4706（2023）02-0112-04

Optimization of Personnel Commuting and Riding Path Based on Genetic Gray Wolf Optimizer

DING Yujie， ZHANG Kai， ZHANG Lingyun， LU Haipeng

（School of Automation， Nanjing University of Information Science & Techonlogy， Nanjing? 210044， China）

Abstract： In order to alleviate urban road congestion caused by excessive use of cars， to achieve the purpose of integrating traffic resources and improving road utilization. Taking the commuting residents around the two places as the research object， the research on the commuting and riding path of employees is carried out. The objective function is established with the shortest commuting and riding path and the least total travel cost of users as the optimization goal. On the basis of retaining the advantages of Gray Wolf Optimizer （GWO） with few parameters and fast convergence speed， it integrates the variation of elite individuals in Genetic Algorithm （GA）. The operation prevents the Gray Wolf Optimizer （GWO） from falling into local in the later stage. The results show that the commuting and riding path optimized by the Genetic Gray Wolf Optimizer （GAGWO） can effectively reduce the empty driving rate of private cars and the travel cost of drivers and passengers.

Keywords： public transportation; path optimization; genetic algorithm; Gray Wolf Optimizer

0? 引? 言

近年來，隨著我國城市化進程的不斷加快，國民收入和購買力也在不斷增長，私家車已經成為人們出行的主要交通工具。由此引發的城市道路擁堵、環境污染等負面問題已經成為制約國民經濟發展的瓶頸，在這種背景下，共享出行也就應運而生。共享出行是指人們無須自己購買車輛，以合乘方式與其他人共享車輛，在雙方具有相似出行需求的前提下，共同分擔道路費用的一種新型出行方式。早期的共享出行模式一般指的是出租車司機搭載多名乘客，這樣會導致路程繞行、乘客的出行時間成本增加等一系列的問題。

合乘出行作為一種新型的出行方式，對它的研究最早在國外興起。早在2004年，Roberto Baldacci等[1]針對大公司組織的一種拼車運輸服務進行研究，鼓勵員工在上下班的同時接送同事，盡量減少私家車上下班的次數，使共享最大化，路徑費用之和最小化。Timo Gschwind等[2]旨在尋找一組滿足車輛容量、時間窗、最大路徑持續時間和最大用戶乘車次數約束的最小費用路線。

國內對合乘出行的研究大多體現在合乘路徑優化。魏軍奎[3]通過聚類算法對出租車的OD數據進行空間聚類，劃分區域，統計需求。吳曉聲[4]通過使用出租車的GPS數據采用雙邊匹配算法進行動態路徑規劃。郭羽含等[5]采用隨機森林與變鄰域下降法求解考慮匹配可行性的長期車輛合乘問題。陳玲娟[6]采用演化策略算法解決帶時間窗約束的無換乘多車輛靜態拼車問題。

國內外學者針對共享出行的問題大多以單一的路徑最短或者以單一的運營成本為目標函數，并沒有綜合考慮路徑、成本、匹配率等問題，單一目標一定程度上能確保優化目標最優，但不能保證系統最優。鑒于上述問題，文章以單位同事通勤合乘為應用背景，綜合考慮合乘路徑、道路成本、懲罰成本等目標，側重討論在系統最優的前提下，加入軟時間窗、車輛容量、最大用戶乘車時間等約束，將目標匯總為一個加權總和目標函數，以多目標函數構建模型，采用多種不同的智能優化算法對比驗證，可以提高單位員工通勤車輛單車乘坐人數、降低車輛空駛率、緩解交通擁堵，為單位員工通勤合乘出行模式提供理論支持。

1? 單位員工通勤合乘數學模型

1.1? 問題定義及描述

單位員工通勤合乘數學模型中成員均為企業公司內部員工，默認都擁有車輛，并且目的地都是公司，通過車輛和乘客的匹配，車主按順序接送其他員工抵達目的地，最終實現以合乘路徑最短、合乘成本最低為目標的單位內部間的合乘通勤。與傳統出行方式相比，有三點優勢。第一，由于私家車一般為5座小汽車，最大載客量為4人，考慮舒適性，最大載客量設為3人。第二，車主和乘客的目的地相同，并且出行路線相似或順路。第三：車主和乘客共同分擔出現成本。合乘服務示意圖如圖1所示。

1.2? 變量及參數設置

模型中的變量及參數如表1所示。

1.3? 數學模型

單位員工通勤合乘問題以合乘總路徑最短、用戶總出行成本最少為優化目標。合乘總路徑是指所有車輛經過站點的總距離，用戶總出行成本是指所有乘客搭乘車輛所產生的懲罰成本和合乘總費用。合乘費用受乘客起始出發點和車輛搭載乘客數的影響而變化。設定轉化系數α、β，建立目標函數，以出行成本最小和總路徑最短為目標。

目標函數：

（1）

約束條件：

（2）

（3）

（4）

（5）

其中，約束（2）為車容量約束，最大載客量設為3人，初始車容（除司機以外的乘客數量）為0。約束（3）為時間窗量口約束：司機需在乘客規定上車時間內到達上車點。約束（4）為乘客合乘成本約束：保證乘客合乘費用比單乘費用低。約束（5）為司機成本約束，保證司機的出行至少要小于非合乘時的出行成本。

2? 遺傳灰狼算法融合求解

2.1? 基本灰狼算法原理

灰狼算法是一種新型的群智能啟發式優化算法，GWO通過模擬灰狼群體捕食行為，基于狼群群體協作的機制來達到優化的目的。GWO優化過程模仿了灰狼的跟蹤、包圍和攻擊獵物等步驟，社會等級分層是指選取每代狼群中個體適應度最高的三匹狼指導完成GWO優化過程。包圍獵物指灰狼捜索獵物時會逐漸地接近獵物并包圍它。狩獵是指在算法優化過程中，挑選出目前狼群中的最好三只灰狼（α、β和δ），β主要負責協助領導者α進行決策，δ聽從α和β的決策命令，根據位置信息來更新其他搜索代理的位置。灰狼隨機地在靠近獵物的空間內做出移動，以逐漸接近最優解。灰狼算法的位置更新公式為：

D=C×XP（t）-X（t）? ? ? ? ? ? ? ? ? ? ? ? ? ?（6）

X（t+1）=XP（t）-A×D? ? ? ? ? ? ? ? ? ? ? ? ?（7）

A=2a×r1-a? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（8）

C=2r2? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（9）

其中：t表示當前迭代次數，A和C表示協同系數向量，XP表示獵物的位置向量；X（t）表示當前灰狼的位置向量；在整個迭代過程中a由2線性降到0；r1和r2是[0，1]中的隨機向量。

2.2? 遺傳灰狼算法融合

灰狼算法具有控制參數少、收斂速度快等優點，但也存在局限性，例如全局搜索能力不足、容易早熟收斂、易陷入局部最優、優秀基因未充分利用等。為解決上述灰狼算法的不足，融合遺傳算法（GA），混合遺傳灰狼算法原理是基于灰狼的社會等級和狩獵機制進行多次優化迭代，挑選出狼群中三只最優個體，由它們帶領其余狼朝著搜索空間的最優方向移動。在生成新的子代狼群后，引入遺傳算法的最佳保留選擇策略，增加了將父代種群中優良的個體遺傳到下一代的概率，并且不遭到破壞，為了防止算法迭代后期出現局部最優，引入了變異算子對種群中的精英個體進行變異操作，使得種群的多樣性得到豐富，使得全局搜索能力提高，相比遺傳算法、混合算法收斂速度更快。遺傳灰狼融合算法流程圖如圖2所示。

3? 算例分析

隨機生成的20名同一家單位的員工，其中5名為司機，另外15名為乘客，他們的終點都是公司（節點編號75），默認到達時間窗一致。員工需求點信息如表2所示，包括乘客編號、起點、出發時間窗。司機出行信息如表3所示，包括車輛編號、起點、出發時間窗和車輛的原始路徑。該實驗假設初始乘客數均為0人，車輛的平均時速為45 km/h，合乘車輛的起步距離2 km，起步價8元，超過起步距離計價為2.2 元/km。額定載客量均為4人，但考慮舒適性，規定車的最大載客量為3人，車輛費率與最大載客量相關，若最大載客量為3人，則設置為0.7，若最大載客量為2人，則設置為0.8。超時的懲罰系數a設置為1，成本損失的懲罰系數b設置為0.5。車輛匹配范圍為5 km，初始種群數量為30、種群進化迭代次數為100次，交叉概率Pc=0.8，變異概率Pm=0.1，收斂因子a隨迭代次數的遞增由2動態降低至0。

為了驗證多車輛合乘問題的模型和算法的有效性，選取某市局部地區的交通路網節點圖為背景，共有個90節點。每個節點的距離已知，如果兩個節點之間不連通，則該兩點之間距離為∞。車輛的原始路徑如圖3所示。

通過借助MATLAB工具針對本文設計的遺傳灰狼優化算法（GAGWO）進行編程，并與GA、PSO、GWO算法對比，得到適應度函數趨于穩定最終結果，如圖4所示。

根據圖4可以發現，對比不同算法，GAGWO優化后的目標函數在迭代32次以后趨于穩定并且最小，其優化后的合乘路徑如圖5所示。

具體的合乘行駛路線如表4所示。以車輛1為例，從起點26出發，途經10、34節點，到達37節點搭載員工1，再經過36、35、45、55節點，到達3節點搭載員工10，節點44搭載員工7，最后依次經過67、68到達終點單位75。

此模式采取互助友好的成本分攤模式，根據合乘距離長短分攤總出行成本。再針對合乘路徑優化方案及同等需求條件下的非合乘方案，進行乘客費用的對比分析與討論，如表5所示。

由表5中的數據可以看出，通過單位員工間的車輛合乘，員工通勤合乘出行費用小于非合乘費用，最大化了乘客的利益，在司機成本方面，合乘方案下的司機出行成本均小于非合乘方案下的。說明單位員工合乘方案能夠充分保障車主的利益并調動其提供合乘服務的積極性。單位有車員工搭乘其他員工的車輛出行，能夠減少上路車輛，降低車輛的空駛率，從而緩解城市道路擁擠的現狀。

4? 結? 論

文章以同一單位員工為研究對象，建立了帶軟時間窗的多車輛合乘問題的數學模型，從合乘路徑最短和出行成本最低的角度分析了多目標下的單位員工通勤合乘，滿足車輛容量，車主和乘客時間出行時間窗和成本等約束條件。并設計融合遺傳算法（GA）和灰狼算法（GWO）算法，給出了求解最優解搜索的運算步驟。運用MATLAB進行算例分析，對比不同算法，驗證了融合算法的有效性，最后通過對比分析合乘方案較非合乘方案，在私家車資源節省、合乘乘客成本降低與車主出行成本降低等方面具有明顯優勢。

文章提出的單位通勤合乘措施需要對實施細節與可能遇到的問題進行具體考察，模型尚未考慮現實生活中紅綠燈、汽車啟停延誤以及城市路網道路擁堵導致的額外時間成本等情況，還需進一步完善。并且由于調查資源與研究條件所限，案例分析中所研究的路網規模與合乘出行需求規模均較小，需在后續應用研究中進行進一步探討。

參考文獻：

[1] BALDACCI R，MANIEZZO V，MINGOZZI A. An Exact Method for the Car Pooling Problem Based on Lagrangean Column Generation [J].Operations Research，2004，52（3）：422-439.

[2] GSCHWIND T，DREXL M. Adaptive Large Neighborhood Search with a Constant-Time Feasibility Test for the Dial-a-Ride Problem [J].Transportation Science，2019，53（2）： 480–491.

[3] 魏軍奎.基于軌跡大數據的出租車合乘路徑優化 [D].蘭州：蘭州交通大學，2020.

[4] 吳曉聲.出租車動態共乘匹配優化算法研究 [D].西安：長安大學，2018.

[5] 郭羽含，胡德甲.基于隨機森林與變鄰域下降的車輛合乘求解 [J].計算機工程與應用，2020，56（13）：243-253.

[6] 陳玲娟，寇思佳，柳祖鵬.網約拼車出行的乘客車輛匹配及路徑優化 [J].計算機與現代化，2021（07）：6-11.

作者簡介：丁昱杰（1997—），男，漢族，江蘇鹽城人，碩士在讀，研究方向：智慧交通。

收稿日期：2022-08-17