基于遺傳灰狼算法的員工通勤合乘路徑優(yōu)化

丁昱杰 張凱 張齡允 盧海鵬

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

關(guān)鍵詞：公共交通；路徑優(yōu)化；遺傳算法；灰狼算法

中圖分類號：TP18 文獻標(biāo)識碼：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? 引? 言

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

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

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

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

1? 單位員工通勤合乘數(shù)學(xué)模型

1.1? 問題定義及描述

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

1.2? 變量及參數(shù)設(shè)置

模型中的變量及參數(shù)如表1所示。

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

單位員工通勤合乘問題以合乘總路徑最短、用戶總出行成本最少為優(yōu)化目標(biāo)。合乘總路徑是指所有車輛經(jīng)過站點的總距離，用戶總出行成本是指所有乘客搭乘車輛所產(chǎn)生的懲罰成本和合乘總費用。合乘費用受乘客起始出發(fā)點和車輛搭載乘客數(shù)的影響而變化。設(shè)定轉(zhuǎn)化系數(shù)α、β，建立目標(biāo)函數(shù)，以出行成本最小和總路徑最短為目標(biāo)。

目標(biāo)函數(shù)：

（1）

約束條件：

（2）

（3）

（4）

（5）

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

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

2.1? 基本灰狼算法原理

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

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

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

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

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

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

2.2? 遺傳灰狼算法融合

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

3? 算例分析

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

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

通過借助MATLAB工具針對本文設(shè)計的遺傳灰狼優(yōu)化算法（GAGWO）進行編程，并與GA、PSO、GWO算法對比，得到適應(yīng)度函數(shù)趨于穩(wěn)定最終結(jié)果，如圖4所示。

根據(jù)圖4可以發(fā)現(xiàn)，對比不同算法，GAGWO優(yōu)化后的目標(biāo)函數(shù)在迭代32次以后趨于穩(wěn)定并且最小，其優(yōu)化后的合乘路徑如圖5所示。

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

此模式采取互助友好的成本分?jǐn)偰Ｊ剑鶕?jù)合乘距離長短分?jǐn)偪偝鲂谐杀尽Ｔ籴槍铣寺窂絻?yōu)化方案及同等需求條件下的非合乘方案，進行乘客費用的對比分析與討論，如表5所示。

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

4? 結(jié)? 論

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

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

參考文獻：

[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] 魏軍奎.基于軌跡大數(shù)據(jù)的出租車合乘路徑優(yōu)化 [D].蘭州：蘭州交通大學(xué)，2020.

[4] 吳曉聲.出租車動態(tài)共乘匹配優(yōu)化算法研究 [D].西安：長安大學(xué)，2018.

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

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

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

收稿日期：2022-08-17