乘用车物流运输计划问题

-1-参赛密码（由组委会填写）全全第十一届华为杯全国研究生数学建模竞赛第十一届华为杯全国研究生数学建模竞赛学校长沙理工大学参赛队号10536001队员姓名1.郑国义2.任涛3.田学-2-参赛密码（由组委会填写）第十一届华为杯全国研究生数学建模竞赛第十一届华为杯全国研究生数学建模竞赛题目乘用车物流运输计划问题摘要：本文针对乘用车物流运输计划问题开展了研究，取得的主要成果如下：对于问题1~3，首先，以单辆轿运车实载率最大为目标建立了单车最佳装载方案模型，运用该模型设计的装载方案总能实现轿运车剩余空间最小；其次，总是以单车最佳装载方案配送乘用车辆直到运输任务完成以获得初始轿运车数；再次，以空载率最小为目标设计了数量调整模型对初始轿运车数进行了优化；最后，针对建立的模型设计了相应的算法并编写了Matlab通用程序对问题1~3进行了求解。结果显示：问题1、问题2和问题3所需轿运车的总数分别为18、13和30辆，其中1-1、1-2型轿运车的数量分别为（16,2）、（12,1）和（25,5），对应的装载方案分别见正文表4-4、4-5和表4-6。对于第4问，首先，运用前3问的通用程序计算了最小的轿运车数；其次，建立了在轿运车数量限制下的多方案比选模型，在不考虑中途换装及迂回送货的情况下，选择总行驶里程最小的装载方案作为最优的配送方案；最后，编写程序对问题进行了求解。结果表明：当存在166辆I型和78辆II型乘用车时，最少需要25辆轿运车（其中1-1、1-2型分别为21辆和4辆），总行驶里程为6404米。具体的装载方案及配送方案见正文表5-1。对于问题5，首先，根据题目要求和实际经验确定了配送方案的一般原则；其次，运用Floyd算法计算了任意OD对（Origin-Destination,起讫点）间的最短路，并对OD对间的距离、各个点的需求及各型轿运车的运能从大到小进行了排序；再次，总是选择运能大的车辆以尽可能满载的方式依次对距离最大→次大→最小的目的地送货，直到满足所有目的地的需求；最后，设计了一种全局搜索算法、编写了完整的Matlab程序计算得到了一种合理的配送方案，并以空载率最小为目标对方案进行了优化。优化后的结果表明：本文设计的方案共-3-需要113辆轿运车才能完成运输任务，剩余38辆1-1型轿运车，车辆闲置率为25.16%，113辆轿运车的具体型号及数量见表1，总的行驶里程为32072。具体的装载方案及配送方式见正文表6-2及表6-3。表1轿运车的型号及需求数量编号12345678910型号1-1型1-1型1-1型1-1型1-2型1-1型1-1型1-1型2-2型1-2型数量20辆15辆16辆13辆10辆7辆4辆16辆5辆7辆整体而言，本文建立的模型和算法具有较强的创新性，较好地解决了本文提出的全部问题，特别是前3问的模型和算法从理论上讲一定能实现最优；编写的计算机程序具有通用性，只需修改参数即可运行并输出最优结果。建立的模型和设计的算法具有较强的理论价值和实用价值。关键词：物流运输；空载率；运能比；单车最佳装载方案模型；数量调整模型；多方案比选模型；最优配送方案-4-1.问题重述乘用车的整车物流规划是降低物流整体成本的重要影响因素。整车物流网络规划问题需要考虑的问题较多，例如库存控制策略、设施布局、运输规模效应等因素，在满足目标服务水平条件下使得整车物流网络运营成本最小。一般情况，当乘用车数量一定的时候，如何优化轿运车的数量是物流公司考虑的核心问题。物流公司根据乘用车生产厂家的全国客户订单需求，需要向全国各地派送订单任务，基于此，物流公司如何根据订单要求派送合理的轿运车，保证运输成本尽可能低，一般情况下，大多数物流公司需要根据人员经验制定运输方案，然而面对复杂运输任务时，效率低下，而且运输成本较高，因此考虑以下三点：（1）轿运车使用数量越少越好；（2）轿运车使用数量相同情况下，尽可能多地使用1-1型轿运车；（3）轿运车使用数量及型号均相同情况下，行驶里程短的成本低。本文根据物流装配人员的经验，结合题目具体要求，首先不考虑目的地限制，制定三次运输方案，提供通用的运输方案模型，其次考虑线路在运输过程中的限制，最后对于一个实际问题进行求解，对于物流公司针对45种乘用车利用现有轿运车装载问题，优化模型几乎不可能完全得到较优的结果，并且保证通用性，因此本文考虑利用启发式算法与优化模型结合的方式进行求解。2.模型假设2.1乘用车只能装在轿运车内部，即不存在最后一辆乘用车超出轿运车车身长度的情况；2.2只考虑纵向平放的情形，也就是乘用车只能纵向且平放在轿运车内部；2.3只考虑一次装货，即轿运车可以中途卸货、但不能中途装货；2.4不考虑轿运车迂回送货及返回出发点的情形。3.名词解释3.1实载率:轿运车实际装载空间与可用装载空间的比值，这里主要是指实载长度与可载长度的比值。本文以实载率最大为目标设计原型轿运车最佳装配方案。3.2空载率:它是相对于实载率而言的，这里主要是指轿运车未用长度与实际长度的比值。本文以空载率最小为目标优化初始可行轿运车数。3.3运能比:各型轿运车两两之间的实际有效长度之比。实际有效长度是指轿运车的实际长度与可装乘运车列数的乘积。如:1-2型轿运车的运能为：24.3(12)72.9m，在优化轿运车数量时，本文用到了该指标。3.4单车最佳装配方案:实载率达到最大时单辆轿运车装载的不同型号乘用车的数量，与之对应的轿运车称为原型轿运车。3.5最佳卸货方案:轿运车从出发点驶往各目的地的过程中，在中途各点卸货以满足各点的需求，这使得部分轿运车出现空置状态，此部分空置的轿运车不需要参与下一个目的地的配送任务，由此可以降低总行驶里程。在所有可行的方案中，将节省里程最大的方案称为最佳卸货方案。3.6车辆闲置率:用于运输任务的所有轿运车数与物流公司能够提供的所有轿运车数的比值。对于单次运输任务而言，企业总是希望以最少的轿运车数完成当次配送任务。因此，本文以车辆闲置率最大为优化目标，以此设计问题5的配送方案。-5-4.问题1~3的建模与求解4.1问题1~3的分析问题1~3只有一个目的地，因此只需考虑使用最少的轿运车完成要求的运输任务，不用考虑运送里程对运输成本的影响。为了保证轿运车的数量最小，应尽可能提高轿运车的实载率。为此，本文拟以轿运车实载率最高作为优化目标，设计单辆轿运车最佳装配方案。在获取单辆轿运车最佳装配方案的基础上，根据给定的运输任务建立优化模型计算最小的轿运车数。事实上，前者提供了各辆轿运车的装配方案，后者提供了最小的轿运车数。由于设计的单辆轿运车装配方案包括了I、II、III三种类型的乘用车及对应的数量，因此可以建立通用的模型和算法求解问题1~3的最优配送方案。4.2模型建立4.2.1单车最佳装配方案的设计本文首先定义了轿运车的实载率，并以此为目标来设计原型车最佳装配方案。事实上，对于任意一辆轿运车和若干辆乘用车，总有一种（或多种）装配方案使得该轿运车的剩余空间最小，这里主要是指轿运车剩余的长度最小。单车装配方案就是要找到使得该轿运车剩余空间最小时对应的乘用车类型及数量。当轿运车的剩余空间最小时，则该车的实载率达到了最大值，相反，该车的空置率达到最小值。由于III型乘用车的高度超过了1.7m，出于安全考虑只能将其装在轿运车的下层，这就导致轿运车上下层的装载方案可能不同。因此，本文根据题目的要求，分别以单辆轿运车上、下层剩余空间最小为目标建立如下的数学模型。原型轿运车下层：11nnxxxijijijjjminZLlxx(4.1)110nnxxjijijjjilxxL(4.2)xihH;12,xxxHHH(4.3)原型轿运车上层：11nnsssijijijjjminZLlxx(4.4)110nnssjijijjjilxxL(4.5)sihH;12,sssHHH(4.6)2sijhhH,,1,2ij(4.7)itT.(4.8)-6-符号说明及模型解释：表4-1原型方案设计中的符号说明iL第i种类型轿运车的长度sH轿运车上层宽度集合jl第j种类型乘用车的长度T高度限制xiH第i种类型轿运车下层的宽度乘用车横向和纵向应保持的最小安全间距siH第i种类型轿运车上层的宽度ih第i种乘用车的宽度xH轿运车下层宽度集合it第i种乘用车的高度式(4.1)~(4.8)中，目标函数表达式(4.1)和(4.4)分别表示装配后的轿运车上、下层所剩空间为最小；约束条件(4.2)和(4.5)分别表示装载后的乘用车不能超出轿运车上、下层的长度；约束条件(4.3)和(4.6)分别表示乘用车的宽度不能超过轿运车的宽度；(4.7)式表示任意两种乘用车的宽度之和不能超过1-2型轿运车上层宽度与最小横向安全距离的差；(4.8)式表示装在轿运车上层的乘用车高度不能超过规定的高度值。4.2.2初始可行轿运车数量模型单车最佳方案模型可以计算出任意最佳的初始装配方案，这些不同的最优初始装配方案对应了不同的原型轿运车。在运输需求确定的情况下，总是希望以最少的轿运车完成给定的运输任务。显然，1-2型轿运车的运能明显高于1-1型轿运车，如果轿运车的选取没有特别的要求，那么总是选择1-2型轿运车肯定是最优的。但是，物流企业拥有的1-2型轿运车数量有限，为了方便后续任务安排，1-2型轿运车的使用量不能超过1-1型使用量的20%。因此，建模时必须考虑比例约束。为了求得最少的轿运车数量，必须要保证选取出来的轿运车尽可能地装满，也就是要尽可能地提高各辆轿运车的实载率。显然，原型轿运车的实载率是最高的，因此本文总是选用这些原型轿运车来消化给定的运输需求。由此可以得到初始轿运车数。假设初始的轿运车数量包含了q1辆1-1型、q2辆1-2型，那么用于计算初始可行轿运车数量的数学模型可以表述为：12minqqq(4.9)qXQ(4.10)210.2qq(4.11)其中，12,qqq为轿运车数量向量，111212221323xxxxxxX为单一轿运车运送乘用车数量矩阵,TQQQQ321为各型乘运车需求数量向量，,,1,2,3xsijijijXxxij。-7-4.2.3算法设计根据前面的分析和建模，本文设计了如图4-1所示的初始可行轿运车数量模型。并运用Matlab编写了计算前3问的通用程序，在程序中直接输入I、II、III三种乘用车的数量即可输出初始可行轿运车的配送方案，完整的计算程序见附件，可以修改相关参数直接运行。由于算法的思想和建模的思路一致，这里不再特别说明。否否是否是否否是是是是否否是是否存在Ⅲ型乘用车计算装载Ⅲ车的最小轿运车数计算剩余空间可装载的Ⅰ、Ⅱ车辆运输任务是否完成是否满足比例要求计算剩余任务所需最小车是否满足比例要求加载原型车计算可行方案输出所需车辆数的最小方案是否满足比例要求输出所需车辆数的最小方案方案是否唯一方案是否唯一开始设计原型车给出初始装配方案输出调运方案图4-1初始可行轿运车装载数量算法流程图-8-下面针对初始可行轿运车数量算法的主要步骤进行说明：原型轿运车最佳装配方案算法设计：Step0：参数输入。各类轿运车及乘用车的参数（长、宽、高）及其它必要参数（如最少间距等）；Step1：定义解空间。计算单辆轿运车可装载单一类型乘用车的最大数量，以此作为边界条件定义多维解空间；Step2：搜索最优方案。在解空间内搜索使得轿运车剩余空间最小的乘用车类型组合及对应的数量；Step3：方案输出。将剩余空间最小的轿运车所对应的乘用车类型及数量输出。初始可行轿运车数量算法设计：Step0：初始化。输入原型轿运车最佳方案及乘用车的数量；Step1：判断是否存在III型乘用车，如果存在，则优先选择方案装载III型乘用车，直到III型轿运车装载完毕，否则，利用原型轿运车最佳装配方案装配I、II型乘用车；Step2：从可行方案中选择装载III型乘用车所需轿运车数量最少的方案；Step3：计算装载