搜索
12014高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）：我们的参赛报名号为（如果赛区设置报名号的话）：所属学校（请填写完整的全名）：参赛队员(打印并签名)：1.2.3.指导教师或指导教师组负责人(打印并签名)：日期：年月日赛区评阅编号（由赛区组委会评阅前进行编号）：2关于公共自行车系统租赁点选址及车辆调度问题的研究摘要本文主要研究了公共自行车系统租赁点选址及车辆调度问题。合适的租赁点选址能更使居民出行更加便捷，从而解决“最后一公里”问题；而较优的车辆调度方案不但能够节约车辆调度产生的各类成本，还能提高公共自行车的使用率。问题一主要解决的是公共自行车初始分配及调度问题。我们首先解决初始分配问题，在满足题目要求各租赁点的车辆必须大于需求量的110%的基础上，我们对于如何处理剩余未被分配的66辆车进行讨论，最终以三个理由确定了将剩余车辆平均分配到两辆调度车上的方案，由此得到了一个最优的分配方案。接着，结合调度时的约束条件,我们利用整数线性规划的思想，建立了以平均调配时间最小为目标的车辆调度模型，即模型一。（见本文第7页）根据模型求解需要，我们计算各类变量及参数（详见第8页），从而确定各站点需要调入或调出的车辆数目。然后通过遗传模拟退火算法（算法一）求出最短调度时间及其调度路径。由于两辆调度车的调度方式对结果具有一定影响，故还需对其调度方式展开详细讨论。两辆车对租赁点进行调度，无非就两种调度方式。第一种方式是两辆车同向一同驶完30个租赁点，此方式将调度车装卸车的耗时减少了一半；第二种方式是将30个租赁点随机划分为2个含15个租赁点的区域，让每辆车在各自区域内同时进行调度，取耗时最长那辆车的调度时间。为了判断哪种调度方式更优，我们通过计算机仿真模拟第一次调度情境，得出两种调度方式下的调度方案，通过调度耗时大小的比较，最终我们确定了第二种调度方式下的调度方案。从调度的实际情况出发，我们模拟仿真了一天内的所有调度情况，即由最优分配下经3次调度回到原始的最优分配，最终计算得3次调度的平均耗时为（167.64+213.61+193.29）/3=191.51分问题二解决的是公共自行车系统租赁点选址问题。查阅相关文献易知，影响点选址的参数有以下几个：1.租赁点需求量及其地理位置；2.覆盖率；3.建设费用。对此，我们在满足需求量最大及建设费用充分利用的原则下，再次利用线性规划的思想，建立了点选址模型，即模型二（见本文第14页），并求得了新增租赁点数量应在24个左右。然后，我们再将覆盖率因素考虑进来。对各备选点所在区域细分成5×5的25个等面积的小区域，选择各区域内需求量较大的租赁点，调整部分租赁点使得各区域均有一个能较好覆盖该区域的租赁点，从而得到最终的优化选址方案，即增设25个租赁点，需购买X辆自行车，总建设费用为X万。由于问题三是问题一调度问题的推广，因此其模型即为模型一。由问题一的模拟比较分析可知，两辆调度车对30个租赁点的调度耗时均大于150分，因此只需要考虑n≥3的情况，利用改进了的算法二（见附录4）求出n辆调度车对55个租赁点进行调度的耗时T，直至T≤150时结束操作。最终得出n的最小值为4时，能满足题意。关键字：调度问题点选址问题整数线性规划遗传模拟退火算法计算机仿真模拟3一、问题重述公共自行车服务系统是指在某个区域内，隔一定距离规划出一些停放自行车的租赁点，很多的自行车租赁点共同组成一个网络以形成一个服务系统，居民可以在任意租赁点租、还车辆，费用全免。然而目前的公共自行车租赁服务系统建设中容易遇到诸如租赁点选址、自行车供求平衡分配、最高效率自行车调度系统、建设成本费用最小化等疑难问题。本文根据比赛的相关要求，首先对题目进行整合处理，同时综合考虑上述疑难问题，对西安市经开区公共自行车服务系统做最优化的设计。问题整合处理如下：西安市经开区公共自行车服务系统于2011年4月开始建设，到目前为止，已建成租赁点30个，自行车总量达到850辆。目前正在筹备第三期建设。已知条件如下：（1）关于租赁点的设置。有关部门事先根据经开区车辆需求调查、地理位置等实际情况确定了100个位置作为备选租赁点，前期的30个租赁点在其中选出，第三期需要建设一定数目的租赁站点，位置亦在其中选出；（2）由于需求及位置限制，每个租赁点能够放置的车辆数目有限，不能超过40辆；且车辆总数至少应超出需求量的10%；（3）已知这100个租赁点在不同时间段的车辆需求情况。为了简化问题，可将实时观测到的数据，取平均值后归结到3个车辆使用需求最多的时间段；（4）居民可以在任意一个租赁点还车，在某个租赁点还车的概率与租车点和还车点的距离成反比，且假设居民的骑行距离不超过2km；（5）假设调度只在车辆需要最多的时间段进行，经开区目前用于运送公共自行车的调度车有2辆，每辆每次可运50辆自行车，调度车平均时速30km/h，每辆自行车装（或卸）平均耗时1min；（6）假设建设一个租赁服务网点需要50000元，在使用周期内，购买、养护一辆自行车需要1000元。（7）如果租赁点停车率达到上下限，例如小于20%或大于90%，该站点将在系统中显示为红色，并按停放率高低排序，就近对接，实现最短距离、最快捷的车辆调度。本文将研究下列问题。（1）针对已有的30个租赁点，根据目前经开区网点自行车需求情况等信息，设计一个最优车辆分配方案和调度方案，使得调度平均耗时最小化，并求出完成调度所耗费的时间。（2）假设经开区公共自行车服务系统三期建设准备投入建设经费200万元，据此建立数学模型，确定新增租赁点数目、位置以及合适的放置车辆数目。（3）针对问题二，进一步研究，如果要求在150min内完成调度，是否需要增加调度车辆（购置调度车辆费用由其它项目经费解决，不包含在三期建设提供的200万元经费中间）？并给出该情形下的自行车调度方案。4二、模型假设1.两租赁点间距离可以按经纬度计算，且只考虑两点间直线距离，忽略道路规划对两点间距离造成的影响。2.每一天各个租赁点需求量基本相同，一天内需求变化规律也不变；3.调度车始终按照30km/h的平均速度行驶；4.调度车可以在任意自行车站点停放，且可以随时出发完成调度任务。5.居民可以在任意一个租赁点还车，在某个租赁点还车的概率与租车点和还车点的距离成反比，且假设居民的骑行距离不超过2km；三、符号说明,ij:自行车租赁点编号；k:调度车辆的编号；Q:调度车辆的最大载重（自行车数量）；ijl：自行车租赁点i和j之间的距离；ke：调度车辆k被使用，则ke=1，否则=0；ijkx：调度车辆k在结束租赁点i之后再进行租赁点j的调度工作，则1ijkx，否则ijkx=0；C：调度车装（或卸）每辆自行车的平均耗时；ia：调度车在第i个租赁点装（卸）自行车数目；ijp：自行车从租赁点i借出，归还到租赁点j的概率；orrowiB：租赁点i自行车借出数量；Reiturn：租赁点i自行车归还数量；isb：租赁点i在早高峰段前的自行车初始分配量；ky：70个备选自行车租赁点对应降序排列的日平均车辆需求数。四、模型的建立与求解4.1问题一的分析问题一主要解决的是公共自行车初始分配及调度问题。由于租赁点需要调度的原因是各租赁点的初始分配车辆经过借还车后不能满足其后的车辆需求。因此要研究如何调度必须先确定车辆初始分配量。结合调度工作的循环特性，我们选择以每天早高峰段前为起点，研究5其最优分配方案。根据题目要求，在满足早高峰段时需求量的110%的基础上，我们对于剩余未被分配的66辆车进行讨论，最终以三个理由确定了将剩余车辆平均分配到两辆调度车上的方案，由此得到了一个最优的分配方案。接着，考虑车辆调度问题的约束条件，建立以平均调配时间最小为目标的车辆调度模型。根据模型求解需要，计算各站点在各高峰段的初始车辆数、借车量、还车量等参数，从而确定各站点需要调入或调出的车辆数目。然后通过遗传模拟退火算法求出最短调度时间及其调度路径。由于本问存在两辆调度车，还需对其调度方式展开详细讨论。两辆车对租赁点进行调度，无非就两种调度方式。第一种方式是两辆车同向一同驶完30个租赁点，此方式将调度车装卸车的耗时减少了一半；第二种方式是将30个租赁点随机划分为2个含15个租赁点的区域，让每辆车在各自区域内同时进行调度，取耗时最长那辆车的调度时间，此种方式则能减少每辆车经驶站点数从而减少行驶的耗时。为了判断哪种调度方式更优，我们通过模拟第一次调度情境，得出两种调度方式下的调度方案，通过调度耗时大小的比较，最终我们确定了第二种调度方式下的调度方案。4.1.1车辆最优分配方案租赁点需要调度的原因是各租赁点的初始分配车辆经过借还车后不能满足其后的车辆需求。因此，要研究如何调度必须先确定车辆初始分配量。我们规定，每天早高峰段前的车辆数即为车辆初始分配量。根据题意要求“调度只在车辆需要最多的时间段进行”，假设租赁点在早中晚三个时间段中均存在车辆供求不足的情况，并考虑到整个调度系统的完整循环，我们需要对每天早中晚时间段之前及当天晚间段之后分别进行共4次车辆调度以满足各时间段的需求量。但如果我们使初始车辆分配量满足了每天早高峰段的需求量，则只需进行3次车辆调度，由此我们得到一个优化的分配方案。通过题目的相关要求及深入分析，最终我们得到一个车辆最优分配方案。具体步骤如下。首先在满足各站点早高峰需求的量基础上，结合题目“通常车辆总数至少应超出需求量的10%”要求（所得小数应向上取整），我们提出第一个分配方案Ⅰ，即初始分配量=各站点早高峰段需求量×110%然而由于每个租赁点最多只有40个停车桩，部分站点出现分配数超过最大停放数的情况，对此我们利用EXCEL对不合理的站点进行调整，统一调整为40辆，得到调整后的分配6方案Ⅱ。由于方案Ⅱ，只分配了784辆自行车，因此需要考虑如何处理剩下的850-784=66辆车。对于剩下的车辆的处理方式无非就两种，第一种是寻找合适理由继续分配，第二种是将剩余车辆平均分配到两辆调度车中，以便后期调度试用。通过计算及分析，最终我们决定采取第二种处理方式，原因有以下几点：（1）调度车在有车的情况下更容易进行车辆调度，从而简化了调度过程；（2）车上自行车数越多越有利于就近装卸车，从而使可行的最短路径最小化；（3）没有找到继续分配的合适理由。由此，我们得到了基于方案Ⅱ下，将剩余车辆平均分配到调度车上的方案Ⅲ，即为最优分配方案。见表4.1。表4.1前30个站点的车辆最优分配方案站点编号12345678910初始分配17264040193615402920站点编号11121314151617181920初始分配2039814401924263126站点编号21222324252627282930初始分配17391738242639201520注：剩余66辆车平均分配到两辆调度车上。4.1.2车辆最优调度方案1.模型的建立假设用有向图G=（A,E）表示公共自行车车辆调配网络，A=｛1,2,…,n｝表示租赁点的集合，随机取一租赁点当作调度中心，E｛(i,j)丨i,jA,i≠j｝表示相连租赁点的边集，K=｛0,1,2,…,m｝，m表示调度车的数量，Q为调度车的装载自行车的最大容量，id为租赁点i的需要调配量，表示从租赁点i到租赁点j的直线距离，C表示装卸每单位自行车的时间耗时，ia表示调度车在第i个租赁点装（卸）自行车数目，jkr（1j,n,1≤k≤m）表示即将对租赁点j进行调配的调度车k的当前载自行车数量，并且定义决策变量如下：ij