JP4610161B2 - Course creation system and course creation method - Google Patents

Description

[0001]
BACKGROUND OF THE INVENTION
The present invention relates to a course creation system and a course creation method.
[0002]
[Prior art]
In an area including a plurality of traveling points, the shortest route for traveling these traveling points can be obtained by a so-called traveling salesman problem method. The traveling salesman problem is a problem of searching for the shortest route when a salesman travels through n cities once. If the number of cities is n, (n-1)! When there are combinations of / 2, and the number of n increases, the number of all combinations increases exponentially, so it is difficult to obtain an exact solution. Therefore, various approximation algorithms are used to optimize the combination. Examples of such approximate algorithms include random search, hill-climbing method, simulated annealing (SA), genetic algorithm (GA), and the like.
[0003]
Conventionally, a route determination method for creating route data suitable for route search from an image map and determining a route with a shorter distance or time using the route data has been disclosed (Patent Document 1). Here, the route is determined in consideration of map traffic such as road traffic volume, intersection position, road shape, and one-way traffic. Thereby, a route having a smaller distance or time can be determined.
[0004]
[Patent Document 1]
JP-A-6-273181
[0005]
[Problems to be solved by the invention]
However, in the past, the only consideration was how efficiently the patrol was carried out within a fixed range, and when creating multiple courses in the area, how to select the patrol points to be included in the course The technique of whether to do was not considered. In particular, the method of creating such a course from an objective viewpoint is not considered at all.
[0006]
Furthermore, conventionally, when creating a plurality of courses in an area assuming movement by a vehicle such as a truck, creation of a course that can be circulated efficiently has not been considered. However, there are demands for traders who deliver goods to reduce the number of workers and the number of vehicles.
[0007]
In addition, considering the characteristics of creating multiple courses in the area and sharing each course among multiple workers, how should the multiple points in the target area be distributed to multiple workers? It is important to consider. Conventionally, a method for creating a traveling course from an objective viewpoint has not been taken into consideration, and as a result, it has been impossible to objectively grasp the labor of workers. As a result, unfairness may occur among workers.
[0008]
An object of the present invention is to provide a technique for creating a course capable of efficiently performing a patrol work by reducing the number of necessary workers when creating a plurality of patrol courses in an area. Another object of the present invention is to provide a technique for creating a course that can be efficiently paved by reducing the number of workers and the number of vehicles when creating a traveling course that is moved by a vehicle such as a truck. It is in. Another object of the present invention is to provide a technique capable of objectively creating such a course. Still another object of the present invention is to provide a technique capable of appropriately and fairly assigning a tour point when creating a plurality of tour courses in an area.
[0009]
[Means for Solving the Problems]
In the present invention described below, it is assumed that a course in which the tour points included in the course are fixed, such as a tour of each tour point every week, is created. Here, the traveling point refers to a point where the worker stops when traveling, or a point where the worker delivers the article. For example, vending machines for filling operations, chain stores such as convenience stores for delivering products, target stores for door-to-door sales and interviews, various delivery services such as newspapers and milk It can be the target facility when distributing the target person or flyer. Here, for example, the course refers to a route from a base that is a starting point of the tour to each tour point and returning to the base. The number of courses is the number of such routes.
[0010]
  According to the present invention,
  A predetermined reference point andCreate a tour course in an area with multiple tour pointsComputerA system,
A reference point information storage unit for storing position information of the reference point;
A traveling point information storage unit for storing position information of the plurality of traveling points;
A course that departs from the reference point in the morning, circulates through each traveling point in the course, takes a break in the middle of the course, travels through the traveling points in the afternoon, and returns to the reference point in the evening. A first upper limit time of the course of the course, a course that departs from the reference point in the morning and goes around the circuit points in the morning course and returns to the reference point, or the reference point after taking a break during the day And the second upper limit time of the second course, the upper limit time being shorter than the first upper limit time. A condition setting receiving unit for receiving settings;
Based on the setting of the theoretical number n of courses to be created in the region,in frontRegisterA dividing line extending radially around the quasi-pointThe dividing line is set so that the angle formed by the adjacent dividing lines is an approximate value of 360 / n.The regionnA search area creation unit for dividing the search area;
Based on the position information of the reference point and the position information of the plurality of circulation points respectively stored in the reference point information storage unit and the cyclic point information storage unit,For each of the search areas, select each of the tour points to include the tour points included in the search area in the same course,AboveThe first coursenA selection part to be created;
Based on the position information of the reference point and the position information of the plurality of circulation points respectively stored in the reference point information storage unit and the cyclic point information storage unit,Course time determined by the tour points included in each first courseCalculateWhen the course time is equal to or longer than the first upper limit time, out of the tour points included in the search area, remove the tour points in order from the reference point,The removed tour point isAn adjustment unit that performs processing included in the second course;
A course creation system characterized by including: Here, each 1st course is formed so that upper limit time may become equal as much as possible.
[0011]
  In this way, a traveling course can be created objectively. Thus, by creating a course objectively, it is possible to perform a course creation simulation in a very short period of time only by setting the minimum necessary parameters. Each course is formed in a search area surrounded by a dividing line that spreads radially around the reference point, so that it can be formed in a shape that is substantially the same and easy to grasp. This makes it possible to create a course that allows workers to have a sense of fairness. Furthermore, according to the present invention, a course that can be circulated efficiently can be created.
  According to the course creation system of the present invention, each course is created in the shape of a petal of a flower. Here, the other courses are located close to the reference point so that the shape of the petal becomes small. It is possible to preferentially select from the tour points. Thereby, the course time in the other course can be made smaller than the course time in the corresponding course.
  In the course creation system of the present invention, the second course may be configured to span a plurality of the search areas.In addition, this makes it possible to create a course having a shape like a flower petal formed radially around the reference point.
[0012]
  In the course creation system of the present invention, the search area creation unit determines the area so that the angles formed by the adjacent dividing lines are substantially equal with the reference point as the center.nIt can be divided into search areas. Thereby, each 1st course can be produced in the shape which is substantially equal, and course time becomes substantially equal. In addition, by forming the search areas substantially uniformly at first and then performing adjustment processing, processing for obtaining the optimum solution for course creation can be performed quickly and efficiently.
[0015]
  In the course creation system of the present invention, the selection unit can select each tour point so that the tour points included in the search area are included in the same course, and the adjustment unitFirstIn the courseCourse timeApplicable considering the average value ofFirstIn the courseCourse timeIf the value is lower than the average value, the angle formed by the dividing lines that form the search area is expanded, andFirstIn the courseCourse timeIs higher than the average value, a process of narrowing the angle formed by the dividing lines forming the search area can be performed.
[0016]
  This allows eachFirstCourseCourse timeCan be made to be substantially equal. In addition, it is possible to quickly and efficiently perform a process for obtaining an optimal solution for creating a course.
[0019]
In the course creation system of the present invention, the search area creation unit can set the dividing line in consideration of road information marking roads included in the area. In this way, for example, when patrol is performed using a vehicle such as a truck, the patrol point located on the left side in the forward direction of the outbound route is first patroled, and then the patrol point located on the left side also in the traveling direction of the return route. Since a course that returns to the reference point can be created, the patrol work can be performed efficiently. It should be noted that, in a country where the vehicle traffic direction is right-hand traffic, the course can be made in the reverse order.
[0021]
In the course creation system of the present invention, the patrol work may be performed using a vehicle, and further includes an order determination unit that determines the order in which the stores included in the course are visited for each created course, The unit can determine the order so that the vehicle travels in order from a traveling point located on the vehicle direction side. In this way, it is possible to create a route that can be patrolled efficiently when the patrol work is performed with the vehicle.
[0022]
In the course creation system of the present invention, the search area creation unit may first select a seed as a starting point when creating a course from a plurality of circulation points, and sets an axis line through the reference point and the seed. The dividing line can be set in consideration of the axis.
[0023]
In the course creation system of the present invention, the course creation system further includes a point information holding unit that holds a flexibility parameter indicating a degree of restriction when including a plurality of tour points in a course in association with each tour point, and the search area creation unit includes: The seed can be selected in view of the flexibility parameter.
[0024]
In the course creation system of the present invention, a region can include a base, and the search region creation unit can use the base as a reference point.
[0025]
  In the course creation system of the present invention, it is determined by the selected tour point.Course timeCan further include a calculating unit for calculating. here,Course timeCan be a course time determined by the delivery time to the selected tour point. Also,Course timeMay be an amount determined by the amount of articles delivered to the selected patrol point. Both of these can also be considered.
[0026]
  According to the present invention,
  The computer system determines the predetermined reference point andA method for creating a traveling course in an area including a plurality of traveling points,
The computer system includes:
A reference point information storage unit for storing position information of the reference point;
A traveling point information storage unit that stores position information of the plurality of traveling points, and
A course that departs from the reference point in the morning, circulates through each traveling point in the course, takes a break in the middle of the course, travels through the traveling points in the afternoon, and returns to the reference point in the evening. A first upper limit time of the course of the course, a course that departs from the reference point in the morning and goes around the circuit points in the morning course and returns to the reference point, or the reference point after taking a break during the day And the second upper limit time of the second course, the upper limit time being shorter than the first upper limit time. Accepting the settings;
  Based on the setting of the theoretical number n of courses to be created in the region,in frontRegisterA dividing line extending radially around the quasi-pointThe dividing line is set so that the angle formed by the adjacent dividing lines is an approximate value of 360 / n.The regionnDividing into search areas;
Based on the position information of the reference point and the position information of the plurality of circulation points respectively stored in the reference point information storage unit and the cyclic point information storage unit,For each of the search areas, select each of the tour points to include the tour points included in the search area in the same course,AboveThe first coursenA step to create,
Based on the position information of the reference point and the position information of the plurality of circulation points respectively stored in the reference point information storage unit and the cyclic point information storage unit,Course time determined by the tour points included in each first courseCalculateWhen the course time is equal to or longer than the first upper limit time, out of the tour points included in the search area, remove the tour points in order from the reference point,The removed tour point isInclude in the second courseAdjustmentProcessing steps;
The course creation method characterized by including is provided.
[0029]
  In the course creation system of the present invention, in the adjusting step,FirstIn the courseCourse timeApplicable considering the average value ofFirstIn the courseCourse timeIf the value is lower than the average value, the angle formed by the dividing lines that form the search area is expanded, andFirstIn the courseCourse timeIs higher than the average value, a process of narrowing the angle formed by the dividing lines forming the search area can be performed.
[0031]
In the course creation method of the present invention, the step of dividing into search areas can set a dividing line in consideration of road information marking roads included in the area.
[0032]
  In the course creation method of the present invention, eachFirstIn the courseCourse timeUntil the difference is within a predetermined range, the dividing step, the selecting step, and the adjusting step can be repeated.
[0034]
It should be noted that any combination of the above-described constituent elements and a representation obtained by converting the expression of the present invention between a method, an apparatus, a system, and the like are also effective as an aspect of the present invention.
[0035]
DETAILED DESCRIPTION OF THE INVENTION
The course creation system according to the following embodiment, when creating a traveling course in an area including a plurality of traveling points, performs a plurality of searches using dividing lines that radiate the target area radially, centering on the bases in the area. A traveling course is created by dividing the region into regions and including the traveling points included in each search region in the same traveling course. In the following embodiment, it is assumed that a course in which the tour points included in the course are fixed is created, for example, each tour point is visited every week.
[0036]
(First embodiment)
Hereinafter, the first embodiment of the present invention will be described using a traveling point as a store.
In the embodiment of the present invention, an example will be described in which a plurality of tour courses are created when a work for visiting each store is performed in an area including a plurality of stores. Each person in charge starts from the bases such as sales offices and distribution centers every day, and goes around the stores included in his patrol course to replenish and deliver products to stores, strengthen relationships with stores, collect information, and sell After making proposals, contracts, verifications, etc., the patrol work of returning to the base will be performed. Therefore, in order to increase the overall work efficiency, it is preferable to set the traveling course so that the distances between the bases where the person in charge moves and between the stores and between the stores and the stores are as short as possible. Although the patrol work can be performed on foot, in the present embodiment, the patrol work using a vehicle such as an automobile will be described. The delivery course may be provided with a plurality of course forms such as those having different delivery time upper limits and different movement distances.
[0037]
FIG. 1 is a flowchart showing a procedure of a course creation method in the present embodiment. First, various data such as map information data, base information data, and store information data necessary for course creation are registered (S2). Next, conditions necessary for course creation are set (S4). Subsequently, parameters necessary for dividing the target area into a plurality of search areas are set (S6). Thereafter, stores to be included in the same course for each of the plurality of search areas set in the area are sequentially selected, and a plurality of courses are created (S8). Subsequently, the course creation result is evaluated and recreated (S10). When the evaluation and re-creation are finished, the course creation process is finished.
[0038]
FIG. 2 is a block diagram showing the configuration of the course creation system in the present embodiment. The course creation system 100 includes a display processing unit 108, a condition setting reception unit 110, a parameter setting reception unit 111, a store selection unit 112, a determination unit 114, a calculation processing unit 116, an adjustment processing unit 122, a course State evaluation unit 124, search area creation unit 161, map information storage unit T1, base information storage unit T2, store information storage unit T3, condition storage unit T4, course information storage unit T5, logic storage unit T6, parameter storage unit T7, and search area storage unit T10. The calculation processing unit 116 includes a calculation unit 118 and an order determination unit 121.
[0039]
The map information storage unit T1 stores map information data of a region for which a course is to be created. Moreover, in this Embodiment, map information storage part T1 memorize | stores the road information which marked road information, such as a main road contained in map information data. The base information storage unit T2 stores base information data. The base information data includes a base identification code, a base name, a base position (latitude and longitude, or X coordinate and Y coordinate), and the like. Here, the base is, for example, a delivery base such as a sales office or a distribution center in the area.
[0040]
The store information storage unit T3 stores store information data. The store information data includes a base identification code, store identification code, store name, store position (latitude, longitude and height, or X coordinate, Y coordinate and Z coordinate), and work time per minute (minutes) , Number of monthly visits (tours), visit date and time conditions, flexibility parameters, monthly sales (yen), monthly sales volume for each product (pieces), travel speed from the base (km / hour), travel speed between stores (km / Information necessary for selecting a store to be included in the same course and calculating statistics such as course time. The flexibility parameter is a parameter indicating the degree of restriction of each store when included in the course. For example, a store with a fixed day of the week and time of visit must visit on that day or time, and the degree of restriction is strong. Therefore, the flexibility parameter is set low. Also, stores with a high number of visits per month have a low flexibility parameter.
[0041]
FIG. 3 is a diagram showing a part of the data structure of the store information storage unit T3 in the present embodiment. Here, the store information storage unit T3 includes a base code column, a store code column, a name column, a position column, a height column, a work time column, a frequency column, a date / time condition column, a flexibility parameter column, and the like. Here, for example, the store with the store code “a” belongs to the base with the base code “1000”, the name is “super”, and the position is “(X₁, Y₁) ”, The height is“ above ground ”, the working time at this store is“ 25 minutes ”, the number of visits per month is“ 8 times ”, and the date and time condition of the visit is“ − (none in particular) ”. In addition, since this store has 8 visits per month but no date / time conditions, the flexibility parameter is medium “3”. For example, the store with the store code “b” belongs to the base with the base code “1000”, the name is “shopping mall 1”, and the position is “(X₂, Y₂) ”, The height is“ above ground ”, the working time at this store is“ 15 minutes ”, the number of visits per month is 12 times, and the date and time conditions for visits are“ Monday / Wednesday / Friday ”. That is, it is necessary to visit the store with the store code “b” every Monday, Wednesday, and Friday. In this store, since the number of visits per month is “12” and the date and time conditions are determined, the flexibility parameter is the lowest “1”.
[0042]
Returning to FIG. 2, the display processing unit 108 performs processing for displaying various data, the created course state, and the like on a screen (not shown) together with map information.
[0043]
The condition setting accepting unit 110 accepts setting of various conditions for course creation from the user. The condition setting accepting unit 110 accepts setting of conditions such as a standard work time for each person in charge, a standard work time at each store, a standard moving speed between stores, and a standard moving speed between bases and stores, for example. . The condition storage unit T4 stores the set conditions.
[0044]
In addition, the condition setting reception unit 110 receives a setting of an allowable range of statistics. The acceptable range is the upper and lower limits of desirable statistics. Hereinafter, in the present embodiment, the course time will be described as a statistic. The course time is the time from the base to the stores in the course before returning to the base. The course time includes travel time by car and work time at each store. For example, the upper limit of the course time can be the daily standard work time of each person in charge, and the lower limit time can be set so that the difference from the upper limit time is within one hour.
[0045]
The parameter setting receiving unit 111 receives parameter settings necessary for dividing the target area into a plurality of search areas. The target area is divided into a plurality of search areas by dividing the area with dividing lines that spread radially from the base. Here, the parameters include a desirable theoretical number of courses to be created in the area, setting conditions for the first dividing line, angles formed by adjacent dividing lines, and the like. The first dividing line can be set taking into account the location of the marked road in the region, for example, starting from the base and taking into account the axis connecting the seed store and base set in the base. You can also Further, the angle formed by the adjacent dividing lines can be, for example, an angle obtained by dividing a circle (360 °) centered on the base by the theoretical number of courses. The method of dividing the target area will be described later.
[0046]
The parameter storage unit T7 stores the parameters set in this way. FIG. 4 is a diagram illustrating a part of the data structure of the parameter storage unit T7. The parameter storage unit T7 also stores data related to selection conditions for seed stores, for example. The selection conditions for the seed store include a case of selecting from a position close to the base and a case of selecting from a position far from the base. Here, it is set to select from a position far from the base. Further, it is set that the course creation process may be terminated if the theoretical number of courses is 12 and the allowable range is +2, that is, if the number of courses is within 14. In this case, the angle between adjacent dividing lines is set to 30 degrees, and the allowable range is set to -10 degrees to +30 degrees.
[0047]
Returning to FIG. 2, the search area creation unit 161 refers to the parameter storage unit T7 and performs a process of creating a plurality of search areas in the area. The search area storage unit T10 stores at least temporarily information related to the search area set by the search area creation unit 161.
[0048]
The store selection unit 112 refers to the search region storage unit T10 and selects stores to be included in the same course for each search region created by the search region creation unit 161. The course creation process will be described later. The course information storage unit T5 stores information related to the created course.
[0049]
In the calculation processing unit 116, the calculation unit 118 calculates statistics such as course time. The calculation processing unit 116 also calculates an average value of course times of a plurality of courses. The order determination unit 121 determines the order of visiting the stores included in the course for each created course. The tour order determined by the order determination unit 121 is also stored in the course information storage unit T5. A method for determining the cyclic order by the order determining unit 121 will also be described later.
[0050]
The determination unit 114 determines whether or not the course time in each course calculated by the calculation unit 118 is within a predetermined allowable range. The adjustment processing unit 122 performs processing such as adjustment of store distribution between courses when the course time is not within a predetermined allowable range.
[0051]
The logic storage unit T6 stores logic relating to various processing procedures.
[0052]
After the course creation process is performed, the course state evaluation unit 124 determines the suitability of course creation by comparing the number of courses finally created with the theoretical number.
[0053]
FIG. 5 is a flowchart specifically showing the course creation process in step 8 shown in FIG.
First, the search area creation unit 161 sets a dividing line that serves as a reference for dividing an area into a plurality of search areas (S18). For example, the search area creation unit 161 selects a seed store from stores in the region, sets an axis passing through the seed store starting from the base, and sets the first division line in consideration of the axis. Can do. Here, the calculation processing unit 116 may refer to the store information storage unit T3 and select a seed store in order from a store having a low flexibility parameter. A store having a low flexibility parameter is, for example, a store having a large number of visits per month or a store having a visit date / time specified. In addition, the search area creation unit 161 may select a seed store according to the distance from the base or the like with reference to the parameter storage unit T7. The search area creation unit 161 can also set the first dividing line in consideration of the position of the marked road with reference to the map information storage unit T1.
[0054]
The search area creation unit 161 sequentially sets a plurality of division lines that spread radially around the base in consideration of the angle formed by the adjacent division lines with reference to the parameter storage unit T7 with the first division line as a reference. I will do it. The search area creation unit 161 divides the area into a plurality of search areas using the area surrounded by the dividing line as a search area (S20).
[0055]
An example of the search area dividing method will be described with reference to FIG. FIG. 6 is a diagram showing points in a region and a plurality of stores. The search area creation unit 161 refers to the parameter storage unit T7 and divides the area into a plurality of search areas based on various preset parameters. As shown in FIG. 6A, here, the point a is described as being a seed store. First, the search area creation unit 161 sets a straight line connecting the base and the point a as the axis L with the base as one end. Subsequently, the search area creation unit 161 refers to the parameter storage unit T7, considers the angle formed by the adjacent division lines, and performs the first division so that the search area is divided into two substantially equally by the axis, for example. Set the line. Here, the dividing line d₁Is the first dividing line. At this time, the first dividing line is preferably set in a counterclockwise direction with respect to the axis. In this way, when traveling around the created course by vehicle, it is possible to visit the store on the left side sequentially on the outbound route and then visit the store on the left side on the return route as well, efficiently. This is because a course that can be visited can be created. Subsequently, the search area creation unit 161 refers to the parameter storage unit T7 and considers the angle formed by the adjacent division lines, and then determines the next division line d.₂Set. As shown in FIG. 6B, the search area creating unit 161 similarly uses a plurality of dividing lines d.₃~ D₁₂Set. Thus, this area is divided into 12 search areas.
[0056]
FIG. 7 is a diagram illustrating another example of the search area dividing method. In this area, for example, a road as indicated by a broken line in FIG. 7A is marked. As shown in FIG. 7B, the search area creation unit 161 selects a reference main road from among the marked roads. As described above, the search area creation unit 161 refers to the parameter storage unit T7, considers the angle formed by the adjacent dividing lines, and the search area is divided into two substantially evenly by the marked main road, for example. Thus, the first dividing line can be set. Again, the dividing line d₁Is the first dividing line. Again, as described above, the first dividing line is preferably set in a counterclockwise direction with respect to the main road. In this way, when traveling around the created course by vehicle, it is possible to visit the store on the left side sequentially on the outbound route and then visit the store on the left side on the return route as well, efficiently. This is because a course that can be visited can be created. In addition, when the vehicle is directed to a domestic area where traffic is on the right side, the direction is preferably reversed. Subsequently, the search area creation unit 161 refers to the parameter storage unit T7 and considers the angle formed by the adjacent division lines, as shown in FIG.₂Set.
[0057]
Returning to FIG. 5, the store selection unit 112 selects each search region divided by the search region creation unit 161 to include stores in the search region in the same course (S22). When the course is created, the order determining unit 121 sequentially visits the stores belonging to the region in the counterclockwise direction with respect to the axis L connecting the base and the seed store with the base as the starting point. The order of patrol is determined so as to invert the store at the farthest position and sequentially visit the stores belonging to the region in the clockwise direction with respect to the axis L. In this way, when the vehicle performs a patrol work in a left-handed country, it is possible to first visit the store on the left side of the road on the outbound route, and then visit the store on the left side on the return route. It is possible to create a course that can be visited efficiently. The calculation unit 118 calculates the statistics of the stores included in the course (S24). Here, the statistic is a course time in the course. Subsequently, the calculation unit 118 calculates the average value of the statistics of these courses.
[0058]
The determination unit 114 determines whether or not the statistic amount in each course is within a predetermined allowable range (S26). When the statistics in all courses are within the predetermined allowable range (Yes in S26), the determination unit 114 determines whether or not the difference in statistics in each course is within the predetermined allowable range (S28). If the difference in statistics in each course is within the predetermined allowable range (Yes in S28), the course creation process ends. Here, the difference of the statistics in each course can also be calculated by comparison with the average value of the statistics of all courses.
[0059]
In step 26, when the statistic in any course is not within the predetermined allowable range (No in S26), the determination unit 114 determines whether or not the statistic in the course is greater than or equal to the allowable range (S30). . When the statistic in the course is lower than the allowable range (No in S30), the process returns to step 20, and the process of creating the search area by increasing the number of courses created in the target area is performed again. In step 30, when the statistical amount in the target course is equal to or larger than the allowable range (Yes in S30) or the difference in statistical amount in each course is not within the predetermined range (No in S28), the adjustment processing unit 122 performs the adjustment. Processing is performed (S32), and the course creation processing is terminated.
[0060]
As the adjustment process, the following two methods can be mainly used.
The first method will be described with reference to FIG. As a result of the calculation unit 118 calculating the course time and the average value thereof as described above, for example, the dividing line d₅And d₆When the statistic of the course created for the search area 5 surrounded by is higher than the average value of the statistic, the adjustment processing unit 122 uses the dividing line d that forms the search area 5.₅And d₆Make adjustments to reduce the angle formed by. At this time, the adjustment processing unit 122, for example, the dividing line d₄And d₅The statistics of the course created for the search area 4 surrounded by and the dividing line d₆And d₇Is compared with the statistic of the course created for the search area 6 surrounded by, and the dividing line between the search area with the smaller statistic is moved. Here, for example, it is assumed that the statistic of the course created for the search area 6 is smaller than the statistic of the course created for the search area 4. In this case, the adjustment processing unit 122 performs the dividing line d as illustrated.₆Is moved in the direction of the search area 5, and the dividing line d forming the search area 5₅And d₆The dividing line d forming the search area 6 is narrowed₆And d₇Processes that increase the angle between Further, the adjustment processing unit 122 is configured to output the dividing line d.₆And parting line d₅It is also possible to move both of them and perform a process of narrowing the search area 5. The adjustment processing unit 122 repeats the same processing until the statistics in each search range are within a predetermined allowable range, and the difference in statistics between courses is within the predetermined allowable range.
[0061]
Further, the adjustment processing unit 122 performs a process of widening the angle of the dividing line forming the search area for the search area whose course statistic is lower than the average value of the statistic. By repeating such a process many times, it is possible to obtain an optimal solution in which the statistics in the courses created for each search area are substantially equal. In the present embodiment, by providing a predetermined range for the statistic and the difference between the statistic, the process for obtaining the optimum solution that satisfies the course creation end condition can be performed quickly, and the course creation can be performed quickly. it can.
[0062]
Next, the second method will be described with reference to FIG. As shown in FIG. 9A, the order determination unit 121 circulates a store on the left side of the main road in the traveling direction of the outbound route, and turns back at the store farthest from the base, and also in the traveling direction of the return route. The patrol order is decided so that the store on the left side of the road is patroled. As a result of calculating the statistic in each course when the calculation unit 118 visits each store in the order determined in this way, the statistic of the course created for a certain search area is an allowable value of the statistic. When the difference from the average value of the statistic amount with the range or more is greater than the allowable range, the adjustment processing unit 122, among the stores included in the course, as shown in FIG. For example, it is possible to remove a store close to the base, create a first course including the remaining stores, and then create a second course including a store removed from the first course.
[0063]
Here, the first course and the second course can be set so that the upper limit of the course time is different, for example. For example, the first course is a course that departs from the base in the morning and goes to each store in the course, takes a break during the day, goes around the store in the afternoon, and returns to the base in the evening Can do. The second course is a course that departs from the base in the morning and visits each store in the morning course to return to the base, or leaves the base after taking a break during the day and visits each store in the course Then, it can be a course returning to the base in the evening. When going around a store far from the base, it takes longer to return to the base, so it is more efficient to include it in the first course.
[0064]
Here, an example in which the first course and the second course are created for the same search area has been described, but the second course may be created so as to extend over a plurality of search areas. For example, the adjustment process part 122 performs the process which removes a store in order from the base, when the course time in a certain course is more than upper limit time. Such a process is repeated, and the same process is repeated until the course time in the course falls below the upper limit, and the course time of the course falls within a predetermined range from the average value of other courses. As a result of performing such processing, the store selection unit 112 can appropriately select a course that has been removed from each course and create a second course.
[0065]
Next, an example of how to obtain the theoretical number of courses to be created in a certain area will be described with reference to FIG. It is a figure which shows an example of the procedure for calculating the theoretical number of courses required in an area.
The calculation unit 118 appropriately refers to the base information data stored in the base information storage unit T2, the store information data stored in the store information storage unit T3, and the various conditions stored in the condition storage unit T4, as follows. Calculate the theoretical number of courses in the procedure.
[0066]
The calculation unit 118 calculates the average travel time M from the base to the store in the target area.₁Is calculated (S160). First, after obtaining the total distance from the base to each store, the total travel time is obtained by dividing this total distance by the standard travel speed between the base and the store stored in the condition storage unit T4. Then, by dividing this total travel time by the total number of stores, M₁Is required.
[0067]
Subsequently, the calculation unit 118 calculates the average travel time M between stores.₂Is calculated (S162). First, after obtaining the total distance from each store to the nearest n stores, the total travel time is obtained by dividing this total distance by the standard travel speed between stores stored in the condition storage unit T4. Then, the average travel time m from each store to other stores is obtained by dividing this total travel time by n.₁~ M_nGet. Next, the average travel time m₁~ M_nAnd M by dividing by the total number of stores₂Is calculated.
[0068]
Subsequently, the calculation unit 118 calculates the number N of stores that can be worked in one day in this area.₁Is calculated (S164). Total work time per day
Tz = M₁× 2 + M₂(N₁-1) + T × N₁
(T is the average work time per store)
So, transform this equation
N₁= (Tz-M₁× 2 + M₂) / (M₂+ T)
Is calculated.
[0069]
On the other hand, the calculation unit 118 calculates the number N of stores that require processing per day.₂Is calculated (S166). First, the number of times of loading W per month is calculated by calculating and summing the number of deliveries per month for each store. Next, assuming that the number of working days in January for each person in charge is 4 weeks x 5 days = 20, N₂= W / 20 is obtained.
[0070]
Thereafter, the calculation unit 118 calculates the number N of stores that need to be processed per day.₂N stores that can work in a day₁The theoretical number of required courses per day = N₂/ N₁Is calculated (S168).
[0071]
The search area creation unit 161 determines the angle formed by the dividing lines forming each search area based on the theoretical number calculated in this way.
[0072]
When the course is created as described above, a radial flower-shaped course shaped like a flower petal is created as shown in FIG. FIG. 11A schematically shows the shape of the course when only the first course is created, and FIG. 11B schematically shows the shape of the course when the second course is also created.
[0073]
Thereby, it is possible to create a course in which the states of a plurality of courses can be clearly understood. Moreover, according to the course creation system 100 of the present embodiment, it is possible to create a course that can efficiently perform operations such as visits and patrols. In particular, when moving by a vehicle such as a car, the stores to be included in the same course are selected mathematically and objectively in consideration of the axis line and the main road passing through the base and the seed store. A high course can be created. As a result, it is possible to create a course that provides a sense of fairness among workers. In addition, in this way, by creating a course objectively with little consideration of actual problems such as actual geography, it is possible to simulate course creation in a very short period of time with only the minimum necessary parameter settings. Can do.
[0074]
(Second embodiment)
Also in this embodiment, the traveling point is a store. Also in the present embodiment, the course creation system 100 has the same configuration as that described with reference to FIG. 2 in the first embodiment.
[0075]
Hereinafter, a course creation method according to the present embodiment will be described with reference to FIGS.
As shown in FIG. 12A, in the present embodiment, the search area creation unit 161 performs the first dividing line d in the same manner as described with reference to FIG. 5 in the first embodiment.₁And the next dividing line d₂Set. Here, the order determining unit 121 uses the dividing line d.₁And parting line d₂For the stores included in the search area surrounded by, the circulation order of these stores is determined. The calculation unit 118 calculates a course time which is a statistic when the stores are visited in this order. In the present embodiment, when the course time is not within a predetermined allowable range, the adjustment processing unit 122 determines that the dividing line d₁And parting line d₂Performs processing to widen or narrow the angle formed by.
[0076]
For example, in the state shown in FIG.₁And parting line d₂When the course time of the course created in the search area surrounded by is lower than the predetermined range, the adjustment processing unit 122₁And parting line d₂For example, the dividing line d₁'And parting line d₂Perform the process of creating a course again using the area enclosed by 'as the search area. Here, the adjustment processing unit 122 uses the dividing line d.₁'And parting line d₂The angle is adjusted so that the course time of the course created in the search area surrounded by 'falls within a predetermined range.
[0077]
As a result of the adjustment process, when the course time of the course in the search area falls within a predetermined range, as shown in FIG.₂To create the next search area. After this, the adjustment process is performed in the same manner, and the next course is sequentially created.
[0078]
(Third embodiment)
Also in this embodiment, the traveling point is a store. Further, in the present embodiment, an example will be described in which a plurality of delivery courses for delivering merchandise by truck to each store are created within an area including a plurality of stores. Each person in charge carries out a delivery operation of loading articles on a truck at a delivery base every day, delivering the goods to a store included in his delivery course, and then returning to the delivery base. Therefore, in order to increase the overall work efficiency, it is preferable to set the delivery course so that the distances between the bases where the person in charge moves and between the stores and between the stores and the stores are as short as possible. Further, it is preferable to set the delivery course in consideration of the upper limit of the truck load capacity.
[0079]
Also in the present embodiment, the course creation system 100 has the same configuration as that described with reference to FIG. 2 in the first embodiment. In the present embodiment, the base is a delivery base such as a distribution center in the target area.
[0080]
In addition to the information described in the first embodiment, the store information storage unit T3 selects a store to be included in the same course, such as a delivery amount for each store, a total amount, a course time, etc. Contains information necessary to calculate the statistic.
[0081]
FIG. 14 is a diagram showing a part of the data structure of the store information storage unit T3 in the present embodiment. Here, the store information storage unit T3 includes a delivery amount column in addition to the information described with reference to FIG. 3 in the first embodiment. Here, for example, the delivery amount per time at the store with the store code “a” is 0.001 t. Further, for example, the delivery amount per time at the store with the store code “b” is 0.002 t.
[0082]
In addition to the conditions described in the first embodiment, the condition setting reception unit 110 receives setting of conditions such as a load amount of a truck.
[0083]
In addition, the condition setting reception unit 110 also receives settings for the maximum load amount and the lower limit load amount of the truck. Here, the maximum load amount is an amount in which no more items can be loaded in each truck, and the lower limit load amount is a lower limit target value of the load amount. Here, when a 2t truck is used, for example, the maximum load capacity can be set to 2t, and the lower limit load capacity can be set to 1.6t which is 80% of the maximum load capacity. Moreover, the condition setting reception part 110 receives the setting of the upper limit and the minimum of course time similarly to 1st embodiment. The course time includes the running time of the truck and the working time at each store.
[0084]
Furthermore, the condition setting accepting unit 110 can accept selection of a course type, such as a one-day course or a half-day course, as in the first embodiment. Considering the amount of goods that can be loaded onto a truck, for example, when going around a store close to the base, the half-day course is substantially equivalent to the total quantity that can be delivered by one truck. The increase increases the efficiency.
[0085]
Similar to the first embodiment, the store selection unit 112 sequentially selects stores for the search area divided by the search area creation unit 161 and creates a plurality of courses in the area. In the present embodiment, the calculation unit 118 calculates the total quantity in addition to the course time of the store selected by the store selection unit 112.
[0086]
The determination unit 114 determines whether the total amount and the course time calculated by the calculation unit 118 are within a predetermined allowable range. The adjustment processing unit 122 performs the same adjustment processing when the total amount or the course time is not within a predetermined range.
[0087]
According to the course creation system of the present embodiment, even when there is an upper limit on the load amount of an article, for example, when delivering an article by a truck, the delivery worker's Since the course is created in consideration of the delivery time, which is the work time, an objective and effective course can be created.
[0088]
(Fourth embodiment)
FIG. 15 is a diagram showing a network configuration including the course creation system 100 described in the first to third embodiments. The processing from the user described in the first to third embodiments can be performed from the user terminal 150 via the network 148. In the present embodiment, the user terminal 150 may be anything as long as it can communicate with the course creation system 100 via the network 148. For example, the user terminal 150 can be a PC, a PDA, a mobile phone, or any other hardware.
[0089]
In this way, the user can transmit the instruction necessary for the course creation process to the course creation system 100 while actually traveling around the area where the store is installed with the user terminal 150. Thereby, it is possible to objectively input the condition setting and parameter setting to the condition setting receiving unit 110 and the parameter setting receiving unit 111 while reflecting the actual situation of the site.
[0090]
In addition to the configuration described in each embodiment, the course creation system 100 described in the first and second embodiments is a data registration reception that receives registration of various data such as base information data and store information data. You may have a part.
[0091]
FIG. 16 is a block diagram illustrating a configuration when the course creation system 100 according to the first embodiment includes a data registration receiving unit 152. The data registration accepting unit 152 accepts registration of various data from the user and stores these data in the base information storage unit T2 or the store information storage unit T3. Thus, the user can register various data while actually traveling around the area where the store is installed with the user terminal 150. Therefore, more accurate and accurate information can be stored in the base information storage unit T2 and the store information storage unit T3. Even if various data are registered in advance in the base information storage unit T2 or the store information storage unit T3, the data can be updated quickly when there is a change in the situation at the site. By preparing various data stored in the base information storage unit T2 and the store information storage unit T3 accurately and quickly, it is possible to appropriately create a course for the target area.
[0092]
In the present embodiment, since information necessary for the course creation system 100 can be transmitted / received from the user terminal 150 to the course creation system 100 via the network 148, information necessary for course creation is created while actually traveling around the area. Can be sent to the system 100. Therefore, for example, various data can be updated accurately and quickly, and a course can be suitably created.
[0093]
The present invention has been described based on the embodiments. The embodiments are exemplifications, and it will be understood by those skilled in the art that various modifications can be made to combinations of the respective constituent elements and processing processes, and such modifications are within the scope of the present invention. .
[0094]
【The invention's effect】
As described above, according to the present invention, it is possible to provide a technique for creating a course capable of efficiently performing a patrol work by reducing the number of necessary workers when creating a plurality of patrol courses in an area. According to the present invention, such a course can be created objectively. According to the present invention, when creating a plurality of tour courses in a region, the tour points can be appropriately and fairly allocated.
[Brief description of the drawings]
FIG. 1 is a flowchart showing a course creation process according to an embodiment of the present invention.
FIG. 2 is a block diagram showing a configuration of a course creation system in the embodiment of the present invention.
FIG. 3 is a diagram showing a part of the data structure of a store information storage unit in the embodiment of the present invention.
FIG. 4 is a diagram showing a part of a data structure of a parameter storage unit in the embodiment of the present invention.
FIG. 5 is a flowchart specifically showing a course creation process in step 8 shown in FIG. 1;
FIG. 6 is a diagram illustrating an example of a search area dividing method;
FIG. 7 is a diagram illustrating another example of a search area dividing method.
FIG. 8 is a diagram illustrating an example of a method of adjustment processing at the time of course creation.
FIG. 9 is a diagram showing another example of a method of adjustment processing at the time of course creation.
FIG. 10 is a diagram showing a method for obtaining a theoretical number of courses to be created in a certain area.
FIG. 11 is a diagram schematically showing the shape of a course created in the embodiment of the present invention.
FIG. 12 is a diagram for explaining a course creation method according to the embodiment of the present invention.
FIG. 13 is a diagram for explaining a course creation method according to the embodiment of the present invention.
FIG. 14 is a diagram showing a part of the data structure of the store information storage unit in the embodiment of the present invention.
FIG. 15 is a diagram showing a network configuration including a course creation system of the present invention.
FIG. 16 is a block diagram showing a configuration of a course creation system in the embodiment of the present invention.
[Explanation of symbols]
100 course creation system
108 Display processing unit
110 Condition setting reception part
111 Parameter setting reception part
112 Store selection department
114 Judgment part
116 Calculation processing unit
118 Calculation unit
121 Order determination unit
122 Adjustment processing unit
124 Course condition evaluation department
148 network
150 User terminal
152 Data registration reception
161 Search area creation part
T1 map information storage unit
T2 site information storage
T3 store information storage
T4 condition storage
T5 Course information storage
T6 logic storage
T7 parameter storage unit
T10 search area storage

Claims (13)

A computer system for creating a traveling course in an area including a predetermined reference point and a plurality of traveling points,
A reference point information storage unit for storing position information of the reference point;
A traveling point information storage unit for storing position information of the plurality of traveling points;
A course that departs from the reference point in the morning, circulates through each traveling point in the course, takes a break in the middle of the course, travels through the traveling points in the afternoon, and returns to the reference point in the evening. A first upper limit time of the course of the course, a course that departs from the reference point in the morning and goes around the circuit points in the morning course and returns to the reference point, or the reference point after taking a break during the day And the second upper limit time of the second course, the upper limit time being shorter than the first upper limit time. A condition setting receiving unit for receiving settings;
Based on the setting of the theoretical number n of course to be created in the area before the split line extending radially from the Kimoto Junten, so that the angle of the parting line adjacent forms becomes the approximate value of 360 / n A search area creating unit that sets the dividing line to divide the area into n search areas;
Based on the position information of the reference point and the position information of the plurality of circulation points respectively stored in the reference point information storage unit and the cyclic point information storage unit, for each of the search areas, wherein the cyclic point to be included in the same course to select each said cyclic point, a selection unit for the first course to the n creation contained,
The cyclic points included in each of the first courses based on the position information of the reference points and the position information of the plurality of cyclic points respectively stored in the reference point information storage unit and the cyclic point information storage unit calculating a course time determined by, if the course time is more than the first upper limit hour, of the cyclic point included in the search area, the disconnect cyclic point to close to the reference point, removed the An adjusting unit that performs processing for including a traveling point in the second course;
Course creation system characterized by including.   In the course creation system according to claim 1,
  A parameter setting receiving unit for receiving the setting of the theoretical number n;
  The search area creation unit divides the region into the n search areas based on the setting of the theoretical number n received by the parameter setting reception unit. In the course creation system according to claim 1,
A theoretical number calculator for calculating the theoretical number n of the course;
The traveling point information storage unit stores the number of delivery times per month for each traveling point,
The theoretical number calculator is
Based on the position information of the reference point and the position information of the plurality of circulation points respectively stored in the reference point information storage unit and the circulation point information storage unit, from the reference point to the circulation point in the region The average travel time M ₁ and the average travel time M ₂ between each of the tour points are calculated, and based on the number of deliveries stored in the tour point information storage unit, the plurality of tour points in the region are calculated . Divide the number of deliveries per month by the number of working days to calculate the number of traveling points N ₂ that need to be processed per day ,
In this area, the number of traveling points N ₁ that can be worked in a day is
Total work time for one day Tz = M ₁ × 2 + M ₂ (N ₁ −1) + T × N ₁
(T is the average working time per round point),
N ₁ = (Tz−M ₁ × 2 + M ₂ ) / (M ₂ + T)
Calculated from
The theoretical number n = N ₂ / N ₁ of the first course is calculated by dividing the number of traveling points N ₂ that need to be processed per day by the number of traveling points N ₁ that can be worked on in one day. Course creation system characterized by doing. In the course creation system according to any one of claims 1 to 3 ,
The course creation system, wherein the second course is created so as to span a plurality of the search areas. In the course creation system according to any one of claims 1 to 4 ,
The course creation system, wherein the search area creation unit divides the area into the n search areas with the reference point as a center so that angles formed by the adjacent dividing lines are substantially equal. In the course creation system according to any one of claims 1 to 5 ,
The adjustment unit considers an average value of the course time in each of the first courses, and forms the search area when the course time in the corresponding first course is lower than the average value. A process of widening the angle formed by the dividing line is performed, and when the course time in the corresponding first course is higher than the average value, a process of narrowing the angle formed by the dividing line forming the search area is performed. A course creation system characterized by that. In the course creation system according to any one of claims 1 to 6 ,
The course creation system, wherein the search area creation unit sets the dividing line in consideration of road information marking a road included in the area. In the course creation system according to any one of claims 1 to 7,
The patrol work is done using a vehicle,
It further includes an order determining unit that determines the order in which the stores included in the course are circulated for each of the created courses, and the order determining unit circulates in order from the traveling point located on the traffic direction side of the vehicle. A course creation system characterized by determining the order. A method for creating a traveling course in a region including a predetermined reference point and a plurality of traveling points by a computer system ,
The computer system includes:
A reference point information storage unit for storing position information of the reference point;
A traveling point information storage unit that stores position information of the plurality of traveling points, and
A course that departs from the reference point in the morning, circulates through each traveling point in the course, takes a break in the middle of the course, travels through the traveling points in the afternoon, and returns to the reference point in the evening. A first upper limit time of the course of the course, a course that departs from the reference point in the morning and goes around the circuit points in the morning course and returns to the reference point, or the reference point after taking a break during the day And the second upper limit time of the second course, the upper limit time being shorter than the first upper limit time. Accepting the settings;
Based on the setting of the theoretical number n of course to be created in the area before the split line extending radially from the Kimoto Junten, so that the angle of the parting line adjacent forms becomes the approximate value of 360 / n Setting the dividing line to divide the region into n search regions;
Based on the position information of the reference point and the position information of the plurality of circulation points respectively stored in the reference point information storage unit and the cyclic point information storage unit, for each of the search areas, a step wherein the cyclic point select each said cyclic point to be included in the same course, the first course to the n creation contained,
The cyclic points included in each of the first courses based on the position information of the reference points and the position information of the plurality of cyclic points respectively stored in the reference point information storage unit and the cyclic point information storage unit calculating a course time determined by, if the course time is more than the first upper limit hour, of the cyclic point included in the search area, the disconnect cyclic point to close to the reference point, removed the Performing an adjustment process for including a traveling point in the second course;
The course creation method characterized by including. In the course preparation method of Claim 9,
The course creation method, wherein the second course is created across a plurality of the search areas. In the course creation method according to claim 9 or 10 ,
In the step of performing the adjustment process, if the course time in the corresponding first course is lower than the average value in consideration of the average value of the course time in each of the first courses, the search area When the course time in the corresponding first course is higher than the average value, the angle formed by the parting lines forming the search area is narrowed. A course creation method characterized by performing processing.   In the course preparation method in any one of Claims 9 thru | or 11,
  Further comprising receiving a setting of the theoretical number n;
  In the step of dividing the region into n search regions, the region is divided into the n search regions based on the setting of the theoretical number n received in the step of receiving the setting of the theoretical number n. How to create a course. In the course preparation method in any one of Claims 9-11,
The traveling point information storage unit stores the number of delivery times per month for each traveling point,
Based on the position information of the reference point and the position information of the plurality of circulation points respectively stored in the reference point information storage unit and the circulation point information storage unit, from the reference point to the circulation point in the region The average travel time M ₁ and the average travel time M ₂ between each of the tour points are calculated, and based on the number of deliveries stored in the tour point information storage unit, the plurality of tour points in the region are calculated . Divide the number of deliveries per month by the number of working days to calculate the number of traveling points N ₂ that need to be processed per day ,
In this area, the number of traveling points N ₁ that can be worked in a day is
Total work time for one day Tz = M ₁ × 2 + M ₂ (N ₁ −1) + T × N ₁
(T is the average working time per round point),
N ₁ = (Tz−M ₁ × 2 + M ₂ ) / (M ₂ + T)
Calculated from
The theoretical number n = N ₂ / N ₁ of the first course is calculated by dividing the number of traveling points N ₂ that need to be processed per day by the number of traveling points N ₁ that can be worked on in one day. The course creation method further comprising the step of:

Images