托运人联盟下的订单组合及车货调配问题研究

闫 芳, 张 凤

(重庆交通大学 经济与管理学院，重庆 400074)

0 引言

中小型托运人企业作为现代物流产业的重要组成部分，对国民经济的发展具有重要的推动作用。然而，一方面作为托运人的中小型生产及贸易企业发展迅速，企业数量增多，另一方面其物流费用水平整体偏高，如何有效整合中小型托运人企业的资源以降低整个中小型托运人市场物流总费用，是亟待解决的一个难题[1]。中小型企业资金及设备资源有限，仍有较大一部分企业采用自营配送模式，但由于自有运输车辆较少、订单规模及订单量不确定，导致大量空载、非满载的运输现象存在，使得物流成本整体偏高。因此，基于物流联盟的理念，本文考虑建立托运人联盟关系以降低物流总费用。

目前国内外针对物流联盟已经展开了一定的研究，但针对托运人联盟的理论研究相对较少。对物流联盟的研究，一部分文献基于运输联盟成本分摊方式的研究[2,3]、配送模式研究[4]、车辆路径问题研究[5]。另一部分基于承运人联盟的研究主要侧重解决联盟线路优化及车辆调度问题[6～8]、利用合作博弈理论设计或改进联盟利润分配机制[9～11]。而对于托运人联盟问题的研究相对匮乏，相关研究一部分解决联盟成员利润或成本分配问题，提出合理的分配机制，Okan等人[12]从合作博弈文献中开发出成本分配机制，并分析了几种成本分配方案。另一部分研究主要通过建立模型、设计相应的算法解决托运人联盟运输路线优化问题，如文献[13～15]。但是，上述研究多考虑单发货中心到有限客户端，较少考虑跨区域干线运输，鉴于我国多级物流中心转运形式较多，如何整合中小型托运人企业同向干线运输任务以降低物流总费用具有重要的研究意义。因此，本文以托运人联盟为背景，结合我国现实需要，综合考虑订单起止点、时间窗等因素，对订单进行组合及车辆调度问题进行研究。

1 模型建立

1.1 问题描述和基本假设

本文建立一个由多托运人组成的运输联盟，联盟内所有资源共享，所有订单的分配与车辆的调度由联盟决定。现考虑，将同一目的地订单，在满足车辆载重的条件下使用同一辆车运输，以最大程度提高车辆装载率。此外，为保证运输联盟的服务质量，还需考虑联盟后成员的整体满意度，该满意度将量化为运输惩罚成本考虑到目标函数中，运输惩罚成本与订单可接受的送达时间范围有关。

为实现上述目标，建立以下车辆调度模型，并假定：各个需求已知且不可拆分；车辆原始定位已知；联盟的总运力满足所有运输需求；托运人的货物已经存放在距离其最近的发货点；由于下阶段的运输任务未知，故不考虑车辆的返程问题。

1.2 模型构建

1.2.1 符号说明

表1 符号说明

1.2.2 模型构建

基于以上假设及符号，为解决上述问题，建立如下混合整数规划数学模型:

(1)

约束条件:

上述模型中相关变量如下：

(1)Xk,i,j,v={1,0}：当订单k由车辆v从i地运往j地时，取值为1，否则为0。

即当运往j地的订单k由i0地发货，则没有产生调配成本，取值为0，否则，取值为1。

(3)Zv={1,0}：当车辆v被使用，则取值为1，否则取值为0。

(4)Ri,j,v={1,0}：当车辆v从i地运往j地时，取值为1，否则为0。

(5)Si,j,v:车辆v从i地运往j地的发车时间。

公式(1)为联盟后总成本函数，由运输成本、固定成本、调配成本、早到惩罚成本、迟到惩罚成本五部分组成，求最小值；公式(2)确保所有运输任务均被完成；公式(3)车辆运输要求限制，保证任意一辆车只能运往一个目的地；公式(4)车辆载重限制；公式(5) 时间约束，车辆到达时间等于车辆出发时间与行驶时间之和；公式(6)保证只有参与运输任务的车辆才会产生车辆发车时间，如果车辆未参与任何运输任务则车辆发车时间为0；公式(7)保证订单不可拆分，且仅能由一辆车从唯一发货地运往唯一到达地；公式(8)确保任意发货地所需车辆数满足该发货地可用车辆数要求；公式(9)车辆数限制，整个运输环节所需车辆数不超过总车辆数；公式(10)～(11)保证任意一辆车无论运输多少订单任务，只要参与运输便被标记；公式(12)表示变量X与订单的关系，仅当订单k有运往j地的运输任务时，变量X取值可能为1，否则为0；公式(13)表示变量X与车辆的关系，仅当i地有车辆v时，变量X取值可能为1，否则一定为0；公式(14)～(15)确定车辆v从唯一出发地i运往唯一目的地j。

2 算法设计

上述模型不仅涉及订单组合、还涉及到车货匹配及调度，这两类问题均为NP-HARD问题，因此该模型的求解较为复杂[16]。考虑粒子群算法具有结构简单、需要调节的参数较少、较容易实现的特点[17,18]，故本文采用粒子群算法进行模型求解。在时间窗处理方面，本文制定了三种策略，三种策略下的车辆与货物匹配问题编码与解码方式一致，但时间窗处理方式不同。

2.1 编码与解码

针对车辆与货物匹配问题，以订单总数m与车辆总数s之和为编码段长度，即粒子维度，提出图1所示编码方案。

图1 车辆与货物匹配问题编码

在车辆与货物匹配问题的编码方案中，主要包括两个部分：即订单安排优先级顺序和车辆安排优先级顺序。其中，1～m段为订单安排优先级顺序编码段，m+1～m+s段为车辆安排优先级顺序。在订单安排优先级顺序编码段中，又将m段划分为k个包，以确定各个包内的订单安排顺序。下面以10个订单5辆车为例，阐述具体的解码过程，如图2～4所示。

首先将发往同一目的地的订单进行打包，并对每个包里各个订单以订单编号升序排列以确定初步的订单顺序，具体过程如图2所示。

图2 合并后的订单顺序

第一步，确定订单安排优先级顺序，如图3(a)所示。

第二步，确定车辆安排优先级顺序，如图3(b)所示。

图3 订单安排优先级顺序及车辆安排优先级顺序

第三步，完成车辆与货物的匹配。在满足订单运量与车辆载重关系情况下，根据订单及车辆安排优先级顺序，为所有订单匹配合适的车辆，具体过程如图4所示。

图4 车辆与订单的匹配

2.2 时间窗处理策略

在确定订单与车辆的匹配关系之后，需要确定车辆的发货时间，发货时间与车辆的达到时间有关，因此可以根据订单可接受的到达时间窗确定车辆的到达时间。

针对时间窗的处理，主要有三种策略：

(1)策略一：“最晚到达时间”里选择“最早的时间”作为到达时间

(2)策略二：“最早到达时间”里选择“最晚的时间”作为到达时间

2.3 算法流程

标准粒子群算法首先随机初始化一群维度一定的粒子，然后所有粒子根据个体极值(pbest)和群体极值(gbest)来更新自身速度与位置，并将按照如下的更新方式再搜索空间中找到最优解:

Vi+1(t+1)=ωVi(t)+c1r1(pbesti(t)-

Xi(t))+c2r2(gbest-Xi(t))

(16)

Xi+1(t+1)=Xi(t)+Vi+1(t+1)

(17)

其中，ω为惯性权重系数，c1，c2为算法的学习因子，r1和r2是介于[0,1]之间的随机数。

本文将采用标准的粒子群算法来对上述模型进行求解，具体过程不再赘述。

3 运算测试及结果分析

由于不同文献假设条件不尽相同，且缺乏针对本文所研究的问题的通用或标准测试算例，因此本文随机生成由4个发货地、4个到达地、20个订单、10辆运输车辆组成的实例。

3.1 系统运算环境及参数设置

鉴于前人研究结果，本文在实际运算过程中通过对不同参数设置下的算法运行结果曲线以及解的优劣性对比分析，确定出使算法表现效果最佳的参数如下：种群规模为400、最大迭代次数为400、粒子维度30、学习因子C1为1.5、学习因子C2为1.5、惯性权重为0.2。

3.2 结果分析

3.2.1 三种时间处理策略下最优方案比较

三种时间处理策略下的惩罚成本均为Pe=0.1(千/天)，Pl=0.2(千/天)。策略一“最晚到达时间里选择最早到的时间为出发时间”，最满意结果总成本为16.6千元。策略二“最早到达时间里选择最晚到达时间为出发时间” 最满意结果总成本为17.3千元。两阶段策略，最满意结果总成本为16.6千元。

对比上述三种策略，“策略一”和“策略三”与“策略二”相比，虽然订单与车辆组合方式不同，但总成本相等且最优。因此，三种时间处理方式，就运行结果而言，“策略一”=“策略三”>“策略二”，本文随机选择“策略一”为最优策略，并以此对论文展开后续分析。

3.2.2 联盟与不联盟情况比较

联盟情况下，比较三种策略下的满意解，可发现总成本最低为16600元，总使用车辆数为5。不联盟情况下，各托运人运输车辆不共享，且车辆不等待，假设每辆车在本此运输阶段仅完成一次运输，在不考虑惩罚成本的情况下，车辆的最低运输成本已经达到了19000元，总使用车辆数10，与联盟情况相比，联盟比不联盟情况下的总成本减少了至少12%，使用车辆数减少了50%。综合上述分析，与不联盟情况相比，托运人联盟时总成本节约显著。

3.2.3 调配成本对最满意方案的影响

以策略一“最晚到达时间”里选择“最早到的时间”策略为最优策略，分析在不同调配成本下总成本的变化情况，表4为不同调配成本下总成本汇总数据。

表4 不同调配成本下总成本变化情况

根据表4数据，可发现当调配成本上调百分比由70%增加到90%的时候，总成本的变化非常明显，总成本增加率达到了20.30%，且增长率差额也达到了百分之6.39%。在调配成本较低时，车辆与订单的最优组合方式变化较小，且总成本的变化也是较平稳的；在调配成本较高时，车辆与订单的最优组合方式发生了明显变化，且总成本增长率变化明显。

3.2.4 惩罚成本对最优方案的影响

以“最晚到达时间里选择最早到的时间策略” 为最优策略，分析在不同惩罚成本下总成本的变化情况，表5为不同惩罚成本下总成本及增长率变化情况。

表5 不同惩罚成本下总成本及增长率变化情况

由表5可知，当惩罚成本上调百分比为30%、60%、90%、120%、150%、200%时，随着惩罚成本成比例的增加，总成本也成比例的增加；但当惩罚成本上调百分比增大到300%、400%时，总成本增长比率变大。在惩罚成本上调百分比低于300%即惩罚成本低于4时，最满意方案不发生变化，总成本也随之成比例增加；但当惩罚成本高于4时，最优方案发生改变，且总成本不再成比例增加，这说明，此时惩罚成本最优方案产生了较大影响，因为只有通过改变原最满意方案，才能够降低总成本。综合上述分析，在惩罚成本较低，对最满意方案的决策影响较小；当惩罚成本较高时，对最满意方案决策的影响较大。

3.3 粒子群算法有效性分析

为证明本文所提算法的求解性能，现增加多组小规模算例，且分别采用LINGO软件以及本文所提粒子群算法求解，并将其求解结果及运行时间进行分析比较。本文依据订单量、托运人数、车辆数、到达地数等参数随机生成了10组小规模算例，其中，算例编号中分别代表(订单数-托运人数-车辆数-出发地数-达到地数)，计算结果如表7所示。

表7 lingo与粒子群算法对比

从表7可明显看出，就运行结果而言，无论采用粒子群算法还是采用LINGO软件，其求解结果一致，从而证明了粒子群算法求解结果的有效性；就运行时间而言，在N=T=50及N=T=300时，采用粒子群算法求解时，不同算例规模下的运行时间基本接近，分别为4s、2m，而采用lingo求解时，不同算例规模下运行时间差异较大，平均运行时间约7分钟。可见，即使是在小规模算例求解中，采用粒子群算法也具有较高的求解质量以及较快的求解速度。

4 结论与展望

本文的主要工作如下：①建立了一个以订单与车辆匹配为基础，同时考虑调配成本及惩罚成本的车辆调度模型；②提出了针对该模型的粒子群算法解决方案；③比较了三种时间处理策略下的联盟的最佳方案，并选择了最佳的时间处理策略；④分析了调配成本对最满意方案的影响以及惩罚成本对最满意方案的影响；⑤通过与LINGO对比，分析本文所提算法的表现。

算例结果表明，本文提出的模型与算法一方面可有效解决中小型托运人企业空载率较高的问题，另一方面托运人联盟有助于整合有限运输能力，在实现资源共享的同时，降低联盟后总运输费用。 本文仅针对托运人联盟后的订单与车辆匹配及调配问题进行研究，未考虑联盟成员的成本分配问题，在以后的研究中将再做讨论。