如果多出，则装满。
3.2符号系统
G------租赁点的集合
T------调度总时间（不包括完成调度后调度车返回原点的时间）。
k------调度车编号
dij------租赁点间的最短距离
k------第k辆车调度完i后是否再调度j xijuk------是否使用调度车k
lj------租赁点j的需要调度的量 Bij------i和j间的距离是否大于M千米
Ztj------t时间段内租赁点j的需求量
?j------j点的需求量占总需求量的比例
Fij------从i点出发到达j租赁点的自行车数量 Fi------i点的单车数量 a------建立一个租赁点耗资 b------维护每辆自行车耗资 p------每一个租赁点的耗资数
P------新增租赁点的耗资总数
四、模型建立
4.1模型分类
在租赁点的分配方案确定后，只剩下调配问题，属于VRP问题，该问题是著
- 6 -
名的问题TSP（旅行商问题）的一个特例，因而也是NP-hard问题。
典型的VRP模型定义如下：假设已知客户网络中的客户数量、客户所在的位置、客户需求和配送车辆的最大负荷，要求在满足约束的前提下为给定的中心仓库设计车辆路径，使运输成本最小。
传统电子商务配送模型是分区域配送模式的单一配送中心（Distribution centre ,DC）-多需求点（demands , DS）的路径优化模型，而且不考虑沿途补货的情况。而针对区域广泛、客户众多且分散、业务量大且频繁的电子商务物流配送业务，需要考虑多个配送区域联合、沿途多次补货的配送策略，从而得到电子商务配送的跨区域VRP模型。
这个思路和我们所要考虑的利用公交车收集和分配公共自行车很类似，问题中有多余自行车的租赁点即可看作电子商务问题中的配送中心DC，而缺少自行车的租赁点也可看作是需求点DS。
我们的问题和电子商务问题的一个不同点是，在调度时，如果调度点由盈余的自行车且数量加上调度车上已有的自行车时其总量会可能会超过调度车的最大装载量，因此有可能导致这些点的二次调度，这和电子商务配送模型中一次性完成调度有所区别，但是可以经过是党的改正后得到正确的模型。
4.2 租赁点分配方案建模
影响租赁点自行车分配的因素有：各租赁点的需求量、从租赁点离开的自行车、从其他租赁点起来的自行车等。若仅考虑需求量对租赁点分配自行车数目的影响，有如下模型：
yj?Ztj??j(4?2?1) (4-2-2)
?j?Ztj?Zj?1ntj（1）式确定按照最终的需求量，以按比例分配的方式确定租赁点的分配量。 （2）式给出需求量占总需求量的比例。
以仅考虑需求量的方式确定的分配方式显然不是最佳方案。分配方案还和租赁点之间的距离有关。由题意可知，从在某个租赁点还车的概率与租车点和还车点的
- 7 -
距离成反比，且假设居民的骑行距离不超过M km，由此可得出下式：
y(k?1)j?y(k)j?j?1,j?i?xnji?Bji?i?1,i?j?xnij?Bij(4-2-3)
yj?y(jk?1)?R(4-2-4)
式（4-2-3）首先按照（4-2-1）式的方式产生一组分配方案，然后让其按照自行车间行驶的规则再次分配，产生新的一组分配方案，然后用（4-2-4）式校正，最终得到优化了的分配方案。
4.3 调度车调度方案建模
4.3.1一辆调度车调度方案
在我们的求解问题中，第一问中调度车辆问2辆，为了问题是建模化简，我
们先考虑调度车为一辆的情况，然后推广到多量的情况，这样就可以给对第一问和第三问的调度问题建立实际的解题模型。
设拥有最大负荷为Q的调度车从指定的节点出发，对集合为G的节点进行调度。完成任务后返回原点。调度需求量和租赁点间的距离已经求得。整个调度方案可以由下列一组方程和约束条件确定：
?dij??minT?????|l|j?xij?vi?1j?1,j?i??n(4-3-1)
?x??xijj?1j?1nnji?1(4-3-2)
?xi?1nij?1(4-3-3)
?xj?1nij?1(4-3-4)
0?lj?rij?QZi??Fij?Bijj?1n(4-3-5) (4-3-6)
- 8 -
lj?Zj?yi?(?xji??xij)?Bijj?1nj?1nnn(4-3-7)
Zj?lj?yi?(?xji??xij)?Bijj?1j?1(4-3-8)
（4-3-1）式为目标函数，求出最短距离；
（4-3-2）确定了出发点，即必须从出发点出发，然后再回到出发点；
（4-3-3）-（4-3-4）确定了调度车对特定节点只能调度1次，不能重复经过一个节点；
（4-3-5）式保证调度车调度时调度车上的数量能够满足任意节点的调度需求量，同时装载量不能超过调度车的最大载重；
（4-3-6）式确定了某一节点的总需求量就是从该租赁点离开去往其他租赁点的自行车的数量之和；
（4-3-7）式确定了每一节点的调度量；
（4-3-8）式给出总需求量、分配量、调度量从该节点出发的自行车数目和到达该节点的自行车的数量之间的关系。 4.3.2多辆调度车调度方案
设拥有最大负荷为Q的k调度车从指定的节点出发，对集合为G的节点进行调度。完成任务后返回原点。调度需求量和租赁点间的距离已经求得。整个调度方案可以由下列一组方程和约束条件确定：
minT??k?1k?dij????v?|lji?1j?1,j?i?n?k|??xij?(4-3-10)
(4-3-9)
?ui?1ki?kn?x??xkijj?1j?1nkji?1(4-3-11)
??xk?1i?1,j?iknkij?1(4-3-12)
- 9 -
??xk?1j?1,j?iknkij?1(4-3-13)
0?lj?rijk?QZi??Fij?Bijj?1nklj?Zj?yi?(?x??xij)?Bijkjij?1nj?1nnn(4-3-14) (4-3-15)
(4-3-16)
kZj?lj?yi?(?x??xij)?Bijkjij?1j?1(4-3-17)
xtk0i1j?xtz0i2j（3-4-9）式为目标函数，求出最短距离； （3-4-10）式确定调度车的数目； （3-4-11）确定了出发点；
(4-3-18)
（3-4-12）-（3-4-13）确定了每辆调度车对特定节点只能调度1次，不能重复经过一个节点；
（3-4-14）式保证每次调度时调度车上的数量能够满足任意节点的调度需求量，同时装载量不能超过调度车的最大载重；
（3-4-15）式确定了某一节点的总需求量就是从该租赁点离开去往其他租赁点的自行车的数量之和；
（3-4-16）式确定了每一节点的调度量；
（3-4-17）式给出总需求量、分配量、调度量从该节点出发的自行车数目和到达该节点的自行车的数量之间的关系。
（3-4-18）式保证不同的调度车不能再同一时刻到达同一个租赁点。
根据以上一组方程和约束条件，就可以将调度问题相对完整的描述出来。这是一个优化问题，在求解过程中由众多的算法可以采用，但是考虑到算法的复杂性可标称的简洁性，我们采用的算法是启发式算法，这将在模型求解中详细讨论。
- 10 -
公共自行车调度问题-数学建模论文
