4.4租赁点数目和位置的确定
题目中新增的租赁点是在已知的若干点中选取的，因此，分析清楚选取租赁
点的约束条件，就可以从最优解的角度得到新增的节点。
建立租赁点时首先考虑的是各个点的需求量（已知），由于在不同时段的需求量不同，所以应当考虑平均需求、不同时段需求。所以首先我们应当确定加权平均比例，一保证确定的租赁点在全天达到最优。在这里引入一个加权平均比，取决于我们实际问题的要求和调度问题的特点。 首先将数据加权平均，有：
再将每一个租赁点的耗资数额按照公式（4-4-1）求出
Y?a?X加权需求量?b （4-4-1）最后将耗资数额加和，即求得满足式（5-2-2）的最大k值。
?p?a?Xi?1ki?b?? （4-4-2）考虑了需求量对新租赁点的影响之后，我们还需要考虑骑行规律对租赁点选取的影响。所谓运输规律就是：居民可以在任意一个租赁点还车，在某个租赁点还车的概率与租车点和还车点的距离成反比，且假设居民的骑行距离不超过M。于是仅考虑运输规律，我们引入一个方便因数，定义如下：
Con??yi?Pi?Si?1n（4-4-3）
Con用来衡量新设置的租赁点的合理程度，它与租赁点的分配量、常数Pi、Si的乘积之和有关，其中，常数Pi的定义如下：
Pi??Bijj?1n （4-4-4）Si的定义如下：
Si??Bij?dijj?1n （4-4-5）Si表示i租赁点能够到达其他节点的数目之和，Si越大表明该节点的辐射能力越
- 11 -
强，也越合理。
在路程不超过M的范围内，租赁点i能够到达的节点越多，则常数Pi越大。 还要保证新增的节点数k尽可能地少。
在新增租赁点的过程中不考虑随后的调度方案，因此在总建设经费的限制下，可以按照优化的方法求出方便因数的最小值。
4.5 调度时间的模型
在三期建设中，为了实现经开区更大的网点覆盖面积，进一步增设站点，新增了一批租赁站点并购进自行车。然而，更多的站点可能会导致部分租赁点的自行车短缺或堆积现象，从而降低了资源利用效率。为了探讨这个问题，我们必须对现有调度方案进行检验和矫正，更好的实现资源利用最大化。故对调度时间进行了计算，发现用两辆调度车进行自行车调度很难满足调度需求,调配时间超过限制时间，必须购置更多的调度车辆，虽然会增加一定成本，但对整体的统筹有很大的意义。
将原有的站点与新增站点进行混合，重新根据密集度，自行车需求量等因素进行分组，根据分组情况配备调度车辆。若所分组数增多，则增加调度车辆的数目可以更快捷地实现调度需求。然后对每一组的调度方案进行独立分析，即求解
mint??k?1k?dij?k????v?|lj|??xiji?1j?1,j?i??
n则总调度时间：
minT??tkk?1k（k代表组数）
具体建模思想与第一问的求解相似。
- 12 -
五、 模型的求解
5.0经纬度转换为横纵坐标 5.1 求解最短路径
思想描述：
我们将最短路径的计算作为一个函数。而经过讨论我们决定计算采用Floyd-Warshall计算方法（以下简称Floyd算法）。Floyd算法是以动态规划为手段，以解决任意两点间的最短路径为目的的一种算法,该算法的时间复杂度为
O(N3)，空间复杂度为O(N2)。它可以正确处理有向图或负权的最短路径问题，
故该方法适用于我们的问题(在实际算法中，为了节约空间，我们直接在原来空间上进行了迭代，这样空间可降至二维)。 Floyd算法的描述如下： 设
Di,j,k为从i到j的只以(1...k)集合中的节点为中间节点的最短路径的长度。
Di,j,k?Di,k,k?1?Dk,j,k?1Di,j,k?Di,j,k?1若最短路径经过点k，则；
若最短路径不经过点k，则因此，
。 。
Di,j,k?min(Di,k,k?1?Dk,j,k?1,Di,j,k?1)?k?1k?1;k?k???k?30 i?i?1i?1;i????i?30
j?j?1j?1;j????j?30
if (
Di,k?Dk,j?Di,j)
Di,j?Di,k?Dk,j
综上,最短路径矩阵为：（单位：km）
- 13 -
图5-1-1
5.2 模型一次运行后的单车重分配求解
依据题意不难得知，在租赁点还车的概率与租车点和还车点的距离成反比，且居民的骑行距离不超过2km。 ○1据骑行距离此可得出筛选算法：
?i?1i?1;i?i???i?30
k=1;
j?j?1j?1;j????j?30
if i?j if
di,j?2000
di,j?0;else
di,j?0;k=k+1;
○2根据反比例关系不难得出每个租赁点向2km内的各个租赁点发送的单车数量为：
Fi,j?
Ki,jdi,j
- 14 -
根据归一化条件：
?Fi,j?j?1nKi,jdi,j?1
综上可得出求得2km内的概率系数K的算法：
?i?1i?1;i?i???i?30
s=0;
j?j?1j?1;j????j?30
if
di,j?0
s?s?
s?1di,j;
1s；
K=[K s];
○3根据各个租赁点发送出的单车概率可求得运行一次后的各个租赁点单车数目：
Fj??Fi,ji?1n
据此可得出求解运行一次后的各个租赁点单车数目的算法：
j?j?1j?1;j????j?30
t=0;
?i?1i?1;i?i???i?30
if
di,j?0
t?t?Fi?Kidi,j；
Fj?t;
模型运行一次后的结果如图所示：
- 15 -
公共自行车调度问题-数学建模论文
