整车物流双层轿运车车辆装载与路径整合优化研究

陈胜波，刘永平，何世伟，黎浩东

(1.深圳市城市交通规划设计研究中心有限公司，广东 深圳 518021；2.北京交通大学交通运输学院，北京 100044)



【交通运输】

整车物流双层轿运车车辆装载与路径整合优化研究

陈胜波1,2，刘永平1，何世伟2，黎浩东2

(1.深圳市城市交通规划设计研究中心有限公司，广东 深圳 518021；2.北京交通大学交通运输学院，北京 100044)

根据启发式算法思想，建立了双层轿运车的车辆配载和路径优化的双层规划模型。在路径优化的求解中融入一定的启发式搜索规则，设计了一种求解该双层规划模型的混合遗传算法，并给出了算法的编码方法、路径搜索方法和适应度函数的定义。案例分析表明，当乘用车种数不超过3种时，采用LINGO商业优化软件能在1 min内求出最优解；超过3种时求解时间呈指数增长。采用本文设计的混合遗传算法，能在较快时间内求出最优解，此模型和算法对编制大规模下的乘用车装载和配送计划具有较强的适用性和可行性。

物流工程；双层轿运车运输； 车辆装载；路径优化；双层规划模型；混合遗传算法

整车物流指的是按照客户订单对整车快速配送的全过程。随着我国汽车工业的高速发展，整车物流量，特别是乘用车的整车物流量迅速增长。汽车整车的装载(vehicle filling problem，VFP)和车辆运行的路径规划(vehicle routing problem，VRP)直接影响着企业的物流效益，一直以来也是业内专家的研究热点。

无论是VFP还是VRP，都已被证明是NP难问题，规模较大时很难求出精确解。井祥鹤等[1]对集装箱的装载问题进行了研究，在基本遗传算法和FFD算法的基础上，提出了一种求解铁路多车型平车的装载问题的混合遗传算法。许光泞等[2-4]分别采用自适应遗传算法、模拟退火算法、混合遗传算法等启发式方法,对集装箱和军用物资的装载问题进行了研究。Ganesh等[5-9]采用了聚类搜索启发式算法、蚁群算法、动态规划方法、禁忌搜索算法、多智能体进化搜索算法等对物流配送中的车辆路径优化问题进行了研究。在两者的综合优化研究方面，张磊等[10-13]对车辆路径及装载的整合优化问题进行了研究，其中文献[10] 仅对单层情景下的整合优化问题进行了研究，并且没有考虑运输车辆规格的影响；文献[11]针对的是多品种货物装载及车辆路径的整合优化研究，并不适用于乘用车的配送问题。

目前关于路径优化、装载或者两者的综合优化问题的研究，绝大多数都是采用启发式算法进行求解。但是单方面的研究较多，两者的综合研究特别是整车物流的车辆装载和路径整合优化的研究较少，多数研究没有考虑到双层轿运车(运送汽车的车辆)对该问题的影响。而在现实生活中，很多物流公司在制定车辆的运输计划时主要依赖调度人员的经验，在面对复杂的运输任务时，往往效率较低，运输成本较大。基于此，本文建立了基于双层规划的整车物流中的车辆装载与路径整合优化模型，并针对大规模问题设计了混合遗传算法进行求解。

1 问题描述

乘用车生产厂家根据全国客户的购车订单，向物流公司下达运输乘用车到全国各地的任务，物流公司则根据下达的任务制定运输计划并配送这批乘用车。为此，物流公司首先要从可以调用的“轿运车”中选择出若干辆轿运车，进而给出其中每一辆轿运车上乘用车的装载方案和目的地，以保证运输任务的完成。“轿运车”是通过公路来运输乘用车整车的专用运输车，根据型号的不同有单层和双层两种类型，由于单层轿运车实际中很少使用，本文仅考虑双层轿运车。双层轿运车又分为三种类型：上下层各装载1列乘用车，记为1-1型(图1)；下、上层分别装载1、2列，记为1-2型(图2)；上、下层各装载2列，记为2-2型(图3)。

图1 1-1型轿运车Fig.1 Car carrier of type 1-1

图2 1-2型轿运车Fig.2 Car carrier of type 1-2

图3 2-2型轿运车Fig.3 Car carrier of type 2-2

在确保完成运输任务的前提下，物流公司追求降低运输成本。但由于轿运车、乘用车有多种规格，当前很多物流公司在制定运输计划时主要依赖调度人员的经验，在面对复杂的运输任务时，往往效率低下而且运输成本不理想。在此种情况下，需要对乘用车的装载以及轿运车的运输路线进行优化，并设计高效的求解算法。

2 模型构建

2.1 上层优化模型

上层优化模型是基于各类型乘用车需求数量，以及能够提供的轿运车数量，在满足相关装载及约束条件下，使轿运车使用总成本最小。该成本是指每辆轿运车的购置及维修等固定使用成本，不包括走行费用的支出成本，假定乘用车数量足够满足需求。

(1)集合及参数定义：I为等待装载的乘用车种类集合；ni(i∈I)为第i类乘用车的需求数量；li为第i类乘用车的长度；wi为第i类乘用车的宽度；hi为第i类乘用车的高度。K为轿用车种类集合；Pk为第k(k∈K)类轿运车的编号集合；ak表示第k(k∈K)类轿运车提供的数量；ck表示第k(k∈K)类轿运车的使用成本。G表示轿运车的层数集合，为了求解方便，根据能够装载的列数将轿运车层数分为4层，即将1-2型的上层看做2层，2-2型的上下层均视为2层进行求解；Lkg表示第k(k∈K)类轿运车第g(g∈G)层的装载面长度；Wkg表示第k(k∈K)类轿运车第g(g∈G)层的装载面宽度；Hkg表示第k(k∈K)类轿运车第g(g∈G)层的装载面高度；Δl表示轿运车的纵向最小间隔；Δw表示轿运车的横向最小间隔。

(3)模型构建

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

2.2 下层优化模型

不同的装载方案对应着不同的最优轿运车走行方案。下层优化模型是在上层优化模型的基础上，即得出车辆的装载方案以后，对轿运车走行线路的优化，使在满足各个乘用车需求的同时，轿运车总走行成本最小。

(1)模型假设：乘用车配送中心只有一个，配送中心拥有运输车辆和仓库，轿运车到达目的地后原地待命，无须放空返回；车辆的最大行驶距离没有限制；每辆轿运车一旦到达乘用车需求地后，与该地需求相应的乘用车全部卸下；卸车成本忽略不计。

(3)模型构建

(13)

(14)

(15)

(16)

(17)

(18)

(19)

(20)

(21)

(22)

3 模型求解

本文设计了相应的混合遗传算法，即采用传统的遗传算法求解上层模型，然后结合现场经验加入一定的启发式搜索规则，求解下层模型得出路径优化方案。

3.1 染色体编码

(23)

3.2 路径优化启发式搜索

在求解下层模型前，首先需要对乘用车需求节点和轿运车相关属性进行定义。

Step 1：采用Dijkstra算法求出任意两点间的最短距离，并记录每个节点n(n∈NS)和其他节点的最短距离。

Step 3：根据所求的轿运车使用情况及装载方案，按照轿运车单位公里的走行成本从高到低排序，单位公里走行成本相同的乘用车随机排序。

Step 7：若k>kmax，或者连续迭代30次，结果不变，程序结束，记录下轿运车总的行驶成本v和对应的路径方案r；否则执行Step 2。

将装载方案j下的最优行驶成本与对应的装载方案j的轿运车固定使用成本求和，带入上层模型循环进行染色体适应度评估，同时将装载方案对应的染色体进行选择、交叉、变异等操作，生成的新一代染色体个体作为一个新的装载方案执行路径优化启发式搜索，不断记录染色体评估适应度最优值；若连续迭代30次或迭代次数超过300次值不变，则跳出循环，记录的最终值则认为是最优的装载方案和最优路径方案。算法流程图见图4所示。

图4 求解算法流程图Fig.4 Solving algorithm flowchart

3.3 适应度函数

上层模型中是考虑每辆轿运车如何装载使得总的轿运车固定使用成本最低，下层模型是最优化每辆轿运车的配送路径，使得总的配送成本最低。由于两者单位相同，并且数量级相差不大。因此将上下层面模型所得目标函数值相加作为适应度函数。

3.4 遗传算子的设计

选择算子设计如下：首先将群体中的个体按照适应度值从大到小的顺序进行排序，然后将排列在前面的个体复制两份，将排列在中间部分的个体复制一份，排列在后面的个体不复制。这样保证了在进化过程中每一代都能使适应度好的个体被选择复制到新的种群中。

为了保证产生新个体的多样性，采用双点逆转交叉的方法，首先对群体进行随机配对，其次按照均匀分布随机产生交叉位置，最后对配对染色体进行交叉操作，产生新个体。

变异操作是对个体的某一个或某一些基因座上的基因进行改变，产生新的个体。在模型中，采用多点动态变异的方法，变异点及其值在每个个体的每次变异中都是随机产生的。

4 案例分析

4.1 相关数据

某物流公司要运输的乘用车的规格及各地需求数量如表1所示，具体路线见图5，其中点O是乘用车供给地，A、B、C、D是乘用车需求地；各段长度：OD=160 km，DC=76 km，DA=200 km，DB=120 km，BE=104 km，AE=60 km。

表1 乘用车规格及各需求地的需求数量

图5 运输线路图Fig.5 Transportation routing map

表2是可调用的轿运车类型(含序号)、数量和装载区域大小。1-1型及2-2型轿运车上、下层装载区域相同；1-2型轿运车上、下层装载区域长度相同，但上层比下层宽0.8 m。此外2-2型轿运车因为层高较低，上、下层均不能装载高度超过1.7 m的乘用车。每辆轿运车能够装载的乘用车数量最小为6，最大为27辆；1-2型轿运车使用数量不能超过1-1型轿运车的20%；1-1型、1-2型以及1-3型轿运车单位公里的走行费用分别为1元、2元、2.5元；乘用车在装载时，横向与纵向最小间隔均不能低于0.1 m，由于是分为4层考虑，因此Δw=0.05，Δl=0.1。

表2 轿运车规格及供给数量

4.2 求解结果及分析

取种群规模为100，交叉概率为0.8，变异概率0.01，最大迭代次数为400次，采用C#编程在CPU频率2.8 GHZ，内存2 G，操作系统Windows XP环境下实现上述混合遗传算法。经过多次测试，最快在第223代得出最优解347.422 8万元。按照以上算法求解出的装载方案如表3所示，1-1型轿运车总的需求数量为10辆，1-2型为12辆，2-2型为1辆。1-2型轿运车使用数量没有超过1-1型轿运车使用数的20%，车辆的使用成本为346万元，其中1-1型轿运车固定使用成本为100万元，1-2型为216万元，2-2型为30万元；每辆轿运车的配送方案如表4所示，需求地的所有乘用车需求均能满足，轿运车总运营成本为14 228元。

表3 装载方案优化结果

注： “/”左右表示同一层的两列摆放方式； “A(B)”中的B表示乘用车编号，A表示乘用车装载数量。

表4 配送方案优化结果

注： “A(B )”中的B表示乘用车编号，A表示乘用车配送数量；表中需求地A、B、C、D下的每一列表示每辆轿运车在该地的配送方案，如表中的第二行第三列“1(1)/1(4)/4(6)”表示编号为1的1-1型轿运车配送给A地1辆编号为1的乘用车，1辆编号为4的乘用车和4辆编号为6的乘用车。

为了验证遗传算法求解上层模型的高效性，针对不同的乘用车车种数量，分别采用了LINGO优化软件和遗传算法进行对比。结果如图6和图7所示，当乘用车车种不超过5种时，LINGO优化软件(图6)在1 min内(最长52 s)都能得出最优解；单一车种求解时，0.1 s即可得出最优解；一旦车种超过3种时，求解时间呈指数增长。当乘用车车种个数超过5种时，在15 min内都难以得出最优解。而采用混合遗传算法时，对本案例的车种个数都进行了验证(图7)，虽然单一车种时求解时间比LINGO时间长，约为13 s，但是随着规模的扩大，求解时间并没有呈现指数增长的形式，而且当车种个数为9种时，最快452 s即可得出最优解，体现了混合遗传算法在求解此类大规模问题时的高效性。

图6 Lingo软件求解Fig.6 Solving results by Lingo software

图7 混合遗传算法求解Fig.7 Solving results by HGA

5 结论

轿运车的装载和配送过程中的路径优化是影响物流企业经营效益的主要问题。本文针对双层轿运车的装载和路径优化问题进行了研究，构建了配装与路径同时优化的双层规划模型。采用遗传算法得出轿运车的配载方案，在此基础上结合人工经验，采用一定的启发式规则对轿运车的行驶路径进行优化，最后通过案例分析，说明了本文设计的双层规划模型及算法对求解大规模整车物流配送问题具有较强的适用性。探索更高效率的求解算法是以后需要进一步研究的问题。

[1]井祥鹤，周献中，徐延勇. 多型号平车装载问题的混合遗传算法[J]. 铁道学报, 2006, 28(6):10-15.

[2]许光泞，肖志勇，俞金寿. 应用自适应遗传算法解决集装箱装载问题[J]. 控制与决策, 2007, 22(11): 1280-1283.

[3] 张德富，彭煜，朱文兴，等. 求解三维装箱问题的混合模拟退火算法[J]. 计算机学报, 2009, 32(11)：2147-2156.

[4] 陈晨, 缪嘉嘉，李爱平，等. 机动车辆装载问题的一种混合遗传算法实现[J]. 计算机应用研究, 2007, 24(9)：34-36.

[5] GANESH K, NARENDRAN T T. CLOVES：A cluster-and-search heuristic to solve the vehicle routing problem with delivery and pick-up[J]. European Journal of Operational Research, 2007, 178(3): 699-717.

[6] REED M, YIANNAKOU A, EVERING R. An ant colony algorithm for the multi-compartment vehicle routing problem[J]. Applied Soft Computing, 2014, 15: 169-176.

[7] NOVOAAB C，STORER R. An approximate dynamic programming approach for the vehicle routing problem with stochastic demands[J]. European Journal of Operational Research, 2009, 196(2): 509-515.

[8] 李建, 张永. 一类集散货物路线问题的禁忌搜索算法设计[J]. 系统工程理论与实践, 2007 (6): 117-123.

[9] 刘欣萌, 何世伟, 陈胜波, 等.带时间窗VRP问题的多智能体进化算法[J]. 交通运输工程学报, 2014, 14(3): 105-110.

[10] 张磊，袁建清，郑磊. 汽车整车配载与运输路线优化方案及算法研究[J]. 计算机技术与发展，2011，21(6):119-222.

[11] 牟欣. 物流配送中的车辆路径与车辆装载整合优化问题研究[D]. 重庆: 重庆大学，2008.

[12] 侯丽晓. 车辆装载和路径安排联合优化问题研究[D]. 大连：大连海事大学，2010.

[13] ZHAO P, PAN W W, YUAN J X. Research for integrated vehicle scheduling and filling problem in logistics systems[EB/OL].[2016-04-05]. http://ascelibrary.org/doi/10.1061/40996%28330%29499.

Research on integrated optimization of double stack car carriers based vehicle loading and routing problems in vehicle logistics

CHEN Sheng-bo1,2, LIU Yong-ping1, HE Shi-wei2, LI Hao-dong2

(1.Shenzhen Urban Transport Planning Center, Shenzhen 518021, China; 2.Traffic and Transportation School of Beijing Jiaotong University, Beijing 100044, China)

∶Based on the heuristic algorithm, a double-decker programming model was established, in which both routing and filling problems of the double stack car carriers were considered. A hybrid genetic algorithm was proposed for solving double-decker programming model and a heuristic search principle was integrated in this algorithm to get the optimized routing. The coding method, routing search method and the dual fitness function were also defined. Finally, the empirical example reveal that when the number of type of cars what to be loaded is less than 3, LINGO software can be used to obtain the optimal solution within 1 minute. However, the solution time may be increased exponentially when the number is 3 or more. Using the hybrid genetic algorithm designed in this paper can get the optimal solution in a short time, which can prove the effectiveness and practicability of this model and algorithm in loading and distribution planning of passenger cars on large scales.

∶logistics engineering; double stack car transportation；vehicle filling; routing optimization; double-decker programming model; hybrid genetic algorithm

10.3976/j.issn.1002-4026.2017.03.013

2016-09-03

陈胜波(1990—)，男，工程师，硕士，研究方向为运输组织现代化。E-mail: chensb@sutpc.com

U492.2

A

1002-4026(2017)03-0073-09