CN104236569A - Method and device for determining optimal meeting point - Google Patents

Abstract

According to the present invention, a method for determining the optimal rendezvous point for a plurality of mobile bodies going to the same destination from different starting points and agreeing to rendezvous in advance is proposed, including: an acquisition step, acquiring the respective a start point and a destination; and a determining step of performing a route search based on the respective start points and destinations of the plurality of mobile bodies using map data, according to the sum of the costs of each route for each mobile body to reach the destination through the meeting point Approximate the minimum way to determine the meeting point as the optimal meeting point.

Description

Method and apparatus for determining an optimal meeting point

technical field

The present invention relates to a method and a device for determining the optimal meeting point for multiple mobile bodies going to the same destination from different starting points and agreeing to meet in advance. Multiple mobile bodies can go to the destination conveniently after meeting at the meeting point, and the total cost of multiple mobile bodies reaching the destination via the meeting point from different starting points can be minimized or approximately minimized.

Background technique

As a social animal, humans have a long history of walking in groups. In other words, traveling together can be understood as traveling together, that is, multiple people in the same or different places meet in advance and then go to the same destination together.

At present, when calculating the meeting point in advance and the corresponding route of each person, people generally select the meeting point in advance according to their own experience, and then use the route planning system on the Internet to calculate. Firstly, route planning is carried out for each person's starting point and the selected meeting point in advance, and then the route from the meeting point to the end point is planned. However, when people are not familiar with the traffic conditions in the geographical area involved, it is difficult for people to select this meeting point in advance according to their own experience, which may lead to a large difference between the obtained results and the best situation, and cause time delays. , monetary loss.

In the known technologies, patent documents such as US5802492, EP1357357, EP2533013, and EP1593938 all propose methods for route planning, each time planning a route for a single person from a single starting point to a single end point. That is to say, in the known technology, the user inputs the starting point of a route and the end point of a route on the corresponding interface, and after the system acquires the user's search request, it calculates the corresponding route planning from the starting point to the end point through different methods. It can include driving route planning, bus route planning, walking route planning, or multi-modal traffic route planning, etc.

In addition, existing known technologies also propose route planning from one starting point to multiple destinations, that is, route planning from one starting point to one destination via one or more passing points. Taking the patent document EP1193626 as a known technology as an example, this known technology proposes a route planning system, which can calculate a route planning starting from a certain starting point and passing through multiple passing points. The user can input the starting point, passing point or end point on the user interface of the system, and the system calculates the corresponding route through the corresponding method, and displays the route on the map of the user interface.

Contents of the invention

To sum up, the existing known technologies only provide route planning for personnel from a single starting point to one or more destinations. The disadvantage of the known technology is that when multiple people arrive at the same end point from different starting points, the known technology cannot provide corresponding route planning. In particular, when a user requires a route plan for a plurality of people from different starting points to a unified end point via an unspecified advance meeting point, the known technology cannot provide corresponding route plan.

In particular, for the situation where people from different places meet to go to the same destination, the people participating in the joint trip either choose to arrive at the destination separately, or meet at a certain place before arriving at the destination (hereinafter referred to as the meeting point in advance or meeting point) Then go to the finish line together. Here, the former can simply use the existing route planning system on the Internet to plan the routes of multiple people separately, that is, plan the routes for each person's starting point and end point separately.

In contrast, existing known technologies cannot perform route planning for the latter. The way that multiple people in different places meet at a certain place before arriving at the destination and then go to the destination together can firstly reduce the total transportation cost of the people and reduce carbon dioxide emissions. For example, people can drive to a certain meeting point in advance, Then take the same car to the finish line. Second, by walking with other people who are familiar with the route (such as one car leading another car), the time spent in traffic can be reduced and the terminal destination can be reached more conveniently.

The present invention has been proposed in order to overcome the above-mentioned drawbacks of the prior art. The purpose of the present invention is to propose a method and device for determining the optimal rendezvous point for a plurality of mobile bodies going to the same destination from different starting points and agreeing to meet in advance, not only by selecting the rendezvous point for the multiple mobile So that the multiple mobile bodies can go to the destination conveniently after meeting at the meeting point, and the total cost of the multiple mobile bodies reaching the destination via the meeting point from different starting points can be minimized or approximately minimized.

In order to achieve the above purpose, a method for determining the optimal meeting point for a plurality of mobile bodies going to the same destination from different starting points and agreeing to meet in advance is proposed, including: an acquisition step, acquiring the respective starting point and destination; and a determining step of using map data to search for a route according to the respective starting points and destinations of the plurality of mobile bodies, according to the cost of each route for each mobile body to reach the destination through the meeting point The sum is approximately minimized to determine the rendezvous point as the optimal rendezvous point.

Preferably, the cost is distance.

Preferably, the step of determining includes: using map data, respectively performing route retrieval starting from the respective starting points and the destinations of the plurality of mobile objects, and when it is detected that all these route retrievals have a common access point, The common access point is determined as the optimal meeting point.

Preferably, when performing route retrieval with the destination as the starting point, during the route retrieval process, the impassable road sections on the return journey are discarded, and the one-way road sections on the return journey are set as two-way passable road sections.

Preferably, the route retrieval uses a Dijkstra search algorithm for step-by-step retrieval.

Preferably, the rendezvous point is a point for the plurality of mobile bodies to set off for the destination after arriving at the rendezvous point.

Preferably, the rendezvous point is a point for the multiple mobile bodies to merge into a smaller number of mobile bodies after arriving at the rendezvous point, and then set off to the destination together.

In addition, according to the present invention, a device for determining the optimal rendezvous point for a plurality of mobile bodies going to the same destination from different starting points and agreeing to rendezvous in advance is proposed, including: an acquisition unit, which acquires the respective starting points and destinations; and a determination unit that uses map data to perform route searches based on the respective starting points and destinations of the plurality of mobile bodies, according to the respective routes of each mobile body passing through the meeting point to the destination. The sum of costs is approximated to be the smallest to determine the rendezvous point as the optimal rendezvous point.

As mentioned above, the present invention relates to a system for planning routes for multiple people traveling, and the system involved in the present invention provides corresponding route planning for multiple people traveling together at different starting points. The present invention particularly provides a route planning method, the planned route can guide multiple people to meet at a certain place on the way to the destination, and then arrive at the destination together, and by determining the optimal meeting point (meeting point) , it is possible to minimize or approximately minimize the total cost for multiple moving bodies to reach the destination via the meeting point from different starting points.

Description of drawings

The above objects, advantages and features of the present invention will become more apparent by referring to the following detailed description of preferred embodiments adopted in conjunction with the accompanying drawings, wherein:

Fig. 1 is a schematic diagram of a system structure according to the present invention.

Fig. 2 is a functional block diagram according to the present invention.

FIG. 3 is a diagram for describing a user interface of the present invention in detail.

FIG. 4 is a flow chart for describing in detail the process of how the system of the present invention obtains the relevant search information input by the user.

Fig. 5 is a flow chart for describing the process of the system making related calculations regarding whether to pre-set the meeting point in advance.

Fig. 6 is a flow chart for describing in detail the process of the system calculating the corresponding advance meeting point and the related route planning when the advance meeting point is not preset.

FIG. 7 is a schematic diagram explaining the calculation method of FIG. 6 by way of example.

Fig. 8 is a diagram illustrating the application method of the present invention in logistics distribution.

FIG. 9 is a diagram illustrating an example of the prior art "Dijkstra search" used by the present invention.

Detailed ways

Preferred embodiments of the present invention will be described in detail below with reference to the accompanying drawings.

<Embodiment 1>

FIG. 1 shows the system structure of an exemplary embodiment of the present invention. Wherein, 110 is an Internet network; 104 is a computer with a user interface or other devices that can use a user interface such as a driving navigator or a mobile phone. Result; 106 represents equipment of other people traveling together this time, which may include mobile phones, computers, driving navigators, etc.; 102 is a server for route planning. The user enters personal information and other personnel's information through the user interface of 104, so as to select meeting points in advance and search for route planning. The user interface at 104 collects the information and sends it to the server 102 through the Internet 110 . The server 102 processes the collected information and generates a corresponding route plan. Afterwards, the server 102 finally transmits and displays the planned content to the personnel devices 104 and 106 participating in the common trip through the Internet 110 .

To put it another way, referring to the functional block diagram in FIG. 2 , the system includes a user demand input device 210 , a computing device 220 for advance meeting point and route planning, and an output module 230 . In the user requirement input device 210, the user enters the search requirement on the user interface of the corresponding device. 220 calculates the route plan according to the user's search requirement, and displays it on the devices of the user and other people who travel together through the output module 230 .

FIG. 3 shows a user interface, ie, 210 in FIG. 2 , used by a certain user to enter search information on 104 in FIG. 1 . Wherein, in 301, the user specifies the specific time for the search route planning, that is, the time when the last user arrives at the destination (end point), including date and time; the user directly fills in the designated route end point in 302; 303, The user can input the starting point (starting position) of oneself; Input the starting point of every other people who participate in the common trip in 305, press "+" button (310) to add the starting point address of each person, the added personnel The number and address will be displayed in 306. When the user does not know the location of his starting point, he can select an electronic calendar (for example, select from OUTLOOK CALENDAR, GOOGLE CALENDAR, etc.) in 304, and the system can determine its time in a certain time period according to the user's electronic calendar. Geographical location, as its starting point; When this user is not clear about the position of other people participating in the common trip at the time point in 301, he can press the "+" (307) button, and a dialog box will pop up, requiring the user to input or select from the The schedule information, location information, contact information, travel mode preference information, etc. of other people selected to participate in this joint trip among the contacts; among them, when 307 adds a person who participates in the joint trip, the person's name icon Will be displayed in 309; After that, the user can drag a group of people who are going to meet at the same advance meeting point from 309 into 310 with the mouse, and press the 312 button to generate a group of groups meeting in advance, and the different groups of people generated Will be displayed in 314 with different colors or codes, and the system will calculate the corresponding advance meeting point according to the starting point and end point of each group of people; finally, the user can use 308 (confirm button), when the user presses this button, the above input The entered information will be transmitted to the server 102 as a search requirement for this joint trip.

After the user inputs the search requirement on the user interface, the system for generating the route plan in the server 102 first analyzes the user's requirement, as shown in FIG. 4 . First, the system determines the end point of the route planning (step 410) and the starting point of the personnel in each group; when the starting point of a person is not specified (yes in step 420), the system obtains the corresponding time from the personnel's electronic schedule The person's starting point for the segment (step 430). When a person's starting point is specified (No in step 420), the system obtains the grouping of the person's participation in meeting in advance from the user's entry (step 425). Finally, the system checks to see if all the people who participated in the advance meeting are grouped (step 440).

FIG. 5 shows that the system performs corresponding route planning calculation according to whether the current personnel group specifies a corresponding meeting point in advance. Specifically, in step 500, it is determined whether a corresponding advance meeting point is designated for the current personnel group. When no corresponding advance meeting point is specified (No in step 500), the system calculates the advance meeting point and performs route planning (step 600). When the corresponding meeting point in advance is designated (Yes in step 500), the system performs route planning for the set meeting point in advance (step 520).

FIG. 6 explains the calculation process of step 600 of FIG. 5 . Before explaining the calculation process, a prior art to be used in the present invention, Dijkstra search, is introduced here. The ordinary Dijkstra search computes the shortest route from a starting point s to every vertex v on the map. Vertices on the map represent physical locations, and routes between vertices represent physical routes.

Ordinary Dijkstra search includes the following steps: (1) Initially, S only contains the starting point, that is, S={v} and the distance from v to v is 0. U contains vertices on other maps except v, and the distance between vertex u in U is the weight value on the edge (if v has an edge with u) (if u is not an outbound adjacent point of v). (2) Select a vertex k with the smallest distance v from U, and add k to S (the selected distance is the shortest path length from v to k). (3) Taking k as the new intermediate point to be considered, modify the distance weight value of each vertex in U; If it is short without passing through vertex k), modify the path from the starting point v to the vertex u as the path passing through the vertex k and modify the corresponding distance weight value. (4) Repeat steps (2) and (3) until all vertices are included in S. 840 in FIG. 9 lists the graph of the Dijkstra search algorithm, in which the shortest path from A to each other vertex (B, C, D, E) is found. The distance marked on the line is the distance between adjacent line segments, that is, the weight value. The process of finding the shortest path from vertex A in 840 to all vertices in the graph is explained step by step in Table 1 below. Wherein, each step in Table 1 below is referred to as "one-step Dijkstra search" in the present invention.

The embodiment of the present invention uses a method of searching from multiple points to search for meeting points, so as to calculate route planning. First, in step 610, the method starts route retrieval from each person's starting point and the route planning end point, that is, temporarily sets the end point as a starting point, which is the same as the starting point of all people. First, in step 611, the route retrieval from any one of the starting points is performed once. In step 612, it is checked whether the route search starts at the end point of the route search. This is due to the consideration of one-way roads, roads with no left-turn and roads with no right-turn in route planning. If the starting point of the current route retrieval is the end point of this route planning (no in step 612), discard the impassable road section of the return journey (step 616) in the route retrieval, and set the one-way road section of the return journey as a two-way passable road section ( Step 617), then run the "one-step Dijkstra search" (step 614). This is because when calculating the final route later, it is necessary to reverse the route from the end point to the advance meeting point, so what this does is prevent the route retrieval from the end point from putting the unreachable road segment into this to be reversed It also prevents the route retrieval from the end point from being unable to put the one-way segment of the return trip into the route to be reversed. If the starting point of the current route retrieval is the starting point of the current route planning (Yes in step 612), then run "one-step Dijkstra search" (step 614).

After each search "one-step Dijkstra search" at step 614, step 620 checks to see if there is a point that has been visited by all route searches. If not, run the next route retrieval (step 630). Until step 620 checks that a point has been accessed by all route searches, this point is the meeting point in advance calculated by this embodiment (ie, the optimal meeting point obtained according to the present invention). Under this condition, the search stops, and at step 640, each route from each person's starting point through the early meeting point to the final destination is calculated.

According to the above method, the present invention can use the map data to search for routes according to the respective starting points and destinations of each person, and according to the way that the sum of the distances of the routes that each person passes through the meeting point to the destination is the smallest or approximately the smallest. This rendezvous point is determined as the optimal rendezvous point. In other words, when any other point is selected as the rendezvous point, the sum of the distances of the routes of each person passing through the other rendezvous point to the destination is greater than the distance of each person passing through the optimal rendezvous point to the destination. The sum of the distances for each route. Of course, the calculation method of providing the minimum sum of the distances of each route for each person to reach the destination through the optimal meeting point is the calculation target of the present invention. Considering that in a real system, the server of the computing system (102 in FIG. 1 ) may receive multiple computing requests at the same time, in order to reduce the computing time, the rendezvous point calculated by this computing method may be a suboptimal result (that is, close to the optimal result). The optimal result), correspondingly, the sum of the distances of each route that each person passes through the meeting point to reach the destination is approximately the minimum value. In contrast, Embodiment 2 and its similar exhaustive search method can calculate the absolute minimum distance of each route for each person to reach the destination through the meeting point, but this type of calculation method consumes too much time and is limited by The calculation and storage speed of the current computer cannot be applied in the actual route planning system. Although Embodiment 1 sometimes provides approximately the smallest sum of distances, it is sufficient to meet the current needs of users because of its high speed.

FIG. 7 explains the calculation method of step 600 by way of example. In the figure, points A and B are the starting points of personnel, and point D is the end point of this route planning. When performing route planning, point D is set as a temporary starting point, and in step 710, route search is started with points A, B, and D. In step 720, point M, as the first point visited by these three route searches, is selected as the meeting point in advance. Here, the shortest route (route 1) from point A to point M is A->C->M, the shortest route (route 2) from point B to point M is B->E->M, and point D to point M The shortest route is D->F->M. After calculating the meeting point in advance, reverse the shortest route from point D to point M in step 730 to obtain M->F->D (route 3), and merge route 1 and route 3 to get from point A to point M via point A The shortest route at point D is A->C->M->F->D. Combine route 2 and route 3 to get the shortest route from point B to point D via M. It is B->E->M->F ->D.

After the route planning is completed, the server sends the route information to the devices (104 and 106 in FIG. 1 ) of all the people participating in the common travel. Route information is displayed on the device in the form of text, pictures or vector maps.

<Modification 1 of Embodiment 1>

As above, Embodiment 1 of the present invention has been described in detail, but this embodiment may be modified as follows.

Specifically, in this modified example, the user can set an early meeting point for each early meeting group on the user interface ( FIG. 3 ). For example, after the user clicks on the grouping in 314, a dialog box will pop up in the user interface, and then the user can input an early meeting point for each group (if no early meeting point is input, that is, a certain early meeting point is not specified). The system calculates the corresponding route planning according to each user's starting point A, ending point D and the designated meeting point M in advance in this group. The system first calculates the shortest route from A to M, then calculates the shortest route from M to D, and then aggregates the results to obtain the shortest route from A to D via M.

According to this modified example, even if the user designates an advance meeting location, the system can still provide relevant personnel with corresponding route planning.

<Modification 2 of Embodiment 1>

This modified example is another modification of the first embodiment. In this modified example, the user divides each person participating in the common trip into a group on the user interface ( FIG. 3 ). In this way, the current route planning does not include the selection of the meeting point in advance or the formulation of the route. In this case, the system will draw up a route plan for each person participating in the joint trip separately. According to the meet time at the end point specified by the user, calculate the route from each person's starting point to the end point before the meeting time.

Therefore, according to this modified example, even if the user specifies that all personnel go to the destination respectively, the system can still provide relevant personnel with corresponding route planning.

<Embodiment 2>

The calculation result of Embodiment 1 is an approximate shortest route (that is, an approximate shortest route planning), in contrast, this embodiment provides a method for calculating the real shortest route. Similar to Embodiment 1, after the system calculates the first meeting point in advance, it continues to calculate until all points on the map are retrieved and accessed by all routes (that is to say, each point on the map becomes an meeting point in advance ). In this process, whenever a point becomes an advance meeting point, all routes retrieved from this point are recorded, and a corresponding route plan is generated. The search stops when every point on the map becomes an early encounter point. The system finds the route with the smallest cost in the previously calculated route planning (the cost here refers to the distance, fuel consumption or other weighting methods can also be used to measure the cost) and the corresponding advance meeting point. This meeting point in advance is the best meeting point in advance, and its route planning is the real shortest route, that is, the best meeting route planning.

<Embodiment 3>

The present invention is also applicable to distribution route planning in road transportation and logistics industry, especially applicable to common distribution. As shown in Figure 8, when vehicle A (805) and vehicle B (810) go to the destination 830 at the same time period, it is assumed that neither vehicle A (805) nor vehicle B (810) is fully loaded (the total amount of goods is less than or equal to one vehicle loading capacity), the two can choose to reassemble the goods in a distribution center (one of the distribution centers 815, 820, 825 in Figure 8) before going to the destination respectively, and the two trucks of goods Combine and load on one truck, so that the goods can be transported to the destination 830 by one vehicle. In this way, it is necessary to find a distribution center, so that the distance between truck A and truck B to the distribution center and the distance from the distribution center to the destination 830 is And the shortest, to minimize fuel consumption and reduce carbon dioxide emissions. The calculation method proposed in Figure 6 can be used here. The starting point of the vehicle is equivalent to the starting point of the personnel in it, and the location of the distribution center is used as a candidate point on the map to search. For example, search for the example in Figure 8, since there will be a car to transport from the distribution center to the destination, so when the calculation method starts searching from the destination, it is necessary to divide the weight value of each road segment in this direction by 2 (because One car instead of two). In this way, the route with the shortest total distance and the corresponding distribution center can be found.

Although the present invention has been illustrated in conjunction with the preferred embodiments thereof, those skilled in the art will understand that various modifications, substitutions and alterations can be made to the present invention without departing from the spirit and scope of the invention. Accordingly, the invention should not be limited by the above-described embodiments, but by the appended claims and their equivalents.

Claims (8)

1. A method for determining the optimal rendezvous point for a plurality of mobile bodies traveling from different starting points to the same destination and agreeing to rendezvous in advance, comprising: an acquiring step of acquiring respective starting points and destinations of the plurality of moving bodies; and The determining step is to use the map data to search for routes according to the respective starting points and destinations of the plurality of mobile objects, and to approximate the sum of the costs of the routes for each mobile body passing through the meeting point to the destination to be the smallest. This rendezvous point is determined as the optimal rendezvous point. 2. The method of claim 1, wherein, The cost is distance. 3. The method of claim 1, wherein, The determining steps include: Using the map data, route searches are performed starting from the respective starting points and the destinations of the plurality of mobile bodies, and when it is detected that all of these route searches have a common access point, the common access point is determined as the Describe the optimal meeting point. 4. The method of claim 1, wherein, When performing route retrieval with the destination as the starting point, during the route retrieval process, the impassable road sections on the return journey are discarded, and the one-way road sections on the return journey are set as two-way passable road sections. 5. The method of claim 1, wherein, The route retrieval adopts the Dijkstra search algorithm for step-by-step retrieval. 6. The method of claim 1, wherein, The rendezvous point is a point for the plurality of mobile bodies to depart together for the destination after arriving at the rendezvous point. 7. The method of claim 1, wherein, The rendezvous point is a point for the plurality of mobile bodies to merge into a smaller number of mobile bodies after arriving at the rendezvous point, and then set off to the destination together. 8. A device for determining the optimal rendezvous point for a plurality of mobile bodies that go to the same destination from different starting points and agree to rendezvous in advance, comprising: an acquisition unit that acquires respective starting points and destinations of the plurality of moving bodies; and The determination unit uses the map data to search for routes according to the respective starting points and destinations of the plurality of mobile objects, and calculates This rendezvous point is determined as the optimal rendezvous point.