文章编号：1003-207(2020)08-0114-13 1 引言 近年来，我国城市配送需求快速增长。2019年，我国快递包裹数量达到635.2亿件，人均包裹数量约45.37个[1-4]。日常普惠的通用型城市配送需求基本得到了满足。各种定制化配送需求逐渐涌现[5-7]，包括配送时间窗[8]、末端交付方式[9]、多温区[10]等。例如，天猫、京东等网上超市开始为顾客提供可选时间窗的配送服务；顺丰速递开始建立“丰巢”自提点服务体系，既提供送货上门交付，也向顾客提供自取和自助寄件服务；多温区配送在国内多见于B2B环节，B2C情景下方兴未艾，英国ASDA、TESCO等超市已经娴熟地进行多品类、多温区杂货配送。 顾客可以自选末端交付方式和时间窗对城市配送订单接受决策带来了挑战。其中，常见的末端交付方式包括：送货上门(Attended Home Delivery，AHD)、自提柜(Reception Box，RB)和自提点(Collection and Delivery Points，CDPs)等[1-2]。自提柜或自提点服务范围限制了顾客对末端交付方式的选择；配送车辆及路径决定了配送的到达时间。在订单接受决策中，已接受的订单集合形成了配送路径的硬约束，须使用既有的自提设施和规划的配送路径满足约定的交付方式和配送时间窗；现有设施布局和配送路径形成了未来可接受订单的软约束，制约着可接受订单的区域、交付方式及时间窗等属性。订单接收决策需要考虑“接受订单—路径更新—约束下一个订单的接受”的动态影响关系。可选末端交付方式和时间窗下城市配送在线订单接受决策将更为复杂。 本文的研究涉及时间窗管理(Time Slot Management，TSM)。时间窗管理主要讨论送货上门交付下时间窗分配、时间窗宽度影响、时间窗定价等问题。对于时间窗分配问题，可以分为静态时间窗分配和动态时间窗分配两种情况。静态时间窗分配是指时间窗分配策略在整个订单接收周期保持不变。例如，Agatz等[12]研究了时间窗顺序计划问题模型(Time Slot Schedule Design Problem，TSSDP)。Agatz等[12]研究了静态情形下时间窗在地理位置上的分配问题。相对的，动态时间窗分配是指时间窗的分配策略会进行调整，消费者行为的刻画是其中的重要问题之一，通常使用离散选择模型进行讨论。Bent和Van Hentenryck[13]通过优化时间窗的分配，实现利润最大化，但是没有考虑拒绝一些服务成本较高的订单；Campbell和Savelsbergh[14]在上述研究的基础上，考虑拒绝某些服务成本较高的订单，并提出了DSR、DIFF、PATH、REG四种路径插入方法。Ehmke和Campbell[15]以配送订单数量最大化为目标，在交通通行时间随机的情况下讨论了几种城市配送订单接受策略。对于时间窗宽度的影响，Punakivi和Saranen[16]的研究表明：弱时间窗约束能够提高收益，完全无时间窗约束能够使总收益提升1/3左右；Campbell和Savelsbergh[14]研究发现将一个小时的时间窗延长为两个小时可以提高总收益6%。对于时间窗定价，较早的研究可以参考Campbell和Savelsbergh[17]。陈淮莉等[8]建立了考虑订单交付期约束并均衡配送能力的多时隙定价模型。总体上看，时间窗管理的研究是面向送货上门的。然而在中国城市化进程中，城市居民多以积聚性居住为主，收件箱或自提点方式更符合中国的实际情形。对于多种末端交付模式下时间窗管理的研究还较少。 鉴于此，在顾客可以自选末端交付方式和时间窗的情境下，本文将构建城市配送动态订单接受决策框架，基于利润最大化目标，设计城市配送订单接受策略调整算法，重点分析不同算法在收益、行驶距离、耗费时间等方面的差异，为顾客可选末端交付方式和时间窗情境下城市配送动态订单接受提供参考。 2 问题分析 城市配送服务供应商为顾客提供配送服务。顾客集合记为N[，c]。顾客i的位置是(x[，i]，y[，j])、相互之间的路径距离是d[，ij](i，j∈N[，c])。供应商为顾客提供两种末端交付方式：送货上门交付，记为AHD交付；自提柜交付，记为RB交付，并提供某个日期T的配送时间窗集合(以下记为SLOT)供顾客选择，例如9：00-10：00、12：00-13：00、14：00-15：00等。顾客i按照实际时间随机到达，基于自身效用最大化，选择末端交付方式d，d∈{RB、AHD}，并从SLOT中选择配送时间窗s，确定接受服务的最早时间early[，i]和最晚时间late[，i]，产生配送需求。 城市配送服务供应商从时刻0开始接受下一批次配送订单，在时刻T停止接受本批次配送订单，时间段[0，T)为订单接受时段。记时间段[0，t]内已经接受的订单集合为A[，t]，A[，t]={(i，d，s)：i∈N[，c]，d∈{RB、AHD}，s∈SLOT}，t∈[0，T]。在时刻T，供应商开始进行配送。记顾客i在时刻t产生的配送需求为r[，ti]。根据收益最大化目标，供应商需要制定相应的订单接受策略(记为Θ[，t])，检查面向A[，t]∪{r[，ti]}订单集合的配送路径可行性和收益大小，快速决定是否接受新配送需求r[，ti]：若接受，则转为配送订单，纳入订单集合A[，t]，获取服务收益；否则，拒绝接受配送需求r[，ti]。 根据问题描述，进行如下假设： 假设1 时段[0，T)内，配送需求r[，ti]是独立到达的，满足到达强度λ的齐次泊松过程。 假设2 根据泊松过程的性质，将时段[0，T)分成M个时段，每个时段[t[，i]，t[，i+1]](i=0，1，2，3，…，M，其中t[，0]=0，t[，M]=T)足够短，使[t[，i]，t[，i+1]]内至多只有一个配送需求到达，产生的配送需求总量为M个。 假设3 对于配送需求r[，ti]，p[，ds]表示选择末端交付公式d和配送时间窗s的概率，满足
p[，ds]=1。
