装 订 线
目 录
一、问题的重述 ........................................................................................................... 2
1.1 问题背景 ...................................................................................................... 2 1.2 问题提出 ...................................................................................................... 2 二、问题的分析 ........................................................................................................... 3
2.1 问题一的分析 .............................................................................................. 3 2.2 问题二的分析 .............................................................................................. 3 2.3 问题三的分析 .............................................................................................. 3 三、模型的假设 ........................................................................................................... 3 四、符号的说明 ........................................................................................................... 4 五、模型的建立、求解与结果分析 ........................................................................... 5
5.1 问题一的模型 .............................................................................................. 5
模型建立 ......................................................................................................... 5 模型求解 ......................................................................................................... 7 结果分析 ......................................................................................................... 7 5.2 问题二的模型 ............................................................................................ 13
模型建立 ....................................................................................................... 13 模型求解 ....................................................................................................... 13 结果分析 ....................................................................................................... 14 5.3 问题三的模型 ............................................................................................ 15
模型建立 ....................................................................................................... 15 模型求解 ....................................................................................................... 17 结果分析 ....................................................................................................... 18
六、模型的评价 ......................................................................................................... 19
6.1 模型的优点 ................................................................................................ 19 6.2 模型的不足 ................................................................................................ 19 6.3 模型的改进 ................................................................................................ 19 七、参考文献 ............................................................................................................. 19 八、附录 ..................................................................................................................... 20
装 订 线
第1页 共 26 页
一、问题的重述
1.1 问题背景
近年来，随着经济的发展，我国各级城市的机动车保有量都进入了持续高速增长时期，但由此所引发的道路拥堵、空气污染也引起了政府以及百姓的极大关注。众所周知，建立快速、便捷的城市公共交通体系是解决这一问题的有效手段之一。然而，居民居住地和交通站点通常都有一段距离，这段不远的距离以及现实存在的公共交通拥挤现象则使居民乘坐公共交通的意愿降低，公共自行车服务系统已被证明能够从一定程度上缓解这一现象。 1.2 问题提出
公共自行车服务系统是指在某个区域内，隔一定距离规划出一些停放自行车的租赁点（如地铁出口、城市中心等人员密集的地方），一个租赁点放置一定数量的自行车，很多的自行车租赁点共同组成一个网络以形成一个服务系统，居民可以在任意租赁点租、还车辆，费用全免（某些城市收取少量的超时费用，但目的只是用来提高自行车的利用率，不以盈利为目的），根据租赁点自行车的使用频率，避免部分租赁点的自行车短缺或堆积现象发生，将通过调度专用车进行合理调度，以最大程度地满足居民对车辆需求，提高车辆利用率（系统有自动报警功能。
公共自行车租赁服务系统纳入城市公共交通体系，有助于解决公交出行“最后一公里”问题，使公共交通服务网络趋于更加完善。西安市经开区公共自行车服务系统于2011年4月开始建设，到目前为止，已建成租赁点30个（附件1），自行车总量达到850辆。目前正在筹备第三期建设。
根据题目中给出的条件和附录中的信息解决如下几个问题：
（1）根据目前经开区网点自行车需求情况等信息，若要求调度平均耗时尽 量少，请针对已有的30个租赁点设计最优车辆分配方案、调度方案，并给出完成调度所耗费的时间。
（2）假设经开区公共自行车服务系统三期建设准备投入建设经费200万元，据此建立数学模型，确定新增租赁点数目、位置以及合适的放置车辆数目。
（3）针对问题（2），进一步研究，如果要求在150min内完成调度，是否需要增加调度车辆（购置调度车辆费用由其它项目经费解决，不包含在三期建设提
第2页 共 26 页
供的200万元经费中间）？并给出该情形下的自行车调度方案。
装 订 线
二、问题的分析
2.1 问题一的分析
问题一是一个TSP问题（即货郎担问题），没有提及任何的费用问题，只需要考虑时间以及路程，而在分析过程中路程可以用时间来衡量，装卸自行车也使用时间来衡量，因此这可以看成是一个单目标规划问题，利用lingo编程用穷举的的方法对最短路程进行求解，进而转化成时间，目标是使调度车行驶的时间最少。
2.2 问题二的分析
问题二中，经开区公共自行车服务系统三期建设准备投入建设经费200万元，由此建立线性规划数学模型，确定新增租赁点数目、位置以及合适的放置车辆数目。我们在此首先考虑居民需求，也就是在满足租赁点自行车数量上限的前提下，使得公共自行车数量达到最大值，确定租赁点相应数目对应地点后，利用几何关系，分析比较新增租赁点分布合理性，从而解出新增租赁点的数目、位置和各个租赁点分配的自行车数量。 2.3 问题三的分析
问题三中，针对问题（2），进一步研究，题目要求在150min内完成调度，若总用时低于150min则不需要增加调度车辆，若总用时大于150min则需要增加调度车辆。该问相当于是问题一的拓广，我们在此利用问题一的模型，只需要考虑时间以及路程，而在分析过程中路程可以用时间来衡量，由此转化成关于时间的单目标函数求解，即求解一辆调度车时的最短路径，两辆调度车时的调度总用时，三辆车时的调度总用时??当车辆数目满足调度用时小于150min时，确定此时的调度路线，即为所求解。
装 订 线
第3页 共 26 页
三、模型的假设
1. 租赁点之间的距离使用经纬度计算，即假设到达任意租赁点所走的路程
就是两租赁点之间的距离，不考虑街道等因素对本题模型的影响。 2. 为简化模型，不考虑调度车启动和停止的时间，假设调度车运输过程匀
速行驶，不会受到交通事故、红绿灯等外界因素的影响。
3. 假设各个租赁点每天的自行车需求量不变，且自行车的需求时间刚好处
在附件二中的时间段。
4. 假设居民的骑行距离不超过2km，在某个租赁点还车的概率与租车点和
还车点的距离成反比，骑行距离超过2km的情况一定不会发生。 5. 求解过程中，自行车数量出现小数时采用四舍五入取整。
四、符号的说明
abpkis 第i个租赁点在第s个时段车辆需求量（i=1,2,…,30;s=1,2,3） 第i个租赁点在第s个时段车辆实际量（i=1,2,…,30;s=1,2,3） 第j个租赁点在第i个租赁点还车的概率（i,j=1,2,…,30） isijij 第j个租赁点在第i个租赁点还车的比例系数（i,j=1,2,…,30） ci第i个租赁点装卸车用时（i=1,2,…,30） 第i个租赁点到第j个租赁点调度车用时 调度总用时 调度车行驶用时 调度车装卸车辆用时 新增租赁点及车辆总花费 新增租赁点个数 编号为l的某租赁点日平均车辆需求量（l=1,2,…,70） 新增车辆的数目 编号为l的某租赁点实际车辆数 tij Z Z1 Z2 W K y lm fl
第4页 共 26 页
装 订 线
五、模型的建立、求解与结果分析
5.1 问题一的模型
模型建立
在问题一中，我们考虑编号为1到30的租点。建立以调度车行驶时间最少为目标的模型，我们结合调度车行驶的方向性，运用lingo编程找出任意两个租赁点的可行最短路径，也就是运用穷举的方法筛选出最短的行驶路径，从而求出从一个点到另一个点花费的时间。
设租赁点之间的距离用矩阵d来表示，离。而租赁点之间的距离
dij表示租赁点i与租赁点j之间的距
dij本模型按照题目要求用经纬度进行计算，此运算过
程用Matlab编程实现，设0-1矩阵x用来表示经过的个城市之间的路线。设：
?0,若租赁点i不到租赁点jxij???1,若租赁点i到租赁点j，且i在j之前 考虑每个租赁点后只有一个租赁点，则
n?xj?1j?iij?1,i?1,2,,n
考虑每个租赁点前只有一个租赁点，则
?xi?1i?jnij?1,j?1,2,n
但仅有以上约束条件不能避免在一次遍历中产生多于一个互不连通回路。为此我们引入额外变量ui?i?1,2,,n?
，附加一下充分约束条件，即
ui?uj?nxij?n?1,1?i?j?n该约束的解释为：
u?u??1,uj?ui??1,xx①i与j不会构成回路，若构成回路有ij=1，ji=1，则ij从而有0??2,导致矛盾；
②i，j与k不会构成回路，若构成回路有
xjixu?uj?=1，jk=1，xki=1，则i-1，
第5页 共 26 页