徐 旭， 周静远

(1. 上海电机学院 商学院，上海 201306； 2. 燕山大学，河北 秦皇岛 066004)

近几年，液化天然气发展潜力很大。国家统计局数据显示，2017年1～12月份，天然气产量1 474.2×108m3，日均生产4.4×108m3。截止2017年底，我国LNG车拥有量已增到26万辆，LNG加气站2 700座左右[1]。随着天然气运输市场的发展，针对LNG运输的研究不断增多，但主要集中在液化天然气开发利用情况、技术装备的介绍和LNG运输的特点等方面，而对LNG运输的车辆调度研究较少。LNG运输不同于其他普通农产品和一般工业品运输等，属于危险品运输，具有鲜明的运输特性。液化天然气由于易燃，所以通常采用低温常压方式储存在LNG储罐中。目前，国内LNG公路运输的主要工具是低温LNG槽车，容积主要分为30 m3、40 m3、45 m3等几种。国家对LNG槽车的拖挂数量有所限制，通常限制最多拖挂两罐，因此,LNG车的载重量受到限制。但实际交易中客户通常是以整罐为基本单位购买LNG，这使得其每次不能运输超过两家客户,同时，LNG槽车在客户处卸货的时间比一般的货物要长很多，通常要7 h，因此,每辆车等待的时间较长。如何最快、成本最低的满足客户需求,如何尽可能的减少等待时间,合理的车辆调度对LNG公路运输企业获得最大程度的利润至关重要。

1 车辆调度概述

车辆调度问题(Vehicle Routing Problem,VRP)由Dantzig等[2]在1959年首先从旅行商问题中得到启发而提出的。在之后的50多年里，VRP作为一个组合优化问题，成为国内外研究的热点。在2010年,Sherbeny[3]对带时间窗的车辆调度问题做了一系列综述，对其模型和解法进行了详细的阐述。Kim等[4]改进了Solomon插入算法并用于解决带时间窗约束的垃圾收集问题。

目前,LNG运输的车辆调度基本上都应用遗传算法来解决此类问题。遗传算法采用概率化寻优，寻求次优路径。刘振玮[5]根据LNG运输的特殊性，建立了一个LNG企业利润最大化的车辆调度模型，运用遗传算法解决某一LNG物流公司能否及时到货和LNG运输车辆到货后等待卸货时间过长的问题。但是遗传算法的局部搜索能力较差，导致单纯的遗传算法比较费时，算法的搜索速度比较慢。在实际应用中，遗传算法容易产生早熟收敛的问题。相比较下，蚁群算法[6]实现了待解决问题的象限内进行散点式搜索，提升了计算方法的信度与效度，并大大拓展了搜索的外延区间，更适合组合优化的问题。因此，蚁群算法更适用于配送中心车辆调度优化问题。

蚁群算法的基本原理是蚂蚁们在不事先告诉食物的具体位置的前提下遍历多地找食物。当一只找到食物以后，它就会在路上放出一种具有可挥发性的信息素，浓度越大表示路径越近，相反浓度越小表示路径越远；而其他的蚂蚁会根据此信息来找寻食物。但是，有一些蚂蚁并没像这些蚂蚁一样重复着相同的路径，他们会寻找其他路径，如果走出来的其他道路比原来的所有道路更短，那么越来越多的蚂蚁会被吸引到这条较短的路径上。最后，经过一段时间后，蚂蚁们很可能会找出一条最短的路径。当前，基于蚁群算法的车辆调度研究较多。各个学科的专家与运输计算制定者、管理者进行了大量的理论研究和实验分析，取得了很大进展，运用这些研究成果，车辆调度问题己被成功运用到邮件速递、出租车服务、奶品配送、粮食配送中。张强等[7]设计了蚂蚁转移策略、可行解构造策略和信息素更新策略，采用K邻域来限制蚂蚁的转移目标，并采用LK算法优化策略来优化多配送中心粮食车辆调度问题；孙晓莹、徐红霞[8]通过对基本蚁群算法的选择策略和信息素的改进，优化了煤矿运输的车辆调度问题；魏明等[9]建立以车辆数、车辆等待和空驶时间最小为目标的混合整数规划模型，在构建人工蚂蚁随机游走的图基础上，优化蚁群算法，解决区域公交“部分班次被一辆车完成”的集合划分问题；卢晓珊等[10]通过对单环路旅行商问题进行断环分析,将运行线路的好坏反馈给蚁群算法的目标函数优化解决带返程货的车辆路由问题。上述文献都是在蚁群算法的基本原理上，根据每一种问题的特征对蚁群算法进行改进，建立模型，最终解决问题。同样，LNG的运输特性使得蚂蚁一次遍历的地点有数量限制，而且很少，不能直接应用蚁群算法基本原理，所以需要对基本蚁群算法进行改进。

本文将蚁群算法与LNG车辆调度相结合，进一步优化蚁群算法，用两两抽样的方法对某单配送中心LNG企业的车辆调度进行优化，寻找最优路径，达到最小成本，提高蚁群算法的遍历速度，减少整个搜索进程耗时。

2 单配送中心LNG车辆调度数学模型

2.1 问题描述

LNG运输配送车辆调度问题：按收到的客户订单要求，配送中心指示带有一个半挂车的LNG车辆发出，前往配送中心的天然气母站装气，再向客户要求的天然气子站运送天然气，一辆车一次最多送2个子站。然而LNG车卸气时间一般要达到7 h，所以半挂车在前1个子站卸下后不需等待其卸完气，LNG车即可马上前往下1个子站卸气，但LNG车最后要原路返回将前一个子站卸完气后的半挂车拉上，再回到配送中心。全部的天然气子站地理坐标和每次的需求量，确定每台LNG车的载重量，且子站的每次需求量为一辆LNG车或一辆LNG车加一辆LNG罐挂车的载重量。LNG配送物流中心每次配送的最大里程数，由天然气母站提供的天然气可以满足全部子站需求量确定，并且每辆LNG车要在一定的软时间窗内到达子站。其中软时间窗是指假如LNG车辆不能在规定的时间窗内到达子站，那么就会以早到或晚到时间长短为基础收取一定等待成本和罚金[11]，作为LNG运输配送的时间成本。

2.2 模型假设

为了使模型不至于太复杂且具有实用性，假设存在下面几个条件：① 每条配送路线上所有子站的天然气需求量之和小于等于一辆LNG车加一辆LNG罐挂车的载重量。② 每条配送路线的长度小于等于LNG车辆一次配送的最大里程数。③ 天然气供应母站能够满足子站需求，不会断货。④ 每个客户的需求必须满足[12]。⑤ 配送中心的LNG车能够无限供应，能满足子站的需求。⑥ 天然气运输成本与总运距成正比[13]，运输收入与运输距离和需求量成正比，且所有LNG车辆每次运送相同吨位的天然气。⑦ 子站需求的天然气要在时间窗内送达。⑧ 不考虑天然气运输中的其他不可避免的时间。

2.3 模型建立

LNG配送物流中心车辆调度问题(有软时间窗)模型为：配送中心用R0表示，其配送中心的LNG车辆用k(k=1,2,…,n)表示，每辆LNG车和罐挂车载重量都为U；m则为客户需求地个数，子站用集合R(R= {ri|i=1, 2,…,m})代表，每个子站ri的一次需求量为qi，并要求在时间窗[ETi，LTi]之内送达并离开，即子站ri要求的最早到达时间为ETi和最晚离开时间为LTi；L代表天然气供货母站，就在配送中心附近。基本模型为

(1)

式中：z为LNG公司车辆调度的利润；P为LNG的运费，t/km；qi为子站ri的一次需求量；di为从配送中心经过母站L再到子站ri应走的距离数；C为每km所需的汽油费；Dk为第k辆LNG车一次运输中的总路程长度；X为LNG车运一趟的折旧费用；Y为司机运一次的工资；G为完成所有子站的需求量需要运的次数；Tx为LNG车一次的卸货时间；Pz为LNG车早到的等待成本；Pw为LNG车晚到的惩罚成本；WTTik为第k辆LNG车在子站ri早到的时间；WTSik为第k辆LNG车在子站ri晚到的时间；Rk为第k辆LNG车一次可以服务子站个数；D为一辆LNG车一次可以走的最大里程数；Hi为消耗完子站ri的库存所需的时间；RT为子站可以接受的等待时间；SD为司机可以接受的等待时间；ETik为第k辆LNG车到子站ri要求的最早到达时间。

该模型相关的约束条件如下:

式(2)表示根据实际情况，第k辆LNG车一次服务1或2个子站。式(3)表示子站ri的每次的需求量为一辆LNG车或一辆LNG车加一辆LNG罐挂车的载重量；式(4)表示第k辆LNG车在一次运输中的总路径长度小于等于一辆LNG车一次可以走的最大里程数；式(5)表示相邻两辆LNG车到达子站ri的间隔时间不少于消耗完子站ri的库存所需的时间减司机可以接受的等待时间，也不能超过消耗完子站ri的库存所需的时间加子站可以接受的等待时间。

模型主要是解决LNG公司配送走的合理路径问题还有时间上的合理优化，尽量降低等待时间，缩短路程。模型的基本利润=收入-成本。假定配送收入为固定。

Dk就是通过蚁群算法得到的最短路径，当Dk最小时，汽油费最小，利润就可以到达最大；PzTx则是模型中设立的等待时间成本，当车辆的卸气时间不能被合理利用起来去送其他子站时，就相当于产生了成本，因此,在模型中考虑到这一点，有利于提高该公司的潜在利润。

3 蚁群算法改进

(6)

式中:α为信息启发式因子(α值越大表示蚂蚁对信息素更敏感)；β为期望启发式因子(β越大表示蚂蚁对路线长短更敏感[14])。

在一次完整的遍历中,每只蚂蚁仅遍历每个子站一次，用禁忌表控制，其中,tabu(k)表中第k只蚂蚁已走过的所有子站，allowed(k)表示蚂蚁k未曾走过的子站，而且allowed(k)=R-tabu(k)。蚂蚁在行走过路线上释放信息素。

当全部蚂蚁都遍历完路径后，每条路径上的信息素为

式中：ρ为信息素挥发系数；1-ρ为信息素残留系数，0<ρ<1；τ(t+n)为t+n时刻下在路径dij上剩余的信息素量；Δτ为路径dij上信息素增量。

第k只蚂蚁在路径dij上留下的信息素量为

(9)

式中：A为常数，代表所有蚂蚁都走完全程所释放的信息素总量；Dk为第k只蚂蚁在一次遍历中的总路径长度。

其基本求解步骤如下:

(1) 参数初始化：输入配送中心信息，输入蚂蚁数量K，也把子站信息导入allowed(k)；时间t←0；循环次数Nc←0；初始时刻信息素τij(0)←0；放于配送中心R0；设置最大迭代次数Nmax。

(2)Nc←Nc+1；k←1。

(3) 设定蚂蚁k的禁忌表，将tabu(k)表清空，将蚂蚁k的初始子站ri放入tabu(k)表中。

(4) 蚂蚁k依据转移概率公式算出将选择的子站ri前进。

(5) 更改禁忌表tabu(k)，将已遍历的子站ri从allowed(k)移到蚂蚁k的禁忌tabu(k)表里。

(6) 判断allowed(k)中的子站是否都被访问，是则到步骤(7)，不然回到步骤(4)。

(7) 对信息素量进行局部更新，记下当前最优解，并把累计当前最优解列入禁忌表，蚂蚁k←k+1。

(8) 若k≥K，则到步骤(9)，否则回到步骤(3)。

(9) 对K只蚂蚁中的最优解实行全部信息素更新。

(10) 判断迭代条件：若Nc≥Nmax，循环终止得出结果；否则清空禁忌表，回到步骤(2)。

在蚁群算法的基本模型和步骤的基础上，根据配送2个子站运输的特点，加入了一个抽样模型。

式(10)主要表示对所有子站进行两两抽样的样本集，式中XAi表示子站A与其他子站之间进行的组合，n为子站的个数。式(11)限制每只蚂蚁每次只抽出2个子站去遍历。式(12)限制每只蚂蚁最终要原路返回。

图1和图2所示为蚁群算法基本走法和基于2个子站的蚁群算法走法对比图。

图1 蚁群算法基本走法

4 蚁群算法实例分析

以河北某液化天然气运输公司G公司为例，车辆调度主要是以传统的人工或经验方式来进行调度。通过调查发现其运输过程中存在如下问题。

图2基于2个子站的蚁群算法走法

(1) 安排一辆LNG车接到订单后马上出发且只配送一个需求地就返回配送中心。相比满足相同需求量的情况下，使得G公司的车辆的行车路程过长，许多路线交叉，并且出现了本可以避免的空驶现象，增加运输费用，也降低了车辆的利用率。

(2) 由于在需求地卸气时间太长，经常一辆车运一次要2 d时间，而这段卸气时间足够满足运送到其他子站的时间，使车辆等待成本提高了，车辆利用率下降了，也使得更多客户需求不能满足。

因此，现阶段G公司需制定一个合理的车辆调度方案，尽量减少车辆的行驶路径和等待时间，提高车辆的利用率，最大程度的满足客户要求，提升服务质量，使公司利润最大化。

收集到数据如下：其配送中心位置坐标为(0，0)，LNG槽车有100多辆，客户需求的子站共有50个，每个子站的天然气一次需求量为qi(单位：t)，要求送达的时间窗为[ETi，LTi](单位：周期)，所要用到的详细参数见表1；各个子站的位置坐标见表2。这里要考虑的是：每次需求量为60 t的子站可以一次派一辆LNG车加一辆半挂车直接送到，而每次需求量为30 t的子站每次LNG车要走2次，所以需要合理规划。现如今要求制定所有每次需求量为30 t的子站的合理的行车路线，使G公司天然气配送运输的总利润最大。

采用了bpython编写改进蚁群算法进行两两子站抽样得到最短路径，对优化模型求解。其中，通过试算取α为1，β为5，ρ为0.5，A为1。

将各个子站的坐标点转化成矩阵后，代入软件运算得出的蚁群算法抽样图见图3。

图3中25个点对应的横坐标和纵坐标分别代表组合起来的两个子站序号，为：(1,26)(2,20)(3,12)(5,13)(6,23)(4,7)(21,41)(9,42)(8,26)(14,25)(10,28)(11,22)(15,38)(16,46)(17,47)(18,31)(19,50)(34,44)(35,43)(39,30)(32,45)(36,49)(33,48)(37,29)(24,40)。

表1 G公司LNG运输相关参数

表2 G公司LNG运输相关数据

图3 蚁群算法抽样图

每一个坐标代表一个LNG车的路径，综合起来转化成配送的最短路径图见图4。

图4 配送的最短路径图

运算后得出的结果要25辆LNG车，每辆LNG车配送路径如下：

R0→R1→R26，R0→R2→R20，R0→R3→R12，R0→R5→R13，R0→R6→R23，R0→R4→R7，R0→R21→R41，R0→R9→R42，R0→R8→R26，R0→R14→R25，R0→R10→R28，R0→R11→R22，R0→R15→R38，R0→R16→R46，R0→R17→R47，R0→R18→R31，R0→R19→R50，R0→R34→R44，R0→R35→R43，R0→R39→R30，R0→R32→R45，R0→R36→R49，R0→R33→R48，R0→R37→R29，R0→R24→R40。

改进前根据模型式(1)得到G公司的利润：z=85 009.28元；改进后根据模型式(1)得到G公司的最大利润：max z=129 369.52元。因此，按本文所提出的方案进行优化后，G公司利润提高了44 360.24元，优化方案理论上可行。

5 结 语

(1) 本文根据LNG运输车辆调度的车辆的载重量受限和卸气等待时间过长特殊性建立了一个每次只配送2个子站的LNG车辆调度模型，同时进一步改进蚁群算法，将蚁群算法与抽样方法相结合，使得算法具有较快的收敛速度。通过试验证明了改进算法的有效性和可行性，从而从理论上找到了一个LNG车辆调度蚁群算法优化的方案，降低了等待时间，优化了运输路线，提高了公司利润。

(2) 蚁群算法运用中，合理的参数值[15]对确定蚁群算法的效率会产生很大影响。本文是通过试算确定参数，但有待进一步从理论上探索确定蚁群算法合理的参数值。

参考文献

[1] 景团朋, 夏鸿文. 我国LNG汽车发展现状及前景分析[J].交通节能与环保, 2014,10(2):24-27，34.

[2] DANTZIG G B, RAMSER J H. The truck dispatching problem[J]. Management Science,1959,6(1):80-91.

[3] SHERBENY N A.Vehicle routing with time window: an overview of exact, heuristic and metaheuristic methods[J]. Journal of King Saud University(Science),2010,22:123-131.

[4] KIM B I, KIM S, SAHOO S. Waste collection vehicle routing problem with time window[J]. Computers & Operations Research,2006,33:3624-3642.

[5] 刘振玮.LNG车辆运输调度优化模型研究[D]. 大连:大连海事大学,2012.

[6] 吴珂. 基于蚁群算法的单配送中心车辆调度问题研究[D].大连:大连海事大学,2013.

[7] 张强,熊盛武.多配送中心粮食物流车辆调度混合蚁群算法[J].计算机工程与应用,2011,47(7):4-7，39.

[8] 孙晓莹,徐红霞.基于蚁群算法的煤矿运输车辆调度应用研究[J].煤炭技术,2012,31(7):140-142.

[9] 魏明,靳文舟,孙博.求解区域公交车辆调度问题的蚁群算法研究[J].公路交通科技,2011,28(6):141-145,152.

[10] 卢晓珊,何伟,贺永金.邮政运输网络中的邮路规划和邮车调度研究[J].数学的实践与认识,2009,39(17):66-71.

[11] 王飞军,吕建新,杨建伟. 基于蚁群算法的农产品配送车辆调度问题研究[J].中国农机化学报,2014,35(1):57-61.

[12] 郎茂祥.多配送中心车辆调度问题的模型与算法研究[J].交通运输系统工程与信息,2006,6(5):65-69.

[13] 彭霞花,左丹,王秋霞. 基于遗传算法的超市配送中心车辆调度优化[J].山西科技,2009(3):99-101.

[14] 胡夏云. 基于蚁群算法的动态车辆调度问题的研究[D].广州:广东工业大学,2013.

[15] 杨仁法,龚延成.带时间窗车辆调度问题的蚁群算法[J].交通运输工程学报,2009,9(4):71-74.