带有时间约束与惩罚的在线订单配送研究

武小平 孙靖

客户提出订货需求后，供应商需要按订单将产品配送给他们。在现实情况下，由于客户的需求是随机提出的，在任意时刻，供应商并不知道客户何时提出订货需求和订单大小，只有当订单到达后，这些信息才能知道，称这样的问题为在线问题，评价在线算法的性能，常常利用竞争分析的方法[1]；衡量在线算法性能的最广泛接受的方法是竞争分析。 某种在线策略的质量由在线算法对一系列请求所需的时间与事先知道该序列的算法所需的最佳时间之间的最坏情况比率来衡量，该比率称为在线算法的竞争比率。因此，如果每个输入的完成时间最多是算法的ρ倍，则该算法称为ρ竞争。想象一下一个配送员不必满足所有要求，但是有一个满足已接受要求的截止日期。通常延迟的服务会导致客户不满意，因为心理学研究表明人们倾向于估计等待时间[2]。对于在线配送问题，Igor以所有订单的总流时间（订单到达至配送给客户这段时间）和配送费用之和最小为目标，在假设配送能力无限时，对于只有一个客户的情形，采用SRPT（Shortest Remaining Processing Time）最优加工策略加工订单，同时设计了竞争比为2的最优在线策略，对于有m个客户情形，给出了竞争比为2m的最优在线策略[3]；随后他又研究了配送能力有限的情形，分别讨论了权重都为1且具有一定加工时间、权重互不相等且加工时间为0、以及订单先到先配送的问题，给出了相应的在线调度策略并给出了竞争比[4]；对于在线旅行商TSP问题（Travelling Salesman Problem），马军平等针对需求事先无法预知并且每个需求服务时长不确定的情形，提出具有服务时长的在线TSP问题，给出在一般网络上PAH-ST算法和直线上的PQR-ST算法，并计算了它们的竞争比[5]。温新刚等研究了预知信息的在线Nomadic TSP问题，分析了需求可提前被预知但不能立即接受服务的情形，即需求揭露时间和释放时间不同的情形，给出在一般网络和直线上的在线策略，结果表明，获取的信息越多，在线策略的竞争性越好[6]。廉文琪等考虑快餐店在提供外送服务时，可选择性提供送餐服务的情形，提出基于预知信息和实时服务选择的在线TSP问题，分析了需求在正半轴和直线上的情形[7]。以上研究仅仅要求订单配送给客户即可，并没有配送时间的限制。订单在供应商处延迟不受限制，这与现实不相符，例如，很多网购行为中，供应商收到订单后必须在规定的时间把产品送到客户手里，否则就会降低信用度或丧失很多潜在客户。本文就是在这种实际背景下，结合已有经典研究，提出了带有时间约束与惩罚的在线订单配送问题。

问题描述与基本假设

问题描述：

揽件员从起点到终点 e过程中，既承担揽件任务，也承担将货物配送至客户所要求的地点（即终点 e）的任务，订货需求随机产生。为了节省费用，某些订单需求产生之后，不用立刻配送至终点 e，而是同后来的订单一同配送，订单需求产生未及时配送的产品存在等待时间（即订单产生后到配送这一段时间），而且客户对货物到达时间有一定的要求，如何权衡这两者之间的矛盾，使得总费用尽可能小呢？即以所有产品等待的时间和配送费用之和最小为目标，如何优化带有时间约束的配送问题。

基本假设 ：

1） 只考虑有一辆服务车的情况，令其行驶速度为1；

2） 载重车辆载重能力不受限制，即一次可以配送所有加工完未配送的产品；

3） 每一份订单不能因配送而被分割（即不能配送订单的一部分）；

4） 服务请求一旦被接受就不能被取消；

在线策略设计与竞争分析

（西安郵电大学现代邮政学院）

参考文献：

[1] K.Pruhs， J.Sgall， E.Tong. Online scheduling，in：Joseph Y.-T. Leung（Ed.）， Handbook of scheduling：Algorithms， Models， and Performance Analysis， CRC Press， 2004，15：1-15， 41（Chapter 15）.

[2] Katz K， Larson B， Larson R （2003） Prescription for the waiting-in-line blues entertain， enlighten， and engage. Oper Manag Crit Perspect Bus Manag 2：160

[3] Igor Averbakh， Zhihui Xue. On-line supply chain scheduling problems with preemption[J].European Journal of Operational Research ， 2007， 181： 500-504.

[4] Igor Averbakh. On-line integrated productiondistribution scheduling problems with capacitated deliveries[J]. European Journal of Operational Research ， 2010， 200：377-384.

[5] 马军平，徐寅峰，陈聪，等.具有服务时长的在线TSP问题[J].系统工程理论与实践， 2015， 35（11）：2832-2839.

[6] 温新刚，徐寅峰，丁黎黎.基于预知信息的占线Nomadic TSP问题[J].系统工程理论与实践，2013，33（1）：1-7.

[7] 廉文琪，徐寅峰.基于预知信息和实时服务选择的在线TSP问题[J].系统工程理论与实践，2016，26（1）：88-95.

[8] 吴腾宇，陈嘉俊，蹇洁，等.O2O模式下的配送车辆实时取送货路径选择问题[J].系统工程理论与实践，2018，38（11）：167-173.[9]吴腾宇，徐寅峰，温新刚.预知信息和有限运载能力下应急车辆路径选择问题[J].系统工程理论与实践， 2015， 35（5）：1224-1229.