2013高教社杯全国大学生数学建模竞赛
承 诺 书
我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛参赛规则》（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）。
我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。
我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。
我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理。
我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。
我们参赛选择的题号是（从A/B/C/D中选择一项填写）： 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 参赛队员 (打印并签名) ：1. 2. 3. 指导教师或指导教师组负责人 (打印并签名)： （论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名。以上内容请仔细核对，提交后将不再允许做任何修改。如填写错误，论文可能被取消评奖资格。）
日期： 年 月 日 赛区评阅编号（由赛区组委会评阅前进行编号）：
2013高教社杯全国大学生数学建模竞赛
编 号 专 用 页
评 阅 人 评 分 备 注 赛区评阅编号（由赛区组委会评阅前进行编号）：
赛区评阅记录（可供赛区评阅时使用）：
全国统一编号（由赛区组委会送交全国前编号）：
全国评阅编号（由全国组委会评阅前进行编号）：
汽车租赁调度问题
摘 要
本文通过对汽车租赁公司调度问题进行认真细致的研究，采用了动态规划的方法建立相关的数学模型，主要运用贪心算法对汽车进行安排调度，利用MATLAB软件编程进行求解，最终得到了具体的解决方案。
针对问题一，首先我们的规划目标为转运费用最小，在保证代理点的需求尽量得到满足的前提下，观察代理点的转入转出情况，根据贪心算法的原理依次按照最小转运费对应的代理点进行转入和转出的调度，然后是次小的转运费对应的代理点，从而建立了使目标函数最小的动态规划模型，找出当天的调度方案，然后依次进行迭代求解,最终得到最小转运费用为15.0243万元以及此时对应的车辆调度安排（见附录1）
针对问题二，首先通过对附件表格中的数据进行分析可知，短缺费一般比转运费高，所以我们优先满足短缺损失费最大的代理点，再找到与之对应的转运费较小的的代理点进行转运，直到满足需求为止，然后再找到短缺损失费次大的代理点重复上述过程，我们以转运费与短缺损失费的和的表达式来构建模型，最终得到结果为62.85万元以及此时的车辆调度方案(见附录2）
针对问题三，首先经过分析，我们认为以租赁收入与短缺损失费的和最大的代理点优先进行调度比较合适，因为其和表示转入车辆之后相对于未转入之前的相对收入。之后按照问题二的解决思路建立基于贪心算法的规划模型，最终可以求得所获最大利润为3993万元以及对应的调度方案（见附录3）
在这之前对附件5中缺损的最后5个租赁收入我们采用多元线性回归[1]进行了预测。
对于问题四，首先分析附件4选出购买第8种车，然后以全年总获利最大为目标，在问题三的基础上，以购买一辆为步长进行搜索，最后得出在购买23辆汽车时可以得到最大获利50924万元。
关键词：贪心算法、迭代、多元线性回归、动态规划
1
一、问题重述
国内汽车租赁市场兴起于1990年北京亚运会，随后在北京、上海、广州及深圳等国际化程度较高的城市率先发展，直至2000年左右，汽车租赁市场开始在其他城市发展。
某城市有一家汽车租赁公司，此公司年初在全市范围内有379辆可供租赁的汽车，分布于20个代理点中。每个代理点的位置都以地理坐标X和Y的形式给出，单位为千米。假定两个代理点之间的距离约为他们之间欧氏距离（即直线距离）的1.2倍。附件1—附件6给出了问题的一些数据。
请解决如下问题：
1．给出未来四周内每天的汽车调度方案，在尽量满足需求的前提下，使总的转运费用最低；
2．考虑到由于汽车数量不足而带来的经济损失，给出使未来四周总的转运费用及短缺损失最低的汽车调度方案；
3．综合考虑公司获利、转运费用以及短缺损失等因素，确定未来四周的汽车调度方案；
4．为了使年度总获利最大，从长期考虑是否需要购买新车？如果购买的话，确定购买计划（考虑到购买数量与价格优惠幅度之间的关系，在此假设如果购买新车，只购买一款车型）。
2
二、问题分析
本题主要在不同的限制条件下，研究车辆租赁的优化调度问题。联系实际，考虑转运费用、短缺损失、利润等因素，利用优化算法和matlab，得到各代理点车辆租赁调度安排的最优解。
针对本问题中的优化问题，本文在对不同的条件下应用了不同的约束和限制，然后运用贪心算法分别求出问题的解决方案。
对问题一，在仅考虑转运费用的情况下，首先根据代理点的需求量和实际数量的差值，判断各代理点的转入和转出情况，然后根据代理点间的费用关系，利用贪心算法寻找最小转运费用对应的代理点进行车辆的调度，最终得到每天的调度方案以及总的调运费用。
问题二是在问题一的基础之上增加了车辆短缺费的情况，因此需要在问题一中增加各代理点车辆短缺时导致的损失费，同问题一的方法，首先确定各代理点的转入转出情况，然后在需转入的代理点中找出缺损费最大的，根据转运费最小的原则进行调度，直到各需转入代理点依次被满足为止。
问题三在问题二的基础上增加了租赁收入，这时利润=租赁收入-转运费-短缺损失费，我们的目标是使净收入最大。在这之前我们用多元线性回归预测出了最后5个代理点的租赁收入。在进行调度时，我们优先对租赁收入与转运费总和最大的代理点进行转运，以此为调度的基准找出总的调度方案。
而对于问题四中考虑是否应购买新车的问题，考虑到问题二、三中由于车辆短缺会造成一定的利润损失，因此我们认为需要购买新车。对附件4的数据进行分析可知应购买8型号的汽车。购买新车需花费一定的费用，此时的获利情况应为第三问中的利润减去购车费和维修、保险费。以此为新的目标函数并结合第三问的调度方式依次增加购买汽车数量，最终可以得到购买方案。
3