整车物流运输模型算法的研究

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

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

=0

=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 模型总结

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

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