摘 要：针对乘用车物流运输计划问题，本文建立了基于三维装箱问题的最优化装箱问题模型，提出了基于两阶段线性规划的处理算法。利用此算法，可在定义目标函数和约束的基础上，以较小的时间开销完成搜索空间的搜索，以得到最优化结果。在路径规划问题上，本文将路径规划问题简化为三角形路径规划问题，大幅减小了复杂度。最后，将两种算法相结合，可解决一般性的物流规划问题，并得到较优结果。
关键词：物流运输；组合优化；路径优化；线性规划；启发式算法
中图分类号：TP391
整车物流指的是按照客户订单对整车快速配送的全过程。随着我国汽车规模的扩大发展，乘用车的整车物流成为了当前面临的主要问题之一。
1 通用模型
1.1 两阶段线性规划模型
1.1.1 模型定义
本文中假设所有轿运车都是双层；轿运车到达目的地后不得返回；轿运车在运输过程中可中途卸载部分乘用车；卸车成本忽略不计，总成本仅与派遣的轿运车数量和行程有关。
在满足假设前提的情况下，定义轿运车集合П=与待运乘用车集合Θ=，有任意轿运车类型Пi=和待运乘用车类型Θ=。其中，πi为轿运车的数量，WiD，LiD，HiD，WiU，LiU，HiU分别为轿运车上下两层的宽、长和高；θi为待运乘用车的数量，wi，li，hi分别为待运乘用车的宽、长和高。则乘用车物流运输计划问题可描述为：在满足Constraint（1）的情况下，对于轿运车和待运乘用车集合П和Θ，求出Xmin，使得Cost（Xmin）=mini（Cost（Xi））。
在假设前提下，对于任意轿运车Пi，可将其视为ПiD=（下层）与ПiU=（上层）。
（1）
λ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。
（wi，li）=（1.605，3.615）
（1.7，4.61）
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）
≥8
≥6
图1 示例-两阶段划分
1.1.3 通用模型
通用模型FS首先，建立通用模型FS。记Пi∈П的规格W*L，Θ=中有 种不同的宽，分别为 。则在规划过程中，总共有 种规格的条形，它们的规格分别为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之后，则可对其进行求解，得出最优解X*以及相应能够运送的各型乘用车数量N*。对于求得的N*， 。
将一般运输路径问题简化为图2所示。在满足假设前提的条件下，乘用车路径规划问题可描述为：对于给定轿运车集合П和待轿运车集合Σ=，需要在指定的约束条件Constraint的情况下，使得轿运车集合Σ运送到目的地。
图2 一般路径规划问题的路径图
因此，定义满足Constraint的解决方案为元组S=，其中Sk=（si为需要使用Пi型轿运车的数量）为运送到k地的指派方案。同时，该解决方案对应成本Cost（S）=（式中Counts为该指派方案需要的轿运车的总数，Lengths为该方案行驶的总里程）；成本之间的比较关系由式（3）定义：
（3）
则乘用车路径规划问题可描述为：对于给定轿运车集合П和待轿运车集合Σ，在满足Constraint的基础上，求出Smin，使得Cost（Smin）=min（Cost（S））。
根据图2，为使运输的轿运车数量以及型号最优（数量最少，轿运车使用成本最低），可采取由远到近的分配策略，从而缩减较近节点的轿运车需求。利用此策略，对原有路径图的简化为图3。如图4，利用上文所提到的两阶段线性规划模型，可计算在E、A两地的需求合并后，轿运车的最优指派方案，以及每辆轿运车的装配方案。
图3 简化后路径图
图4 E、A两地的运输规划问题
根据图4，可把B地作为始发站。对E、A两地的运输规划问题可转化为标签问题。可定义标签A为0，E为1，解定义为Spath=。路径优化的问题优化模型约束为： ； ； 。
初始状态：上述问题模型可转化为分层选择模型。初始状态，将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）
2 模型总结
针对多规格轿运车装配问题和多地点路径规划问题，本文分别提出了对应的数学模型：两阶段线性规划模型与基于蚁群算法的路径优化模型，并给出了相应算法流程。模型最后可输出对多规格轿运车的最优装配方案，以满足单一目标地的乘用车需求。
对于路径优化问题，本文给出基于蚁群算法的优化模型，利用启发式算法正反馈的机制，以较少时间实现对复杂解空间最优解的逼近。
参考文献：
[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）.
