[發(fā)明專利]一種基于多智能體強(qiáng)化學(xué)習(xí)的訂單匹配和車輛重定位方法

在審

• 申請?zhí)枺?/td>: 202210318631.2
• 申請日: 2022-03-29
• 公開（公告）號: CN114970944A
• 公開（公告）日: 2022-08-30
• 發(fā)明（設(shè)計）人: 樂鵬;徐明月;楊璨
• 申請（專利權(quán)）人: 武漢大學(xué)
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/06;G06Q50/30;G06N7/00;G06N3/04;G06N3/08;G06F16/9537
• 代理公司: 武漢科皓知識產(chǎn)權(quán)代理事務(wù)所(特殊普通合伙) 42222
• 代理人: 許蓮英

1.一種基于多智能體強(qiáng)化學(xué)習(xí)的訂單匹配和車輛重定位方法，其特征在于，包括以下步驟：

步驟1：通過網(wǎng)約車平臺獲取多條訂單數(shù)據(jù)和多個網(wǎng)約車司機(jī)的歷史軌跡點(diǎn)數(shù)據(jù)；對多條歷史訂單數(shù)據(jù)以及多個網(wǎng)約車司機(jī)的歷史軌跡點(diǎn)數(shù)據(jù)進(jìn)行空間和時間劃分預(yù)處理，將城市等分為不重疊的多個六邊形格網(wǎng)，將一天等分為不重疊的多個時間切片；根據(jù)多條網(wǎng)約車司機(jī)的歷史軌跡點(diǎn)數(shù)據(jù)軌跡點(diǎn)數(shù)據(jù)構(gòu)建司機(jī)初始分布向量；

步驟2：通過多條預(yù)處理后的訂單數(shù)據(jù)構(gòu)建訂單分布變化記錄矩陣；

步驟3：構(gòu)建訂單匹配和車輛重定位馬爾科夫決策過程；

步驟4：構(gòu)建時空價值網(wǎng)絡(luò)、目標(biāo)時空價值網(wǎng)絡(luò)以及組合優(yōu)化函數(shù)；根據(jù)步驟1.4的供應(yīng)向量和步驟2.2的需求矩陣得到當(dāng)前時間切片編號t每個格網(wǎng)的空閑車輛和等待訂單，得到所有可能的匹配方案；根據(jù)所有可能的匹配方案和構(gòu)建的時空價值網(wǎng)絡(luò)、目標(biāo)時空價值網(wǎng)絡(luò)計算匹配權(quán)重，根據(jù)匹配權(quán)重得到組合優(yōu)化函數(shù)的最優(yōu)匹配方案，從而構(gòu)建基于多智能體強(qiáng)化學(xué)習(xí)的訂單匹配模型：

步驟5：構(gòu)建集中式價值網(wǎng)絡(luò)、目標(biāo)集中式價值網(wǎng)絡(luò)、共享策略網(wǎng)絡(luò)和目標(biāo)共享策略網(wǎng)絡(luò)，進(jìn)一步構(gòu)建基于多智能體強(qiáng)化學(xué)習(xí)的車輛重定位模型；

步驟6：使用步驟1的司機(jī)分布向量和步驟2的訂單分布變化記錄矩陣交替進(jìn)行步驟5、步驟6執(zhí)行N_T次，使用步驟5和步驟6記錄的變量訓(xùn)練交替訓(xùn)練基于多智能體強(qiáng)化學(xué)習(xí)的訂單匹配模型和基于多智能體強(qiáng)化學(xué)習(xí)的車輛重定位模型；按照設(shè)定的次數(shù)重復(fù)上述步驟，直到模型穩(wěn)定，得到訓(xùn)練好的模型；

步驟1具體如下：

步驟1.1：獲取多條訂單數(shù)據(jù)和多個網(wǎng)約車司機(jī)的歷史軌跡點(diǎn)數(shù)據(jù)；

所述每條訂單數(shù)據(jù)包括：

每條訂單數(shù)據(jù)的編號、每條訂單數(shù)據(jù)的服務(wù)司機(jī)編號、每條訂單數(shù)據(jù)的乘客上車的時間、每條訂單數(shù)據(jù)的上車點(diǎn)的經(jīng)度、每條訂單數(shù)據(jù)的上車點(diǎn)的緯度、每條訂單數(shù)據(jù)的乘客下車的時間、每條訂單數(shù)據(jù)的下車點(diǎn)的經(jīng)度、每條訂單數(shù)據(jù)的下車點(diǎn)的緯度、每條訂單數(shù)據(jù)的價格和每條訂單數(shù)據(jù)的行程距離；

所述每個網(wǎng)約車司機(jī)的歷史軌跡點(diǎn)數(shù)據(jù)包括：

每個網(wǎng)約車司機(jī)的歷史軌跡點(diǎn)數(shù)據(jù)的編號、每個網(wǎng)約車司機(jī)的歷史軌跡點(diǎn)數(shù)據(jù)的當(dāng)前時間、每個網(wǎng)約車司機(jī)的歷史軌跡點(diǎn)數(shù)據(jù)的當(dāng)前位置的經(jīng)度、每個網(wǎng)約車司機(jī)的歷史軌跡點(diǎn)數(shù)據(jù)的當(dāng)前位置的緯度、每個網(wǎng)約車司機(jī)的歷史軌跡點(diǎn)數(shù)據(jù)的服務(wù)狀態(tài)；

所述服務(wù)狀態(tài)為空載或者載客；

步驟1.2：根據(jù)預(yù)設(shè)的六邊形大小對訂單數(shù)據(jù)所在的網(wǎng)約車服務(wù)區(qū)域進(jìn)行六邊形格網(wǎng)劃分，分成N_H個不重疊的六邊形格網(wǎng)，記作六邊形格網(wǎng)編號六邊形格網(wǎng)編號的數(shù)量是N_H；將每條訂單數(shù)據(jù)的上車點(diǎn)的經(jīng)度、每條訂單數(shù)據(jù)的上車點(diǎn)的緯度、每條訂單數(shù)據(jù)的下車點(diǎn)的經(jīng)度、每條訂單數(shù)據(jù)的下車點(diǎn)的緯度、每個網(wǎng)約車司機(jī)的歷史軌跡點(diǎn)數(shù)據(jù)的當(dāng)前位置的經(jīng)度、每個網(wǎng)約車司機(jī)的歷史軌跡點(diǎn)數(shù)據(jù)的當(dāng)前位置的緯度依次轉(zhuǎn)換為對應(yīng)的六邊形格網(wǎng)編號；將對應(yīng)的六邊形格網(wǎng)編號添加至每條訂單數(shù)據(jù)，將對應(yīng)的六邊形格網(wǎng)編號添加至每個網(wǎng)約車司機(jī)的歷史軌跡點(diǎn)數(shù)據(jù)；

步驟1.3：根據(jù)預(yù)設(shè)的時間間隔對一天進(jìn)行時間切片，分成N_T個不重疊的時間切片，記作時間切片編號時間切片編號的數(shù)量為N_T；將每條訂單數(shù)據(jù)的乘客上車的時間、每條訂單數(shù)據(jù)的乘客下車的時間、每個網(wǎng)約車司機(jī)的歷史軌跡點(diǎn)數(shù)據(jù)的當(dāng)前時間依次轉(zhuǎn)換為對應(yīng)的時間切片編號，將對應(yīng)的時間切片編號添加至每條訂單數(shù)據(jù)得到每條預(yù)處理后的訂單數(shù)據(jù)，將對應(yīng)的時間切片編號t添加至每個網(wǎng)約車司機(jī)的歷史軌跡點(diǎn)數(shù)據(jù)得到每個預(yù)處理后的網(wǎng)約車司機(jī)的歷史軌跡點(diǎn)數(shù)據(jù)；

步驟1.4：根據(jù)所有網(wǎng)約車司機(jī)的歷史軌跡點(diǎn)數(shù)據(jù)的編號和所有網(wǎng)約車司機(jī)的歷史軌跡點(diǎn)數(shù)據(jù)的時間切片編號得到每個司機(jī)編號第一次出現(xiàn)的時間切片編號，作為每個網(wǎng)約司機(jī)的上班時間，統(tǒng)計所有網(wǎng)約司機(jī)的上班時間的分布的峰值，根據(jù)所有網(wǎng)約車司機(jī)的歷史軌跡點(diǎn)數(shù)據(jù)位于峰值時段內(nèi)每個六邊形格網(wǎng)的司機(jī)數(shù)量的比例生成上班時間每個六邊形格網(wǎng)的司機(jī)數(shù)量，記作初始供應(yīng)向量S，所述S的長度為N_H；

所述的步驟2具體包括：

步驟2.1：根據(jù)多條預(yù)處理后的訂單數(shù)據(jù)的上車時間編號、上車點(diǎn)的六邊形格網(wǎng)編號、下車點(diǎn)的六邊形格網(wǎng)編號，統(tǒng)計得到每個時間片段從每個六邊形格網(wǎng)出發(fā)到每個六邊形格網(wǎng)的訂單數(shù)量，記作需求矩陣D，大小為N_T×N_H×N_H,；

步驟2.2：根據(jù)多條預(yù)處理后的訂單數(shù)據(jù)的上車點(diǎn)的六邊形格網(wǎng)編號、下車點(diǎn)的六邊形格網(wǎng)編號、訂單價格和行程距離，統(tǒng)計得到從每個六邊形格網(wǎng)出發(fā)到每個六邊形格網(wǎng)的訂單平均收益，記作獎勵矩陣R，大小為N_H×N_H，其中，每個訂單的收益＝價格―油價×距離，油價根據(jù)網(wǎng)絡(luò)查詢得到；

步驟2.3：根據(jù)多條預(yù)處理后的訂單數(shù)據(jù)的上車點(diǎn)的六邊形格網(wǎng)編號、下車點(diǎn)的六邊形格網(wǎng)編號、時間切片編號，統(tǒng)計得到從每個六邊形格網(wǎng)出發(fā)到每個六邊形格網(wǎng)的訂單平均行程時長，記作時長矩陣T，大小為N_H×N_H，其中，每個訂單的行程時長＝下車時間編號-上車時間編號。