[發明專利]一種行程規劃方法及系統

有效

• 申請號: 202010071853.X
• 申請日: 2020-01-21
• 公開（公告）號: CN111310985B
• 公開（公告）日: 2022-04-22
• 發明（設計）人: 龔月姣;趙森華;黃婷;詹志輝
• 申請（專利權）人: 華南理工大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06N3/00
• 代理公司: 北京知呱呱知識產權代理有限公司 11577
• 代理人: 朱芳

1.一種行程規劃方法，其特征在于，所述方法包括：

將預設的種群大小NP根據小生境策略分為M組，將所述M組重組為一組有序的交配池，NP和M為大于1的整數；

將交配池中的親本方案進行配對，在配對后進行交叉操作產生子代方案；

對待變異方案執行變異算子，所述待變異方案是根據突變率確定的子代方案；

對無效方案執行修復策略，所述無效方案是根據總時間約束確定的子代方案；

執行替換操作確定進入下一代的子代方案；

重復迭代，當滿足結束條件時，確定出每個組的目標子代方案；

所述種群內的每個個體的基因編碼為：S＝{s¹,s²,...,s^D}；

其中，一個方案由D天行程組成；s^d(d＝1，2，...，D)代表第d天的時間表；

假設每天都有游客離開并返回同一家酒店；則一天時間表s^d是一個序列：

其中n_d是在第d天行程中訪問的興趣點POI數，h為酒店；方案中的每個基因為POI索引或占位符；占位符表示沒有訪問。

2.如權利要求1所述的方法，其特征在于，所述興趣點POI網絡模型信息建模如下：

POI網絡模型是一個有向完整圖G＝(V,E,X)；

V＝{v₁,v₂,...,v_N}是N個POI的頂點集；每個頂點v_i與四個屬性相關聯：建議參觀時間duration(v_i)，評分score(v_i)，類別category(v_i)和地理位置；

E＝{(v_i→v_j)|v_i,v_j∈V,v_i≠v_j}是連接兩個不同頂點的一組邊集；

集合中的每個(v_i→v_j)表示從v_i到v_j的連接，所述連接表示兩個POI之間的交通時間transit(v_i→v_j)。

3.如權利要求1所述的方法，其特征在于，所述將預設的種群大小NP根據小生境策略分為M組，包括：

所述將預設的種群大小NP根據小生境策略分為M組；

在所述種群NP中將適應值最大的個體確定為組長；

計算所述組長和未處理個體之間的相似度；

將NP/M個與組長相似的個體標記為已處理的一組；

以組為單位，將每個組的所有個體附加到交配池。

4.如權利要求3所述的方法，其特征在于，所述組長和未處理個體之間的相似度按照如下公式計算：

其中，SI是訪問邊集大小占總訪問邊集大小的比值，J₁和J₂分別是個體S₁和S₂的邊集，|J₁∩J₂|是J₁和J₂的交集大小，表示S₁和S₂的共同訪問邊數，|J₁∪J₂|是J₁和J₂的并集大小，表示S₁和S₂的總訪問邊緣，SI的取值范圍為[0，1]。