数学建模竞赛优秀选2014年

（由填写赛赛题目乘用车物流计划问 要 过程中存在的效率低和成本不理想等诸多问题， 运车上乘用车的装载方案和目的地，充分利用轿运车的最大运能，以保证任输路线，有效的降低成本且提高效率。针对问题一要I型乘用车100辆及II型乘用车68辆到同一目的地，由III1-11-2型轿运车的上层和下层，求解过程中只乘用车分配方案：21-2型轿运车和161-1型轿运车。针对问题二要II型乘用车72辆及III型乘用车52辆到同一目的地，考III1.7m1-11-2IIIII型乘用车进行配载。确定出最少的轿运车数量，最优的乘用车分配方案：11-2型轿运车和12辆1-1型轿运车。针对问题三物流公司要Ⅰ车型的乘用车156辆、Ⅱ车型的乘用车102辆Ⅲ39辆到达同一个目的地，结合前两问，要使得轿运车的运能最大化，节省成本，则每辆轿运车应尽可能的装满，空间利用率高，确定出完成任务所需的最少轿运车数量以及最优的乘用车分配方案:5辆1-2型251-1得出的最优方案为：4辆1-2型、21辆1-1型轿运车，过程中共卸货3辆，D11-1B21-1114辆。确定最少车问题重据统计数据显示：2012年，我国汽车销量已达到1364万辆，第一次日按现在的发展速度，今年我国的汽车产量就可望达到1800万辆，占世界市场的厂家根据客户的购车订单，向物流公司下达乘用车到各地的任务，由于单层轿运车实际中很少使用,本题仅考虑双层轿运车[2]。图1-1、1-2、1-3就是乘用车整车物流实施过程中的画面。双层轿运车又分为三型：上下层各11-1型（11、21-223用车的最大数量在627辆之间。 经验，在面对复杂的任务时，往往效率低下，而且 问题二：物流公司要Ⅱ车型的乘用车72辆及Ⅲ车型的乘用车52辆问题四：物流公司要166辆Ⅰ车型的乘用车（其中目的地是A、B、C、D 、、、辆）和78辆Ⅱ车型的乘用车（其中目的地是A、C的，分别为31、47辆），具体路线见图1-4，各段长度：OD=160，DC=76，DA=200，2给出可以调用的轿运车类型（2-21.7米的乘用图1- 1-1型轿运 图1- 1-2型型轿运图1-32-2型轿运 图1-4路径模型假符号说III车型的乘用车装在轿运车1-1上层的数III车型的乘用车装在轿运车1-2下层的数问题分针对问题一要I型乘用车100辆及II型乘用车68辆到同一目的地，由III1-11-2型轿运车的上层和下层，求解过程中只针对问题二要II型乘用车72辆及III型乘用车52辆到同一目的地，考III1.7m1-11-2IIIII型乘用车进行针对问题三物流公司要Ⅰ车型的乘用车156辆、Ⅱ车型的乘用车102辆4-1问题一、二、三解题思路流程模型的建立与求5.1乘用型长(米宽(米高(米ⅠⅡⅢ5.2轿运车类上下层长度(米上层宽度(米下层宽度(米1-1-每辆轿运车的乘用车装载方案与乘用车的类型有关，假设a1I车型的乘用1-2下层的数量，他们之间的关系满足如下： 4.61a13.615b190.1*(a 4.61a3.615b24.30.1*(ab b a2b2其中a1b1a2,b2为正整数。max4.61a1 4.61a 65II型车分布数量4II型车分布数量3210 I型车分布数量

5-1I、II5.4、5.55.65.31-1051322314005132231405.51-2I型II型0248648200615243241505.35.45.55.61-11-2的上下层的乘用车配载情况，表中轿运车上下层每一种可能出现的装配组合依次用x1，x2，…，x15，x16A1A2A3A4为对应的表中的组合 x

xx

x

(5-3 xixi 5.75-21 36 7 0 1--2 针对问题二，物流公司要Ⅱ车型的乘用车72辆及Ⅲ车型的乘用车52IIIII型车进行整车物流。每辆轿运车的乘用车装载方案与乘用车的类型有关，假设a1II车型的乘 3.615a4.63b190.1*(ab1)3.615a4.63b24.30.1*( ab a2b2ab 其中a1,b1a2,b2为正整数。max3.615a13.615a2

(5-65III型车分III型车分布数3210 II型车分布数5-3IIIII505.91-1的下层装载乘用车的I型车的量II型车数04132231505.101-2的上层装载乘用车的情I量数05.11轿运1-2的下层装载乘用车的情I量II型车的量051423425160 A1*xiA2(i,1)*xi1A3*x7A4(i,1)*xi8 A1*xiA2(i,2)*xi1A3*x7A4(i,2)*xi8 0.2*(xxxxx)(xxxxxx) xi xi xixi 5-4131-15.12辆上下各类车型装1-1 1-2112[4]问题三中提出物流公司要的乘用车中Ⅰ、Ⅱ、Ⅲ型都有。针对该问题，Ⅱ、Ⅲ型a1、b1、c1辆。1-2车下层分别装有Ⅰ、Ⅱ、Ⅲ型车a2、b2、c2辆。为max 4.61amax 4.61a3.615b 由约束条件可以等到以下方4.61a13.615b14.63c119(a1b1c11)4.61a3.615b4.63c24.3(abc1) bc

2 2 abc3,2 2其中a、、、、、为正整数 乘用车的分布情III型车III型车的分布数量5 0 42I型车的分布数 II型车的分布数5-5乘用车的装载分布现考虑对1-1、1-21-1、1-2轿运车上层只能放置Ⅰ、1-215.13（1-1型车上层情况I型车的数量II型车的数量III型车的量0501302203104005.14：（1-1型车下层情况I型车的数量II型车的数量III量0040130220310501031121211302022112203013104005.15（1-2上层情况III型车的数量III型车的数量0020480640820005.16（1-2下层情况III型车的数量III型车的数量005014023042051060104113122141150203212221240302311320401410500其目标函数及约束条件方程如5-9所示：min=x1+x2+x3+x4+x5+x21+x22+x23+x24+x24+x24+x25+x260.2*(x+x+x+x+x)-(x+x+x+x+x+x+x+x)0 A1(i,1)*xiA2(i,1)*xi5A3(i,1)*xi20A4(i,1)*xi26 iA1(i,2)*xiA2(i,2)*xi5A3(i,2)*xi

A4(i,2)*

A2(i,3)*

A3(i,3)* A1(i,3)*x

i1A4(i,3)*xi26x

xi

xixi[6, xi[6,其中x—x 5-65.17轿运总辆上下层分配II型车个III个1-2轿车 1-2轿运车共2 辆1-2轿车3 1-1轿运车共1-1轿运4 00 辆1-1轿运7400004001-1轿运40001031-1轿运140000041-1轿运340000505-71-4中，从OA、B、C、D各目的地的线路权重最小，用最短路径算法分析得出，在满足II型车完全装载的情况下，要使去A地的车尽可能的少，去C地的车尽可能的多，得出的方案是最省的[5]。具体分析如下：I、II型乘用车求解出要完成任务的最少轿运车的车辆数[3]。求解的步骤同问题一，最终得出需要1-1型轿运车211-2型轿运车4辆可完成任务。2、从OA条件知II型车只送往A、C两地，而I型车A、B、C、D都有任务，故在 xxxxxx x x (5-

i11运车的数量和乘用车的装载方案，结果如表5.18所示。5.18轿运车数中途卸货中途卸货组里程A1-140B1040A1-3484100A1-10243、从O地到C由于从O地到C地的实际距离比从O地到其他各地的距离要近，前面分析出去C地的车尽可能的多，轿运车1-1的装载乘用车的数量少，所以去C地全部安1-1II型乘用车恰好全部装载。相应目标函数和约束条件如下：in(xxxxx)(xxxxxx 5A(i,2)*x5A(i,2)*x6A(i,2)*x6A(i,2)*x i

i

i115.19终点轿运车辆中途卸货中途卸货组里程C1-705D 40C1-14005 C1-105224、从OBDA地的轿运车在全部装完到A地的乘用车后2个装I型乘用车的空位，BI型乘用车，从O地到C地的轿运车在全部装完到C地的乘用DI48辆、40IIB、D两地的方案，如表5.20所示。5.20终点层中途卸货中途卸货组里程B1-640无无40D1-540无无40辆1-2型车和1辆1-1型车共5辆车去往A处，5辆轿运车的里程数位车的总里程为1800 +800=6404。如表5.21所示5.21终点上层组合下层中途卸货组里程总里程C1-705D 40C1-14005 C1-10522A1-140B 40A1-34841 A1-1024B1-640无无40D1-540无无405-8的所有数据，如表5.22所示：所有轿运的装载及方轿运车型号类长宽高各类别车数1-172518214165221-2215102-215Excel2中给出的数据可知，我们首先排除高度大于1.7米的车，有8辆，其表示如下表5.23所示：高度大于1.7m乘用车的类1-1-21.71.71.73特3特车5迪迪车7纳车8车车卡车车车舰车奥车车车车车 51.7辆。现假设乘用车全部5辆车的情况下（10辆且上层放置两列总共可以250车，该数据远小于425辆可以放置在1-2型Excel2中的乘用车数据过多不好筛选，故我们现应用动态规划的方法对上表5.24所示的轿运车数据进行处理。动态规划的实质是分治思想和解决冗子问题的解而避免重复计算子问题,以解决最优化问题的算法策略。表5.25轿运车的装载方轿运车号类长宽高各类别车数1-11-1A**641-1B**251-1C**221-1**252-1**5Excel2中的乘用车的数据进行筛选对Excel2乘用车的大数据进行筛选得到表5.26。5.26轿运车的装载方轿运车号类长1-11-1A56441-1B52541-1C6225461-162552-1554传算法对xl2(netilgoith)是一类借鉴生物界的进化规律适者生存,优胜劣汰遗传机制)的J.ollnd授1975年首先提出,其主要特点是直接对结构对象进行操作,不存在求导和函数连续性的限定;具有内在的隐并行性和更好的全局寻优能力;采用概率化的寻优方法,能自动获取和指导优化的搜索空间,自适应地调整搜索方向,不需要确定的规则]。遗传算法是一种常用的优化方法,是以编码的空间来取代问题的参数,以适应度函数为评价标准,以编码群体为进化基础,以对群体中的位串的遗传操作来实现选择和遗传机制,从而建立的一个迭代过程。并且,其编码的技术和遗传操作是简单易行的,不受限制性条件的约束的一种优化方法,具有隐含的并行性和全局最优解的搜索能力。遗传算法是基于高度并行的、随机的及自适应的优化算法,整个过程是将问题的求解方法表示成的生存过程,并通过种群的一代代不断的进化(选择、交叉、变异等)操作,最终收敛得到最适应环境的或种群,逐渐得到问题的最优解或满意解,最终达到求解问题的目的[。型如表5.27所示：5.27优化后乘用车的分配方乘用型长宽高数车型中含的I*187、、、30、*7773、4、6、7、8、9 *87、*156、、新模型，其数据如下表5.28（b，5.28（a）所示：长宽高I3*辆3*辆8*878*辆长宽高1-11-长宽高1-11-A9**641-B**251-C**221-16*252-1**5表5.28（b）轿运车新模1-1A1122。1-1B型上15、35。1-1C18、48。1-2型上下层的最大配载数为17、41。2-2型上下层的最大配载数为12、12。能出现的放置情况记为x11x33。现的放置情况记为y15y50。的放置情况记为z18z66。1-2型其上层可能出现的放置情况记为m1m17,1-2型下层可能出现的放置情况记为m17m58。轿运车2-2型其上层可能出现的放置情况记为n1n12,2-2型下层可能出现的放置情况记为n12n24。 min=xiyizimi 0.2*(xiyizi)-(mi) A1(i,1)*xiA2(i,1)*xi11B1(i,1)*yiB2(i,1)*yi15C1(i,1)*ziC2(i,1)*zi18i1

D1(i,1)*m

D2(i,1)*

i

E1(i,1)*m

E2(i,1)*

A1(i,2)*xi A2(i,2)*xi11 B1(i,2)*yi C1(i,2)*zi C2(i,2)*zi18 D1(i,2)*miD2(i,2)*mi17E1(i,2)*miE2(i,2)*mi12 A1