基于混合算法的多目标多式联运路径选择问题研究

万 杰，魏 爽



基于混合算法的多目标多式联运路径选择问题研究

万 杰，魏 爽

(河北工业大学经济管理学院，天津 300401)

针对多目标多式联运路径选择问题，在综合分析多式联运现状的基础上，集成考虑运输成本、运输时间以及物流服务质量3个方面因素，构建混合整数规划模型，其优化的目标是最小化运输成本、运输时间的同时，最大化物流服务质量；考虑到客户的不同侧重点和差异化需求，确定3个目标的权重，设计遗传算法和蚁群算法相结合的混合算法对模型进行求解．以“西安—柏林”为例进行算例分析，将所求结果与遗传算法、蚁群算法进行对比，结果表明：当客户对时间和成本重视程度较高时，混合算法、遗传算法和蚁群算法求得最优解的迭代次数分别为164次、170次和183次，最优路线为西安—郑州(铁路)—大连(铁路)—鹿特丹(水路)—柏林(铁路)；当客户对时间和物流服务质量重视程度较高时，3种算法求得最优解的迭代次数分别为112次、117次和150次，最优路线为西安—重庆(公路)—柏林(铁路)；当客户对成本和物流服务质量重视程度较高时，3种算法求得最优解的迭代次数分别为115次、120次和160次，最优路线为西安—郑州(铁路)—深圳(铁路)—鹿特丹(水路)—柏林(铁路)．研究表明：设置不同的目标权重时，模型和混合算法均能够有效地为多目标多式联运路径选择问题提供实用性的优化方案和路线参考．

多目标；多式联运；路径问题；混合算法

随着“一带一路”倡议的提出和国际贸易的加大，多式联运在运输领域占有越来越重要的地位．多目标多式联运路径选择问题也成为该领域的研究热点与难点．多式联运是指将货物采用两种或两种以上的运输方式运送到目的地．随着物流技术的不断发展，以及多式联运货运需求不断增加，国内外学者对多式联运的路径优化研究也逐渐深入．

综合目前的研究成果，物流路径选择问题是多式联运的核心问题，即在不同的因素情况下的模型构建和算法优化．多式联运物流路径选择受运输费用、运输时间、服务质量、运输风险、技术水平、环境因素以及行程利用率等因素的影响[1]，例如Cho等[2]选取成本和时间为目标，应用从釜山到鹿特丹的实际运输路线来验证标签算法；Seo等[3]选取运输费用、运输时间以及信心指数研究重庆到荷兰鹿特丹的笔记本电脑出口多式联运路线选择问题；付新平等[4]选取运输时间和运输费用，研究从武汉到欧洲的国际集装箱多式联运线路问题；李玉民等[5]选取运输时间、运输费用和碳排放，构建中多式联运路径优化的多目标优化模型．目前国内外对于物流服务质量概念界定和构成要素还没有统一的见解，最广泛使用的以时间、地点、效率、仓储为基础的物流服务质量．如Limbourg 等[6]设计了SERVQ UAL量表，将物流服务质量划分为4个维度，用越南岘港市的200家物流客户进行实证研究；郑茜[7]将运输时效性作为物流服务质量指标，构建多式联运优化模型．对于多式联运路径选择优化研究的求解算法多为启发式算法，其中包括蚁群算法[8]、遗传算法[9]、模拟退火算法[10]和声搜索算 法[11]等，目前国内外对于多式联运混合算法的研究较少，Wang等[12]研究了集装箱多式联运系统中集装箱类型的选择和运输方式的组合优化，构建了模糊需求下运输成本最小化的数学模型，并利用改进的粒子-蚁群优化算法进行求解；Jiang等[13]研究了寻求运输成本、转运费用等最小化的多式联运运输方案选择问题，并提出采用混合交叉熵算法来对模型进行求解.

通过以上国内外文献的研究发现，多数研究成果考虑运输成本、运输时间建立模型，且少有文献考虑多式联运中物流服务质量．针对以上问题，本文综合考虑运输成本、运输时间以及物流服务质量3个因素，构建混合型整数规划模型，将遗传算法和蚁群算法相结合对模型进行求解，结合不同的货物需求，求解不同的运算结果，将混合算法的结果与蚁群算法以及遗传算法做对比，验证了该算法的可行性与正确性.

1 多目标多式联运的混合整数规划模型

1.1 问题描述

图1 传统多式联运网络

1.2 相关假设

(1) 货物的转载只能发生在城市节点，且在城市节点只能转载一次．

(2) 货物在运输途中不能分割．

(3)货物在城市节点之间只能选择一种运输方式．

1.3 模型描述

表1 符号说明

Tab.1 Symbol description

多式联运选择不同的运输路线会导致不同的服务质量．本文使用物流服务能力系数来衡量各城市节点的物流服务能力．各城市节点依据自身资源(如基础设施建设、经济条件和运输组织资源等)与各种能力(如安全性、可靠性以及便利性等)为货物提供物流服务，对于不同的城市节点来说，自身资源和能力越好，所提供的物流服务质量越好．因此，综合各城市节点状况与特点，选取基础设施建设水平、经济发展水平以及多式联运物流服务水平来对城市节点进行分析．

本文多目标多式联运问题的混合整数规划包括以下3个函数．

(1)运输费用为

(1)

 (2)

(2) 运输时间为

   (3)

(3) 物流服务质量为

 (4)

其中

 (5)

 (6)

约束条件为

     (7)

    (8)

  (9)

 (10)

2 多目标多式联运模型的混合算法求解

2.1 混合算法

蚁群算法根据蚂蚁群体之间的信息传递达到寻优的目的，其具有正反馈机制、分布式全局优化的特点，但会因为初期信息素匮乏，导致求解速度慢．遗传算法具有全局搜索能力，搜索过程简单易理解，但存在对反馈信息利用不够的问题，且当求解到一定的范围，会出现冗余迭代的现象，求精确解的效率低．

为了克服这两种算法各自的缺陷，使其优势互补，在算法的设计过程中，首先评估个体序值，选取前20%通过遗传算法的随机搜索、快速、全局收敛性产生初始解，为了保证种群的多样性，在后80%的个体中随机选取个体，共同作为新一代个体作为蚁群算法的初始信息素，然后利用蚁群算法正反馈机制与求解精确度高的特点来求最优解[14]．同时，在混合算法中，通过合理设置遗传算法的迭代次数，避免由于过早或者过晚的迭代而影响混合算法的性能．混合算法同时发挥了遗传算法和蚁群算法的优势，提高了求解效率和时间效率．混合算法流程如图2所示．

2.2 混合算法流程

(1)统一量纲：因本文3个目标函数之间存在相互约束的关系，一个目标结果最优则会导致其他两个目标达不到最优，而作为一个系统需要考虑整体最优．所以应将多目标转化为单目标优化，即

图2 混合算法流程

 (11)

且对于不同的客户和货物，影响路径选择的因素对其的重要程度是不同的，例如急于交货的货物更注重时效性、普通大宗货物更注重价格便宜、电子类产品更注重物流服务质量等，因此不同的因素在进行路径选择时拥有不同的权重．对于每一个评估者可以根据个性化的需求和重视程度确定相应的权重．本文将敏感度进行等级划分：{极强、较强、一般、较弱、极弱}，对应的数值分别为{9、7、5、3、1}．

其次由于目标函数单位不一致，需要通过统一量纲规范化各目标函数

 (12)

 (13)

(2)随机选取城市节点与运输方式，初始化条路线，并对其函数值进行排序，并选取20%个体进行遗传操作，在后80%个体中随机产生条个体进入下一代．遗传算法操作步骤如下．

步骤1 编码．对节点城市和运输方式进行采用二进制编码，具体编码方式见图3．每一条染色体被分为两个部分：在城市节点部分，0、1变量表示是否通过该城市节点，在运输方式部分，0、1、2、3表示铁路、公路、水路和航运4种运输方式．

图3 染色体编码示意

步骤2 选择．为了能将更好的信息传递给下一代同时保证种群的多样性，本文使用轮盘赌选择法进行操作．选择概率的公式为

 (14)

步骤3 交叉．为了防止当前群体的最优个体在下一代发生丢失，导致遗传算法不能收敛到全局最优解，本文采用单点交叉方式．选择的父辈个体通过交换部分信息，从而产生新的运输方案．详见图4．

101…100321…312 110010312…121

↓

101…100322…121 110010311…312

步骤4 变异．本文中采用单点变异方法．在随机选取的个体中上按一定的概率改变基因，从而会产生新的个体．

(3)遗传算法终止：为了保证上一代个体与蚁群算法有效的融合，在遗传算法中设置最最大迭代次数，同时在迭代过程中计算群体的进化率，设置子代群体的最小进化率．如果在设置的迭代次数的范围内，群体的进化率小于最小进化率，则说明遗传算法的优化速度已经大大降低，终止遗传算法，进入蚁群算法．

 (15)

步骤2 将只蚂蚁放在个城市节点上，使只蚂蚁随机生成一个城市节点作为蚂蚁下一个要走的城市节点，按照概率选取第3个城市，即

(16)

步骤3 采用蚁周模型对信息素进行更新，要求一周内只有当前最优解进行更新，路径轨迹更新规则为

 (17)

 (18)

(4)输出最优解及目标函数值．本文采用最大代数为终止条件，算法迭代到最大代数时迭代终止．

3 算例计算与结果分析

3.1 算例分析

表2 3种运输方式所需的数据及其来源

Tab.2 Data required for the three modes of transport and their sources

表3 3种运输方式中转时间以及中转费用

Tab.3 Transit time and transfer fee for three modes of transportation

运输中转中转时间/(h·m-1)中转费用/(￥·m-1) 公路—铁路30.41219.2 铁路—水路54.91676.4 水路—公路42.71371.6

3.2 测试结果

图5 对时间以及成本重视程度较高时3种算法的迭代示意

图6 对时间以及物流服务质量重视程度较高时3种算法的迭代示意

图7 对成本以及物流服务质量重视程度较高时3种算法的迭代示意

表4给出了3种算法的求解结果，从仿真结果可以看出，3种方法求解问题的最终结果比较一致，但混合算法具有更快的收敛能力，说明了混合算法可以得到更加合理的寻优结果，具有更好的优化性能．

表4 3种算法求解结果的比较

Tab.4 Comparion of the results of the three algorithms

4 结 语

本文构建了综合考虑运输成本、运输时间以及物流服务质量的混合整数规划模型，提出了混合算法来求解该模型，设计了西安—柏林的算例进行测试，定量地分析了在不同重要程度下的不同运输方案的选择，结果表明，当对运输成本、运输时间以及物流服务质量3方面的不同要求下，模型与算法能够有效地提供优化方案．

由于数据的限制，本文随机生成客户的期望与实际物流服务水平，但在实际情况下，客户对物流服务质量的打分可能分为多个等级，在未来的研究中，可以基于实际情况设计调查问卷对模型进行改进与 完善．

［1］ 伍转青. 物流企业多式联运运输线路选择研究[J]. 铁路采购与物流，2011，6(2)：52-54.

Wu Zhuanqing. Research on selection of multimodal transport routes in logistics enterprises[J]. Railway Purchasing and Logistics，2011，6(2)：52-54(in Chinese).

［2］ Cho J H，Kim H S，Choi H R. An intermodal transport network planning algorithm using dynamic programming—A case study：From Busan to Rotterdam in intermodal freight routing[J]. Applied Intelligence，2012，36(3)：529-541.

［3］ Seo Y J，Chen F，Roh S Y. Multimodal transportation：The case of laptop from Chongqing in China to Rotterdam in Europe[J]. Asian Journal of Shipping & Logistics，2017，33(3)：155-165.

［4］ 付新平，何瑜莎，邹 敏，等. 国际集装箱多式联运线路选择研究[J]. 铁道运输与经济，2017，39(12)：12-17.

Fu Xinping，He Yusha，Zou Min，et al. A study on the route selection of international container transport in the multimodal scenario[J]. Railway Transport and Economy，2017，39(12)：12-17(in Chinese).

［5］ 李玉民，郭晓燕，杨 露. 考虑多目标的中欧集装箱多式联运路径选择[J]. 铁道科学与工程学报，2017，14(10)：2239-2248.

Li Yumin，Guo Xiaoyan，Yang Lu. Route optimization of China-EU container multimodal transport considering various factors[J]. Journal of Railway Science and Engineering，2017，14(10)：2239-2248(in Chinese).

［6］ Limbourg S，Giang H T Q，Cools M. Logistics service quality：The case of Danang City[J]. Procedia Engineering，2016，142∶124-130.

［7］ 郑 茜. 低碳约束下多式联运路径优化问题研究[D]. 杭州：浙江工商大学经济管理学院，2017.

Zheng Qian. Research on Multi-modal Transport Path Optimization Problem under Low Carbon Constraints [D]. Hangzhou：School of Economics and Manage-ment，Zhejiang Gongshang University，2017 (in Chinese).

［8］ 刘维林. 基于动态蚁群算法的集装箱国际多式联运路径优化研究[J]. 北京交通大学学报：社会科学版，2012，11(3)：57-62.

Liu Weilin. Route optimization of international multimodal container transportation based on dynamic ant colony algorithm[J]. Journal of Beijing Jiaotong University：Social Sciences Edition，2012，11(3)：57-62(in Chi-nese).

［9］ 龚景海，刘锡良. 基于遗传算法的网格结构优化方法[J]. 天津大学学报，2000，33(1)：93-96.

Gong Jinghai，Liu Xiliang. Grid structure optimization method based on genetic algorithm[J]. Journal of Tianjin University，2000，33(1)：93-96(in Chinese).

［10］ 郭丹丹. 基于模拟退火混合遗传算法的多式联运优化问题的研究[D]. 大连：大连海事大学理学院，2012.

Guo Dandan. Research on Multi-modal Transport Opti-mization Problem Based on Simulated Annealing Hybrid Genetic Algorithm[D]. Dalian：School of Science，Dalian Maritime University，2012(in Chinese).

［11］ 赖志柱. 和声搜索算法优化多时间窗多式联运运输方案[J]. 计算机应用，2013，33(9)：2640-2642，2693.

Lai Zhizhu. Harmony search algorithm for solving selec-tion ofmultimodal transportation scheme with several time windows[J]. Journal of Computer Applications，2013，33(9)：2640-2642，2693(in Chinese).

［12］ Wang H，Wang C. Selection of container types and transport modes for container multi-modal transport with fuzzy demand[J]. Journal of Highway & Transportation Research & Development，2012，12(3)：65-74.

［13］ Jiang Y，Zhang X，Wang Y. A cross-entropy method for solving selection of multimodal transportation scheme [J]. Journal of Transportation Systems Engineering and Information Technology，2012，12(5)：20-25.

［14］ 陈亚云，韩文涛，崔鹤平. 遗传算法与蚁群算法的改进融合[J]. 中国农机化学报，2014，35(4)：246-249.

Chen Yayun，Han Wentao，Cui Heping. Improved fusion of genetic algorithm and ant colony algorithm[J]. Journal of Chinese Agricultural Mechanization，2014，35(4)：246-249(in Chinese).

［15］ 付新平，张 雪，邹 敏，等. 基于价值量模型的中欧班列经济性比较分析[J]. 铁道运输与经济，2016，38(11)：1-5.

Fu Xinping，Zhang Xue，Zou Min，et al. Analysis on economics of China-Europe block trains based on the value model[J]. Railway Transport and Economy，2016，38(11)：1-5(in Chinese).

(责任编辑：孙立华)

Multi-Objective Multimodal Transportation Path Selection Based on Hybrid Algorithm

Wan Jie，Wei Shuang

(School of Economics and Management，Hebei University of Technology，Tianjin 300401，China)

To address the problem of multi-objective and multimodal transport path selection，a mixed integer programming model is constructed by integrating transportation cost，transportation time，and logistics service quality. The optimization goal is to minimize transportation cost and transportation time and maximize logistics service. Owing to the different priorities and needs of customers，the weights of the three targets are determined by using a hybrid algorithm that combines genetic algorithm and ant colony algorithm，to solve the model. Taking Xi’an-Berlin path as an example，the analysis result of the hybrid algorithm is compared with those of the genetic algorithm and the ant colony algorithm. The results show that when the customer pays more attention to time and cost，the hybrid algorithm，genetic algorithm，and ant colony algorithms require 164，170，and 183 iterations，respectively，to obtain the optimal solution. In this case，the optimal route is Xi’an-Zhengzhou(railway)-Dalian(railway)-Rotterdam (waterway)-Berlin(railway). When the customer pays more attention to the time and logistics service quality，the hybrid，genetic，and ant colony algorithms require 112，117，and 150 iterations，respectively，to obtain the optimal solution，and the optimal route is Xi’an-Chongqing(highway)-Berlin (railway). When the customer pays more attention to the cost and logistics service quality，the hybrid，genetic，and ant colony algorithms require 115，120，and 160 iterations，respectively，to obtain the optimal solution，and the optimal route is Xi’an-Zhengzhou(railway)-Shenzhen(railway)-Rotterdam(waterway)-Berlin (railway). The research shows that both models and hybrid algorithms can effectively provide practical optimization schemes and route references for multi-objective multimodal transport path selection problems when setting different target weights.

multi-objective；multimodal transportation；path problem；hybrid algorithm

10.11784/tdxbz201807034

U15

A

0493-2137(2019)03-0285-08

2018-07-26；

2018-09-03.

万 杰（1972—  ），女，博士，教授，jeanwan1218@163.com.

魏 爽，1224871115@qq.com.

河北省高等教育教学改革研究与实践项目(2017GJJG021).

Hebei Province Higher Education Teaching Reform Research and Practice Project(No. 2017GJJG021).