ｍｏｄｅｌ
ａｎｄ
ｓｏｌｕｔｉｏｎ，ｔｈｅ ｓｏｌｖｉｎｇ ｉｄｅａｓ
ｓａｌｅｓｍ珊１ ｐｒｏｂｌｅｍ ｐｒｏｖｉｄｅｓ
ａ
ｂｅ ｕｓｅｄ
ｔｏ
ｔｏ
ｓｏｌｖｅ
ｔｈｅ ｉｓｓｕｅ ｏｆ ｐｕｂｌｉｃ ｂｉｃｙｃｌｅ
ｓｃｈｅｄｕｌｉｎｇ
ｓｃｈｅｄｕｌｉｎｇ ｏｐｔｉｍｉｚａｔｉｏｎ．，１１ｌｉｓ ｐａｐｅｒ ｊｕｓｔ
Ａ学海泛舟ｖ｜Ｉｌ｝｛ ｉＩ【ｌ Ｉ ｜ｆｌ｛Ｉ｜Ｊ
万方数据
２０１
１．Ｏ｛＜城市公共交矗＞ｕＲ卧Ｎ ｎ舢ｃ＂ｎ＇，ｔ，ｔｌＳｔ＇ＯＭ
年５月１日开始试运营，同年９月１６日正式运营。 ２００９年５月１日，武汉市启动ＰＢＳ，其中青山区由 龙骑天际公司负责，武汉市其他区由鑫飞达公司负 责运营，两者间不能互借互还。 国内在ＰＢＳ的实践尚处于起步摸索阶段，公共 自行车规划方面的研究也处于起步阶段，姚遥等分别 对杭州、上海和武汉的ＰＢＳ规划作了较深入的研究， 根据各个城市的实际情况，分别提出了自行车系统服 务点的布点原则和配车规模，并给出近期布局规划方 案［５１１ ６】【７１，但均未提及动态合理调度方面的研究。
・３９・
，
Ｓｙｓｔｅｍ，ＰＢＳ）界定为：公司或组织在大型居住区、 商业中心、交通枢纽、旅游景点等客流集聚地设置 公共自行车租车站，随时为不同人群提供适于骑行 的公共自行车，并根据使用时间的长短征收一定额 度费用，以该服务系统和配套的自行车路网为载体， 提ｇＶｈ共，自行车出行服务的城市交通系统…。 自上世纪９０年代末，欧美许姆 斯特丹等国际大城市，自行车租赁服务发展迅速，
Ｅｎｇｉｎｅｅｒｉｎｇ，Ｗｕｈａｎ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ
Ｄｉｎｇ
Ｌｉｕ Ｚｕｐｅｎｇ
Ｗｅｉｄｏｎｇ
Ｃｈｅｎｇ Ｙｉｍｉｎ ｃｏｍｌｎｏｎ
Ａｂｓｔｒａｃｔ：Ｃｉｔｉｅｓ ｉｎ Ｃｈｉｎａ ｈａｖｅ ｂｅｇｕｎ ｔｈｅ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｆ ｐｕｂｈｃ ｂｉｃｙｃｌｅ ｓｙｓｔｅｍ，ｗｉｔｈ ｔｈｅ ｉｎｃｏｎｖｅｎｉｅｎｃｅ
过２个点，到达终点的最短路径。以此类推，分别
求出第２、３、４阶段从①出发到其余各点的最短路
径，分别如附表中第２、３、４列所示。 最终在第４阶段求解得到最短路径的最小值
图２收集自行车的站点分布圈
厶（９’｛４，５，２，６｝）＝１６，即表示从④出发，经
④一⑤一②一⑥，到达⑨的路径为所有收集自行车路
根据货郎担问题定义最优值函数五（ｉ，ｓ），表示 径中的最短路径，其距离为１６。即收集车辆的最短
五（ｉ，ｓ）＝ｒａｉｎ【Ａ（歹，ｓ＼Ｕ））＋喀】。
根据动态规划分阶段求解，在第０阶段中，仅
中从①点出发，经过其余５个点的最短路径。
②、④两点与①直接相连，其余点距离为００，如附 表中第一列所示。在第１阶段中，⑤、⑥、⑨与起
点①之间经过一个点时的最短路径如附表第二列所
示，其中ｆｌ（５＇｛２））表示从①出发，经②，到达⑤ 的最短距离为６＋２＝８。第２阶段求解从①出发，经
货车车厢空间有限，此处的④点可以在第一次经过
时不操作，第二次经过时再运走５辆自行车，则调 度用的货车上可以少存放５辆自行车，此处是对调 度线路的重复站点的优化。
了的发放站点（如此例中的③点，在收集车辆时点 ②到点⑥必经点③，所以经过点③时可把点③需要
的车辆先卸下），组成发放自行车的站点分布图，如
图３所示。图中①一⑧、①一⑨的最短路径由
砂（ｉ）点开始，由ｋ个中间点的ｓ集，到达ｉ点时的最
行走路径为①＿÷④一⑤一②＿＋⑥＿⑨。
附表收集自行车各阶段的最短路径
・４１・
万方数据
２０１１．０１‘城市公共交囊＇ｕ阻州ＰＩＪＯＵＣ仰口ｓＰｏＲｒ
３．２发放自行车
根据第一步收集自行车的路线，除去已经经过
在图４中④点经过了两次，第一次经过时运走５
辆自行车，第二次经过时不操作。考虑到调度用的
ｏｆ
ｂｉｃｙｃｌｅｓ ｂｅｔｗｅｅｎ
ｓｉｔｅｓ ｉｓ
ｎｏｔ
Ｕｓｅ ｏｆ”ｏｐｅｒａｔｉｏｎａｌ ｒｅｓｅａｒｃｈ”
ｓｃｈｅｄｕｈｎｇ ｏｂｔａｉｎ
ｓｏｌｖｉｎｇ ｔｒａｖｅｌｉｎｇ ｓａｌｅｓｍａｎ
ｆｉｒｓｔ ｃｏＵｅｃｆｉｎｇ
ｐｒｏｂｌｅｍ
ｄｙｎａｍｉｃ ｐｒｏｇｒａｍｍｉｎｇ ｉｄｅａｓ
ｓｏｌｖｅ ｔｗｏ－ｓｔｅｐ
２模型假设
为便于阐述，假设一个调度的模型如图１所示：
在自行车系统调度方案中，不仅需过各个站点， 还有站点调度自行车数量Ｎｉ（ｉ＝１，２…９）的问题， 且Ｎｉ有正有负：Ｎｉ为正数表示需运走的车数，为负 数表示需补给的车数。因此需对货郎担问题模型进 行修改，．并将调度问题分作收集自行车和分发白行 车两步进行。
Ｋｅｙ
ｗｏｒｄｓ：Ｐｕｂｈｃ Ｂｉｃｙｃｌｅ Ｓｙｓｔｅｍ；Ｂｉｃｙｃｌｅ Ｓｃｈｅｄｕｈｎｇ；Ｄｙｎａｍｉｃ Ｐｒｏｇｒａｍｍｉｎｇ；Ｔｒａｖｅｌｉｎｇ Ｓａｌｅｓｍａｎ Ｐｒｏｂｌｅｍ
“公共自行车”源于欧洲，推行目的是为解决 公共交通站点到居住地还有一段距离的“最后一公 里”难题。公共自行车交通系统（Ｐｕｂｌｉｃ
在①点附近，进行调度时：该车只能从①点出发， 且最后须再回到①点。
・４０・
万方数据
ｕＲＢ＾Ｎ ＰｕＢｕｃ
ＴＲ州ｓＰｏ阿《城市公获交通》２０１
１．０１
站点分布图，如图２所示。图中④一⑨之间的距离可
用Ｄｉｊｋｓｔｒａ算法求得其最短路径。这一步要解决的问 题是：要用货郎担问题的动态规划解法求解得到图２
短路径，如表示从点ｉ到点ｊ的距离，根据货郎担问 题的动态规划方法，可知其满足递推关系
图１调度模型示意图
１
问题提出
经过数年ＰＢＳ实践，国内几个城市的ＰＢＳ都出 ３
解决方案
在《运筹学》的图论中有最短路问题、货郎担
现了一些急需解决的共性问题，其中主要是“借车 难、还车也难”。问题的成因主要有三个，一是ＰＢＳ 站点选址不合理；二是ＰＢＳ站点配车数不合理；三 是ＰＢＳ站点之间的自行车调度不及时等。 武汉鑫飞达公司运营的ＰＢＳ各站点有专人值守， 不设电子停车桩，因此不存在“还车难”问题，但 调查发现“借车难”问题同样较为严重。本文通过 建立假设模型，运用《运筹学》中货郎担问题解题 思路来求解ＰＢＳ站间的最优调度路径，优化调度方 案，为解决“借车难”问题提供参考。
Ｄｉｊｋｓｔｒａ算法求得。这一步要解决的问题是：再次运
４结束语
本模型只是提供了一个解决站点间调度方案优 化的思路，如要加以实际应用，首先须对ＰＢＳ刷卡 数据进行大规模的数据统计和整理，得到所需的数 据，计算出站点配车数和站间调度车数；再者应用 货郎担问题解决大规模调度时，需对货郎担问题的 解法进行计算机编程处理，这样才能给出最优的配 车数和调度方案，才具实用价值。后续的研究可与 ＰＢＳ公司合作，结合数据挖掘和货郎担问题编程处 理，提出实用的解决方案。
Ｂｉｃｙｃｌｅ
实施效果表明ＰＢＳ提供了一种既方便健康，又有益 于环境保护、资源有效利用以及城市形象改善的出 行方式，ＰＢＳ对改善城市道路环境条件、缓解交通 压力、促进节能减排都起到了积极的作用Ⅲ…【４１。 在我国，上海市自２００５年８月起在沿地铁３号 线的２０个车站试用ＰＢＳ，但试点效果不佳。２００８年 ９月ＰＢＳ再次登陆上海，地铁２号线张江高科站和 浦东软件园内的两个自行车租赁网点正式开业，成 为上海构建ＰＢＳ的新起点。北京市为迎接奥运会， 缓解城市交通拥堵和环境污染，自２００７年８月１９ 日起，多家自行车租赁公司开始宣传并提供公共自 行车出行服务。杭州市公共自行车服务系统自２００８
（１）图中①二⑨表示９个ＰＢＳ站点的编号，暂
时不需运走或补给的站点未被列人模型中。 （２）站点之间连线上的数字表示点与点的距离
（或费用），如：①一②之间的６表示：两点之间有６
个单位的距离。 （３）假设各个站点需运走或补给的自行车辆数 已经求得Ｎｉ（ｉ＝ｌ，２…９），在图中用编号右上的粗体
结合本模型，调度货车从①点出发，先收集自 行车：找到从①点经过②、④、⑤、⑥、⑨所有点
ｔｏ
ｐａｔｈ
ｂｅｔｗｅｅｎ
ｓｔａｔｉｏｎｓ：ａｔ
ｂｉｃｙｃｌｅｓ；ｔｈｅｎ ｒｅｌｅａｓｉｎｇ ｂｉｃｙｃｌｅｓ，ｉｎｔｅｇｒａｔｉｎｇ ｔｗｏ ｓｔｅｐｓ
ａ
ｏｐｔｉｍａｌ
ｔｏ
ｓｃｈｅｄｕｌｉｎｇ
ｔｒａｖｅｌｉｎｇ
ｐａｔｈ．Ｔｈｒｏｕｇｌｌ
ｔｈｅ
ｅｓｔａｂｈｓｈｍｅｎｔ ｏｆ
Ｃａｌｌ
ｓｉｍｐｌｅ
ｍａｔｈｅｍａｔｉｃａｌ
用货郎担问题的动态规划解法求解得到图３中从⑨
点出发，经过其余２个点，最终回到①点距离最短 的路径。
图３发放自行车的站点分布图
参考文献：
［１］龚迪嘉，朱忠东．城市公共自行车交通系统实施机制
由于本例中发放时的站点较少，从图３中可见，
【Ｊ】．城市交通，２００８，６（６）：２７—３２ 【２］王志高，孔嚣，谢建华等．欧洲第三代公共自行车系 统案例及启示【Ｊ １．城市交通，２００９，７（４）：７—１２ ［３］韩慧敏，张宇，乔伟．里昂公共自行车系统ｆＪ】．城 市交通，２００９，７（４）：１３—２０ 【４］耿雪，田凯，张字，黎睛．巴黎公共自行车租赁点规 划设计【Ｊ】．城市交通，２００９，７（４）：２１—２９ ［５】姚遥，周扬军．杭州市公共自行车系统规划【Ｊ】．城 市交通，２００９，７（４）：３０—３８ ［６］郭敏辉，钟明．上海市公共自行车系统规划与实践 【Ｊ】．城市交通，２００９，７（４）：４５—５０ ［７］李黎辉，陈华，孙小丽．武汉市公共自行车租赁点布 局规划【Ｊ】．城市交通，２００９，７（４）：３９—４４，３８ ［８］＜运筹学》教材编写组．运筹学（修订版） 【Ｍ】．北
ｓｉｔｅ ｉｎ ｉｓ
ｔｏ
ｐｒｏｂｌｅｍ ｏｆ
］｜Ｉｌ ｜Ｉ｝｛ｌｉ ｆ