毕业设计（论文）-自行车服务系统的分配方案和调度问题.doc

装 订 线摘 要针对自行车服务系统的分配方案和调度问题，本文进行了深入的研究，最终以0-1整数规划模型、马氏链模型、模型以及模型为主，自己编程为辅，通过精确的计算，准确的实现了对自行车服务系统的设计与研究。1.2.对问题一，已知租赁点的最优车辆分配和调度方案设计问题。直接利用经纬度计算出30个租赁网点间的最短距离矩阵。 建立0-1整数规划模型和旅行商模型计算出2辆调度车的最优调度路径。再通过分析马氏链模型近一步预测出各站点还车概率，精确确定各租赁点调度车辆的数目。最后，通过LINGO求解出最优车辆分配方案和最短时间调度路线。并给出30个租赁站点的最短调度时间123.3562；对于问题二，在已知建设投入经费的前提下，确定新增租赁点数目、位置以及合适的放置车辆数目。主要考虑最优车辆分配，建立0-1规划模型，以市民最大的需求量为目标函数，在分配初始条件、成本、租赁站点最短距离以及需求性等条件的限制下对新加入的70个站点进行筛选，最终确定新增25个租赁点以及相应的自行车分配量；对于问题三，以建立模型为主，将两个目标函数调度车总路程最短和调度用车访问租赁站点数之差最小化合成为单目标规划问题，求解出4辆调度车的最优方案。并给出最短用时为136.0122min；对于问题四，在一定的条件下所需的动态的车辆调度方案。实时监测出的第个站点停车数量，通过位于20%90%范围外判断被调度条件。随后对该站点周边站点建立最短距离序列，依照距离最小原则，判断符合调度条件的最近站点，并使调度后两站点停车率满足正常值。关键词：0-1整数规划模型 TSP模型 MTSP模型 马氏链模型 动态车辆调度 单目标规划问题 距离最小原则目录摘要 0一、 问题重申：2二、 问题的基本假设与说明: 3三、 符号说明：四、 模型的建立和求解： 4.1.问题1：4.1.1 模型建立:4.1.2 模型求解: 4.2.问题2：4.2.1 模型建立:4.2.2 模型求解:4.3.问题3：4.3.1 模型建立:4.3.2 模型求解:五、 模型的优缺点评价： 六、 模型的优化与推广:七、 参考文献：附页：一、 问题重申：近年来，随着经济的发展，我国各级城市的机动车保有量都进入了持续高速增长时期，但由此所引发的道路拥堵、空气污染也引起了政府以及百姓的极大关注。众所周知，建立快速、便捷的城市公共交通体系是解决这一问题的有效手段之一。然而，居民居住地和交通站点通常都有一段距离，这段不远的距离以及现实存在的公共交通拥挤现象则使居民乘坐公共交通的意愿降低，公共自行车服务系统已被证明能够从一定程度上缓解这一现象。公共自行车服务系统是指在某个区域内，隔一定距离规划出一些停放自行车的租赁点（如地铁出口、城市中心等人员密集的地方），一个租赁点放置一定数量的自行车，很多的自行车租赁点共同组成一个网络以形成一个服务系统，居民可以在任意租赁点租、还车辆，费用全免（某些城市收取少量的超时费用，但目的只是用来提高自行点的自行车短缺或堆积现象发生，将通过调度专用车进行合理调度，以最大程度地满足车的利用率，不以盈利为目的），根据租赁点自行车的使用频率，避免部分租赁居民对车辆需求，提高车辆利用率（系统有自动报警功能。如果租赁点停车率达到上下限，例如小于20%或大于90%，该站点将在系统中显示为红色，并按停放率高低排序，就近对接，实现最短距离、最快捷的车辆调度）。公共自行车租赁服务系统纳入城市公共交通体系，有助于解决公交出行“最后一公里”问题，使公共交通服务网络趋于更加完善。目前，北京、上海、深圳、济南、郑州、武汉、无锡、佛山、西安等全国30多个大中城市正在逐步建设公共自行车租赁服务系统，它是国内新兴起的一个行业。西安市经开区公共自行车服务系统于2011年4月开始建设，到目前为止，已建成租赁点30个（附件1），自行车总量达到850辆。目前正在筹备第三期建设，请你根据以下信息（1）租赁点设置。租赁点通常设在地铁出口、城市中心等人员密集的地方，根据经开区车辆需求调查、地理位置等实际情况，有关部门事先确定了100个位置作为备选租赁点，前期的30个租赁点在其中选出，第三期需要建设一定数目的租赁站点，位置亦在其中选出；（2）由于需求及位置限制，每个租赁点能够放置的车辆数目有限，不能超过40辆；为了更好满足居民对车辆的租赁要求、简化调度、提高车辆使用率，通常车辆总数至少应超出需求量的10%；（3）附件2列出了各个租赁点（或备选租赁点）在不同时间段的车辆需求情况。为了简化问题，附件2将实时观测到的数据归结到3个车辆使用需求最多的时间段，并进行了平均（可以认为每天的需求量不变）；（4）居民可以在任意一个租赁点还车，在某个租赁点还车的概率与租车点和还车点的距离成反比，且假设居民的骑行距离不超过2km；（5）假设车辆调度只在附件2中车辆需要最多的时间段进行，经开区目前用于运送公共自行车的调度车有2辆，每辆每次可运50辆自行车，调度车平均时速30km/h，每辆自行车装（或卸）平均耗时1min；（6）假设建设一个租赁服务网点需要50000元，在使用周期内，购买、养护一辆自行车需要1000元。完成如下问题（1） 根据目前经开区网点自行车需求情况等信息，若要求调度平均耗时尽量少，请针对已有的30个租赁点设计最优车辆分配方案、调度方案，并给出完成调度所耗费的时间。（2）假设经开区公共自行车服务系统三期建设准备投入建设经费200万元，据此建立数学模型，确定新增租赁点数目、位置以及合适的放置车辆数目。（3）针对问题（2），进一步研究，如果要求在150min内完成调度，是否需要增加调度车辆（购置调度车辆费用由其它项目经费解决，不包含在三期建设提供的200万元经费中间）？并给出该情形下的自行车调度方案。2、 问题的基本假设与说明：2.1、假设题目所给的数据全部真实可靠；2.2、考虑到时刻安排表的问题，觉得以分钟作为最小的时间单位是相对比较合理的；2.3、假设在整个过程中，公民必须将自行车及时归还，以保证自行车无丢失；2.4、假设调度车运行正常，速度恒定为0.5km/min，且无特殊事件发生（如交通拥挤等）；2.5、在本题所有的计算中，将道路的转弯处看成直角弯，并忽略马路宽度以及具体交通规则对整个系统的影响；2.6、假设任意站点都可作为调度车的起点或终点。3、 符号说明： 3.1 符号系统符号名称符号意义量纲/单位任意两个租赁站点之间的最短距离调度过程的决策变量1排出子巡回的累加变量1最优分配方案下个租赁站点的自行车分配数目辆租赁站点在当天第个用车高峰期的自行车需求量辆 市民在第租赁网点借自行车，使用完毕后在第租赁网点处归还概率1经过一次借还后租赁站点剩余自行车数目辆第次用车高峰后最优调度路线长度最短调度时间min在处建立租赁站点的决策变量1第辆调度车经过租赁点的决策变量1辆调度用车访问的租赁站点数个西安市所有租赁站点自行车最大需求辆调度车的总数目辆第个站点某时间的停车数量辆表示在点之间调度自行车的数量辆四、模型的建立与求解：4.1 问题1，租赁点优化建设问题： 4.1.1 模型的建立： 求解租赁网点间最短距离矩阵： 租赁网点间自行车的调度需要按照最短距离完成，以缩短调度时 间。据此，结合30个租赁网点的经纬度关系，在假设道路宽度为零的前提下，通过长度换算求出30个租赁网点两两之间的最短距离矩阵 其中为车辆变化预测矩阵，在计算中若两租赁网点的距离大于2km，则将其表示为无穷大（即假设居民的骑行距离不超过2km，公民在这两个租赁网点间借还车概率为0）。为调度时间分析矩阵，求解时以各个租赁网点间实际计算距离为准。由于地球子午线长度39940.67千米，纬度一分合1.849千米，不同纬度之间的间距是一样的。地球赤道圈长度40075.36千米，因此经度一分的距离需通过纬度的位置来计算。由经纬度求最短距离方法如下：经度距离： 纬度距离： 最短距离： 其中，为租赁网点的经度值，为租赁网点的纬度值。1.2.3.4.5.5.1.5.1.1.引入0-1整数变量 则TSP模型可表示为： 其中由调度时间分析矩阵中取得 若仅考虑前三个约束条件，对TSP模型只是必要条件，并不充分，因此增加“不含子巡回”的约束条件，通过增加变量，并附加约束条件来实现： 从而可以得到覆盖30个租赁站点的最短距离调度路径如下： 30个租赁站点的最短距离调度路径图路线长度（/km）调度路线 30个租赁站点的最短距离调度路径表由马氏链模型预测一次借还后租赁点剩余车辆：已知30个租赁网点，现以第一个用车高峰期各租赁网点车辆分配方案作为初始情况进行分析。假设初始时每个租赁网点需求量为辆，实际供给辆，则初始条件满足： （5-9）（若，则）然后分析本系统与马氏链模型的联系。针对马氏链模型的基本原理：根据大量的统计数据来建立转移矩阵，由初始状态向量预测未来任意时刻系统发生各种状态的概率，从而采取相应的对策。建立马氏链模型是以下列假设为前提的：1) 转移矩阵不随时间变化而变化；2) 预测期内状态数量不变；3) 系统变化过程具有后无效性。我们知道，居民可以在任意一个租赁点还车，且在某个租赁点还车的概率与租车点和还车点的距离成反比，因此我们可以得到一个转移矩阵，而且它是有一定的规律的，因为市民的出行是有目的性的；同时为了更好地得到预测结果，在预测期内租赁站点的数目恒为30个；最后，市民在租借自行车之后在哪里归还只与归还前的租借状态有关，而与以后的状态无关，这就是所谓的系统状态无后效性。通过上述分析，可见我们研究的系统满足马氏链模型的前提条件。具体流程：（1）、建立状态转移矩阵P通过 其中A为待定常量，通过计算确定；其中由车辆变化预测矩阵中取得，若市民骑行距离不超过则他需要在点还车，即满足： 从而建立状态转移矩阵为： 式中，代表市民在第租赁网点借自行车，使用完毕后在第租赁网点处归还的概率。已知城市公共自行车租赁系统满足前面三个假定，因此由马氏链模型的结论，经过若干阶段以后，各状态发生的概率趋于稳定，也就是说把归还的车辆按照所代表的比重进行预测。则经过一次借还后租赁点剩余车辆数目为： 最小调度总车辆的预测：假设最优车辆分配以满足日首次高峰，且经过最后一次用车高峰后只需调度至满足首次名车高峰数目即可，不必还原为初始状态。现考虑在满足一天内三次用车高峰的调度使用下最小调度车辆的数目。建立如下模型： 其中，假设三次高峰期和经过最后一次调度后这四个时期各站点的供给车辆数目为则每个站点每次调度的车辆数目为 通过LINGO编程，求解出在一天内各租赁站点三次调度自行车数目总和，由这个数值可以看出，由于有一些站点不需要进行自行车的调度问题，因此回归到上面中，再一步对30个站点调度路径进行再次优化，可以得到优化后一天内三次调度路径情况如下表：调度次数路线长度（/km）调度路线123 日三次调度车行驶路径表 4.1.2、问题一求解由上述分析知：调度车辆行驶时间为 调度车辆装卸时间为： 假设两辆调度车从某站点分头行驶完最优调度路径，则每辆调度车在一次调度过程中最短用时： 解得则最优分配方案如下表格所示：编号 网点位置自行车最优分配数目1经发大厦172可口可乐北门403经发国际会馆404昆仑银行405赛高街区196西安中学西门367运动公园东门308运动公园南门409管委会2910出口加工区广场2011鼎新花园2012西安外国语学校4013雅荷花园814御道华城1415天地时代广场4016市图书馆1917文景观园2418长庆电视台4019移动公司3120凤城五路2621凤城六路2722中登家园北门3923万华园1724粤华凤城家园3825市人大2426市委2627政务大厅4028首创国际城2429中登广场1530运动公园北门274.2 问题2：新增租赁点设施决策问题 4.2.1 模型的建立：现在已知70个备选租赁点，其中一些作为第三期新增加的自行车租赁站点。我们考虑三期工程选点的因素：（1）、考虑出行因素，规划布局结合公共设施，以方便市民为主要目的；（2）、整个区域公共自行车租赁站点的密度应控制在合理范围内；基于此，建立新增租赁点决策的0-1模型如下：目标函数： 限制条件： 下面具体描述该0-1规划模型：引入决策变量，则 其中，表示可以建立的备选租赁站点。为该租赁站点一天内三次用车高峰的需求量，则自行车分配应满足第一次用车高峰的需求，即： 租赁站点的建设应该控制在预计成本之内，即 同时，假设自行车无丢失，则保证在各个调度过程中，租赁系统中自行车的总量不发生变化，即： 除此之外，还应考虑站点建设的密度性问题，以合理扩大租赁系统覆盖范围，结合巴黎时自行车租赁系统的设置原则，将租赁站最短距离设为200m，结合西安市情况，我们假设任意两个租赁站的最短距离不小于300m，从而简化计算，即： 最后，联系到新增租赁站点应以满足最大市民需求量为目的，因此有建设完成后西安市所有租赁站点达到最大需求： 4.2.2、问题二求解 计算结果如下所示：具体新增加的自行车租赁站点为31,33,34等25个站点，其对应的自行车最优分配方案如下表所示：站点序号自行车分配方案站点序号自行车分配方案3140694033107232342073244137762145367740461480204732812949408434504087155640883060409031621391406331 新增加的自行车租赁站点及其自行车分配方案表然后通过找出70个点中以每个点为圆心，半径为2km的圆，得到该点覆盖区域内所包含的待定租赁点的点集列：在中确定单日需求量（以三个高峰期的平均值代替单日需求量）最大的点如下表所示：租赁站点3101827475056607277出现次数27158312161918 每个站点2km范围内需求量最大的站点及其出现次数 经过比较发现，这些点较符合模型的条件，有着一定的合理性。4.3 问题3：均分MTSP模型的新增调度车辆问题 4.3.1 模型的建立 任务均分的多旅行商问题多旅行商回路（MTSP）是旅行商（TSP）的拓展，而任务均分的MTSP问题实际上是一个多目标的规划问题，针对自行车租赁系统，目标函数有两个：一个是使辆调度车所走的总路程最短；二是满足辆调度用车的访问的租赁站点数之差最小化。 假设为第辆调度用车访问的站点数，则均分访问租赁站点的MTSP模型如下： 约束条件： 下面具体描述该模型：引入决策变量，则 其中，作为调度车的标记，。由上一问知现有55个自行车租赁点，假设各调度车负责的调度范围不交叉，且某站点作为所有调度车的起点和终点。即满足除起点外每个租赁站点仅被访问一次： 若每辆调度用车访问的租赁站点数为，即： 且各调度车任务总和满足： 第辆调度车完成调度的用时，假设调度车位于租赁站点时下一站点为，则： 即目标函数1： 同时满足辆调度用车的访问的租赁站点数之差最小化：即目标函数2： 将目标函数1和目标函数2合成一个总目标函数为 这样一方面，总目标函数与总行程成正比，故总行程最小则目标函数也越小。另一方面，总目标函数与最大访问点数与最小访问点数之差成正线性相关，即越小，总目标函数越小。总之，当总目标最小时，两个目标函数都能取得最小值，即总目标函数既能使总行程达到最小，同时也能达到平均分配辆调度车的访问点数的目的。4.3.2、问题三求解使用MATLAB中编程求解得到，即共需要新增加2辆调度车。且4辆调度车具体分工如下表：调度车序号路线长度（/km）调度路线1234 4辆调度车最短调度路线由上述分析，假设以4辆调度车中最长的行驶时间和装卸时间计算调度过程中最短用时，知为最大调度车辆行驶时间为： 四辆调度车辆中最大的装卸量为： 则完成一次调度用时为： 解得4.4、问题四分析：实时调度的车辆上下限动态调整问题4.4.1、建立模型目标函数：限制条件： 其中表示第站点某时间的停车数量下面对该模型进行具体分析：表示第站点某时间的停车数量，当或者时调度站点指示变红，从而满足调度条件。随后对该站点周围其他站点建立最短距离序列，依照距离由小至大序列依次进行计算，判断是否符合条件，如果符合则进行调度，否则选取该站点进行自行车调度，且停止下一步判断。在完成调度之后需要满足点对点连线的两个点的停车率满足正常值，位于20%90%之间。4.4.2、模型的模拟计算： 在MATLAB的应用文件中，随即对55个站点分配若干个自行车数，要求自行车数不能大于40辆，经过验证，发现该算法具有一定的可行性，应该可以实现车辆上下线动态调整问题。五、模型的优缺点评价 模型的优点（1）、问题一中，将多点分配及遍历问题转化为经典的TSP问题，引入0-1整数规划模型求出最优的自行车分配方案，更加方便的求解出了实际问题中所需要的最优解；（2）、在问题二中通过定义任意两租赁站点距离应不小于300m，控制租赁站点建设的密度性，使租赁系统的建立更加合理；（3）、在第二问中，构造区域点集A并得到每个区域中点集中单日平均需求量最大的点，并与第二问模型的解进行比较，使选取的点更具有可信性；（4）、在第三问中，通过引入MTSP模型，并利用修改后的0-1模型将多目标问题化为单目标规划问题，使调度车数量选取最优。模型的缺点（1） 、虽然能得到全局最优的结果，但是程序运行时间较长，算法效率不高有待改进；（2） 、在整个计算过程中，虽然准确的计算出了结果，但并不是最优的方案，在所需模型上有待提高；（3） 、在问题四中，最后只能大概的做出一个结果，但不是可以完全肯定，在这儿还是存在比较多的问题，有待提高。六、模型的推广与优化 模型的推广： 像这种选址问题的研究内容十分广泛，从城市、产业带、经济技术开发区、跨国经济集团分公司到机场、水利设施、人类居住区、销售网点以及仓库、配送中心等的区位决策都是选址问题研究的范畴，涉及经济、政治、社会、管理、心理及工程地质等多门学科。设施选址是众多选址问题的一个重要研究领域。所研究的设施是指与生产、商业流通及人类生活有关的用地规模相对较小的具体网点、场所，如工厂、仓库、消防站、变电站、污水处理中心，加油(气)站等。研究方法主要依靠运筹学、拓扑学、管理学等计量方法。 模型的优化：在本题中，主要应用了0-1整数规划模型、马氏链模型、模型以及模型，虽然说比较精确的计算出了结果，但是耗时太多是一个重要的有待解决的问题，在模型的优化方面，应该主要把精力放在解决程序运行时间上，这样的话，更有利于让我们达到事半功倍的效果。七、参考文献1 孙永征，李望，刘亮.零售业连锁网点选址与布局演化模型，2009.2 袁新生，邵大宏，郁时炼.LINGO和Excel在数学建模中的应用M.科学出版社，2007.3 卢厚青，王辉东，黄杰，李波.任务均分的多旅行商问题,2005. 附件1、求每个站点还车概率%c为邻接矩阵；%d为概率；for i=1:1:55 for j=1:1:55 if i=j c(i,j)=3; end if a(i)c(j,i) a(i)=c(j,i); end end c(i,i)=a(i)*2; if c(i,i)2 c(i,i)=+inf; end end for k=1:1:55 for g=1:1:55 if c(g,k)2 b(k)=b(k)+1/c(g,k); end end b(k)=1/b(k); end for x=1:1:55 for y=1:1:55 d(x,y)=b(x)/c(x,y); end End2、TSP模型求解MODEL: SETS: city/1.12/:u; link (city,city): dist, X; ENDSETSDATA: dist=!邻接矩阵；;ENDDATAn=SIZE(city); MIN=SUM(link: dist*X);FOR(city(K): SUM(city(I) |I#NE# K: x(I,K)=1; SUM(city (J)|J#NE#K:x(K,J)=l;);FOR(city (I): FOR(city (J) |J#GT#1 #AND# I#NE# J: u (I)-u(J) +n*x (I,J)=n-1);); FOR(city (I): u(I)=n-1); FOR(link:BIN(x); END1.2.3. 求新增加站点SETS: SITE/1.100/:A,C,n1,n2,n3; ENDSETSDATA:n1=!早晨需求量的1.1倍；n2=!中午需求量的1.1倍；n3=!下午需求量的1.1倍；ENDDATAMAX=SUM(SITE:A*n1/3.3+A*n2/3.3+A*n3/3.3); FOR(SITE:BIN(A); for(SITE(I):gin(C(I); FOR(SITE(I)|I#LT#31: A(I)=1); FOR(SITE(I)|I#LT#31:C(I)=0); FOR(SITE(I)|I#GT#30:C(I)=n1(I); X=SUM(SITE(I)|I#GT#30: A(I)*5+A(I)*0.1*C(I); BND(190,X,200); Y=SUM(SITE(I)|I#GT#30:A(I)*C(I)+850+2000-10*X; SUM(SITE(I): A(I)*n1(I)=Y; SUM(SITE(I): A(I)*n2(I)=Y; SUM(SITE(I): A(I)*n3(I)=Y; END 4、求最少装卸次数MODEL:SETS:time /1.55/: X1,X2,X3,X4,V1,V2,V3,U1,U2,U3,W1,W2,W3,Y1,Y2,Y3;ENDSETSDATA:U1=;U2=;U3=;!分别为早中晚需求量的1.1倍；V1=;V2=;V3=;!分别为早中晚还回量；W1=;W2=;W3=;!分别为早中晚需求量；ENDDATA MIN=SUM(TIME:ABS(X2-X1+W1-V1)+ABS(X3-X2+W2-V2)+ABS(X4-X3+W3-V3); FO