基于乘用车物流运输模型程序算法的分析

李 鹏，窦霁虹，仲文林，卢克英

(西北大学数学学院，陕西西安710127)

基于乘用车物流运输模型程序算法的分析

李 鹏，窦霁虹，仲文林，卢克英

(西北大学数学学院，陕西西安710127)

基于第十一届“华为杯”全国研究生数学建模竞赛E题，针对一类乘用车物流运输问题，首先建立了单目的地乘用车运输优化模型；其次通过在遗传算法中构造新的适应度函数对模型求解，得到较优的运载方案。该程序算法对直接利用软件或Java Web技术解决一般的乘用车物流运输计划问题提供了新的算法思想。

乘用车物流运输；遗传算法；适应度函数；程序算法

随着我国乘用车的整车物流量迅速增长，制定一个最佳的乘用车物流运输计划直接关系到物流公司的经济收益和发展状况。但由于轿运车、乘用车有多种规格等原因，当前很多物流公司在制定运输计划时主要依赖调度人员的经验，面对复杂的运输任务时，往往效率低下，而且运输成本不尽理想。因此，建立一个合理的乘用车物流运输计划的数学模型变得至关重要，然后将模型中蕴含的数学思想转化为程序算法，从而将数学问题转化为计算机程序问题，极大地提高了应用计算机解决实际问题的能力。因此，针对数学模型建立和算法分析的研究是很有价值的[1]。

图1 1-1型轿运车

图2 1-2轿运车

本文只针对文献[1]中的前3问建立通用模型，在模型求解方面给出程序算法分析。为简化分析，故作如下假设：

1)相邻乘用车距离纵向和横向距离按0.1 m计算；

2)装载时，假设每辆乘用车的车身不能超出轿运车的边缘线；

3)假设轿运车到达目的地后原地待命，无需放空返回；

4)轿运车足够多，满足所有运输任务；

5)“装满”是指在满足要求的情况下，不能再装入任何类型的乘用车；

6)乘用车的重量对于运输成本的影响忽略；

通过分析可得，该实际问题为双目标的最优化模型[2]。

1 模型的建立

ni表示1-t型轿运车的数量；m1表示Ⅰ型乘用车的数量，m2表示Ⅱ型乘用车的数量，m3表示Ⅲ型乘用车的数量；xij(k)(s.t)表示第s型的第i辆乘用车装在第t型的第j辆轿运车的第k层；其中，xij(1)(s.t)表示第s型的第i辆乘用车装在第t型的第j辆轿运车的上层，xij(2)(s,t)表示第s型的第i辆乘用车装在第t型的第j辆轿运车的下层，s=1，2，3；k=1，2；t=1，2；i=1，2，…，ms；j=1，2，…，nt。具体符号说明如表1。

表1 有关轿运车-乘用车符号标记

由表1可以清楚得看出：任意一辆乘用车在物流运输中的具体装载方式，因此这样的标记方式具有一定的科学性。

经分析，该实际问题属于双目标规划问题[2]。接下来根据题意并结合实际，深度挖掘数据信息，在模型建立之前确定目标函数和决策变量、寻找约束条件。

(1)目标函数

在确保完成运输任务的前提下，物流公司追求降低运输成本，影响成本高低的首先是轿运车使用数量；其次，在轿运车使用数量相同情况下，1-1型轿运车的使用成本较低，2-2型较高，1-2型略低于前两者的平均值，用P1表示1-1型轿运车的使用成本，用P2表示1-2型轿运车的使用成本，则P1

本问题为总成本尽可能低和轿运车的数量尽可能小的双目标规划问题，目标函数如下：

(2)决策变量

根据以上的分析，nt和xi(k)(s,t)为决策变量(t=1,2)，其中

(3)约束条件

1-1型与1-2型两种轿运车数量关系的约束：

为方便后续任务安排，每次1-2型轿运车使用量不超过1-1型轿运车使用量的20%，所有的1-1型车的数量为n1，所有的1-2型车的数量为n2，则有：

20%n1≥n2

(1)

Ⅲ型乘用车的约束：

受层高限制，高度超过1.7 m的乘用车只能装在1-1、1-2型下层，因此在实际装载中，Ⅲ型乘用车只能装在1-1、1-2型轿运车的下层，不能装载在1-1、1-2型轿运车的上层，即

xij(1)(3,t)=0 (t=1,2)

(2)

轿运车车长的约束：

每一辆轿运车上装载的所有乘用车的纵向摆放，相邻乘用车之间纵向及横向的安全车距均至少为0.1m。1-2的上层只能装载运输Ⅰ、Ⅱ型乘用车，1-2的上层，本题只考虑纵向距离。对1-1型轿运车而言，上下两层均单列装载，轿运车每层上装载的所有乘用车的纵向距离加上各个相邻乘用车的0.1 m，应该小于该轿运车的车长，因此有：

(k=1，2；j=1，2，…，n1)

(3)

对1-2型轿运车而言，下层单列装载，同上有：

(j=1,2,…n2)

(4)

由于1-2型轿运车的上层装载2列乘用车，该层上装载的所有乘用车的纵向距离加上各个相邻乘用车的0.1 m，应该小于该轿运车的车长的两倍，则：

(j=1,2,…,n2)

(5)

轿运车最大数量约束：

每辆轿运车可以装载乘用车的最大数量在6到27辆之间，则：

t=1,2

(6)

下层尽量装满的约束：

题目要求“下层力争装满”，我们理解的“装满”是在满足要求的情况下，不能再装入任何类型的乘用车，即最后所剩的长度比Ⅰ型、Ⅱ型、Ⅲ型三者车上的最小值ε还小就装满了，其中

ε=min(4.61，3.615，4.63)+0.1=3.715

那么就得到下面关系式：

(7)

上层两列力求对称的约束：

根据直观性分析：1-2型轿运车的上层可以装载两列乘用车，为了保证轿运车行驶平稳，上层两列装载时力求对称。当1-2的上层所装的同一类型的乘用车数量为偶数时，显然能够保证轿运车行驶平稳，即

s=1,2,3；j=1,2,…,n2

(8)

以上是根据题意和对数据信息深度挖掘后得到：决策变量与目标函数间的约束关系，在数学建模过程中，这部分工作属于难点部分。

综上，建立单目的地的乘用车运输模型：

2 遗传算法及适应度函数的构造

模型的求解我们选择遗传算法[3]来寻找可行解，遗传算法(Genetic Algorithm)是一种通过模拟自然进化过程搜索最优解的方法，其中选择、交叉和变异构成了遗传算法的遗传操作，遗传算法在解决优化问题时，最主要的特征是：不在单点上寻优，而是从整个种群中选择生命力强的个体产生新的种群，应用随机转换原理时，遗传算法得到结果好坏，主要依赖于遗传代数和解组规模。在实际中，可根据具体要求，在合理的时间内对问题求解，如果得到的解不满足要求，则可以增加遗传代数或是解组规模，有望得到问题的全局最优解，当然这是以延长计算时间为代价的。基本遗传算法的流程图如图3所示：

图3 遗传算法的流程图

从实际的整车物流运输出发，并由简单到复杂逐步考虑，层层深入，如此会为解决乘用车物流运输计划问题提供宝贵的模型思想和简单算法。因此需要通过直观性分析计算出1-1和1-2型轿运车的所有满载方案，具体方案如表2和表3。

表2 1-1型轿运车装载方案

表3 1-2型轿运车装载方案

为了清晰地表达，做符号说明：(pi(k),qi(k),ri(k))表示轿运车的第k层上装有pi(k)辆Ⅰ型乘用车、qi(k)辆Ⅱ型乘用车、ri(k)辆Ⅲ型乘用车这类方案，∂i表示第i种方案；At为t型轿运车的车长(t=1，2分别表示1-1型和1-2型轿运车)。为了更好地体现装载剩余的空间，定义第i个装载方案的“装载效率”为：

其中ri为第i个运载方案中剩余的空间。将遗传算法及其思想应用到乘车物流运输模型中，具体步骤如下[4]：

第一步：随机产生初始种群，即从所有可能的装载运输方案中随机m种1-1型轿运车的装载方案、n种1-2型轿运车的装载方案，如下表：

第二步：确定收敛准则

要完成所有的装载运输任务，装载的i型乘用车的总量不少于需要装载的i型乘用车的数量Ni，i=1，2，3，定义“剔除函数”g1、g2、g3：

第三步：适应函数的构造

为了剔除在约束条件下“明显”不是最优的装载方案，建立适应函数：

这样便能逐步迭代，剔除“明显”不是最优的装载方案，最后找出最优解或次优解。

3 模型结果

应用以上算法思想并采用Java-web技术对模型求解。

表4 模型结果

注：模型结果不唯一，原因是采用遗传算法时，初值点的选取是由计算机自动随机生成，具有任意性，但是模型的结果都符合实际，真实有效，可供物流公司参考，从而采取最佳运输方案。

根据模型思想和遗传算法的程序算法思想，将数学问题转化为计算机程序问题，极大地提高了应用计算机解决实际问题的能力。

该实际问题必须借助计算机程序来执行，程序有许多，如C语言、C++、Java-web和MATLAB等。但是多个计算机程序共同的算法是相同的，因此本文的核心工作是提供算法思想和算法分析。

[1]http：//www.madio.net/thread-223965-1-1.html.

[2]董文永，刘进，丁建立，等.最优化技术与数学建模[M].北京：清华大学出版社，2010.

[3]张磊.汽车整车配载与路线优化方案及算法研究[J].计算机技术与发展，2011，2(6)：199-222.

[4]王占锋.求解非满载车辆调度问题的改进遗传算法[J].计算机工程与设计，2008，2(15)：3991-3996.

[责任编辑 毕 伟]

Based on Analysis of Passenger Transport Modeling Program Algorithm

LI PENG,DOU Ji-hong,ZHONG Wen-lin,LU Ke-ying

(School of Mathematics,Northwest University,Xi′an 710127,China)

Based on the E question of the eleventh Graduate Mathematical Modeling,which is related to a class of passenger transport and logistics problems.Firstly,a single destination for passenger transport optimization model is established; secondly a new fitness function of genetic algorithms is constructed when solving the model.This algorithm provides new algorithms ideas for the direct use of the software program or Java web technology to solve the general problem of passenger transport and logistics plan.

passenger transport logistics; genetic algorithms; fitness function; program algorithm

2014-12-19

陕西省教育厅自然科学专项基金(CU0631206030001)

李 鹏(1988-)，男，山西忻州人，西北大学在读硕士研究生。

O232

A

1004-602X(2015)02-0059-04