Visiting plan generation method and system

• US 7,054,825 B1
• Filed: 09/25/2000
• Issued: 05/30/2006
• Est. Priority Date: 09/24/1999
• Status: Expired due to Term

• Current Assignee: Engage Nova Pte. Ltd.
• Original Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Inventors: Maenishi, Yasuhiro, Kindo, Toshiki, Shida, Takehiko, Hirahara, Makoto
• Primary Examiner(s): Hafiz, Tariq R.
• Assistant Examiner(s): TARAE, CATHERINE MICHELLE
• Application Number:
  US09/668,296
• Time in Patent Office: 2,073 Days
• Field of Search: 705/8, 705/10, 705/9
• US Class Current: 705/7.22
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G06Q 10/06312 Adjustment or analysis of established resource schedule, e.g. resource or task levelling, or dynamic rescheduling

Abstract

A visiting plan generation method and system for promptly carrying out optimum formation of groups, optimum destination assignment to the groups, and optimum planning for each of the groups in an optimization problem of an action plan. In implementation, at least information on plural groups which are to take visiting actions, information on members of each of the plural groups, and information on destinations are received by input means, and optimum formation of the plural groups and optimum destination assignment to each of the plural groups are performed by cost calculation means which provides a cost function for evaluating a visiting plan. Thus, in preparation of a visiting plan for a plurality of groups to visit a plurality of destinations on a task-sharing basis, it is possible to carry out optimum formation or the plural groups, optimum destination assignment to the plural groups, and optimum planning for each of the plural groups.

Claims

1. A visiting plan generation system, comprising:

a plan generating means for generating a visiting plan of a group at a predetermined point of time, based on information including locations of destinations, and conditions of tasks to be performed as information on said destinations, and information of said group constructed by a plurality of members including a mobile capacity (speed of movement) and a working capability defined by time required for the tasks of said members necessary for visiting plan generation;

a destination assignment means for assigning a destination to the group and the members of the group when the plan generating means generates the visiting plan;

a state memory means for memorizing a state X showing said visiting plan generated, the members of said each group and information on destination assignment to each group, and an optimum state in preceding visiting plan conditions;

a state re-arrangement means connected with said state memory means for re-arranging the visiting plan to an optimum states by re-arranging the destination to the group and the members of the group based on the state X memorized in said state memory means;

a cost calculation means for calculating total time spent in moving and total time spent in working as the visiting plan cost Fi (Xi) of each group, based on information including locations of destinations, and conditions of tasks to be performed as information on said destinations, and information of said group constructed by a plurality of members including a mobile capacity (speed of movement) and a working capability defined by time required for the tasks of said members necessary for visiting plan generation;

a plan re-formation means for re-forming a visiting plan Xi for each group based on information including locations of destinations, and conditions of tasks to be performed, information of said group constructed by a plurality of members including a mobile capacity (speed of movement) and a working capability defined by time required for the tasks of said members, and information of visiting plan cost Fi (Xi) of the group, and sending the re-formed visiting plan data to said state re-arrangement means;

wherein said state re-arrangement means re-arranges members of the group and visiting plan thereof to an optimum state, using the visiting plan Xi of the group I under the state X sent from the plan re-formation means and the visiting plan cost Fi (Xi) thereof, and sending the re-arranged visiting plan data to the state memory means as a visiting plan of the group I to an optimum state.

2. A visiting plan generation system as claimed in claim 1, wherein the state re-arrangement means comprises:

new-assignment means for newly assigning an unassigned destination to a group based on a state X memorized in the state memory means;

re-assignment means for re-assigning an already assigned destination based on a state X memorized in the state memory means;

group re-arrangement means for re-arranging groups based on a state X memorized in the state memory means.

3. A visiting plan generation system as claimed in claim 1, wherein the information on a group contains the members constructing a group and constraints between the members of the group.

4. A visiting plan generation system as claimed in claim 3, wherein the group constraints contains a maximum number of the members which can belong to the group.

5. A visiting plan generation system as claimed in claim 1, wherein the information on a group contains information that said group is an invariable-member group in which the members of the group cannot be re-arranged, or said group is a variable-member group in which the members of the group can be re-arranged.

6. A visiting plan generation system as claimed in claim 1, wherein the state re-arrangement means re-arranges members of the group and visiting plan thereof to an optimum state, in which a state cost function F(X) giving maximum value of the cost among the groups is minimized by using the visiting plan Xi of the group i under the state X and the visiting plan cost Fi(Xi) thereof.

7. A visiting plan generation system as claimed in claim 1, wherein the state re-arrangement means re-arranges members of the group and visiting plan thereof to an optimum state, in which a state cost function F(X) giving average value of the cost among the groups is minimized by using the visiting plan Xi of the group i under the state X and the visiting plan cost Fi(Xi) thereof.