汽车租赁的优化调度问题.doc

汽车租赁的优化调度问题摘　要本文利用matlab和lingo进行线性规划从而实现汽车租赁的优化调度根据题意确定合理的目标函数和约束条件，同时基于贪心算法思想，在不影响全局最优解的前提下划分子集简化运算，通过规划子集的最优解，最终得到各个问题的全局最优解由于当需求量与实际车辆数相等时，该天的车辆安排是唯一的，因此以该天为节点将全局划分为若干子集，全部子集的最优解则组成全局的最优解利用贪心算法的思想通过求解各子集的最优实现全局最优，使得计算的数据量分散开来，提高了运算效率问题一规划目标为转运费用最小，在保证各代理点转进与转出的车辆数相等以及分配后的车辆数符合实际供求关系的前提下，利用lingo对划分的子集进行规划求解，最终得到最小转运费用为40.5150万元以及此时对应的车辆调度安排问题二在问题一的基础上规划目标为转运费用和短缺损失费用的总和最小，在同样的约束条件下利用lingo进行求解，最终得到转运和短缺导致的最小总费用为70.3055万元以及此时对应的车辆调度安排问题三规划目标为公司获得的利润，公司获得的利润为车辆租赁收入扣除转运费用和短缺损失费用后的数值考虑同样的约束条件，利用lingo进行优化，最终得到公司最大获利为3966.053万元以及此时对应的车辆调度安排。

问题四通过对附件4的分析决定采购第8类车型，通过对附件2的分析发现每天代理点的需求量前后不存在相关性，因此抽取其中的三分之一作为计算数据来考虑今年的年度总获利最大的购车方案考虑到实际情况，购车方案中的购车成本要在一年内能够完全收回在此基础上分别求解并分析购买新车数量为0、10、20、30、40、50的时候年度最大获利情况的变化，利用三次多项式拟合发现购车数量在20和30之间存在最大值再分析购车数量为21、22、23、24、25、26、27、28、29的时候年度最大获利值的变化情况，最终得出新购买26辆第8类车型可以获得最大年度获利，约为51822.33万元为了检验本模型的性能，以一周为检验区间，分别求解每天最优时的结果和不进行调度安排时的结果，与本模型得到的结果进行对比，得到了本模型求解的结果是已知最优的结论本模型利用贪心算法，通过合理划分子集的思想来分散计算量，在实际数据处理中有一定的借鉴意义Lingo显示规划的结果为全局最优，模型求解较好关键词：汽车租赁 线性规划 贪心算法 随机数据相关性分析 多项式拟合1　问题重述国内汽车租赁市场自兴起以来发展迅猛某城市有一家汽车租赁公司，此公司年初在全市范围内有379辆可供租赁的汽车，分布于20个代理点中。

每个代理点的位置都以地理坐标X和Y的形式给出，单位为千米假定两个代理点之间的距离约为他们之间欧氏距离（即直线距离）的1.2倍附件1至附件6给出了问题的一些数据试建立数学模型，请解决如下问题：1．给出未来四周内每天的汽车调度方案，在尽量满足需求的前提下，使得总的转运费用最低；2．考虑到由于汽车数量不足而带来的经济损失，给出使未来四周总的转运费用及短缺损失最低的汽车调度方案；3．综合考虑公司获利、转运费用以及短缺损失等因素，确定未来四周的汽车调度方案；4．为了使年度总获利最大，从长期考虑是否需要购买新车？如果购买的话，确定购买计划（考虑到购买数量与价格优惠幅度之间的关系，在此假设如果购买新车，只购买一款车型）2　问题分析本题主要在不同的限制条件下，研究车辆租赁的优化调度问题联系实际，考虑转运费用、短缺损失、利润等因素，利用优化算法和lingo、matlab工具，得到各代理点车辆租赁调度安排的最优解对于动态优化问题，贪心算法是很常见的算法之一，这是由于它简单易行，构造贪心策略不是很困难但是遗憾的是，使用贪心算法时需要证明整个问题的最优解是不是由在贪心策略中存在的子问题的最优解构成的对于本问题，仅仅将每天的最优解进行累加作为问题最后的最优解是不对的，这是因为整个问题的最优解不是由每天的最优解构成的（有时可能会因为统筹考虑未来几天的需求而导致某一天的调度安排并不是该天的最优解）。

但是通过对附件2和附件3的数据进行分析，我们发现总会存在一些天数，其当天的总需求量和公司的车辆总数是相近甚至是相等的正如我们将在假设中提到的，考虑到实际过程中公司为了盈利和声誉，不会存在有需求可以满足的时候却让汽车闲置的情况，所以当总需求量和车辆数相等时，该天的调度安排是唯一的（即各代理点拥有的车辆数等于其需求的车辆数），并且一定是整个问题的最优解的一部分当各代理点的总需求量和公司的车辆总数相近的时候，考虑到个别车辆的安排调度对整个全局的影响很小，可以忽略不计，也可以认为该天的最优解也是整个问题的最优解的一部分以这些天数作为节点可以把整个问题划分成若干个子集，对子集利用lingo进行线性规划求出最优解最终得到整个问题的最优解通过对子集进行求解可以大大降低运算的复杂程度和运算时间，这一方法的优点在后面处理一年的数据的时候得到了体现对于问题一，仅考虑总的转运费用的情况下，首先根据未来四周每天各代理点的总需求量和实际车辆数的差值，对未来四周进行子集的划分再在各个子集里求转运费用最小的解，最终得到全局的最优解问题二在问题一的基础上考虑车辆短缺带来的损失因此目标函数需要在问题一的基础上加上各代理点车辆短缺时导致的损失费，再通过线性规划求使目标函数最小时的解。

问题三考虑到公司的获利，首先对缺失的租赁收入数据用平均值代替目标函数为各代理点的租赁收入扣除转运和缺失的费用后的利润值利用lingo规划求解目标函数最大时的车辆调度安排问题四首先通过对附件4分析选定车型再对附件2去年一年各代理点需求量进行分析作为求解今年时的数据参考由于数据量比较大，可以考虑对数据进行处理以简化计算通过尝试购买不同数量的新车来研究年度获利的变化情况以从中发现规律，最终确定新车的购买计划3　模型假设1.租出的车辆只归还于所租赁的代理点2.汽车的转运成本仅与距离有关，不考虑汽车在转运途中的损耗3.租赁的汽车当日归还，不存在拖延的现象4.不考虑车型对维修、转运等费用带来的影响5.调度工作在第二天各代理点营业开始前已经完成6.当总需求量不大于实际车辆数的时候，保证各个代理点的需求都得到满足（此时不存在为了降低转运费用使代理点出现供不应求的情况，这样做既会影响公司声誉，也不符合实际公司的盈利目的）7.今年和去年营业状况相似，市场需求不会出现较大的波动8.车辆在求解的时间范围内不存在报废的现象4　符号说明d i j —— 代理点i到代理点j的欧氏距离（i≤20,j≤20）c i j —— 代理点i到代理点j的转运成本（万元/千米）（i≤20,j≤20）r t i —— 代理点i第t天的需求量（t≤29,i≤20）kz —— 编码过程中的控制参数，当判断条件大于零的时候kz=2；当判断条件小于零的时候kz=0f i j —— 代理点i到代理点j的转运费用（万元/辆）（i≤20,j≤20）F20×20 —— 代理点间相互转运的费用矩阵，由f i j组成a t i j —— 第t天代理点i转运给代理点j的车辆数。

当i=j的时候表示该天的分配方案中i代理点留给自己的车辆数（t≤29,i≤20, j≤20，A t i j≥0）A29×20×20 —— 未来四周公司各个代理点的车辆调度安排，由a t i j组成s i —— 代理点i的短缺损失费（万元/天·辆）S1×20 —— 短缺损失费用矩阵p i —— 代理点i的租赁收入（万元/天·辆）P1×20 —— 租赁收入矩阵x —— 新购车辆的数量mi —— 购买第i种车的成本（万元/辆）wij —— 第i种车在第j年的维修保险费用（万元/辆）Z —— 问题求解中的目标函数5　模型的建立与求解5.1　问题一5.1.1　数据的处理与分析1.代理点地理位置的处理根据附件1代理点的地理位置坐标，通过Excel绘制出各代理点之间的地理位置关系，如图5-1所示5-1　代理点的地理位置2.未来四周需求量与实际车辆数的差值代理点总共拥有379辆可供租赁的汽车对附件3进行数据处理，计算出未来四周内每天各代理点总的需求量和公司可供租赁的汽车辆数的差值，并绘制成折线图，见图5-25-2　总需求量与实际车辆数的差值通过折线图我们可以发现，未来四周内存在某些天代理点的总需求量和公司总共的车辆数相近甚至是相等（图中标红的点）。

由于这些点其当天的最优解一定是整个问题最优解的子集，所以可以据此将未来四周划分成若干子集，利用贪心算法思想，通过求解子集的最优解最终得到全局的最优解当然，本问题由于只是二十八天的数据，计算量还不是很大，为了保证解的最优性，可以只选择差值为零的第十天作为节点分成两个子集3.各代理点相互转运的费用利用matlab对附件1和附件6的数据进行读取和处理，计算各代理点相互转运的费用f i j= d i j * c i j，从而得到各代理点相互转运的费用的矩阵F20×20，见图5-3和图5-4图5-3　代理点之间相互转运的费用图5-4　代理点之间相互转运的费用5.1.2　模型的建立本问题属于整数线性规划问题，根据各代理点的需求和各代理点之间的转运费用，通过动态规划实现总转运费用最小首先构造矩阵A29×20×20用来表示未来四周公司各个代理点的车辆调度安排，则可以发现矩阵A29×20×20第i行表示该天代理点i对其所拥有车辆的调度安排，第i列表示调度安排完之后该天代理点i所拥有的车辆，元素a t i j代表第t天代理点i转运给代理点j的车辆数，以第一天的矩阵为例，如图5-5图5-5　第一天车辆调度安排计划a 12 =7,表示A点转运给B点七辆车；第七行表示代理点G转运给D五辆车，留给自己十四辆车；第七列表示当天调度安排结束后代理点G拥有十五辆车，其中十四辆是自己留给自己的，一辆是代理点J转运过来的。

调度安排过程中还要满足以下三点：代理点i转运前拥有的车辆数等于代拥有理点i转运出去的车辆数、转运进来的车辆数以及留下来的车辆数之和，即转进来的车辆数等于转出去的车辆数，包括自身对自身的转进和转出，见式（1）；当该天的总需求量大于公司总的车辆数的时候，各站点调度后拥有的车辆数不大于该站点的需求量，见式（2）；当该天的总需求量小于公司总的车辆数的时候，各站点调度后拥有的车辆数要不小于该站点的需求量，见式（3） （1）对于第i个站点来说，其第t天的需求量为r t i，则 时， （2） 时， （3）根据上述条件可以得到规划模型中的目标函数Z，见式（4）： （4）根据（1）、（2）、（3）、（4）式，通过编码，利用lingo软件进行线性规划求目标函数Z最小对于判断语句我们编码时用控制参数kz来实现，从而便于公式的表达以及求解过程中运算的简便当时kz=2；当时kz=0这样我们执行语句就可以写成由于第十天的时候总需求量等于总车辆数，可以据此分成两段，分别求解出每个子集的最优解，最终得到整个二十八天车辆调度安排的最优解（代码见附件二）5.1.3　结果分析经过求解得出未来四周车辆调度安排在最优解的情况下转运费用为40.5150万元。

车辆调度安排计划如下（A-B，7；表示代理点A转运给代理点B七辆车）：2日：A-B，7；B-M，3；E-J，9；G-D，5；H-D，1；H-T，4；I-K，3；J-C，3；J-F，4；J-G，1；N-M，5；O-D，1；P-M，2；Q-T，5；R-D，1；R-。