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

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

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

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

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

（一）基本假設(shè)

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

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

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

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

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

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

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

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

（三）模型的建立

1.乘客滿意度模型

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

式中:Cp是公交車乘客的出行成本；Ce為站點乘客的等車成本；Cw是公交車行駛路途中的乘客時間成本；ue為單位乘客時間成本；uw是單位乘車時間成本；qij為第i輛公交車停靠在第j站時上車的乘客數(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）是由美國密歇根大學的John H.Holland教授及其學生于 20 世紀 60 年代末到 70 年代初提出的。是模擬達爾文生物進化論的自然選擇和遺傳機理的生物進化過程的計算模型算法。其中在公交調(diào)度優(yōu)化方面也有著十分廣泛應用，這里也借助遺傳算法對公交調(diào)度優(yōu)化目標函數(shù)進行求解。

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

（二）遺傳算法求解步驟

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

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

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

3.重復第 2 步。

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

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

三、結(jié)語

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