[發明專利]一種基于改進型果蠅算法的多車協同拼車路徑優化方法

在審

• 申請號: 201910231350.1
• 申請日: 2019-03-26
• 公開（公告）號: CN110084390A
• 公開（公告）日: 2019-08-02
• 發明（設計）人: 楊文強;宋長源;孔曉紅;李曉娟;徐君鵬;付廣春;張素君
• 申請（專利權）人: 河南科技學院
• 主分類號: G06Q10/02
• 分類號: G06Q10/02;G06Q10/04;G06N3/00;G06Q50/30
• 代理公司: 新鄉市平原智匯知識產權代理事務所(普通合伙) 41139
• 代理人: 路寬

本發明公開了一種基于改進型果蠅算法的多車協同拼車路徑優化方法，屬于智能交通技術領域。本發明的技術方案要點為：通過步長正弦衰減策略，使算法在進化前期能夠以較大步長對解空間進行廣度探索，在進化后期以較小步長進行深度開發，同時由于步長呈正弦振蕩衰減，因而能夠使算法的性能在全局和局部尋優中得到較好的兼顧；通過混沌變異策略，改善種群的多樣性，進一步提高其跳出局部最優的能力。上述改進措施進一步提高果蠅算法的求解性能。本發明有效改善了市民拼車出行的效率，為乘客節省了開支，為司機增加了收益，更為重要的是減少了汽車尾氣的排放，改善了空氣質量。

技術領域

本發明屬于智能交通技術領域，具體涉及一種基于改進型果蠅算法的多車協同拼車路徑優化方法。

背景技術

隨著外來人口的增多以及機動車單雙號交替限行措施的出臺，打車難問題更加凸顯。在出租車保有量飽和的情況下，針對這一困擾民眾正常出行的民生難題，拼車出行將成為行之有效的解決途徑。在此背景下，對出租車多車協同拼車業務路徑優化問題進行研究，其對于節能減排、提高民眾出行效率具有很好的促進作用。因而，針對多車協同拼車路徑優化問題，尋求一種有效的出租車路徑優化方法具有很好的科學意義和社會價值。

截止目前，學者關注較多的仍是單個出租車的路徑優化問題，而較少考慮多個出租車同時參與拼車的情況，因而很難滿足實際需要。比如：Ma et al.(Path optimizationof taxi carpooling,Plos One,2018)基于遺傳算法對拼車路徑優化問題進行了探討，盡管其對多出租車拼車路徑優化問題進行了研究，但其前提是所有乘客都上車后再將乘客送往各自的目的地，這種方式將會對優化結果產生不利影響。張等(基于三維時空軌跡的拼車改進算法研究，計算機工程與應用，2018)提出一種改進的Hausdorff距離拼車算法，在匹配準確度及減少時間代價方面有較大提高。本發明對多車協同模式下的拼車路徑優化問題進行了認真的分析與研究，并提出了求解該問題的改進型果蠅算法，不僅提高了出租車的運營效率、司機的收入，而且為乘客節省了支出，更重要的是豐富了求解拼車路徑優化問題的方法，對于提升出租車行業的運營能力及服務水平具有很好的示范作用。

發明內容

本發明解決的技術問題是提供了一種基于改進型果蠅算法的多車協同拼車路徑優化方法，該方法能夠有效解決市內交通限行情況下民眾出行打車難的問題，并助推城市交通向智能化方向進一步發展，最終使得出租車或私家車能夠承載較多的乘客，提高上座率，減少空駛和油耗，有效緩解打的難、交通擁堵的現狀。

為解決上述技術問題，本發明的構思為：以出租車有限載客為約束條件，將多車協同拼車模式引入到出租車的路徑模型當中，以所有乘客到達目的地出租車所用時間最短為優化目標，把載客有限的多車協同拼車路徑優化問題抽象成帶約束的組合優化問題。本發明建立了考慮多車模式下的拼車路徑優化模型，并基于改進型果蠅算法(Improved FruitFly Optimization Algorithm,IFOA)對該模型進行求解。鑒于傳統果蠅算法(Fruit FlyOptimization Algorithm,FOA)在存在易陷入局部最優、求解精度低等缺點，引入步長正弦衰減策略、混沌變異策略，即通過步長正弦衰減策略，使算法在進化前期能夠以較大步長對解空間進行廣度探索，在進化后期以較小步長進行深度開發，同時由于步長呈正弦振蕩衰減，因而能夠使算法的性能在全局和局部尋優中得到較好的兼顧；通過混沌變異策略，改善種群的多樣性，進一步提高其跳出局部最優的能力。

根據以上發明構思，本發明采用如下技術方案：一種基于改進型果蠅算法的多車協同拼車路徑優化方法，其特征在于包括以下步驟：

(1)對多出租車協同拼車存在的約束及要優化的目標進行分析，并抽象為帶約束的數學模型；

(2)初始化參數：總體最大進化代數G_max、進化代數計數器t、果蠅規模M、果蠅個數計數器n、步長step、初始化種群個體；