乘用车物流运输计划问题的研究

张静

摘要：本文针对乘用车物流运输计划问题，基于现有数据与相关研究，采用整数规划、配载优化两种方法，对所需要各种类型轿运车的数量、每辆轿运车的乘用车装载方案建立了数学模型，从而对整车物流的运输成本进行定量分析，降低运输成本。

关键词：整数规划 配载优化 启发式算法 Lingo220 Visual C++

中图分类号：F426文献标识码：A文章编号：1009-5349（2017）20-0021-02

（一）整数规划模型

整数规划是从1958年由RE戈莫里提出割平面法之后形成独立分支的，现已发展出很多方法解决各种问题。解整数规划最典型的做法是逐步生成一个相关的问题，称它是原问题的衍生问题。对于给定Ⅰ车型、Ⅱ车型、Ⅲ车型的数量，求解所需要各种类型轿运车的数量、每辆轿运车的乘用车装载方案，显然可以归结为启发式算法中的整数规划问题。可以应用已有的不同类型轿运车和不同类型乘用车之间的约束条件和目标函数，有效地利用lingo软件进行整数规划模型求取可行解，从而得以获取对所需要各种类型轿运车的数量、每辆轿运车的乘用车装载方案。

（二）基于乘用车和轿运车规格数据的相关分析

装载具体要求如下：每种轿运车上、下层装载区域均可等价看成长方形，各列乘用车均纵向摆放，相邻乘用车之间纵向及横向的安全车距均至少为01米，下层力争装满，上层两列力求对称，以保证轿运车行驶平稳。受层高限制，高度超过17米的乘用车只能装在1-1、1-2型下层。假设运输Ⅰ车型的乘用车156辆、Ⅱ车型的乘用车102辆及Ⅲ车型的乘用车39辆，这里以所有1-1型轿运车和1-2型轿运车的总数量为优化目标如下：

min Z=P1+P2

约束条件为：

（1）由每次1-2型轿运车使用量不超过1-1型轿运车使用量的20%，有P1≤P2；

（2）1-1型和1-2型轿运车装满I、II型乘用车的约束：

471*Z11+3715*Z12+473*Z13≤38*P1；

471*Z21+3715*Z22+473*Z23≤729*P2；

（3）因Ⅰ、Ⅱ、Ⅲ车型的乘用车数量限制，满足关系有： Z11+Z12=156；Z12+Z22=102；Z13+Z23=39；

（4）考虑III型乘用车只能放在轿运车下层的情况，需要满足放在1-1和1-2型轿运车上的所有乘用车的数量不超过III型车放满一层1-1和1-2型轿运车时对应的数量限制为： Z13≤P1；Z23≤5*P2；

符号说明：Pi表示所有1-i型轿运车的数量；Zij表示所有1-i型轿运车搭载的乘用车j的数量。

实验结果：通过Lingo220软件求解，得到如图1数据：

如图1所示，最优解的车辆数是30台，其中1-1型轿运车25台，1-2型轿运车5台。相应分配方案如下：

（三）用Visual Studio C++建立的配载优化模型分析

应用Visual Studio C++软件，提供一个通用的程序，生成exe的文件，对不同车型的轿运车和同一轿运车上不同乘用车的组合形式进行比例划分，提高组合利用率和计算效率。在通用程序中可直接在输入三种乘用车型数量后，迅速得出1-1和1-2所需数量和每种轿运车的搭载组合情况。

面对混装配载订单的情况时，不仅需要考虑单辆轿运车中的商品车的配载优化问题，还需要考虑多辆轿运车配载多辆商品车的优化组合问题。用visual C++语言设计求解线性规划的单纯形法，需要从配载优化理论的最基本原理和基本原则出发，进行专门的底层开发，给出通用算法及程序。

BisChoff&Marriott算法是建立在分层的基础上进行讨论的，运用二维填装技术来解决三维布局问题。该算法的构想是，先按照某种标准确定物体的优先级，然后取出级别高的物体，分别尝试用它的长、宽、高充当层的宽度，一旦层的厚度确定，由于同层的物体尺寸相同，问题就转化为二维填装问题。该算法的特点是要求每一层尽可能由同一类物体组成。如果没有足够的尺寸相同的物体能够把一层装满，就暂且放弃对这种物体的处理，转而处理下一个优先级类别的物体。到最后所有的物體刚好装入集装箱内，但是更多的情况是剩下的每类物体都不能装满一个完全层。在B&M算法的基础上，本文对算法思想又做了如下改进：

（1）因为受层高限制，高度超过17米的乘用车只能装在1-1、1-2型下层，所以III型乘用车只能放在1-1，1-2型轿运车下层中。

（2）考虑相邻乘用车之间纵向及横向的安全车距均至少为01米，可在处理每个乘用车时，假定自身长度都增加01米，则I、II、III型乘用车的长度都变为461米、3715米、463米，所以1-1型和1-2型轿运车装满I、II型乘用车的条件：

461*Z11+3715*Z12+463*Z13≤38*P1；

461*Z21+3715*Z22+463*Z23≤729*P2；

（3）因Ⅰ车型的乘用车P1辆、Ⅱ车型的乘用车P2辆及Ⅲ车型的乘用车P3辆，满足关系如下：

Z11+Z21=P1；Z21+Z22=P2；Z13+Z23=P3；

（4）考虑III型乘用车只能放在轿运车下层的情况，需要满足放在1-1和1-2型轿运车上的所有乘用车的数量不超过III型车放满一层1-1和1-2型轿运车时对应的最多的数量限制，即：

Z13≤5*P1；Z23≤5*P2；

（5）考虑到使用轿运车的数量能尽量少，算法采用先装满I型乘用车，后先装满II型乘用车的原则。

（6）算法中优先考虑Ⅰ型和II型乘用车，最后考虑III型乘用车，即III型乘用车的优先级低一些。endprint

（7）在1-1型轿运车中，因为Ⅰ型乘用車最多放4辆，II型乘用车最多放5辆，所以II型乘用车数量大致是Ⅰ型乘用车数量的，这样分配时可以粗略考虑。

（8）在1-2型轿运车中，按照Ⅰ型乘用车与II型乘用车的比值是1：2，Ⅰ型乘用车与I型乘用车的比值也是1：2来装载乘用车，这样就可以更好地节省空间。

（9）在分配装载乘用车的时候，首先得到次优解，算法会通过优化的过程得到最优解。

（四）设计求解线性规划的优化模型及通用算法

首先对III型车进行分配，1-1型和1-2型尽量按5比1分配，不足5比1安排1-1型，当III型不足一辆车时不分配，再用I型，II型填充上层空位，其中1-2型轿运车，I型，II型尽可能按1比2排放。再对剩余的I型，II型车进行分配，其中1-1型和1-2型也尽量按5比1分配，不足5比1安排1-1型，当不足一辆车时不分配。最后再对剩余的车进行微调。利用Microsoft visual C++软件，给出通用算法，编写exe程序，程序是在dos环境下运行的，具体使用说明如下：

首先打开Testexe，若从文件中读取请输入1，手动输入请输入2。输入2后，会自动弹出“请输入I型车的数量”，输入I型车的数量后，会自动弹出“请输入II型车的数量”，输入II型车的数量后，会自动弹出“请输入III型车的数量”，输入III型车的数量后，会显示各类轿运车各层需要摆放的乘用车的数量。

用Mirosoft visual C++编写的Testexe程序及给出的通用算法，对各类型轿运车的上下两层都给出了详细的装载方案。一方面实现了面向轿运车的最大运能优化研究。利用整数规划算法，通过对规划对象的动态规划变化来优化出每辆轿运车针对不同种类商品车的最大运能配载方案。另一方面，提供了可行Microsoft visual C++算法分析，实现了面向混装订单的配载优化的研究，调整了计算的速度和精度。

运行Testexe，手动输入各类型乘用车数量要求，得到以下显示（如图2）：

对比Lingo220和Microsoft visual C++得到的解，两种分配方案均能达到配送目的要求，但是对比成本而言，考虑1-2型轿运车成本较1-1型成本高，所以Microsoft visual C++得到的解更优一些。之所以Lingo会出现这样的结果，并不是模型本身的漏洞，而是Lingo在求解整数规划的问题上，只会给出一个最优解，而往往问题是会有可能出现多种最优解的情况，却无法显示。又因优化目标并没有考虑到两种车型的成本，所以，Lingo出现的结果还需要进一步分析，这也体现出了Microsoft visual C++模型的优越性。而且，后者可以清晰地列举出每种车型的装配方案，也弥补了整数规划结果细节上的不足。

（五）结论

本文研究的主要结论：

（1）实现了面向轿运车的最大运能优化研究。利用整数规划算法，通过对规划对象的动态规划变化来调整计算的速度和精度，优化出每辆轿运车针对不同种类乘用车的最大运能配载方案。

（2）实现了面向混装订单的配载优化的研究。

（3）提供了所需要各种类型轿运车的数量、每辆轿运车的乘用车装载方案，设计了一个通用算法。考虑多路径的乘用车和轿运车分配比例情况，以分配路程为优先级，乘车利用率高为原则建立了一个一般的优化规划模型，提供了可行Microsoft visual C++算法分析，实现了面向混装订单的配载优化的研究，调整计算的速度和精度，具有一定的实际意义。

参考文献：

[1]蔡菂迪.改进遗传算法在车辆路径问题中的研究应用[D].哈尔滨工程大学，2013.

[2]姚婷.车辆调度遗传算法[D].西北大学，2013.

[3]陈赛虎.基于整数规划的轿车物流配载优化的研究[D].上海交通大学，2008.

[4]陈萍.启发式算法及其在车辆路径问题中的应用[D].北京交通大学，2009.

责任编辑：于蕾endprint