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

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

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

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

（一）基本假設(shè)

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

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

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

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

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

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

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

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

（三）模型的建立

1.乘客滿意度模型

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

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

2.公交運營公司滿意度模型

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

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

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

公交車在不同時間段內(nèi)的發(fā)車間隔是公共交通總公司制定公交車時刻表的關(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）是由美國密歇根大學(xué)的John H.Holland教授及其學(xué)生于 20 世紀(jì) 60 年代末到 70 年代初提出的。是模擬達(dá)爾文生物進(jìn)化論的自然選擇和遺傳機(jī)理的生物進(jìn)化過程的計算模型算法。其中在公交調(diào)度優(yōu)化方面也有著十分廣泛應(yīng)用，這里也借助遺傳算法對公交調(diào)度優(yōu)化目標(biāo)函數(shù)進(jìn)行求解。

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

（二）遺傳算法求解步驟

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

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

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

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

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

①編碼。編碼是設(shè)計遺傳算法首要解決的問題。選擇合適的編碼方式，對問題的求解精度有非常關(guān)鍵的影響，由于二進(jìn)制編碼的隨機(jī)性使得其局部搜索能力較差，尤其在高精度的問題上不夠理想，鑒于此，本文采用實數(shù)編碼的方法，在這種編碼方法中，染色體的各個基因就是決策變量的真實值。每個染色體代表一個時間段的發(fā)車間隔。②初始種群。在本文中，根據(jù)經(jīng)驗法，初步選擇初始群體中的個體值。對于高峰時段的初始值可以選擇[5,15]區(qū)間的任意值作為初始值，對于平峰時段可以選擇[15,30]區(qū)間的任意值作為初始值。③適應(yīng)值函數(shù)。遺傳算法的適應(yīng)度是用來判斷群體中的個體的優(yōu)劣程度的指標(biāo)，它是根據(jù)所求問題的目標(biāo)函數(shù)來進(jìn)行評估的。這里直接以待求解的目標(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)遺傳算法運行達(dá)到停止條件，運行終止。

三、結(jié)語

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