[go: up one dir, main page]

CN110458309B - Network about splicing station point location method based on actual road network environment - Google Patents

Network about splicing station point location method based on actual road network environment Download PDF

Info

Publication number
CN110458309B
CN110458309B CN201910580890.0A CN201910580890A CN110458309B CN 110458309 B CN110458309 B CN 110458309B CN 201910580890 A CN201910580890 A CN 201910580890A CN 110458309 B CN110458309 B CN 110458309B
Authority
CN
China
Prior art keywords
road
point
points
distance
station
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Expired - Fee Related
Application number
CN201910580890.0A
Other languages
Chinese (zh)
Other versions
CN110458309A (en
Inventor
程琳
熊佳莹
杜明洋
李雪峰
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Southeast University
Original Assignee
Southeast University
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Southeast University filed Critical Southeast University
Priority to CN201910580890.0A priority Critical patent/CN110458309B/en
Publication of CN110458309A publication Critical patent/CN110458309A/en
Application granted granted Critical
Publication of CN110458309B publication Critical patent/CN110458309B/en
Expired - Fee Related legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F18/00—Pattern recognition
    • G06F18/20—Analysing
    • G06F18/23—Clustering techniques
    • G06F18/232—Non-hierarchical techniques
    • G06F18/2321—Non-hierarchical techniques using statistics or function optimisation, e.g. modelling of probability density functions
    • G06F18/23213—Non-hierarchical techniques using statistics or function optimisation, e.g. modelling of probability density functions with fixed number of clusters, e.g. K-means clustering
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
    • G06Q10/00—Administration; Management
    • G06Q10/02—Reservations, e.g. for tickets, services or events
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
    • G06Q50/00—Information and communication technology [ICT] specially adapted for implementation of business processes of specific business sectors, e.g. utilities or tourism
    • G06Q50/40—Business processes related to the transportation industry
    • Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y02—TECHNOLOGIES OR APPLICATIONS FOR MITIGATION OR ADAPTATION AGAINST CLIMATE CHANGE
    • Y02T—CLIMATE CHANGE MITIGATION TECHNOLOGIES RELATED TO TRANSPORTATION
    • Y02T10/00—Road transport of goods or passengers
    • Y02T10/10—Internal combustion engine [ICE] based vehicles
    • Y02T10/40—Engine management systems

Landscapes

  • Engineering & Computer Science (AREA)
  • Business, Economics & Management (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • Data Mining & Analysis (AREA)
  • Tourism & Hospitality (AREA)
  • General Physics & Mathematics (AREA)
  • Marketing (AREA)
  • General Business, Economics & Management (AREA)
  • Economics (AREA)
  • Strategic Management (AREA)
  • Human Resources & Organizations (AREA)
  • Probability & Statistics with Applications (AREA)
  • Artificial Intelligence (AREA)
  • Quality & Reliability (AREA)
  • Health & Medical Sciences (AREA)
  • General Health & Medical Sciences (AREA)
  • Primary Health Care (AREA)
  • Operations Research (AREA)
  • Development Economics (AREA)
  • Life Sciences & Earth Sciences (AREA)
  • Entrepreneurship & Innovation (AREA)
  • Bioinformatics & Cheminformatics (AREA)
  • Bioinformatics & Computational Biology (AREA)
  • Computer Vision & Pattern Recognition (AREA)
  • Evolutionary Biology (AREA)
  • Evolutionary Computation (AREA)
  • General Engineering & Computer Science (AREA)
  • Management, Administration, Business Operations System, And Electronic Commerce (AREA)

Abstract

本发明公开了一种基于实际路网环境的网约拼车站点选址方法，包括以下步骤：(1)利用K‑means聚类法对乘客预约需求点进行分组，并确定各分组的聚类中心；(2)各分组根据乘客需求点和聚类中心的空间位置来确定对应的路网分析区；(3)针对任一分组对应的路网分析区，取其中任一条路段，计算该分组所有乘客需求点对应的路段分割点；(4)以拼车站点在该路段上的位置作为变量，计算路网分析区内所有乘客需求点到拼车站点的最短路距离之和，来确定针对该路段的最优站点位置；(5)对路网分析区中其它路段重复上述操作，再比较各路段的最短距离之和来确定最优站点所在的路段及位置。该方法为现实生活中拼车站点的合理布设提供了参考和选择依据。

Figure 201910580890

The invention discloses a site selection method for online carpooling sites based on the actual road network environment, which includes the following steps: (1) using the K-means clustering method to group passenger reservation demand points, and determine the clustering center of each group ; (2) Each group determines the corresponding road network analysis area according to the passenger demand point and the spatial position of the cluster center; (3) For the road network analysis area corresponding to any group, take any road section and calculate all (4) Taking the position of the carpooling station on the road section as a variable, calculate the sum of the shortest distances from all passenger demand points to the carpooling station in the road network analysis area to determine the road section segmentation point corresponding to the passenger demand point; Optimal site location; (5) Repeat the above operations for other road sections in the road network analysis area, and then compare the sum of the shortest distances of each road section to determine the road section and location where the optimal site is located. This method provides a reference and selection basis for the reasonable layout of carpooling stations in real life.

Figure 201910580890

Description

一种基于实际路网环境的网约拼车站点选址方法A site selection method for online carpooling sites based on the actual road network environment

技术领域technical field

本发明属于交通运输规划与管理中的公共交通领域，具体涉及一种基于实际路网环境的网约拼车站点选址方法。The invention belongs to the field of public transportation in transportation planning and management, and in particular relates to a site selection method for online carpooling sites based on an actual road network environment.

背景技术Background technique

作为“互联网+共享经济”的代表，“拼车”被认为是一种公共交通服务改良式的出行模式，能在城市公共交通服务盲区发挥替补作用。现有的网约拼车采取的是任意地点的自由拼车模式，当乘客定位较偏或需搭载多名乘客时，会造成网约车辆绕行距离较大、乘客等待时间较长，从而使得用户行程无法得到保障。As a representative of "Internet + sharing economy", "carpooling" is considered to be an improved travel mode of public transportation services, which can play a substitute role in the blind spots of urban public transportation services. The existing online carpooling adopts the free carpooling mode at any location. When the passenger’s location is biased or many passengers need to be carried, it will cause a large detour distance for the online carpooling vehicle and a long waiting time for passengers, which will make the user’s itinerary difficult. cannot be guaranteed.

站点拼车由滴滴公司率先发行，主要目的是为了减少现存网约拼车服务中因接拼友而产生的绕路里程，且拼车站点的设立允许车辆在同一地点搭载多名乘客而不会增加额外地停车次数。目前，我国站点拼车的发展仍处初步探索阶段，关于拼车站点选址问题的研究较为缺乏。然而在现实生活中，合理的拼车站点位置对提高拼车匹配率、增强用户体验感、促进拼车行业的可持续发展等方面具有较强的现实意义。此外，在拼车站点选址时考虑实际路网环境，可使站点选址的结果更加贴近现实情况且容易实施。Station carpooling was first issued by Didi, the main purpose is to reduce the detour mileage caused by picking up carpooling friends in the existing online carpooling service, and the establishment of carpooling stations allows vehicles to carry multiple passengers at the same location without adding additional parking times. At present, the development of carpooling stations in my country is still in the preliminary exploration stage, and there is a lack of research on the location of carpooling stations. However, in real life, a reasonable carpooling site location has strong practical significance for improving the carpooling matching rate, enhancing user experience, and promoting the sustainable development of the carpooling industry. In addition, considering the actual road network environment when selecting the location of carpooling stations can make the results of station location closer to reality and easier to implement.

因此，有必要设计一种基于实际路网环境的网约拼车站点选址方法对拼车站点进行合理布设，为当前站点拼车的发展提供相应的参考。Therefore, it is necessary to design a site selection method based on the actual road network environment for online carpooling sites to reasonably arrange carpooling sites and provide corresponding references for the development of carpooling at current sites.

发明内容Contents of the invention

本发明提供一种能满足实际路网中乘客需求、最小化乘客步行距离、构思巧妙合理的基于实际道路环境的网约拼车站点选址方法。The present invention provides a site selection method for online carpooling sites based on the actual road environment, which can meet the needs of passengers in the actual road network, minimize the walking distance of passengers, and has an ingenious and reasonable conception.

为了解决上述技术问题，本发明采用的一种基于实际路网环境的网约拼车站点选址方法，包括以下步骤：In order to solve the above-mentioned technical problems, a site selection method based on the actual road network environment adopted by the present invention comprises the following steps:

(1)利用K-means聚类法对乘客预约需求点进行分组，并确定各分组的聚类中心；(1) Use the K-means clustering method to group passenger reservation demand points, and determine the cluster center of each group;

(2)根据所述各分组乘客需求点和聚类中心的空间位置，确定各分组对应的实际路网分析区；(2) According to the spatial position of each grouping passenger demand point and the clustering center, determine the actual road network analysis area corresponding to each grouping;

(3)取路网分析区Zi中任一路段[va,vb]，计算该分组所有乘客需求点对应的路段[va,vb]分割点；(3) Take any road section [v a , v b ] in the road network analysis area Z i , and calculate the division point of the road section [v a , v b ] corresponding to all passenger demand points in this group;

(4)对于可能存在于路段[va,vb]上的拼车站点x，计算分析区内所有乘客需求点到站点x的最短路距离，并将距离求和，来确定针对该路段的最优站点位置；(4) For the carpooling site x that may exist on the road segment [v a , v b ], calculate the shortest distance from all passenger demand points in the analysis area to the site x, and sum the distances to determine the shortest distance for this road segment Excellent site location;

(5)对路网分析区Zi中其它路段重复步骤(3)和步骤(4)的操作，再比较各路段的最短距离之和，确定最优站点的所在的路段和位置。(5) Repeat steps (3) and (4) for other road sections in the road network analysis area Zi , and then compare the sum of the shortest distances of each road section to determine the road section and location of the optimal site.

进一步的，本发明中，步骤(1)中，聚类中心点个数确定的具体步骤为：Further, in the present invention, in step (1), the specific steps for determining the number of cluster center points are:

(11)收集乘客预约需求点的空间位置坐标信息，包括：上车点和下车点经纬度坐标；(11) Collect the spatial position coordinate information of the passenger reservation demand point, including: the longitude and latitude coordinates of the boarding point and the getting off point;

(12)基于K-means聚类算法，当聚类中心为K时，计算每个聚类范围内的所有乘客需求点与对应聚类中心Ki的欧式距离，取距离最大值

Figure GDA0004146562840000021
(12) Based on the K-means clustering algorithm, when the cluster center is K, calculate the Euclidean distance between all passenger demand points within each cluster range and the corresponding cluster center Ki , and take the maximum distance
Figure GDA0004146562840000021

(13)对于每个聚类中心范围，以拼车站点服务半径R为约束，判断步骤(12)计算得到的距离最大值

Figure GDA0004146562840000022
是否大于R。若否，则跳过步骤(14)，此时对应的K值即为聚类中心点个数。(13) For the range of each cluster center, with the service radius R of the carpooling station as the constraint, the maximum distance calculated in the judgment step (12)
Figure GDA0004146562840000022
Is it greater than R. If not, step (14) is skipped, and the corresponding K value at this time is the number of cluster center points.

(14)取K＝K+1，重复步骤(12)和步骤(13)。(14) Take K=K+1, repeat step (12) and step (13).

进一步的，本发明中，步骤(13)中，拼车站点服务半径确定方法如下：Further, in the present invention, in step (13), the method for determining the service radius of the carpooling site is as follows:

站点服务半径R为乘客最大步行范围，取500m，站点服务范围是以聚类中心为圆心，以R为半径向外辐射的圆形区域范围。The station service radius R is the maximum walking range of passengers, which is 500m. The station service range is a circular area with the cluster center as the center and R as the radius radiating outward.

进一步的，本发明中，步骤(2)中，各分组对应的实际路网分析区确定方法如下：Further, in the present invention, in step (2), the method for determining the actual road network analysis area corresponding to each grouping is as follows:

设UNIT为路网节点能构成的最小封闭多边形，为最小路网单元；Let UNIT be the smallest closed polygon that can be formed by road network nodes, which is the smallest road network unit;

路网分析区即为包含一个聚类范围所有乘客需求点的最小实际路网区域；The road network analysis area is the smallest actual road network area including all passenger demand points within a cluster range;

(21)对一个聚类范围Ki内的乘客需求点进行判断，若其位于路网单元UNIT内或边界处，则记录该单元包含的节点ni(包括顶点)和路段ei(包括边界)，路段也可用其端点表示，如路段[v1,v2]；(21) Judge the passenger demand point within a cluster range K i , if it is located in the road network unit UNIT or at the boundary, record the node n i (including the vertex) and road section e i (including the boundary) contained in the unit ), the road section can also be represented by its endpoint, such as road section [v 1 ,v 2 ];

(22)得到包含聚类范围Ki内所有需求点的节点集Ni＝{n1,n2,n3…}和路段集Ei＝{e1,e2,e3…}；(22) Obtain the node set N i ={n 1 ,n 2 ,n 3 ...} and the road segment set E i ={e 1 ,e 2 ,e 3 ...} containing all demand points within the clustering range K i ;

(23)路网分析区Zi用图论方法可表示Zi＝(Ni，Ei)。(23) The road network analysis area Z i can be represented by graph theory method as Z i = (N i , E i ).

进一步的，本发明中，步骤(3)中，乘客需求点对应的路段分割点确定方法如下：Further, in the present invention, in step (3), the method for determining the section segmentation point corresponding to the passenger demand point is as follows:

说明：最短路距离均采用实际网络距离，而不是欧几里得距离；Note: The shortest distance uses the actual network distance, not the Euclidean distance;

va和vb代表一个路段两端点，路段及路段长度均可用[va,vb]表示；pi和pj之间的最短路用

Figure GDA0004146562840000023
表示；若pi和pj之间的最短路经过点va和点vb，则pi和pj之间的最短路可用
Figure GDA0004146562840000024
表示；v a and v b represent the two ends of a road section, and the road section and the length of the road section can be represented by [v a , v b ]; the shortest path between p i and p j is represented by
Figure GDA0004146562840000023
means; if the shortest path between p i and p j passes through point v a and point v b , then the shortest path between p i and p j is available
Figure GDA0004146562840000024
express;

(31)由所述的步骤(23)可知，一个路网分析区Zi中含有节点数Ni，路段数Ei，含有的乘客需求点集合为Pi＝{p1,p2,p3…}；(31) From the above step (23), it can be seen that a road network analysis area Z i contains the number of nodes N i and the number of road sections E i , and the set of passenger demand points contained in it is P i ={p 1 ,p 2 ,p 3 ...};

(32)对于路段[va,vb]([va,vb]∈Ei)，以乘客需求点pi(pi∈Pi)为起点，分别以路段[va,vb]的两端点va和vb为终点，运用Dijkstra算法分别计算最短路径距离，记为

Figure GDA0004146562840000025
和
Figure GDA0004146562840000026
(32) For the road segment [v a , v b ]([v a , v b ]∈E i ), starting from the passenger demand point p i (p i ∈ P i ), the road segment [v a , v b ]’s two ends v a and v b are the end points, and the Dijkstra algorithm is used to calculate the shortest path distance respectively, denoted as
Figure GDA0004146562840000025
and
Figure GDA0004146562840000026

(33)以pi、va、vb为三角形的顶点，以

Figure GDA0004146562840000031
[va,vb]，/>
Figure GDA0004146562840000032
为三角形的边，利用三角形不等式关系寻找路段[va,vb]的分割点。(33) Take p i , v a , v b as the vertices of the triangle, and
Figure GDA0004146562840000031
[v a , v b ], />
Figure GDA0004146562840000032
is the side of the triangle, use the triangle inequality relationship to find the segmentation point of the road section [v a , v b ].

进一步的，本发明中，步骤(33)中，利用三角形不等式关系寻找路段[va,vb]的分割点，具体步骤如下：Further, in the present invention, in step (33), utilize the triangle inequality relation to find the division point of road section [v a , v b ], concrete steps are as follows:

(331)在三角形pivavb中，有以下关系成立：(331) In the triangle p i v a v b , the following relations hold:

Figure GDA0004146562840000033
Figure GDA0004146562840000033

Figure GDA0004146562840000034
Figure GDA0004146562840000034

则对于乘客需求点pi来说，在路段[va,vb]存在的一个分割点espi，使得Then for the passenger demand point p i , there is a split point es pi in the section [v a , v b ], such that

Figure GDA0004146562840000035
Figure GDA0004146562840000035

(332)分割点espi在路段[va,vb]上的位置可用分割点espi与va的距离占路段[va,vb]总长度的比例

Figure GDA0004146562840000036
(以下称为分割点espi的路段[va,vb]占比)来表示。其中/>
Figure GDA0004146562840000039
对应路段起点va，/>
Figure GDA0004146562840000037
对应路段终点vb。(332) The position of the split point es pi on the road section [v a , v b ] can be the ratio of the distance between the split point es pi and v a to the total length of the road segment [v a , v b ]
Figure GDA0004146562840000036
(hereinafter referred to as the proportion of the section [v a , v b ] of the split point es pi ). where />
Figure GDA0004146562840000039
Corresponding to the starting point v a of the road segment, />
Figure GDA0004146562840000037
Corresponding to the end point v b of the road segment.

设路段距离分布函数为

Figure GDA0004146562840000038
表示路段上点i和点j之间的距离；Let the road section distance distribution function be
Figure GDA0004146562840000038
Indicates the distance between point i and point j on the road segment;

分割点espi的位置计算公式如下：The formula for calculating the position of the split point es pi is as follows:

Figure GDA00041465628400000310
Figure GDA00041465628400000310

分割点espi距离路段起点va的距离计算公式如下：The formula for calculating the distance between the split point es pi and the starting point v a of the road segment is as follows:

Figure GDA00041465628400000311
Figure GDA00041465628400000311

Figure GDA00041465628400000312
——分割点espi的路段[va,vb]占比；
Figure GDA00041465628400000312
——the proportion of road section [v a , v b ] at the split point es pi ;

Figure GDA00041465628400000313
——乘客需求点pi到路段起点va的最短路距离；
Figure GDA00041465628400000313
——The shortest distance from the passenger demand point p i to the starting point v a of the road segment;

Figure GDA00041465628400000314
——乘客需求点pi到路段终点vb的最短路距离；
Figure GDA00041465628400000314
——The shortest distance from the passenger demand point p i to the end point v b of the road segment;

[va,vb]——路段[va,vb]的长度；[v a , v b ]——the length of road section [v a , v b ];

Figure GDA00041465628400000315
——分割点espi到va的距离；
Figure GDA00041465628400000315
- the distance from the split point es pi to v a ;

(334)对乘客需求点集合Pi中的所有对象，可求出其对应于路段[va,vb]上的分割点集合为

Figure GDA00041465628400000316
(334) For all objects in the passenger demand point set P i , the set of segmentation points corresponding to the road section [v a , v b ] can be calculated as
Figure GDA00041465628400000316

进一步的，本发明中，步骤(4)中，对于可能存在于路段[va,vb]上的拼车站点x，计算分析区内所有乘客需求点到站点x的最短路距离，将距离求和，来确定针对该路段的最优站点位置，具体步骤如下：Further, in the present invention, in step (4), for the carpooling site x that may exist on the road section [v a , v b ], calculate the shortest distance from all passenger demand points in the analysis area to the site x, and calculate the distance and to determine the optimal site location for this section, the specific steps are as follows:

初始化，最短路距离集合

Figure GDA00041465628400000317
Initialization, shortest distance collection
Figure GDA00041465628400000317

(41)取路段[va,vb]上任意一点x作为拼车站点，设站点x的路段[va,vb]占比为θ；(41) Take any point x on the road section [v a , v b ] as the carpooling site, and set the proportion of the road section [v a , v b ] at site x to be θ;

(42)结合步骤(32)和步骤(333)所述，可知当

Figure GDA0004146562840000041
时，此时乘客需求点pi到站点x最短路必经由起点va，最短路长度表示为/>
Figure GDA0004146562840000042
当
Figure GDA0004146562840000043
时，此时乘客需求点pi到站点x最短路径必经由终点vb，最短路长度为
Figure GDA0004146562840000044
(42) In combination with step (32) and step (333), it can be seen that when
Figure GDA0004146562840000041
, the shortest path from passenger demand point p i to station x must pass through the starting point v a , and the shortest path length is expressed as />
Figure GDA0004146562840000042
when
Figure GDA0004146562840000043
, the shortest path from passenger demand point p i to station x must pass through the terminal point v b , and the shortest path length is
Figure GDA0004146562840000044

则从乘客需求点pi到站点x最短路径距离可表示为如下的线性分段函数，Then the shortest path distance from passenger demand point p i to station x can be expressed as the following linear piecewise function,

Figure GDA0004146562840000045
Figure GDA0004146562840000045

(43)以路网分析区Zi内所有乘客需求点集合Pi为对象，重复步骤(42)操作，计算Pi中每个对象到站点的最短路径距离，结果存入集合Dθ[va,vb]中，记为(43) Taking all the passenger demand point set P i in the road network analysis area Z i as the object, repeat step (42) to calculate the shortest path distance from each object in P i to the station, and store the result in the set D θ [v a , v b ], recorded as

Figure GDA0004146562840000046
Figure GDA0004146562840000046

(44)将距离集合中的元素求和，记为∑Dθ[va,vb]；(44) Sum the elements in the distance set, which is recorded as ∑D θ [v a , v b ];

进一步的，本发明中，步骤(5)中，对路网分析区Zi中其它路段重复步骤(3)和步骤(4)的操作，再比较各路段的最短距离之和，确定最优站点的所在的路段和位置，具体步骤如下：Further, in the present invention, in step (5), the operations of step (3) and step (4) are repeated for other road sections in the road network analysis area Zi , and then the sum of the shortest distances of each road section is compared to determine the optimal site The road section and location of the road, the specific steps are as follows:

初始化，距离和集合

Figure GDA0004146562840000047
和最小距离集合/>
Figure GDA0004146562840000048
Initialization, distances and collections
Figure GDA0004146562840000047
and minimum distance set />
Figure GDA0004146562840000048

(51)对路网分析区Zi中路段集合Ei中其他元素重复步骤(3)和步骤(4)中对路段[va,vb]的相同操作，分别将距离求和得到的值存入集合D中，则D＝{∑Dθ[e1],∑Dθ[e2],∑Dθ[e3]…}(51) Repeat steps (3) and (4) for the other elements in the road segment set E i in the road network analysis area Z i to the road segment [v a , v b ] in step (3) and step (4), respectively sum the values obtained by the distance Stored in the set D, then D={∑D θ [e 1 ],∑D θ [e 2 ],∑D θ [e 3 ]…}

(52)记sd(e1)＝min∑Dθ[e1]，计算∑Dθ[e1]的最小值，并记录sd(e1)值和对应的θ值；(52) Record sd(e 1 )=min∑D θ [e 1 ], calculate the minimum value of ∑D θ [e 1 ], and record the sd(e 1 ) value and the corresponding θ value;

(53)同样的，类似对路段e1的操作，分别计算集合D中所有元素的最小值，结果存入集合sd中，即sd＝{sd(e1),sd(e2),sd(e3),sd(e4)…}，并记录各自对应的θ值；(53) Similarly, similar to the operation on road section e 1 , the minimum value of all elements in the set D is calculated respectively, and the result is stored in the set sd, that is, sd={sd(e 1 ), sd(e 2 ), sd( e 3 ),sd(e 4 )…}, and record their corresponding θ values;

(54)比较集合sd中的所有元素，最小的元素值对应的路段和θ值即为路网分析区Zi中拼车站点x存在的最优路段及位置。(54) Comparing all the elements in the set sd, the road section and θ value corresponding to the smallest element value are the optimal road section and location of the carpool site x in the road network analysis area Z i .

与现有技术相比，本发明的技术方案具有以下有益效果：Compared with the prior art, the technical solution of the present invention has the following beneficial effects:

1.本发明能够基于乘客预约需求数据对拼车站点进行合理布设，填补了网约拼车站点选址方法的空白，为当前站点拼车服务中的站点选址层面提供相应的参考和方法支撑。1. The present invention can rationally arrange carpooling stations based on passenger reservation demand data, fills the gap in site selection methods for online carpooling sites, and provides corresponding reference and method support for site site selection in current site carpooling services.

2.本发明提出的拼车站点选址方法依托于真实道路网络环境，摒弃了传统人为经验主观设置调整方法的弊端，确保了拼车站点布设的科学性、准确性、合理性和有效性。2. The site selection method for carpooling stations proposed by the present invention relies on the real road network environment, abandons the disadvantages of the traditional subjective setting adjustment method based on human experience, and ensures the scientificity, accuracy, rationality and effectiveness of carpooling station layout.

3.本发明基于路段分割点对任一条路段的拼车站点位置进行优化，再比较各路段的结果来确定最终的最优站点所在路段及位置，方法合理且计算简便。3. The present invention optimizes the location of the carpooling site of any road section based on the road section segmentation point, and then compares the results of each road section to determine the road section and location of the final optimal site. The method is reasonable and the calculation is simple.

附图说明Description of drawings

图1是本发明的流程图。Figure 1 is a flow chart of the present invention.

图2是本发明所述的实际路网结构。Fig. 2 is the actual road network structure described in the present invention.

图3是本发明所述的路网分析区Z2。Fig. 3 is the road network analysis area Z 2 of the present invention.

具体实施方式Detailed ways

下面结合说明书附图和实施例，对本发明的技术方案作进一步详细说明。The technical solutions of the present invention will be described in further detail below in conjunction with the accompanying drawings and embodiments.

实施例1：参见图1，一种基于实际路网环境的网约拼车站点选址方法，包括以下步骤：Embodiment 1: Referring to Fig. 1, a site selection method based on the actual road network environment for carpooling site, comprising the following steps:

(1)利用K-means聚类法对乘客预约需求点进行分组，并确定各分组的聚类中心；(1) Use the K-means clustering method to group passenger reservation demand points, and determine the cluster center of each group;

(2)根据所述各分组乘客需求点和聚类中心的空间位置，确定各分组对应的实际路网分析区；(2) According to the spatial position of each grouping passenger demand point and the clustering center, determine the actual road network analysis area corresponding to each grouping;

(3)取路网分析区Zi中任一路段[va,vb]，计算该分组所有乘客需求点对应的路段[va,vb]分割点；(3) Take any road section [v a , v b ] in the road network analysis area Z i , and calculate the division point of the road section [v a , v b ] corresponding to all passenger demand points in this group;

(4)对于可能存在于路段[va,vb]上的拼车站点x，计算分析区内所有乘客需求点到站点x的最短路距离，并将距离求和，来确定针对该路段的最优站点位置；(4) For the carpooling site x that may exist on the road segment [v a , v b ], calculate the shortest distance from all passenger demand points in the analysis area to the site x, and sum the distances to determine the shortest distance for this road segment Excellent site location;

(5)对路网分析区Zi中其它路段重复步骤(3)和步骤(4)的操作，再比较各路段的最短距离之和，确定最优站点的所在的路段和位置。(5) Repeat steps (3) and (4) for other road sections in the road network analysis area Zi , and then compare the sum of the shortest distances of each road section to determine the road section and location of the optimal site.

进一步的，本发明中，步骤(1)中，聚类中心点个数确定的具体步骤为：Further, in the present invention, in step (1), the specific steps for determining the number of cluster center points are:

(11)收集乘客预约需求点的空间位置坐标信息，包括：上车点和下车点经纬度坐标；(11) Collect the spatial position coordinate information of the passenger reservation demand point, including: the longitude and latitude coordinates of the boarding point and the getting off point;

(12)基于K-means聚类算法，当聚类中心为K时，计算每个聚类范围内的所有乘客需求点与对应聚类中心Ki的欧式距离，取距离最大值

Figure GDA0004146562840000051
(12) Based on the K-means clustering algorithm, when the cluster center is K, calculate the Euclidean distance between all passenger demand points within each cluster range and the corresponding cluster center Ki , and take the maximum distance
Figure GDA0004146562840000051

(13)对于每个聚类中心范围，以拼车站点服务半径R为约束，判断步骤(12)计算得到的距离最大值

Figure GDA0004146562840000052
是否大于R。若否，则跳过步骤(14)，此时对应的K值即为聚类中心点个数。(13) For the range of each cluster center, with the service radius R of the carpooling station as the constraint, the maximum distance calculated in the judgment step (12)
Figure GDA0004146562840000052
Is it greater than R. If not, step (14) is skipped, and the corresponding K value at this time is the number of cluster center points.

(14)取K＝K+1，重复步骤(12)和步骤(13)。(14) Take K=K+1, repeat step (12) and step (13).

本发明中，步骤(13)中，拼车站点服务半径确定方法如下：In the present invention, in step (13), the method for determining the service radius of the carpooling site is as follows:

站点服务半径R为乘客最大步行范围，取500m，站点服务范围是以聚类中心为圆心，以R为半径向外辐射的圆形区域范围。The station service radius R is the maximum walking range of passengers, which is 500m. The station service range is a circular area with the cluster center as the center and R as the radius radiating outward.

本发明中，步骤(2)中，各分组对应的实际路网分析区确定方法如下：In the present invention, in step (2), the method for determining the actual road network analysis area corresponding to each grouping is as follows:

设UNIT为路网节点能构成的最小封闭多边形，为最小路网单元；Let UNIT be the smallest closed polygon that can be formed by road network nodes, which is the smallest road network unit;

路网分析区即为包含一个聚类范围所有乘客需求点的最小实际路网区域；The road network analysis area is the smallest actual road network area including all passenger demand points within a cluster range;

(21)对一个聚类范围Ki内的乘客需求点进行判断，若其位于路网单元UNIT内或边界处，则记录该单元包含的节点ni(包括顶点)和路段ei(包括边界)，路段也可用其端点表示，如路段[v1,v2]；(21) Judge the passenger demand point within a cluster range K i , if it is located in the road network unit UNIT or at the boundary, record the node n i (including the vertex) and road section e i (including the boundary) contained in the unit ), the road section can also be represented by its endpoint, such as road section [v 1 ,v 2 ];

(22)得到包含聚类范围Ki内所有需求点的节点集Ni＝{n1,n2,n3…}和路段集Ei＝{e1,e2,e3…}；(22) Obtain the node set N i ={n 1 ,n 2 ,n 3 ...} and the road segment set E i ={e 1 ,e 2 ,e 3 ...} containing all demand points within the clustering range K i ;

(23)路网分析区Zi用图论方法可表示Zi＝(Ni，Ei)。(23) The road network analysis area Z i can be represented by graph theory method as Z i = (N i , E i ).

本发明中，步骤(3)中，乘客需求点对应的路段分割点确定方法如下：Among the present invention, in step (3), the method for determining the section segmentation point corresponding to the passenger demand point is as follows:

说明：最短路距离均采用实际网络距离，而不是欧几里得距离；Note: The shortest distance uses the actual network distance, not the Euclidean distance;

va和vb代表一个路段两端点，路段及路段长度均可用[va,vb]表示；pi和pj之间的最短路用

Figure GDA0004146562840000061
表示；若pi和pj之间的最短路经过点va和点vb，则pi和pj之间的最短路可用
Figure GDA0004146562840000062
表示；v a and v b represent the two ends of a road section, and the road section and the length of the road section can be represented by [v a , v b ]; the shortest path between p i and p j is represented by
Figure GDA0004146562840000061
means; if the shortest path between p i and p j passes through point v a and point v b , then the shortest path between p i and p j is available
Figure GDA0004146562840000062
express;

(31)由所述的步骤(23)可知，一个路网分析区Zi中含有节点数Ni，路段数Ei，含有的乘客需求点集合为Pi＝{p1,p2,p3…}；(31) From the above step (23), it can be seen that a road network analysis area Z i contains the number of nodes N i and the number of road sections E i , and the set of passenger demand points contained in it is P i ={p 1 ,p 2 ,p 3 ...};

(32)对于路段[va,vb]([va,vb]∈Ei)，以乘客需求点pi(pi∈Pi)为起点，分别以路段[va,vb]的两端点va和vb为终点，运用Dijkstra算法分别计算最短路径距离，记为

Figure GDA0004146562840000063
和
Figure GDA0004146562840000064
(32) For the road segment [v a , v b ]([v a , v b ]∈E i ), starting from the passenger demand point p i (p i ∈ P i ), the road segment [v a , v b ]’s two ends v a and v b are the end points, and the Dijkstra algorithm is used to calculate the shortest path distance respectively, denoted as
Figure GDA0004146562840000063
and
Figure GDA0004146562840000064

(33)以pi、va、vb为三角形的顶点，以

Figure GDA0004146562840000065
[va,vb]，/>
Figure GDA0004146562840000066
为三角形的边，利用三角形不等式关系寻找路段[va,vb]的分割点。(33) Take p i , v a , v b as the vertices of the triangle, and
Figure GDA0004146562840000065
[v a , v b ], />
Figure GDA0004146562840000066
is the side of the triangle, use the triangle inequality relationship to find the segmentation point of the road section [v a , v b ].

本发明中，步骤(33)中，利用三角形不等式关系寻找路段[va,vb]的分割点，具体步骤如下：Among the present invention, in step (33), utilize triangle inequality relation to find the division point of section [v a , v b ], concrete steps are as follows:

(331)在三角形pivavb中，有以下关系成立：(331) In the triangle p i v a v b , the following relations hold:

Figure GDA0004146562840000067
Figure GDA0004146562840000067

Figure GDA0004146562840000068
Figure GDA0004146562840000068

则对于乘客需求点pi来说，在路段[va,vb]存在的一个分割点espi，使得Then for the passenger demand point p i , there is a split point es pi in the section [v a , v b ], such that

Figure GDA0004146562840000069
Figure GDA0004146562840000069

(332)分割点espi在路段[va,vb]上的位置可用分割点espi与va的距离占路段[va,vb]总长度的比例

Figure GDA00041465628400000610
(以下称为分割点espi的路段[va,vb]占比)来表示。其中/>
Figure GDA00041465628400000611
对应路段起点va，/>
Figure GDA00041465628400000612
对应路段终点vb。(332) The position of the split point es pi on the road section [v a , v b ] can be the ratio of the distance between the split point es pi and v a to the total length of the road segment [v a , v b ]
Figure GDA00041465628400000610
(hereinafter referred to as the proportion of the section [v a , v b ] of the split point es pi ). where />
Figure GDA00041465628400000611
Corresponding to the starting point v a of the road segment, />
Figure GDA00041465628400000612
Corresponding to the end point v b of the road segment.

设路段距离分布函数为

Figure GDA00041465628400000613
表示路段上点i和点j之间的距离；Let the road section distance distribution function be
Figure GDA00041465628400000613
Indicates the distance between point i and point j on the road segment;

分割点espi的位置计算公式如下：The formula for calculating the position of the split point es pi is as follows:

Figure GDA00041465628400000614
Figure GDA00041465628400000614

分割点espi距离路段起点va的距离计算公式如下：The formula for calculating the distance between the split point es pi and the starting point v a of the road segment is as follows:

Figure GDA0004146562840000071
Figure GDA0004146562840000071

Figure GDA0004146562840000072
——分割点espi的路段[va,vb]占比；
Figure GDA0004146562840000072
——the proportion of road section [v a , v b ] at the split point es pi ;

Figure GDA0004146562840000073
——乘客需求点pi到路段起点va的最短路距离；
Figure GDA0004146562840000073
——The shortest distance from the passenger demand point p i to the starting point v a of the road segment;

Figure GDA0004146562840000074
——乘客需求点pi到路段终点vb的最短路距离；
Figure GDA0004146562840000074
——The shortest distance from the passenger demand point p i to the end point v b of the road segment;

[va,vb]——路段[va,vb]的长度；[v a , v b ]——the length of road section [v a , v b ];

Figure GDA0004146562840000075
——分割点espi到va的距离；
Figure GDA0004146562840000075
- the distance from the split point es pi to v a ;

(334)对乘客需求点集合Pi中的所有对象，可求出其对应于路段[va,vb]上的分割点集合为

Figure GDA0004146562840000076
(334) For all objects in the passenger demand point set P i , the set of segmentation points corresponding to the road section [v a , v b ] can be calculated as
Figure GDA0004146562840000076

本发明中，步骤(4)中，对于可能存在于路段[va,vb]上的拼车站点x，计算分析区内所有乘客需求点到站点x的最短路距离，将距离求和，来确定针对该路段的最优站点位置，具体步骤如下：In the present invention, in step (4), for the carpooling site x that may exist on the road section [v a , v b ], calculate the shortest distance from all passenger demand points in the analysis area to the site x, and sum the distances to obtain To determine the optimal site location for this section, the specific steps are as follows:

初始化，最短路距离集合

Figure GDA0004146562840000077
Initialization, shortest distance collection
Figure GDA0004146562840000077

(41)取路段[va,vb]上任意一点x作为拼车站点，设站点x的路段[va,vb]占比为θ；(41) Take any point x on the road section [v a , v b ] as the carpooling site, and set the proportion of the road section [v a , v b ] at site x to be θ;

(42)结合步骤(32)和步骤(333)所述，可知当

Figure GDA0004146562840000078
时，此时乘客需求点pi到站点x最短路必经由起点va，最短路长度表示为/>
Figure GDA0004146562840000079
当
Figure GDA00041465628400000710
时，此时乘客需求点pi到站点x最短路径必经由终点vb，最短路长度为
Figure GDA00041465628400000711
(42) In combination with step (32) and step (333), it can be seen that when
Figure GDA0004146562840000078
, the shortest path from passenger demand point p i to station x must pass through the starting point v a , and the shortest path length is expressed as />
Figure GDA0004146562840000079
when
Figure GDA00041465628400000710
, the shortest path from passenger demand point p i to station x must pass through the terminal point v b , and the shortest path length is
Figure GDA00041465628400000711

则从乘客需求点pi到站点x最短路径距离可表示为如下的线性分段函数，Then the shortest path distance from passenger demand point p i to station x can be expressed as the following linear piecewise function,

Figure GDA00041465628400000712
Figure GDA00041465628400000712

(43)以路网分析区Zi内所有乘客需求点集合Pi为对象，重复步骤(42)操作，计算Pi中每个对象到站点的最短路径距离，结果存入集合Dθ[va,vb]中，记为(43) Taking all the passenger demand point set P i in the road network analysis area Z i as the object, repeat step (42) to calculate the shortest path distance from each object in P i to the station, and store the result in the set D θ [v a , v b ], recorded as

Figure GDA00041465628400000713
Figure GDA00041465628400000713

(44)将距离集合中的元素求和，记为∑Dθ[va,vb]；(44) Sum the elements in the distance set, which is recorded as ∑D θ [v a , v b ];

进一步的，本发明中，步骤(5)中，对路网分析区Zi中其它路段重复步骤(3)和步骤(4)的操作，再比较各路段的最短距离之和，确定最优站点的所在的路段和位置，具体步骤如下：Further, in the present invention, in step (5), the operations of step (3) and step (4) are repeated for other road sections in the road network analysis area Zi , and then the sum of the shortest distances of each road section is compared to determine the optimal site The road section and location of the road, the specific steps are as follows:

初始化，距离和集合

Figure GDA00041465628400000714
和最小距离集合/>
Figure GDA00041465628400000715
Initialization, distances and collections
Figure GDA00041465628400000714
and minimum distance set />
Figure GDA00041465628400000715

(51)对路网分析区Zi中路段集合Ei中其他元素重复步骤(3)和步骤(4)中对路段[va,vb]的相同操作，分别将距离求和得到的值存入集合D中，则D＝{∑Dθ[e1],∑Dθ[e2],∑Dθ[e3]…}(51) Repeat steps (3) and (4) for the other elements in the road segment set E i in the road network analysis area Z i to the road segment [v a , v b ] in step (3) and step (4), respectively sum the values obtained by the distance Stored in the set D, then D={∑D θ [e 1 ],∑D θ [e 2 ],∑D θ [e 3 ]…}

(52)记sd(e1)＝min∑Dθ[e1]，计算∑Dθ[e1]的最小值，并记录sd(e1)值和对应的θ值；(52) Record sd(e 1 )=min∑D θ [e 1 ], calculate the minimum value of ∑D θ [e 1 ], and record the sd(e 1 ) value and the corresponding θ value;

(53)同样的，类似对路段e1的操作，分别计算集合D中所有元素的最小值，结果存入集合sd中，即sd＝{sd(e1),sd(e2),sd(e3),sd(e4)…}，并记录各自对应的θ值；(53) Similarly, similar to the operation on road section e 1 , the minimum value of all elements in the set D is calculated respectively, and the result is stored in the set sd, that is, sd={sd(e 1 ), sd(e 2 ), sd( e 3 ),sd(e 4 )…}, and record their corresponding θ values;

(54)比较集合sd中的所有元素，最小的元素值对应的路段和θ值即为路网分析区Zi中拼车站点x存在的最优路段及位置。(54) Comparing all the elements in the set sd, the road section and θ value corresponding to the smallest element value are the optimal road section and location of the carpool site x in the road network analysis area Z i .

应用实施例1：参见图1-图3，一种基于实际路网环境的网约拼车站点选址方法，包括以下步骤：Application Example 1: Referring to Fig. 1-Fig. 3, a site selection method based on the actual road network environment for online carpooling sites includes the following steps:

(1)利用K-means聚类法对乘客预约需求点进行分组，并确定各分组的聚类中心。本实施例选取了部分真实道路网，如图2所示，路网包含11个节点，19条路段。在路网上随机产生乘客拼车预约需求点。通过乘客最大步行距离范围约束，采用K-means聚类法可得聚类中心个数为3，编号分别为K1、K2、K3。(1) Use the K-means clustering method to group passenger reservation demand points, and determine the cluster center of each group. In this embodiment, part of the real road network is selected. As shown in FIG. 2 , the road network includes 11 nodes and 19 road sections. Randomly generate passenger carpool reservation demand points on the road network. Through the constraints of the maximum walking distance of passengers, the number of cluster centers can be obtained by using the K-means clustering method to be 3, and the numbers are K 1 , K 2 , and K 3 .

(2)根据所述各分组乘客需求点和聚类中心的空间位置，确定各分组对应的实际路网分析区。这里及后续内容均以聚类中心K2为例进行详细说明，其他聚类范围操作类似。通过对聚类中心K2范围内的需求点(编号为p1、p2、p3)存在路网范围进行判断，可确定其对应的路网分析区为Z2，如图3所示。路网分析区Z2包含的节点集合N2和路段集合E2分别为N2＝{V5,V4,V6,V7]，E2＝{[V5,V4],[V4,V6],[V6,V7],[V5,V6],[V5,V7]}。(2) Determine the actual road network analysis area corresponding to each group according to the spatial positions of passenger demand points and cluster centers of each group. Here and the following content are described in detail by taking the cluster center K 2 as an example, and the operation of other cluster ranges is similar. By judging the existence of the road network range of the demand points (numbered p 1 , p 2 , p 3 ) within the range of the cluster center K 2 , it can be determined that the corresponding road network analysis area is Z 2 , as shown in Figure 3 . The node set N 2 and road segment set E 2 contained in the road network analysis area Z 2 are respectively N 2 ={V5,V4,V6,V7], E 2 ={[V5,V4],[V4,V6],[V6 ,V7],[V5,V6],[V5,V7]}.

(3)取路网分析区Z2中任一路段[V5,V6]，计算该分组所有乘客需求点对应的路段[V5,V6分割点。分析区Z2中路段权值分别为[V5,V4]＝6，[V4,V6]＝7，[V6,V7]＝4，[V5,V6]＝7，[V5,V7]＝5。乘客需求点p1、p2、p3在路段上的位置分别为[V5,p1]＝4,[V4,p2]＝3,[V5,p3]＝2。(3) Take any road section [V5, V6] in the road network analysis area Z 2 , and calculate the road section [V5, V6 segmentation point corresponding to all passenger demand points in this group. The link weights in the analysis area Z 2 are [V5, V4]=6, [V4, V6]=7, [V6, V7]=4, [V5, V6]=7, [V5, V7]=5. The positions of passenger demand points p 1 , p 2 , and p 3 on the road section are respectively [V5,p1]=4, [V4,p2]=3, and [V5,p3]=2.

乘客需求点p1对应的路段[V5,V6]分割点计算如下：The section [V5, V6] segmentation point corresponding to passenger demand point p 1 is calculated as follows:

Figure GDA0004146562840000081
Figure GDA0004146562840000081

同理，可计算乘客需求点p2和p3对应的路段[V5,V6]分割点为

Figure GDA0004146562840000082
In the same way, it can be calculated that the segmentation point of the section [V5, V6] corresponding to passenger demand points p 2 and p 3 is
Figure GDA0004146562840000082

(4)对于可能存在于路段[V5,V6]上的拼车站点x，计算分析区内所有乘客需求点到站点x的最短路距离，将距离求和，来确定针对该路段的最优站点位置。各乘客需求点到站点x的最短路距离可表示为(4) For the carpool site x that may exist on the road segment [V5, V6], calculate the shortest distance from all passenger demand points in the analysis area to the site x, and sum the distances to determine the optimal site location for this road segment . The shortest distance from each passenger demand point to station x can be expressed as

Figure GDA0004146562840000083
Figure GDA0004146562840000083

Figure GDA0004146562840000091
Figure GDA0004146562840000091

Figure GDA0004146562840000092
Figure GDA0004146562840000092

将距离求和得到∑Dθ[V5,V6]为Sum the distances to get ∑D θ [V5,V6] as

Figure GDA0004146562840000093
Figure GDA0004146562840000093

(5)对路网分析区Z2中其它路段重复步骤(3)和步骤(4)的操作，再比较各路段的最短距离之和，确定最优站点的所在的路段和位置。对于分段函数∑Dθ[V5,V6]来说， 由于sd([V5,V6])＝min∑Dθ[V5,V6]，当θ＝4/7时，可得sd([V5,V6])＝13；(5) Repeat step (3) and step (4) for other road sections in the road network analysis area Z 2 , and then compare the sum of the shortest distances of each road section to determine the road section and location of the optimal site. For the piecewise function ∑D θ [V5,V6], since sd([V5,V6])=min∑D θ [V5,V6], when θ=4/7, sd([V5, V6]) = 13;

相似的，可计算得到sd([V5,V7])＝19，sd([V4,V5])＝15，sd([V4,V6])＝18，sd([V6,V7])＝18；因此，集合sd＝{13,19,15,18}，最小元素为13，即为sd([V5,V6])；Similarly, it can be calculated that sd([V5,V7])=19, sd([V4,V5])=15, sd([V4,V6])=18, sd([V6,V7])=18; Therefore, the set sd={13,19,15,18}, the smallest element is 13, which is sd([V5,V6]);

在路网分析区Z2中，拼车站点x存在的最优选址为路段[V5,V6]上且距点V5距离为4/7路段长度的位置处。In the road network analysis area Z 2 , the optimal location of the carpool station x is on the road section [V5, V6] and the distance from point V5 is 4/7 of the length of the road section.

对其它聚类中心范围确定最优拼车站点位置操作均与上述K2类似。The operation of determining the optimal carpool site location for other cluster center ranges is similar to the above K2 .

上述实施例仅是本发明的优选实施方式，应当指出：对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以做出若干改进和等同替换，这些对本发明权利要求进行改进和等同替换后的技术方案，均落入本发明的保护范围。The foregoing embodiments are only preferred implementations of the present invention. It should be pointed out that for those of ordinary skill in the art, without departing from the principles of the present invention, several improvements and equivalent replacements can be made, which are important to the rights of the present invention. Technical solutions requiring improvement and equivalent replacement all fall within the protection scope of the present invention.

Claims (8)

1. The network about splicing station site selection method based on the actual road network environment is characterized by comprising the following steps of:
(1) Grouping the passenger reservation demand points by using a K-means clustering method, and determining a clustering center of each grouping;
(2) Determining an actual road network analysis area corresponding to each group according to the space positions of the demand points of each group passenger and the clustering center;
(3) Road network analysis zone Z i Any road section [ v ] a ,v b ]Calculating the road section [ v ] corresponding to all the passenger demand points of the group a ,v b ]Dividing points;
(4) For existing in road section v a ,v b ]The method comprises the steps of calculating the shortest path distance from all passenger demand points to a station x in an analysis area at a carpooling station x, and summing the distances to determine the optimal station position for the road section;
(5) Analysis zone Z of road network i Repeating the operations of the step (3) and the step (4) on other road sections, comparing the sum of the shortest distances of the road sections, and determining the road section and the position of the optimal station.
2. The method for selecting the site of the network approximately splicing station based on the actual road network environment according to claim 1, wherein the specific steps in the step (1) are as follows:
(11) Collecting the space position coordinate information of the passenger reservation demand point, comprising: longitude and latitude coordinates of the get-on point and the get-off point;
(12) Based on a K-means clustering algorithm, when the clustering center is K, calculating all passenger demand points in each clustering range and corresponding clustering centers K i Is the Euclidean distance of (1) taking the maximum value of the distance
Figure QLYQS_1
(13) For each clustering center range, taking the spliced station point service radius R as a constraint, and judging the maximum distance value calculated in the step (12)
Figure QLYQS_2
If not, skipping step (14), wherein the corresponding K value is the number of clustering center points;
(14) Taking k=k+1, and repeating the step (12) and the step (13).
3. The method for selecting the network approximately spliced station points based on the actual road network environment according to claim 2, wherein the step (13) uses the spliced station point service range as a constraint, and comprises the following steps:
the station service radius R is the maximum walking range of passengers, 500m is taken, and the station service range is a circular area range which takes the cluster center as the center and takes R as the radius to radiate outwards.
4. The network approximately splicing station location method based on the actual road network environment according to claim 1, wherein in the step (2), the determination method of the actual road network analysis area corresponding to each packet is as follows:
setting UNIT as the minimum closed polygon which can be formed by the road network nodes and as the minimum road network UNIT; the road network analysis area is the minimum actual road network area containing all passenger demand points in a clustering range;
(21) For a cluster range K i Judging the passenger demand point in the network UNIT, if it is in the network UNIT or at the boundary, recording the node n contained in the UNIT i And road segment e i ；
(22) Obtaining the cluster containing range K i Section of all demand points inPoint set N i ＝{n 1 ,n 2 ,n 3 … and road segment set E i ＝{e 1 ,e 2 ,e 3 …}；
(23) Road network analysis zone Z i The Z can be represented by a graph representation method i ＝(N i ,E i )。
5. The method for selecting the network pinch points based on the actual road network environment according to claim 4, wherein in the step (3), the method for determining the road segment division points corresponding to the passenger demand points is as follows:
wherein the shortest distance adopts the actual road network distance,
v a and v b Representing two end points of a road section, the length of the road section can be [ v ] a ,v b ]A representation; passenger demand point p i And p j For shortest path between
Figure QLYQS_3
A representation; if p i And p j The shortest path point v between a Sum point v b Then p i And p j The shortest possible between +.>
Figure QLYQS_4
A representation;
(31) From the above step (23), a road network analysis zone Z i Contains node number N i Road segment number E i The set of the included passenger demand points is P i ＝{p 1 ,p 2 ,p 3 …}；
(32) For road section [ v a ,v b ]Wherein [ v ] a ,v b ]∈E i At the passenger demand point p i ，p i ∈P i Starting from the road segments [ v ] a ,v b ]Two end points v of (2) a And v b As the end point, the Dijkstra algorithm is used to calculate the shortest path distance respectively, which is recorded as
Figure QLYQS_5
And
Figure QLYQS_6
(33) At p i 、v a 、v b Is the vertex of triangle, to
Figure QLYQS_7
[v a ,v b ]，/>
Figure QLYQS_8
For triangle side, find road segment [ v ] using triangle inequality relation a ,v b ]Is defined by the dividing points of the pair.
6. The method for selecting a station point for a network about splicing based on an actual road network environment according to claim 5, wherein in said step (33), a triangle inequality relation is used to find a road section [ v ] a ,v b ]The specific steps are as follows:
(331) In triangle p i v a v b The following relationship holds:
Figure QLYQS_9
Figure QLYQS_10
then for the passenger demand point p i For the road section [ v ] a ,v b ]There is a dividing point es pi So that
Figure QLYQS_11
(332) Dividing points es pi In road section [ v ] a ,v b ]Available segmentation points es for positions on pi And v a The distance of the road section [ v ] a ,v b ]Ratio of total length
Figure QLYQS_12
Is hereinafter referred to as a division point es pi Road segment [ v ] a ,v b ]Duty ratio of->
Figure QLYQS_13
Corresponding road segment origin v a ，/>
Figure QLYQS_14
Corresponding road segment end v b ；
Let the road distance distribution function be
Figure QLYQS_15
Representing the distance between point i and point j on the road segment;
dividing points es pi The position calculation formula of (2) is as follows:
Figure QLYQS_16
dividing points es pi Distance segment origin v a The distance calculation formula of (2) is as follows:
Figure QLYQS_17
Figure QLYQS_18
-segmentation points es pi Road segment [ v ] a ,v b ]A duty cycle;
Figure QLYQS_19
passenger demand point p i To the road segment start point v a Is the shortest distance of (2);
Figure QLYQS_20
passenger demand point p i To road end v b Is the shortest distance of (2);
[v a ,v b ]road section [ v ] a ,v b ]Is a length of (2);
Figure QLYQS_21
-segmentation points es pi To v a Is a distance of (2);
(334) Set of demand points for passengers P i All the objects in the map can be found to correspond to the road segment v a ,v b ]The division point duty ratio set is
Figure QLYQS_22
7. The method for network pinch point location based on actual road network environment according to claim 6, wherein in the step (4), for the road segment [ v ] a ,v b ]The shortest path distance from all passenger demand points to the station x in the analysis area is calculated, and the distances are summed to determine the optimal station position for the road section, and the method specifically comprises the following steps:
initializing, shortest distance set
Figure QLYQS_23
(41) Get the road section [ v ] a ,v b ]Any point x is taken as a spelling station point, and a road section v of the station x is set a ,v b ]The duty ratio is theta;
(42) As described in connection with step (32) and step (333), it is known that when
Figure QLYQS_24
At this time, the passenger demand point p i Shortest to site x must go through start point v a The shortest length is denoted +.>
Figure QLYQS_25
When->
Figure QLYQS_26
At this time, the passenger demand point p i The shortest path to site x must be via endpoint v b The shortest length is denoted +.>
Figure QLYQS_27
From the passenger demand point p i The shortest path distance to site x can be expressed as a linear piecewise function,
Figure QLYQS_28
(43) Road network analysis zone Z i Set of all passenger demand points P in i Repeating the operation of step (42) for the object to calculate P i The shortest path distance from each object to the site, the result is stored in the set D θ [v a ,v b ]In (a) is marked as
Figure QLYQS_29
(44) Will shortest distance set D θ [v a ,v b ]The sum of the elements in (a) is denoted as Sigma D θ [v a ,v b ]。
8. The method for selecting a station point for network splicing based on actual road network environment according to claim 1, wherein in the step (5), the road network analysis zone Z is i Repeating the operations of the step (3) and the step (4) on other road sections, comparing the sum of the shortest distances of the road sections, and determining the road section and the position of the optimal station, wherein the method comprises the following specific steps:
initializing, distance and collection
Figure QLYQS_30
And minimum distance set->
Figure QLYQS_31
(51) Analysis zone Z of road network i Road segment set E i Repeating the steps (3) and (4) for the road segment [ v ] a ,v b ]Respectively, the values obtained by summing the distances are stored in the set D, then d= { Σd θ [e 1 ],∑D θ [e 2 ],∑D θ [e 3 ]…}
(52) Sd (e) 1 )＝min∑D θ [e 1 ]Calculating Sigma D θ [e 1 ]And record sd (e) 1 ) A value and a corresponding θ value;
(53) Likewise, similar to road segment e 1 Respectively, the minimum values of all elements in the set D are calculated, and the result is stored in the set sd, i.e., sd= { sd (e 1 ),sd(e 2 ),sd(e 3 ),sd(e 4 ) …, and recording the respective corresponding θ values;
(54) Comparing all elements in the set sd, wherein the road section and theta value corresponding to the minimum element value are the road network analysis zone Z i The optimal road section and the optimal position of the middle carpooling station x.
CN201910580890.0A 2019-06-29 2019-06-29 Network about splicing station point location method based on actual road network environment Expired - Fee Related CN110458309B (en)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN201910580890.0A CN110458309B (en) 2019-06-29 2019-06-29 Network about splicing station point location method based on actual road network environment

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN201910580890.0A CN110458309B (en) 2019-06-29 2019-06-29 Network about splicing station point location method based on actual road network environment

Publications (2)

Publication Number Publication Date
CN110458309A CN110458309A (en) 2019-11-15
CN110458309B true CN110458309B (en) 2023-07-11

Family

ID=68481844

Family Applications (1)

Application Number Title Priority Date Filing Date
CN201910580890.0A Expired - Fee Related CN110458309B (en) 2019-06-29 2019-06-29 Network about splicing station point location method based on actual road network environment

Country Status (1)

Country Link
CN (1) CN110458309B (en)

Families Citing this family (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN115472008B (en) * 2022-08-30 2023-09-19 东南大学 Network vehicle travel space-time characteristic analysis method based on k-means clustering

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN105206046A (en) * 2015-10-10 2015-12-30 东南大学 Big-data-based taxi service station site selection and feasibility evaluation method
CN108734337A (en) * 2018-04-18 2018-11-02 北京交通大学 Based on the modified customization public transport rideshare website generation method of cluster centre
CN108764555A (en) * 2018-05-22 2018-11-06 浙江大学城市学院 A kind of shared bicycle based on Hadoop parks a site selecting method

Family Cites Families (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US8364515B1 (en) * 2005-12-30 2013-01-29 At&T Intellectual Property Ii, L.P. Method and system for facility location optimization

Patent Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN105206046A (en) * 2015-10-10 2015-12-30 东南大学 Big-data-based taxi service station site selection and feasibility evaluation method
CN108734337A (en) * 2018-04-18 2018-11-02 北京交通大学 Based on the modified customization public transport rideshare website generation method of cluster centre
CN108764555A (en) * 2018-05-22 2018-11-06 浙江大学城市学院 A kind of shared bicycle based on Hadoop parks a site selecting method

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
New spatial clustering-based models for optimal urban facility location considering geographical obstacles;Maryam Javadi 等;《Journal of Industrial Engineering International》;20140325;第1-12页 *

Also Published As

Publication number Publication date
CN110458309A (en) 2019-11-15

Similar Documents

Publication Publication Date Title
US11594137B2 (en) Method and apparatus for providing mobility insight data for points of interest
Modesti et al. A utility measure for finding multiobjective shortest paths in urban multimodal transportation networks
Sevtsuk et al. Predicting pedestrian flow along city streets: A comparison of route choice estimation approaches in downtown San Francisco
US10274329B2 (en) Method and apparatus for providing a minimum overlapping alternative path
US11430335B2 (en) Method and apparatus for providing large scale vehicle routing
Jiang et al. Computing the fewest-turn map directions based on the connectivity of natural roads
CN107101645B (en) A kind of paths planning method and path planning apparatus
Bucher et al. A heuristic for multi-modal route planning
US20200217680A1 (en) Generating and recommending customized traversal routes
US12123726B2 (en) Method and apparatus for ridesharing pickup wait time prediction
Hrnčíř et al. Generalised time-dependent graphs for fully multimodal journey planning
Liu et al. A distributed Markovian parking assist system
Meng et al. Street morphology and travel by dockless shared bicycles in Beijing, China
US20100198505A1 (en) Method for Representing Linear Features in a Location Content Management System
CN108332754A (en) Method for optimizing route, device, electronic equipment and computer storage media
Dibbelt Engineering algorithms for route planning in multimodal transportation networks
Albalawneh et al. Evaluation of Using Genetic Algorithm and ArcGIS for Determining the Optimal‐Time Path in the Optimization of Vehicle Routing Applications
CN110458309B (en) Network about splicing station point location method based on actual road network environment
CN107677277A (en) A kind of determining method of path based on dijkstra's algorithm
Anjum et al. Accessibility enhancement of mass transit system through GIS based modeling of feeder routes
US20180180431A1 (en) Determining Commute Tolerance Areas
Teimouri et al. Analysis of route choice based on path characteristics using Geolife GPS trajectories
CN113761397B (en) Recommendation method, system, equipment and storage medium for customizing passenger transport route
CN111854768B (en) Method and system for determining map route, terminal, and computer-readable storage medium
US12345535B2 (en) System and method for rideshare matching based on locality sensitive hashing

Legal Events

Date Code Title Description
PB01 Publication
PB01 Publication
SE01 Entry into force of request for substantive examination
SE01 Entry into force of request for substantive examination
GR01 Patent grant
GR01 Patent grant
CF01 Termination of patent right due to non-payment of annual fee
CF01 Termination of patent right due to non-payment of annual fee

Granted publication date: 20230711