论文解读者：杨子萱，杨春苇，Guo
编者按
随着电子商务的兴起，物流配送的时间和成本管理变得尤为关键。客户期望快速、灵活的配送选项，而企业则需要在满足这些期望的同时，寻找降低成本的有效策略。在这一背景下，本文提出了一个动态激励机制，为电商配送领域带来了新的解决方案。
本文通过深入分析动态激励机制在电商配送中的应用，揭示了如何通过灵活调整激励策略，引导客户选择对企业成本更低的配送时段，从而实现显著的成本节约。研究采用了近似动态规划方法，预测未来订单分布，优化车辆路径，以实现资源的高效配置。文章的核心贡献在于提出了一种新的配送时段管理方法，该方法不仅能够提高配送效率，还能在不牺牲客户体验的前提下，显著降低企业的物流成本。
1 研究背景
随着电子商务的迅猛发展，上门配送（Attended Home Delivery, AHD）服务在满足顾客便利性和提升配送效率方面的发挥了重要作用。上门配送服务要求顾客在收货时必须在家，因此，AHD适用于易腐商品、高价值商品或危险品的配送。这种服务模式在电商杂货业（e-groceries）中尤为突出，尤其是在新加坡这样的城市国家，企业为了在低利润的杂货行业中保持竞争力，不断寻求更高效的配送计划。
为了降低成本，AHD通常使用非冷藏车进行配送，因此，在像新加坡这样温暖潮湿的气候下，限制车辆的行驶时间以保持易腐商品的新鲜度变得尤为重要。一些公司，如RedMart、FairPrice Online、Amazon Prime Now Singapore，通过设置不同的激励机制来管理配送时段，但这些策略在实际操作中均面临着不同的挑战和限制。
历史文献指出，最后一英里配送（last-mile delivery）由于占据约50%的配送成本而对于电子零售业的运行至关重要。本文所研究的问题涉及配送时间限制、独立需求和短视性客户，且订单生成是动态的，这是一个考虑时间窗的动态定价（dynamic pricing）问题。进一步地，在激励机制方面，作者在历史研究的基础上还在模型中考虑了未来订单、运输附加费（即负激励）、最终路线成本（final routing cost）对动态定价的影响。同时，上门配送服务的车辆路径规划模型对于确定在特定配送时段配送订单的边际配送成本非常关键。而在学界，近似动态规划方法（approximate dynamic programming, ADP）已经在解决动态车辆路径规划问题和定价问题中有诸多应用。因此，为了平衡快速计算和成本估计准确的需求，本文中的边际履行成本（包括机会成本）估计是通过考虑使用近似动态规划方法计算的运输运营成本来完成的。
由此，本研究的目标是通过整合动态激励（dynamic incentive）和订单配送来降低整体配送成本并提高盈利能力。我们需要一种能够利用订单边际履行成本的可变性和顾客配送时段偏好的激励机制，来影响顾客的选择。
2 问题描述
本文所研究的问题为，如何在AHD服务中，动态地计算激励菜单（incentive menu，即对每一个时间窗的激励值），以最大化总利润或等效地最小化最终配送成本。下图描述了客户到达、订单接收、配送路线规划和激励菜单生成的整个流程：
客户到达是随机的，即在规划时间内，客户以一定的概率
到达，并且每个客户在到达时会提供一个订单。每个订单包含了商品和配送位置信息。电商则需要利用这些信息，结合之前接收的订单，生成配送路线，并决定在每个配送时段提供哪些激励措施，以形成激励菜单。接着，客户选择其中一个配送时段并等待配送。对于每个到达的客户，将重复该基本流程，直到订单接收期结束。为了达到成本最小化的目标，电商使用激励措施去影响顾客的选择偏好。我们期望最终得到的结果是，对于每个时间段的配送服务，所规划的运输路线集中在某特定区域。然而，激励机制与运输路线的规划并非相互独立。为一个特定订单提供的激励会影响客户的选择，进而影响车辆运输成本，进一步影响后续订单的边际成本，以及为该后续订单计算的激励菜单。不仅如此，客户在激励菜单展示后立即选择配送时段，并且一旦选择，电商就必须在选定的时段内完成配送；而实际的配送路线和相应的配送成本只有在订单接收期结束时，即所有客户都已经到达并选择他们的配送时段后，才能知道并实现。这与静态定价问题不同，在静态定价问题中，每个配送时段的价格是基于预期的配送负荷事先决定的。因此，研究的核心问题在于如何动态地生成激励菜单，以适应不断变化的客户到达情况，从而最大化总利润或最小化最终配送成本。
为了解决这个问题，作者提出了一个基于动态规划的方法，该方法可以形式化地描述激励计算和最终车辆路径之间的相互作用。假定客户在离散的时间点（time epochs，也是开始计算激励菜单的时间点）到达，且顾客到达的概率服从伯努利分布。到达的客户将从一组可选的运输窗口中选择一个配送时间窗（不考虑客户不购买行为与平台拒绝订单行为），则模型的参数即为时间窗的长度与顾客到达概率。而要服务的客户数是一个随机变量，其二项分布为参数 ，因此要服务的预期客户数由给出。
具体模型将在下一节进行阐述。
3 模型
3.1 激励优化设计 (Incentive Optimization)
在每个客户到达时，系统需要为每个配送时间段 s 提供一个激励值以引导客户选择对配送成本最优的时间段，从而实现整体利润最大化。文章假设激励对客户选择概率有线性影响。具体来说，客户在给定时间 t 选择配送时间段 s 的概率 表示为：
以此可以建立激励优化模型，目标函数是最大化每个时间点 t 对应的期望利润，该期望利润可以表示为：
约束条件为：
尽管该问题的目标函数是非线性的，文章使用KKT条件来求解这个二次规划问题
由KKT条件推导出的激励的最优值为：
该公式表明最优激励值会根据边际成本和客户的初始选择概率进行调整，从而实现最大化利润的目标。
由此激励机制导出的客户在时间段 s 的最终选择概率可表示为：
因此，最优目标函数值为：
这个公式揭示了激励机制如何通过利用时间段之间的边际成本的差异以及客户的选择偏好，实现利润的最大化。
3.2 基于服务选择的车辆路径问题 (Vehicle Routing Problem with Service Choice, VRPSC)
在这一节中，文章描述了如何利用车辆路径模型来优化电商的配送路径，并将其整合到激励机制中。首先，文章定义了一个静态的基于服务选择的车辆路径问题 (VRPSC)，VRPSC的目标是最小化在所有时间段中的配送成本以及由于订单无法被服务导致的罚金，目标函数定义如下：
该模型的服务选择约束，确保每个订单 i 必须且仅能在一个配送时间段 s 内被服务：
接下来是车辆路径约束，确保一个节点 j 只能在已分配的时间段 s 被车辆 k 服务：
还有车辆起点和终点的约束，确保车辆必须从配送中心出发并最终返回：
车辆流动一致性约束，确保车辆在服务客户 j 后会继续访问下一个节点：
时间一致性和无子循环约束：
车辆离开时间的边界约束：
求解时，由于每个时间段 s 内的路径是独立的，整体车辆路径问题 (VRPSC) 可以被分解成每个时间段 s 的车辆路径问题（VRP）：
这种分解方法允许文章分别优化每个时间段的路径规划，从而更快速地解决问题。
3.3 动态激励-路径优化 (Dynamic Incentive–Routing Optimization)
在3.1节中，文章建立了一个激励优化模型来影响客户选择配送时间段，从而降低配送成本。在3.2节中，文章描述了车辆路径问题（VRPSC），用于计算每个时间段的配送成本。然而，这两部分的结合并非简单的静态决策问题，因为客户订单是动态到达的，配送时间段的选择也是逐步进行的。因此，3.3节提出了一个动态激励-路径优化框架，将激励模型与车辆路径模型结合起来，以实现实时的动态优化。文章使用动态规划（Dynamic Programming, DP）来建模整个激励-路径优化过程。该模型在每个时间点 t 上以递归的方式进行，并考虑未来可能到达的订单情况。具体的动态规划模型如下：
最终的动态规划目标函数在订单接受周期的最后一个时间点 T 为：
其中 VRPSC(X) 表示在状态 X 下通过VRPSC模型计算的最终配送成本。该公式意味着文章在时间点 T 最小化所有订单的总配送成本。
关键的边际成本通过以下公式定义：
这里可以被理解为将当前订单分配到配送时间段 s 后，对未来总配送成本的影响。这与激励优化模型中的等价，决定了在每个时间段应该提供多少激励。
以上三个小节之间的联系：
3.1节：激励优化模型根据边际成本计算激励值，引导客户选择对配送更有利的时间段。
3.2节：车辆路径问题（VRPSC）用于计算这些边际成本并规划最优的配送路径。
3.3节：将两者动态结合，实时调整激励机制和配送路径，以实现整体配送系统的动态优化。
通过将激励机制和车辆路径问题相结合，整个模型实现了对客户订单选择和配送路径的动态优化，最终目标是降低配送成本并提高电商配送的效率。
4 边际履约成本的计算
边际履约成本（marginal fulfillment cost）是第三章激励优化模型中一个关键的输入参数。这里，本文提出了两种计算边际履约成本的方法：
近视边际成本（Myopic Marginal Cost）：
这是一种简单的计算方法，通过计算包含和不包含某个订单时的车辆路径成本的差异来得出。这种方法只考虑当前已知订单的路径规划，没有考虑未来订单和最终路径成本。
近似动态规划方法（Approximate Dynamic Programming Approach, ADP）：
这种方法考虑了最终路径成本和订单接受时间范围内的未来订单。通过近似动态规划，可以更准确地估计边际履约成本。文章中提出了一个基于模拟历史订单数据的ADP方法，通过训练过程来拟合值函数近似，从而在实时在线激励优化中使用。
5 数值实验
本文通过一系列的实验来评估所提出的动态激励机制的有效性，特别是考虑了近似动态规划（ADP）方法在处理未来订单时的表现。实验基础设置如下：
配送时段：一天中的7个非重叠的两小时时段。 车辆数量：基础案例为5辆车。 订单到达率：λ = 1.0。 订单密度：平均每辆车每个时段10个订单。 配送区域：一个40x25分钟的区域，代表东南亚的一个典型城市。 客户：被分成不同的类别，每个类别有特定的配送位置分布和配送时段偏好。 本文比较了五种不同的激励机制和客户选择配送时段的方法，包括自由选择、近视激励、ADP激励、近视时段分配和ADP时段分配。结论如下：
ADP激励机制在所有情况下都优于自由选择和近视激励机制，并且随着客户对激励的敏感度增加，总成本降低。 自由选择机制在订单高峰期的总成本急剧上升，而ADP激励机制则能够更平稳地控制成本。 随着订单密度的增加，ADP激励机制的成本节约增加。 更高的到达率导致ADP激励机制的成本节约增加。 增加车辆数量可以提高ADP激励机制的成本节约，直到某个点之后效益递减。
综上所示，本文总结了通过实验获得的管理洞察，包括激励机制如何减少配送成本、历史订单数据如何用于预测未来订单、以及如何通过增加车辆数量和调整订单密度来提高成本效益。
参考文献
Albert Vinsensius, Yuan Wang, Ek Peng Chew, Loo Hay Lee (2020) Dynamic Incentive Mechanism for Delivery Slot Management in E-Commerce Attended Home Delivery. Transportation Science 54(3):567-587. https:// doi.org/10.1287/trsc.2019.0953
微信公众号后台回复
加群：加入全球华人OR|AI|DS社区硕博微信学术群
资料：免费获得大量运筹学相关学习资料
人才库：加入运筹精英人才库，获得独家职位推荐
电子书：免费获取平台小编独家创作的优化理论、运筹实践和数据科学电子书，持续更新中ing...
加入我们：加入「运筹OR帷幄」，参与内容创作平台运营
知识星球：加入「运筹OR帷幄」数据算法社区，免费参与每周「领读计划」、「行业inTalk」、「OR会客厅」等直播活动，与数百位签约大V进行在线交流
文章须知
推文作者：杨子萱，杨春苇，Guo
责任编辑：Guo
微信编辑：疑疑
文章由『运筹OR帷幄』原创发布
如需转载请在公众号后台获取转载须知
关注我们
FOLLOW US
