基于前景理论的电动汽车配送路径优化

孟 楠，王 静

（武汉科技大学 管理学院，湖北 武汉 430070）

0 引言

2022年1月18日国务院发文倡导推广新能源交通运输工具，强调在城市物流配送中电动汽车的使用比例不得低于80%。由此可见，燃油汽车电动化正在加速影响绿色物流中的“最后一公里”环节。但是，电动汽车在符合低碳运输和环境友好发展要求的同时，也存在“充电焦虑”和“续航差”等问题，因此探讨其配送路径优化问题具有深刻意义。

近年来，不少学者对带时间窗的物流配送路径优化问题进行了研究。文献[1]为了避免提前配送和延迟配送问题，设计了关于软时间窗的惩罚成本并纳入目标函数，但其惩罚系数为自定义参数。文献[2]以硬时间窗设计为约束，使货物送达时间既不得早于订单的生成时间，也不能晚于客户允许的最晚服务时间，并且通过综合考虑硬时间窗和合单配送的滚动时与延迟配送算法求解了生鲜即时域送问题。文献[3]针对混合时间窗设计了客户满意度评价函数，构建了客户平均满意度最大化和空载行驶里程最小化的混合整数规划模型。

许多学者针对电动汽车的充电管理展开了大量研究。文献[4]设计了基于混合柔性充电策略的带时间窗的电动汽车车辆路径优化数学模型，通过基于充电站启发式插入的蚁群算法证实其能够降低总体成本。文献[5]针对考虑货损的生鲜实例建立了成本最低的数学模型，得出边充边卸模式能够降低物流配送成本。文献[6]基于人群感觉设计了电动汽车的充电战略模型。文献[7]根据“峰谷电网”设计电动汽车的充放电管理，得到了兼顾客满意度最高和配送成本最低的方案。

通过分析上述文献可以发现，目前相关研究多从客观因素进行分析，但人是有限理性的，对于配送方案的决策需要考虑客户心理，因此越来越多的学者从主观心理角度出发进行深入研究，其中一个重要分支为“前景理论”。文献[8]基于“滴滴”交通数据集和累计前景理论来量化不同决策者的充电行为。文献[9]通过贝叶斯理论和累积前景理论建立了用户在活动链上的转移关系和充电需求模型，结合动态交通网络和实例验证了其有效性。文献[10]利用改进的前景理论决策方法，建立直觉模糊评价矩阵，解决了集中电动汽车充电中心的选址问题。

通过学者们的研究可知，基于前景理论的价值函数可以量化用户的出行选择概率模型、电动汽车的充电选择概率、改进的最优准测权重，本文将前景理论纳入电动汽车路径优化中，基于前景理论的价值函数量化了客户对电量补给的行为感知。

1 模型构建

1.1 问题描述

某一配送中心服务于具有特定时间窗和需求量的客户群，并使用同种类型的电动汽车进行订单不拆分配送作业，每辆电动汽车的最大装载量、最大额定电池容量和最长行驶时间相同。车辆从配送中心出发时为满电状态，按平均速度匀速行驶，假设电量的消耗与行驶路程是线性相关的，并且在客户点停留时不消耗任何电量。当电动汽车的电量不足以到达下一客户点或者返回配送中心时，需访问周围可到达的充电站补充电量，离开时为满电状态，完成任务返回配送中心后不再出车。电动汽车由于电量补给而未在时间窗内将货物送达客户手中时，需要根据前景理论支付补偿费用。并且，一辆电动汽车可服务于多个客户，但是每一个客户能且只能被一辆车服务。

1.2 符号说明

为了建立数学模型，引入以下符号，见表1。

表1 符号一览表

1.3 基于前景理论的补偿费用

物流配送服务商的核心竞争力之一就是能确保在客户要求的某一时间段内将货物送达。然而整个配送环节中的不确定性风险较多，某些配送中心选择使用纯电动汽车作为基础设施，其电能补给行为可能会导致延迟配送的情况。这种超出时间窗收货的焦虑感和不满感直接影响客户对配送商的评价以及忠诚感，这种行为与感受与前景理论的刻画是相符的。因此根据前景理论的价值函数和客户的特定时间窗，向客户提供补偿费用，以弥补失误且维护后期合作关系。前景理论中客户点i的价值函数可表示为：

其中αi、γi、λi为参数，i=1,2,...,c，0＜αi＜1，0＜λi＜1，损失厌恶系数γi＞1表示决策者对损失是厌恶的。

前景理论表示，在决策选择的初始阶段，需要选择一个适当的参照点，此时价值为0，据此衡量与参照点之间的差距，从而得到结果是亏损还是盈利。本文选择时间窗为现状，即为参照点，用Oi来表示现值与参照点之间的偏差；用表示车辆到达客户点的时间。根据前景理论的价值函数可知，当时，客户会感到满足；反之当时，客户会感知到损失，需支付给客户补偿费用。本文的总目标为成本最低,基于价值函数的补偿函数可表示为：

其中，式（3）表示偏差的量化方法，可具体解释为：如果电动汽车到达客户点时的时间超过了客户的最迟收货时间，那么取二者之间的差作为偏差值；如果在时间窗内送达或者早于时间窗送达，那么偏差取0。

1.4 建立数学模型

以车辆行驶费用、基于前景理论的补偿费用以及充电费用之和最小为目标，建立基于前景理论的电动汽车配送路径优化模型，具体如下：

具体解释如下：式（5）保证每个客户被服务且仅被服务一次；式（6）保证流量的平衡；式（7）保证一辆车只使用一次；式（8）保证派出的电动汽车不超过总车辆数；式（9）保证配送中心既是起点也是终点；式（10）-（11）保证各个顾客的配送需求量、车辆配送任务不超过电动汽车的最大额定载重量；式（12）表示在客户点停留时间内不消耗任何电量；式（13）保证电动汽车在配送网络中满足最大额定电量的限制；式（14）保证电动汽车从充电站或者配送中心出发时为满电状态；式（15）保证到达下一节点j的时间与离开上一节点i时间和行驶时间有关；式（16）保证离开节点i的时间只与到达时间和服务时间有关；式（17）表示如果在客户点i的开始服务时间在时间窗内，超时服务时间为0，晚于最晚到达时间需要支付补偿费用。

2 算法设计

本文构建的单配送中心多客户路径优化模型是非线性规划模型，属于NP-hard问题。运筹学中某些精确算法对于小规模问题能够求得最优解，随着数据规模变大会出现“组合爆炸”的问题，而启发式算法因其稳定性和较快的收敛性能够得到近似最优结果，因此本文采用遗传算法进行求解。

2.1 编码与种群初始化

遗传算法中将所有节点视为基因，本文通过自然数编码构成染色体，其长度为c+f+g+1。配送中心的编码为0；编码1，2，3，…，c代表各个客户点被分配的自然数序号；c+1，c+2，c+3，…，c+f代表各充电站被分配的自然数序号。

种群是由一定数量的染色体构成的，本文根据载重量约束构造初始种群，需遵循以下步骤：

（1）随机排列包括充电站的所有节点；

（2）qi表示客户节点i的配送需求量表示一条染色体中第i位基因对应的客户的配送需求量。若满足则在此染色体第a位基因后插入0；

（3）根据上述规则重复多次计算，直至处理完所有客户点的需求量约束；

（4）将染色体的开头和结尾各补1个0，形成一条完整的初始染色体。

（5）重复上述操作构造种群数量为N的初始种群。

比如某一配送中心某一天共有3辆电动汽车服务于8个客户点，在配送区域中共有2个充电站。假设经过编码后形成的一条染色体为：0，3，6，9，2，0，1，7，0，4，10，5，8，0，由于每辆电动汽车都是从配送中心出发，最终又回到配送中心，所以在“0”处进行分割，得出了三条路线，具体解读如下：第一辆车依次服务于客户点3，6，2，并且在离开客户点6后先驶往充电站9，之后再服务客户2；第二辆车依次服务于客户1，7；第三辆车服务于客户4，5，8，并且在离开客户点4后先驶往充电站10，之后再服务客户8。

2.2 适应度函数

由于在形成初始染色体时没有考虑电动汽车的电量约束，因此通过设计惩罚函数的方法使其结果符合电量要求，从而达到保证电动汽车电量补给行为的同时进一步检验载重量约束的目的。根据目标函数的设计以及研究的问题，需要用惩罚函数的形式来表示电动汽车的电量和载重量限制，从而得到以下改良目标函数：

其中，M1、M2分别为极大的正数。在一条染色体上，某一辆车的载重量或者电量约束不符合条件时，改良目标函数值会非常大，表明此染色体表示的配送路径方案是不可行的。

遗传算法的适应度函数是通过排序来筛选优秀个体的工具，与上述设计的改良目标函数的作用相同，适应度函数的值越大，说明此染色体个体越优，因此，适应度函数为：

2.3 遗传操作

2.3.1 选择复制。本文没有采用选择算子，而是选择一定比例的个体。首先，采用传统的轮盘赌法计算每个个体的选择概率并且进行降序排列；其次，选择偶数位的前1/3的染色体进行保留，以便后续的交叉操作；最后，构成新的种群。

2.3.2 交叉操作。传统的交叉方法的寻优能力有限，因此需改进后再运用。首先，对种群中的偶数位个体A、B随机选取一段由0开始且由0结束的路径1、2，并且分别移动到染色体的头部，构成新的父代A、B；其次，分别将上述子路径1作为子代染色体C的头部，将新形成的父代B中非子路径1的元素按照顺序依次加到C中，并且在尾部补足0，按照上述方法形成子代D；最后，在子路径1、2后的位置中按照适应度值最高原则插入一个0，构成最终的子代。

2.3.3 变异操作。采用2-opt算法对交叉后的个体进行变异，即随机数小于变异概率时，随机选择个体两个不同位置的基因进行对调。

2.3.4 终止条件。上述流程循环次数达到最大迭代次数时得到最终结果。

3 算例设计与分析

3.1 算例介绍

某小型物流配送中心共有三辆同型号的电动汽车，为25位客户提供配送服务。本文的算例来自于Solomon设计的带时间窗的车辆路径标准数据库，采用拥有25个客户的R101算例。分别将其时间窗、需求量和服务时间进行等比例缩小，且生成2个与客户分散程度相匹配的充电站，得到更符合小型配送中心实际情况的初始数据。各个节点的具体参数见表2，其中编号0为配送中心，编号1-25为客户点，编号26-27为充电站。电动汽车的额定载重量Q为12t，最大额定电量为100kW·h。电动汽车进入充电站后达到满电状态，耗时0.4h，单次花费40元；电动汽车从配送中心出发的时间为0h，且在配送过程中的行驶速度恒定为30km/h。电动汽车的行驶成本为1元/km，每单位时间消耗的电量为22kW·h，补偿金额系数为2.25，超时厌恶系数为0.88。

本文采用python3.9对上述算例进行求解，运行环境为64位的Windows 10家庭版操作系统，运行内存为8GB，CPU频率为2.38GHz。种群大小为200，最大迭代次数为2 000，变异概率为0.08。

根据表2的第二列和第三列绘制各节点的位置分布，如图1所示，其中“”表示客户的坐标所在；“”表示配送中心的坐标所在；“”表示充电站的坐标所在。

图1 各节点位置分布图

表2 各节点信息

3.2 算例结果与分析

通过本文设计的改进遗传算法求得最终的结果为：

其中data表示某配送中心设计的配送方案，由3辆车负责服务25位客户，其中包括4个“0”，每2个“0”之间为一辆车的服务对象，车辆1号、2号和3号的子路径的载重量分别对应表3中的第一行、第二行和第三行。

根据图1和表3绘制此算例的配送路线，如图2所示，其中用点划线表示的闭环路线表示车辆1号的行动轨迹，用圆点表示的闭环路线表示车辆2号的行动轨迹，用实线表示的闭环路线表示车辆3号的行动轨迹。

表3 配送方案与载重量

由表3和图2可以发现，车辆1号到3号的装载率分别为87.50%、89.17%、100%。未充电的车辆1号和2号的装载量相似，几乎达到整车配送要求，进行了两次充电的车辆3号为整车配送，以较高满意度完成配送任务的同时降低了成本。

图2 配送路径

电动汽车的电量补给行为影响着整个配送方案，需通过剩余电量进一步分析配送路径的优化性，每辆车的实时剩余电量如图3所示。

图3 车辆电量变化图

由表4可知，车辆1号和2号回到配送中心时剩余电量较少且没有充电，较大限度的利用电量资源进行配送。由图3可知，车辆3号在剩余38.274kW·h电量时到编号为26的充电站进行第一次充电，后续以满电状态再次出发，在消耗了71.544kW·h后到达编号为27的充电站进行第二次充电，最终回到配送中心时留有近似一半的电量。虽然剩余电量较多，但由于其充电成本远小于整车配送的成本节约，因此具有优越性。此外，物流配送商的运营环境中充满不确定性，可能还会出现一些偶然意外事件或者临时性需求，存有一定安全电量的车辆3号可以根据一定的路线规划和运量规划执行紧急性任务，从而提高整个配送系统的灵活性和响应性。

表4 配送方案其他信息

4 结语

本文以纯电动汽车为研究重点，因客户会因电动汽车的充电耽误配送时效而产生一定的不满情绪，从而需要付出一定的补偿费用，以提高顾客满意度和稳固合作关系，建立了成本最低的配送路径优化模型，突破传统的衡量顾客对时间紧迫性的度量，通过改进的遗传算法对处理后的Solomon-R101算例进行求解，得到优化的配送方案，使方案更加贴合人性中的非理性部分和现实。

但由于笔者的能力有限，此研究还具有一定的局限性：

（1）本文为单配送中心的配送问题，但现实中多为多配送中心的路径优化。

（2）本文假定电量的消耗是线性消耗，但其与载重量、坡度、时变角度、风速等因素密切相关。

（3）随着“绿色产业、良性发展”的深入推进，电动汽车的充电行为越来越复杂。