JP6823697B2 - Multiple vehicle route planning method and multiple vehicle route planning system - Google Patents

Description

The present invention relates to a multi-vehicle route planning method and a multi-vehicle route planning system.

In logistics delivery in cities, planning of vehicle travel routes is an important element that is fundamental to building a logistics delivery information system. The quality of the vehicle's travel route planning greatly affects the efficiency of physical distribution and delivery.

In recent years, despite the daily improvement in delivery efficiency, road congestion in cities and the like remains serious. In order to alleviate the serious traffic congestion situation, traffic restrictions for delivery vehicles are being enforced in various places. For example, traffic regulation measures by area / vehicle type are taken to regulate the traffic of vehicles of a specific vehicle type in a specific area. However, it is becoming difficult for conventional route planning technology to meet new demand when such traffic regulation measures are implemented.

Patent Document 1 describes a vehicle real-time dynamic traffic guidance route optimization method. In this method, a navigation route is generated based on map data and avoidance road section information. The map data includes traffic regulation data, and in this method, when planning a driving route, the vehicle parameters input by the user are compared with the traffic regulation data values corresponding to the road data to avoid roads that cannot be passed. By repeatedly executing the process, a passable route is generated.

Non-Patent Document 1 describes that a route passing through a base outside the restricted traffic area is planned by dividing the base into two parts according to the inside and outside of the restricted traffic area. For bases within the restricted traffic area, we will put those bases on the conventional route to determine whether they violate the traffic regulation conditions, and if so, arrange a new vehicle to deal with it.

Chinese Patent Application Publication No. 1804932

Xiao Jianhua, 3 outsiders, "Multi-energy / vehicle route optimization for multiple vehicle types based on urban road traffic regulations", System Engineering Theory and Practice, China System Engineering Society, (China), May 2017, 37th ticket, No. 5, P.M. 1339 to 1348

The prior art as disclosed in Patent Document 1 has the following problems. That is, since the update cycle of the map-based data is long but the update cycle of the regulation data is short, the actual road traffic regulation conditions and the regulation data in the map may not match when using such a technology. In addition, all of these prior arts relate to route planning from a single starting point to an ending point, and do not consider optimization of traveling route planning of a plurality of vehicles (for example, a vehicle team).

Further, the prior art as disclosed in Non-Patent Document 1 has the following problems. That is, it is not suitable for the actual situation to arrange and deliver a new vehicle every time a situation contrary to the traffic regulation is encountered. In addition, if the direct base is divided inside and outside the traffic restricted area, if neither the starting point nor the ending point of the route is located within the traffic restricted area, the planned route may still pass through the traffic restricted area.

As described above, in the prior art, when there is a road regulation, it is not possible to efficiently plan a traveling route for a plurality of vehicles.

The present invention has been made in view of this background, and provides a multi-vehicle route planning method and a multi-vehicle route planning system capable of efficiently and appropriately planning routes of a plurality of vehicles when there are road regulations. The purpose is to provide.

One of the present inventions for achieving the above object is a multi-vehicle route planning method for planning a delivery route for delivery by a plurality of vehicles, in which an information processing device is used as a distribution center and a plurality of delivery destination bases. A step of storing node information including information indicating the position of each of a plurality of nodes including, and regulation information including information about a restricted area and a regulated time zone in which vehicle traffic is restricted, said regulation information. Based on the above, for two of the plurality of nodes, the inter-node route corresponding to each of the restricted time zones and the inter-node route cost of each of the inter-node routes are set to each of the restricted time zones. The step of calculating as the corresponding inter-node route information, the delivery plan including the travel route information when each of the plurality of vehicles delivers with the distribution center as the starting point and the ending point, and the plurality of the traveling route information. A step of generating a delivery plan including an inter-node route through which each of the vehicles of the vehicle passes and information indicating the transit time of each of the plurality of vehicles passing through the inter-node route, a travel route of each of the plurality of vehicles. Based on the inter-node route cost in the inter-node route information corresponding to each transit time of the inter-node route indicated by the information, the inter-node route cost of each inter-node route through which each of the vehicles included in the delivery plan passes. A step of calculating the delivery plan cost acquired by reflecting the above, and a step of selecting a delivery plan from the plurality of delivery plans based on the delivery plan costs of each of the plurality of delivery plans are executed. To do.

As described above, the multi-vehicle route planning method of the present invention generates a multi-vehicle delivery plan in consideration of the regulated area and the regulated time zone, so that the total delivery cost can be reduced while satisfying the user's demand.

Another one of the present invention is the above-mentioned multiple vehicle route planning method, and the regulation information includes information on a customized regulation area partitioned by a user using the intersection information of the regulation area.

As described above, the multi-vehicle route planning method of the present invention allows the user to customize the regulation information of the regulated area, so that the regulation information is updated in real time in response to the change of the regulated area to improve the accuracy of the planned delivery plan. Can be made to.

The other one of the present invention is the above-mentioned multiple vehicle route planning method, in which the information processing apparatus calculates the route information between the nodes for each of two of the plurality of nodes in the step. In the step of generating the unregulated inter-node route information which is the inter-node route information when there is no regulated area and generating the delivery plan, the inter-node route information is used to generate the unregulated inter-node route information. A step of extracting a route between nodes as an initial route, a step of determining whether or not the initial route violates the regulation condition based on the regulation information, and a step of determining whether the initial route violates the regulation condition, and if the initial route does not violate the regulation condition, the initial route. And its transit time are introduced into the delivery plan, and the inter-node route cost between the two nodes is extracted from the unregulated inter-node route information as the inter-node route cost between the two nodes in the delivery plan. Perform more steps.

According to the present invention, when the initial route based on the unregulated area does not violate the regulation conditions, the route can be preferentially applied to save the calculation amount and the route cost can be reduced to the maximum.

Another one of the present invention is the above-mentioned multi-vehicle route planning method, in which the information processing apparatus violates the regulation conditions in the step of generating the delivery plan, a certain regulation time zone. A step of extracting an internode route between the two nodes as a candidate route from the internode route information corresponding to the above, a step of determining whether or not the candidate route violates the regulation condition based on the regulation information, and a step of determining whether or not the candidate route violates the regulation condition. If the candidate route does not violate the regulation conditions, the candidate route and its transit time are introduced into the delivery plan, and the inter-node route cost between the two nodes is selected from the inter-node route information corresponding to the regulation time zone. Is further executed as the internode route cost between the two nodes in the delivery plan.

According to the present invention, it is possible to automatically generate a candidate route that does not violate the regulatory conditions corresponding to the time zone, and improve the practicality of the planned multi-vehicle delivery plan.

The other one of the present invention is the above-mentioned multi-vehicle route planning method, wherein in the step of calculating the inter-node route information by the information processing apparatus, about two nodes of the plurality of nodes. Further executing the step of generating the maximum regulated inter-node route information which is the inter-node route information when the regulation condition is the strictest, and in the step of generating the delivery plan, the inter-node corresponding to each of the restricted time zones. When all of the candidate routes extracted from the route information violate the regulation conditions, the node-to-node route cost between the two nodes is calculated from the maximum regulation node-to-node route information, and the node-to-node route between the two nodes in the delivery plan. Perform further steps to extract as costs.

According to the present invention, it is possible to automatically avoid inter-node routes where traffic is always restricted as much as possible, and to improve the practicality of a planned multi-vehicle delivery plan.

Another one of the present invention is the above-mentioned multiple vehicle route planning method, in which the regulation information includes at least one of traffic regulation, speed regulation, and traffic congestion, and the information processing apparatus is described by the information processing apparatus. The regulation information is divided into the regulated road section passing through the regulated area, the regulated time zone in which each regulated road section is regulated, and the speed limit corresponding to at least one of traffic regulation, speed regulation, and congestion. In the step of further executing the conversion step and calculating the route information between the nodes, each of the regulated time zones is supported based on the regulated road section, the regulated time zone, and the restricted speed included in the converted regulated information. In the step of generating the delivery plan by further executing the step of calculating the inter-node route information, when determining whether or not the inter-node route violates the regulation information, the road section through which the inter-node route passes. And whether or not the road section through which the internode route passes is the regulated road section, and whether or not the transit time is within the regulated time zone in which the regulated road section is regulated. If the road section through which the inter-node route passes is the regulated road section and the passing time is within the regulated time zone of the regulated road section, it is determined that the inter-node route violates the regulation conditions. Take more steps to do.

According to the present invention, it is possible to avoid a closed area within a predetermined time zone, and at the same time, it is possible to consider the price of passing through a congested area road, thereby planning a delivery plan that meets the user's demand at the minimum cost. Can be done. Furthermore, a highly reliable delivery plan can be generated by automatically determining whether or not the inter-node route in the delivery plan violates the regulatory conditions.

Another one of the present invention is the above-mentioned multiple vehicle route planning method, in which the information processing apparatus repeatedly executes the step of generating the delivery plan and the step of calculating the delivery planning cost a predetermined number of times. Then, in the step of selecting the delivery plan, the step of selecting the delivery plan having the lowest delivery plan cost after the predetermined number of times is repeated is further executed.

According to the present invention, by repeatedly executing the above steps, it is possible to plan a delivery plan that meets the user's demand at the minimum cost, and it is also possible to suppress an excessive increase in the processing load of the apparatus.

Another one of the present invention is the above-mentioned multi-vehicle route planning method, in which each of the plurality of vehicles included in the delivery plan selected in the step of selecting the delivery plan by the information processing apparatus. Further execution of the step of displaying the travel route information of.

According to the present invention, the user intuitively observes the planned multi-vehicle delivery plan, adjusts the plan in advance as necessary, and monitors in real time during delivery for the convenience of the user. Can be done.

Another one of the present invention is the above-mentioned multiple vehicle route planning method, wherein the information processing device includes the node information, vehicle type information indicating each vehicle type of the plurality of vehicles, and each of the plurality of vehicle types. In the step of storing the regulation information including the regulation area and the regulation time zone corresponding to each vehicle type and the step of calculating the route information between the nodes, each two of the plurality of nodes are based on the regulation information. For each node, the step of calculating the inter-node route corresponding to each regulated time zone for each vehicle type and the inter-node route cost of each inter-node route as inter-node route information corresponding to each vehicle type and each regulated time zone, described above. In the step of calculating the delivery plan cost, it is included in the delivery plan based on the inter-node route cost in the inter-node route information corresponding to each node-to-node route transit time indicated by the vehicle type of each vehicle and the travel route information of each vehicle. Further executing the step of calculating the delivery planning cost obtained by reflecting the inter-node route cost of each inter-node route through which all the vehicles pass.

The above-mentioned technical means is particularly suitable for a delivery plan of a mixed vehicle vehicle team that delivers a vehicle in which a plurality of vehicle types are mixed, and has an important meaning in actual physical distribution delivery.

The other one of the present invention is a multi-vehicle route planning system, which is configured by using an information processing device and indicates information indicating the position of each of a plurality of nodes including a distribution center and a plurality of delivery destination bases. The node information including the above and the regulation information including the information about the regulated area and the regulated time zone where the passage of the vehicle is regulated are stored, and based on the regulation information, about two nodes out of the plurality of nodes. , The inter-node route corresponding to each of the restricted time zones and the inter-node route cost of each of the inter-node routes are calculated as the inter-node route information corresponding to each of the restricted time zones, and the plurality of vehicles Each of the delivery plans includes travel route information when delivery is performed from the distribution center as a start point and an end point, and the inter-node route and the plurality of nodes through which each of the plurality of vehicles passes in the travel route information. The delivery plan including the information indicating the transit time of each vehicle passing through the inter-node route is generated, and the travel time of each of the plurality of vehicles corresponds to the transit time of each of the inter-node routes indicated by the travel route information. Based on the inter-node route cost in the inter-node route information, the delivery plan cost acquired by reflecting the inter-node route cost of each inter-node route through which each vehicle included in the delivery plan passes is calculated, and the above-mentioned A delivery plan is selected from the plurality of delivery plans based on the delivery plan costs of each of the plurality of delivery plans.

Each of the above-mentioned specific forms and effects of the plurality of vehicle route planning system of the present invention includes a multiple vehicle route planning method, a multiple vehicle route planning device, a multiple vehicle route planning program for causing a computer to execute a multiple vehicle route planning method, or It can also be realized by a recording medium in which a multi-vehicle route planning program is stored.

In addition, the problems disclosed in the present application and the solutions thereof will be clarified by the column of the form for carrying out the invention and the drawings.

According to the present invention, it is possible to efficiently and appropriately plan the routes of a plurality of vehicles when there is a road regulation.

It is a schematic diagram which shows the outline of the multi-vehicle route planning technology. It is a schematic diagram which shows a regulated area. It is a block diagram which shows the multi-vehicle route planning system which concerns on 1st Embodiment. It is a flowchart which shows the multi-vehicle route planning method which is the process executed by the multi-vehicle route planning system which concerns on 1st Embodiment. This is an example of the route information table between nodes. It is a flowchart which shows the specific example of the plurality of vehicle route planning method which concerns on 1st Embodiment. It is a flowchart which shows the specific method of calculating the cost between two nodes in the specific example of the plurality of vehicle route planning method which concerns on 1st Embodiment. This is an example of the post-conversion regulation information table. It is a flowchart which shows the specific method of determining whether or not the route between nodes violates a regulation condition in the specific example of the plurality of vehicle route planning method which concerns on 1st Embodiment. It is a block diagram which shows the multi-vehicle route planning system which concerns on 2nd Embodiment. It is a flowchart which shows the multi-vehicle route planning method which is the process executed by the multi-vehicle route planning system which concerns on 2nd Embodiment.

Hereinafter, the present invention will be described in detail together with the drawings. The following description is merely an example for facilitating the understanding of the present invention, and is not intended to limit the scope of the present invention. In a specific embodiment, the members provided in the device and the system can be changed, deleted or added according to the actual situation, and the steps of the method change or delete the procedure according to the actual situation. , Can be added or modified. In the following description, the letter "S" preceded by the number code means a processing step.

[First Embodiment]
First, an outline of a technique for planning routes for a plurality of vehicles (hereinafter referred to as "multi-vehicle route planning technique") will be described. In the following, the Vehicle Routing Problem (VRP) will be described as an example of the multi-vehicle route planning technology. The vehicle allocation route problem is that there is a different number of freight demands for each of a certain number of customers, a distribution center provides the customers with freight, and one vehicle team is in charge of freight delivery and organizes an appropriate travel route. That is. The goal of the vehicle allocation route problem is to meet customer demand and achieve objectives such as shortest distance, minimum cost, and minimum travel time under certain constraints.

FIG. 1 is a schematic diagram showing an outline of a plurality of vehicle route planning technology. As shown in the figure, each of a plurality of vehicles has a distribution center (for example, a warehouse) as a starting point and an ending point of delivery, and jointly delivers to a plurality of bases based on a planned delivery plan. The figure shows a case where three vehicles jointly deliver to 12 bases, but the number of vehicles and bases is not necessarily limited.

FIG. 2 is a schematic diagram illustrating a regulated area where the passage of vehicles is restricted. As shown in the figure, there is a regulated area between the place A and the place B, and the passage of vehicles in the regulated area is prohibited. Therefore, the vehicle cannot move from the place A to the place B along the route shown by the dotted line in the figure, and has no choice but to bypass the regulated area along the route shown by the solid line in the figure. Here, the areas where the passage of vehicles is restricted are not only the restricted areas where the passage of vehicles is prohibited as described above, but also the congested areas which affect the passage of vehicles and the traveling speed of vehicles are restricted. It may include a speed control area or the like. In addition, different regulations may be taken depending on the time of day, vehicle type, and the like.

FIG. 3 is a block diagram illustrating a plurality of vehicle route planning system 1 shown as a first embodiment. In the figure, the direction of the arrow indicates the data transmission direction.

The multi-vehicle route planning system 1 plans a delivery route for delivery by a plurality of vehicles. As shown in the figure, the plurality of vehicle route planning system 1 includes an input unit 10, an inter-node route information calculation unit 20, a delivery plan generation unit 30, a delivery plan cost calculation unit 40, and a delivery plan selection unit 50.

Each of the above units may be realized, for example, by a software module or by a dedicated hardware integrated circuit. Further, the plurality of vehicle route planning system 1 may be realized by a single computer or a server, or may be realized by a plurality of separate devices, for example, a cloud computing server including a plurality of servers. Further, a plurality of vehicle route planning programs stored in advance in the recording medium are executed by the processor of the information processing device (computer) to realize the functions of the above-mentioned units of the multiple vehicle route planning system 1, thereby realizing the functions of the plurality of vehicle route planning devices. This embodiment may be implemented as. Hereinafter, each unit will be specifically described.

The input unit 10 inputs node information to the inter-node route information calculation unit 20. The input unit 10 inputs node information from the delivery database 2 to the inter-node route information calculation unit 20, for example. The node information includes information indicating the position of each of a plurality of nodes (including a distribution center and a plurality of delivery destinations). For example, node information is represented as a set of nodes composed of a distribution center and a plurality of delivery destinations. The node information may be input to the inter-node route information calculation unit 20 from other than the delivery database 2, and may be input manually by the user or may be input using a portable type storage medium. ..

The input unit 10 inputs the regulation information to the inter-node route information calculation unit 20. The input unit 10 inputs regulation information from the traffic information database 3 into the inter-node route information calculation unit 20, for example. Regulatory information includes information indicating at least one regulated area and time zone in which vehicle traffic is regulated. Regulatory information includes, for example, information such as coordinates of regulated area boundaries, regulated time zones, speeds of different regulated road sections within the zone, and the like. Vehicle traffic regulation includes, for example, that traffic is prohibited (traffic regulation), traffic is affected (traffic congestion), traveling speed is restricted (speed regulation), and the like.

As the regulation information, the regulation information may be input to the inter-node route information calculation unit 20 from other than the traffic information database 3, and for example, the user may manually set the regulation area via the input unit 10. The user may, for example, partition the regulated area using the intersection information of the regulated area and customize the regulated information of the regulated area. Generally, the map infrastructure data has a long update cycle, but the regulation data has a short update cycle, so the actual road regulation conditions do not match the regulation information in the map, but the user can customize the regulation information of the regulated area. By doing so, it is possible to update the regulation information in real time in response to the change of the regulation area and improve the accuracy of the planned delivery plan.

Based on the input regulation information, the inter-node route information calculation unit 20 has, for two nodes out of a plurality of nodes indicated by the input node information, the inter-node route and each node corresponding to each of the restricted time zones. The inter-node route cost of the inter-node is calculated as the inter-node route information corresponding to each of the regulated time zones. Here, the inter-node route can be generated by the base map and the regulated area conditions. The inter-node route cost is, for example, a cost obtained by combining the distance cost and the required time cost of the inter-node route, and can be obtained by weighting and adding the distance cost and the required time cost. The cost calculation method is not necessarily limited, and may be calculated in consideration of other factors.

The delivery plan generation unit 30 generates a delivery plan including travel route information in which each of the plurality of vehicles delivers from the delivery center as the starting point and the ending point. Here, the traveling route information of each vehicle includes information indicating at least one inter-node route through which the vehicle passes and the passing time of the vehicle passing through each inter-node route. The delivery plan generation unit 30 generates a travel route of each vehicle by using a destruction reconstruction algorithm, for example, based on a plurality of node-to-node route information corresponding to the regulation time zone generated by the inter-node route information calculation unit 20. .. The method of generating the travel route is not necessarily limited, and other methods may be used. The delivery plan generation unit 30 can generate a plurality of candidate delivery plans.

The delivery plan cost calculation unit 40 is based on the inter-node route cost in the inter-node route information corresponding to the transit time of the inter-node route indicated by the travel route information of each vehicle, and each of the vehicles included in the delivery plan passes through. Calculate the delivery planning cost obtained by reflecting the inter-node route cost of the inter-node route. The delivery planning cost is obtained, for example, by adding up the route costs between all the nodes of all the vehicles included in the delivery plan. The above addition may be weighted. The delivery plan cost calculation unit 40 calculates the delivery plan cost for each of the plurality of delivery plan candidates generated by the delivery plan generation unit 30.

The delivery plan selection unit 50 selects a delivery plan from a plurality of delivery plan candidates based on the delivery plan cost of each delivery plan. For example, the delivery plan selection unit 50 selects the delivery plan with the lowest delivery plan cost. It should be noted that a predetermined number of delivery plans having a low delivery plan cost may be presented and selected by the user.

FIG. 4 is a flowchart illustrating a process executed in the plurality of vehicle route planning system 1 (hereinafter, referred to as “multiple vehicle route planning process S400”). The plurality of vehicle route planning process S400 is executed, for example, on the day before the day when the plurality of vehicles deliver, when drafting the delivery plan for the next day. The plurality of vehicle route planning process S400 is realized, for example, by the information processing apparatus (computer) executing a program that realizes the process.

As shown in the figure, first, the input unit 10 inputs the node information and the regulation information to the inter-node route information calculation unit 20 (S101). For example, the input unit 10 inputs information on a plurality of nodes and regulation information indicating a traffic restricted area.

Subsequently, the inter-node route information calculation unit 20 describes the inter-node route corresponding to each of the regulated time zones and the inter-node route of each node for each of the two nodes of the plurality of nodes based on the regulation information. Calculate the root cost. For example, the inter-node route information calculation unit 20 determines the inter-node route and its cost between two nodes of node A (delivery center), node B, node C, and other nodes for each regulation time zone. Calculated as inter-node route information corresponding to each regulated time zone.

FIG. 5 is a table showing an example of inter-node route information (hereinafter, referred to as “inter-node route information table 500”). As shown in the figure, the inter-node route information table 500 has one or more entries having each item of a start point 511, an end point 512, an inter-node route 513, a required time 514, a distance 515, and an inter-node route cost 516. Records) are included. The inter-node route information table 500 is generated corresponding to each regulated time zone, and the illustrated inter-node route information table 500 corresponds to a certain regulated time zone.

Based on the regulation information of the regulation time zone, the inter-node route information calculation unit 20 has, for example, node A as a starting point, node B as an ending point, node B as a starting point 511, node A as an ending point 512, and node A as a starting point 511. Node C is the end point 512, node C is the start point 511, node A is the end point 512, node B is the start point 511, node C is the end point 512, node C is the start point 511, node B is the end point 512, and so on. Calculate the inter-node route and inter-node route cost between nodes, respectively. Here, the inter-node route includes information such as a route passing position (for example, latitude and longitude), road section information corresponding to the position, and time to pass the position. The inter-node route cost 516 (for example, the inter-node route cost “C_AB” when moving from node A to node B) is the time required for the inter-node route 513 (for example, the time required from node A to node B “T_AB”). ”) And the distance 515 (for example, the distance from node A to node B“ D_AB ”) are weighted and added.

Returning to FIG. 4, the delivery plan generation unit 30 subsequently generates a delivery plan including travel route information in which each of the plurality of vehicles delivers from the delivery center as the starting point and the ending point (S103). The travel route information of each vehicle includes information indicating at least one inter-node route through which the vehicle passes. For example, in the example of FIG. 5, when a vehicle passes from node A as a delivery starting point, passes through node B and node C, and finally returns to node A, the traveling route of the vehicle corresponds to each of the transit times of the vehicle. Includes inter-routes "R_AB", "R_BC", and "R_CA".

Subsequently, the delivery plan cost calculation unit 40 is based on the inter-node route cost in the inter-node route information corresponding to the transit time of the inter-node route indicated by the travel route information of each vehicle, and each of the vehicles included in the delivery plan The delivery planning cost obtained by reflecting the inter-node route cost of each passing inter-node route is calculated (S104). For example, when the traveling route of a certain vehicle in a certain delivery plan includes "R_AB", "R_BC", and "R_CA" as inter-node routes, the delivery planning cost calculation unit 40 uses the inter-node route "R_AB" for the vehicle. The inter-node route cost "C_AB" of the inter-node route information corresponding to the time to pass through, the inter-node route cost "C_BC" in the inter-node route information corresponding to the time for the vehicle to pass the inter-node route "R_BC", and Based on each of the inter-node route costs "C_CA" in the inter-node route information corresponding to the time when the vehicle passes through the inter-node route "R_CA", the delivery cost of the vehicle is calculated by performing addition or weighting addition or the like. Further, the delivery plan cost calculation unit 40 calculates the cost of the delivery plan by performing addition, weighting addition, or the like based on the delivery cost of all vehicles in the delivery plan.

Finally, the delivery plan selection unit 50 selects a delivery plan from the plurality of delivery plans based on the delivery plan cost of each delivery plan (S105). For example, the delivery plan selection unit 50 selects the delivery plan with the lowest delivery plan cost.

According to the multi-vehicle route planning system and the multi-vehicle route planning method according to the present embodiment, inter-node route information between two nodes is calculated for each regulated time zone in consideration of the regulated area and the regulated time zone. As a result, when generating the travel route of each vehicle in the delivery plan of multiple vehicles, the route between nodes included in the travel route is generated using the route information between nodes corresponding to the time, and the cost of the route between nodes is generated. Can be calculated. As a result, it is possible to generate a multi-vehicle delivery plan considering the regulated area and the regulated time zone, meet the demand of the user, and reduce the total delivery cost.

Hereinafter, specific examples of the first embodiment will be described. Since the configuration of the plurality of vehicle route planning system 1 of the specific example is the same as that of FIG. 3, the description thereof is omitted here. Hereinafter, a method of planning a multiple vehicle route of a specific example will be described.

FIG. 6 is a flowchart showing a specific example of the plurality of vehicle route planning method according to the first embodiment.

First, the input unit 10 inputs the node information and the regulation information to the inter-node route information calculation unit 20 (S201).

Subsequently, the inter-node route information calculation unit 20 converts the nodes into a matrix and assigns a value. The matrix value corresponds to the actual node number (S202).

Subsequently, the inter-node route information calculation unit 20 calculates the route, distance, and required time between each of the two nodes of all the nodes based on the regulation information, stores them in the inter-node route information, and determines the corresponding time zone. Generate route information between different nodes (S203).

Subsequently, the inter-node route information calculation unit 20 further generates unregulated inter-node route information which is inter-node route information when there is no regulated area for each of two nodes among the plurality of nodes (S204). Further, in the process, the inter-node route information calculation unit 20 further generates maximum inter-node route information, which is inter-node route information when the regulation conditions are the strictest, for each of the two nodes among the plurality of nodes. May be good. The strictest regulatory conditions are, for example, that all regulated areas are regulated all day, that is, the regulated time zone is 24 hours all day, and may be incorporated and calculated as the minimum speed limit.

Subsequently, the delivery plan generation unit 30 generates a candidate delivery plan based on the destruction reconstruction algorithm (S205). In one example of a destructive reconstruction algorithm, for example, first generate an acceptable delivery plan, then select a destructive model, destroy some of the generated delivery plans, and deliver for some locations. Do not do this, and add these locations to the delivery plan and reconfigure the delivery plan to determine if the reconfigured delivery plan is acceptable.

Subsequently, the delivery plan cost calculation unit 40 calculates the cost of the candidate delivery plan and determines whether or not the candidate delivery plan is superior to the current optimum plan (S206). If it is determined that the process is not superior to the current optimum plan, the process returns to S205 and a new candidate delivery plan is generated. If it is determined in S206 that the candidate delivery plan is superior to the current optimal plan, S207 is executed and the delivery plan selection unit 50 updates the candidate delivery plan as the current optimal plan.

In S208, the delivery plan selection unit 50 determines whether or not the predetermined number of repetitions has been reached. If it is determined in the process that the predetermined number of repetitions has not been reached, the process returns to S205, and the delivery plan selection unit 50 generates a new candidate delivery plan. When it is determined in S208 that the predetermined number of repetitions has been reached, the delivery plan selection unit 50 executes S209 and converts the matrix node through which the current optimum plan passes through the conversion matrix into an actual node.

That is, the processing of the delivery plan generation unit 30 (step of generating the delivery plan) and the processing of the delivery plan cost calculation unit 40 (step of calculating the delivery plan cost) are repeatedly executed a predetermined number of times, and the delivery plan selection unit 50 After being repeated a predetermined number of times, the delivery plan with the lowest delivery plan cost (current optimal plan) is used as the selected delivery plan. The higher the number of iterations, the more likely it is to obtain a delivery plan with a lower cost, but the processing load on the device will increase, so the number of iterations should be determined appropriately according to the actual demand and the processing capacity of the device. Good. As a result, it is possible to plan a delivery plan that meets the user's demand at the minimum cost by repetition, and it is possible to suppress an excessive increase in the processing load of the device.

Subsequently, in S210, the plurality of vehicle route planning system 1 executes a step of displaying the delivery plan, and travel route information of each vehicle included in the delivery plan (current optimum plan) selected by the delivery plan selection unit 50. Is displayed. For example, the map display module can display the travel route included in the delivery plan, which can be used for advance planning or real-time monitoring. As a result, the user can intuitively observe the planned multiple vehicle delivery plan, adjust the plan in advance as necessary, and monitor in real time during delivery for the convenience of the user.

Hereinafter, a specific method for calculating the required cost between two nodes will be described in the above specific example.

FIG. 7 is a flowchart showing a specific method for calculating the required cost between two nodes in a specific example of the plurality of vehicle route planning method according to the first embodiment. The flowchart of FIG. 7 is executed, for example, in the process of generating a candidate delivery plan in S205 of the flowchart of FIG.

As shown in FIG. 7, the delivery plan generation unit 30 first inputs the positions and departure times of the two nodes (starting point and ending point) (S301).

Subsequently, the delivery plan generation unit 30 extracts the inter-node route between the two nodes as the initial route from the unregulated inter-node route information when there is no regulated area (S302).

Subsequently, the delivery plan generation unit 30 determines whether or not the initial route violates the regulation conditions based on the regulation information (S303). When it is determined that the initial route does not violate the regulation conditions (S303: NO), the delivery plan generation unit 30 executes S304, introduces the initial route and its transit time into the delivery plan, and unregulated inter-node route information. The inter-node route cost between two nodes is extracted as the inter-node route cost between two nodes in the delivery plan. The delivery plan generation unit 30 generates inter-node route information when there is no regulated area, and extracts the initial route from the inter-node route information when there is no regulated area, so that the initial route does not violate the regulation conditions. Not only can the route be applied preferentially to save computation, but the route cost can also be reduced as much as possible.

On the other hand, when it is determined that the initial route violates the regulation conditions (S303: YES), the delivery plan generation unit 30 executes S305, and the inter-node route information corresponding to a certain regulation time zone, for example, the next regulation time The inter-node route between two nodes is extracted as a candidate route from the inter-node route information of the band.

Subsequently, returning to S303, the delivery plan generation unit 30 determines whether or not the candidate route violates the regulation conditions based on the regulation information. If it is determined in S303 that the candidate route does not violate the regulation conditions (S303: NO), S304 is executed, the candidate route and its transit time are introduced into the delivery plan, and the inter-node route information corresponding to the regulation time zone is displayed. The inter-node route cost between two nodes is extracted as the inter-node route cost between two nodes of the vehicle in the delivery plan. That is, when the initial route based on the unregulated area violates the regulation conditions, the candidate routes are extracted by repeatedly checking the inter-node route information corresponding to each regulation time zone, and it is judged whether the candidate routes satisfy the regulation conditions. Therefore, it is possible to automatically generate candidate routes that do not violate the regulatory conditions corresponding to the time zone, and improve the practicality of the planned multi-vehicle delivery plan.

When S303 is repeatedly executed and it is determined that all the candidate routes extracted from the inter-node route information corresponding to each regulation time zone violate the regulation conditions, the delivery plan generation unit 30 executes S306 to the maximum. From the regulated inter-node route information, the inter-node route cost between two nodes is extracted as the inter-node route cost between two nodes in the delivery plan. That is, no suitable route was found even after the repetition was completed, and it was considered that the passage of vehicles between the two nodes was always restricted. Therefore, the most restrictive inter-node route information was applied to the two nodes. Return to the route with the highest cost (preliminary plan) so that the travel route of the generated vehicle avoids the inter-node route between the two nodes as much as possible. This makes it possible to avoid inter-node routes, where traffic is always restricted, as automatically as possible, and improve the practicality of planned multi-vehicle delivery plans.

Hereinafter, the conversion process of the regulation information input in the above specific example will be described. The multi-vehicle route planning method of this embodiment may further include a step of converting regulatory information. In the regulation information conversion step, the input unit 10 converts the input regulation information into the regulation road section passing through the regulation area and the regulation time zone in which each regulation road section is regulated.

FIG. 8 is a table showing an example of the regulated information after conversion (hereinafter, referred to as “converted regulation information table 800”). As shown in the figure, the converted regulation information table 800 includes one or more entries (records) having each item of the road section ID 811, the regulation time zone 812, and the speed limit 813. As shown in the figure, for example, based on the position of the regulated area boundary (for example, latitude and longitude), by examining the road section corresponding to the position, the input regulation information is applied to the road section passing through the regulated area boundary. It is converted into a set of (road section ID 811) and a time zone (regulated time zone 812) corresponding to the road section, and saved in the form of a hash table, for example. Also, if the regulatory information includes at least one of traffic regulation, speed regulation, and congestion, the regulatory information may be converted to a speed limit corresponding to at least one of traffic regulation, speed regulation, and congestion. For example, the speed limit of the road section in the traffic restricted area is set to 0, the speed limit of the road section in the congested area is set to a value larger than 0, and the speed limit of the road section in the speed restricted area is set to the value corresponding to the speed regulation. Set to.

Further, the inter-node route information calculation unit 20 is a node corresponding to each regulated time zone based on the road section ID 811 (regulated road section), the regulated time zone 812, and the speed limit 813 included in the converted regulation information table 800. Calculate inter-route information. For example, based on the base map and the converted regulatory information, the speed limits corresponding to different regulatory types of road sections within the regulated area are modified, and the route, duration and duration between the two nodes on the modified map are modified. Calculate the distance and store it in the inter-node route information table.

By different treatments for various restricted areas such as restricted areas and congested areas, it is possible to avoid areas where traffic is prohibited within a predetermined time zone and consider the price of passing through roads in congested areas. This makes it possible to plan a delivery plan that meets the user's demand at the lowest cost.

Hereinafter, in the above specific example, a specific example for determining whether or not the route between nodes violates the regulation conditions will be described.

FIG. 9 is a flowchart showing a specific method for determining whether or not the inter-node route violates the regulatory conditions in the specific example of the plurality of vehicle route planning method according to the first embodiment. The flowchart shown in FIG. 7 is executed, for example, in S303 of the flowchart of FIG. 7.

As shown in the figure, first, the delivery plan generation unit 30 acquires the road section through which the inter-node route passes and the transit time thereof for the inter-node route to be determined (S401). For example, when calculating the inter-node route information, the delivery plan generation unit 30 calculates the position (for example, latitude and longitude) through which the inter-node route passes, and passes through the road section corresponding to the position and the road section. Check the time and save.

Subsequently, the delivery plan generation unit 30 determines whether or not the road section through which the inter-node route passes is the regulated road section indicated by the above-mentioned converted regulation information (S402). The delivery plan generation unit 30 determines, for example, whether or not the road section ID through which the inter-node route passes and the road section ID 811 of the converted regulation information table 800 (for example, the hash table of regulation information) have a common set. Thereby, it is determined whether or not the road section through which the route between the nodes passes matches the regulated road section included in the converted regulation information. When it is determined that the road section is not a regulated road section (S402: NO), the delivery plan generation unit 30 executes S403 and determines that the route between the nodes does not violate the regulation condition.

On the other hand, when it is determined that the road section is regulated (S402: YES), the delivery plan generation unit 30 executes S404, and is the transit time of the route between the nodes within the regulated time zone of the regulated road section? Further judge whether or not. If it is determined that the route is not within the regulated time zone (S404: NO), the delivery plan generation unit 30 executes S403 and determines that the inter-node route does not violate the regulated condition. On the other hand, in S404, when it is determined that the route is within the regulated time zone (S404: YES), S405 is executed, and it is determined that the route between the nodes violates the regulated condition.

In this way, the regulation information is converted into a set of the regulated road section and the corresponding regulated time zone, and the set is examined to determine whether or not the route between nodes is the regulated road section and is within the regulated time zone. By doing so, it is possible to generate a highly reliable delivery plan because it is automatically determined whether or not the route between nodes in the delivery plan violates the regulation conditions.

[Second Embodiment]
Subsequently, the second embodiment of the present invention will be specifically described. The second embodiment provides a plurality of vehicle route planning technology for regulatory information corresponding to vehicle type information based on the first embodiment. Hereinafter, the differences from the first embodiment will be mainly described, and the description of the same or similar contents as the first embodiment will be omitted.

First, the plurality of vehicle route planning system 1 of the present embodiment will be described.

FIG. 10 is a block diagram showing a plurality of vehicle route planning system 1 according to the second embodiment. As shown in the figure, the basic structure of the plurality of vehicle route planning system 1 of the present embodiment is the same as that of the first embodiment, but the contents of the functions are partially different.

The input unit 10 inputs not only the node information but also the vehicle type information indicating each vehicle type of the plurality of vehicles to be delivered to the inter-node route information calculation unit 20 from the delivery database 2. Vehicle types include, for example, light trucks, large trucks, container trucks, and the like. The plurality of vehicles to be delivered may all be one vehicle type, or each may belong to a plurality of vehicle types. Further, the regulation information input to the inter-node route information calculation unit 20 by the input unit 10 includes a regulation area and a regulation time zone corresponding to each vehicle type among the plurality of vehicle types. The vehicle type information and the regulation information corresponding to the vehicle type are not limited to being input from the delivery database 2 or the traffic information database 3, and may be customized and input by the user.

The inter-node route information calculation unit 20 is based on the regulation information corresponding to each vehicle type, and for each of the two nodes of the plurality of nodes, the inter-node route and the inter-node route corresponding to each regulation time zone for each vehicle type. The inter-node route cost is calculated as the inter-node route information corresponding to each vehicle type and each regulated time zone.

The delivery planning cost calculation unit 40 includes all of the delivery planning costs included in the delivery plan based on the inter-node route cost in the inter-node route information corresponding to the transit time of each inter-node route indicated by the vehicle type of each vehicle and the traveling route information of each vehicle. The delivery planning cost obtained by reflecting the inter-node route cost of each inter-node route through which each vehicle passes is calculated.

Subsequently, a plurality of vehicle route planning method, which is a process executed by the multiple vehicle route planning system 1 of the present embodiment, will be described.

FIG. 11 is a flowchart showing a plurality of vehicle route planning method, which is a process executed by the plurality of vehicle route planning system 1 according to the second embodiment.

As shown in the figure, in the input S501, the input unit 10 inputs the node information, the vehicle type information, and the regulation information corresponding to each vehicle type from the delivery database 2 to the inter-node route information calculation unit 20 (S501). For example, the input unit 10 has vehicle type information indicating delivery by two light trucks and one large truck, and the traffic of the large truck is restricted in the restricted area A from 9:00 to 17:00, but the small truck. Inputs regulation information that is not restricted to traffic all day into the inter-node route information calculation unit 20.

Subsequently, the inter-node route information calculation unit 20 calculates inter-node route information corresponding to each vehicle type and each time limit (S502). For example, in the above example, the delivery plan generation unit 30 calculates unregulated inter-node route information for two nodes among a plurality of nodes and for light trucks based on the regulation information corresponding to each vehicle type. For large trucks, the inter-node route information corresponding to the time zone 9:00 to 17:00 is calculated.

Subsequently, the delivery plan generation unit 30 generates a delivery plan including travel route information of a plurality of vehicles (S503). For example, in the above example, the delivery plan generation unit 30 generates a delivery plan including travel route information of two light trucks and one large truck.

Subsequently, the delivery planning cost calculation unit 40 calculates the delivery planning cost based on the inter-node route cost in the inter-node route information corresponding to the vehicle type and the passing time of each vehicle (S504). For example, in the above example, the delivery plan generation unit 30 determines the inter-node route cost in the inter-node route information corresponding to the transit time of the inter-node route indicated by the travel route information of two light trucks and one large truck. Calculate the delivery planning cost based on.

Subsequently, the delivery plan selection unit 50 selects a delivery plan from the plurality of delivery plans based on the delivery plan cost (S505). For example, in the above example, the delivery plan generation unit 30 selects a delivery plan based on the delivery plan cost from a plurality of delivery plans of two light trucks and one large truck.

As described above, the plurality of vehicle route planning system 1 of the second embodiment is based on each vehicle type of the plurality of vehicles participating in the delivery and the regulation information corresponding to the vehicle type, and between the nodes corresponding to each vehicle type and each regulation time zone. Since it generates route information, it is particularly suitable for a delivery plan of a vehicle team of a mixed vehicle type that delivers a vehicle in which a plurality of vehicle types are mixed, and has an important meaning in actual physical distribution delivery.

As described above, the multi-vehicle route planning method and the multi-vehicle route planning system according to the present invention generate a multi-vehicle delivery plan in consideration of the regulated area and the regulated time zone, satisfy the user's demand, and the total delivery cost. Since it is possible to reduce the number of vehicles, it is possible to efficiently and appropriately plan the routes of a plurality of vehicles when there is a road regulation, and it can be effectively used for delivery planning in the logistics field.

Although specific embodiments and examples of the present invention have been described above with reference to the drawings, the above-mentioned specific embodiments and examples are merely specific examples for understanding the present invention, and the present invention. It is not intended to limit the range of. Based on the technical idea of the present invention, engineers in this field can make various changes, combinations, and rational omissions of elements to specific embodiments and examples, and the methods obtained thereby are also available. It is included in the scope of the present invention. For example, each of the above embodiments and specific examples can be combined with each other, and an embodiment composed of the combination is also included in the scope of the present invention.

1 Multiple vehicle route planning system, 10 input units, 20 node-to-node route information calculation unit, 30 delivery plan generation unit, 40 delivery plan cost calculation unit, 50 delivery plan selection unit, 2 delivery database, 3 traffic information database

Claims (7)

A method of planning a delivery route for delivery by multiple vehicles.
The information processing device
Node information, including information indicating the location of each of multiple nodes, including a distribution center and multiple destination locations, and regulatory information, including information about regulated areas and time zones where vehicle traffic is restricted. And the step to remember,
Based on the regulation information, for two nodes among the plurality of nodes, the inter-node route corresponding to each of the regulation time zones and the inter-node route cost of each of the inter-node routes are determined in the regulation time zone. Steps to calculate as inter-node route information corresponding to each of
A delivery plan including travel route information when each of the plurality of vehicles delivers from the distribution center as a starting point and an end point, and the inter-node route through which each of the plurality of vehicles passes in the travel route information. And a step of generating a delivery plan that includes information indicating the transit time for each of the plurality of vehicles to pass through the inter-node route.
Each of the vehicles included in the delivery plan passes based on the inter-node route cost in the inter-node route information corresponding to each transit time of the inter-node route indicated by the travel route information of each of the plurality of vehicles. Steps to calculate the delivery planning cost obtained by reflecting the inter-node route cost of each inter-node route, and
A step of selecting a delivery plan from the plurality of delivery plans based on the delivery plan cost of each of the plurality of delivery plans.
And
In the step of calculating the inter-node route information, for each of the two nodes of the plurality of nodes, a step of generating unregulated inter-node route information which is inter-node route information when there is no regulated area is executed. ,
In the step of generating the delivery plan,
A step of extracting an inter-node route between two nodes as an initial route from the unregulated inter-node route information,
Based on the regulatory information, the steps to determine whether the initial route violates the regulatory conditions, and
When the initial route does not violate the regulation conditions, the initial route and its transit time are introduced into the delivery plan, and the node-to-node route cost between the two nodes is calculated from the unregulated node-to-node route information in the delivery plan. The step of extracting as the inter-node route cost between the two nodes in
And
In the step of generating the delivery plan,
When the initial route violates the regulation conditions, the step of extracting the inter-node route between the two nodes as a candidate route from the inter-node route information corresponding to a certain regulation time zone,
Based on the regulation information, a step of determining whether or not the candidate route violates the regulation conditions, and
If the candidate route does not violate the regulation conditions, the candidate route and its transit time are introduced into the delivery plan, and the node-to-node route cost between the two nodes is selected from the node-to-node route information corresponding to the regulation time zone. As the inter-node route cost between the two nodes in the delivery plan,
And
In the step of calculating the inter-node route information, for two of the plurality of nodes, a step of generating the maximum inter-node route information which is the inter-node route information when the regulation condition is the strictest is executed. And
In the step of generating the delivery plan, if all of the candidate routes extracted from the inter-node route information corresponding to each of the restricted time zones violates the regulation conditions, the two above-mentioned two from the maximum regulated inter-node route information. Performing the step of extracting the inter-node route cost between nodes as the inter-node route cost between the two nodes in the delivery plan.
Multiple vehicle route planning method. The method for planning a plurality of vehicle routes according to claim 1.
The regulation information includes information on a customized regulation area partitioned by the user using the intersection information of the regulation area.
Multiple vehicle route planning method. The method for planning a plurality of vehicle routes according to claim 1 .
The regulatory information includes at least one of traffic regulation, speed regulation, and traffic congestion.
The information processing device
The regulation information includes a regulated road section passing through the regulated area, a regulated time zone in which each regulated road section is regulated, and a speed limit corresponding to at least one of traffic regulation, speed regulation, and traffic congestion. Take further steps to convert to
In the step of calculating the inter-node route information, the inter-node route information corresponding to each regulated time zone is calculated based on the regulated road section, the regulated time zone, and the speed limit included in the converted regulated information. Take more steps to
In the step of generating the delivery plan, when determining whether or not the inter-node route violates the regulation information, the road section through which the inter-node route passes and the passage time thereof are acquired, and the inter-node route passes through. It is determined whether or not the road section is the regulated road section and whether or not the passing time is within the regulated time zone in which the regulated road section is regulated, and the road section through which the internode route passes is described as described above. If it is a regulated road section and the transit time is within the regulated time zone of the regulated road section, the step of determining that the inter-node route violates the regulation condition is further executed.
Multiple vehicle route planning method. The method for planning a plurality of vehicle routes according to claim 1.
The information processing device
In the step of repeatedly executing the step of generating the delivery plan and the step of calculating the delivery plan cost a predetermined number of times and selecting the delivery plan, the delivery plan cost after being repeated the predetermined number of times is the highest. Take further steps to select a lower delivery plan,
Multiple vehicle route planning method. The method for planning a plurality of vehicle routes according to claim 1.
The information processing apparatus further executes a step of displaying the travel route information of each of the plurality of vehicles included in the delivery plan selected in the step of selecting the delivery plan.
Multiple vehicle route planning method. The method for planning a plurality of vehicle routes according to any one of claims 1 to 5 .
The information processing device
A step of storing the node information, vehicle type information indicating each vehicle type of the plurality of vehicles, and the regulation information including a regulation area and a regulation time zone corresponding to each vehicle type in the plurality of vehicle types.
In the step of calculating the inter-node route information, based on the regulation information, for each of the two nodes of the plurality of nodes, the inter-node route and the inter-node route corresponding to each regulation time zone for each vehicle type. Steps to calculate the inter-node route cost as inter-node route information corresponding to each vehicle type and each regulated time zone,
In the step of calculating the delivery plan cost, the delivery plan is based on the inter-node route cost in the inter-node route information corresponding to each node-to-node route transit time indicated by the vehicle type of each vehicle and the travel route information of each vehicle. A step to calculate the delivery planning cost obtained by reflecting the inter-node route cost of each inter-node route that all the vehicles included pass through,
A multi-vehicle route planning method that further executes. A multi-vehicle route planning system that plans a delivery route for delivery by multiple vehicles.
It is configured using an information processing device,
Node information, including information indicating the location of each of multiple nodes, including a distribution center and multiple destination locations, and regulatory information, including information about regulated areas and time zones where vehicle traffic is restricted. And remember,
Based on the regulation information, for two nodes among the plurality of nodes, the inter-node route corresponding to each of the regulation time zones and the inter-node route cost of each of the inter-node routes are determined in the regulation time zone. Calculated as inter-node route information corresponding to each of
A delivery plan including travel route information when each of the plurality of vehicles delivers from the distribution center as a starting point and an end point, and the inter-node route through which each of the plurality of vehicles passes in the travel route information. And generate a delivery plan that includes information indicating the transit time for each of the plurality of vehicles to pass through the inter-node route.
Each of the vehicles included in the delivery plan passes based on the inter-node route cost in the inter-node route information corresponding to each transit time of the inter-node route indicated by the travel route information of each of the plurality of vehicles. Calculate the delivery planning cost obtained by reflecting the inter-node route cost of each inter-node route,
A delivery plan is selected from the plurality of delivery plans based on the delivery plan costs of each of the plurality of delivery plans .
When calculating the inter-node route information, unregulated inter-node route information, which is inter-node route information when there is no regulated area, is generated for each of the two nodes among the plurality of nodes.
When generating the delivery plan,
From the unregulated inter-node route information, the inter-node route between two nodes is extracted as the initial route, and
Based on the regulation information, it is determined whether or not the initial route violates the regulation conditions.
When the initial route does not violate the regulation conditions, the initial route and its transit time are introduced into the delivery plan, and the node-to-node route cost between the two nodes is calculated from the unregulated node-to-node route information in the delivery plan. Extracted as the inter-node route cost between the two nodes in
When generating the delivery plan,
When the initial route violates the regulation conditions, the inter-node route between the two nodes is extracted as a candidate route from the inter-node route information corresponding to a certain regulation time zone.
Based on the regulation information, it is determined whether or not the candidate route violates the regulation conditions.
If the candidate route does not violate the regulation conditions, the candidate route and its transit time are introduced into the delivery plan, and the node-to-node route cost between the two nodes is selected from the node-to-node route information corresponding to the regulation time zone. Is extracted as the inter-node route cost between the two nodes in the delivery plan.
In calculating the inter-node route information, for two of the plurality of nodes, the maximum inter-node route information which is the inter-node route information when the regulation conditions are the strictest is generated.
When all of the candidate routes extracted from the inter-node route information corresponding to each of the restricted time zones in the generation of the delivery plan violate the regulation conditions, the maximum regulated inter-node route information is used between the two nodes. The inter-node route cost is extracted as the inter-node route cost between the two nodes in the delivery plan.
Multi-vehicle route planning system.