JP7792641B2 - Route search device, route search method, and route search program - Google Patents

Description

Embodiments of the present invention relate to a route search device, a route search method, and a route search program.

Transporting goods by vehicle is essential in modern society. Finding the optimal route for transportation is an important issue. For example, in the event of a disaster, if it is necessary to supply goods including electricity and water by vehicle to multiple demand points, it is necessary to find a route that minimizes damage caused by a shortage of goods (electricity or water) at each demand point.

Traditional route search methods include a technique that uses a discrete minimization method by treating the vehicle's starting point and demand points as vertices and the mud between points as edges. For example, Patent Document 1 discloses a technique for sequentially inserting demand points. Furthermore, for example, Non-Patent Document 1 discloses a technique for dividing demand points and solving the traveling salesman problem.

Japanese Patent Application Laid-Open No. 2004-333377

Masashi Ito, Shinya Watanabe, and Kazunori Sakakibara, "Proposal of a New Search Framework Based on Subproblem Decomposition and Adaptive Problem Integration for Large-Scale Vehicle Routing Problems," Transactions of the Japanese Society for Evolutionary Computation, Vol. 6, No. 3 (2015)

Patent Document 1 aims to optimize vehicle travel costs and total cargo weight, and may output routes that are not useful for minimizing the "maximum amount of damage due to resource depletion at each demand point" (hereinafter referred to as delay cost). For example, if there is a demand point that is far from the vehicle's starting point but must be reached quickly, a route search that minimizes travel costs will output a route that visits that point last, as this point has a large delay cost. As a result, the technology disclosed in Patent Document 1 has the problem of being unable to minimize delay costs.

Furthermore, the method disclosed in Non-Patent Document 1 has the problem that it cannot provide a good division for the problem of minimizing delay costs, which are affected by the importance of each demand point and the time when supplies begin to run out.

The subject of this invention was made in light of the above circumstances, and its purpose is to provide technology that can find a solution that is close to the optimal solution to the problem of searching for a route that minimizes the maximum delay cost.

According to an embodiment, a route search device uses a column generation method to search for a route that travels from the vehicle's initial position to all demand points and minimizes the maximum delay cost at each vertex. The route search device includes: a data acquisition unit that acquires vertex information including the vehicle's initial position and the demand points; point information including the time until the delay cost corresponding to each vertex reaches a predetermined cost, the work time at each vertex, and weights; and condition data including travel time between the vertices; a calculation unit that calculates an upper bound for a route that can be traveled at or below the predetermined cost and the maximum objective function value for the weights based on dynamic programming that further constrains the way the demand points are passed; and a search unit that rounds the value corresponding to the upper bound to an integer and uses a local search method as appropriate to search for the route.

One aspect of the present invention provides a route search device, a route search method, and a route search program that can find a solution close to the optimal solution to the problem of searching for a route that minimizes the maximum delay cost.

FIG. 1 is a block diagram illustrating an example of a hardware configuration of a route search device according to an embodiment. FIG. 2 is a block diagram showing the software configuration of the route search device according to the embodiment in relation to the hardware configuration shown in FIG. FIG. 3 is a flowchart showing an example of a processing procedure for calculating a lower bound of an objective function value in this embodiment. FIG. 4 is a flowchart showing an example of a specific processing procedure for calculating the lower bound. FIG. 5 is a flowchart showing an example of a specific processing procedure for calculating the upper bound. FIG. 6 is a diagram showing an example of the travel time between vertices. FIG. 7 is a diagram showing an example of calculating the lower bound of the maximum value of the objective function. FIG. 8 is a diagram showing an example of calculating the upper bound of the maximum value of the objective function.

The route search device, route search method, and route search program will be described in detail below with reference to the drawings. Note that in the following embodiments, parts with the same numbers perform similar operations, and redundant explanations will be omitted. For example, when there are multiple identical or similar elements, a common symbol may be used to describe each element without distinguishing between them, or a sub-number may be used in addition to the common symbol to describe each element with distinction between them.

[Embodiment]
(the purpose)
Initially, there are D+S vertices on a two-dimensional plane, and each vertex is denoted as v _i ,iε{1,...,D+S}. Here, D and S are assumed to be positive integers. The D vertices correspond to the initial placement points of vehicles, and the S vertices correspond to demand points. That is, D vehicles will travel around this point. For each v _i ,iε{1,...,D+S} corresponding to a demand point, the power-off time is assumed to be _di , the work time is assumed to be _wi εR _>0 , and the importance is assumed to be α _i εZ _>0 . Here, R and Z are non-negative real number sets. Also, for each two vertices v _i ,v _j ,i,jε{1,...,D+S}, the travel time between them is assumed to be t(v _i ,v _j )εR _>0 .

When a vehicle finishes work at a vertex v _i at time T _i , the delay cost c(v _i ) of that vertex is defined as follows:

c(v _i ):=max {α _i (T _i −d _i ), 0}
That is, the delay cost is a function of the importance and power down time at each vertex up to time T _i .

In this case, suppose we want to find a route that allows D vehicles to visit all vertices and minimizes the maximum delay cost at each vertex.

Here, consider the feasibility problem of whether the delay cost of this optimization problem is equal to or greater than λ. Here, λ may be any delay cost when considering the feasibility problem. This problem can be formulated as a set partitioning problem. That is, a vector b _r ∈ Z ^S+D corresponding to a route r is defined as a vector in which the components passing through the vertex corresponding to r are 1 and the other components are 0. Let A _λ be a matrix listing all vectors corresponding to routes that pass through all vertices with a cost equal to or less than λ and that do not pass through the same vertex twice. In that case, the integer programming problem is
find x
s.t.A _λ x=1
x∈{0,1} ^A
This can be formulated as follows:

A linear relaxation of this integer programming problem
find x
s.t.A _λ x=1
0≦x≦1
is solved using the column generation method.

For example, let us denote the value obtained by solving λ by iteratively performing a binary search as λ _L,P . This λ _L,P is a lower bound on the optimal value of the original problem. For example, the optimal value can be obtained by solving the integer programming problem of the original problem. However, the above-mentioned method solves a problem in which the constraints of the original problem are relaxed. Therefore, the value λ _L,P obtained by the above-mentioned method is a value better than the optimal value, i.e., a lower bound on the original problem.

The column-adding part of the column generation method is performed by dynamic programming on a space-time network. That is, a path r with a cost λ or less that maximizes y ^T b _r for a given weight y can be calculated by sequentially filling in a table in which the vertical axis represents each vertex and the horizontal axis represents the time step. The weight y is the weight of each vertex and may be a value that changes with each iteration. More precisely, the weight y is the dual solution of the linear programming problem (LP) formed by the current matrix, and is a weight used to find a column vector that narrows the constraints of the dual problem.

However, if this calculation method is strictly implemented, due to the constraint that the same vertex must not be passed twice, it is necessary to store information about the paths that have been passed through each type of vertex for each cell in the table. This can take exponential time to calculate, and as the number of paths increases, it becomes difficult to calculate in practice. Therefore, the purpose of this invention is to explain an algorithm that appropriately modifies the dynamic programming portion and restricts the range of maxy ^T _br from both above and below, thereby obtaining the upper and lower bounds of λ _L,P after a bisection search.

(composition)
FIG. 1 is a block diagram showing an example of the hardware configuration of a route search device 1 according to an embodiment.
The route search device 1 is a computer that analyzes input data and generates and outputs output data. The route search device 1 may be installed at any location. For example, the route search device 1 is installed at a predetermined location of a base station where a power supply vehicle, a water supply vehicle, or the like is deployed.

As shown in FIG. 1 , the route search device 1 includes a control unit 10, a program storage unit 20, a data storage unit 30, a communication interface 40, and an input/output interface 50. The control unit 10, the program storage unit 20, the data storage unit 30, the communication interface 40, and the input/output interface 50 are communicatively connected to one another via a bus. The communication interface 40 may also be communicatively connected to an external device via a network. The input/output interface 50 is also communicatively connected to an input device 51 and an output device 52. The control unit 10 controls the route search device 1. The control unit 10 includes a hardware processor such as a central processing unit (CPU). For example, the control unit 10 may be an integrated circuit capable of executing various programs.

The program storage unit 20 can use a combination of non-volatile memory that can be written to and read from at any time, such as an EPROM (Erasable Programmable Read Only Memory), HDD (Hard Disk Drive), or SSD (Solid State Drive), and non-volatile memory such as a ROM (Read Only Memory) as a storage medium. The program storage unit 20 stores the programs necessary to execute various processes. In other words, the control unit 10 can achieve various controls and operations by reading and executing the programs stored in the program storage unit 20.

The data storage unit 30 is a storage medium that combines non-volatile memory, such as a HDD or memory card, which can be written to and read from at any time, with volatile memory, such as RAM (Random Access Memory). The data storage unit 30 is used to store data acquired and generated in the process of the control unit 10 executing programs and performing various processes.

The communication interface 40 includes one or more wired or wireless communication modules. For example, the communication interface 40 includes a communication module that establishes a wired or wireless connection with an external device via a network. The communication interface 40 may also include a wireless communication module that establishes a wireless connection with an external device such as a Wi-Fi access point or base station. Furthermore, the communication interface 40 may also include a wireless communication module that establishes a wireless connection with an external device using short-range wireless technology. In other words, the communication interface 40 may be any general communication interface that can communicate with an external device under the control of the control unit 10 and send and receive various information, including past performance data.

The input/output interface 50 is connected to the input device 51, output device 52, etc. The input/output interface 50 is an interface that enables the transmission and reception of information between the input device 51 and the output device 52. The input/output interface 50 may be integrated with the communication interface 40. For example, the route search device 1 and at least one of the input device 51 or the output device 52 may be wirelessly connected using short-range wireless technology, etc., and information may be transmitted and received using this short-range wireless technology.

The input device 51 includes, for example, a keyboard or pointing device that allows the user to input various data to the route search device 1. The input device 51 may also include a reader for reading data to be stored in the program storage unit 20 or data storage unit 30 from a memory medium such as a USB memory, or a disk device for reading such data from a disk medium.

The output device 52 includes a display that displays images from the route search device 1 to be displayed to the administrator of the route search device 1.

FIG. 2 is a block diagram showing the software configuration of the route search device 1 according to the embodiment in relation to the hardware configuration shown in FIG.
The control unit 10 includes a data acquisition unit 101, an upper and lower bound calculation unit 102, a solution calculation unit 103, an error evaluation unit 104, and an output control unit 105. The data storage unit 30 includes a data storage unit 301 and a processed data storage unit 302.

The data acquisition unit 101 acquires condition data. The condition data includes vertex information including the initial position of the vehicle and a demand point, point information including the time until the delay cost corresponding to each point reaches a predetermined cost (λ), the work time at each vertex, and weight information, and travel time between points.

The data acquisition unit 101 may store the acquired conditions in the data storage unit 301 .

The upper and lower bound calculation unit 102 further includes a table creation unit 1021, a path control unit 1022, an objective function calculation unit 1023, and a cost determination unit 1024.

The table creation unit 1021 creates a table based on the condition data stored in the data storage unit 301. For example, the table may be one in which each row corresponds to a vertex and each column corresponds to a time at a predetermined interval. The time at a predetermined interval may be based on the minimum travel time between vertices, for example. Then, as the initial state, the table creation unit 1021 inputs a weight value based on the condition data into the square (vertex) where the vehicle is initially placed. The table creation unit 1021 outputs the created table to the route control unit 1022.

The table creation unit 1021 also inputs the path and the objective function value into the square corresponding to the moved vertex. The table creation unit 1021 may input the path and the objective function value into the square corresponding to the moved vertex based on information received from the path control unit 1022 and the objective function calculation unit 1023.

The route control unit 1022 moves the vehicle along an arbitrary route based on dynamic programming, which further restricts or relaxes the constraints on the route of the demand points. That is, the route control unit 1022 moves the vehicle to another vertex. The route control unit 1022 outputs information about the moved vertex to the table creation unit 1021 and the objective function calculation unit 1023.

The objective function calculation unit 1023 calculates the objective function value at the moved vertex based on the condition data. The objective function calculation unit 1023 outputs the calculated objective function value to the table creation unit 1021.

The cost determination unit 1024 determines whether the delay cost is greater than or equal to λ.

The solution calculation unit 103 calculates a solution using a local search method as appropriate. The solution calculation unit 103 rounds the value corresponding to the upper bound to an integer solution. The solution calculation unit 103 then calculates a solution using a local search method as appropriate. In other words, the solution calculation unit 103 operates as a search unit that searches for a path.

The error evaluation unit 104 calculates the difference between the solution calculated by the solution calculation unit 103 and the lower bound received from the upper bound/lower bound calculation unit 102. The error evaluation unit 104 evaluates the error from the optimal value of the original problem based on this error. For example, since the lower bound < the cost of the optimal solution to the original problem, (cost of the solution calculated by the solution calculation unit 103 - lower bound) > (cost of the solution calculated by the solution calculation unit 103 - cost of the optimal solution). In other words, it is possible to evaluate the error between the solution calculated by the solution calculation unit 103 and the optimal solution as being smaller than the difference between the solution calculated by the solution calculation unit 103 and the lower bound.

(operation)
First, the method for calculating the lower and upper bounds will be described.
- Calculation method for lower bound (relaxation)
In the original problem, there was a constraint that the same vertex must not be passed twice. However, when calculating the lower bound, dynamic programming is performed under a relaxed constraint, instead of the near constraint, that allows passing twice, but does not pass through the same point consecutively. This relaxed constraint eliminates the need to store information about vertices that have been passed so far; it is sufficient to simply store one path (the path passed most recently) for each square. Therefore, the calculation time for dynamic programming can be calculated in polynomial time. As the problem moves in the direction of relaxation, a value greater than or equal to the maximum value of the objective function maxy ^T b _r is obtained. Therefore, after performing the binary search, the lower bound of λ _L,P is calculated.

For example, if the current integer programming problem is solved exactly, the value of λ _L,P can naturally be obtained exactly. Here, by relaxing the constraints of the current integer programming problem, a lower bound of λ _L,P can be obtained. Since _{λ L,P} is a lower bound of the maximum value of the objective function value, the lower bound of λ _L,P is a lower bound of the lower bound of the maximum value of the objective function value, i.e., a lower bound of the maximum value of the objective function value. Here, since λ _L,P itself is a lower bound of the optimal value of the original problem, this lower bound of λ _L,P can be used as a lower bound of the original problem.

・How to calculate the upper bound (limit)
While maintaining the constraint that the same vertex must not be passed twice, a new constraint is added that if two or more paths are held in each cell, only the one with the largest objective function value at that time is left. Due to this constraint, just as with the lower bound, it is sufficient to hold one path in each cell. Therefore, the calculation time for the dynamic program can be calculated in polynomial time. As the number of paths to be searched is narrowed, a value equal to or less than the maximum value of the objective function value maxy ^T _br is calculated. After the binary search is performed, the upper bound of λ _L,P is calculated.

For example, the upper bound of λ _L,P is the upper bound of the lower bound of the maximum objective function value. Therefore, the magnitude relationship with the maximum objective function value itself is not determined. However, it is possible to evaluate the accuracy of the relaxation depending on whether the upper and lower bounds of λ _L,P are close to each other.

In addition, since there are no changes to the path constraints, it is possible to simultaneously output a feasible solution to the linear relaxation problem, and by rounding the value calculated after the bisection search to an appropriate value, it is possible to obtain a feasible solution to the original problem.

(operation)
FIG. 3 is a flowchart showing an example of a processing procedure for calculating a lower bound of an objective function value in this embodiment.
The operation of this flowchart is realized by the control unit 10 of the route search device 1 reading and executing a program stored in the program storage unit 20. This operation is started when a user or an administrator of the route search device 1 inputs condition data into the input device 51. Alternatively, it may be started by obtaining condition data stored in the data storage unit 30 at any time. In this case, step ST101 described below may be omitted.

In step ST101, the data acquisition unit 101 acquires condition data. The condition data may include, for example, vertex information including the vehicle's initial position and demand point, the time until the delay cost corresponding to each vertex information reaches a predetermined cost (λ), location information including the work time and weight at each vertex, and travel time between vertices. The data acquisition unit 101 may store the acquired conditions in the data storage unit 301.

In step ST102, the upper and lower bound calculation unit 102 calculates the lower bound. The upper and lower bound calculation unit 102 calculates the lower bound based on the condition data stored in the data storage unit 301.

FIG. 4 is a flowchart showing an example of a specific processing procedure for calculating the lower bound.
In step ST201, the table creation unit 1021 creates a table. The table creation unit 1021 creates the table based on the condition data stored in the data storage unit 301. The table may be, for example, a table in which each row corresponds to a vertex and each column corresponds to a time at a predetermined interval. The time at a predetermined interval may be based on, for example, the minimum travel time between each vertex. Then, as an initial state, the table creation unit 1021 inputs a weight value based on the condition data into the square (vertex) where the vehicle is initially placed. The table creation unit 1021 outputs the created table to the route control unit 1022.

In step ST202, the route control unit 1022 moves the vehicle along an arbitrary route. The route control unit 1022 moves the vehicle along an arbitrary route that satisfies the constraint that the vehicle may pass through the same vertex twice, but not pass through the same point consecutively. In other words, the route control unit 1022 moves the vehicle to another vertex. The route control unit 1022 outputs information about the vertex to which the vehicle has been moved to the table creation unit 1021 and the objective function calculation unit 1023.

In step ST203, the objective function calculation unit 1023 calculates the objective function at the moved vertex based on the condition data. The objective function calculation unit 1023 outputs the calculated objective function to the table creation unit 1021.

In step ST204, the table creation unit 1021 inputs the path and the objective function value into the cell corresponding to the moved vertex. The table creation unit 1021 may input the path and the objective function value into the cell corresponding to the moved vertex based on information received from the path control unit 1022 and the objective function calculation unit 1023.

In step ST205, the cost determination unit 1024 determines whether the delay cost is equal to or greater than λ. If the delay cost is less than λ, the process returns to step ST202. On the other hand, if the delay cost is equal to or greater than λ, the process proceeds to step ST206.

In step ST206, the table creation unit 1021 outputs the maximum objective function value to the error evaluation unit 104. The table creation unit 1021 searches for the square into which the maximum objective function value is input, and outputs the searched maximum objective function value as a lower bound to the error evaluation unit 104. The table creation unit 1021 may also store the maximum objective function value in the processing data storage unit 302. In this way, the upper and lower bound calculation unit 102 can calculate the lower bound of the maximum objective function value for a route and weight that can be traversed at a cost of λ or less, based on dynamic programming that relaxes the constraints on how the vertices are passed.

Returning to FIG. 3, in step ST103, the upper bound/lower bound calculation unit 102 calculates the upper bound. The upper bound/lower bound calculation unit 102 calculates the upper bound based on the condition data stored in the data storage unit 301.

FIG. 5 is a flowchart showing an example of a specific processing procedure for calculating the upper bound.
Steps ST301 to ST303 may be the same as steps ST201 to ST203 described with reference to FIG. 4, and therefore a duplicated description will be omitted here.

In step ST304, the table creation unit 1021 determines whether two or more routes exist in the square corresponding to the moved vertex. For example, if there are two or more vehicles, they may arrive at the same point by following different routes. The table creation unit 1021 determines whether this is the case. If it is determined that two or more routes do not exist in the square corresponding to the moved vertex, the process proceeds to step ST305. On the other hand, if it is determined that two or more routes exist in the square corresponding to the moved vertex, the process proceeds to step ST306.

In step ST305, the table creation unit 1021 inputs the path and the objective function into the cell corresponding to the moved vertex. The table creation unit 1021 may input the path and the objective function value into the cell corresponding to the moved vertex based on information received from the path control unit 1022 and the objective function calculation unit 1023.

In step ST306, the table creation unit 1021 enters the maximum objective function value among the objective function values received from the objective function calculation unit 1023 and the path corresponding to that objective function value into the cell corresponding to the vertex traveled. In other words, if there are multiple vehicles that arrive at the same point via different paths, the table creation unit 1021 keeps only the one with the maximum objective function value.

Step ST307 can be performed using the same processing as step ST205 described with reference to Figure 4, so a duplicated explanation will be omitted here.

In step ST308, the table creation unit 1021 outputs the maximum objective function value to the solution calculation unit 103. The table creation unit 1021 searches for the square into which the maximum objective function value is input, and outputs the searched maximum objective function value as an upper bound to the solution calculation unit 103. The table creation unit 1021 may also store the maximum objective function in the processing data storage unit 302. In this way, the upper bound/lower bound calculation unit 102 can calculate an upper bound for the maximum objective function value for a route and weight that can be traveled at a cost of λ or less, based on dynamic programming that further restricts the constraints on how demand points are routed.

Returning to FIG. 3 , in step ST104, the solution calculation unit 103 calculates a solution using a local search method as appropriate. The solution calculation unit 103 rounds the value corresponding to the upper bound to an integer solution. The solution calculation unit 103 then calculates a solution using a local search method as appropriate. This solution is close to the optimal solution for the original problem. The solution calculation unit 103 then outputs the calculated solution to the error evaluation unit 104 and to the processing data storage unit 302.

In step ST105, the error evaluation unit 104 evaluates the error. The error evaluation unit 104 calculates the difference between the solution received from the solution calculation unit 103 and the lower bound received from the upper bound/lower bound calculation unit 102. The error evaluation unit 104 evaluates the error from the optimal value of the original problem based on the error. The error evaluation unit 104 then outputs information about the evaluation result to the processing data storage unit 302.

In step ST106, the output control unit 105 outputs the results. The output control unit 105 outputs the calculation results, including the upper bound, lower bound, solution, evaluation results, etc. stored in the processing data storage unit 302, to the output device 52 via the input/output interface 50. The output control unit 105 may then control the output device 52 to display the results on its display.

(Calculation example)
A specific example will be described in which the weight is y and the upper and lower bounds of the maximum value of the objective function value y ^T b _r within a route r that can be traveled at a cost λ or less will be calculated.

As condition data, the number of vehicles is two, and the initial points are v ₁ and v _2. The number of demand points is three, and the demand points are v ₃ , v ₄ , and v ₅ .

FIG. 6 is a diagram showing an example of the travel time between vertices.
The travel time between each vertex is as shown in Fig. 6. The unit of this value may be, for example, time.

Also, the times when the delay cost reaches λ are d ^λ ₃ : 1, d ^λ ₄ : 1.25, and d ^λ ₅ : 1, and the work times are w ₃ = 0, w ₄ = 0, and w ₅ = 0. Furthermore, the weight is y=(1, 2, 3, 4, 5) ^T .

The maximum value of the objective function value y ^T _br under these conditions is 11. An example of calculating the upper and lower bounds of this value will be described.

The table creation unit 1021 prepares a table corresponding to each vertex, and then inputs values corresponding to the weights into the squares corresponding to the initial positions of the vehicles, i.e., the squares of _v1 and _v2 .

Then, the route control unit 1022 moves the vehicle from the vertex corresponding to the current square to an arbitrary vertex. The objective function calculation unit 1023 calculates the objective function value for the corresponding vertex. The table creation unit 1021 then inputs the route and objective function value into the square corresponding to the moved vertex. This is repeated until the delay cost reaches λ.

Figure 7 shows an example of calculating the lower bound of the maximum objective function value, and Figure 8 shows an example of calculating the upper bound of the maximum objective function value.

When calculating the lower bound, the constraint is relaxed to allow the same vertex to be passed twice, but not consecutively, and the path is entered into the table. As shown in Figure 7, a path that passes through the same vertex twice at time 1.25 is entered, and it can be seen that a value greater than the maximum value of the original objective function is calculated.

In addition, when calculating the upper bound, the objective function values and paths are entered into the table from left to right under the constraint that the same vertex must not be passed twice. As shown in Figure 8, at time 0.75, the path _v1 , _v3 , and _v5 with an objective function value of 9 and the path _v2 , _v4 , and _v5 with an objective function value of 11 are entered into the same cell, but only the latter path with the larger objective function value remains.

(Effects of the embodiment)
According to the embodiment described above, by calculating the lower and upper bounds by appropriate relaxation and restriction, rounding the value corresponding to the upper bound, and calculating the solution by a local search method, it is possible to avoid falling into a local optimum that is clearly different from the global optimum and obtain a practically good solution. In addition, by taking the difference from the lower bound, it is possible to evaluate the error from the optimum value of the original problem.

This makes it possible, for example, in the event of a disaster, to calculate routes to supply water or electricity to affected areas while minimizing damage by taking into account the importance of each location.

Other Embodiments
It should be noted that the present invention is not limited to the above-described embodiments. For example, the route search device 1 may calculate only the upper bound without calculating the upper and lower bounds, and calculate only the solution. Although several embodiments of the present invention have been described, these embodiments are presented as examples and are not intended to limit the scope of the invention. These novel embodiments can be embodied in various other forms, and various omissions, substitutions, and modifications can be made without departing from the spirit of the invention. These embodiments and their modifications are included within the scope and spirit of the invention, as well as within the scope of the claims and their equivalents.

DESCRIPTION OF SYMBOLS 1... Path search device 10... Control unit 101... Data acquisition unit 102... Upper and lower bound calculation unit 1021... Table creation unit 1022... Path control unit 1023... Objective function calculation unit 1024... Cost determination unit 103... Solution calculation unit 104... Error evaluation unit 105... Output control unit 20... Program storage unit 30... Data storage unit 301... Data storage unit 302... Processed data storage unit 40... Communication interface 50... Input/output interface 51... Input device 52... Output device

Claims (4)

A route search device for searching, using a column generation method, for a route that travels from an initial position of a vehicle to all vertices corresponding to demand points, and minimizes the maximum value of delay costs at each vertex, which is a function of the importance of each vertex, the time when the vehicle finishes work at any one of the vertices, and the time when supplies at each vertex are depleted, comprising:
a data acquisition unit that acquires condition data including vertex information including vertices corresponding to the initial position of the vehicle and the demand points, point information including the time until the delay cost corresponding to each vertex reaches a predetermined cost, the work time at each vertex, and the weight of each vertex, and travel time between the vertices;
calculating a route that can be traveled at or below the predetermined cost and a lower bound of the maximum value of the objective function at the weight based on dynamic programming in which the constraint on how the vertices are passed is relaxed to allow the same vertex to be passed twice, but not consecutively;
calculating an upper bound on the maximum value of the objective function value for the weight and a route that can be traveled at a cost equal to or less than the predetermined cost based on dynamic programming with further constraints on the manner in which the vertices are passed ;
A calculation unit;
a search unit that rounds the value corresponding to the upper bound to an integer value and searches for a path that minimizes the maximum value of the delay cost of each vertex by using a local search method as appropriate;
an evaluation unit that evaluates that the error between the searched route solution and the optimum value of the route is smaller than the difference between the searched route solution and the lower bound by calculating the difference between the searched route solution and the lower bound;
wherein the objective function value is defined by the weight and a vector corresponding to a route that can be traveled at or below the predetermined cost , the constraint on how to pass through the vertices is a constraint that the same vertex is not passed through twice, and further constraining the constraint on how to pass through the vertices is by adding a constraint that, when two or more vehicles arrive at the same vertex at the same time, only one with the largest objective function value at that time is left. The path search device of claim 1, wherein the calculation unit repeats the operation of determining a path from the vehicle's position to the next vertex and calculating an objective function value for the determined path for as long as the cost is equal to or less than the predetermined cost, and calculates the largest value as the maximum value of the objective function. A route search method executed by a route search device for searching, using a column generation method, for a route that travels from an initial position of a vehicle around all vertices corresponding to demand points, and minimizes a maximum value of delay costs at each vertex, the maximum value being a function of the importance of each vertex, the time when the vehicle finishes work at any one of the vertices, and the time when supplies are depleted at each vertex, the method comprising:
acquiring condition data including vertex information including vertices corresponding to the initial position of the vehicle and the demand points, point information including the time until the delay cost corresponding to each vertex reaches a predetermined cost, the work time at each vertex, and the weight of each vertex, and travel time between the vertices;
calculating a route that can be traveled at a cost equal to or less than the predetermined cost and a lower bound of the maximum value of the objective function at the weight, based on dynamic programming in which the constraint on how the vertices are passed is relaxed so that the same vertex may be passed twice, but not consecutively;
calculating an upper bound on the maximum value of the objective function for the weight and a route that can be traveled at a cost equal to or less than the predetermined cost based on dynamic programming with further constraints on the manner in which the vertices are passed;
rounding the value corresponding to the upper bound to an integer value and searching for a path that minimizes the maximum value of the delay cost of each of the vertices using a local search method as appropriate;
calculating a difference between the solution of the searched route and the lower bound, and evaluating that the error between the solution of the searched route and the optimum value of the route is smaller than the difference between the solution of the searched route and the lower bound;
wherein the objective function value is defined by the weight and a vector corresponding to a route that can be traveled at or below the predetermined cost , the constraint on how to pass through the vertices is a constraint that the same vertex is not passed through twice, and further restricting the constraint on how to pass through the vertices is by adding a further constraint that, when two or more vehicles arrive at the same vertex at the same time, only one with the largest objective function value at that time is left. A route search program for searching, using a column generation method, for a route that travels from an initial position of a vehicle to all vertices corresponding to demand points, and minimizes the maximum value of delay costs at each vertex, which is a function of the importance of each vertex, the time when the vehicle finishes work at any one of the vertices, and the time when supplies at each vertex are depleted, the program comprising:
acquiring condition data including vertex information including vertices corresponding to the initial position of the vehicle and the demand point, point information including the time until the delay cost corresponding to each vertex information reaches a predetermined cost, the work time at each vertex, and the weight of each vertex, and travel time between the vertices;
calculating a route that can be traveled at a cost equal to or less than the predetermined cost and a lower bound of the maximum value of the objective function at the weight, based on dynamic programming in which the constraint on how the vertices are passed is relaxed so that the same vertex may be passed twice, but not consecutively;
calculating an upper bound on the maximum value of the objective function for the weight and a route that can be traveled at a cost equal to or less than the predetermined cost based on dynamic programming with further constraints on the manner in which the vertices are passed;
rounding the value corresponding to the upper bound to an integer value and searching for a path that minimizes the maximum value of the delay cost of each of the vertices using a local search method as appropriate;
calculating a difference between the solution of the searched route and the lower bound, and evaluating that the error between the solution of the searched route and the optimum value of the route is smaller than the difference between the solution of the searched route and the lower bound;
an instruction to cause a processor of the route search device to execute the above;
A route search program, wherein the objective function value is defined by the weight and a vector corresponding to a route that can be traveled at or below the specified cost , the constraint on how to pass through the vertices is a constraint that the same vertex is not passed through twice, and further restricting the constraint on how to pass through the vertices is by adding a constraint that if two or more vehicles arrive at the same vertex at the same time, only the one with the largest objective function value at that time is left.