Optimization of Customer-service Planning for Distribution Facilities using Digital Annealer

3. Evaluation of effectiveness in customer-service planning

The Power Distribution Department of Chubu Electric Power Grid Co., Inc. is engaged in the construction and maintenance of utility poles, power lines, and other facilities to deliver electricity to its customers. In daily maintenance operations, service engineers (SEs) at each business office are dispatched to specific sites to perform construction, inspection, or restoration work as needed in response to applications from customers in their service area for the supply or discontinuance of electricity, expansion of facilities, etc. or on receiving information on a power outage due to some sort of failure.

In this type of job scheduling (customer-service planning), the operations manager of the customer service center creates a schedule taking into account the daily work required and the number of personnel needed. However, how best to combine the order of visits, assignment of jobs, etc. is not necessarily obvious, so it would be highly useful if the optimization of scheduling could be automated. Additionally, in the case of an unexpected event occurring during work (such as a power outage or electric shock requiring an urgent response), there would be a need for flexible rescheduling based on working conditions at each site, the current location of each SE, and other relevant information.

Given this problem and taking into account a variety of constraints such as the order of visiting customers’ homes, SE work skills, time periods in which work can be performed, and the time needed to travel from one site to another, the number of combinations in job scheduling that could be considered would be massive. The focus of this study is to evaluate the effectiveness of Digital Annealer in solving this type of combinatorial optimization problem.

3.1 Optimization criteria and constraint conditions

On evaluating Digital Annealer, we analyzed the target task and defined the following optimization criteria (objective functions):

• Reduction of work time
• Optimization of number of SEs
• Workload leveling among SEs

In this study, we targeted only a reduction of work time over all SEs.

We also defined the following constraint conditions in optimization:

• Each job is executed only once.
• Each SE cannot execute another job from the time a job is begun until it is finished.
• Each SE cannot perform another job while traveling.
• There are jobs whose execution times have been established.
• The first job is defined as arriving at the office and each worker begins work at a prescribed time.
• The last job is defined as returning to the office and each worker returns to the office at some time after which no work can be executed.

The concept of optimizing customer-service planning is shown in Figure 1. Scheduling in customer-service planning must reduce the overall work time. For example, switching job A2 of SE-A with job B2 of SE-B can shorten the travel time of SE-A and shorten overall work time as a result.

Figure 1 Reduction of work time by optimization of customer-service planning.

3.2 Evaluation Results

The evaluation data for this experiment was provided to us from one business office of Chubu Electric Power Grid as a portion of the work results for one day (40 jobs extracted as electronic data). With this data set, we attempted to automatically create a job schedule under the optimization criteria and constraint conditions described in the previous section.

In actual work, it was necessary to consider the following additional conditions:

• All SEs return to the office at 12:00 and take a lunch break until 13:00.
• Travel time by car differs according to the time of day.
• Unexpected work may suddenly occur. Job scheduling is revised and rescheduled from the time of that occurrence.

In this evaluation, we compared optimization results by Digital Annealer and an existing commercial solver (Gurobi Optimizer [3]) using the evaluation data described above. Specifications of the server for Gurobi Optimizer are as follows: CPU: Intel® Xeon® CPU E5-2680 2.7 GHz × 32 cores; memory: 200 GB.

The evaluation results are listed in Table 2 for the four conditions: (1) 4 SEs, (2) 5 SEs, (3) 5 SEs with unexpected work in the afternoon, and (4) 6 SEs. Note that in condition (3), work is interrupted by the sudden occurrence of unexpected work at the beginning of work in the afternoon so that work rescheduling is performed at that time.

Table 2 Test results.

First, focusing on the results for solving time (time required for calculating a job schedule), it can be seen that Digital Annealer is superior for each condition. In condition (1) having four SEs, Digital Annealer obtained a solution in which work would be completed by 17:40, but in contrast, Gurobi was unable to obtain an effective optimal solution after any amount of time. Furthermore, in condition (3) featuring the occurrence of unexpected work, Digital Annealer was able to find a solution at about 1.5 times (35 + 16) the solving time of condition (2) indicating high-speed processing that outdid even Gurobi. This last result confirmed the feasibility of rescheduling while work is in progress.

Second, focusing on the results for work completion time, a solution in which all jobs would be completed by 17:00 was obtained for the cases of five or more SEs. It should be noted here that, in actual customer-service planning, there are jobs assigned on the basis of paper forms that could not be reflected in the evaluation data. As a result, job-scheduling results (work completion time) based on the existing human-assist system could not be measured under the same conditions. For this reason, a direct comparison cannot be made with the job results of the existing human-assist system. However, these evaluation results suggest that Digital Annealer can achieve efficient scheduling.

These experimental results therefore show that Digital Annealer is an effective approach to the optimization of customer-service planning.

3.3 Future work and directions

Some aspects of this evaluation need to be improved considering actual operations. Specifically, the time at which unexpected work suddenly occurred was fixed, the work skills of each SE were not considered, and load leveling of work between SEs was not considered. Achieving practical application of Digital Annealer to the optimization of customer-service planning will require modification of a mathematical model that takes these points into account and the conducting of additional experiments.

In future work, we plan to make use of the knowledge gained from this experiment to perform practical evaluations based on large-scale datasets.