作者：京東物流 蘇裕焜

一、引言

在配送需求不斷增長的背景下，個(gè)人配送服務(wù)的大規(guī)模眾包化將對(duì)配送市場產(chǎn)生重大影響，且眾包定價(jià)涉及要素較多；這些變化意味著我們的營業(yè)部需要進(jìn)行更精細(xì)化的定價(jià)管理，以適應(yīng)眾包人員市場。與自營人員不同，眾包騎手的服務(wù)質(zhì)量受到當(dāng)?shù)禺?dāng)時(shí)的人員可用性和成本波動(dòng)的影響。為了提高騎手服務(wù)的攬派效率，降低整體運(yùn)營經(jīng)營成本，如何動(dòng)態(tài)定價(jià)成為一個(gè)可考慮的選擇。通過動(dòng)態(tài)定價(jià)，可以一定程度的幫助配送站點(diǎn)通過響應(yīng)配送需求的變化來最大化收入并減少人員短缺；

在日常配送中，動(dòng)態(tài)定價(jià)的優(yōu)勢(shì)顯而易見。然而，在高峰時(shí)段或偏遠(yuǎn)地區(qū)，臨時(shí)性的眾包騎手服務(wù)比全職騎手更復(fù)雜，需要更精細(xì)的規(guī)劃。價(jià)格的不確定性可能增加規(guī)劃和配送的難度。然而，如果眾包騎手可以提前儲(chǔ)備，那么報(bào)價(jià)也可以提前規(guī)劃并完成鎖定。這樣，配送站點(diǎn)可以規(guī)劃整個(gè)運(yùn)營周期，并明確騎手服務(wù)的成本。這也是從過往一些營銷補(bǔ)貼案例中，對(duì)于券種選擇，觸達(dá)人員分析的一些思考，只是眾包的定價(jià)更強(qiáng)調(diào)周期性以及地區(qū)性，因此僅作為探索；

二、 MDP模型用于動(dòng)態(tài)定價(jià)

站點(diǎn)眾包騎手的定價(jià)主要是基于路區(qū)難度系數(shù)，歷史單均等因素對(duì)未來的預(yù)測(cè)單量進(jìn)行順序定價(jià)決策。因此，馬爾可夫決策過程（MDP）是可以作為一個(gè)基礎(chǔ)模型。MDP是其他動(dòng)態(tài)定價(jià)工作的常用模型，尤其是當(dāng)與強(qiáng)化學(xué)習(xí)結(jié)合時(shí)，如一些經(jīng)典的充電樁分配問題。在這些案例中，狀態(tài)空間盡可能多地構(gòu)建狀態(tài)變量，并從數(shù)據(jù)中學(xué)習(xí)定價(jià)策略。然而，由于訓(xùn)練模型需要大量的計(jì)算資源來訓(xùn)練歷史每天的運(yùn)單數(shù)據(jù)與計(jì)費(fèi)數(shù)據(jù)，強(qiáng)化學(xué)習(xí)的優(yōu)先級(jí)會(huì)較低。在此選擇一些規(guī)則疊加聚類模型能更好的幫助我們進(jìn)行歷史數(shù)據(jù)特征選擇和模型訓(xùn)練。最后，可以參考其余案例使用泊松過程來模擬每個(gè)周期內(nèi)單量需求的情況。通過將泊松過程應(yīng)用于我們的離散時(shí)間模型在線動(dòng)態(tài)定價(jià)中，并且可以定義為一種離散化誤差；

如圖所示，可以拆解為這幾步：

資源矩陣：在眾包騎手定價(jià)中，資源矩陣可以表示為不同時(shí)間段內(nèi)可用的騎手資源。

產(chǎn)品定義：產(chǎn)品可以定義為特定時(shí)間段內(nèi)的騎手服務(wù)組合。例如，產(chǎn)品 [1, 1, 0] 可以表示在三個(gè)時(shí)間段中的第一個(gè)和第二個(gè)時(shí)間段內(nèi)提供騎手服務(wù)。

請(qǐng)求到達(dá)和預(yù)算：站點(diǎn)在不同時(shí)間提出對(duì)騎手服務(wù)的請(qǐng)求/需求，并提供他們?cè)敢庵Ц兜膱?bào)價(jià)預(yù)算（b1 到 b7）。

定價(jià)行動(dòng)：營業(yè)部根據(jù)當(dāng)前的騎手可用性和市場需求，采取動(dòng)態(tài)定價(jià)策略（a1 到 a7）。每個(gè)定價(jià)決定都是基于當(dāng)前資源狀態(tài)和預(yù)期需求。

接受與獎(jiǎng)勵(lì)：當(dāng)客戶接受報(bào)價(jià)（即，當(dāng)他們的預(yù)算 bi 大于或等于定價(jià) ai 時(shí)，用綠色的 ? 表示），營業(yè)部獲得一個(gè)獎(jiǎng)勵(lì) ri。這可以是收入或其他績效指標(biāo)。同時(shí)，騎手資源的可用性根據(jù)所售產(chǎn)品的需求而減少。

資源管理：營業(yè)部需要持續(xù)監(jiān)控和調(diào)整騎手的分配，以確保在滿足需求的同時(shí)最大化收入。這包括在高需求時(shí)段提高價(jià)格，或在低需求時(shí)段進(jìn)行調(diào)價(jià)處理。

1. 眾包動(dòng)態(tài)定價(jià)問題描述

眾包騎手服務(wù)的動(dòng)態(tài)定價(jià)涉及為不同的配送產(chǎn)品（計(jì)費(fèi)類型）在線設(shè)置最優(yōu)或接近最優(yōu)的價(jià)格，因?yàn)檎军c(diǎn)下不同路區(qū)、不同地址導(dǎo)致的報(bào)價(jià)都不盡相同。我們的配送站點(diǎn)將其資源——一組配送站的配送能力——組合成提供給客戶的產(chǎn)品，例如小時(shí)達(dá)等。 同樣的，對(duì)于不同的配送產(chǎn)品，公司內(nèi)部的計(jì)費(fèi)形式和計(jì)費(fèi)價(jià)格都不盡相同，需要我們更精準(zhǔn)更合理的進(jìn)行資源分配；

由于對(duì)不同的配送產(chǎn)品的需求事先是未知的，但我們擁有關(guān)于攬派送的歷史數(shù)據(jù)、未來單量的一個(gè)粗粒度的預(yù)測(cè)數(shù)據(jù)以及不同時(shí)間段下單均成本變化數(shù)據(jù)。我們的目標(biāo)是以一種方式可以定價(jià)每個(gè)到達(dá)該站點(diǎn)的攬派產(chǎn)品請(qǐng)求，以最大化目標(biāo)函數(shù)，同時(shí)考慮需求的不確定性（季節(jié)性，大促活動(dòng)等）。

那么在定價(jià)策略中，騎手和站點(diǎn)分別對(duì)應(yīng)供應(yīng)方和需求方的不同角色：

騎手（供應(yīng)方）：騎手是提供服務(wù)的主體，因此他們代表供應(yīng)方。他們的可用性、工作時(shí)間、以及他們?cè)敢饨邮艿膱?bào)酬水平都是供應(yīng)方的關(guān)鍵因素。騎手的數(shù)量和他們的工作時(shí)間限制了站點(diǎn)能夠提供的服務(wù)數(shù)量。

站點(diǎn)（需求方）：站點(diǎn)需要管理和激勵(lì)騎手，以滿足客戶的需求，因此在某種程度上站點(diǎn)也可以被視為需求方。站點(diǎn)需要制定價(jià)格策略來吸引足夠的騎手，同時(shí)也要考慮客戶的需求和支付意愿。站點(diǎn)通過定價(jià)策略來平衡騎手的供應(yīng)和客戶的需求。

問題的供應(yīng)方由一組 ( n ) 個(gè)資源組成，這些資源可以組合成 ( m ) 個(gè)可供出售的配送產(chǎn)品。每個(gè)產(chǎn)品由一個(gè)向量

? 表示，其中的元素規(guī)定了產(chǎn)品中使用的各個(gè)資源的數(shù)量。這些產(chǎn)品的可用性受到資源初始容量 (?) 和不同資源銷售期長度 (?) 的限制，這些長度決定了每個(gè)資源及其所在產(chǎn)品在何時(shí)之后不再可售（表示騎手在特定時(shí)間段內(nèi)可用的時(shí)間窗口。在此時(shí)間之后，騎手可能不再可用，類似于資源過期。）。

問題的需求方通過一個(gè)非齊次復(fù)合泊松計(jì)數(shù)過程 (

?) 來建模，該過程模擬了不同時(shí)刻對(duì)于不同產(chǎn)品請(qǐng)求的到達(dá)，以及不同產(chǎn)品的有限內(nèi)部客戶估值的分布 (?)。即站點(diǎn)需要在騎手的可用性和成本之間找到平衡。

2. MDP模型

在描述了眾包動(dòng)態(tài)定價(jià)問題后，我們將嘗試開發(fā)一個(gè)馬爾可夫決策過程（MDP）模型，以確定定價(jià)策略 (

?)。定價(jià)策略是一個(gè)映射，它將價(jià)格 (a) 分配給站點(diǎn)-時(shí)間對(duì) (?)，并結(jié)合騎手資源的當(dāng)前可用和計(jì)劃中的未來容量 (c)。

在我們的MDP中，定義為一個(gè)五元組 ((S, T, R, A, s_0))，騎手從某個(gè)初始狀態(tài)

? 開始。每個(gè)狀態(tài)捕捉當(dāng)前的時(shí)間步、正在請(qǐng)求的站點(diǎn)以及當(dāng)前可用的騎手?jǐn)?shù)量。騎手為請(qǐng)求的站點(diǎn)提供一個(gè)價(jià)格 (?) ，采取一個(gè)行動(dòng)，導(dǎo)致轉(zhuǎn)移到一個(gè)新狀態(tài) (?)。然而，轉(zhuǎn)移并不是確定性的，因?yàn)樯胁磺宄T手是否會(huì)接受或拒絕價(jià)格以及下一個(gè)站點(diǎn)請(qǐng)求是什么。通過將隨機(jī)需求過程 (?) 和騎手內(nèi)估值的分布 (?) 擬合到歷史數(shù)據(jù)，我們可以估計(jì)轉(zhuǎn)移概率 (?，該概率決定了在狀態(tài) (s) 下采取行動(dòng) (a) 時(shí)達(dá)到狀態(tài) (s') 的可能性。狀態(tài)之間的轉(zhuǎn)移還會(huì)為騎手帶來由函數(shù) (R(s, a, s')) 決定的獎(jiǎng)勵(lì)。

從資料中查詢到的關(guān)于電動(dòng)汽車充電動(dòng)態(tài)定價(jià)的馬爾可夫決策過程（MDP）狀態(tài)的示意圖。該圖展示了資源在其銷售期結(jié)束后的過期情況（容量和產(chǎn)品向量中的灰色部分）。藍(lán)色方塊表示MDP狀態(tài)。在時(shí)間步 (t)，充電站的容量通過容量向量 (c_t) 表示。向量的元素代表相應(yīng)時(shí)間段（綠色方塊中的時(shí)間范圍）內(nèi)的可用充電容量。從上一個(gè)時(shí)間步開始到達(dá)的可能充電會(huì)話預(yù)約請(qǐng)求由向量 (p_t) 表示，其中1表示請(qǐng)求的時(shí)間段?；谌齻€(gè)狀態(tài)變量 (c_t)、(t)、(p_t)，定價(jià)策略提供一個(gè)動(dòng)作 (a)，即充電價(jià)格，用戶可以接受（底部的前兩個(gè)狀態(tài)）或拒絕（右側(cè)的狀態(tài)）。然后狀態(tài)轉(zhuǎn)移到下一個(gè)時(shí)間步（轉(zhuǎn)移函數(shù)的詳細(xì)信息在圖4中說明）。接受的充電請(qǐng)求會(huì)導(dǎo)致容量值減少。下一個(gè)充電會(huì)話預(yù)約被輸入到新狀態(tài)中。注意，時(shí)間步的分辨率必須比充電時(shí)間段更精細(xì)?；疑@示了關(guān)于充電容量和會(huì)話向量 (c_t) 和 (p_t) 的過去信息。

而如果我們的項(xiàng)目需要進(jìn)行相關(guān)的框架復(fù)用，可以類比騎手資源在其服務(wù)期結(jié)束后的過期情況（在容量和任務(wù)向量中的灰色部分）。藍(lán)色方塊表示MDP狀態(tài)。

在時(shí)間步 (t)，騎手的可用數(shù)量通過容量向量 (c_t) 表示。向量的元素代表相應(yīng)時(shí)間段內(nèi)可用的騎手?jǐn)?shù)量。從上一個(gè)時(shí)間步開始到達(dá)的可能訂單請(qǐng)求由向量 (p_t) 表示，其中1表示請(qǐng)求的時(shí)間段。

基于三個(gè)狀態(tài)變量 (c_t)、(t)、(p_t)，定價(jià)策略提供一個(gè)動(dòng)作 (a)，即服務(wù)價(jià)格，用戶可以選擇接受（底部的前兩個(gè)狀態(tài)）或拒絕（右側(cè)的狀態(tài)）。然后狀態(tài)轉(zhuǎn)移到下一個(gè)時(shí)間步（轉(zhuǎn)移函數(shù)的詳細(xì)信息可以通過類似的圖進(jìn)行說明）。接受的訂單請(qǐng)求會(huì)導(dǎo)致可用騎手?jǐn)?shù)量減少。下一個(gè)訂單請(qǐng)求被輸入到新狀態(tài)中。

在調(diào)整后的框架下：

容量向量 (c_t)：表示在不同時(shí)間段內(nèi)的可用騎手?jǐn)?shù)量。

訂單請(qǐng)求向量 (p_t)：表示在不同時(shí)間段內(nèi)的訂單請(qǐng)求情況。

定價(jià)策略 (a)：根據(jù)當(dāng)前狀態(tài)決定的服務(wù)價(jià)格。

狀態(tài)轉(zhuǎn)移：訂單被接受后，騎手的可用數(shù)量會(huì)減少，未被接受的訂單則不影響騎手?jǐn)?shù)量。

2.1 狀態(tài)空間

眾包項(xiàng)目中，MDP的狀態(tài)空間 (S) 由狀態(tài) (s = (c, t, p)) 組成。這里，(c) 表示當(dāng)前時(shí)刻可用的騎手資源數(shù)量，(t) 是離散化的時(shí)間步，(p) 是客戶在該時(shí)間步請(qǐng)求的產(chǎn)品類型。通過將整個(gè)服務(wù)時(shí)間段（0, max(T)）離散化為 (k) 個(gè)時(shí)間步，我們確保狀態(tài)空間是有限的。雖然可以使用連續(xù)時(shí)間MDP，但這會(huì)增加問題的復(fù)雜性，并使解決方案更難以實(shí)現(xiàn)?？蛻粽?qǐng)求到達(dá)時(shí)間是連續(xù)的，但在我們的模型中被視為離散事件。我們假設(shè)在相似時(shí)間到達(dá)的客戶請(qǐng)求表現(xiàn)出相似的行為，即需求隨時(shí)間以分段連續(xù)的方式變化，具有有限的不連續(xù)性。

2.2 動(dòng)作空間

MDP的動(dòng)作空間 (A) 是騎手可以提供給客戶的可能價(jià)格集合。雖然理論上價(jià)格集合可以是連續(xù)的，但在實(shí)踐中，我們假設(shè)價(jià)格是一個(gè)有限集合。這種離散化反映了大多數(shù)服務(wù)提供商在定價(jià)時(shí)的做法。特別地，有一個(gè)特殊的價(jià)格 (a = infty)，表示拒絕動(dòng)作，因?yàn)闆]有客戶會(huì)接受無限高的價(jià)格。當(dāng)騎手資源不足以滿足請(qǐng)求時(shí)，采用此動(dòng)作。

2.3 獎(jiǎng)勵(lì)函數(shù)

MDP的獎(jiǎng)勵(lì)函數(shù) (

?) 確定了通過采取動(dòng)作 (a) 從 (s_t) 轉(zhuǎn)移到 (s_{t+1}) 所獲得的獎(jiǎng)勵(lì)。若目標(biāo)是最大化收入，則獎(jiǎng)勵(lì)為提供給客戶的價(jià)格。當(dāng)客戶接受報(bào)價(jià)時(shí)，獎(jiǎng)勵(lì)為動(dòng)作 (a) 的值，否則為0。成功的交易意味著騎手資源從 (c) 減少到 (c - p)。

2.4 轉(zhuǎn)移函數(shù)

轉(zhuǎn)移函數(shù) (

?) 是MDP模型中最復(fù)雜的部分，它決定了采取動(dòng)作 (a) 后系統(tǒng)如何從狀態(tài) (s_t) 轉(zhuǎn)移到 (s_{t+1})。此函數(shù)由客戶請(qǐng)求的到達(dá)過程 (D(t)) 和客戶對(duì)產(chǎn)品的內(nèi)部估值分布 (?) 決定。在狀態(tài) (s_t = (c, p)) 中，騎手為客戶請(qǐng)求的產(chǎn)品 (p) 選擇一個(gè)價(jià)格 (a)。客戶接受報(bào)價(jià)的概率由估值分布 (?) 的補(bǔ)充累積分布函數(shù)? 決定。

客戶請(qǐng)求的到達(dá)過程 (D(t)) 基于復(fù)合泊松計(jì)數(shù)過程 (

?)，假設(shè)客戶到達(dá)時(shí)間具有無記憶性。我們將泊松過程離散化為多類伯努利過程 (D(t))，在每個(gè)時(shí)間步最多允許一個(gè)產(chǎn)品請(qǐng)求。通過選擇適當(dāng)?shù)臅r(shí)間步數(shù) (k)，確保離散化過程 (D(t)) 能夠很好地近似泊松過程 (?)。

三. MDP模型的離散需求過程

我們嘗試使用了一個(gè)離散需求過程來模擬每個(gè)客戶請(qǐng)求的泊松到達(dá)過程。

離散需求過程的定義：

假設(shè)整個(gè)服務(wù)時(shí)間段 ((0, T)) 被縮放為單位時(shí)間段 ((0, 1))，這可以通過簡單的時(shí)間線重新縮放實(shí)現(xiàn)。

對(duì)于每種客戶請(qǐng)求的產(chǎn)品 (p in P)，我們假設(shè)有一個(gè)泊松計(jì)數(shù)過程 (N_p(tau))，其到達(dá)率為 (lambda_p)，用于生成該產(chǎn)品的請(qǐng)求到達(dá)時(shí)間。

所有產(chǎn)品請(qǐng)求的到達(dá)時(shí)間可以被視為一個(gè)復(fù)合泊松過程 (N(tau))，其強(qiáng)度為 (lambda = sum_{p in P} lambda_p)。

離散化的必要性：

因?yàn)闀r(shí)間被離散化為 (k) 個(gè)時(shí)間步，我們需要用離散的伯努利過程來逼近泊松過程的到達(dá)。

伯努利過程是一系列伯努利試驗(yàn)，定義為 (k) 次試驗(yàn)和每次試驗(yàn)中任何請(qǐng)求到達(dá)的概率 (p)。

這種逼近基于泊松過程是通過保持 (kp = lambda) 不變并讓 (k to +infty) 的伯努利過程序列的極限。

單個(gè)產(chǎn)品請(qǐng)求的分配：

我們可以通過根據(jù)概率分配產(chǎn)品索引來重建單個(gè)產(chǎn)品的到達(dá)過程。 在伯努利過程中，可以通過采樣離散分布來將到達(dá)分配給產(chǎn)品類型。

逼近質(zhì)量取決于將連續(xù)服務(wù)時(shí)間段 ((0, 1)) 劃分為 (k) 個(gè)時(shí)間步的值 (k)。

離散需求過程的期望請(qǐng)求數(shù)量與泊松過程的期望到達(dá)數(shù)量在((0, 1))區(qū)間內(nèi)相匹配，因此在這個(gè)指標(biāo)上兩者沒有差異。

以下是模擬的偽代碼，供參考

# 輸入?yún)?shù)
stations = [s1, s2, ..., sn]  # 站點(diǎn)集合
riders = [r1, r2, ..., rm]  # 騎手集合
products = [p1, p2, ..., pk]  # 產(chǎn)品集合
zones = [z1, z2, ..., zl]  # 路區(qū)集合
lambda_p = [λ1, λ2, ..., λk]  # 各產(chǎn)品的到達(dá)率
historical_prices = {...}  # 歷史報(bào)價(jià)數(shù)據(jù)
historical_volumes = {...}  # 歷史單量數(shù)據(jù)
predicted_volumes = {...}  # 預(yù)測(cè)單量數(shù)據(jù)
pricing_types = ["fixed", "dynamic", "promotional"]  # 計(jì)費(fèi)類型

# 時(shí)間步設(shè)置
T = 1  # 單位時(shí)間段
k = 100  # 時(shí)間步數(shù)

# 初始化請(qǐng)求到達(dá)矩陣
requests = [[[[0 for _ in range(k)] for _ in range(len(zones))] for _ in range(len(products))] for _ in range(len(stations))]

# 模擬請(qǐng)求到達(dá)過程
for t in range(k):
    for station in stations:
        for product_index, product in enumerate(products):
            # 預(yù)測(cè)到達(dá)率調(diào)整
            adjusted_lambda = adjust_lambda(lambda_p[product_index], historical_volumes, predicted_volumes, station, product)

            # 計(jì)算每個(gè)時(shí)間步的到達(dá)概率
            p = adjusted_lambda / k

            # 在當(dāng)前時(shí)間步內(nèi)是否有請(qǐng)求到達(dá)
            if random_bernoulli(p):
                # 確定請(qǐng)求的路區(qū)
                zone_index = sample_zone_distribution(zones, historical_volumes, station, product)

                # 增加對(duì)應(yīng)產(chǎn)品和路區(qū)的請(qǐng)求計(jì)數(shù)
                requests[stations.index(station)][product_index][zone_index][t] += 1

# 動(dòng)態(tài)定價(jià)策略
def dynamic_pricing(station, product, zone, time_step):
    # 使用歷史報(bào)價(jià)和單量調(diào)整價(jià)格
    base_price = historical_prices[(station, product, zone)]
    demand_factor = calculate_demand_factor(historical_volumes, predicted_volumes, station, product, zone, time_step)
    
    # 定價(jià)策略：基于歷史數(shù)據(jù)和當(dāng)前需求
    if pricing_types[product] == "dynamic":
        price = base_price * (1 + demand_factor)
    elif pricing_types[product] == "promotional":
        price = base_price * (1 - 0.1)  # 例如促銷打九折
    else:  # fixed
        price = base_price
    
    return price

# 輔助函數(shù)：伯努利試驗(yàn)
def random_bernoulli(probability):
    return random.uniform(0, 1) < probability

# 輔助函數(shù)：從路區(qū)分布中采樣
def sample_zone_distribution(zones, historical_volumes, station, product):
    # 根據(jù)歷史單量在不同路區(qū)的分布進(jìn)行采樣
    zone_distribution = calculate_zone_distribution(historical_volumes, station, product)
    random_value = random.uniform(0, 1)
    cumulative_sum = 0
    for index, probability in enumerate(zone_distribution):
        cumulative_sum += probability
        if random_value < cumulative_sum:
            return index
    return len(zones) - 1  # 返回最后一個(gè)索引作為默認(rèn)

# 輔助函數(shù)：調(diào)整到達(dá)率
def adjust_lambda(base_lambda, historical_volumes, predicted_volumes, station, product):
    # 根據(jù)歷史和預(yù)測(cè)數(shù)據(jù)調(diào)整到達(dá)率
    adjustment_factor = predicted_volumes[(station, product)] / historical_volumes[(station, product)]
    return base_lambda * adjustment_factor

# 輸出請(qǐng)求到達(dá)矩陣和價(jià)格策略
print(requests)
for station in stations:
    for product in products:
        for zone in zones:
            for t in range(k):
                price = dynamic_pricing(station, product, zone, t)
                print(f"Price for {station}, {product}, {zone} at time {t}: {price}")

四. 使用蒙特卡羅樹搜索（MCTS）

蒙特卡羅樹搜索（Monte Carlo Tree Search, MCTS）是一種用于決策過程的啟發(fā)式搜索算法，廣泛應(yīng)用于博弈論和其他復(fù)雜決策問題。MCTS通過隨機(jī)模擬來探索可能的決策路徑，逐步構(gòu)建決策樹，以找到最優(yōu)策略。以下是MCTS的基本組成部分和工作原理：

選擇（Selection）:

從根節(jié)點(diǎn)開始，使用選擇策略（如UCB1，Upper Confidence Bound for Trees）在樹中選擇一個(gè)子節(jié)點(diǎn)，直到到達(dá)一個(gè)未完全擴(kuò)展的節(jié)點(diǎn)。

UCB1策略通過平衡探索（探索不太確定的節(jié)點(diǎn)）和利用（利用當(dāng)前已知最優(yōu)的節(jié)點(diǎn)）來選擇節(jié)點(diǎn)。

擴(kuò)展（Expansion）:

如果選擇的節(jié)點(diǎn)不是終止?fàn)顟B(tài)且可以擴(kuò)展，則添加一個(gè)或多個(gè)子節(jié)點(diǎn)。每個(gè)子節(jié)點(diǎn)表示一個(gè)可能的動(dòng)作或狀態(tài)。

仿真（Simulation/Rollout）:

從擴(kuò)展的節(jié)點(diǎn)開始，進(jìn)行隨機(jī)模擬直到達(dá)到終止?fàn)顟B(tài)。這個(gè)過程通常稱為“rollout”。

在仿真過程中，隨機(jī)選擇動(dòng)作來模擬未來的可能路徑，以估計(jì)該路徑的潛在獎(jiǎng)勵(lì)。

回溯（Backpropagation）:

將仿真得到的獎(jiǎng)勵(lì)回溯更新到經(jīng)過的每個(gè)節(jié)點(diǎn)。更新節(jié)點(diǎn)的統(tǒng)計(jì)信息，如訪問次數(shù)和平均獎(jiǎng)勵(lì)。

這種更新有助于逐漸提高對(duì)不同路徑的估計(jì)準(zhǔn)確性。

在一些復(fù)雜系統(tǒng)中，MDP可以用于建模和提供初步策略，而MCTS可以在實(shí)時(shí)操作中進(jìn)行具體的決策優(yōu)化和調(diào)整。這種結(jié)合可以充分利用兩者的優(yōu)勢(shì)，適應(yīng)不同的需求和約束。

下面是探索過程中的脫敏偽代碼：

function MCTS(root_state, iterations):
    root_node = CreateNode(state=root_state)

    for i from 1 to iterations do:
        # Selection
        node = root_node
        while node is fully expanded and not terminal(node) do:
            node = BestChild(node, exploration_param)

        # Expansion
        if not terminal(node) then:
            node = Expand(node)

        # Simulation
        reward = Simulate(node.state)

        # Backpropagation
        Backpropagate(node, reward)

    return BestAction(root_node)

function CreateNode(state):
    return Node(state=state, parent=None, children=[], visits=0, total_reward=0)

function BestChild(node, exploration_param):
    best_score = -Infinity
    best_child = None
    for child in node.children do:
        exploit = child.total_reward / child.visits
        explore = exploration_param * sqrt(log(node.visits) / child.visits)
        score = exploit + explore
        if score > best_score then:
            best_score = score
            best_child = child
    return best_child

function Expand(node):
    action = UntriedAction(node)
    next_state, reward = SimulateAction(node.state, action)
    child_node = CreateNode(state=next_state)
    child_node.parent = node
    node.children.append(child_node)
    return child_node

function Simulate(state):
    current_state = state
    total_reward = 0
    while not terminal(current_state) do:
        action = RandomAction(current_state)
        next_state, reward = SimulateAction(current_state, action)
        total_reward += reward
        current_state = next_state
    return total_reward

function Backpropagate(node, reward):
    while node is not None do:
        node.visits += 1
        node.total_reward += reward
        node = node.parent

function BestAction(root_node):
    best_action = None
    best_value = -Infinity
    for child in root_node.children do:
        value = child.total_reward / child.visits
        if value > best_value then:
            best_value = value
            best_action = child.action
    return best_action

function SimulateAction(state, action):
    # Simulate the effect of an action in the environment
    next_state = TransitionFunction(state, action)
    reward = RewardFunction(state, action, next_state)
    return next_state, reward

function UntriedAction(node):
    # Return an action that has not been tried yet from this node
    # This function should consider the set of possible actions and filter out those already tried
    return SomeUntriedAction(node.state)

function RandomAction(state):
    # Return a random action from the set of possible actions for the given state
    return SomeRandomAction(state)

function terminal(state):
    # Determine if the state is a terminal state
    return IsTerminalState(state)

五. 結(jié)論說明

我們嘗試描述了一種基于馬爾可夫決策過程（MDP）的動(dòng)態(tài)定價(jià)模型，用于優(yōu)化眾包騎手的服務(wù)分配和定價(jià)策略。隨著眾包配送服務(wù)的快速增長，這種模型可能成為未來物流和配送系統(tǒng)的重要組成部分。該模型允許眾包平臺(tái)在為客戶提供靈活且高效的配送服務(wù)的同時(shí)，最大化其收入。

為了解決我們的MDP模型，還嘗試使用蒙特卡羅樹搜索（MCTS）啟發(fā)式算法來優(yōu)化定價(jià)決策。在實(shí)際項(xiàng)目中還需要明確定價(jià)算法是否優(yōu)于固定費(fèi)率基線，并且在可以獲得該基線的情況下，與最優(yōu)價(jià)值迭代（VI）基線是否具有競爭力。

在一些別的定價(jià)項(xiàng)目中，會(huì)看到有同學(xué)采取因果推斷的方式進(jìn)行定價(jià)選擇、價(jià)格補(bǔ)貼，這可能取決于我們的具體目標(biāo)和問題特性。如果目標(biāo)是動(dòng)態(tài)地優(yōu)化定價(jià)策略或資源分配策略，以便在不斷變化的環(huán)境中最大化收益（如利潤、效率或客戶滿意度），MDP是也是一個(gè)合適的選擇。MDP可以幫助我們?cè)诓煌瑺顟B(tài)下制定最優(yōu)行動(dòng)策略，并有效處理不確定性，通過概率模型預(yù)測(cè)不同狀態(tài)的轉(zhuǎn)移和相應(yīng)的獎(jiǎng)勵(lì)。另一方面，如果我們希望理解某些因素（如定價(jià)策略、激勵(lì)措施）對(duì)騎手行為或客戶需求的因果影響，因果推斷也可以作為補(bǔ)充加入。因果推斷可以幫助識(shí)別哪些因素真正驅(qū)動(dòng)了結(jié)果變化，并評(píng)估新策略的效果，尤其是在數(shù)據(jù)中存在混雜因素時(shí)，因果推斷方法可以提供更準(zhǔn)確的因果估計(jì)。

在后續(xù)項(xiàng)目中，結(jié)合兩者的方法可能會(huì)更有效，例如，先使用因果推斷識(shí)別關(guān)鍵因果關(guān)系，然后在MDP中利用這些關(guān)系進(jìn)行優(yōu)化決策。

參考來源：

【1】J. Gao, T. Wong, C. Wang, and J. Y. Yu, “A Price-Based Iterative Double Auction for Charger Sharing Markets,” IEEE Transactions on Intelligent Transportation Systems, vol. 23, no. 6, pp. 5116–5127, Jun. 2022, issn: 1558-0016. doi: 10.1109/TITS.2020.3047984. [Online]. Available: https://ieeexplore.ieee.org/document/9325919 (visited on 08/09/2024)

【2】P. V. Dahiwale, Z. H. Rather, and I. Mitra, “A Comprehensive Review of Smart Charging Strategies for Electric Vehicles and Way Forward,” IEEE Transactions on Intelligent Transportation Systems, pp. 1–21, 2024, issn: 1558-0016. doi: 10.1109/TITS.2024.3365581. [Online]. Available: https://ieeexplore.ieee.org/document/10457989 (visited on 08/08/2024)

審核編輯 黃宇