租车市场充盈条件下货运车队构成优化的探讨

何 彤

（广东技术师范大学 管理学院，广东 广州 510665）

由于货车租赁市场及其相关物流信息技术的迅猛发展，从外部市场租赁货车来补充企业自有车队运力的不足，已经极为便利并可降低固定资产投入和运输成本.故此，目前货运行业已经普遍采取自有与租赁车辆相结合的货运车队组合策略，其运营优化的主要方式是车队组合构成优化及运输线路优化[1].目前国内外对后者的研究较多而对前者的研究很少，有必要做更为深入的探讨.

车队构成优化的难点就是自有车队应该购置多少辆车和配置哪些车型，以及如何判断在何种情况下应从租车市场租用货车？由于具体到某一天的运输需求量一般都是随机的，相应的运输车辆需求数量也就随机变化.对于车队而言，自有车辆多而运输需求量少时，会出现车辆闲置；而在自有车辆少而运输需求量多时，就需要从外部企业租赁车辆来满足需求，但租赁车辆的变动成本更高，其服务水平也往往低于自有车辆.当需求集中在少数几个客户点时，为使可变成本最小化，企业倾向于使用大型车辆来运输，因为在可变成本方面大型车比小型车更有效率，诸如燃油和司机工资等方面；而如果同样数量的需求被均匀地分布到大量的客户站点上，则倾向于使用众多小型车辆来运输.所以，如何确定自有车队最优规模和构成，使其在借助车辆租赁市场的情况下，既满足客户需求又尽量降低车队运营成本，就成了货运企业经营管理所必须面对的问题.

为了帮助货运企业解决这一问题，本文提出了一个优化模型，其目标是在满足需求的前提下，在自有车辆的固定成本与租赁车辆的较高可变成本之间取得最优配置，并以成本最低作为评价标准，来判定和优化车队的构成.模型中对某一天的需求以要交付的总货物量和要访问的总客户站点数量来进行描述，由于需求空间简化为二维，就能够直接用数值积分来计算所需的梯度，并易于对每个积分域计算出相应的最优对偶向量以及最优基矩阵的逆.据此，本文构建了一个基于该二维特性需求的两级补偿线性规划，并提出一种利用标准梯度法进行连续优化的该模型的有效求解算法.

1 模型的建立与分析

本文模型参考了Eberly和Van Mieghem的研究结果[2]，但他们的模型中对于所涉及的多种资源中哪些车型应纳入车队的决策周期只有一个；而且本文模型的最优控制策略(即每种车型的最优数量)可以根据预期利润函数的梯度来定义，采用的补偿规划是一个所有系数都假定为正的、具有正分数覆盖约束的最小化问题.

设O为包含n1种车型的企业自有车型集合，设H为包含n2种车型的可租赁车型集合，总车型数量n=n1+n2.注意：如果某种特定型号货车既可从自有车队调用也可从外部租车公司租赁，由于其获取的成本不同，本文视其为两种不同的“车型”.用非负变量Q和S分别表示要交付货物总量和要访问的各客户站点的总数量，则规划周期内随机选取的某个工作日的货运需求D=(Q,S).

货运需求量还未明确时，车队一般都考虑优先使用自有车辆来满足货运需求，本文称之为事先决策；而把明确了某天的需求后，如何最好地利用自有和租赁车辆(运力补偿)来满足这天的需求称之为工作决策.设车队构成向量表示自有车队所拥有各种车型的车辆数量，则选择K就是事先决策；利用向量表示每种车型中要利用的车辆数量，即工作决策.在给定车队构成K和已知需求D=(Q,S)时，工作决策的最优成本为：

式中v'，q'，s'是对变量v、q、s的微分计算.

本文假设可从外部租赁的车辆数是无限的.

工作决策的预期成本是关于二元概率分布的整数集Z(K):=E[z(K,D)].这样可得到K≥0条件下的事先决策公式为：.在需求不确定的情况下，或者需求已知而且其变化符合二元概率分布，上述公式可将规划周期内的车队成本减至最低.

设t为规划周期中工作日的索引指标，T为规划周期内的工作日总数，P(t)=T-1表示第t天被选中的概率.随机向量D的分布表示规划周期中随机抽取的某个工作日需求，即Dt是第t天的需求量.这样，在规划周期中发生的预期总成本为向量K的函数：通过线性期望，即将上述函数乘以正常数T-1来最小化函数，可得：再通过运用总期望定律，它可归纳为本文模型的目标函数

2 模型的求解算法

在本节中，2.1小节先申明模型的前提假设条件，本文的确定性等价规划因此被保证为一个凸规划，并在可行集内部各处定义的梯度.2.2小节中参照带两个附加变量的补偿规划迭代公式，定义了补偿规划的基，并在可能需求范围内定义了基的可行域，以及与最优基对应的最优对偶向量.定义了补偿规划的“权威”基集合的概念，并阐明了该集合在一个标准梯度搜索算法中的作用.在2.3小节中，给出了生成补偿规划的一组权威基集合的算法过程，并对其正确性和多项式复杂度进行了论证.

2.1 前提假设

为简化对模型有效性的评估，本文假设下述前提条件成立：

假设2：非负随机变量D = (Q,S)具有有限二阶矩联合概率密度函数.

假设3：整个规划周期内，自有和租赁车型的单位使用成本和能力参数均为恒量，并且独立于车队构成和利用决策.

假设4：货运需求独立于车队构成和利用决策.

在假设1成立条件下，本文随机规划模型具有相对完整的补偿.优化模型（在K≥0条件下的可视为确定性等价规划，使得Z(K)内的随机性符合条件，对于任何可能的需求向量，不需要在K上添加约束来确保工作决策有一个最优解.在假设1和2成立的前提下，Birge和Louveaux已证明确定性等价规划是一个凸规划，且对可行集内的所有K都存在梯度[4].

2.2 “权威”的基集合

2.2.1 专用于补偿规划的基集合及其可行域和最优对偶向量

Bertsimas和Tsitsiklis论证了可使用具有上下界的变量来定义一个基[5]，本文依据其理论来构造一组用于补偿的专用基集合.用两个附加变量xq和xs重构以产生等式约束，通过将决策变量划分为三个集合来识别确定一个基：包含两个基础指标的集合B、从O中选取的保持在其上界的变量指标集合U、保持在其下界的变量指标集合L.本文还定义差额成本为，式中B-1是由前述最优成本等式系统的两个基本列所构成的方矩阵的逆，Ai是该系统中选定的非基本列.则一个最优基应满足的条件有两个：首先是其相关解是可行的，即基本变量都是非负的，在适用情况下，分别是的上界；其次对于每个i∈L是非负的，而对于每个i∈U是非正的.对于每一个基b，在可能需求范围内定义其相关可行域为：

对于Ωb中某些点的最优基b也是该域中每个点的最优.补偿问题的对偶性可表示如下：

如果b是Ωb的最优解，则在整个Ωb内部可获得唯一最优对偶向量.每当的第i分量可被视为对Ωb(K)内需求点处的最优成本的右偏导数.

2.2.2 “权威”基集合的定义及其梯度公式的应用

本文把满足以下三个关键条件的基集合B称为具有足够代表性的“权威”基集合：1）全面覆盖：对于每个K≥0都满足2）最优性：每一个基b∈B均是Ωb的最优解；3）不相交：对于每个K≥0和基对b1, b2∈B，Ωb1(K)和Ωb2(K)内部不相交.

而当B是一组权威基集合，且在假设1和2成立的前提下，对于每一个K≥0时必然有预期工作决策成本的梯度公式成立：

有了生成补偿问题的权威基集合的算法，就可以采用标准的梯度投影算法来进行优化了.而模型的目标函数及其梯度的计算也可以简化如下：在开始搜索算法之前，先使用本文算法生成一个权威集合B，并对于每个基b∈B，连同界定集合B、L、U一起存储相应基的逆矩阵B-1和向量；假设在梯度搜索算法中得到K≥0以及目标函数的梯度.且对于每个基b∈B，通过适当域密度函数的数值积分来获得P(Ωb(K))，则所期望梯度为；最后，在K≥0条件下求搜索算法的目标函数值.为达此目的，通过对需求空间进行数值积分来计算关于密度函数的期望值.在这一过程中，使用集合B、L、U和D∈Ωb(K)时相应于基b∈B的存储矩阵B-1，来评估在给定点D=(Q,S)的工作决策成本z(K,D).依次执行对域Ωb(K)的积分，就能立即知道哪些基参数适用于当前域的给定需求点.

注意：为了便于数值积分的目的，依据Birge和Louveaux的研究结果，可把理论上无边界的需求空间缩小到一个大的有界域，如此依然可以捕获几乎所有的概率质量[4].而鉴于决策的策略性和参数空间的低维性，也不需要采用复杂的数值积分方法.

2.3 为本文模型有效地生成“权威”集合的算法

下面说明生成权威集合B的算法.该算法可以自由地从公式中舍弃某些不需要出现在车队最优构成中的车辆类型，并用效率向量来表示某种车型的可变成本效率.根据假设1，这些向量的每一个都定义明确且两个分量均为正数.

2.3.1 算法过程：

步骤1排除明显不经济或不必要的车辆类型：

对于每种车型i1，判断是否有第二种车型i2满 足 条 件和.如果是，则排除车型i1.（理由在于用车型i2取代i1来满足需求时，其成本会更低.）这一步骤完成后，可确保没有两个向量φi1和φi2是完全相同的.假定在所有排除工作完成后仍有n1＞0，否则，本文模型的技术经济研究就不适用了.

步骤2生成容许站点能力过剩的基：

步骤3生成容许运力能力过剩的基：

这里产生的任何给定基所关联的最优对偶向量，对于所有i∈OU，有=0；对所有的

步骤4生成具有两种基本车型的基：

对于每一对车型{i1,i2}执行下述操作：如果，继续计算下一对车型.否则，计算使直线在内同时相交于和的和值.确定时向量φi的集合V使得，或使得凸组合.如果V∩H不为空，则继续计算所考虑的下一对车型.否则，依据B={i1,i2}、U=V，以及包含所有剩余指标(包括q和s)的L来生成基.

这里生成的任何给定基所关联的最优对偶向量，对于所有i∈OU有；对所有的i∈U有 λi=vi-qiμ1-siμ2.

2.3.2 算法的有效性证明

在本小节中，将论证本文算法所生成的基，能完全满足前述权威基集合的三个关键条件，以及评估其计算复杂度.

1）假设1成立时，由本文算法生成的基必然满足最优性条件.

由于设每个qi和si都为正，则Ωb(1)的内部非空.从Ωb(1)内部选取点(Q,S)，如果其所对应的基本解满足互补松弛条件是非退化的，就表示这个解也是最优的.

证明如下：当b是在步骤2中生成，那么对于一些车型il有B={il,s}，并构建对偶解：对于所有的i∈OU 有μ1=vil/cil，μ2=0，λi=0，而对于所有i∈U 有λi=vi-qiμ1.这个对偶解是可行的，并且与基b对应的原解满足互补松弛条件，从而建立最优性[6].当在步骤3中生成b，则与步骤2生成b类似情况地可建立最优性；在这里，对一些车型il有B={q,il}，对偶解对所有i∈OU，有μ1=0，μ2=vil/sil，λi=0；和 对 于 所 有i∈U 有λi=vi-siμ2.最后，如果b生成于步骤4中，那么对于某些车型i1和i2有B={i1,i2}.设是应用本文算法对该对车型计算出的值；对于所有i∈OU设λi=0和对 于 所 有i∈U 则 有λi=vi-qiμ1-siμ2.可 见 该 对 偶解是可行的，并且互补松弛条件成立.所以，由本文算法生成的基必然满足最优性条件.

2）假设1成立时，本文算法生成的基必然满足覆盖条件.

证明：由于n1、n2、qi和si均为正，工作决策规划是可行的，并且对于每个存在一个最优基本解.依据线性规划理论，本文补偿问题的基本解最多有两个不在其边界上的变量.由于设v为正，一个最优基本解永远不会有离开其边界的xq和xs.对于一些车型il，如果在xs和xil远离其边界时，却存在(Q,S,K)最优基本解，那么互补松弛性使μ1=vil/cil，具有的车型i必须是满足xi=Ki的自有车型，而符合的车型i必有xi=0.当有多种车型具有=vi/qi时，通过参照使用指定基的最后车型所使用站点可变成本效率的递减顺序去运用它们，则最优性得以保持；通过确保每个车型i满足Ki=0，且 如 果则i∈U而 如 果则i∈L，也保持最优性并最后得到步骤2中生成的基.可以类似地证明，对于某些车型il当xq和离开其边界且存在(Q,S,K)是最优基本解时，步骤3中生成的一些基是最优的.最后，在相应于车型对i1和i2的离开其边界时，如果存在(Q,S,K)这样一个最优基本解，那么互补松弛性规定这一基本对的μ1和μ2应计算如步骤4中所示，φi超过此线时的车型i必须是满足xi=Ki的自有车型，φi完全低于此线时的车型i必须满足xi=0.当有两种以上车型的φi在此线之上时，通过按部就班地减少“最外层”车型的利用，同时增加利用“内层”车型，可得到一个基对并与第4步相应的最优利用率一致；通过确保满足Ki=0的每种车型i在φi高于此线时i∈U，以及φi低于此线时i∈L，可保持最优性并最后得到第4步生成的基.对于每一个K≥0，除一组勒贝格测度之外，上述情形使Ub∈BΩb(K)乘的覆盖为零.由于这是闭集的有限覆盖，这个并集实际上覆盖了需求空间的全部.

3）假设1成立时，本算法生成的基满足不相交的内部条件.

证明：给定K≥0，且设(Q,S)是算法生成的基b中某些域Ωb(K)的一个内部点.如果b在步骤2中生成，对于一些具有B={il,s}车型il，依据互补松弛性在双最优下必有=0.对于另一些由算法生成的基b*，如果(Q,S)是Ωb*(K)的一个内部点，这些独特的对偶值意味 着b*一 定 有在不失一般性的情况下，假设在步骤2的处理顺序中车型il优先于车型il*.但当Ωb*(K)内从开始的任意点超过这个运力数量时，Ωb(K)内任意一点会完全小于运力单位.可类似地证明步骤3中生成b的情况，对一些车型il有B={q,il}和唯一地最优双值.最后，来考虑对于一些车型i1和i2当B={i1,i2}时，在步骤4中生成b的情况.这里，互补松弛性意味着μ1和μ2的唯一最优双值是在步骤4中为此基对的计算所得.如果在步骤4中生成的另一个基b*有B={i3,i4}并且Ωb*(K)内部点共享的最佳值，则φi1、φi2、φi3和φi4必然是共线的.

4）算法的计算复杂度.假定假设1成立.在计算O(n3)次以内，本文算法将生成不超过个基.

注意，由于补偿线性规划的排除结构，算法实际上是丢弃了大量不经济车型的基.所以上述生成权威集算法的计算复杂度在实际应用中并不会过于庞大.

计算次数：由于只是简单的逐项对比和排序，故算法步骤1-3的计算次数少于O(n2)次；步骤4因为要执行二次方多线性时序运算，以使得对于向量对φi，可为每一个剩余的向量确定它属于哪个单一界定域，故其执行一次只需要不高于O(n3)次计算.由于n3远大于n2，所以总的计算次数可认为是在O(n3)次以内.

3 结语

本文介绍了一个相对简单和快速的解决方案，用于解决运输公司的车队构成问题.为了支持这一总体目标，引入了一个具有新颖特性参数的车队构成模型，并对该模型进行了技术分析以促进模型的求解.

专业运输车队要实现以低成本为多个企业提供快速准时和安全优质的运输服务目标，就应以满足客户需求为出发点，以低成本运营为目标来确定恰当地车队规模和结构.本文的研究旨在为运输车队的经营管理提供一定的理论依据和决策方法，期望能对企业的生产实践活动产生积极的指导作用.