[發(fā)明專利]一種網(wǎng)約服務(wù)拼單路線規(guī)劃方法及存儲(chǔ)介質(zhì)

有效

• 申請(qǐng)?zhí)枺?/td>: 202110156527.3
• 申請(qǐng)日: 2021-02-04
• 公開（公告）號(hào): CN112964266B
• 公開（公告）日: 2022-08-19
• 發(fā)明（設(shè)計(jì)）人: 王欣;毛林冉;曲博婷;馮筠
• 申請(qǐng)（專利權(quán)）人: 西北大學(xué)
• 主分類號(hào): G01C21/34
• 分類號(hào): G01C21/34
• 代理公司: 西安恒泰知識(shí)產(chǎn)權(quán)代理事務(wù)所 61216
• 代理人: 史玫

本發(fā)明公開了一種網(wǎng)約服務(wù)拼單路線規(guī)劃方法及存儲(chǔ)介質(zhì)。該方法通過(guò)獲取乘客出行需求信息，構(gòu)建拼單數(shù)據(jù)的時(shí)空拓?fù)潢P(guān)系，并根據(jù)時(shí)空拓?fù)潢P(guān)系規(guī)劃車輛拼車的出行路線。基本步驟包括：獲取城市路網(wǎng)信息，城市交通信息和行車信息并根據(jù)交通信息與路網(wǎng)信息，生成交通加權(quán)路網(wǎng)；獲取所有乘客出行請(qǐng)求，根據(jù)所述交通加權(quán)路網(wǎng)生成乘客出行路網(wǎng)數(shù)據(jù)；建立乘客間的可拼車關(guān)系，生成拼單數(shù)據(jù)；構(gòu)建拼單數(shù)據(jù)的時(shí)空拓?fù)潢P(guān)系圖；生成拼車路線。本發(fā)明的路線規(guī)劃方式能夠在滿足所有客戶服務(wù)需求的前提下，使通行成本達(dá)到最低、降低區(qū)域交通壓力。尤其適用于網(wǎng)約車、無(wú)人自動(dòng)駕駛服務(wù)行業(yè)、快遞拼單路線規(guī)劃。

技術(shù)領(lǐng)域

本發(fā)明屬于智能交通領(lǐng)域，涉及一種基于時(shí)空拓?fù)潢P(guān)系的網(wǎng)約服務(wù)拼單路線規(guī)劃方法及系統(tǒng)。

背景技術(shù)

隨著城市化建設(shè)推進(jìn)，城市人口數(shù)量與日俱增，同時(shí)人們的出行、網(wǎng)購(gòu)目的性增強(qiáng)，例如：網(wǎng)約車服務(wù)和快遞、外賣等在日常生活中越來(lái)越普及。但現(xiàn)有技術(shù)中關(guān)于最小化預(yù)約服務(wù)通行工具成本的拼車路線規(guī)劃存在研究空缺。

發(fā)明內(nèi)容

針對(duì)現(xiàn)有技術(shù)的缺陷或不足，本發(fā)明提供了一種網(wǎng)約服務(wù)拼單路線規(guī)劃方法。

為此，本發(fā)明提供的方法包括：

步驟1，將目標(biāo)區(qū)域的歷史通行數(shù)據(jù)添加到該目標(biāo)區(qū)域的路網(wǎng)數(shù)據(jù)中，獲得目標(biāo)區(qū)域的包含節(jié)點(diǎn)與節(jié)點(diǎn)之間通行所需時(shí)長(zhǎng)信息的路網(wǎng)信息，得到目標(biāo)區(qū)域的交通時(shí)間加權(quán)路網(wǎng)；

步驟2，獲取目標(biāo)區(qū)域總時(shí)間段內(nèi)客戶網(wǎng)約服務(wù)信息，并將各客戶網(wǎng)約服務(wù)信息與交通時(shí)間加權(quán)路網(wǎng)匹配，得到所有客戶網(wǎng)約服務(wù)路網(wǎng)信息，任一一個(gè)客戶網(wǎng)約服務(wù)路網(wǎng)信息至少包含起始節(jié)點(diǎn)v_o、目的節(jié)點(diǎn)v_d、預(yù)約服務(wù)時(shí)間和最長(zhǎng)等待時(shí)長(zhǎng)t_w；

步驟3，建立客戶間的可拼單關(guān)系，拼單信息列表R

步驟3.1將所有客戶網(wǎng)約服務(wù)路網(wǎng)信息按照預(yù)約服務(wù)時(shí)間從早到晚進(jìn)行排序，并將排序后的客戶網(wǎng)約服務(wù)路網(wǎng)信息依次劃分至總時(shí)間段的相應(yīng)時(shí)間步內(nèi)，且在各時(shí)間步內(nèi)保留所述排序；

步驟3.2依次對(duì)各時(shí)間步內(nèi)的各客戶網(wǎng)約服務(wù)路網(wǎng)信息執(zhí)行以下步驟，直至最后一個(gè)時(shí)間步內(nèi)的最后一個(gè)客戶網(wǎng)約服務(wù)路網(wǎng)信息：

3.2.1對(duì)于當(dāng)前時(shí)間步s的當(dāng)前客戶網(wǎng)約服務(wù)路網(wǎng)信息x_m，利用單源最短路徑算法，在交通時(shí)間加權(quán)路網(wǎng)上獲取從x_m的起始節(jié)點(diǎn)x_m.v_o在搜索時(shí)間范圍內(nèi)可達(dá)到的節(jié)點(diǎn)集V_m，其中搜索時(shí)間范圍取x_m的最大等待時(shí)長(zhǎng)x_m.t_w，執(zhí)行步驟3.2.2；如當(dāng)前時(shí)間步內(nèi)沒(méi)有客戶網(wǎng)約服務(wù)路網(wǎng)信息，執(zhí)行3.2.7；s為大于等于1的自然數(shù)；

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

3.2.3若x_m.不為空，則執(zhí)行3.2.5，若x_m.為空，執(zhí)行3.2.4；