[發明專利]一種網約服務拼單路線規劃方法及存儲介質

有效

• 申請號: 202110156527.3
• 申請日: 2021-02-04
• 公開（公告）號: CN112964266B
• 公開（公告）日: 2022-08-19
• 發明（設計）人: 王欣;毛林冉;曲博婷;馮筠
• 申請（專利權）人: 西北大學
• 主分類號: G01C21/34
• 分類號: G01C21/34
• 代理公司: 西安恒泰知識產權代理事務所 61216
• 代理人: 史玫

1.一種網約服務拼單路線規劃方法，其特征在于，所述方法包括：

步驟1，將目標區域的歷史通行數據添加到該目標區域的路網數據中，獲得目標區域的包含節點與節點之間通行所需時長信息的路網信息，得到目標區域的交通時間加權路網；

步驟2，獲取目標區域總時間段內客戶網約服務信息，并將各客戶網約服務信息與交通時間加權路網匹配，得到所有客戶網約服務路網信息，任一一個客戶網約服務路網信息至少包含起始節點v_o、目的節點v_d、預約服務時間和最長等待時長t_w；

步驟3，建立客戶間的可拼單關系，拼單信息列表R：

步驟3.1將所有客戶網約服務路網信息按照預約服務時間從早到晚進行排序，并將排序后的客戶網約服務路網信息依次劃分至總時間段的相應時間步內，且在各時間步內保留所述排序；

步驟3.2依次對各時間步內的各客戶網約服務路網信息執行以下步驟，直至最后一個時間步內的最后一個客戶網約服務路網信息：

步驟3.2.1對于當前時間步s的當前客戶網約服務路網信息x_m，利用單源最短路徑算法，在交通時間加權路網上獲取從x_m的起始節點x_m.v_o在搜索時間范圍內可達到的節點集V_m，其中搜索時間范圍取x_m的最大等待時長x_m.t_w，執行步驟3.2.2；如當前時間步內沒有客戶網約服務路網信息，執行3.2.7；s為大于等于1的自然數；

步驟3.2.2將當前通行工具信息列表L內當前位置節點屬于節點集V_m、且承載量有余的通行工具信息加入x_m的候選通行工具集合x_m.C，x_m.C初始為空，L初始為空；若x_m.C內存在相同距離的通行工具，則隨機刪除相同距離的通行工具只保留其中一條信息，執行步驟3.2.3，所述距離為通行工具的當前位置節點與x_m.v_o的距離；

步驟3.2.3若x_m.C不為空，則執行3.2.5，若x_m.C為空，執行3.2.4；

步驟3.2.4生成一條新的通行工具信息y′，通行工具信息y′至少包括最大承載量y′.cpty、服務的客戶網約服務路網信息集合行駛過的路網節點序列y′.path、生成時的時間步y′.t_s、行駛至y′.path中最后一個節點的時間步y′.t_stay和計劃行程節點序列y′.path_schedule，y′.path＝{x_m.v_o}，y′.t_s＝s，y′.t_stay＝s，y′.path_schedule為x_m的起始節點x_m.v_o到x_m的目的節點x_m.v_d的最短路徑節點序列中除去節點x_m.v_o的路徑序列；將y′存入L，獲得更新后的通行工具信息列表L，之后對當前時間步內的下一個客戶x_m+1執行步驟3.2.1，若當前時間步內所有客戶均執行完，則執行3.2.7；

步驟3.2.5在x_m.C內選取與當前客戶網約服務路網信息x_m距離最近的通行工具為當前客戶的配給通行工具y_m，將該客戶x_m信息加入該配給通行工具的中，計算當前客戶從x_m的起始節點x_m.v_o到x_m的目的節點x_m.v_d的最短路徑節點序列x_m.v_i為最短路徑節點序列中的任一節點，執行3.2.6；

步驟3.2.6選取配給通行工具的y_m.path_schedule中與的公共節點，并選取公共節點中距離當前客戶起始節點最遠的公共節點，將中最遠公共節點后面的節點序列加入配給通行工具的y_m.path_schedule中的最遠公共節點與該最遠公共節點的下一個節點之間，即對該配給通行工具的y_m.path_schedule進行了更新，獲得更新后的通行工具信息列表L_s；之后對當前時間步內的下一個客戶網約服務路網信息x_m+1，執行步驟3.2.1；若當前時間步內客戶均執行完，則執行3.2.7；

步驟3.2.7檢查當前通行工具信息列表L中各通行工具信息內當前位置節點與其服務的所有客戶的目的節點是否相同，刪除目的節點與通行工具當前位置節點相同的客戶信息，獲得更新后的通行工具信息列表，執行3.2.8；

步驟3.2.8檢查當前通行工具信息列表L中各通行工具信息的服務的客戶網約服務路網信息集合中是否包含客戶信息，生成當前通行工具信息列表L中不包含客戶信息通行工具的拼單信息，任一不包含客戶信息的通行工具y_u的拼單信息r_u＝(path_u，t_s，u，t_e，u)，其中，path_u＝y_u.path，t_s，u＝y_u.t_s，t_e，u＝s，并將生成的拼單信息加入拼單信息列表R中，獲得更新后的拼單信息列表R，R初始為空，t_e，u為通行工具y_u從L中刪除時的時間步；從當前通行工具列表中刪除不包含客戶信息的通行工具，獲得更新后的通行工具信息列表L，執行3.2.9；如當前通行工具信息列表L中所有通行工具都包含客戶信息，則執行3.2.9；

步驟3.2.9對于當前通行工具信息列表中的每一個通行工具，獲取任一通行工具y_q當前位置節點到達其當前y_q.path_schedule中第一個節點的時間e，當t≥e時，t＝s-y_q.t_stay，將通行工具當前y_q.path_schedule中第一個節點刪除并將該刪除的第一個節點加入該通行工具當前y_q.path中，并作為y_q.path中的最后一個節點，同時將該通行工具的y_q.t_stay更新為s+1；若t＜e，則不更新；對所有通行工具執行完后獲得更新后的通行工具信息列表L，進入下一個時間步，對下一個時間步的第一個客戶需求服務信息執行步驟3.2.1；

所有時間步執行完后輸出拼單信息列表R；

步驟4，利用拼單信息列表R構建時空拓撲網絡，其中任一拼單信息r_u＝(path_u，t_s，u，t_e，u)對應時空拓撲網絡中的一個節點v_sp，u＝(v_s，u，v_e，u，t_s，u，t_e，u，path_u)，v_s，u為path_u中的第一節點，v_e，u為path_u中的最后一個節點；

對于時空拓撲網絡中任意兩個節點v_sp，u到v_sp，λ進行連線操作，如v_e，u到v_s，λ最短距離的時間小于|t_e，u-t_s，λ|時則連接v_sp，u到v_sp，λ；對所有任意兩個節點進行完連線操作后構建得時空拓撲網絡；

步驟5，求解時空拓撲網絡的最小不相交路徑覆蓋，得到相關拼單信息之間的最優路徑解，將相關拼單信息的path_u按最優路徑解連接后得最終拼單路線。