How is field service scheduling like moving in freezing water?
Creating a good field service schedule requires that you get everything right: getting the right service engineer(s) to the right place at the right time with the right parts is just the beginning, and you must do all that and more while achieving maximum efficiency, productivity, customer satisfaction, workforce satisfaction, regulatory compliance etc. No wonder it sometimes seems as challenging as an expedition to the North Pole.
Well, recent research indicates that this analogy is more than skin deep. As already mentioned in this blog, ClickSoftware is devoting substantial efforts into research and, as much as possible, into sharing results of that research. We are proud that some of our research has been accepted for academic publication. Such acceptance follows a peer-review process and signifies that the research makes some contribution towards furthering knowledge and understanding of its subject. Now, we report yet another publication, in the book “Intelligent Computational Optimization in Engineering: Techniques and Applications”.
The book’s publisher, Springer, includes it in the prestigious “Studies in Computational Intelligence” series, and describes the book as follows:
“We often come across computational optimization virtually in all branches of engineering and industry. Many engineering problems involve heuristic search and optimization, and, once discretized, may become combinatorial in nature, which gives rise to certain difficulties in terms of solution procedure. Some of these problems have enormous search spaces, are NP-hard and hence require heuristic solution techniques. Another difficulty is the lack of ability of classical solution techniques to determine appropriate optima of non-convex problems. Under these conditions, recent advances in computational optimization techniques have been shown to be advantageous and successful compared to classical approaches.
This Volume presents some of the latest developments with a focus on the design of algorithms for computational optimization and their applications in practice. Through the chapters of this book, researchers and practitioners share their experience and newest methodologies with regard to intelligent optimization and provide various case studies of the application of intelligent optimization techniques in real-world applications. This book can serve as an excellent reference for researchers and graduate students in computer science, various engineering disciplines and the industry.”
The new book’s editors selected 12 academic papers, and one of them is “Optimization Strategies for Restricted Candidate Lists in Field Service Scheduling” by Marko Žerdin, Alexander Gibrekhterman, Uzi Zahavi and Dovi Yellin, all of whom are or have been ClickSoftware employees as well as being associated with several academic institutes. A preview (abstract and first page) is publicly available.
One finding reported in this paper results from evaluation of the common “cluster first, route second” optimization approach. In this approach, the algorithm first looks for clusters of similar tasks that need to be performed. In this context, “similar” typically means “nearby”. Once it has identified the clusters, the algorithm assigns one or more service engineers to each cluster. This approach tends to reduce the total travel, since each engineer’s assignments are within a relatively small area. However, it is vulnerable to problems such as mismatch of skills (as when nearby tasks require different skills), timing issues (as when an engineer receives a cluster where one task needs to be performed early in the day while other tasks all have afternoon time slots) etc. These vulnerabilities may be addressed by several methods which we won’t go into here.
An alternative approach is to avoid the two-phase approach – clustering phase followed by routing phase. Instead, this approach uses a one-phase routing solution where each engineer may select from the full set of tasks, not just tasks within a pre-selected cluster. Not surprisingly, this approach avoids the pitfalls of the “cluster first, route second” but at some cost: It is forced to examine more possibilities, and therefore it may be slower to reach a good solution. Another way to say this is that when calculation time is limited, the one-phase method may reach low-quality results, not having had time to examine better directions, while the two-phase approach uses the limited time better by making the clustering decisions up front, thus needing to search through a much smaller set of possibilities.
Many papers have been published regarding versions of these two general approaches. One contribution of the new paper is in proposing a generic framework which is capable of switching between the two, according to the specific characteristics of the scheduling problem being solved. It turns out that a key characteristic is the number of service engineers who are acceptable candidates for each task. “Acceptable candidates” are those whose profile is a good match with the task’s requirements – their location is close enough to the task’s location; their skills are compatible with the task’s requirements etc. When this number is high, the number of options that need to be examined for each task is so high that “cluster-first” can become the preferred approach, especially when considering that its vulnerabilities are less problematic in such a scenario.
This finding may seem intuitive: When each task has many possible engineers, and many engineers has many possible tasks, it’s pretty fast and pretty safe to cluster nearby tasks and be confident that an engineer can be found to efficiently handle each cluster. The less-intuitive finding comes as the authors experimented with scheduling problems by gradually changing the number of acceptable candidates. At one extreme, two phases are better. At the other extreme, a single phase is the best performer. Now, what happens in the transition area? Is there a large range where both options perform equally well?
It turns out that the answer is no: As the number of acceptable candidate’s changes, we reach a point of rather abrupt transition: On one side of that point, a single phase performs much better than two. Change the average number of acceptable candidates by a tiny amount, and suddenly the two-phase approach dominates. This is why I compared this problem to an expedition to the north pole: As the ship approaches colder waters, water temperature may drop to 10 degrees above freezing, then 5 degrees, then 0.5 degree, but the ship moves on as it did before: water is water, even when it’s cold. But once temperature drops just a tiny bit more, to 0.5 degree below freezing, the water isn’t water anymore: it is solid ice, and the ship can’t proceed. The expedition must then switch to some other ways of moving further towards their goal.
This research shows us that to be successful under varying conditions, optimization needs two characteristics: First, it needs to support multiple solution strategies, since each strategy dominates in its own type of scheduling problem. Second, it needs to be able to switch between these strategies, since each day may be different, and even on the same day each geographic region may require a different optimization strategy. The good news: the abrupt transition means that each strategy works well across its full domain until the transition point is reached: it doesn’t need to be fine-tuned according to the problem’s precise characteristics. In the analogy to the polar expedition, imagine how tough it would have been if each drop of one degree in water temperature had meant that a different vehicle is required. Instead, each vehicle (say, ship and sled) works well across its entire temperature domain. This bodes well for a self-adaptive generic approach to optimization that can switch between distinct solution strategies.
It should be clear that this research looked at just one distinction between optimization strategies, and the experiments were for one family of scheduling problems. Therefore the findings should be regarded as indicative, not prescriptive. Our team continues its research with the goal of improving our understanding and our algorithms.