基于组合算法的易腐货物多式联运路径优化

2022-02-15 08:22马昌喜郭思亮

兰州交通大学学报 2022年1期

董佳，齐博，马昌喜，郭思亮

(1.兰州交通大学交通运输学院，兰州 730070；2.中国铁路兰州局集团有限公司兰州货运中心陇南西营业部羊木营业室，四川广元 628015)

近年来，多式联运作为一种高效的长途运输方式，对普通货物运输有一定影响，对冷链货物运输可降本增效[1].随“一带一路”发展，远距离易腐货物多式联运快速发展[2].航空、水运、公路和铁路等结合起来的多式联运，不仅效率高且成本低.国内对多式联运发展的重视度不断提升，进行了多个专项部署，为不同运输方式间衔接转换提效率；且国内高速公路、高速铁路和高铁网运输服务面广、选择多，为多式联运奠定了基础[3].

国外Deng等[4]为优化运输路线并选择合理运输方式，建立以总成本最低和碳排放最少的混合时间窗最优路径多式联运模型；Lu等[5]考虑运输成本的规模效应，建立了在交付时间和路径容量约束下以成本最小为目标的组合优化模型，建立了一种将遗传算法嵌入到蚁群优化中的双信息素混合算法，并用该算法探讨影响路径选择的因素；Chang[6]分析多式联运路径优化问题的难点，建立多式联运时间窗商品流模型来解决该问题；Deng等[7]建立成本最低的多式联运网络流模型，提出网络模型的KSP算法来求解最优路径，再从最短路径中选择满足时间约束的运输成本最小路径；Gräbener等[8]考虑了时间窗，用改进Martins算法，实现城市交通多目标最优路径模型求解.

国内研究分四部分：一是路径优化；王陆平等[9]考虑速度和拥堵因素，基于Dijkstra算法创建多式联运路径优化模型仿真系统；赵霞[10]设计易腐食品冷链物流多式联运路径优化系统，用蚁群算法处理数据并规划最优路径；周骞等[11]考虑运输、中转和惩罚成本及时间限制等，实现成本低和耗时短的多式联运物流配送网络优化模型，并设计改进遗传算法；尹传忠等[12]考虑交货时间窗、班期限制和在途、中转时间的随机性，将一般多式联运路径优化模型扩展为以总期望成本与时间为优化目标的随机机会约束规划模型，设蒙特卡洛模拟和改进的自适应NSGA-II相结合的算法进行求解；陈汨梨等[13]用随机规划理论估计不确定值，以总成本最低设置货物准时送达概率为模型的机会约束，再用K短路算法求解多式联运路径优化模型.二是运输方式选择和路径规划结合；张润杰[14]建立多式联运路径优化模型，并设计改进遗传算法；蒋洋等[15]考虑运输成本和中转时间用交叉熵法求解；裴骁等[16]考虑运到时限和路径容量约束，以成本最低设计双信息素蚁群-遗传混合算法来解决该组合优化模型.三是多目标多式联运；王正彬等[17]考虑收入、转运成本、存储成本、损失费用和时间价值等，用多目标转换为单目标法求解多目标规划模型；何艳梅等[18]以成本最低和时间最小为目标，设计Dijkstra和GA算法的结合优化，求得模型最优解；万杰等[19]建立运输费用低和服务质量好的多式联运路径优化数学模型，并设计多目标遗传算法进行求解；汤银英等[20]考虑运输时间窗、节点不同运输方式的能力及客户需求，建立时间最短和成本最低的多目标0-1整数规划模型，用NSGA-II算法求解Pareto非劣解集.四是特殊货物多式联运.黄丽霞等[21]同时考虑货物送达时间及路段容量限制，构建总成本最低和风险最小的双目标0-1线性规划模型，设计多目标优化算法求解非劣路径最优解；刘松等[22]考虑铁路和水运发班时间和集装箱转运次数限制，设计成本低的遗传算法进行路径优化模型求解，之后文献[23]考虑制冷、货损和冷藏费用，建立碳排放限制下的优化模型，用改进遗传算法进行求解；李玉民等[24]考虑中间节点混合时间窗及目的地收货软时间窗约束，构建总成本最低的多式联运路径选择与运输方式组合模型，用混合田口遗传算法求解.

多数学者集中研究运输数学规划模型和路径算法.遗传和禁忌搜索组合算法最流行，文献[25]对混合算法可行性进行了理论分析；现有文献中有两种混合方式：文献[26-31]为改善遗传算法局部搜索能力，将交叉和变异算子改进成具有记忆功能的禁忌交叉和禁忌变异算子.文献[32-33]对问题进行全局搜索，用遗传算法得到较好的禁忌初始解，再进行局部搜索得到最优解.该文在研究易腐货物多式联运路径规划和方式选择时，考虑不同运输方式运距、运费和中转耗时的不同、货物运到时限和货物时间窗等，建立低成本易腐货物多式联运路径优化选择模型，并用第二种方法设计遗传-禁忌搜索的组合算法，来求最佳运输方式组合下的低成本最优路径.模型研究思路：徐林坤[34]建立最小成本单目标路径优化模型；李世昌[35]构建带时间窗的多商品流广义费用最优的非线性数学优化模型；该文建立以成本最低和时间最小化的双目标模型，设计遗传-禁忌搜索组合算法来求解.文献[36]中多目标函数求解会存在相互约束；若想求整体最优，需得把多目标转化为单目标或将多目标应用于求解多目标的算法中；该文运用遗传-禁忌搜索组合算法，先基于遗传算法求出一个基于成本最低的初始解，再用禁忌搜索基于时间最小进行优化搜索，再求出较好的Pareto非劣解.文献[37]采用的易腐货物多式联运是对单一易腐货物进行运输；该文用的是对多种食品、不同目的地的统一规划运输.

1 问题描述与建模

1.1 问题描述

运输易腐货物前规范好运输流程并合理分配货物堆放顺序、运输中实时监测调温调湿、运输后收货人尽快提货.该文运输易腐货物时考虑保质期，建立低成本易腐货物多式联运路径优化模型，设计遗传-禁忌搜索的组合算法，借鉴文献[38]加入时间窗来求最佳运输方式的低成本最优路径.

1.2 模型假设：

1)货物箱体运输前已预冷，箱内温度确定后，运输途中保持不变；

2)暂不考虑交通拥堵和火车轮船班期情况，车辆行驶速度固定；

3)同一批货物在运输过程中以集装箱一次性运输；

4)货物转运只发生在城市节点上，且最多转运一次；城市间货物转载运输方式只能是一种；

5)各节点均可进行货物转运，且同节点上同种运输方式间转运费用为0.

1.3 模型建立

1.3.1 决策变量

(1)

式中：N为网络节点，i,j∈N；M为公路、水运和铁路运输，m,n∈M={1.2.3}；Z为易腐货物品类，1,2,3,…,h.

(2)

(3)

1.3.2 目标函数

1)低成本

(ch+ceth)+cP.

(4)

图1 易腐货物品质规律图

图2 节点服务时间窗

(5)

(6)

2)短耗时

(7)

1.3.3 约束条件

1)两城市间最多选择一种运输方式：

(8)

2)最多转运一次：

(9)

3)节点运输连续性：

(10)

4)节点流量平衡约束：

(11)

5)在途时间和中转时间之和小于保质期：

(12)

2 遗传-禁忌搜索组合算法

鉴于文献[39]，建立易腐货物多式联运路径优化选择模型后，考虑遗传算法全局搜索能力强和禁忌搜索记忆优势和结果的好坏大都依赖于初始解和领域结构的特点，设计遗传-禁忌搜索组合算法，具体过程是先用遗传产生一个较好的初始解，再用禁忌进行局部搜索找出全局最优解.

2.1 遗传算法操作

Step1：染色体编码

用可变长路径编码方式进行两段式编码；第一段0-1编码，代表联运时货物是否经过该节点，构成一条运输路径，起讫点需提前输入；第二段实数编码，代表两城市间的运输方式，随机产生铁路、公路或水运.染色体编码如图3所示.当遗传算法交叉和变异操作都执行完后，最优解是第二段插入到第一段中构成一条混合式运输线路.

图3 染色体编码

Step2：适应度函数为运输总成本的倒数

(13)

Step3：染色体解码

运输路径和运输方式全部0-1编码会导致染色体编码长度过长，而两段式染色体编码易于解码[40].1)第一段：起讫点由运输需求获取；中间是0-1编码，解码位置为1的，可连成一条路径.2)第二段：随机生成运输方式1，2，3.3)第二段插到第一段构成完整路线.

Step4：初始种群

据网络图求得连通矩阵；用Dijkstra算法求得最优路径为第一段编码，再随机生成运输方式，构成初始染色体；循环产生染色体，达到种群数量为止.

Step5：约束条件

用Dijkstra算法求得最短路没考虑时间窗限制，需计算节点间运输时间，早或晚均产生惩罚成本.不满足时间窗要求的，先求各个体总运输时间，再判断是否超过要求，若超时则以一定概率删除；从余下群体中随机复制删除个体数来替代.

Step6：用轮盘赌选择机制进行选择操作

Step7：交叉操作

染色体第一段用两点交叉法，第二段不进行交叉操作.

Step8：变异操作

起讫点的值不变，中间段用两点变异如下所示.

Step9：非法个体进行修复

在进行交叉和变异操作时，可能会产生无效路径，即无通路；则用动态规划法找该节点与相邻的上一节点有效路径代替，重新生成通路，直到找到有效路径.

若出现环路，即某城市访问了两次，此时需去除中间所有节点，再删除一个相同节点.当第一段节点发生变化了，则随机产生城市间的运输方式作为第二段编码，其余不变，如图4所示.

图4 环路处理

Step10：形成连通路径并破圈

1)寻找各节点的关联节点集；

2)将城市路径节点分为U集和V集(U含起点，V含其余节点)；

3)从U的末关联节点中选择适应度值最大的节点纳入U，并从V中剔除；

4)若适应度值最大的节点不是终点，则重复第③步，达到终点为止.

2.2 禁忌搜索算法操作

禁忌搜索的记忆和局部搜索优势结合禁忌准则和藐视准则后，保证多样化，既避免重复搜索，又可赦免被禁忌的优良状态，最终实现全局优化[41].

2.2.1 邻域操作

用2-opt交换法定义邻域，先删除两段运输路径，再通过Dijkstra法生成两条新路径替换它们，并在其中选一部分作为产生候选解的搜索对象[37].

2.2.2 禁忌准则

目的是避免迂回搜索.一是设置禁忌对象，即状态本身.二是禁忌长度，即禁忌对象不允许被选取的最大次数[38]，一般被插入的边小于被删除的边的禁忌长度.

2.2.3 藐视准则

将最先前的一些禁忌状态重新启用，计算其适配值，若优于“Best so far”状态，则把该解作为当前状态最优解，并更新最优解的状态[42].

2.2.4 精英保留和终止策略

更新全局最优解用精英保留法；终止策略用步数终止原则.

2.3 算法流程

鉴于文献[43]，遗传-禁忌搜索组合算法中，遗传算法用可变长路径编码，随机选取运输方式产生初始种群，计算适应度函数，再用轮盘赌竞争选择策略进行选择，若形成通路且无环，则输出历代最优解，再从中选出一个适应度值最好的个体作为禁忌搜索算法初始解；进行禁忌搜索算法时，定义初始解的领域映射，产生一定个数的候选集，排序并保留前一半的最好候选解，满足藐视准则和约束条件，并达到一定迭代次数，输出最优解，如图5所示.

图5 算法流程图

3 易腐货物多式联运算例分析

多种类易腐货物路径规划和运输方式的选择，产销地已知，需规划最优路径.模拟现实场景建立运输网络，验证模型有效性，得多个Pareto非劣解集进行对比分析.选取非劣解集中较优解，对比多式联运与单一运输方式产生的费用，验证该模型及算法的可行性，分析各影响参数对结果的影响程度，验证多式联运在易腐货物运输中的优势，提出有益建议.

3.1 算例背景

据国内现实情况构建多式联运网络，考虑起讫点供需关系选合适的易腐货物进行运输，对多商品流OD、运输线路及参数进行选取，构建算例环境.

3.1.1 OD分布

考虑各生产基地优势产品和实际销售量，选苹果、圣女果、豆角和冻羊肉等易腐货物；四种运输的易腐货物OD分布情况如图6所示.

图6 OD分布

3.1.2 运输网络结构

把国内枢纽城市及易腐货物供需地作为网络节点.结构中共有23个节点，51条运输路线，各路径上至少有两种及以上运输方式.节点布局及节点间联运网络运输图如图7所示.

图7 网络图

3.2 统计数据

3.2.1 相关指标

3.3 案例计算结果

在Matlab中用遗传-禁忌搜索组合算法进行编程求解.遗传阶段：种群规模NP=200；交叉概率Pc=0.8；低频变异可防止丢失重要基因，高频变异可使算法陷入随机搜索[40]，该文Pm=0.05；禁忌搜索阶段：全部领域解个数选10个；最大迭代次数为500次.

3.3.1 Pareto非劣解集

对双目标模型进行组合算法求解，得到各个易腐货物的Pareto非劣解集，如表7所列.

表7 Pareto非劣解集

由上述非劣解集看出，各易腐货物多式联运路径符合实际情况，验证了在实际生活中的可行性.非劣解集中，当费用最少时，时间不一定最小，要据实际情况选较合适的运输方案.

3.3.2 总费用及构成

各易腐货物多式联运总费用及各组成部分取值如表8所列，易腐货物各费用占比如图8所示.

图8 易腐货物各费用占比

表8 各易腐货物总费用

3.4 对比单一运输和多式联运

多式联运大都优于单一运输，分别研究了多式联运、公路和铁路运输的费用，其总费用和总时间计算结果如表9所列，对比图如图9所示.

表9 单一运输方式总费用和总时间表

如图9(a)所示，多式联运产生总费用略高于铁路运输，且略低于公路运输，因此多式联运在易腐货物运输中有成本优势；如图9(b)所示，多式联运过程中的总时间略高于公路运输时间，略低于铁路运输总时间，验证了多式联运的高效.近些年推广易腐货物集装箱运输可节约成本、提高效率.

图9 不同运输方式总费用和总时间对比图

3.5 灵敏度分析

公路、铁路和水运运输中，水运范围较窄、竞争小；且铁路公路网遍布全国，有很大优势.公路在短距离运输中很便利，但在中长距离运输时，铁路占成本优势，若要提升效率和降低成本可提高铁路货运量，基于案例研究提升铁路旅行速度与降低铁路运价对联运总费用的影响程度，并提出有益建议.

3.5.1 成本构成

易腐货物多式联运各耗用成本占总成本的比例如图8所示.运输成本占比最多；铁路运量大、运价低，在多式联运中应得到充分利用，若运输途中无铁路，则用公路联合运输，极大降低总成本.中转成本占比最小，要尽量采用直达运输，减少中转次数.每次运输不一定都要产生蓄冷和时间惩罚成本，若有也是极低；长距离运输中圣女果和豆角在夏季不易保存，易产生质损和时间惩罚成本，提升运输工具速率和减少运距均可降低成本；苹果和冻羊肉不易变质，若时间要求不苛刻，可选择成本低的铁水联运，运输途中基本不产生质损和时间惩罚费用.

3.5.2 运到期限

不同易腐货物运到期限不同，通常与总成本成负相关，要想降低多式联运运输成本，可推迟货物运到期限.运输某易腐货物的时间要求苛刻，建议选择公路或铁路运输，速度快且货物品质有保障；若某易腐货物对时间要求不高，则选铁水联运来降低成本.多式联运运输圣女果和豆角时，质损费用小于铁路运输费用；当运到期限较低时，可选速度快的公路运输；当运到期限较高时，可选择成本低的铁路运输；运输苹果和冻羊肉时，当运到期限较低时，多采用公路或铁路运输，但成本提高了；当运到期限较高时，可选择铁水联运，总成本降低了.所以易腐货物长距离运输中，铁路速度快，能缩短运输时间并降低费用，最终降低多式联运总费用.

3.5.3 运输里程

不同运输里程收费价格不一.公路在一定距离内，运价与运距成负相关，超过该值运价与运距成正相关.铁路运输较稳定，运价随运距增加而减少.易腐货物运输里程越长，铁路运价比公路低.长距离运输时，随运距增加，公路和铁路成本差距渐大.该文易腐货物均是长距离运输，用多式联运进行配送来权衡成本和时间.运输圣女果和豆角时用铁路运输会使成本较低，若时间要求不严格，也可公转铁；短距离时公路和铁路运输成本差不多，但耗时短.运输苹果和冻羊肉时宜用铁路运输节约成本.易腐货物资源丰富且经济发展不平衡，大都属于长距离运输；发挥运量大、安全可靠和运价低的特点，常以铁路运输为主要方式，有助于完善国内多式联运货物运输体系，提高运输效率并保证货物品质.短距离运输中，公路适应性好且灵活性强，误差不超过半小时.

4 结论

在实际配送易腐货物时，该文设置早到或晚到两种产生惩罚费用的情况，考虑不同运输方式运距、费用、中转耗时和运到期限、时间窗约束等，建立遗传-禁忌搜索组合优化算法求最优路径并选择合适运输方式，最后求得较好的Pareto非劣解.通过实例对比多式联运和单一运输方式的各费用和时间来看，体现了多式联运的优势，验证了该文在理论上与应用上的巨大价值.在多式联运中各因素都应考虑在内，降本增效.在研究易腐货物多式联运路径规划和运输方式选择时存在不足，望今后学者针对以下方面对其进行深入研究：

1)对我国易腐货物多式联运存在问题分析不够全面；

2)研究的实际转运时间、转运成本应据具体情况而定；

3)易腐货物多式联运影响因素考虑不全面，运输中意外将对运输费用有一定影响，需考虑；

4)一个OD对不可分批运输，未来可考虑货物的分批与合运；

5)仅研究集装箱物流中的运输环节，未来可考虑从仓库布局、库存策略等的整体规划.