[發明專利]一種車輛路徑選擇方法

在審

• 申請號: 201710101813.3
• 申請日: 2017-02-24
• 公開（公告）號: CN106951981A
• 公開（公告）日: 2017-07-14
• 發明（設計）人: 葉楓;宋小萌;戴佩武
• 申請（專利權）人: 河海大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/08;G06K9/62;G06N3/12
• 代理公司: 南京蘇高專利商標事務所(普通合伙)32204
• 代理人: 梁耀文

1.一種車輛路徑選擇方法，其特征在于，包括如下步驟：

步驟一：事先約定變異概率p1、交叉概率p2及目標站點數目K。針對所采集到的所有乘車地點信息，從中隨機選取K個地點作為初始站點；

步驟二：計算各個乘車地點到每個初始站點的距離；

步驟三：將乘車地點與其相距最近的初始站點劃分為一簇；取每簇均值作為新站點；

步驟四：計算新站點與初始站點的距離是否小于某一給定的閥值，若距離大于等于閥值，則返回步驟二，若距離小于閥值則進入步驟五；

步驟五：將新站點作為選定站點；初始化線路群；

步驟六：計算線路群中每條線路適應度和累計概率；

步驟七：保留適應度最高的線路到下一線路群，其他線路一定概率下變異，生成新線路群；

步驟八：判斷是否達到最大迭代次數，若已經達到最大迭代次數則進入步驟九，若沒有達到最大迭代次數則進入步驟六；

步驟九：將適應度最高的線路進行解碼，生成最優線路。

2.根據權利要求1所述的一種車輛路徑選擇方法，其特征在于：所述步驟二中所述各個乘車地點到每個初始站點的距離中的距離為地理距離，通過地圖引起收集兩地點所處地理位置及周邊環境的距離信息，并根據實際情況進行距離測量得到最終的地理距離。

3.根據權利要求1所述的一種車輛路徑選擇方法，其特征在于：所述步驟六中計算線路群中每條線路適應度的方法為：該線路的最大長度+(該線路所需車輛數-最大限制車輛數)*懲罰因子，所述懲罰因子為初始設定時人工設定。

4.根據權利要求1所述的一種車輛路徑選擇方法，其特征在于：所述步驟六中計算線路群中每條線路累計概率的方法為：該線路適應度/所有線路群中線路的適應度之和+前一條線路求出的累計概率。

5.根據權利要求1所述的一種車輛路徑選擇方法，其特征在于：所述步驟七中其他線路一定概率下變異的方法為：以事先約定的交叉概率相互交換某兩條線路之間的站點信息，隨機對線路配對并隨機設置交換位置，或對線路中某一或幾個位置上的站點信息按照事先約定的變異概率進行改變。

6.根據權利要求1所述的一種車輛路徑選擇方法，其特征在于：所述步驟九中的對適應度最高的線路進行解碼的方法為：將最高適應度的線路根據每輛車的最大載重限制對線路進行拆分，拆分后的若干條序列即為最終安排的若干條線路。