论文原文
Alexander M. Stroh, Alan L. Erera, Alejandro Toriello (2022) Tactical Design of Same-Day Delivery Systems. Management Science 68(5):3444-3463.
解读人：吕贤
编者按
Tactical Design of Same-Day Delivery Systems 获2024年运筹学与管理科学学会 (The Institute for Operations Research and the Management Sciences, INFORMS) 交通科学和物流最佳论文奖 (TSL Best Paper Award) 。我们愿意用“Less is more” 来形容这篇论文，它用轻巧的模型描述复杂的优化问题，并给出了结构优美、易于理解和便于使用的优化方案，同时基于运营决策模型给出了策略设计上的分析与见解，行文有流云之势，特此与大家分享。
1 当日可达系统和策略性设计简介
顾名思义，“当日可达” （same-day delivery a.k.a. SDD）指顾客会在下单当天收到他们的订单。在日益蓬勃的电子商务领域，当日可达服务通常由大型零售商和物流供应商提供，例如亚马逊。当日可达服务通常包含两个物流过程：一是在货仓 (stocking location) 的订单管理，二是从货仓到顾客收货地址 (customer delivery addresses) 的订单配送 (order distribution) 。这篇文章将聚焦从货仓到收货地址的订单配送过程。
管理当日可达系统面临着诸多挑战，包括例如紧迫的ddl，较低的订单量，和较高的订单波动水平——概括而言，是极大的需求端不确定性和有限的响应时间。因此，如果不仔细规划，订单的配送可能成本高昂且效率低下。
SDD系统里有两大类需要关注的要素：策略性设计 (tactical design) 和运营性决策 (operational decisions)。简单来说，策略性设计解决"how", 运营性决策解决"action"。在策略层面，我们会关注系统的配置如：
SDD服务会覆盖哪些区域 (how large the service region)？ SDD系统中派送车队的规模应该有多大(how large the delivery vehicle fleet size)？ 顾客每天最迟可以在什么时候下单 (How late in the day should SDD service be offered to customers)？
而在运营层面，我们则会关注系统的运作如：
何时配送订单 (when to dispatch)? 哪些 “等待中” 的顾客会被服务 (which to be served)?
分析SDD系统时，物流研究界通常假设固定系统中策略性设计，再对运营性决定进行详细的分析、优化和/或模拟。不幸的是，已有的运营决策模型往往太过复杂且计算不友好，因此可能无法提供关于策略层面设计的见解。相反，简单的运营决策模型有利于策略层面设计的分析，但简单的模型可能会在刻画系统表现的时候失真。
本次解读的文章建立了一个简单的SDD订单配送模型，其中单个货仓及其派送车队在指定的服务区域内服务SDD订单。这个简单模型仍可以精确刻画系统的表现。作者研究了这类模型的最优订单配送决策（即一个派送车辆应该载多少订单，在什么时间从货仓出发）。基于这个简单的SDD订单配送模型和最优的订单配送决策（运营性决定），作者回答了各种策略性设计问题，包括车队规模，接单截止时间，以及服务区域的划分等。
2 技术路线和分析框架
为了保证简单的模型仍然可以精确刻画系统的表现，作者使用了连续近似（continuous approximation）方法来描述派单时间 （派单时间指车辆从货仓出发，派送完所有的订单后回到货仓的总时间）。连续近似方法的核心，是将派单时间写成一个关于订单数量的函数，这个函数是递增且凹的。例如，当我们用表示订单数量（同时也是收货地点数量），表示订单派送时间，那么
其中，常数表示车辆在货仓的固定准备时间；常数表示每个订单的服务时间；用于近似经过个收货地点的最短封闭路径 （即旅行商路径）时间，其中为常数。
注：事实上，这一项的出现依赖于BHH定理（Beardwood, Halton, and Hammersley Theorem）—— Beardwood等人在1959年证明了，在面积为的有界平面区域中，经过个点的最短封闭路径的期望长度几乎总是与渐近成正比 (the length of the shortest closed path through points in a bounded plane region of area is ‘almost always’ asymptotically proportional to for large n)。BHH定理揭示了旅行商路径的一个优雅的渐进特性。这一结果对人们理解旅行商路径的行为，以及为其提供最优上下界，有着深远的影响。
当顾客的收货地址在服务区域内的随机分布来自于一个连续的分布，用连续近似描述派单时间被认为是相当准确的。这样，我们就无需知道每一个顾客的收货地址再去计算派单时间，从而极大地简化了模型的复杂程度。【这是第一篇在SDD建模场景中使用连续近似方法的文章哦，作者把这个写在了文章贡献的第一条o(￣▽￣)ブ】
在分析最优订单配送决策时，作者对两种重要的情况直接刻画了最优决策的结构：
派送车队只有一辆车，这辆车每天会被派送多次 派送车队有足够多数量的车，每辆车每天只会被派送一次
对于另一种重要的情况——派送车队有多辆车，每辆车每天会被派送多次——最优决策的结构刻画则比较困难。因此作者对其提供了一个启发式的最优决策，并给出了worst-case performance guarantee.
拥有了最优订单配送决策，作者进一步回答了一些策略性设计问题，给出了分析性质，并用案例研究验证了分析结论。
3 模型
模型设定与符号：
货仓与车辆。只有一个货仓。派送车队里有辆车。每辆车都从货仓出发，完成派单后会回到货仓。 运营时间。运营以天为单位。记时间为，每辆车第一次可以离开货仓的时间为, 当天服务结束的时间为 （即所有的车辆需要在时刻之前回到货仓）。方便起见，我们可以看成一天有 单位的时间。 服务区域与顾客订单。服务区域是给定的。服务区域内订单数量以每单位时间的速率累积，所有的订单都会在当天被满足。因此每天在时刻，系统里订单的数量为。不失一般性，我们假设。 接单截止时间。系统每天从时刻开始接单，在某一时刻<停止接单，因此一天内一共会接数量的订单。可以被解释为接单截止时间或者每日订单总量。 派单时间。我们定义派单时间为：一辆需要派送数量的订单的车，从离开货仓到返回货仓的总时间。给定订单数量，派单时间是一个递增的凹函数。【这意味着服务更多的订单需要更多的时间，但整合订单时，边际时间效率将有所提高。】 决策变量。假设一天里系统一共派次单。系统的决策变量是一系列派单三元组 ，其中表示第 次的派单决策：车辆 载着数量的订单在 时刻离开货仓。这里我们假设派单是按时间顺序编号的。
我们需要求解的优化问题 (P1) 如下：
4 最优订单配送
作者一共考虑了三种情况下的最优配送方案：
无限车辆系统。我们能以微不足道的成本添加任何数量的车辆进入车队。 单车辆系统。车队中只有一辆车。 一般性的有限车辆系统。车队中车的数量大于1，并且每辆车可以执行多次派单。
作者给前两种情况提供了最优的配送方案，并基于此为第三种情况提供了启发式的配送方案。我们将逐一介绍这些配送方案。
4-1 无限车辆系统
最优配送方案：Many-Vehicle Policy (MVP). 从时刻开始，系统在时刻发出第次派单指令，收到指令的派送车可以把时间段内货仓中所有在等待并且已经实现的(awaiting and realized)订单派送完，并恰好在时刻回到货仓。最后一次派单在接单截止时间时刻发生，这次派单将会把所有剩下的订单派送完，并且派送车会在时刻之前回到货仓。
下图展示了一个使用4辆车的MVP。图中每个弧形对应一次派单调度，弧前相同线形的水平直线表示该次派单所服务的订单区间。
注：第一辆车从时刻0等待到时刻，于时刻开始执行派单任务，于时刻返回货仓；第二辆车从时刻0等待到时刻，于时刻开始执行派单任务，于时刻返回货仓；第三辆车从时刻0等待到时刻，于时刻开始执行派单任务，于时刻返回货仓；第四辆车从车从时刻0等待到时刻，于时刻开始执行派单任务，于时刻之前 （即不晚于时刻）回到货仓。
MVP不仅是无限车辆系统的最优配送方案，而且，在派送车辆数量相同的情况下，MVP的配送时间为优化问题的目标函数提供了一个下界。 MVP的求解是很方便而且简单的。
4-2 单车辆系统
在单车辆系统中，为了确保结果有意义，我们需要添加额外的条件。
（C1）充足的派送速度。存在, 使得 for all 。【这个条件保证了车辆派送时间里新产生的订单一定是小于原派送订单的数量的】 （C2）充足的返回时间。 满足 。【这个条件保证了最后一笔订单到达的时刻和时刻之前留有充足的间隔】 （C3）最小派单规模。任何的可行解 都满足 <。【这个条件可以被看做一个额外的约束，它用于保证所有的订单都会被满足】
最优配送方案：Single-Vehicle Policy (SVP). 对于一个满足 (C1)-(C3) 的单车量SDD系统，从时刻开始，系统在时刻发出第次派单指令，派送车可以把时间段内货仓中所有在等待并且已经实现的(awaiting and realized)订单派送完，并且恰好在时刻返回货仓。在执行最后一次派送时，车辆恰好在时刻返回货仓。
下图展示了一个执行两次派单的SVP。每个弧形对应一次派单调度。
注：派送车从时刻0等待到时刻，于时刻开始执行第一次派单任务，于时刻返回货仓；返回货仓后，立马于时刻开启第二次调度。另外，一个SVP中的最后一次派单任务会发生于时刻之后，这样才能保证所有的订单被覆盖。
SVP可以完全被第一次的派单时间所刻画。第一次派单时间的计算作者在文中给出了具体的算法。
4-3 有限车辆系统
混合配送方案 Hybird Policy. 对于一个拥有辆车的车队，先对前辆车使用MVP。最后一辆车根据SVP服务所有剩余的订单。
下图对比了3辆车的MVP（上）与2辆车的混合配送方案（下）。
注：上方的图表示一个MVP，包含了3辆车，它与图1是相同的。下方的图表示一个混合策略，包含了2辆车。混合策略中，第一辆车采用MVP调度，只执行一次派单任务，服务第一个黑点之前的订单，即图中的实线部分；第二辆车采用SVP调度，服务第一个黑点之后产生的订单，在后续的每个黑点处各执行一次派单任务。
作者还为这个启发式的方案提供了worst-case performance guarantee。记调用辆车的MVP需要 的最优派单时间。如果车队中一共拥有辆车，在混合配送方案下最后一辆车执行了次派单任务，那么对任何拥有辆车的SDD系统，最优派单时间的一个下界为。
4 策略性设计分析
拥有了简单的SDD订单派送模型和易于计算的最优派送方案，作者进一步进行了策略性设计的分析。
4-1 服务区域的划分和派送车队的规模
作者想回答：划分服务区域是否比让每辆车服务整个区域更有优势？
连续近似为我们定性分析服务区域的划分与派送车队规模带来了方便。对于一个服务区域，假设派送时间关于订单数量的函数为
这里为在货仓的启动时间，为每一个订单的派送时间，为路程中所花的时间。如果我们把这个服务区域划分为个同等大小的子区域，那么每个区域中的订单到达率将从1减少为，对每个子区域而言，派送时间关于订单数量的函数为
在-子服务区域的情况下，如果每个子区域的订单可以通过一辆车执行一次派单完成，那么派送件订单的总时间为：
注解：上式中的后两项表示一辆车在一次派单中服务个订单所需要的服务时间和路程时间。
因此，如果 (1) MVP使用了辆车，(2) 我们可以把区域划分为个子区域，(3) 每个子区域的订单可以通过一辆车执行一次派单完成，那么划分区域将是有效的 (相当于把串行派单改成了并行派单)。但是，不同的分区策略下，系统所需的车辆数目可能比大，也可能比小。因此，当MVP使用了辆车，但我们需要把区域划分为个子区域才能保证每个子区域的订单可以通过一辆车执行一次派单完成，那么这时候就需要考虑是否值得添加的车辆（这会增加开销）来节省派单时间。
4-2 停止接单时间（Cutoff Time）
在最优配送方案中，最后一辆车最早可能返回仓库的时刻与服务最晚结束时间之间可能会存在间隔——这意味着最后一辆车的使用可能时不够充分的，因为它本可以服务更多的订单。从系统利润的角度，系统设计师可以 (1) 缩小停止接单时间以使用更少的车辆，从而降低成本，或者 (2) 增加停止接单时间 让最后一辆车服务更多的订单，从而提高收益。
这里，我们固定服务停止时间，订单派送时间函数 ，以及派单规模的下界 ，让接单停止时间 在 范围内变化， 是外生的。
我们假设所获得的收益与接单停止时间/订单总数 成正比，比例为, 同时运营成本也是接单停止时间/订单总数的函数，记为。我们想通过选择停止接单时间来最大化利润（第一项为收益，与订单数量成正比；第二项为运作成本），即解决如下优化问题（P2）
4-2-1 无限车辆系统
MVP告诉我们，如果最优策略使用 辆车，那么前 辆车将恰好在时刻 返回货仓。如果停止接单时间 被选择得很巧妙，那么最后一辆车也将在时刻 返回货仓。
现在我们记 为以下情况的停止时间：MVP使用 辆车，并且每辆车都恰好在时刻 返回货仓，。于是我们有如下的递推公式 ， 这里 唯一求解了 。定义 。
作者证明了在无限车辆系统里，(P2) 的最优解属于集合。 基于上述结论，我们可以方便地选择最优的接单截止时间。例如，图4中 ，我们可以求解出 , 其中。比较对应的利润，, , , ，我们可以发现这个例子下最优的接单停止时间为。
4-2-2 单车辆系统
对于单车辆系统，我们需要增加限制 。定义 为当 时所需的派单数量，定义为如下情况接单停止时间的上界： 对任意的， SVP仅要求一次派单。
作者证明了在单车辆系统里，若 并且 ，那么(2)的最优解属于集合 。 同样地，单车辆系统的最优接单截止时间也可以很方便地计算得到。例如，下图中 , , , 并且对应的利润为, , ，于是这个例子中的最优接单截止时间为。
除了对服务区域的划分和派送车队的规模，以及接单截至时间的分析外，作者还探究了其它的策略性设计：（1）服务伊始有遗留订单/预订单时，如何设计最优配送方案，（2） 每辆车的服务订单有上限时，如何设计最优配送方案。作者还进行了案例研究，对比了利用连续近似估计的和使用求解器通过整数规划求解出的派单时间，验证了连续近似方法的估计准确性。
5 结语
这篇文章对当日可达系统设计了一个简单的订单配送模型，并利用连续近似方法估计了系统的订单派送时间。值得一提的是，连续近似方法在对模型的简化中功不可没。作者刻画了无限车辆系统和单车辆系统下的最优配送方案，并对一般有限车辆系统提供了启发式配送方案。这些配送方案在实际应用中都仅需要简单的计算。案例研究表明，文章所提出的模型能够将平均服务订单数和派单时间的预测误差控制在1%以内。
基于简单的模型和容易计算的最优配送方案，作者首次探究了一些策略性的设计问题，例如如何选择车队规模，如何确定订单截止时间，以及如何将当日可达系统和隔夜订单交付操作相结合。这为OM社区研究SDD系统的策略性设计提供了很好的范例。
参考文献
Beardwood, J., Halton, J. H., & Hammersley, J. M. (1959, October). The shortest path through many points. In Mathematical proceedings of the Cambridge philosophical society (Vol. 55, No. 4, pp. 299-327). Cambridge University Press.
Stroh, A. M., Erera, A. L., & Toriello, A. (2022). Tactical design of same-day delivery systems. Management Science, 68(5), 3444-3463.
微信公众号后台回复
加群：加入全球华人OR|AI|DS社区硕博微信学术群
资料：免费获得大量运筹学相关学习资料
人才库：加入运筹精英人才库，获得独家职位推荐
电子书：免费获取平台小编独家创作的优化理论、运筹实践和数据科学电子书，持续更新中ing...
加入我们：加入「运筹OR帷幄」，参与内容创作平台运营
知识星球：加入「运筹OR帷幄」数据算法社区，免费参与每周「领读计划」、「行业inTalk」、「OR会客厅」等直播活动，与数百位签约大V进行在线交流
文章须知
推文作者：吕贤
责任编辑：薛桂琴，张云天
微信编辑：疑疑
文章由『运筹OR帷幄』原创发布
如需转载请在公众号后台获取转载须知
关注我们
FOLLOW US
