校园共享单车停放点布局及调度问题

西南大学电子信息工程学院课程论文考试科目数学建模教师学年20162017学期2年级专业2015级电子信息工程学号姓名成绩电子信息工程学院制队员1姓名学号班级联系电话队员2姓名学号班级联系电话队员3姓名学号班级联系电话指导老师校园共享单车停放点布局及调度问题摘要目前，共享单车已经成为我国的一大热点，如何通过建立数学模型来解决共享单车的停放点的布局以及如何调度共享单车，有重要的商业价值和研究意义。本文通过建立数学模型，以平均停放点间距为指标成功解决了这两个问题。针对问题一，我们提出了一种设立停放点的方法方格法。在本方法中，先确定中心点，然后以平均站间距为间距画出等大的一些方格，并在每个方格内布设一个停放点。同时我们在方格内还定义了几类主要吸引点，以备选点和方格内各吸引点的距离为指标，运用了层次分析法来确定各吸引点类型的权重，最后使用备选点重要度的计算公式，从而来确定停放点。针对问题二，我们首先根据行业标准以及西南大学校内调查的实际情况求出西南大学需要多少辆共享单车，多少单车维修人员，再根据停放点建立TSP问题模型，最后使用遗传算法求解。关键词共享单车，调度，停放点，TSP问题1问题重述11问题背景“小黄”共享单车就像一股阳光清新的风，吹进山城重庆，也吹进了高校校园。目前，西南大学已有2000多辆“共享单车”投入使用，所以同学们对这种单车并不陌生手机扫描车上二维码，进入共享单车平台；输入车牌号，解开密码锁，在平台支付99元的租车押金就可以把小黄车骑走了，享受“一公里”的短途出行。校园共享单车自由度高，价格低廉，方便了学校师生最后1公里的出行。有数据显示，截止2017年4月，中国共享单车行业共计融资90至100亿元人民币。另有人推算，至2020年，中国共享单车行业市场营收规模，每年最高可以达到900至1000亿元人民币。不过，扣除生产成本、盗窃失踪、运营维护、保养改进、市场推广、企业运营成本、补贴获新，车辆三年报废，以及潜在政策管理风险，现有商业模式来看，单车收益率几乎为负，仍面临极大挑战。12问题描述1）共享单车停放点布局针对西南大学共享单车的情况，给出维修总站、大、中、小三类停放点的布局。2）共享单车的优化调度西南大学需要多少辆共享单车，多少单车维修人员和车辆调度人员，几辆调度运送车（每辆最多运载20辆），如何进行调度，才能使得成本最少。2问题分析21问题一分析问题一要求针对西大校园内的情况给出维修总站以及大中小三类停放点的布局。我们首先建立站间距模型，计算出西南大学校内共享单车停放点合理的站间距，再根据站间距将西大地图画出一些等大的方格，同时建立六类吸引点，运用桑蒂（SANTY）标度法对不同吸引点的权重进行标度，最后通过层次分析法，分析几个备选点，得出最佳备选点。22问题二分析问题二要求西南大学需要多少辆共享单车，多少单车维修人员和车辆调度人员，几辆调度运送车（每辆最多运载20辆），如何进行调度，才能使得成本最少。我们首先根据行业标准以及西南大学校内调查的实际情况求出西南大学需要多少辆共享单车，多少单车维修人员，再根据停放点建立TSP问题模型，最后使用遗传算法求解。3模型假设与符号系统31模型假设1西南大学校内每个宿舍居住的学生几乎一样多；2西南大学校内每栋教学楼每天上课的学生几乎一样多；3自行车在行驶过程中是完全匀速行驶的，不考虑上下坡对车速的影响；4西南大学校内没有非本校人员居住的居民楼；5西南大学校内任意两个位置的非直线系数相同；7使用者到达和离开共享单车停放点是采用步行的方式；8西南大学校内站间距为平均站间距且相等。32符号系统符号意义单位共享单车使用者的总效益Q共享单车需求量T使用者选择共享单车的临界时间值T使用者使用共享单车总的出行时间秒C使用者使用共享单车的平均时间价值T1使用者步行到达最近共享单车停放点的时间秒T2使用者借车花费的时间秒T3使用者使用共享单车到达目标停放点的时间秒T4使用者还车花费的时间秒T5使用者步行离开共享单车停放点的时间秒T6骑行过程中的延误时间秒D共享单车停放点平均站间距千米道路非直线系数1共享单车的骑行速度千米每小时2人的步行速度千米每小时借使用者解锁租借共享单车的时间秒还使用者归还共享单车的时间秒L平均骑行距离千米共享单车在十字路口被延误的概率N区域内十字路口的个数个C十字路口高峰期的平均周期秒G高峰期内平均可通行时间秒备选点的重要度A吸引点与备选点之间的距离A千米I类备选点的权重4问题一的模型建立与求解41模型的建立411站间距模型本文主要从使用者效益方面及成本建立站间距模型。从使用者的角度出发，站间距越小，使用者步行到达共享单车停放点的距离就越短，出行更加方便，用一个区域的共享单车使用者的总效益类比一条公交线路一天的乘客总效益，那么在一个区域内所有共享单车停放点一天内使用者的总效益为E2接下来分析使用者使用共享单车总的出行时间T，从使用者的角度出发使用者使用共享单车的总的出行时间应当最小，使用者使用共享单车的时间又分为步行到站时间、借车时间、骑行时间、还车时间和步行离站时间，即MINMIN1234561T1的计算使用者从交通源步行到达最近的共享单车停放点的平均距离为两个停放点之间步行距离的一半，任意两停放点之间的平均步行距离为共享单车平均站间距与道路非直线系数的乘积，使用者步行的速度为（取3公里每小时）。那么使用者步行到达最2近共享单车停放点的时间T1222T2的计算2借使用者使用手机扫描共享单车二维码，确认借车后，用户即可使用密码解锁自行车完成租车。解锁以及扫码过程需要消耗一定的时间，因此根据调查结果以及各地租借的情况将取值为60秒。借3T3的计算使用者骑行到达目标停放点的时间为31式中L按照重庆市共享单车的使用情况来看，平均行驶距离为12千米，因此取2千米；自行车的速度取平均15千米每小时。14T4的计算4Q还式中T还取值与相同，为60秒。借5T5的计算在理想的条件下，使用者步行离开共享单车停放点的时间与步行到达共享单车停放点的时间相同，即516T6的计算共享单车在道路上行驶时肯定要受到十字路口拥堵的影响，因此在计算使用者行程时间的时候也必须考虑拥堵所带来的延误时间，拥堵的延误时间为6C式中共享单车被十字路口拥堵延误的概率，G则区域内所有使用者使用共享单车总的出行时间为2借还12运营企业的效益E式中共享单车运营企业的总效益（元）；E使用者的单位费用成本（元）；共享单车运营企业的成本（元）。1）使用者的单位费用成本CPX式中共享单车每小时价格（元）；X共享单车平均租赁时间。2）共享单车运营企业的成本CO共享单车运营企业的运营成本由两大部分组成，为车辆的运行成本和服务网点所需的人工费，即122式中车辆的运行成本（元）；1运营的人工成本（元）；2车辆的折旧系数；每个停放点的人工费用，每个管理人员管理8个停放点，根据每个人月薪2400元/月计算，每个停放点每天的人工成本为10元/天；N区域内共享单车停放点的个数；区域的面积（KM2）；D平均站间距（KM）。因此，2此模型需要附加一下限制条件。使用者最大可容忍的步行距离如果使用者步行到达共享单车停放点的距离超过了他能忍受的最大步行距离，使用者就会放弃使用共享单车出行，取使用者能容忍的步行时间为6分钟，按步行速度为5千米每小时来计算，使用者能容忍的步行距离D为500米，则D2共享单车停放点最小站间距限制条件从使用者的角度出发，站间距越小，使用者步行至最近共享单车停放点的时间与距离就越小，但从运营企业的角度考虑站间距过短会增加站点的建设费用，因此必须有一个最小站间距。从国内外共享单车的应用现状来看，巴黎的共享单车停放点设置的最小站间距为150M，考虑到中国的实际情况，因此设置的最小站间距取值为200M。综上所述，可建立如下站间距模型MAX122借还112021222200412方格法布局模型在一个区域内首先确定一点，这个停放点大致位于区域的形心，且该停放点应当是非常有必要设置的停放点将其同时作为维修总站。以中心点为中心，画DD的网格（D为411计算得出的平均站间距），如下图41所示图41方格法中心点每个格子内只能设立一个自行车停放点，但位置不受限制。用这种方法来布设自行车停放点，可以使得区域内共享单车停放点均匀的分布在该区域内，并且平均站间距为合理站间距。接下来描述如何在每个网格内选择停放点的最佳位置。在的网格内，建立一个直角坐标系，在网格内将出行吸引点的位置用坐标表示DD出来。吸引点的类型主要包括学生公寓（P1）、教学楼（P2）、行政楼（P3）、图书馆（P4）、景点（P5）、食堂（P6）。如小区域内有多个同类型吸引点，那么第J个I类吸引点的坐标表示为。共,享单车主要利用人行道、广场、社区的空地进行布置，因此在一个小区域内可供布设点的位置相对比较有限。如果在小区域内有一个吸引点，通常应该将停放点布设于吸引点的100M范围内，如果小区域内有2个吸引点，那么停放点应尽量布设于2个吸引点中间，若超过2个吸引点，那么停放点布设的位置应尽量考虑所有的吸引点以便方便该小区域内使用者的使用共享单车。如图42所示图42各吸引点直角坐标系示意图图中是一个的小方格区域，以方格的左下角为O点建立直角坐标系，在小区域DD内所有类型的吸引点都有，在交叉口的四周有四个地铁出入口，有两个公交站点，一个居民点，一个公建点，一个校园点和一个景点，区域内有两条垂直交叉的道路，相当于与两条直线，通常共享单车停放点是布设在道路旁的人行道上的，因此图中黑色的YB区域是可以布设自行车停放点的区域。在道路上有若干个可供布设共享单车停放点的备选点，停放点的位置应当兼顾小区域内所有吸引点，乘客从各个吸引点步行至停放点的距离总和应当最小，距离总和小说明备选点的重要度最大，距离总和大说明备选点的重要度小。如果将该区域内每一个备选站点与所有吸引点的距离简单相加虽然可反映总的距离之和，但是在选择停放点位置时对与某些吸引点的距离应当优先考虑，如学生宿舍点应当优先于行政楼进行考虑，因此对不同的吸引点给以相应的权重可以更科学的反应在选择停放点时各吸引点的优先程度。现定义备选点的重要度如下公式区域内同一类型的吸引点可能有若干个，因此J表示区域内同一类型停放点的数量，将备选点与同一类型的所有吸引点（如，表示所有的学生宿舍）的距离求算术平均1值，即为备选点与该类型吸引点的距离值。通过该式计算选取数值最高的备选点作为该小区域内的停放点位置。42模型的求解421运动层次分析法确定运用层次分析法需要经过3个步骤（1）建立层次结构模型（2）构造判断（成对比较）矩阵（3）一致性检验1建立层次结构模型层次结构模型可分为目标层、准则层和方案层3个层次。在本文中，一个小区域内共享单车停放点的具体位置的确定综合考虑与学生宿舍、教学楼、食堂、图书馆、行政楼和景点的距离，因此层次结构模型如下图43所示。2构造判断矩阵在确定不同层次的因素的权重时，单纯的定性结果往往不能被认可，因此桑蒂（SANTY）等人提出了一致矩阵法，即1）将每两个不同的因素进行比较。2）为了降低不同性质的各种因素两两比较的难度，提高对比的准确度，在进行两者比较时使用相对的尺度。判断矩阵是表示本层所有元素针对上一层某一个相对重要性的比较。心理学家认为每层不要超过9个因素46。判断矩阵的元素AIJ用桑蒂（SANTY）的19标度方法给出。如下表所示设要比较各准则,对目标O的重要性，12,3456，则A,0,1A13557313133511513113131513113131715131311513133513一致性检验要由A确定,对O的权向量，由于评价者根据主观对两个元素进12,3456行比较得到判断矩阵，导致矩阵出现不一致的情况，虽然允许不一致的情况出现，但是要使不一致在一定的允许范围内，因此需要对判断矩阵进行修正。首先计算将矩阵的列向量归一化，然后求行和归一化，得出归一化后的W，由AWW可计算得出。检验一致性一致性比率，若，则可通过一致性检验，否则需要对CRCRRANDELSEWFLOORL/108ENDPUNIDRNDLW1FPRINTFPD,PFORI1WXFINDAB1,PI1YFINDBA1,PI1A1,PI1,B1,PI1EXCHANGEA1,PI1,B1,PI1A1,X,B1,YEXCHANGEA1,X,B1,YENDEND4对调函数EXCHANGEMFUNCTIONX,YEXCHANGEX,YTEMPXXYYTEMPEND5变异函数MUTATIONMFUNCTIONAMUTATIONAINDEX10INDEX20NNPERRANDPERMSIZEA,2INDEX1NNPER1INDEX2NNPER2FPRINTFINDEX1D,INDEX1FPRINTFINDEX2D,INDEX2TEMP0TEMPAINDEX1AINDEX1AINDEX2AINDEX2TEMPAAEND6连点画图函数PLOT_ROUTEMFUNCTIONPLOT_ROUTEA,RSCATTERA,1,A,2,RXHOLDONPLOTAR1,1,ARLENGTHR,1,AR1,2,ARLENGTHR,2HOLDONFORI2LENGTHRX0ARI1,1Y0ARI1,2X1ARI,1Y1ARI,2XXX0,X1YYY0,Y1PLOTXX,YYHOLDONENDEND7主函数CLEARCLCN50城市的个数M100种群的个数C100迭代次数C_OLDCM2适应值归一化淘汰加速指数PC04交叉概率PMUTATION02变异概率生成城市的坐标POSRANDNN,2生成城市之间距离矩阵DZEROSN,NFORI1NFORJI1NDISPOSI,1POSJ,12POSI,2POSJ,22DI,JDIS05DJ,IDI,JENDEND生成初始群体POPMZEROSM,NFORI1MPOPMI,RANDPERMNEND随机选择一个种群RPOPM1,FIGURE1SCATTERPOS,1,POS,2,RXAXIS3333FIGURE2PLOT_ROUTEPOS,R画出种群各城市之间的连线AXIS3333初始化种群及其适应函数FITNESSZEROSM,1LENZEROSM,1FORI1MLENI,1MYLENGTHD,POPMI,ENDMAXLENMAXLENMINLENMINLENFITNESSFITLEN,M,MAXLEN,MINLENRRFINDLENMINLENRPOPMRR1,1,FORI1NFPRINTFD,RIENDFPRINTFNFITNESSFITNESS/SUMFITNESSDISTANCE_MINZEROSC1,1各次迭代的最小的种群的距离WHILEC0FPRINTF迭代第D次N,C选择操作N