公路行业核心期刊整车物流运输模型算法的研究

　　摘要：针对乘用车物流运输计划问题，本文建立了基于三维装箱问题的最优化装箱问题模型，提出了基于两阶段线性规划的处理算法。利用此算法，可在定义目标函数和约束的基础上，以较小的时间开销完成搜索空间的搜索，以得到最优化结果。在路径规划问题上，本文将路径规划问题简化为三角形路径规划问题，大幅减小了复杂度。最后，将两种算法相结合，可解决一般性的物流规划问题，并得到较优结果。

　　关键词：公路行业核心期刊,物流运输,组合优化,路径优化,线性规划,启发式算法

　　整车物流指的是按照客户订单对整车快速配送的全过程。随着我国汽车规模的扩大发展，乘用车的整车物流成为了当前面临的主要问题之一。

　　1 通用模型

　　1.1 两阶段线性规划模型

　　1.1.1 模型定义

　　本文中假设所有轿运车都是双层;轿运车到达目的地后不得返回;轿运车在运输过程中可中途卸载部分乘用车;卸车成本忽略不计，总成本仅与派遣的轿运车数量和行程有关。

　　在满足假设前提的情况下，定义轿运车集合П=<П1，…，Пp>与待运乘用车集合Θ=<Θ1，…，Θi>，有任意轿运车类型Пi=<πi，WiD，LiD，HiD，WiU，LiU，HiU>和待运乘用车类型Θ=<θi，wi，li，hi>。其中，πi为轿运车的数量，WiD，LiD，HiD，WiU，LiU，HiU分别为轿运车上下两层的宽、长和高;θi为待运乘用车的数量，wi，li，hi分别为待运乘用车的宽、长和高。则乘用车物流运输计划问题可描述为：在满足Constraint(1)的情况下，对于轿运车和待运乘用车集合П和Θ，求出Xmin，使得Cost(Xmin)=mini(Cost(Xi))。

　　在假设前提下，对于任意轿运车Пi，可将其视为ПiD=<πi，WiD，LiD，HiD>(下层)与ПiU=<πi，WiU，LiU，HiU>(上层)。

　　(1)

　　1.1.2 两阶段线性规划

　　定义1 切分模式：给定宽为W，长为L的长方形X=，以及一系列的小的长方形Y=，Yi=，1≤i≤n。需要将X切分为宽为且长为L的条(长方形)。一种切分模式λiX可定义如公式(2)：

　　λiX=T，Σjbj*wj≤W (2)

　　其中，是在切分模式λiX下，能切分出的宽为长为L的长方形个数。记可能切分模式的总数为γX。

　　定义2 两阶段线性规划：给定Пp∈П和Θ，两阶段线性规划问题分为两个阶段。

　　(1)将规格为Wi*Li的长方形切分为wj*Li，θj∈Θ的“条”，Σwj≤Wi。

　　(2)给定规格wj*Li的条，将其切分为最终规格为wk*lk的块，wk≤wj且Σlk≤Li。

　　0 0 2 1 2 0 1 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0

　　W0=3.5 L0=24.3 λ10λ20λ30λ40 λ11 λ12λ22λ32λ42λ52 λ13λ23λ33λ43λ53λ63λ73λ83λ93λ103λ113λ123λ133λ143λ153

　　(wi，li)=(1.605，3.615)

　　(1.7，4.61)

　　(1.785，4.63) 2 1 1

　　1 2

　　1 -1

　　-1 -1 -1 -1 -1

　　-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 =0

　　(wi，li)=(1.605，3.615)

　　(1.7，4.61)

　　(1.785，4.63) 6 5 4 2 1

　　1 2 3 4 5 5 4 2 1 4 2 2 1 1 1

　　4 3 2 1 1 2 1 3 2 1

　　1 2 3 4 1 2 3 4 1 1 2 1 2 3 5 ≥20

　　≥8

　　≥6

　　图1 示例-两阶段划分

　　假设只有一种规格的轿运车П0=<π0，3.5，24.3>，三种待运乘用车Θ1=<20，1.605，3.615>，Θ2=<8，1.7，4.61>和Θ3=<6，1.785，4.63>，则。两阶段可描述为：第一步：将条形3.5?24.3编号为0。该条形能够以γ0=4种方式，切分成包含宽分别为<1.605，1.7，1.785>，长为24.3的条。如图1，在切分模式λ30中，可得到<1.605，1.7，1.785>，长为24.3的条各<1，0，1>块。第二步：给定规格为1.785?24.3的条，给定切分模式λ83，可切分出规格为<1.605，3.615>，<1.7，4.61>，<1.785，4.63>的块各<0，1，4>块。

　　1.1.3 通用模型

　　通用模型FS首先，建立通用模型FS。记Пi∈П的规格W*L，Θ=<Θ1，…，Θm>中有种不同的宽，分别为。则在规划过程中，总共有种规格的条形，它们的规格分别为W*L，。按顺序将这些规格编号为。

　　定义3 Ai定义Ai=[λ1i…λγii]。λji是针对规格编号i的形状，能进行的第j种切分方式。记Ai的行数和列数分别为ri，ci，则有：当或i≠0，ri=m时，ci=γi。

　　定义4 ，其中表示的是对应第j种切分方法需重复的次数。

　　定义5 Ni=[n1i…nmi]T，其中nji表示对应切分方法j能产生史小块的数量。　　根据上述定义，给定规格编号为i的长方形，其能分割出的长方形数量可通过公式求出。实际上，第一阶段问题是是针对W*L的线性规划问题，第二阶段是针对第一阶段wi*L的线性规划问题，将两者结合，可得到以下条件： ; 。其中是指，第一阶段的产出需要等于第二阶段的消耗。

　　至此，可以得适用于单一规格的单层轿运车的通用形式FS，通用模型FM可对适用单一规格的通用形式进行修改，以形成适用于多规格的单层轿运车构造通用形式。考虑到有q种不同的单层轿运车，对于每一种轿运车1≤i≤q，都有对应的Ai，则适用于多规格的单层轿运车的线性方程应满足以下基本形式：AX≥N′;A=diag[A1，…，Aq];N′=[0 n11 n21 … nm1 … 0 n1p … nmp]T。

　　在建立好通用形式FS或FM之后，则可对其进行求解，得出最优解X*以及相应能够运送的各型乘用车数量N*。对于求得的N*，。

　　1.2 基于蚁群算法的路径优化模型

　　将一般运输路径问题简化为图2所示。在满足假设前提的条件下，乘用车路径规划问题可描述为：对于给定轿运车集合П和待轿运车集合Σ=<ΣA，ΣB，ΣC，ΣD，ΣE>，需要在指定的约束条件Constraint的情况下，使得轿运车集合Σ运送到目的地。

　　图2 一般路径规划问题的路径图

　　因此，定义满足Constraint的解决方案为元组S=，其中Sk=(si为需要使用Пi型轿运车的数量)为运送到k地的指派方案。同时，该解决方案对应成本Cost(S)=(式中Counts为该指派方案需要的轿运车的总数，Lengths为该方案行驶的总里程);成本之间的比较关系由式(3)定义：

　　(3)

　　则乘用车路径规划问题可描述为：对于给定轿运车集合П和待轿运车集合Σ，在满足Constraint的基础上，求出Smin，使得Cost(Smin)=min(Cost(S))。

　　1.2.1 基本模型及建模

　　根据图2，为使运输的轿运车数量以及型号最优(数量最少，轿运车使用成本最低)，可采取由远到近的分配策略，从而缩减较近节点的轿运车需求。利用此策略，对原有路径图的简化为图3。如图4，利用上文所提到的两阶段线性规划模型，可计算在E、A两地的需求合并后，轿运车的最优指派方案，以及每辆轿运车的装配方案。

　　图3 简化后路径图

　　图4 E、A两地的运输规划问题

　　根据图4，可把B地作为始发站。对E、A两地的运输规划问题可转化为标签问题。可定义标签A为0，E为1，解定义为Spath=。路径优化的问题优化模型约束为： ; ; 。

　　1.2.2 蚁群算法流程

　　初始状态：上述问题模型可转化为分层选择模型。初始状态，将m只蚂蚁随机放入第一层的0节点或1节点，随机从下层中选择一个标签来前进;t时刻在节点i和下层节点j之间的残留信息量用τij(t)表示;在初始时残留信息量相同，设τij(0)=c。

　　转移概率：蚂蚁k(k=1，…，m)在运动过程中，由各条路径上残留的信息量决定其运动方向。蚂蚁k在t时刻从节点i运动到下一层的节点j的概率用pkij(t)来表示，如式(4)：

　　(4)

　　其中，α为残留信息量的信息素启发因子;β为期望值的启发因子;ηij为启发值。

　　信息素更新：经过n个时间段，所有蚂蚁都完成对每个标签的选择，将最新的蚂蚁访问过的路径留下的新信息加入到τij(t)中。信息素根据以下公式进行更新：

　　τij(t+1)=(1-p)τij(t)+Δτij; (5)

　　; (6)

　　其中，1*代表第k只蚂蚁通过Pathij;2*代表第k个解决方案满足约束。式中，p表示信息素挥发因子，取[0.5，0.9];Δτkij表示第k只蚂蚁在此次循环中在ij路径上的信息素增量，若该蚂蚁访问了该路径，则增量为正数，否则为0;在计算增量上，Q为正常数，Fk为第k只蚂蚁的路径所产生的解的适应度;在计算适应度时，若第k只蚂蚁的标签方案符合所有的约束，则适应度为正值，否则为0;fmax，fmin分别为当前蚁群中产生的最优解和最差解的适应度函数值。

　　2 模型总结

　　针对多规格轿运车装配问题和多地点路径规划问题，本文分别提出了对应的数学模型：两阶段线性规划模型与基于蚁群算法的路径优化模型，并给出了相应算法流程。模型最后可输出对多规格轿运车的最优装配方案，以满足单一目标地的乘用车需求。

　　对于路径优化问题，本文给出基于蚁群算法的优化模型，利用启发式算法正反馈的机制，以较少时间实现对复杂解空间最优解的逼近。

　　参考文献：

　　[1]P.C.Gilmore，R.E.Gomory，Multistage cutting stock problems of two and more dimensions，Operations Research[J]，Vol.13，No.1，Jan.-Feb.，Page 94 of 94-120，1965.

　　[2]Eugene J.Zak，Row and column generation technique for a multistage cutting stock problem，Computers & Operations Research[J]，Vol.29，No.9.(2002)，pp.1143-1156.

　　[3]吴宗彦，王景华，张建军，基于蚁群算法的智能运输调度问题的研究[J].计算机工程与应用，2006(35).

　　[4]张志霞，邵必林.基于改进蚁群算法的运输调度规划[J].公路交通科技，2008(04).

　　[5]杨菊花，朱昌锋，田志强.基于蚁群算法的应急物资运输路径优化[J].铁道科学与工程学报，2012(06).

　　[6]欧邦才.基于线性规划的物流运输方案探讨[J].黑龙江水利科技，2009(06).

　　[7]彭月.基于线性规划的运输模型[J].科技致富向导，2014(08).

　　[8]吴雪琴.线性规划在物流运输中数学模型的建立及应用[J].江西电力职业技术学院学报，2007(01).

　　作者简介：潘杭一，女，满族，黑龙江齐齐哈尔人，工学学士，软件工程专业硕士在读，研究方向：信息安全。

　　作者单位：同济大学软件学院，上海 201804