1 引言 随着人们对外卖需求的日益增加和对外卖配送时效的要求不断提高，餐饮外卖企业的竞争也愈发激烈，现阶段的O2O配送平台，如美团、饿了么等，顾客通过O2O平台下单，商家通过平台接受实时的需求订单后，将取送货地点，货物种类和数量等配送订单信息推送给配送员。而配送车辆一般的工作流程是，配送员从商铺取到货物后，随着顾客需求的不断出现即时调整车辆的行驶路线，配送车辆根据订单信息凭借经验选择多个顺路订单并自行进行路线规划，进而导致配送车辆为了保证配送时间一单一送，或为了同时配送多单而牺牲客户满意度等资源浪费、效率低下的现状。因此，为了提升配送车辆的配送效率和客户满意度，本文通过设计在线算法为配送车辆实时提供多个订单的合单配送及路径规划的策略。在现实的外卖配送服务中，配送车辆应该尽快地对每一个需求点进行服务，而每个顾客的需求往往不同，因此配送车辆需不断地往返于需求点和商铺之间取送货，这种要求服务器返回原点，并且以服务完所有需求的总时间最小为目标的问题可以用带有取送货的在线旅行商问题来描述。与一般TSP问题相比，这个服务过程具有二点特殊性：第一，顾客需求具有在线性，在O2O平台上，终端客户在线上进行订餐，顾客的需求信息对于配送车辆是实时获知并且顾客需求是序贯到来的。因此，当出现新需求时，配送车辆只能根据当前的情形决定下一步行动方向。第二，顾客需求具有差异性，即取送的货物与顾客之间是一一对应的关系。因此，当配送车辆在服务的过程中出现新的服务需求时，配送车辆均需返回原点取货再进行下一轮的配送。尽管TSP问题的研究成果较多，但是同时考虑上述两个特征时应该如何建模求解，还有待深入研究。因此，本文提出带有取送货的在线TSP问题，设计在线算法并分析算法的竞争性能，该研究对于一般在线TSP问题进行扩展，并可以对O2O平台中外卖配送车辆的科学调度提供理论支持。 对于O2O模式下的车辆配送问题。国内学者的研究还比较少，赵泉午等[1]研究了服装鞋类连锁经营企业实施O2O转型面临的城市配送网络优化问题，建立以总成本最小为目标函数的城市中心店选址及末端需求点分配联合优化模型。赵泉午等[2]对该问题进行了拓展，研究了O2O背景下大型零售企业城市配送网络优化问题，构建了中转中心选址及末端需求点分配联合优化模型。陈萍等[3]基于传统的取送货车辆路径问题，考虑餐饮O2O外卖客户满意度的特点，提出了基于客户满意度的O2O外卖配送路径优化问题，并用启发式算法进行有效求解。但是这些研究均未考虑在O2O平台中需求产生的不确定性。而对于需求的出现是无法确定的TSP问题，往往采用在线方法进行分析。Ausiello等[4]在2001年最早提出在线TSP问题，设计了直线上和一般网络上的在线算法，进行了竞争分析，并针对服务器是否返回原点进行分析，得到了相应的竞争比。Yu等[5]研究了服务完所有需求无须返回原点的在线旅行商问题(online nomadic TSP)，针对正半轴网络和一般网络进行了竞争分析，并设计了最优的在线算法。Wen等[6]考虑了带有服务选择和时间窗的在线旅行商问题，并在线段上设计了相应的在线算法。温新刚等[7]研究了带有预知信息的nomadic旅行商问题，并分析了预知信息对于结果的改进。廉文琪等[8]研究了在线送餐情形下的车辆路径选择问题，但其并未考虑顾客需求的差异性。而在现实的外卖送餐服务中，顾客需求通常具有差异性，因此还需考虑取送货的情形。Ascheuer等[9]考虑了在线拨号叫车问题(online dial-a-ride problem，OLDARP)，在该问题中，网络中的任意一点均可作为取货点，设计了三个在线算法(REPLAN，IGNORE和SMARTSTART)用于求解车容量为1，目标函数为最小化完成时间的OLDARP。Feuerstein和Stongie[10]研究了OLDARP的两个目标，最小化服务完最后一个订单的时间和最小化服务所有需求点的时间之和。Hauptmeier等[11]研究了带有时间窗的OLDARP，并给出了两个在线算法REPLAN和IGNORE。在该环境中时间和到达的需求数量是无限的。他们考虑了最小化平均的客户等待时长的目标函数。Lipmann等[12]研究了不完全信息下的OLDARP，即当一个需求订单出现时仅获知原点而不知道终点的信息，只有在车辆开始服务该需求并到达原点时才获知终点的信息。在以上的OLDARP中，均考虑的是任意一个节点作为取货点，而现实O2O模式下的外卖配送服务中，配送车辆取货的商铺不可能是网络中的任意一点，并且商铺所在的位置都比较集中，因此研究取货点为网络中固定的点更有现实的意义，而在这种情形下，如何设计相应的在线算法，以及算法的竞争性能如何，目前尚未有相关的研究。 本文研究了带有取送货的在线旅行商问题，即在线服务器需返回原点取货情形下的在线配送车辆的路径选择问题。如果网络上任意点都可以作为取货点，那么就是一般的OLDARP问题，而如果不考虑返回原点取货的情形，则本问题就转化成一般的在线旅行商问题。因此，本文研究的问题从两方面都更符合现实的O2O模式下的外卖配送情形。本文首先构建了在正半轴上的一个特殊情形，得到了该问题在正半轴的竞争比下界，并且给出了TAIB算法，通过数理分析得到了该算法的竞争比。然后对于一般网络的情形，得到了该问题在一般网络上的竞争比下界，接着给出了IGNORE算法，并得到该算法的竞争比。最后通过一个算例说明该算法在现实中的可行性。 2 问题描述与基本定义 本文的假设和问题定义如下： 给定一个网络图M，需要服务的需求点均位于网络图M上。将出现的需求i表示为
，i∈N，其中N=(1，2，…，n)，n为需求的总数量。
表示需求i在网络图中的位置，
表示需求的释放时间，即顾客通过平台下单的时间。在网络中，只考虑一个配送车辆(即服务器)进行服务，每出现一个新需求时，配送车辆都需返回原点取货后才能服务该需求(即在线服务器和离线服务器均只能在需求释放以后从原点取货)。假设所有需求服务的时间为零，当配送车辆经过了该节点即服务了该需求。零时刻时，配送车辆位于指定原点o，行驶速度为单位速度，服务完所有的需求即可，并不需要返回原点。本文考虑的带有取送货的在线旅行商问题，即配送车辆在时刻
才获知需求i的信息
，在i∈N的情形下，如何进行路径选择使得服务完所有需求的时间尽可能小。
