基于最小点覆盖的共享单车投放点选取方法

A Method of Location Selection of Parking Sites for Shared Bicycles Based on Minimum Vertex Cover Problem

针对城市共享单车投放点和电子围栏等设置不合理的问题,考虑共享单车对城市交通环境影响和共享单车运营企业的成本,研究了一种基于最小点覆盖的共享单车投放点选取算法。将整个城市交通网络抽象为图,将共享单车投放点抽象为图的节点。对于图的不同点覆盖方案,引入路段权值函数和调度成本矩阵,以最少投放点和最小调度成本2个指标对不同点覆盖方案进行排序,从中选优得到共享单车投放点选取方案。算法既考虑了共享单车投放点在城市交通网络的覆盖情况,又考虑了共享单车企业车辆投放和车辆调度的成本问题,克服了现有共享单车投放点选取方法的单一性和盲目性的问题。

In a view of unreasonable setting of parking sites and electronic fences for shared bicycles in urban areas,considering its impacts on urban traffic environment and cost of business operation,an algorithm of location selection of parking sites for shared bicycles based on minimum vertex cover problem.The entire urban transportation network is abstracted into a graph,and the parking sites for shared bicycles are abstracted as nodes of the graph.For different node coverage schemes of the graph,a function of road segment weight and a matrix of scheduling cost are introduced.The different node coverage schemes are sorted by the minimum number of parking sites and the minimum cost for scheduling,then the optimal scheme is selected.The algorithm not only considers the coverage of parking sites in urban transportation network,but also considers the cost of sharing and scheduling of the shared bicycle enterprises,and overcomes the simplicity and blindness of the existing methods location selection of parking sites for shared bicycles.