数学建模汽车租赁调度问题.doc

.汽车租赁调度问题摘要国内汽车租赁市场兴起于1900年北京亚运会，随后在北京、上海、广州及深圳等国际化程度较高的城市率先发展直至2000年左右，汽车租赁市场开始在其他城市发展。为了对某市的一家租赁公司获利情况进行分析并确定汽车调度方案，本文我们以非线性规划为基础，通过matlab，excel等软件对数据进行处理，最小二乘法对缺失数据进行预测，最终使用lingo软件进行编程求解得到最终的优化方案。在问题一中，我们基于对题目中尽量满足需求的理解，考虑到总的车辆数和总的需求量之间的关系，用最小偏差法和分段考虑法进行了计算，分别建立多目标规划模型和非线性规划模型，通过对转运后各代理点最终的车辆数进行分析，比较两种结果得到更优的转运方案。在问题二中，我们一方面要对其短缺损失进行理解，另一方面要考虑，是否应该考虑在尽量满足需求的条件下求其最低的转运费用和短缺损失，此问题中我们同样分两种情况对其进行考虑，通过比较两者最低费用并且结合实际情况，得到更合理的转运方案。在问题三中，首先我们分析数据，剔除了其中一场的部分，并用最小二乘法对缺失数据进行预测，得到完整的单位租赁费用与短缺损失费用，然后综合考虑各种因素后，我们将公司获利最大作为最终目标函数通过非线性规划的模型求得最佳方案。在问题四中，我们没有直接对是否购买新车作出判断，而是直接以其八年获利最大为目标进行非线性规划，购买的车辆数成为其目标函数中的一个未知数，用lingo可直接求得在获利最大时的购车数量，将其与不购车时的利润进行比较可得到最佳的购买方案。关键词：非线性规划 全局最优 短缺损失 最小二乘法 一 问题重述国内汽车租赁市场兴起于1990年北京亚运会，随后在北京、上海、广州及深圳等国际化程度较高的城市率先发展，直至2000年左右，汽车租赁市场开始在其他城市发展。某城市有一家汽车租赁公司，此公司年初在全市范围内有379辆可供租赁的汽车，分布于20个代理点中。每个代理点的位置都以地理坐标X和Y的形式给出，单位为千米。假定两个代理点之间的距离约为他们之间欧氏距离（即直线距离）的1.2倍。要求根据附件所给数据计算如下问题：1给出未来四周内每天的汽车调度方案，在尽量满足需求的前提下，使总的转运费用最低；2考虑到由于汽车数量不足而带来的经济损失，给出使未来四周总的转运费用及短缺损失最低的汽车调度方案；3综合考虑公司获利、转运费用以及短缺损失等因素，确定未来四周的汽车调度方案；4为了使年度总获利最大，从长期考虑是否需要购买新车？如果购买的话，确定购买计划（考虑到购买数量与价格优惠幅度之间的关系，在此假设如果购买新车，只购买一款车型）。二问题分析汽车租赁调度问题是一个典型的数学规划问题，需要综合考虑转运费用，短缺损失，公司获利等多方面因素，在掌握了各代理点实际需求下，根据一定要求，寻找到使目标函数满意的优化解。问题一中，要求在尽量满足需求的前提下，使未来四周的总转运费用最低。对数据进行处理后，对尽量满足需求这一约束条件，认为其在需求量大于供应量时应保证每辆车都能够被利用，在需求量小于供应量时应保证每个代理点的需求都能被满足。然后据此约束建立多目标规划模型求全局最优解，使得未来四周总的转运费用最小。针对问题二，我们需要考虑在汽车数量不足的情况下所带来的短缺损失，所谓短缺损失是指，在某代理点某天经过转运后最终的车辆数比需求量少时，少的车辆数与单位短缺损失的乘积。在此基础上建立两种模型，第一种是尽量满足需求条件下的模型，第二种是不考虑尽量满足需求这一条件下的模型。然后分别建立非线性规划模型求全局最优，使得未来四周的转运费与短缺损失之和最小。针对问题三，综合考虑公司获利、转运费用以及短缺损失等因素，以公司获利最多作为目标函数，考虑到前期尽量满足需求对公司后续的租赁需求影响，在此仅分析在尽量满足需求条件下获利最多。对于附录中丢失的数据，我们将平均需求量与租赁收入之间的关系曲线采用最小二乘法进行拟合，预测出缺失的数据以及异常数据。最后将其考虑为非线性规划问题对其进行规划求全局最优，得到最佳的调度方案。针对问题四，由于一年中最大需求量要比实际供应量多66辆车，故我们将购买车的数量m取小于66的值，然后分别计算每增加一辆能够获得的最大的利润，然后求得最优的m值，该m的取值区间会有一个值使得获利最大。由于车型不影响租赁收入，所以在考虑车型时，选择是8年成本和维修费用之和最低的一款。三符号说明第k天第i个代理点转运之后最终的车辆数第k天第i个代理点的需求车量数第k天第i个代理点转到第j个代理点的车辆数第i个代理点到第j个代理点转运一辆的运费第i个代理点的单位短缺损失（万元/天*辆）该公司拥有的总的车辆数每天所有代理点总的需求量e 选中的车型每辆总的花费m需要购买的车辆数 第k天第i个代理点短缺的车辆数四模型假设1.假设租赁车辆不会损坏，且不会产生维修保养费用。2.假设当天租出去的车会当天归还，不影响第二天租赁。3.假设每次车辆转运发生在一天的结束后，第二天之前。4.假设附件2所给一年各代理点的汽车需求量代表未来八年的汽车需求量。5.假设购买新车的周期为8年。6.假设价格不考虑涨价等情况。7.假设前期的不满足需求不会影响到后续的需求量。五模型建立与求解5.1问题一5.1.1对问题一的理解问题一要求在尽量满足需求的前提下，使总的转运费用最低。对于尽量满足需求，我们对其有两种理解。一是使每天每个代理点转运后最终的车辆数与其需求量的偏差最小。二是认为其在需求量大于供应量时应保证每辆车都能够被利用，在需求量小于供应量时应保证每个代理点的需求都能被满足。5.1.2基于偏差最小的多目标规划模型的建立与求解首先用matlab对附件1和附件6中数据进行处理，得到两两代理点之间每转运一辆车的转运费用。具体结果见附件1。用表示其偏差，建立多目标规划如下：min s.t. 上式可求得当其偏差和最小时每天每个代理点经过转运后的最终车辆数。在此基础上以其转运费用最低为目标函数建立如下模型：min s.t. 利用lingo软件编程解得最小的转运费用为70.4987万元，以下是前11天各代理点转运之后最终的车辆数。 由下表数据可知，在该模型下，虽然大部分代理点几乎完全满足需求，但是一些代理点经过转运之后一辆车也没有，这违背了尽量满足需求这一条件，也不符合实际情况，同时求解得到其运输费用最小为70.4987万元，远高于第二个模型的最小运输费用，所以该模型被舍弃。表5.1.2 前11天各代理点转运之后最终的车辆数 日期代理点1234567891011A2215980221912132826B182228172319390292016C192225213054272502514D182715202020201215110E241528017151228181321F1620241819131529141720G1915252221122216242214H174191418261724231328I221901725251820271411J15160180231930142911K1827171123161630272712L2324182913171412162223M1430262320112015291930N1813192715161215111218O1817151520141513141319P1724302829113017182316Q2116281830113012151425R2313121525141118221529S1812282830141221221625T1928133012611302826215.1.3基于分段考虑的非线性规划模型的建立与求解 对该公司拥有的总的车辆数和总的需求量进行比较，通过对两者大小的判断，以此述判断为分段约束条件，直接以转运费用最低位目标函数建立非线性规划模型如下： min s.t. 当 时 当 时 利用lingo软件编程对该模型进行求解得，最小的转运费用为40.4916万元，下表给出前11天各代理点转运之后的最终车辆数，完整表格见附件3：表5.1.3 前11天各代理点转运之后最终的车辆数1234567891011A2215151514222115222828B1822221721191211252011C1922222127272725112514D1826152020202012121112E2415151217151518181321F1620241818141529141720G1915212121132216242214H1712151418262424231322I2219181725252020241411J1516131813231926142911K1821171112161630272712L2323181813171412162222M1430212320122015201930N1813192015161415111218O1817151515151513131317P1724282829253017182316Q2116281824143012151425R2313121515141118221529S1812282828202021221625T1928133014261430282621由上表数据可以看出，该模型在尽量满足需求的条件下分配的也比较合理，远远优于第一种模型，而且转运费用也远远低于第一种模型。转运方案：1-20分别代表A-T20个租赁代理点第一天：12(7) 213(3) 510(9) 74(5) 84(1) 820(4) 911(3) 103(3) 106(4) 107(1)1413(5) 154(1) 1613(2) 1720(5)184(1) 1816(9) 1 913(6)第二天：47(2) 414(9) 910(1) 107(4) 116(4) 1214(5) 1316(4) 1319(5) 1419(8) 119(2) 1819(1) 208(3) 2017(12)第十四天：411(12) 611(2) 820(3) 910(16) 1413(2)1416(4) 152(6) 153(2) 1 54(5) 1514(1) 173(3) 1918(1) 203(2)完整转运方案可见附件2分析第十四天的转运方案在代理点4既有转入又有转出，表面上看如此周折会产生多余费用，实际上这样是节省了转运费用，由附件1可知，1 511转运费用0.04余万元每千米，而1 54再从411转运费用是0.03余万元每千米。因此如此周转节省了转运费用。5.1.4模型比较通过对以上两种方案最小转运费用的的比较，发现第二种基于全局优化的非线性规划模型得到的最小转运费用远远小于第一种模型，并且由第一种方案得到的转运后的最终车辆数在一部分代理点中出现了零，这是不符合实际情况的，也偏离了尽量满足需求这一要求。所以我们选择了第二种方案作为最终的调度方案。5.2问题二5.2.1 对问题二的理解问题二要求在考虑短缺损失的情况下，求得使四周总的转运费用及短缺损失最低的最佳汽车调度方案。本题我们同样分两种情况考虑，第一种是考虑在尽量满足需求的前提进行求解，即在问题一的基础上保留使得尽量满足需求的约束条件。第二种是不考虑尽量满足需求即在问题一的基础上去掉使得尽量满足需求的约束条件。并且应该明确的是：在尽量满足需求的前提下，只有在该公司拥有的总的车辆数小于总的需求量时才存在短缺损失，并且是转运费用与短缺损失之和最低。由此我们可以以和费用最低为目标函数建立如下模型。5.2.2考虑尽量满足需求时模型的建立与求解考虑尽量满足需求，即要对该公司拥有的总的车辆数和总的需求量之间进行比较，在需求量大于供应量时应保证每辆车都能够被利用，在需求量小于供应量时应保证每个代理点的需求都能被满足。建立非线性规划模型如下： s.t. 当 时 当 时 当 时 当 时 利用lingo软件编程对该模型进行求解，最小的转运费用与短缺损失共为70.1639万元5.2.3不考虑尽量满足需求时的模型建立与求解不考虑尽量满足需求，即使得损失与运输费之和最小而不用考虑尽量满足需求这一约束条件，建立非线性规划模型如下： s.t. 当时 当时 运用lingo软件编程对该模型进行求解，最小的转运费用为64.2085万元。 汽车调度方案见附件4 通过分析各代理点的转运费用和短缺损失费用，可以知道造成两种模型的差价原因，由数据可知，部分代理点中从一个代理点到另一个代理点的转运费用是大于后者代理点的短缺损失费用的。因此在尽量满足需求的前提下，调动进行的多一些，忽略了差价，使得总的费用高于第二种模型。 5.2.4模型比较通过比较以上两种情况下的最小转运费用，我们会发现考虑尽量满足需求与不考虑尽量满足需求的最小转运费用相差并不大，我们综合考虑能让每个代理点尽可能的正常运行，该公司的信誉等多方面因素，考虑尽量满足需求这种情况更加合理。5.3问题三5.3.1对问题三的理解问题三要在综合考虑公司获利、转运费用以及短缺损失等因素的情况下，确定未来四周的汽车调度方案，使总的获利最大化，同样需要考虑尽量满足需求，在此与问题2相似，仅考虑尽量满足需求这一情况，其余不再赘述。由于附件5所给的单位租赁收入数据不完整，我们需要对其缺少的数据进行预测，从而计算其总的租赁收入。5.3.2基于最小二乘法的预测模型对于该题中的数据缺失，需要对其数据进行预测，我们认为其租赁收入预期地理位置有关，用MATLAB做出代理点分布图如下，对地理位置邻近的代理点的租赁收入分析后发现并无必然联系。图5.3.2.1再次经过对数据的比对分析后我们认为其与未来四周各代理点平均每天的需求量有一定关系，计算出每个代理点前四周平均需求量与租赁收入表如下表5.3.2.1其数据基本满足线性关系，在MATLAB下用最小二乘法分别进行一次函数拟合，二次函数拟合，三次函数拟合， 可得其拟合函数均为一次线性关系，如下图图5.3.2.2所以采用一次拟合函数补全缺失数据如下表表5.3.2.25.3.3基于公司获利最多的模型建立与求解考虑到公司获利要多，转运费用及短缺损失要尽量少，我们建立非线性规划模型如下： s.t. 当时 当时 当 时 当 时 利用lingo软件编程对该模型进行求解，可以得到在尽量满足需求的条件下公司在这四周内获利最多为4103.29万元。5.4问题四5.4.1对问题四的理解首先我们要考虑购买新车是否能够使获利增加。其次，如果购买，则要对其购买哪种车型及购买多少辆进行确定。在此我们假设购买了m辆车，使其总车辆数达到379+m辆，然后对其最大获利进行计算，从而可得到最大获利时m的值。如果m=0则表示购买车并不能够使获利增加。5.4.2问题四模型的建立与求解a.对车型的选择通过excel对附件4中数据进行处理，得到购买每种车型八年所需总费用。结果如下表：表5.4.2.1车型12345678910八年总花费（万元）43.1946.6648.7544.2758.353.354.7141.2160.2456.68由上表可得第8种车型八年总的花费最低，因为不管车好车坏我们都只考虑其只能使用8年，且不考虑八年后车辆的残存费用，较贵的车型并不能使得租赁费用增加或使需求量有所改变，故在对车型的选择时我们只考虑车费和8年总的维修费之和最低，根据上表，如需购买车辆，则选择第8种型号的车。b.模型建立假设购买m辆第8种型号的车，由附件2中一年的数据分析可得，需求量最多时缺少66辆车，所以购买车辆数m的上限为66辆，为使其八年总的获利最多，即建立目标函数使得平均每年的的获利最多，以减少计算的数据量，将每辆车的总费用平均分摊到每一年，建立非线性规划模型如下：s.t. 当时 当时 c.模型求解用lingo软件编程对该模型进行求解，得到最大获利与够买车辆数量关系图如下图5.4.2.1可得出该公司八年中平均每年获利最大值为52855.52万元，获利最大时对应m值为46即购买46辆第8种型号的车能够使每年获利达到最大值52855.52万元，所以应该购买新车，购买46辆第八种型号的车可以使总获利最大。六.模型评价与改进问题一通过比较对尽量满足需求的两种理解，得出分段考虑总的车辆数和总的需求量大小的结果更优，但我们并不知道该公司具体对尽量满足需求的要求。在本题中分别建立了多目标规划模型和非线性规划模型，用lingo求解运行时间过长，如果可以建立线性规划模型那么可以大大缩短运行时间。问题二同样建立非线性规划模型，对转运费用与短缺费用之和求最小值，模型简单明了，易于执行，并且考虑了尽量满足需求与不尽量满足需求两种情况，通过比较分析，得到的结果更加符合实际。问题三巧妙地使用最小二乘法求得缺失的数据，虽然不是非常精确，但方法简单，执行方便，可靠程度较高。通过对问题的分析，将获利最大作为最终目标进行规划求解，简化了求解过程。考虑到预测数据的精确性，本题还可用BP神经网络，综合多个因素影响，结果会更加可靠。问题四引入变量购买车辆数将两问结合成一个非线性规划问题，一次性可以解决两个问题，模型简单，可行性高，便于推广。 七参考文献1李庆杨等，数值分析（第四版），华中科技大学出版社，2006.72胡运权，运筹学教程（第三版）,清华大学出版社，2007.43吴建国等，数学建模案例精编，中国水利水电出版社，20054姜启源等，数学模型（第三版），高等教育出版社，20035赵东方，数学模型与计算，科学出版社，2007.2八附录程序问题1：ti1.lg4model:sets:i/1.20/:shu;k/1.29/:shuzi;lin(k):c;link(k,i):a,b;links(i,i,k):p;linkp(i,i):yun;endsetsmin=sum(k(z):sum(i(x):sum(i(y):p(x,y,z)*yun(x,y);for(k(z)|z#le#28:for(i(y):sum(i(x):p(y,x,z+1)-p(x,y,z+1)=b(z,y)-b(z+1,y); for(k(z):c(z)=sum(i(x):a(z,x);for(link(z,x):if(c(z)#gt#379,b(z,x),-b(z,x)=if(c(z)#gt#379,a(z,x),-a(z,x); for(k(t):sum(i(x):b(t,x)=379); for(link:gin(b); for(links:gin(p);data:enddataendti1.m%计算两两代理点之间的距离clear all;clc;%读取坐标coordinate=xlsread(C:UserslifengDesktop2014模拟练习2A题汽车租赁调度问题附件1：代理点的位置及年初拥有车辆数.xls,Sheet1,B3:U4);distance=zeros(20);length=size(distance);% 为距离矩阵赋权值for i=1:length for j=1:i distance(i,j)=sqrt(coordinate(1,i)-coordinate(1,j)2+(coordinate(2,i)-coordinate(2,j)2); endend% 计算每辆车在代理点间的转运价格%单位转运成本cost=xlsread(C:UserslifengDesktop2014模拟练习2A题汽车租赁调度问题附件6：不同代理点之间的转运成本.xls,Sheet1,C3:V22);price=cost.*distance*1.2;for i=1:length for j=i:length price(i,j)=price(j,i); endendxlswrite(C:UserslifengDesktop2014模拟练习2代码每辆车在代理点间的转运价格.xls,price,C3:V22);问题2：ti2.lg4!第二题;model:!i代表站点，k代表日期，lost代表站点的单位损失，c代表每天的需求总量，a，b，d分别为每个站点需求量,实际量和缺口量，p为转移数量，yun代表运费;sets:i/1.20/:shu;k/1.29/:shuzi;li(i):lost;lin(k):c;link(k,i):a,b,d;links(i,i,k):p;linkp(i,i):yun;endsetsmin=sum(k(z):sum(i(x):sum(i(y):p(x,y,z)*yun(x,y)+sum(link(z,x):d(z,x)*lost(x);for(k(z)|z#le#28:for(i(y):sum(i(x):p(y,x,z+1)-p(x,y,z+1)=b(z,y)-b(z+1,y); for(link(z,x):d(z,x)=if(a(z,x)#gt#b(z,x),a(z,x)-b(z,x),0);for(k(z):c(z)=sum(i(x):a(z,x);for(link(z,x):if(c(z)#gt#379,b(z,x),-b(z,x)=if(c(z)#gt#379,a(z,x),-a(z,x); for(k(t):sum(i(x):b(t,x)=379); for(link:gin(b); for(links:gin(p);data:enddataend问题3：ti3.lg4!第三题;model:!i代表站点，k代表日期，lost代表站点的单位损失，c代表每天的需求总量，a，b，d分别为每个站点需求量,实际量和缺口量，p为转移数量，yun代表运费;sets:i/1.20/:shu;k/1.29/:shuzi;li(i):lost,win;lin(k):c;link(k,i):a,b,d,e;links(i,i,k):p;linkp(i,i):yun;endsetsmax=sum(link(z,x):e(z,x)*win(x)-sum(k(z):sum(i(x):sum(i(y):p(x,y,z)*yun(x,y)-sum(link(z,x):d(z,x)*lost(x);for(k(z)|z#le#28:for(i(y):sum(i(x):p(y,x,z+1)-p(x,y,z+1)=b(z,y)-b(z+1,y); for(link(z,x):e(z,x)=if(a(z,x)#gt#b(z,x),b(z,x),a(z,x);for(link(z,x):d(z,x)=if(a(z,x)#gt#b(z,x),a(z,x)-b(z,x),0);for(k(z):c(z)=sum(i(x):a(z,x);for(link(z,x):if(c(z)#gt#379,b(z,x),-b(z,x)=if(c(z)#gt#379,a(z,x),-a(z,x); for(k(t):sum(i(x):b(t,x)=379); for(link:gin(b); for(links:gin(p);data:enddataend问题4：ti4.lg4!第四题;model:!i代表站点，k代表日期，lost代表站点的单位损失，c代表每天的需求总量，a，b，d分别为每个站点需求量,实际量和缺口量，p为转移数量，yun代表运费;sets:i/1.20/:shu;k/1.365/:shuzi;li(i):lost,win;lin(k):c;link(k,i):a,b,d,e;links(i,i,k):p;linkp(i,i):yun;endsetsmax=sum(link(z,x):e(z,x)*win(x)-sum(k(z):sum(i(x):sum(i(y):p(x,y,z)*yun(x,y)-sum(link(z,x):d(z,x)*lost(x)-q*5.15125;for(k(z)|z#le#28:for(i(y):sum(i(x):p(y,x,z+1)-p(x,y,z+1)=b(z,y)-b(z+1,y); for(link(z,x):e(z,x)=if(a(z,x)#gt#b(z,x),b(z,x),a(z,x);for(link(z,x):d(z,x)=if(a(z,x)#gt#b(z,x),a(z,x)-b(z,x),0);for(k(z):c(z)=sum(i(x):a(z,x);for(link(z,x):if(c(z)#gt#379+q,b(z,x),-b(z,x)=if(c(z)#gt#379+q,a(z,x),-a(z,x); for(k(t):sum(i(x):b(t,x)=379+q); for(link:gin(b); for(links:gin(p);gin(q);data:enddataend数据附件1：每辆车在代理点间的转运价格.xls附件2：问题1转运方案.xlsx附件3：问题1转运后的.xlsx附件4：问题2转运方案.xlsx附件5：问题3转运方案.xlsx可编辑