考虑不确定因素的低碳配送优化研究

王艳朋 台玉红

摘要：当配送车辆遇到道路堵塞、恶劣天气、限行、道路质量差等不确定因素时，不仅行驶车速会受到影响，甚至可能会导致配送服务水平下降。即使在配送过程中有些路段是最短距离，当遇到这些不确定的因素时，路径优化的结果将会发生变化。文章试将受不确定因素影响路段的实际距离转化为理想距离，在其路径优化的过程中将碳的排放量转换为成本，最终以成本最低为目标函数建立数学模型，讨论了基于改进禁忌搜索算法的配送路径优化问题的设计和实现。优化对比结果表明，考虑不确定因素的配送路径优化比不考虑不确定因素的优化结果更贴近实际。

关键词：物流工程；低碳配送；禁忌搜索；电子商务；路径优化

一、引言

传统的物流路径优化研究一般假设所有的信息（包括路况信息、车辆信息、顾客信息）都是确定的，这类车辆路径问题被称为确定型VRP。但是，在配送过程中，难免会出现道路堵塞、恶劣天气、限行、道路质量差等不确定因素，这些不确定因素随着时间的推移出现，需要适时改变车辆的运行路线，对已安排好的车辆路径进行及时调整。此时需要研究一套考虑不确定信息车辆路径问题（Uncertain Information Vehicle Routing Problem，UIVRP）的理论和方法。并且，随着全球气候变暖，温室气体（主要是CO2）的减排问题受到各国的密切关注，低碳经济、绿色物流逐渐成为国内外研究的热点。随着供应链全球化发展，供应链中各物流节点距离不断增加，车辆在运输配送过程中所带来的碳污染等环境问题逐渐显现，因此把减少“碳排放”的理念融入到物流网络设计当中，构建一个碳排放量最低的绿色物流网络具有广泛的现实意义。

已有学者提出了一些模型来研究这些问题，其中通过运输距离的优化间接达到减排目的的研究较多，而直接计算碳排放量并将其整合进目标函数的研究较少。国内对VRP最先进行系统性研究的是郭耀煌教授，他及其学生對多车场、多车型等类型的问题进行了较多的研究，并且先后承担了多项基金项目的研究，出版了国内车辆路径问题研究领域的第一部专著——《车辆优化调度》，将sweep算法和节约算法结合起来使用，从而提出了一种多车场转化为单车场的处理方法。国外Miguel Figliozzi文献中以碳排放量最小为第一目标函数和以燃油量为第二目标函数提出了一种以碳排放量为目标函数的车辆路径问题（EVRP），用启发式算法对其进行了求解，结论显示通过优化可以明显地降低车辆运行中的碳排放量，在拥堵的地区，可以通过增加少许的运作成本来大幅降低温室气体的排放。Kim. N.S （2009）在多式联运网络中探讨了货物运输成本与CO2排放量之间的关系，研究表明CO2排放量受运输系统载货量的影响，通过优化多式联运的组合可以降低CO2的排放量。Palmer在零售业背景下建立了一套以降低碳排放为目的的车辆路径模型，模型具有优化配送时间和将低碳排放量的功能。

二、问题描述

当配送车辆遇到道路堵塞、恶劣天气、限行、道路质量差等不确定因素时，不仅行驶车速会受到影响，甚至可能会导致配送服务水平下降。即使在配送过程中有些路段是最短距离，当遇到这些不确定的因素时，路径优化的结果将会发生变化。考虑到现实生活中配送路径十分复杂，为确保模型的逼真性，需对现实问题进行必要的抽象和简化。

首先，在配送过程中，载货量的多少不可避免地会对碳排放造成影响，若将载货量考虑到模型里，模型规模将会很大。为降低建模难度的同时又不影响模型的真实性，本文在研究配送优化时暂不考虑载货量对碳排放的影响。

其次，为体现当前各大物流公司的战略目标，即满足客户满意度最大化的原则，对模型中车辆出现延迟配送的确定无穷大惩罚值，对车辆提前到达客户处的确定惩罚值。

再次，为提高配送服务质量和客户满意度，本文在建模时，按客户对收货时间的要求制定时间窗建模。

最后，考虑到车速变化对碳排放的影响较大，故模型假定以经济车速配送；为使建模更加逼真，由于是小范围内配送故暂不考虑天气等不确定因素的影响，将每一条实际路径赋予一个交通条件和道路条件系数来转化为理想路径，在此基础上优化路径。

（一）实际距离转化为理想距离

考虑到不确定因素对配送的影响，分别引入道路条件（hij）、交通条件（rij）、和天气（wij=0）等影响因素定量讨论其对城市交通运行状况的影响程度，计算公式为

其中，dij为客户i和j之间的实际距离；d*ij为客户i和j之间的理想距离。

（二）碳排放成本计算

在配送过程中的碳排放量，不仅与运输距离有关，还与载货量等因素相关。本文收集相关数据进行回归分析，得出碳排放量是依赖于配送距离和载货量的二元一次函数，即

其中，d是车辆行驶距离，Q0是车重，x是载货量，α、β、b是一常数。

设车辆的最大载货量为Q，满载时单位距离排放量为

空载时单位距离碳排放量为

三、模型

（一）模型假设

设某城市有一个大型配送中心，随机给这个城市里的n个客户进行配送。

1. 共有型号统一的M辆配送车辆。

2. 货物流向为单向，即纯送货。

3. 每个客户只能由一辆车进行配送服务。

4. 每辆车都从配送中心出发，然后又回到配送中心。

5. 每个客户都有属于自己的一个服务时间窗，服务必须在此时间范围内进行。

6. 顾客总的需求量不能大于车辆总的载重量。

7. 每条线路上的车辆载重量之和不能超过车的载重量。

8. 假设公式（1）中城市配送中的交通现状中道路条件（hij）、交通条件（rij）和天气（wij）对交通运行状况的影响程度的取值范围可参考。

（二）定义模型中的变量

M为配送车辆编号集合，M=[l，2，3，…，m]。

N为客户编号集合，N=[1，2，…，n]。

dij为客户i到客户j的实际距离。

B为配送车辆的启动成本。

C1为车辆单位里程运行成本。

Cij为客户i和j之间碳排放成本。

Pe 、Pl为惩罚系数，其取值为正数，一般认为早到要比晚到所带来的损失要少一些，即令pe

[ai，bi]为客户i要求的货物到达时间窗。

Ti为配送车辆到达客户i的时间点。

PTi 为未能按时到达客户i的惩罚成本。

Di为客户下订单的时间。

Xijk=1，如果配送车辆k从客户i到客户j

0， 否则

Zk=1，如果配送车辆k被使用

0， 否则

Yik=1，如果客户i需求由车辆k满足

0， 否则

（三）低碳配送的数学模型

四、改进的禁忌搜索算法设计

首先，通过贪婪算法，以客户的订货的时间和收货的时间窗按成本最低的原则确定车辆配送的数量，同时生成禁忌搜索算法的初始解。其次，设计邻域结构并从中选出候选解集，设计出禁忌表和禁忌长度。再次，设计出特赦准则。最后，确定迭代步数终止算法并输出结果。

（一）编码的方式

本文以自然数编码的方式编码，方式如下。

假设需要调用的配送车辆数为k，可以将配送路径编译成一个自然数序列数组，即

该数组中ikj表示配送车辆k的配送任务，每条子路径之间用0进行分割，表示每台配送车辆从配送中心出发完成配送任务后回到配送中心。每条子路径之间客户之间的位置是有序的，表示配送车辆对客户提供服务的顺序。

（二）初始解生成

本文求初始解的具体步骤的如下。

步骤一，根据公式（1）得出客户之间路径的理想距离，然后计算出客户间所需要的行驶时间，且令r=1。

步骤二，派出第一辆车配送，确定第一条带有第一个客户ir1的新路径，其中客户ir1需满足与配送中心的理想距离最小，且有最迟服务时间。

步骤三，若能找到与客户irn（n=2，3，…）之间理想距离最小的，且满足时间窗中最迟服务时间的客户作为irn+1，否则转至步骤一。

步骤四，派出另外一辆车，开始一条新路径，令r=r+l，转至步驟二。

步骤五，若车辆配送到所有客户，得到一个初始解。

（三）邻域结构设计

本文拟用路径内交换和路径间变换的邻域设计策略。路径内的交换主要是利用2-opt的方法在同一路径中随机找到两个点进行交换；路径间的变换包括路径间的交换与插入。

（四）选择候选解

本文在选择最佳候选解时利用邻域结构设计策略，使每个当前解产生N个候选解，让这些候选解对应的适应度从小到大排序，从中选出排在前面的n（n

（五）禁忌表设计

本文在设计禁忌表时选用从上一个当前解变为现在当前解时用到的两两交换的对象（客户点）作为禁忌的对象，为了记录这些禁忌对象的任期在每一次迭代中的变化，本文在编写程序时设计了一个[26*26]的矩阵专门记录这些禁忌对象任期的变化。本文选用固定型的禁忌长度，用客户点数n的作为禁忌的长度。

（六）特赦准则设计

本文选用基于适应度的原则进行特赦准则设计，如果在迭代的过程中某个候选解的适应度值优于历史最优值，那么无论这个候选解是否处于被禁忌的状态，都要被接受，成为下一次迭代的初始解并取代当前的历史最优解成为新的“best so far”。

（七）终止准则设计

本文用不同的迭代次数进行实验，根据实验的结果确定合适的最大迭代步数终止算法。

五、算例仿真

（一）背景介绍

本文以某电子商务企业在某城市有一大型配送中心为例，配送车辆为10，设每台车的启动成本为300，经济车速下每台车每公里的运输成本为2，碳排放成本为0.5，等待时间的惩罚系数pe=10、pl=inf，若某一天客户为25，且rij和hij可由rand命令随机生成。因同城配送，天气状况基本相同，故可取wij=0。根据某电子商务企业随机对客户信息提取整理需要配送客户的具体信息见表1。

（二）考虑不确定因素的路径优化

对于考虑不确定因素的路径优化，首先利用公式

为保证算法更具有稳定性和求得更为满意精确解，运算10次并将与未考虑不确定因素的优化结果进行对比，见表2。

分析可知，虽然两种路径优化方式结果的实际距离差不多，但考虑不确定因素的各种配送成本及总成本明显比不考虑不确定因素的路径优化小。因此，物流企业在配送优化时，需考虑不确定因素各种条件，首先将每条路径的实际距离转化为理想距离，在此基础上再对路径进行优化可以有效降低配送成本和碳排放量。所以，为提高配送服务满意度及达到节能减排的目的，在路径优化过程中单纯优化实际路径是不够完善的。

本文在前人研究成果的基础上，探讨了考虑不确定因素前提下，配送路径优化问题，经过本文的研究，构建相关模型并对其进行求解，得到了预期的结果。

参考文献：

[1]周叶，王道平，赵耀.中国省域物流作业的CO2排放量测评及低碳化对策研究[J].中国人口、资源与环境，2011（09）.

[2]SAMIR ELHEDHLI， RYAN MERRICK.Green supply chain network design to reduce carbon emissions[J].Transportation Research Part D，2012（05）.

[3]郭耀煌，李军.车辆优化调度[M].成都：成都科技大学出版社，1994.

[4]Kim N.S.，Janic M.，Wee B.Trade-Off Between Carbon Dioxide Emissions and Logistics Costs Based on Multiobjective Optimization[J].Transportation Research Record，2009.

[5]Palmer.The Development of an Integrated Routing and Carbon Dioxide Emissions Model for Good Vehicles[J].PHD thesis： Cranfield University，2007.

[6]李柞泳，钟俊，彭蔡红.基于蚁群算法的两地之间的最佳路径选择[J].系统工程，2004（07）.

[7]Yiyong Xiao，Qiuhong Zhao Ikou Kaku，et al.Development of a fuel consumption optimization model for the capacitated vehicle routing problem[J].Computers & Operations Research，2012（07）.

[8]陈京荣.交通网络路径选择及应用[D].兰州交通大学，2009.

（作者单位：上海理工大学管理学院）