Fujitsu has been working on several practical applications of Digital Annealer. To apply this technology to our customers’ business operations, it is essential that Digital Annealer be evaluated with real-world problems to compare its performance with existing techniques and identify its technical issues clearly.
This article describes an approach to optimizing scheduling tasks in customer-service planning for distribution facilities of an electric power company as a combinatorial optimization problem. Evaluation results using real data suggest that Digital Annealer is effective in carrying out this combinatorial optimizing task.
Initiatives toward the practical use of quantum computers have been progressing rapidly in recent years throughout the world. As part of this trend, work has begun on the practical application of the annealing method that specializes in solving combinatorial optimization problems. A variety of companies have been promoting research and development in this area including Fujitsu, which has developed the FUJITSU Quantum-Inspired Computing Digital Annealer (hereafter, Digital Annealer) . Digital Annealer is new computer architecture designed for solving combinatorial optimization problems at high speed through digital circuits inspired by quantum phenomena. Quantum computers themselves are still at the research stage due to a number of issues including the difficulty of maintaining quantum states and limitations in connections and extendibility .
Digital Annealer, on the other hand, operates by digital circuitry that makes for stable operation and ease of miniaturization. It also features full-connectivity architecture that makes it easy to map complex problems thereby facilitating application to real problems.
This article describes an application of quantum annealing technology to customer-service planning for distribution facilities, which is being studied by the Advanced Research and Innovation Center of Chubu Electric Power Co., Inc., and introduces a trial of optimizing scheduling tasks using Digital Annealer.
2. Superiority of Digital Annealer in solving combinatorial optimization problems
Digital Annealer has been shown to be superior to existing computer architecture for a number of combinatorial optimization problems typified by the graph-coloring problem. Graph coloring is the problem of coloring all of the vertices of a graph such that no two vertices connected by an edge are of the same color. In this regard, a commercial solver is software equipped with an algorithm for solving combinatorial optimization problems.
The superiority of Digital Annealer in solving the graph-coloring problem is shown by Table 1. Here, regardless of the ratio of vertices connected by an edge (edge density), the commercial solver cannot produce a solution within a prescribed amount of computation time (maximum ten minutes) for a problem of 8–50 kbit. Digital Annealer, on the other hand, can produce solutions 100% of the time. In addition, Digital Annealer achieves a solving speed 30 times greater than the only commercial solver that could solve problems having an edge density of 50% or greater and a bit scale less than 8 kbit.
Table 1 Superiority of Digital Annealer in solving graph-coloring problem.
|Edge density||Bit scale
|Correct answer rate||Solving speed|
|50% or greater||8 – 50||0%||100%||―|
|Less than 8||33%||100%||30 times|
|Less than 50%||8 – 50||0%||100%||―|
|Less than 8||100%||100%||0.9 times|
Edge density ：Ratio of vertices connected by an edge
Correct answer rate ： Percentage of solutions obtained within prescribed computation time
(maximum ten minutes)
Solving speed ：Speed factor of DA against one commercial solver
bit scale ：number of vertices × number of colors for coloring
Dataset ：10 graphs used from the random/quasi-random graphs (DSJ/CUL) at the following URL.
DA ：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 ) 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.
|Work completion time||Digital Annealer solving time (s)||Gurobi Optimizer solving time (s)|
|(1) No. of SEs: 4||17:40||857||―
(no solution obtained for 17:40)
|(2) No. of SEs: 5||17:00||35||120|
|(3) No. of SEs: 5 + unexpected work||17:00||35＋16*||120＋19*|
|(4) No. of SEs: 6||17:00||5||12|
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.
This article introduced Fujitsu’s Digital Annealer computer architecture designed for high-speed solving of combinatorial optimization problems and described the results of applying it to customer-service planning for distribution facilities in an electric power company.
Combinatorial optimization problems exist in a variety of fields in our society. Going forward, Fujitsu aims to use Digital Annealer to provide solutions to social issues and to contribute to the creation of a sustainable world.
All company and product names mentioned herein are trademarks or registered trademarks of their respective owners.
References and Notes
About the Authors
Inquiries Regarding Fujitsu Technical Review
This site uses SSL encryption for security purposes.