带时间窗的整车多式联运路径优化模型研究

谢雪梅 杨家其

(武汉理工大学交通学院 武汉 430063)

带时间窗的整车多式联运路径优化模型研究

谢雪梅 杨家其

(武汉理工大学交通学院 武汉 430063)

整车物流作为汽车物流核心组成部分，如何优化控制成本成为物流和汽车行业关注点.针对整车物流路径优化问题，在实现物流成本最低和满足时间约束的条件下，引用多式联运理论，构建带有时间窗的整车物流多式联运0-1整数规划模型，综合考虑运输成本、换装成本、风险成本和提早到达造成的仓储成本或推迟到达造成的惩罚成本，设计基于Matlab的遗传算法进行求解，并结合实例进行验证分析.结果表明，该模型和算法对于解决整车多式联运线路优化具有可行性和实用性.

整车物流；多式联运；时间窗；路径优化；遗传算法

0 引 言

整车物流作为汽车物流的核心，对于如何控制物流成本成为人们关注的焦点.整车物流的运输方式包括水路、公路和铁路，且各具特点.我国整车物流采用铁路运输占比仅为7%，公路运输则高达85%，其余仅8%为水路运输[1].然而公路运输具有成本和污染等方面的局限性，且只采用一种运输方式在物流成本与时效性上的缺陷日渐明显，因此，在整车物流过程中如果将铁路、公路、水路灵活分配运用，发挥各自优势，引用多式联运的思路，对于降低物流成本具有重要的意义.

目前，针对带时间窗的车辆路径问题已有一些研究，易云飞等[2]采用改进伊藤算法求解带有软时间窗的车辆路径配送问题，汪秋云等[3]论证了运用混合算法对带有软时间窗的车辆路径优化的求解优势.针对多式联运问题，Ekki[4]以配送时间和路程最短为目标，不考虑不同运输方式的单位成本差异，用最短时间完成货物配送.Chang[5]构建多目标多式联运优化模型，实现不同商品共同配送.以上都是针对这两类问题分别展开研究，带时间窗的车辆路径的研究主要为带软时间窗约束，而多式联运的研究对象较多针对集装箱，但将两者综合研究较少，同时对整车物流多式联运的研究也较少.相对于传统单一的运输方式系统，多式联运具有降低成本、节约时间等优势.文中将带时间窗的车辆路径问题引入多式联运的理论，对于整车物流成本问题，建立带有时间窗的多式联运线路优化模型，充分发挥多式联运的优势，实现降低整车物流成本的目的.在实际运用中解决车辆路径问题需要寻找有效的算法求解，求解算法包括启发式算法及精确算法.规模较大的路径问题采用启发式算法，包括粒子群算法、遗传算法、邻域搜索算法、蚁群算法等，而精确算法主要适用于规模较小的路径问题[6].窦莉薇[7]采用优化后的蚁群算法研究路径问题.Chen等[8]开拓了迭代邻域下降算法处理配送时间及配送货物种类具有周期性的车辆路径问题.储庆中等[9]针对危险品，对其运输线路进行优化，采用遗传算法，产生最稳定的最优解.王旭等[10]以总成本最低为目标，但未考虑风险成本，采用遗传算法求解.徐珏等[11]根据配送点分散且各自配送点需求量小的特点，建立运输线路网，使用遗传算法优化，使得配送成本降低及送达时间更为准确.遗传算法在解决路径问题时，具有很好的收敛性及良好的全局搜索能力，计算时间短且精度高，过程较为简单[12]，因此，文中采用遗传算法进行模型求解.

基于此，文中将整车物流与多式联运相联系，构建带时间窗的整车多式联运路径优化模型，实现物流总成本最低.综合考虑运输成本，换装成本，仓储成本或惩罚成本和运输和换装可能发生的风险成本，采用遗传算法进行求解，在Matlab中实现，并结合案例进行分析.

1 带有时间窗的整车物流多式联运模型分析与构建

1.1 问题描述

整车物流运作模式为车辆从主机厂下线入库到整车分拨中心，进行检查和测试后，再由整车分拨中心(vehicle distribution center，VDC)经过一次运输至各区域整车仓储中心(vehicle storage center，VSC)，VSC起到中转的作用，最后从各区域整车仓储中心二次运输至分散的经销商[13]，见图1.车辆由主机厂短途运输到整车分拨中心，主要为公路运输.而一次运输为中长途运输，有铁路、公路、水路三种方式可选，这是整车物流多式联运的阶段，作为文中研究的对象，而二次运输较为分散，主要采用公路运输.

图1 整车物流运作模式

因此，文中整车物流多式联运研究的范围主要是指车辆由整车分拨中心配送至整车仓储中心的一次运输阶段.

车辆由VDC配送至VSC，中间需要经过N个中转点，相邻中转点之间有水路、公路、铁路三种运输方式可选，产生不同的运输成本和运输时间.各个中转点若转换其它运输方式，因此，产生一定的换装成本和时间.不同运输方式在运输和换装过程中，可能发生车辆的丢失、损坏等情况，产生不同的风险成本.同时，文中设置一定的时间窗，即完成运输服务要求的时间范围，过早或过晚到达目的地，将产生一定的仓储成本或惩罚成本，因此，在满足时间和运输需求的条件下，实现物流总成本最低，包含运输成本、换装成本、仓储成本或惩罚成本、风险成本，寻找最优的运输方案.

1.2 模型构建

1.2.1模型假设

1) 考虑到城市规模对运输和换装成本的影响，将各城市简化为质点.

2) 每两个相邻节点间只采用一种运输方式，换装必须在节点城市进行.

3) 由于自然因素带来的风险和损失难以计量，运输过程处于理想状态，不考虑自然因素(如大风大雨导致运输延迟等)的影响.

4) 文中不考虑空载返程，完成配送任务后，不必返回出发点.

1.2.2模型建立

根据以上假设，建立整车物流多式联运模型，目标函数为

(1)

简化之后可表示为

约束条件为

(4)

(5)

(6)

(7)

(8)

(9)

(10)

式中：Z为物流总成本，万元；Q(i)为总需求量，万辆；q(i)为节点i需求量，万辆；N为节点城市集合；M为运输方式集合，其中m∈M，m=1，2，3，(1-公路；2-铁路；3-水路) ；vij为实际点到j点的运输量；Vij为i点到j点的路线最大运输量；ckij为在i点用k方式运输到j点的单位运输成本，万元/(100 km·万辆)；ekij为在i点用k方式运输到j点时的风险成本，万元/(100 km·万辆)；rkij为在i点用k方式运输到j点的运输距离，100 km；wkij为在i点用k方式运输到j点的运输时间，h；ukli为在i点将运输方式由k方式换至l方式的换装时间，h/万辆；pkli为在i点将运输方式由k方式换至l方式所产生的换装成本，万元/万辆；okli为在i点将运输方式由k方式换至l方式所产生的风险成本，万元/万辆；F(t)为违反时间要求而产生的惩罚成本，万元；t为将货物从起点运至目的地的总时间，h；[ai，bi]为到达i点的时间窗，h；S1为提前到达，仓储成本；S2为推迟到达，惩罚成本,万元.

式(1)为目标函数，表示物流总成本最低，包括运输成本、换装成本、风险成本、惩罚成本；式(3)为总时间t；式(4)为惩罚成本；式(5)、(6)为变量；式(7)为在i市到j市只能用一种方式运输；式(8)为在i市只能换装一次；式(9)为满足每个节点的运输需求；式(10)为两相邻节点间的运量小于运输能力.

2 遗传算法求解步骤

采用遗传算法对模型进行求解主要进行六个步骤的操作.将节点、运输方式编码，随机选择几组运输方式作为初始种群，计算各运输方式的适应度值，对运输方式进行交叉和变异操作.具体步骤如下：

步骤1编码设计 采用二进制编码，将节点和节点之间的是否采取何种运输方式，以及是否换装编码成染色体，均采用0-1整数规划模型.模型涉及m种运输方式以及n个节点城市，随机编成一条长度为[2(n-2)+1]维的自然数向量，前n-1维向量表示每个节点之间采用何种运输方式，后n-2维表示是否链接.

步骤2种群规模的确定 种群数量为A(偶数)，每次迭代生成A条[2(n-2)+1]维的向量，并从这A条向量中寻找最优解并记录.通过多次的选择、交叉、变异的迭代计算，直至全局最优解产生，采取随机法生成初始种群.

步骤3适应度函数的设计 适应度函数为各方案的总成本Z，适应度较高表示其总成本较低，而适应度较低其总成本较高.

步骤4选择操作 采用轮盘赌选择算子进行选择操作，见图2，每个扇面所对应的圆心角不同，角度越大，表示适应度越高，遗传到下代的可能性越大.模型中路线总成本低的反而适应度大，因此,均将总成本Z取倒数得1/Z，每条路线的适应度p1即为p1=(1/Z1)/sum(1/Z).

图2 轮盘赌选择示意图

步骤5交叉操作 将种群A条向量平均分成上部和下部各A/2条，并将上部第x条向量与下部第x条向量对应配对.交叉操作从第1条向量开始，直至A/2条向量结束.设置一个平均分布的伪随机数rand(0—1)作为依据，若rand小于设置的交叉概率则进入交叉操作.交叉操作分为两部分，即每条向量前n-1维和后n-2维分别与对应的向量交叉操作，交叉的位置在前n-1维和后n-2维中随机选取.

步骤6变异操作 从第1条向量开始，直至A条向量结束.变异操作同样分为两部分，即每条向量前n-1维和后n-2维，变异的位置在前n-1维和后n-2维中随机选取.对于前n-1维变异，变异的值在原值以外的在1～m中再次选取；对于后n-2维变异，由于是0-1规划模型，因此将0变异成1，1变异成0.

最后判断是否达到迭代终止条件，如否，进行群体更新迭代，跳回至步骤3重复进行操作，循环迭代直至输出满足条件的结果.

3 算例分析

M公司以整车物流为主要经营业务之一，具备稳定的水运、铁路、公路运力条件，建立了自己的水路运输路线，自有滚装船13艘和铁路车皮348节，公路可用运力有15 000辆，并积极开展整车物流多式联运.目前在国内共拥有9个VDC，15个较大的VSC.

以M公司长江业务为例，公司沿长江有三个VDC，分别为金桥VDC、安亭总库和仪征VDC，地处仪征和上海，为便于计算，合称上海VDC(a)，有四个VSC，分别处于南京(b)、武汉(c)、重庆(d)、德阳(e).对M公司整车多式联运研究主要是由上海VDC向南京VSC、武汉VSC、重庆VSC、德阳VSC节点配送的过程，各节点有内河水运、铁路和公路三种方式可选.

查询各节点各种方式运输距离，根据各运输方式平均速度计算运输时间(铁路、汽车、内河船舶的平均速度分别为80，100，20 km/h)，见表1.为了方便研究，假设各运输方式在不同城市单位成本、换装成本无差异，根据各运输方式最优路径和距离，以及营运成本、管理成本、燃料成本等，计算可得各方式运输成本，见表2.换装成本主要来源于装卸设备和人力，根据装卸设备的维修费、燃油费、设备折旧成本等以及人工费估算可得换装成本，换装时间由各方式装卸效率测算可得，换装成本和换装时间只与节点前后两种运输方式有关；根据丢失、损坏导致赔偿产生成本估算可得风险成本，见表3.A汽车品牌各个VSC需求量如表4所示，所设的时间窗见表5，若提前到达，设置仓储成本为5万元/(万辆·小时)，若推迟到达，设置惩罚成本为50万元/(万辆·小时).

表1 各节点之间三种方式运输距离、运输时间

注：运输距离单位，100 km；运输时间单位，h.

表2 各种方式运输成本、风险成本 万元·100 km·万辆-1

表3 各种运输方式的换装时间、换装成本

注：换装时间单位，h/万辆；换装成本单位，万元/万辆.

通过Matlab编写程序进行求解，其中遗传算法相关参数设置为：种群规模为30，变异概率为0.04，交叉概率为0.5，最大迭代次数为100，迭代过程见图4，算法在28次循环已收敛，即该问题的最优组合为2，2，3，1，即上海—南京、南京—武汉、武汉—重庆、重庆—德阳各阶段分别采用铁路、铁路、水路、公路运输方式，此时物流总成本最低Z=1 328.727万元，这比纯公路方式物流总成本节约了122.694万元，充分体现三种运输方式的优势，可见该模型和算法优化效果显著.

表4 2015年A汽车品牌VSC所在城市需求量

表5 各节点城市之间的时间窗

图4 迭代过程

4 结 束 语

文中综合考虑物流成本和时效性的要求，将带时间窗的车辆路径和多式联运问题相结合，并运用于整车物流，充分体现各运输方式优势，降低物流总成本.建立物流总成本最低为目标的带时间窗多式联运0-1整数规划模型，包括不同运输方式产生的运输成本、换装成本、运输和换装过程中产生的风险成本，以及提早到达或延迟到达产生的仓储成本或惩罚成本，采用遗传算法进行求解，解决整车物流配送中路径优化问题，并进行实例验证，结果说明此模型和算法在整车物流多式联运中具有可行性和实用性.

[1] 黑秀玲.汽车整车多式联运优化研究[D].南京：东南大学,2015.

[2] 易云飞,董文永,林晓东,等.求解带软时间窗车辆路径问题的改进伊藤算法及其收敛性分析[J].电子学报,2015(4):658-664.

[3] 汪秋云,蒋文保.带软时间窗车辆路径问题的求解算法研究[J].北京信息科技大学学报(自然科学版),2013(4):57-59.

[4] Ekki D K. Distance and time in intermodal goods transport networks in Europe: a generic approach[J]. Transportation Research Part A: Policy and Practice, 2008,42(7):973-993.

[5] CHANG T. Best routes selection in international intermodal networks[J]. Computers & Operations Research, 2008,35(9):2877-2891.

[6] GROMICHO J A S, OUDSHOORN E, POST G. Generating price-effective intermodal routes[J]. Statistica Neerlandica, 2011,65(4):432-445.

[7] 窦莉薇.基于改进蚁群算法的A公司整车物流多式联运路径问题研究[D]. 天津：天津师范大学, 2016.

[8] CHEN P, HUANG H, DONG X. Iterated variable neighborhood descent algorithm for the capacitated vehicle routing problem[J]. Expert Systems with Applications, 2010,37(2):1620-1627.

[9] 储庆中,刘玉兵,吴国君.基于遗传算法求解的危险品道路运输线路优化双层规划模型[J].交通信息与安全,2011(2):95-99.

[10] 王旭,迟增彬,葛显龙.带时间窗的整车多式联运模型研究与解析[J].计算机应用研究,2011(2):563-565.

[11] 徐珏,何利力.基于双层遗传算法的烟草配送路径优化问题研究[J].工业控制计算机,2015(12):33-34.

[12] 吴小珍,李表奎,董紫嫣,等.基于SPFA的整车物流运输线路及运输方式的优化及求解[J].物流工程与管理,2014(5):176-178.

[13] 陈然.上海安吉与同方环球的整车联合运输研究[D].北京：北京交通大学,2012.

Research on Route Optimization Model for Vehicle Multimodal Transport with Time Window

XIEXuemeiYANGJiaqi

(SchoolofTransportation,WuhanUniversityofTechnology,Wuhan430063,China)

Vehicle logistics is a core part of automobile logistics, and how to optimize the costs becomes the focus in logistics and automotive industry. According to the route optimization of vehicle logistics, the 0-1 integer programming model of route optimization of vehicle multimodal transport with the time window was established based on the minimum logistics cost and proper time constraints. Considering transportation cost, transit cost, risk cost, and storage cost or penalty cost without arriving on time, the genetic algorithm was designed to solve this problem based on Matlab. Meanwhile, the model was verified and analyzed by some examples. The results show that the proposed model and algorithm are reasonable and practical for the route optimization of vehicle logistics multimodal transport.

vehicle logistics; multimodal transport; time window; route optimization; genetic algorithm

U116.2

10.3963/j.issn.2095-3844.2017.06.035

2017-09-25

谢雪梅(1991—)：女，硕士生，主要研究领域为物流管理