基于满意度的投标产生问题研究

文/郑金诺 王浩青

在物流运输服务中，托运人除了考虑配送成本以外，还会考虑客户的满意度，如交货时间。准时的交货可以有效地给客户提供更好的服务。承运人在投标过程中也要根据托运人的需求来进行投标选择。本文研究了通过组合拍卖实现的协同运输中承运人的投标产生问题并且考虑客户的满意度，使用禁忌搜索算法对所提出的模型进行了验证。

1 引言

随着我国公路运输服务的迅速发展，越来越多的企业提供在线服务，并承诺在数小时内送达，以方便城市地区的人们的生活。这种环境下给承运人带来了重大的挑战，承运人必须做出明智的决策，才能在竞争如此激烈的环境下生存。对于托运人，承运人的客户，除了最大限度地降低运输成本以满足他们的要求，他们还对减少订单的交货提前时间感兴趣。在许多情况下，虽然成本是评估承运人提交的投标的一个重要属性，但托运人在评估投标时也会关注每个承运人的服务质量，客户会考虑货物到达的时间，从而影响客户的满意度。

组合拍卖（CA）是多线路拍卖的一种方式，托运人作为拍卖人，发放在几个出发地和目的地之间运输服务的需求，承运人作为投标人，通过提交托运人发布的运输合同的投标来进行竞争。本文主要解决在组合拍卖问题中包含的投标生成问题（bid generation problem，BGP）。投标生成问题必须由参与拍卖的每个承运人来解决。允许组合投标时，包括确定要投标的拍卖合同的子集和要求在每次投标中送达所有合同的价格。

组合拍卖问题已经有许多国内外学者进行研究，Rekik[1]等人（2017）提出了基于路径的CA中BGP的公式，该公式具有同质车队，并采用分支-价格-削减的方法求解。Ben Othmane[2]等人（2019）研究了BGP的一种变体，在这种变体中，承运人通过将可拍卖的合同与现有路线整合在一起来优化运营。Triki[3]等人（2014）考虑了CA具有随机清算价格的BGP。他们提出了一个概率优化模型，集成了投标构建和定价问题，只允许产生一个组合投标。李军[4]等人针对运输服务采购的多轮组合拍卖问题，考虑承运人竞价不确定特征，构建了上层最小化托运人成本和下层最大化承运人利润的二层规划模型。综上所述，本文站在承运人的角度考虑组合拍卖的投标同时满足客户要求，提高满意程度建立了以总成本最小，满意度最大为目标的数学模型，结合Solomon算例并使用禁忌搜素算法进行仿真实验对模型进行验证。

2.问题描述。

由于承运人竞争随物流环境的发展变得愈来愈激烈，承运人需要考虑更多投标因素。本文考虑了基于时间窗口的满意度问题，当在预定的时间窗前后送达货物时，会导致满意度下降。从而降低承运人以后的拍卖效率。除了考虑满意度的同时，承运人也要考虑自己的成本，如何在保证满意度高的情况下，减少承运人成本是本文的目标。此外还引用了李倩[5]等设计的惩罚成本函数，未按约定时间送达货物要支付惩罚金，这也算在承运人的总成本内。假设如下：（1）承运人车队车辆为同质车辆并且装载货物不能超过车辆载重量；（2）已知送货点位置及预定的时间窗；（3）每个送货点仅由一辆车提供配送服务，且只能到达和出发一次，但每辆配送车可服务多个送货点。

3.数学模型

3.1 参数设置。本文设置了一个有向图G=(N，E)，其中N为所有节点的集合，包括所有收货和交付节点以及承运人仓库节点，E为边集。节点集设置为N=（0，1，…，2n+1），n为请求数量，0和2n+1均为承运人仓库节点。I为取货点；j为交付点；H表示一组周期；K为车辆数量，本文承运人车队为同质车辆；Q为车辆容量，车辆不能超载；q表示取货点需求量；tij表示从i点到j点的运输时间；cij表示从i点到j点的运输成本；所有请求的取货点集设置为P，交付点设置为D；决策变量xijhk=1表示只有车辆k在周期h中访问节点i之后直接访问节点j，否则为0；yihk=1表示请求i由车辆k在周期h内送达，否则为0；uihk为车辆k在周期h中到达节点i的时间。

3.2 引入满意度函数

假设客户预约服务时间为[ei，li]，如果在此时间窗内进行配送，则fi（ti）=1。但是在实际运输过程中会遇到外部环境影响等状况，就会导致实际配送时间与预约的时间不符，导致满意度会下降。假设[Ei，Li]分别表示客户能接受的最早和最晚服务时间。若在[Ei，ei]或[li，Li]时间范围内进行配送，则客户满意度随着与预约服务时间窗的时间差的增大而降低。若配送时间在[Ei，Li]范围之外，fi（ti）=0。图1为客户满意度随时间窗变化情况。

图1

3.3 模型建立

约束（3）确保车辆在一个周期到达某个点，必须在同一周期离开；约束(4)确保每辆车在一个周期离开承运人仓库，必须在同一周期返回；约束（5）必须在同一周期内使用相同车辆的取货点之后访问其交付点；约束（6）定义等待时间；约束（7）确保送货时间在最大约束时间内；约束（8）确保车辆不超载；约束（9）为各项决策变量。

4.算法实现

4.1 禁忌搜索算法

禁忌搜索（简称TS）最早是由Glover F.[6]于1986年提出，是一种改进的局部搜索算法。此算法的基本原理是：对某问题给定一个初始解和领域结构，在领域中通过一定规则确定若干候选解；若这些候选解的值的值好于当前的最优解，则藐视准则被触发，忽视禁忌状态，用其替代当前解和最佳状态，并纳入禁忌表；若候选解均不好于最优解，则从候选解中找出最优，将其加入禁忌表中；如此不断迭代上述过程，直至满足停止准则。禁忌表是用来存放禁忌对象的表。它是禁忌搜索得以进行的基本前提。禁忌表本身是有容量限制的，它的大小对存放禁忌对象的个数有影响，会影响算法的性能，禁忌对象是指禁忌表中被禁的那些变化元素。禁忌长度指的是禁忌对象不能被选取的周期。禁忌搜素算法基本步骤如下：（1）给定算法参数，随机产生初始解x，置禁忌表为空。（2）判断算法终止条件是否满足？若是，则结束算法并输出优化结果；否则，继续以下步骤。（3）利用当前解的邻域函数产生其所有（或若干）邻域解，并从中确定若干候选解。（4）对候选解判断特赦准则是否满足？若成立，则用满足特赦准则的最佳状态y替代x成为新的当前解，即x=y，并用与y对应的禁忌对象替换最早进入禁忌表的禁忌对象，同时用y替换“best so far”状态，然后转步骤6；否则，继续以下步骤。（5）判断候选解对应的各对象的禁忌属性，选择候选解集中非禁忌对象对应的最佳状态为新的当前解，同时用与之对应的禁忌对象替换最早进入禁忌表的禁忌对象元素。（6）转步骤（2）。

4.2 实验算例及测试环境本文采用基本的禁忌搜素算法和Solomon算例中的C208算例来验证本文所提出模型的有效性。使用的软件为matlab R2019a,设备为Intel(R)Core(TM)i7-6700HQ CPU@2.60GHz,8g内存。

4.3 确定参数

设向量X、Y和K用于表示所提出问题中的每个解，向量X由所有取货节点和交付节点组成，其大小为.向量Y的大小等于所有请求的数量，与请求相对应的向量Y的每个分量表示分配给服务请求的周期。K的每个分量对应一个请求，K的维数等于所有请求的数量。请求量与取货点的量相同。

首先，从向量X的第一个分量到最后一个分量逐个选择取货和交付节点。在选择取货节点及其相应的请求之后，根据向量Y和向量K依次确定服务于请求的周期和车辆（路线）。当一个取货节点在一段时间内被分配给一条路线时，其成对的交付节点也被分配给同一时间段的同一条路线。如果在当前路线中插入请求导致不可行的解决方案，则将创建新路线，这意味着插入违反了时间窗口约束，或者由于车辆容量约束，当前路线无法满足请求。一些算法参数设置为：禁忌长度：20；最大迭代次数：300；车辆负载：700；车辆成本：500；车辆单位距离运输费用60元/km。送货时间早于时间窗则罚款30元，晚于时间窗则罚款80元。

以总成本最小，满意度最大为目标，最终得到最短距离946.4050km；使用车辆10辆；实验中出现了违反时间窗范围的情况，导致满意度下降，满意度为94%，总成本为62164.3元。

5.结论。

本文提出了一个考虑满意度的投标生成问题，满意度从时间窗入手，设定了时间周期，一个最早和最晚的时间期限。承运人要在预定的周期内完成任务才能获得更高的满意度.同时还建立了一个数学模型，并使用了禁忌搜索算法来对模型进行检验。通过解决此问题，承运人可以确定在组合拍卖过程中服务哪些运输请求，为承运人提供了更有力的竞争手段，此外，托运人也得到了决定竞胜标的新标准。