基于线性规划方法的汽车租赁调度问题

2013高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛参赛规则》（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理。我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。我们参赛选择的题号是（从A/B/C/D中选择一项填写）：我们的参赛报名号为（如果赛区设置报名号的话）：所属学校（请填写完整的全名）：参赛队员(打印并签名)：1.2.3.指导教师或指导教师组负责人(打印并签名)：（论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名。以上内容请仔细核对，提交后将不再允许做任何修改。如填写错误，论文可能被取消评奖资格。）日期：年月日赛区评阅编号（由赛区组委会评阅前进行编号）：2013高教社杯全国大学生数学建模竞赛编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：1汽车租赁调度问题摘要本文利用LINGO和MATLAB软件进行数据处理，针对时下汽车租赁与调度的优化问题进行的分析，主要采用线性规划方法来建立数学模型，最终得到各个问题的全局最优解。问题一通过附件1所给的数据得到各个可供租赁的汽车代理点之间的欧氏距离,建立数学模型公式（4），通过对附件3中数据的分析，确定各个代理点之间的基本转进转出关系。再根据附件6给出的不同代理点的转运成本得出转入和转出量的转运成本表格，利用LINGO优化模型进行求解，得到第一天各个代理点之间的调度方案。利用累加法算出最小转运费，并依次求出未来四周内每天的调配方案。问题二在问题一所得结果的基础上，从转运费用和短缺损失两个方面进行考虑，因为转运费用与短缺损失费之间是负相关，所以我们用转运费用与短缺损失费之差的数学模型，求解每一天的调度费用最小的方案。同时，为防止转运周折产生的多余费用，只进行汽车的单向转入与转出，利用excel做出关于附录一所有汽车费用的表格，再运用累加法算出相对最小转运费。最后，找到其中相对运费与短缺损失费之差最多的转运方式删去，从而得到满足调度的最优方案。问题三综合考虑公司获利、转运费用以及短缺损失等因素，在需求量大于拥有量时，对n代理点进行分析，（一辆车获得的利润）=（n代理点的一辆汽车的租赁收入）—（m代理点转运到n代理点的转运费+相应代理点的转入的n代理点的短缺损失中的一辆汽车的费用）数学模型，利用规划模型求出n代理点转给m代理点一辆车所获得的利润。再以此类推，分别求出转移一辆汽车至其余代理点所获得的利润。最后，解得每一天转给所有的转入的代理点所获得的利润的最大值，即得到使公司每一天获得利益最大化的调度方案累加起来就是总的调度方案。问题四此模型的建立与求解，主要运用到运筹学中设备更新问题的数学模型。我们主要通过对过去一年各个代理点的租赁车辆的需求量的总表的统计与分析，并且根据车辆价格汽车的价格，使用寿命，以及年维修费用的不同，所产生的不同的维修费用，根据不同代理点的短缺损失费用的不同建立数学模型得到汽车租赁公司的利润最大化的方案。最后，确定购买新车的数量为12辆时，公司可以得到最大化利润.关键词：运输模型、6发点8收点约束问题、累加法、负相关2一、问题重述国内汽车租赁市场兴起于1990年北京亚运会，随后在北京、上海、广州及深圳等国际化程度较高的城市率先发展，直至2000年左右，汽车租赁市场开始在其他城市发展。某城市有一家汽车租赁公司，此公司年初在全市范围内有379辆可供租赁的汽车，分布于20个代理点中。每个代理点的位置都以地理坐标X和Y的形式给出，单位为千米。假定两个代理点之间的距离约为他们之间欧氏距离（即直线距离）的1.2倍。现在需要根据附件所提供的数据，来解决以下四个问题：1.给出未来四周内每天的汽车调度方案，在尽量满足需求的前提下，使总的转运费用最低；2.考虑由于汽车数量不足而带来的经济损失，给出使未来四周总的转运费用及短缺损失最低的汽车调度方案；3.综合考虑公司获利、转运费用以及短缺损失等因素，确定未来四周的汽车调度方案；4．为了使年度总获利最大，从长期考虑是否需要购买新车。如果购买的话，确定购买计划（考虑到购买数量与价格优惠幅度之间的关系，在此假设如果购买新车，只购买一款车型）。二、模型假设1、假设汽车的转运成本仅与距离有关，不考虑汽车在转运途中的损耗。2、假设每天租赁出的汽车于当日归还于该代理点。3、假设汽车只进行单向转入与转出，不考虑通过第三个代理点调度。4、假设每一天的费用的最小值累加起来的费用最小就是整个调度费用最小。5、若代理点的拥有量和需求量相等时，该代理点将不再参与汽车的转运系统。6、每次进行调度都基于上一日的调度方案。7、今年的营业情况和去年几乎相似，不应该存在较大的变动。8、汽车车辆数目求解时，不存在车辆报废的可能。三、符号说明𝑋𝑖:代理点ｉ的横坐标；𝑌𝑗:代理点ｊ的纵坐标；Ｍ:总的转运费；Ｗ:总的转运费用的最小值；𝑋𝑖𝑗:从代理点ｉ转运到代理点ｊ的车辆数；𝐿𝑖𝑗:代理点ｉ和代理点ｊ的距离；𝐶𝑖𝑗:代理点ｉ和代理点ｊ的欧氏距离；𝛽𝑖𝑗:代理点ｉ和代理点ｊ之间每转运一辆汽车的费用；𝛼𝑠:第ｓ天的最小转运费；μ:公司综合考虑下，获得的利润值；3四、问题分析本题是在不同的限制条件下，求解车辆租赁调度优化问题。调度问题是一个数学规划问题，即在满足调度限制的解空间内，寻找使调度选择中提出的目标函数都满意的优化解。结合实际，综合考虑租赁公司租借盈利情况和短缺亏损，以及车辆维修和保险成本等因素，运用MATLAB和LINGO软件，解出各代理点车辆租赁调度安排的最优解。问题一：根据附件1和附件3所给的数据。首先，我们通过MATLAB软件分析得到各个可供租赁的汽车代理点的位置分布图，并且可以通过对附件1中数据的分析确定各个代理点之间的基本转进转出关系。其次，对汽车租赁公司各个代理点之间调度进行分析，并且建立模型，利用LINGO求解，得到第二天各个代理点之间的调配方案。再根据模型所得结果，进行迭代处理，分别求出未来四周内每天的调配方案。最后，计算两个代理点之间的欧氏距离，通过LINGO求得转运费用最低的方案。问题二：在问题一的基础上考虑车辆短缺带来的损失，利用excel做出关于附录一所有汽车费用的表格，运用累加法算出相对最少的转运费找到其中相对运费和转运损失费最多的转运方式删去，直至相对的转入需求量与原来拥有的量相同时终止程序并分析结果。问题三：综合考虑公司获利、转运费用以及短缺损失等因素，得出每一天利润最大的调度方案使得需求量与拥有量相平衡，得到每一天所获得的最大的利润，所以总的调度方案就可以得出。问题四：根据前三问得出的结果考虑汽车价格以及使用寿命、寿命期内的年维修费用得到当供需量与拥有量平衡时的利润与没有增加车辆之前的利润进行对比，得出利润最大的购车方案。五、模型的建立和求解问题一：只考虑转运成本条件下调动方案的确定5.1.1目标函数的确定从所要解决的问题和模型的假设条件出发，我们建立了一个数学模型并对其进行求解。首先将该汽车租赁公司20个代理点的位置在图中标识（利用MATLAB），如下图所示：4各代理点的位置分布图5.1.1公式推导过程如下：根据各代理点位置坐标点计算出各个代理点之间的实际距离，再由此求出各个代理点之间的欧式距离，然后，由已知量和求第天最小转运费用。最后，将每天的最小转运费用想叠加，从而求出总的转运费用最小值。𝐶𝑖𝑗=√(𝑋𝑖−𝑋𝑗)^2+(𝑌𝑖−𝑌𝑗)^2；（1）𝐿𝑖𝑗=1.2𝐶𝑖𝑗（2）𝛼𝑠=𝛽𝑖𝑗∗𝑋𝑖𝑗（3）W=∑𝛼𝑠20s=1;（4）（i=1,2，…，20；j=1,2，…，20；s=1,2，…，20）5.1.2转移调度的初步分析：拥有量大于需求量的代理点只能出多余的车辆，如果转移出的车辆多了，还要从别的代理点重新再转移车辆，这样会使转移的距离变长，转运费变多，因此，代理点要么转进，要么转出，不可能某个代理点既转进又转出的（证明见附录）。在尽可能满足需求的情况下，分时间考虑转运费的大小，然后利用累加法即可算出最小转运费s。010203040506070010203040506070ijijXs55.1.3相应的模型建立：第2日各个代理点的拥有量、需求量以及拥有量与需求量之差表5-1-1第二天代理点需求量初始拥有最终拥有调度量1152215-72221822432219190427182795152415-9620162047151915-48121712-59192219-3101615161112718235122423230133014301614131813-515171817-116241724717162116-518132313-1019121812-6202819289根据表5.1.1可知，1、5、7、8、9、14、15、17、18、19为转出的代理点，2、3、4、6、10、11、12、13、16、20为转入的代理点。分析如下：①在需求量等于拥有量时，转运费用为0。②在需求量大于拥有量的时候，根据附录二“代理点i和代理点j之间转运一辆汽车的运费”一表，可以得到取转入2中转运运费最小的方式为15转给2，运费为0.031，同时取转入3、4、6、10、11、12、13、16、20中转运运费最小的方式分别为17转给3、运费为0.04，15转给4、运费为0.023，18转给6、运费为0.021，5转给10、运费为0.006，18转给11、运费为0.042，14转给12、运费为0.045，14转给13、运费为0.015，14转给16、运费为0.017，17转给20、运费为0.011。在这些转运运费最小的方式中，找到运费最多的一种方式，去掉这种方式，使得其相对应的转入对象的需求量与原来的拥有量相同，如果总的需求量仍然大于总的拥有量，去掉第二多的方式，使得其相对应的转入对象的需求量与原来的拥有量相同，以此类推，直至需求量等于拥有量时才停止这种做法。③在需求量小于拥有量时候，与②的方法相类似。若1代理点的需求量小于拥有量，根据附录2查到转入的代理点的转运运费，取其中的最小值。相应地，6记录其他转出代理点（即需求量小于拥有量）到转入代理点的转运运费的最小值。在所有的转运运费最小值中，找到转运运费最多的一种方式，去掉这种方式，使其不再转出任何汽车，即使其需求量与拥有量相同。以此类推，直至需求量等于拥有量相同时才停止这种做法。根据Lingo软件的“6发点8收点约束问题”，得到每一天最小的转运费𝛼𝑖。转入量（横行）和转出量（纵列）表5-1-22(4)3(3)04(9)6(4)10(1)11(9)512(1)013(16)16(7)20(9)1(7)0.0340.1230.0660.1080.2050.0560.0760.0610.0990.1785(9)0.1730.0620.1140.1450.0060.0970.1750.0650.0910.0507(4)0.0930.0540.0430.1340.0100.1380.2000.0640.0850.1058(5)0.0660.0810.0400.0460.0660.0890.0830.0910.0870.0129(3)0.1310.1280.074