物流服务供应链任务分配问题研究

王芝泉，刘晋浩

(1.东北林业大学工程技术学院，哈尔滨150040;2.北京林业大学工学院，北京100083)

目前，对供应链的定义有多种，其中比较权威的是我国在2001年发表的物流术语国家标准中的定义:“生产及流通过程中，涉及将产品和服务提供给最终用户活动的上游与下游企业，所形成的网链结构”［1］。根据以上定义，供应链的内涵不仅包括提供产品 (产品供应链)，还包括提供服务 (服务供应链)。物流服务供应链是服务供应链中的一种，具有服务供应链的一般特征。田宇 (2003)认为其基本结构是:功能型物流服务提供商→物流服务集成商→制造、零售企业，其中功能型物流服务提供商是指传统的功能型物流企业，如运输企业、仓储企业等，它们因提供的服务功能单一、标准，业务开展往往局限于某一地域，而被物流服务集成商在构建全国甚至全球服务网络时吸纳为供应商，它们利用自身物流能力，帮助物流服务集成商向客户提供物流服务［2］。一般来说，物流服务集成商通常拥有众多的功能型物流服务提供商。物流服务集成商在得到客户需求后，根据客户需求将物流服务订单分配给各个服务提供商，由各个服务提供商提供相应的物流能力完成物流服务。这个过程就是物流服务供应链的任务分配过程。Suman和Patrick(2004)指出，任务分配决策是供应链战略中最重要的决策之一［3］。面对多个物流服务提供商时，物流服务集成商如何进行需求订单任务的合理分配是保证物流服务供应链长期稳定运作的关键。

1 物流服务供应链任务分配特点分析

物流服务供应链的任务分配就是由物流服务集成商将物流服务订单分配给各个物流服务提供商，以使物流服务供应链的整体效益最优。物流服务供应链任务分配过程是一个不确定性环境下的序贯决策。具体来说，物流服务供应链任务分配具有以下特点:

(1)物流服务供应链任务分配是集中式运作。供应链中的成员相互合作，追求的物流供应链整体效益的最优。集中式运作意味着存在一个管理者或协调者，即物流服务集成商，该管理者拥有供应链中所有的决策信息，负责从物流服务供应链的整体效益最优角度制定决策，并将决策方案通知给供应链中的各个物流服务提供商。

(2)物流服务供应链任务分配环境具有不确定性。这种不确定性，一方面是由于外部环境的变化接到新订单，另一方面是由于内部资源能力的限制，以前分配出去的任务执行失败。面对每个新订单的到来和分配完的订单的执行失败，物流服务集成商都需要不断地进行任务分配和再分配。

(3)物流服务供应链的任务分配过程是一个序贯决策。序贯决策是指决策者 (物流服务集成商)在每个观测点上 (出现新订单或订单执行失败)都要进行决策 (任务分配或再分配)，决策时不知道下一个观测点上的决策信息［4］。一般来讲，序贯决策不仅需要当前决策的即时效应，还需要考虑当前决策对未来的影响，为将来决策创造机会。

(4)物流服务供应链任务分配具有马尔可夫性。马尔可夫性是指一个随机过程未来发展的概率规律与观察之前的历史无关的性质，也就是说物流服务供应链任务分配决策只与物流服务提供商的最多可接受任务量以及目前已接受的任务量有关。

2 基于MDP的物流服务供应链任务分配模型

马尔可夫决策过程MDP(Markov Decision Processes)是指决策者周期地或连续地观察具有马尔可夫性的随机动态系统，序时地作决策。即根据每个时刻观察到的状态，从可用的行动集合中选用一个策略。系统下一步 (未来)的状态是随机的，决策者根据新观察到的状态，再作新的决策，依此反复地进行。马尔可夫决策过程常用来解决动态规划中的序贯决策，同时由于物流服务供应链任务分配过程的特点符合马尔可夫决策过程的要求，因此物流服务供应链任务分配问题可用马尔可夫决策过程建模求解。

2.1 前提假设

为了简化这类问题的研究，做出如下假设:

假设1:任务空间的结构是明确的。各类任务都可以统一表达为分解任务，即用简单任务及其相互依赖关系表示。被分配的任务都是已分解完成的任务，这些分解任务的类型有限。各类分解任务对应某一固定报酬。其中的简单任务都只能由一个物流服务提供商单独完成。

假设2:成批出现的任务服从相同的概率分布。由于物流服务供应链外部环境和内部成员资源能力的变化，随时都可能出现需要分配的任务，且这些任务可以被分解，用简单任务及其相互关系表达。这些分解后的简单任务视为同批出现，它们具有相同的到达时间和到达概率。

假设3:物流服务提供商对它所分得任务的处理按先来先服务原则。由于物流服务提供商可能会在一批任务的分配时接受多个任务并且不等这批任务处理完毕，又可以接受新的任务。这样就形成了各物流服务提供商的任务队列，且各物流服务提供商按队列中任务出现的先后序进行处理。

2.2 模型构建

基于前文对物流服务供应链任务分配特点的分析可知，物流服务供应链任务分配具有马尔可夫性，即任务分配决策只与物流服务提供商的当前状态有关。当前状态包括被分配任务的特征和各物流提供商的任务执行能力两项内容。每批出现的任务都可以表达为分解任务，即用简单任务及其相互依赖关系表示。每个物流提供商具有不同的任务执行能力。任务执行能力由物流提供商的当前可接受的任务量和当前要执行的任务量来共同决定。状态的转移也包括被分配任务的特征转移和各物流提供商的任务执行能力转移。由于同批任务的具有相同概率分布，被分配任务特征的转移概率与任务分配的策略无关，只取决于决策时刻该批任务的概率分布。由于各物流服务提供商的可接受的最大任务量在一定时间内是一定的，各物流提供商的任务执行能力转移概率只与要执行的任务量和任务执行速度有关。每个物流服务提供商能接受的任务数受自身任务执行能力的限制。物流服务集成商在不同状态下将出现的任务实时地分配给合适的物流服务提供商，以实现物流服务供应链绩效最大化。完成每一项任务所获得的收益，取决于完成任务所得的报酬与所消耗的费用。每一类型的任务都有固定的报酬。任何一项任务的完成都需要消耗一定的费用，包括执行费用和通信费用。执行费用是与物流服务提供商要执行的任务量有关的费用，它随着需要执行的任务量的增加而增大;通信费用是因为简单任务之间相互依赖物流服务提供商之间协商产生的费用，它取决于相互依赖任务的通信量和对应物流服务提供商之间的单位通信费用，而物流服务提供商之间的单位通信费用通常由物流服务供应链的结构决定，只有存在连接的两个物流服务提供商能通信。

MDP马尔可夫决策过程通常被表示为:{S，A(s)，p(s'/s，a)，r(s，a)，V}。其中:S 是状态空间;A(s)是行动空间;p(s'/s，a)是状态转移概率函数;r(s，a)是报酬函数;V是准则函数［5］。物流服务供应链的运作具有长期性，考虑到资金的时间价值，因此应以在无限时段上完成任务获得报酬的净现值作为任务分配决策的准则。基于上述分析，物流服务供应链的任务分配模型构造如下:

(1)式的含义是最优任务分配策略是在完成任务所获得收益的净现值最大时取得。

(2)式的含义是任一简单任务只由一个物流服务提供商完成。

(3)式的含义是物流服务提供商接受的任务量受其任务执行能力限制。

其中，β为折现因子;a*为最优任务分配策略;xikt=1表示t时刻第i项任务被分配给第k个物流服务提供商;xikt=0表示t时刻第i项任务没有分配给第k个物流服务提供商;s表示状态，s=b×w，b表示物流服务提供商的任务执行能力，w表示被分配任务的特点，记φk为第k个物流服务提供商的当前可接受任务量，lk为当前要执行的任务量，则t时刻第k个物流服务提供商的能力可表示为 bkt={＜ φk，lkt＞ /lkt=0，1，2，…，φk}，用 Vi表示简单任务组成的集合，Ei为所有简单任务构成的相互依赖关系集，则t时刻第i个物流服务提供商的任务执行能力可表示为Wit={Vit，Eit};r(s，a);为报酬函数，表示物流服务供应链采取任务分配策略a所获得的收益，用R(Wt)表示完成任务Wt所获得的报酬，C 1t表示执行费用，C2t表示通信费用，则rt(s，a)=R(Wt)-C1t-C2t，其中，qkt为t时刻第k个物流服务提供商要执行的作务量;j)fk，lxiktxilt，E(i，j)=1 表示第 i个任务和第 j个任务相互依赖，E(i，j)=0表示第i个任务和第j个任务相互不依赖，fk，l表示第k个物流服务提供商与第l个物流服务提供商之间的通信费用;pr(s'/s，a)为状态转移函数，可表示为pr(s'/s，a)，其中vk为各物流服务提供商在任意时段上的任务执行速度，h(vk):lk，t+1，表示下一决策时刻的要执行的任务量。

3 基于迭代算法的模型求解

从根本上讲，基于MDP的物流服务供应链任务分配模型是一个动态规划模型，可以利用求解动态规划的迭代算法得到任务分配的最优策略。迭代算法的基本思想是:通过迭代逐步逼近最优准则值，随着迭代次数的增加，所得的结果越来越接近最优准则值。从理论上讲，迭代算法可进行无限次，但在现实应用中通常设定终止条件，选取有限步的计算结果，作为近似最优。具体步骤如下:

(1)选取初值:对∀s∈S，令V0(s)=0，并给定一个充分小的正数ε。

(2)计算Vn+1(s)，Vn+1(s)∈ma{r(s，a)+β∑p(s'/s，a)Vn(s')}。

(4)对∀s∈S，选取最优任务分配策略a*，并终止算法。最优任务分配策略a*就是使物流服务供应链完成任务所获得报酬净现值最大的任务分配策略，即满足at(s)∈arg max{r(s，a)+β∑p(s'/s，a)Vn+1(s')}。

4 实验仿真及结果分析

4.1 实验设计

(1)实验目的。比较三类任务分配策略对物流服务供应链绩效的影响，检验基于MDP模型最优任务分配策略的有效性。三类策略是:随机任务分配策略、即时最优任务分配策略和基于MDP模型的最优任务分配策略。随机任务分配策略就是当任务出现时，从对应状态下的任务分配行动空间中等可能地选取任务分配方案;即时最优策略是当前任务负载状态下的最优任务分配策略，以指导系统按眼前最优策略行动;基于MDP的最优任务分配策略就是从系统存在的长远意义出发，考虑一段时间上的总收益最优。

(2)实验原理。一般认为，任务分配的较好策略是根据当时系统的状态确定的，应当是即时最优策略;较差的策略是随机任务分配策略，因为随机策略不考虑系统完成任务的绩效。因此，可以通过与即时最优策略和随机策略的比较来判断基于MDP模型的最优策略的有效性。

4.2 实验结果

当状态数较多，不便列举出整个求解结果时，可采用仿真实验方法证明任务分配MDP模型的有效性。仿真试验进行1 000个时段，在相同的实验条件下重复执行20次，每50个时段记录一下从初始化状态到当前为止系统执行任务的报酬净现值。实验结果如图1所示，基于MDP的任务分配模型和即时最优策略明显优于随机策略;同时，还可发现基于MDP的任务分配策略也优于即时最优策略。

图1 仿真时段Fig.1 Simulation Section

实验结果表明，基于MDP的最优任务分配策略是有效的。这是因为基于MDP的最优任务分配策略不仅考虑了任务分配对即时所得报酬的影响，还考虑了任务分配对系统长远报酬的影响。即时最优策略虽然在当前状态下是最优的，但它可能会因为追求当前报酬的最优而导致下个时刻资源的不足，产生大的损失。

5 结论

物流服务集成商如何进行需求订单任务的合理分配是保证物流服务供应链长期稳定运作的关键。由于新订单不断出现及旧订单执行失败，物流服务集成商要实时地进行任务分配和再分配。在实际操作中，物流服务供应链任务分配具有随机性，任务分配过程是一个复杂的不确定环境下的动态决策过程。本文从分析物流服务供应链任务分配的特点出发，基于物流服务供应链任务分配具有集中运作性、决策过程的序时性及马尔可夫性，提出用马尔可夫决策过程构建物流服务供应链任务分配模型。最后给出了基于迭代算法的模型求解过程。由于求解过程中最优解的获得可能要经过很多次的迭代，而物流服务供应链的任务分配应在任务出现时实时地进行分配，因此提出在模型实际求解中，可以在设定终止条件下，用迭代算法求出近似最优解。

［1］蔡云飞，邹 飞.物流服务供应链及其构建［J］.企业改革与管理，2006，13(1):17-18.

［2］刘伟华，季建华，顾巧论.物流服务供应链两级合作的质量监控与协调［J］.工业工程与管理，2007，11(3):47-52.

［3］刘伟华.物流服务供应链能力合作的协调研究［D］.上海:上海交通大学，2007.

［4］刘成钢，宁宣熙.变动市场环境下的马尔可夫决策［J］.南京航空航天大学学报，2002，34(5):505-508.

［5］李江洪，韩正之.马尔可夫决策过程自适应决策的进展［J］.控制与决策，2001，16(1):7-11.

［6］杨 波，薛 伟.区域物流分流动力学仿真研究［J］.森林工程，2009，25(1):81-86.