丁昱杰 張凱 張齡允 盧海鵬

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

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

中圖分類號(hào)：TP18 文獻(xiàn)標(biāo)識(shí)碼：A? 文章編號(hào)：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? 引? 言

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

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

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

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

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

1.1? 問題定義及描述

單位員工通勤合乘數(shù)學(xué)模型中成員均為企業(yè)公司內(nèi)部員工，默認(rèn)都擁有車輛，并且目的地都是公司，通過車輛和乘客的匹配，車主按順序接送其他員工抵達(dá)目的地，最終實(shí)現(xiàn)以合乘路徑最短、合乘成本最低為目標(biāo)的單位內(nèi)部間的合乘通勤。與傳統(tǒng)出行方式相比，有三點(diǎn)優(yōu)勢(shì)。第一，由于私家車一般為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)過站點(diǎn)的總距離，用戶總出行成本是指所有乘客搭乘車輛所產(chǎn)生的懲罰成本和合乘總費(fèi)用。合乘費(fèi)用受乘客起始出發(fā)點(diǎn)和車輛搭載乘客數(shù)的影響而變化。設(shè)定轉(zhuǎn)化系數(shù)α、β，建立目標(biāo)函數(shù)，以出行成本最小和總路徑最短為目標(biāo)。

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

（1）

約束條件：

（2）

（3）

（4）

（5）

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

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

2.1? 基本灰狼算法原理

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

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)前灰狼的位置向量；在整個(gè)迭代過程中a由2線性降到0；r1和r2是[0，1]中的隨機(jī)向量。

2.2? 遺傳灰狼算法融合

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

3? 算例分析

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

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

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

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

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

此模式采取互助友好的成本分?jǐn)偰Ｊ?，根?jù)合乘距離長(zhǎng)短分?jǐn)偪偝鲂谐杀?。再針?duì)合乘路徑優(yōu)化方案及同等需求條件下的非合乘方案，進(jìn)行乘客費(fèi)用的對(duì)比分析與討論，如表5所示。

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

4? 結(jié)? 論

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

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

參考文獻(xiàn)：

[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] 吳曉聲.出租車動(dòng)態(tài)共乘匹配優(yōu)化算法研究 [D].西安：長(zhǎng)安大學(xué)，2018.

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

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

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

收稿日期：2022-08-17