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

在審

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

本發(fā)明提出了一種基于多智能體強(qiáng)化學(xué)習(xí)的訂單匹配和車輛重定位方法。本發(fā)明通過(guò)網(wǎng)約車平臺(tái)獲取多條訂單數(shù)據(jù)和多個(gè)網(wǎng)約車司機(jī)的歷史軌跡點(diǎn)數(shù)據(jù)；對(duì)該數(shù)據(jù)進(jìn)行時(shí)空劃分預(yù)處理；根據(jù)預(yù)處理后的數(shù)據(jù)構(gòu)建司機(jī)初始分布向量和訂單分布變化記錄矩陣；構(gòu)建訂單匹配和車輛重定位馬爾科夫決策過(guò)程；構(gòu)建訂單匹配模型和車輛重定位模型；交替訓(xùn)練訂單匹配模型和車輛重定位模型；按照設(shè)定次數(shù)重復(fù)上述步驟，直到模型穩(wěn)定，得到最終模型。本發(fā)明將兩個(gè)任務(wù)建模在同一個(gè)馬爾科夫決策過(guò)程中同時(shí)優(yōu)化兩個(gè)任務(wù)；本發(fā)明可以一對(duì)一的車輛調(diào)度并通過(guò)共享權(quán)重減少計(jì)算量；本發(fā)明對(duì)城市級(jí)別大規(guī)模車輛和訂單之間的長(zhǎng)期時(shí)空依賴關(guān)系進(jìn)行建模，緩解網(wǎng)約車供需不平衡。

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

本發(fā)明涉及智能交通技術(shù)和深度學(xué)習(xí)交叉技術(shù)領(lǐng)域，具體涉及一種基于多智能體強(qiáng)化學(xué)習(xí)的訂單匹配和車輛重定位方法。

背景技術(shù)

滴滴出行、優(yōu)步、Lyft等網(wǎng)約車平臺(tái)的普及，通過(guò)提供便捷、個(gè)性化的交通服務(wù)，顯著提高了人們的出行效率，使當(dāng)前的交通運(yùn)輸更加高效。在叫車服務(wù)中，乘客提交乘車請(qǐng)求；然后，平臺(tái)將其分配給一個(gè)可用的空閑車輛。用戶的實(shí)時(shí)數(shù)據(jù)采集有助于更準(zhǔn)確地更新供需分布，從而提高網(wǎng)約車平臺(tái)的效率，緩解交通擁堵。設(shè)計(jì)一個(gè)有效的叫車服務(wù)通常需要解決兩個(gè)任務(wù):訂單匹配，將訂單分配給可用的車輛；車輛重定位，部署空閑的車輛到潛在的高需求地區(qū)。

訂單匹配和車輛重定位屬于車輛調(diào)度任務(wù)，需要解決復(fù)雜的時(shí)間和空間依賴性建模。近幾年研究的主流訂單匹配和車輛重定位方法都是基于組合優(yōu)化和強(qiáng)化學(xué)習(xí)在時(shí)空調(diào)度任務(wù)上取得了較好的效果，這些方法主要分為兩種，一是將每個(gè)區(qū)域建模為一個(gè)智能體，忽略了網(wǎng)約車服務(wù)區(qū)域全局的供需變化；另一種方法假設(shè)同一區(qū)域的車輛是同質(zhì)的，并在當(dāng)前區(qū)域等待或遷移到同一目的地，然而，這種假設(shè)在實(shí)踐中可能是不現(xiàn)實(shí)的，并且會(huì)導(dǎo)致大量車輛涌入同一目的地。除此之外，這類建模方法忽略了城市級(jí)別大規(guī)模車輛數(shù)量和訂單數(shù)量帶來(lái)的巨大計(jì)算量，并且訓(xùn)練時(shí)需要耗費(fèi)大量的計(jì)算資源和時(shí)間。

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

本發(fā)明的目的在于克服現(xiàn)有的訂單匹配和車輛重定位方法存在的建模問(wèn)題及模型訓(xùn)練費(fèi)時(shí)、資源耗費(fèi)大的問(wèn)題，提出了一種基于多智能體強(qiáng)化學(xué)習(xí)的訂單匹配和車輛重定位方法，能夠有效地對(duì)城市級(jí)別大規(guī)模車輛和訂單之間的長(zhǎng)期時(shí)空依賴關(guān)系進(jìn)行建模。此外，現(xiàn)有的方法大多數(shù)只對(duì)訂單匹配或者車輛重定位一個(gè)任務(wù)進(jìn)行建模并優(yōu)化，本發(fā)明將訂單匹配和車輛重定位統(tǒng)一到同一個(gè)馬爾科夫決策過(guò)程中，并同時(shí)優(yōu)化兩個(gè)任務(wù)。

為了實(shí)現(xiàn)上述目的，本發(fā)明提出了一種基于多智能體強(qiáng)化學(xué)習(xí)的訂單匹配和車輛重定位方法，包括以下步驟：

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

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

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

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

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

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