智慧城市理念下基于多目標(biāo)優(yōu)化與遺傳算法的公交車高平峰調(diào)度方案

陳泓宇 馮雅楠 張利艷 孫雅楠 汪玉明

（長(zhǎng)春理工大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，吉林 長(zhǎng)春 130022）

在總結(jié)和分析前人對(duì)公共交通調(diào)度方案的研究方法后，發(fā)現(xiàn)其對(duì)人流高平峰區(qū)段的劃分依據(jù)比較模糊，在此基礎(chǔ)上增加閾值計(jì)算模型，以長(zhǎng)春市某一條線路為例，分別建立了乘客滿意度模型和公交運(yùn)營(yíng)公司滿意度模型，以公交車在高峰期與平峰期的車輛運(yùn)行的滯后性為突破口，針對(duì)在高峰末期發(fā)出的車輛途中進(jìn)入平峰期所造成的資源浪費(fèi)情況，以及平峰末期發(fā)出的車輛途中進(jìn)入高峰期所造成的市民候車時(shí)間長(zhǎng)的情況，設(shè)計(jì)了一個(gè)考慮高平峰過渡期的基于遺傳算法的公交車轉(zhuǎn)換調(diào)度方案。為保證多目標(biāo)處理結(jié)果的準(zhǔn)確性和高效率性，本研究采用遺傳算法對(duì)目標(biāo)函數(shù)進(jìn)行求解。

一、數(shù)學(xué)模型的建立

（一）基本假設(shè)

公交調(diào)度的數(shù)學(xué)模型主要是對(duì)實(shí)際公交調(diào)度問題的抽象和概況，因此不可能完全考慮到所有的復(fù)雜外部因素，必須合理的對(duì)外部因素做相應(yīng)的限制，公交車的調(diào)度模型，具有復(fù)雜和受外部影響因素多的特點(diǎn)，為建立公交車發(fā)車間隔的雙層優(yōu)化模型，需做如下基本假設(shè)：①公交車輛為同一車型，且公交車運(yùn)行情況良好；②乘客到達(dá)站點(diǎn)數(shù)量服從均勻分布；③乘客上車的時(shí)間可以忽略不計(jì)；④公交車只運(yùn)行一條公交線路上，且只考慮單程車運(yùn)行；⑤乘客消耗的單位時(shí)間費(fèi)用是固定值；⑥公交車輛單位乘次運(yùn)營(yíng)成本是固定值；⑦假設(shè)公交車線路票價(jià)實(shí)行統(tǒng)一制，1 元/人次；⑧假設(shè)公交車發(fā)車間隔取1 的整數(shù)倍，忽略細(xì)微誤差；⑨假設(shè)公交車乘客的等車時(shí)間與公交公司的發(fā)車間隔存在一定的函數(shù)關(guān)系；⑩假設(shè)車輛磨損、車輛故障和因駕駛員個(gè)人因素導(dǎo)致的時(shí)間誤差忽略不計(jì)。

（二）目標(biāo)函數(shù)及設(shè)計(jì)步驟

在實(shí)際的公交調(diào)度中，公交車輛調(diào)度優(yōu)化的目標(biāo)函數(shù)，需要從乘客利益和公交公司利益的角度來考慮，從公交公司的角度，需盡量大的發(fā)車間隔以減少發(fā)車次數(shù)，從而降低運(yùn)營(yíng)成本來提高公司的收入，從乘客的角度，需要盡量小的發(fā)車間隔，以最大限度地降低因等車和換乘帶來的交通費(fèi)用損失。方案設(shè)計(jì)的具體步驟為：

步驟 1：模型假設(shè)。根據(jù)公交現(xiàn)狀數(shù)據(jù)，對(duì)模型進(jìn)行初步假設(shè)，提出針對(duì)公交公司和乘客兩者的分治策略；

步驟 2：建立模型。基于統(tǒng)計(jì)數(shù)據(jù)，進(jìn)行模型訓(xùn)練，進(jìn)而構(gòu)建多目標(biāo)優(yōu)化模型構(gòu)建；

步驟 3：多目標(biāo)優(yōu)化設(shè)計(jì)。確定影響因素以及經(jīng)驗(yàn)數(shù)值，并結(jié)合構(gòu)架完成的模型結(jié)果，構(gòu)建多目標(biāo)體系；

步驟 4：目標(biāo)函數(shù)求解。根據(jù)多目標(biāo)模型，利用遺傳算法對(duì)目標(biāo)函數(shù)進(jìn)行求解；

步驟 5：檢驗(yàn)優(yōu)化結(jié)果是否為最優(yōu)解，若達(dá)到優(yōu)化結(jié)果，則輸出優(yōu)化結(jié)果，否則返回步驟 1。

（三）模型的建立

1.乘客滿意度模型

建立以發(fā)車間隔為變量的乘客出行成本模型，建立發(fā)車間隔和乘客等待時(shí)間 2者之間的函數(shù)關(guān)系，將時(shí)間成本轉(zhuǎn)化為經(jīng)濟(jì)成本，以滿足乘客出行費(fèi)用最少的目標(biāo)，乘客滿意度模型如下式 1 所示:

式中:Cp是公交車乘客的出行成本；Ce為站點(diǎn)乘客的等車成本；Cw是公交車行駛路途中的乘客時(shí)間成本；ue為單位乘客時(shí)間成本；uw是單位乘車時(shí)間成本；qij為第i輛公交車停靠在第j站時(shí)上車的乘客數(shù)；Qij是第 輛公交車?？吭诘趈站時(shí)車上的乘客總數(shù)量；S為乘客等待時(shí)間，假設(shè)為發(fā)車間隔的一半，；0T 為所研究的公交線路起點(diǎn)和終點(diǎn)路程的平均行程時(shí)間；Sij是第i輛公交車在第j站點(diǎn)的停留時(shí)間；pj為公交車乘客在j站點(diǎn)的平均下車比例；Dj是在站點(diǎn)j的乘客下車數(shù)量。

2.公交運(yùn)營(yíng)公司滿意度模型

從企業(yè)運(yùn)營(yíng)總成本的角度出發(fā)，建立基于公交車輛運(yùn)營(yíng)成本的公司滿意度模型?？勺冞\(yùn)營(yíng)成本和固定運(yùn)營(yíng)成本構(gòu)成了公交公司運(yùn)營(yíng)總成本，研究固定成本意義不大，基于此，可變成本則是下層規(guī)劃模型研究的關(guān)鍵所在，公交公司全天的發(fā)車數(shù)量和全天運(yùn)營(yíng)時(shí)長(zhǎng)決定了可變成本的多少，公司滿意度模型如下式 2 所示:

式中:Cg為公交公司車輛運(yùn)營(yíng)的可變成本；ug是公交車輛的運(yùn)營(yíng)成本；n為某條公交線路全天發(fā)車總數(shù)量；tg是公交車運(yùn)營(yíng)時(shí)段內(nèi)的運(yùn)營(yíng)總時(shí)長(zhǎng)。

3.雙層優(yōu)化模型

公交車在不同時(shí)間段內(nèi)的發(fā)車間隔是公共交通總公司制定公交車時(shí)刻表的關(guān)鍵依據(jù)，公交公司和乘客的利益存在一種反比例非線性關(guān)系，為了權(quán)衡兩者的利益關(guān)系，建立基于公交車發(fā)車間隔的雙層規(guī)劃模型，使得雙方利益最大化。整合模型如下式3所示:

式中:O為公交公司和乘客雙方的總成本；v是設(shè)定的權(quán)重系數(shù)，取值介于［0，1］之間；Cp和Cg意義同上。

約束條件:fmin≤f≤fmax，f為發(fā)車間隔，城市規(guī)范發(fā)車間隔取值介于［3，30］之間，單位:分鐘（(min)。

二、模型的求解

（一）遺傳算法求解概述

遺傳算法[8]（Genetic Algorithm,GA）是由美國(guó)密歇根大學(xué)的John H.Holland教授及其學(xué)生于 20 世紀(jì) 60 年代末到 70 年代初提出的。是模擬達(dá)爾文生物進(jìn)化論的自然選擇和遺傳機(jī)理的生物進(jìn)化過程的計(jì)算模型算法。其中在公交調(diào)度優(yōu)化方面也有著十分廣泛應(yīng)用，這里也借助遺傳算法對(duì)公交調(diào)度優(yōu)化目標(biāo)函數(shù)進(jìn)行求解。

遺傳算法是通過二進(jìn)制或者實(shí)數(shù)編碼將問題的解表示為“染色體”個(gè)體，然后進(jìn)行種群初始化，對(duì)種群進(jìn)行一系列的選擇，交叉，變異操作，直至輸出適應(yīng)度最優(yōu)的個(gè)體，得到最終結(jié)果[9]。

（二）遺傳算法求解步驟

遺傳算法求解的基本步驟：

1.首先是編碼，一般采用二進(jìn)制編碼或?qū)崝?shù)編碼把問題的解表示成“染色體”（個(gè)體）；然后進(jìn)行種群初始化，就是依據(jù)編碼規(guī)則給出種群的初始解，也即隨機(jī)產(chǎn)生一群“個(gè)體”

2.計(jì)算適應(yīng)度，即根據(jù)適應(yīng)度函數(shù)計(jì)算每一個(gè)個(gè)體的適應(yīng)度值，然后按適者生存的原則，從中選擇出適應(yīng)度較大的“個(gè)體”進(jìn)行復(fù)制，再通過交叉、變異過程產(chǎn)生更適應(yīng)環(huán)境的新一代“個(gè)體”種群，即子代。

3.重復(fù)第 2 步。

4.經(jīng)過這樣的一代一代地進(jìn)化，達(dá)到終止條件，最后就會(huì)收斂到最適應(yīng)環(huán)境（適應(yīng)度最大）的一個(gè)“染色體”（即個(gè)體）上，那它就是問題的最優(yōu)解。圖 1 所示，給出了基本遺傳算法求解流程圖。

①編碼。編碼是設(shè)計(jì)遺傳算法首要解決的問題。選擇合適的編碼方式，對(duì)問題的求解精度有非常關(guān)鍵的影響，由于二進(jìn)制編碼的隨機(jī)性使得其局部搜索能力較差，尤其在高精度的問題上不夠理想，鑒于此，本文采用實(shí)數(shù)編碼的方法，在這種編碼方法中，染色體的各個(gè)基因就是決策變量的真實(shí)值。每個(gè)染色體代表一個(gè)時(shí)間段的發(fā)車間隔。②初始種群。在本文中，根據(jù)經(jīng)驗(yàn)法，初步選擇初始群體中的個(gè)體值。對(duì)于高峰時(shí)段的初始值可以選擇[5,15]區(qū)間的任意值作為初始值，對(duì)于平峰時(shí)段可以選擇[15,30]區(qū)間的任意值作為初始值。③適應(yīng)值函數(shù)。遺傳算法的適應(yīng)度是用來判斷群體中的個(gè)體的優(yōu)劣程度的指標(biāo)，它是根據(jù)所求問題的目標(biāo)函數(shù)來進(jìn)行評(píng)估的。這里直接以待求解的目標(biāo)函數(shù)轉(zhuǎn)換為適應(yīng)度函數(shù)，該公交調(diào)度模型的目標(biāo)函數(shù)為最小化問題，所以適應(yīng)度函數(shù)為fD= max(mC p+nCg)。④算子選擇。遺傳算法的操作算子有選擇、交叉和變異這三種，它們分別模擬了生物繁衍、交配和基因突變。在選擇算子方面，我們這里采用輪盤賭選擇算子；在交叉算子方面，我們采用算術(shù)交叉算子，在變異方面，我們采用均勻變異算子。⑤終止條件。設(shè)定最大的進(jìn)化代數(shù)，當(dāng)遺傳算法運(yùn)行達(dá)到停止條件，運(yùn)行終止。

三、結(jié)語

市民出行并不均勻，可相應(yīng)的分為高峰期和平峰期，容易理解，高峰期公交車發(fā)車頻率高，投入的運(yùn)營(yíng)車輛也多，以滿足乘客的需要；而平峰期需要相應(yīng)的減少車輛數(shù)目，節(jié)約成本開支。“高峰期”和“平峰期”的劃分并不是絕對(duì)的，為明確起見，高峰期指的是運(yùn)營(yíng)總收入與運(yùn)營(yíng)總成本之差不小于某一個(gè)“閾值”的時(shí)段?？墒?，設(shè)計(jì)調(diào)度方案的目標(biāo)是使得在乘客數(shù)目下降和恢復(fù)的過程中，通過相應(yīng)地減少和恢復(fù)投入運(yùn)營(yíng)的車輛數(shù)量來保證閾值不被突破，當(dāng)然盈利上界是不受限的。