Using a constraint solver to automate planning and scheduling

There is no known solution for this problem in which possible combinations do not grow exponentially with each additional city, yet the scenario is familiar to many different businesses. Companies that provide courier services, field repairs, or in-home medical care deal with these types of routing scenarios daily. Individuals in charge of planning understand the complexity of this type of problem as the number of stops increases. 

THE ADDED COMPLEXITY OF CONSTRAINT SOLVING 

In the traveling salesman example, you typically factor for one resource—a salesman—and several destination cities. These constraints are simplistic, and yet they result in highly complex data sets. Once you add more factors, like adding people to the route scheduling, assessing the skills of each employee, dealing with a truck breaking down, or a customer canceling, you complicate the situation further. 

With each added constraint, your planning complexity skyrockets, as does the cost of your analysis—if you are gathering results by hand. To find the most efficient solution in a constraint-solving scenario, you must quickly cycle through scenarios until you achieve your desired results. 

TRANSCEND HUMAN CAPABILITIES

With any increase in your business resources, many factors result in massive permutations that are beyond human calculations. Even with moderately large data sets, your constraint planning exercises can stress conventional computer-based algorithms. Constraint solvers are different. They use advanced heuristics and metaheuristics, including tabu search, simulated annealing, and late acceptance to accelerate how quickly you get results. 

The algorithms available through a constraint solver are customizable and helps software developers and business owners solve problems in minutes or hours instead of weeks or months with conventional algorithms. 

FIGURING FAIR AND EQUITABLE SOLUTIONS 

If you have a handful of employees, determining a fair schedule is straightforward. However, large companies such as fulfillment warehouses or call centers employ thousands of people with varying skill sets. Determining who should work when, where, and for how long presents a significant challenge. A constraint solver provides powerful problem-solving tools that consider time, resources, and business rules to determine best-case scenarios for achieving business goals. 

HITTING A MOVING TARGET 

Very rarely are business planning problems static. Resource counts change—sometimes on the fly—and your carefully considered schedule, route, or plan suddenly has gaps that need to be filled. 

Constraint solvers allow you to find an optimal solution to your challenges more quickly, even when the conditions change. With the unique ability to manage and modify conditions before, during, and after processing, you will be able to rapidly adjust and remain agile with negligible changes in system performance. Since these solutions are typically embedded and customized, adapting to new constraints is as easy as changing your input data.
 

CONSTRAINT SOLVING FOR EMPLOYEE SHIFT ROSTERS 

Employees are happier when scheduling is fair and equitable. However, as your team grows, ensuring a balanced schedule with traditional planning methods can be increasingly difficult. Additionally, you must consider constraints such as skill requirements (e.g., languages spoken, specializations), the number of hours employees can work in a day, and the total number of employees needed for each shift. You will also need to keep in mind requested days off and desired time slots or locations. 

Traditionally, shift rostering is delegated to management teams who are responsible for sets of people. Each of those managers then spends time and energy planning shifts and working up schedules by hand or using traditional algorithm-based tools. If employees call in sick or leave the job, a manager must go back and revisit that schedule to ensure proper coverage. This shift rostering method takes away from each manager’s potential to perform more important tasks. 

BUSINESSES THAT BENEFIT FROM AUTOMATED SHIFT ROSTERING

• Hospitals
• Assembly lines
• Call centers
• Police and fire departments
• Distribution and fulfillment centers

TABLE 1. OPTAPLANNER BENCHMARK: NURSE ROSTERING

A nurse rostering benchmark, run on the OptaPlanner constraint solver, demonstrates how a planning engine can optimize a shift roster for a sizeable data set in minutes. 

During this benchmark, employees were defined as proficient in zero to many skills, and only those employees who were eligible for shifts were considered in the results. Shifts were defined as having a starting date and time, ending date and time, and an assigned unit. Each unit could require a certain skill set for an employee to qualify for assignment. 

RAPID OPTIMIZATION OF VEHICLE ROUTING 

Vehicle routing applies to the traditional traveling salesman problem. From local delivery services to global freight carriers, the ability to optimize vehicle routing results in lower fuel costs, reduced environmental impact, increased customer satisfaction, and happier drivers and operators. Because these businesses are highly complex, planning vehicle routing can come with a long list of constraints, including time windows, employee skills, job locations, and employee location. 

A constraint solver can produce an optimized vehicle routing plan in seconds or minutes. With flexible, adaptable designs, you can easily change your input constraints or goals to test scenarios and find the best routes for your business. Whether you need to deliver during time windows, optimize fuel use, or schedule as many deliveries as possible each day, your constraint solver can help you ensure driver success and customer satisfaction.

BUSINESSES THAT BENEFIT FROM OPTIMIZED VEHICLE ROUTING 

• Shipping companies
• Courier services 
• Package and mail delivery 
• Car sharing and taxi services
• Public transportation 

TABLE 2. OPTAPLANNER SIMULATION: VEHICLE ROUTING WITH TIME WINDOWS

For the vehicle routing examples, vehicles are required to deliver packages to customers within time windows. Customers are expecting their packages during their assigned time window with no leniency for late or early arrivals.

RED HAT BUSINESS OPTIMIZER: CONSTRAINT SOLVING FOR THE ENTERPRISE 

Using Red Hat^® Business Optimizer is like having a team of mathematicians, data scientists, and analytics experts on your team. Yet, all you need are the Java™ developers you already have on staff. Using this lightweight, embeddable, open source planning engine, your Java programmers can solve optimization problems easily and efficiently using a variety of out-of-the-box-provided algorithms, and your team can experiment and choose the right algorithm to achieve optimal results. 

SUPPORTED AND ENTERPRISE-READY

Red Hat Business Optimizer is a fully supported, enterprise-ready business constraint solver. Using the open source OptaPlanner project, Business Optimizer is a validated solution, delivering the best of OptaPlanner’s functionality along with Red Hat support.

SCALABLE AND COMPATIBLE 

Because Business Optimizer is written in pure Java, it runs on Linux®, Mac, and Windows platform Java virtual machine (JVM). Additionally, the engine is compatible with enterprise Java applications like Red Hat JBoss^® Enterprise Application Platform (EAP) and with JVM languages such as Kotlin and Scala. You can embed Business Optimizer into your existing codebase to enhance your in-house planning solutions, or you can start from scratch. You can also run your solution on-premise or on any cloud with Red Hat OpenShift^®. Wherever you use Business Optimizer, you can scale your planning tools to meet your growing needs. 

OPTIMIZED AND FLEXIBLE 

To solve your unique business problems, you need a tool that can adapt to your exact data sets, criteria, and constraints. Red Hat Business Optimizer provides you with the foundation to:

LEARN MORE 

Request a discovery session with Red Hat, and we will show you how to accelerate business decision making with Red Hat Business Optimizer. 

RESOURCES 

For more information, and to run OptaPlanner benchmarks yourself, visit https://www.optaplanner.org/code/benchmarks.html