Optimisation to the rescue!
A step-by-step guide to Operations Research
Nowadays, AI and Machine Learning are all the rage. These powerful techniques have been helping businesses analyse and draw insights from data, and enable them to be more efficient and to make smarter decisions. A lesser known but equally powerful and helpful field for business is Operations Research. According to informs.org, Operations Research deals with applying advanced analytical methods to help make better decisions. It involves techniques like linear programming and heuristics and can solve problems such as network optimisation, routing, scheduling, and resource allocation issues.
To show you step-by-step how OR can be employed, in this article we will solve a simple use case in the transportation field, to see how we can approach such problems and develop our modelling capabilities. The question we want to answer is: given that a set of routes needs to be fulfilled by a set of vehicles, how do we assign vehicles to these routes using the least number of vehicles?
We are going to make some assumptions to simplify this problem. First, we can consider that every route starts and ends at the same place so that a vehicle that did route A can do route B without having to travel to another location. This is realistic since vehicles usually depart and arrive at a depot or terminal, for example. We are also going to consider that the vehicle always has fuel to complete the route. This assumption is less realistic and used here just to simplify our example, but can be built and improved upon later.
First things first: separate the information from your goals
The first thing we need to do when trying to solve an optimisation problem is to separate what we have as information from what our goal is. Since we are trying to plan routes, it is safe to assume that we will have route information, such as start time and end time. We could also have the length of the route, departure and arrival destination, etc. For the sake of our example, we are going to work only with start time and end time. We also will have information about the vehicles available. This can be model, cost of use, fuel tank capacity, fuel spent per kilometer, etc. For our example, the vehicle only has a name.
What’s next? Finding solutions
We know that our routes have start time and end time, our vehicles have a name, and we need to assign vehicles to our routes. Now we need to find solutions. First, how many solutions can there be? If we consider that a vehicle can be assigned to any route, we have at least as many solutions as the number of vehicles to the power of the number of routes. However, not all solutions are feasible. For example, if a vehicle is assigned to two routes, and these two routes overlap at any given time, then it is impossible for the same vehicle to fulfil both routes, so our search space should probably be limited by some rules. Finally, we also need to guide our search, because some solutions are better than others. For instance, if we had ten routes and used four vehicles, but could have fulfilled them using three vehicles, this is surely better, since we want the least amount of vehicles used.
To implement a solution to our problem, we are going to use a Java library called OptaPlanner. An excerpt from OptaPlanner’s documentation reads that: “Every organization faces planning problems: providing products or services with a limited set of constrained resources (employees, assets, time and money). OptaPlanner optimizes such planning to do more business with less resources. This is known as Constraint Satisfaction Programming (which is part of the Operations Research discipline)”. You can find more information here: https://www.optaplanner.org/
The first thing we need to do is to define our entities. This is easy since we already thought about them earlier. In this case, we will have a Vehicle class with a name, and a Route class with a start time and end time. Since the vehicle will be assigned to the route, we are also going to have a field for the assigned vehicle. This field will be set by OptaPlanner during solving time.
You can see that the Route class was marked with a @PlanningEntity annotation. This is the way to tell OptaPlanner that this class has a variable that will need to be decided. You call also see that we have the following code snippet:
@PlanningVariable(valueRangeProviderRefs = "vehicles")
private Vehicle designatedVehicle;This indicates that the value of the designatedVehicle variable will be picked from a list of vehicles called vehicles, that we will define later. We also need a no args constructor for each entity, to be used internally by OptaPlanner.
After defining the entities, it’s time to define the solution class
Now that we have defined our entities, we need to define our solution class. Our solution class will hold all the facts about our problem and a score.
As we can see, we have a @PlanningSolution at the top of the class, to indicate that this class represents a solution. We also have a list of vehicles, with @ProblemFactCollectionProperty to indicate that this is a collection of facts or truths, something that will not be changed, and also with a @ValueRangeProvider(id = “vehicles) to indicate that this list of vehicles can provide values that OptaPlanner can pick up during solving time. This is the list that is referenced inside the Route.java class. Besides that, we also have a list of routes, with all the routes that need vehicles assigned to, and we mark it with @PlanningEntityCollectionProperty to sinalize that it will hold a list of @PlanningEntity objects that can be changed by OptaPlanner.
The last thing our solution class will have is a score, of type HardSoftScore. In OptaPlanner, you can define two types of constraints:
- Hard constraints: these are constraints that cannot, by any means, be broken. If they are, we will have an unfeasible solution. In our case, this would be assigning a vehicle to two routes that are overlapping in time, as we discussed earlier.
- Soft constraints: these are constraints that, when broken, will still produce a feasible solution, but we would rather not, if possible, break them. In our case, we can use this to find solutions that uses less vehicles, for example.
A score of type HardSoftScore is one that supports both types of constraints.
We’re almost there: Defining the constraints
All that is left now is to define our constraints and our solver configuration. OptaPlanner allows us to define constraints in a variety of ways. Here, we will use the ConstraintStream API.
We define two constraints, routesWithSameVehicleMustNotOverlap and useTheLeastAmountOfVehicles . In routesWithSameVehicleMustNotOverlap, we pair two routes and, if they have the same assigned vehicle and overlap, we penalize our hard score in one. In useTheLeastAmountOfVehicles, we group by vehicles assigned and count all distinct ones, and penalize our soft score with the value of the count. This will make OptaPlanner prefer solutions that use less vehicles, since they will have higher (less negative) scores.
Finally, let’s create a configuration for the solver
We define our solution class, our entity class, our constraint class that calculates our score and how long we will allow our solver to run. There can be other things configured as well, such as what kind of algorithm we want to use, but we do not need more configurations for our simple example.
Congratulations, you just built your first solver! Time to test.
Here, I created a simple RoutePlanner class that creates a couple of vehicles, a couple of routes, and invoke our solver.
If we run this, we can see the solutions we get always fulfil our constraints!
Solved route plan with score -2Solution is feasible trueRoute{id=07377e0b-3816-4da7-9d1e-7684c7264b8b, startTime=08:22, endTime=09:22, designatedVehicle=Vehicle{name='Vehicle 0'}}Route{id=90495305-5c1b-479a-ba45-2eabeb77980d, startTime=08:44, endTime=09:44, designatedVehicle=Vehicle{name='Vehicle 1'}}Route{id=e86c54cc-1cf4-4c5f-8006-94b893d6645a, startTime=09:55, endTime=10:55, designatedVehicle=Vehicle{name='Vehicle 0'}}Route{id=fb450364-247a-4c76-b38e-6ba6f373530e, startTime=11:49, endTime=12:49, designatedVehicle=Vehicle{name='Vehicle 0'}}Route{id=2faf5b93-6256-4c23-92bb-83e8a046dfef, startTime=14:01, endTime=15:01, designatedVehicle=Vehicle{name='Vehicle 0'}}Route{id=245aad46-3e30-4573-9d98-54932eb3e70d, startTime=15:38, endTime=16:38, designatedVehicle=Vehicle{name='Vehicle 0'}}Route{id=a4ce43e8-c607-49c2-8092-c7094cd5c939, startTime=17:21, endTime=18:21, designatedVehicle=Vehicle{name='Vehicle 0'}}Route{id=c68109b1-00be-4112-a67f-1d92e086a2b7, startTime=17:56, endTime=18:56, designatedVehicle=Vehicle{name='Vehicle 1'}}Route{id=2a348b9f-c901-40dc-b509-617e4b895f1a, startTime=22:33, endTime=23:33, designatedVehicle=Vehicle{name='Vehicle 0'}}Route{id=944fb2a2-1a9d-4c78-b307-df9df82e6f63, startTime=22:41, endTime=23:41, designatedVehicle=Vehicle{name='Vehicle 1'}}
and
Solved route plan with score -4Solution is feasible trueRoute{id=903d67de-3a22-4187-a995-86674ff2e222, startTime=00:58, endTime=01:58, designatedVehicle=Vehicle{name='Vehicle 0'}}Route{id=8b5d785c-cf53-4c3a-86d9-96f713ecaa40, startTime=02:08, endTime=03:08, designatedVehicle=Vehicle{name='Vehicle 0'}}Route{id=bafb48bf-05eb-4398-87b7-1f4733121122, startTime=02:21, endTime=03:21, designatedVehicle=Vehicle{name='Vehicle 1'}}Route{id=a2f7641e-35fb-4398-bd38-200458a22d1f, startTime=04:21, endTime=05:21, designatedVehicle=Vehicle{name='Vehicle 0'}}Route{id=49f600a3-0977-4b6f-a953-7df289c2c87b, startTime=04:40, endTime=05:40, designatedVehicle=Vehicle{name='Vehicle 1'}}Route{id=5fc6a391-476c-4947-8ddb-2b29dfc14d34, startTime=04:52, endTime=05:52, designatedVehicle=Vehicle{name='Vehicle 2'}}Route{id=485cac3f-d4fa-4124-b109-517396c79cbb, startTime=04:59, endTime=05:59, designatedVehicle=Vehicle{name='Vehicle 3'}}Route{id=a4083f53-9b2d-4789-ad12-e964bb3726af, startTime=17:40, endTime=18:40, designatedVehicle=Vehicle{name='Vehicle 0'}}Route{id=9941c873-e213-4032-a4b8-1bff18bd94a5, startTime=22:03, endTime=23:03, designatedVehicle=Vehicle{name='Vehicle 0'}}Route{id=c0fc0d0e-5797-4185-8c7a-211dc34b6ddf, startTime=23:10, endTime=00:10, designatedVehicle=Vehicle{name='Vehicle 0'}}
We can force an unfeasible solution if we make the number of overlapping routes to be higher than the number of available vehicles. This is a case when there are no feasible solutions according to the constraints we defined, which can happen.
Solved route plan with score -5Solution is feasible falseRoute{id=5c0d4f17-6f4e-4618-9a7b-035dffed3753, startTime=08:00, endTime=09:00, designatedVehicle=Vehicle{name='Vehicle 0'}}Route{id=0452a6aa-21ac-426f-adfd-60fd8079993f, startTime=08:00, endTime=09:00, designatedVehicle=Vehicle{name='Vehicle 1'}}Route{id=d9650cf7-e6e3-463e-8e34-e31483a18014, startTime=08:00, endTime=09:00, designatedVehicle=Vehicle{name='Vehicle 2'}}Route{id=2a2cff86-7e7b-4544-9ed7-99ba224ebfe4, startTime=08:00, endTime=09:00, designatedVehicle=Vehicle{name='Vehicle 3'}}Route{id=9fb9297f-73ae-40a6-b275-6bb0281525cf, startTime=08:00, endTime=09:00, designatedVehicle=Vehicle{name='Vehicle 4'}}Route{id=8a1bfc32-2b42-4b87-a59e-16a2af7173e8, startTime=08:00, endTime=09:00, designatedVehicle=Vehicle{name='Vehicle 0'}}
I hope you enjoyed this article and that it gave you enough knowledge about another technique that you could implement to help your organisation! The code for this example can be found here: https://github.com/felipefonsecadev/route-planning.
If you would like to deep dive into this, you can start thinking about what would need to be changed if the routes could start and end at different points. Or how could we also take into account the fuel consumed by doing each route? And what if we wanted to use electric vehicles, what should we consider them? The possibilities are endless.
And if you have any comments, suggestions, or questions, feel free to reach out to us. Happy learning and coding!
Felipe Fonseca works as a Backend Engineer at tb.lx in Lisbon
