ICDE 2024最新论文分享｜BEEP：容量约束下能够对抗异常干扰的航运动态定价系统

论文简介

本推文详细介绍了上海交通大学高晓沨教授和陈贵海教授团队发表在顶级学术会议ICDE 2024上发表的最新论文《Corruption Robust Dynamic Pricing in Liner Shipping under Capacity Constraint》，该论文的学生作者为胡永祎、李雪嫣、魏熙锴，合作者为山东大学时阳光教授，通讯作者为高晓沨教授。

本文聚焦于航运业中的集装箱定价问题，旨在通过设计动态定价策略来最大化收益。通过对中国远洋运输公司（COSCO）的业务进行深入研究，本文总结了两大关键要素：(1) 每种类型的集装箱在班轮上的容量有限，并且航运公司会采取超售策略；(2) 销售量偶尔会因罕见的不可控因素（如COVID-19）而出现剧烈波动。基于这两点以及班轮运输的周期性特点，本文将动态定价问题建模为一个结合容量约束和对抗性干扰的MDP模型，称为C3-MDP。

为了在C3-MDP模型中最大化累积收益，本文提出了一种基于奖励探索的规划求解框架BEEP，该框架能够直接适应线性规划算法，形成BEEP-LP算法。此外，本文还提供了详细的遗憾分析，表明BEEP-LP的遗憾随着售卖周期的增加呈次线性增长。针对BEEP-LP的大规模状态-动作空间问题，本文结合深度强化学习技术，提出了相应的近似算法BEEP-DQN，以在运行时间和性能之间取得更好的平衡。基于实际集装箱销售数据的大量实验，验证了C3-MDP模型的合理性以及BEEP框架的有效性。

本推文由胡永祎撰写，审校为高晓沨老师。

论文链接:https://ieeexplore.ieee.org/abstract/document/10598030

一、会议介绍

国际数据工程大会（International Conference on Data Engineering，ICDE）由IEEE主办，是数据挖掘领域的顶级国际学术会议之一，并且被中国计算机学会（CCF）推荐为A类会议。该会议每年举行一次，涵盖数据管理、数据库系统、分布式系统、大数据处理、数据挖掘、数据分析、数据隐私与安全等相关主题。

二、研究背景及主要贡献

由于航运业具备成本低、运输量大的优势，当前全球贸易中超过80%的货物依赖于班轮运输。然而，如何设计一个适用于航运产业的动态定价系统以最大化整体收益，仍然是一个亟待解决的问题。

本文基于班轮集装箱运输的实际场景，得出了一些关键结论：(1) 班轮使用的集装箱已实现国际标准化，最常见的类型为20英尺（1 TEU）和40英尺（2 TEU）集装箱。(2) 每艘货船在出发前，航运公司会固定销售周期，并在此期间为不同类型的集装箱动态定价，以最大化收益。(3) 航运公司通常会采用超售策略，以吸引潜在的高价值客户，但必须谨慎管理，以避免因容量不足产生订单违约，从而损害公司的声誉。(4) 航运公司的销售业绩偶尔会受到罕见的不可控因素（如COVID-19）的影响。

现有的一些强化学习定价模型不能直接应用于这样的班轮定价场景。具体来说，它们要么忽视了容量限制建模，要么没有考虑到罕见的分布外市场波动的影响。最常见的容量建模做法是将最大容量设置为停止标志，即当集装箱售罄时立即结束销售。然而，这种做法的主要问题在于，模型忽略了班轮公司在现实情况下允许的少量超售，导致丢失估值更高的后期客户，影响了整体销售业绩。同时，其缺乏对罕见且不可预测的因素（本文称为对抗性破坏）的考量。因此，模型必须提高探索能力，以确保能够应对这些突发状况。

图1 基于COSCO公司真实数据分析，2020年4月14日由于COVID19集装箱销售量出现异常离群点

本文主要贡献包括：

（1）问题建模：本文是第一篇将航运定价问题建模到在线强化学习框架 C3-MDP 中的工作，该框架结合了容量约束和对抗性干扰。

（2）算法框架：本文提出了一种基于奖励机制的新颖框架 BEEP，该机制鼓励模型探索更多未知的状态-动作对，并可以有效处理超售问题。

（3）理论证明：详细的理论证明表明算法 BEEP-LP 的遗憾值随着周期数呈现次线性增长。本文进一步分析了算法的时间复杂度，以阐明其计算效率。

（4）实验评估：本文针对大型航运公司的真实集装箱销售数据进行了实验验证，并证明了 BEEP 的表现优于现有基线方法。

三、方法

（1）C3-MDP模型

本文将动态定价问题建模为在线强化学习模型，提出了容量约束下的对抗性破坏马尔可夫决策过程（Capacity Constrained Markov Decision Process under Corruptions, C3-MDP)。其对MDP进行了以下调整：

首先，新增参数 K 和 H 分别表示训练中的周期数和步数，从而将周期性设定融入模型，即每个销售周期结束后，定价系统将返回初始状态。

其次，本文定义了一个常量向量 ξ 以表示各种集装箱类型的最大容量。同时本文在状态-动作空间内定义了资源消耗函数 c（s,a），用于表示每一步进行调价后产生的销售量。

此外，本文还引入了参数来表示可能受到对抗性破坏影响的最大周期数，从而为系统抵御对抗性攻击的能力设定了阈值。

在C3-MDP中，目标函数旨在满足售卖限制的同时最大化累计收益，其被定义为：

与此同时，为了衡量提出算法与最佳策略之间的差距，本文还根据最大化收益和满足容量限制两个目标分别定义了两个遗憾函数：

另外，本文的一大亮点是给出了完整的理论分析。本文详细证明了在存在对抗性破坏的场景下，REVREG 和 INVREG 两个遗憾函数仍然在累积贝尔曼误差约束内，进而证明模型关于售卖周期保留次线性遗憾。

（2）BEEP算法框架

针对C3-MDP模型，本文设计了基于奖励探索的周期性规划求解框架 (Bonus-Exploration based Episodic Programming, BEEP)。这是因为在面对容量限制和对抗性破坏时，传统强化学习智能体往往会由于担心超出容量限制而采取过于保守的策略，并可能被分布外数据误导，从而做出次优决策。为解决这一问题，BEEP融合了奖励机制，使智能体在探索访问频率较低的状态-动作对时，能够消耗更少的资源并获得更多奖励。一方面，这允许模型更有效地探索超售行为；另一方面，强化学习智能体能够获得更多真实样本，从而更准确地估计环境参数。奖励函数如下所示：

BEEP模型能够与线性规划求解器兼容，因此本文验证了可以通过BEEP-LP 的线性规划算法来寻找最优解。然而，由于航运定价场景涉及大量的状态-动作空间，BEEP-LP 给计算能力带来挑战。因此，为了平衡计算效率和性能，本文使用拉格朗日松弛将深度强化学习集成到 BEEP 框架中，形成了 BEEP-DQN 近似算法。

算法1 基于C3-MDP的BEEP-DQN算法

图2 模型概览：C3-MDP, BEEP和BEEP-DQN

四、实验及结果

首先，本文通过消融实验证明了容量限制和对抗干扰两个模块的有效性。

1）BEEP-DQN w/o CC （容量限制）: 此基线保持奖励函数不变，使得模型在达到容量上限时即停止售卖。

2）BEEP-DQN w/o AC （对抗干扰）：此基线忽略模型中的奖励机制，不鼓励模型探索分布外数据点。

图3 消融实验，纵轴为平均收益，横轴为不同对抗性干扰最大周期参数设置

此外，本文还通过Prophet 动态规划算法获得最优策略，并据此证明了BEEP-DQN的遗憾是关于周期呈次线性的。

图4 BEEP-DQN and Q-learning两个算法，当对抗性干扰最大周期为10时，在YIK-QZH 数据集上的遗憾

最后，本文在真实数据集上测试了BEEP-DQN的有效性，证明在不同对抗性破坏最大周期数设置下，模型效果都优于其他算法。

表1 预训练数据集的统计信息

五、总结与展望

针对航运业集装箱定价的两个难点：（1）集装箱库存有限的同时公司会采取超售策略。（2）定价收入会受到罕见的外部因素的影响，从而出现离群值。本文提出了C3-MDP模型，该模型同时考虑了容量限制和对抗性干扰。为了重新平衡探索与利用的关系，本文引入了基于奖励机制的BEEP算法框架。同时，本文详细证明了BEEP-LP 线性规划算法能够保证亚线性遗憾。此外，为了在庞大的状态-动作空间上加速算法，本文结合深度强化学习技术，提出了 BEEP-DQN近似算法，并在真实数据集上验证了其有效性。本论文的研究对深度强化学习的应用和定价领域发展有着重要意义。