OptaPlanner logo
  • Download
  • Learn
    • Documentation
    • Videos

    • Use cases
    • Compatibility
    • Testimonials and case studies
  • Get help
  • Blog
  • Source
  • Team
  • Services
  • Star
  • T
  • L
  • F
  • YT
Fork me on GitHub

Solve the facility location problem

Fri 9 October 2020
Avatar Jiří Locker
Jiří Locker

GitHub

OptaPlanner developer

We have created a new quickstart that extends OptaPlanner use case portfolio with the facility location problem and also demonstrates building a cloud-native application using Quarkus, the new Java Native stack.

The facility location problem

The facility location problem consist of a set of potential facility locations and a set of consumer points that need to be served by the facilities. The goal is to select a subset of the potential facility locations, to minimize the sum of distances from consumers to their assigned facilities, and to minimize the total cost of establishing the selected facilities.

You can see a sample facility location problem on the picture below. Blue circles represent the consumers and grey pins represent potential facility locations.

Facility location problem
Figure 1. An unsolved facility location problem

To understand the problem better, let’s use a concrete use case to illustrate it. Imagine you are starting a network of coffee roasteries with the goal to supply coffeehouses all over the country. Coffeehouses are the consumers and roasteries are the facilities.

A single roastery has a producing capacity that only allows it to cover a limited number of coffeehouses, so you will have to establish a number of roasteries. You have been given a list of places that you can buy and run a roastery there. These are the potential locations where you can place a facility. Each place has a different price that you need to pay before opening a roastery there. The price represents the facility setup cost.

The challenge is to select a set of places to buy, minimize the total buying cost by preferring cheaper places and, at the same time, minimizing the sum of distances between roasteries and the coffeehouses that they supply.

The new quickstart

Project structure

Quickstart project structure
Figure 2. Quickstart project structure

The server side code is in the src/main/java directory and is organized in four packages.

bootstrap

Generates a randomized (but reproducible) data set and populates the repository with it on application startup.

domain

Contains the domain model used by OptaPlanner. The @PlanningSolution, @PlanningEntity and ConstraintProvider are in the domain package.

persistence

Takes care of persisting the facility location problem data set.

rest

Contains the REST API used by the client-side code to start and stop solving and to retrieve the best solution.

The client code is in the src/main/resources/META-INF/resources/ directory. It has an index.html file that contains the basic HTML structure and loads the app.js file that calls server’s REST API and makes the web page dynamic.

Planning domain model

Class diagram
Figure 3. Planning domain diagram

Constraints

The constraints are implemented using the Constraint Streams API. You can find them in the org.acme.facilitylocation.domain.FacilityLocationConstraintProvider class. It defines the following constraints:

facilityCapacity

Hard constraint that penalizes the demand of consumers assigned to a facility if the total demand exceeds the facility’s capacity.

setupCost

Soft constraint that penalizes the setup cost of used facility locations.

distanceFromFacility

Soft constraint that penalizes the distance of a consumer from its assigned facility.

Notice that there are two soft constraints that “compete” against each other because they affect the same score level. You can control how each constraint affects the score by tweaking the constraint weights in org.acme.facilitylocation.domain.FacilityLocationConstraintConfiguration. The more weight you put on a constraint, the more it will affect the score when it is broken, and the more will OptaPlanner try to avoid it.

@ConstraintConfiguration
public class FacilityLocationConstraintConfiguration {
    ...
    @ConstraintWeight(FACILITY_SETUP_COST)
    HardSoftLongScore facilitySetupCost = HardSoftLongScore.ofSoft(2);
    @ConstraintWeight(DISTANCE_FROM_FACILITY)
    HardSoftLongScore distanceFromFacility = HardSoftLongScore.ofSoft(5);
}

Use constraint weights to find a balance between minimizing the distance from consumers to facilities, and minimizing the total setup cost. If you put too much weight on the distance constraint you might end up using unnecessarily expensive facilities. If you put too much weight on the setup cost constraint the vehicles providing service from facilities to consumers might spend too much time traveling.

Balanced solution

Balanced solution of a facility location problem
Figure 4. Balanced solution

This screenshot of the quickstart app shows a balanced solution. Notice the total setup cost spent on facilities and the total distance, and compare the values with the other solutions where you put an extreme weight on just one of the soft constraints.

Priority on minimal setup cost

Balanced solution of a facility location problem
Figure 5. Solution focused on minimal setup cost

The cheapest facility locations are selected, and they are utilized to 100% of their capacity, so we use a minimal number of facilities that can serve all the consumers.

The distance is also minimized but the weight of the distance constraint is negligible compared to the setup cost constraint so it doesn’t affect the choice of facility locations. You could achieve the same result by making setup cost a medium constraint while leaving the distance constraint on the lower, soft level.

Priority on minimal distance

Balanced solution of a facility location problem
Figure 6. Solution focused on minimal distance

Consumers are assigned to the closest facilities, paying only a little attention to the facility cost and utilization efficiency. If you look closely, you can find a few places where the distance could be reduced even more. It is just a matter of deciding the distance constraint weight.

Running the quickstart

Run the quickstart yourself:

  1. Git clone https://github.com/kiegroup/optaplanner-quickstarts.

  2. Descend into the directory quarkus-facility-location.

  3. Run mvn quarkus:dev.

  4. Open http://localhost:8080 in your browser and click on the Solve button.


Permalink
 tagged as use case facility location problem quarkus

Comments

Visit our forum to comment
AtomNews feed
Don’t want to miss a single blog post?
Follow us on
  • T
  • L
  • F
Blog archive
Latest release
  • 9.44.0.Final released
    Wed 6 September 2023
Upcoming events
    Add event / Archive
Latest blog posts
  • Scaling Up Vehicle Routing Problem with planning list variable and Nearby Selector
    Thu 27 April 2023
    Anna Dupliak
  • OptaPlanner 9 has been released
    Mon 24 April 2023
    Radovan Synek
  • OptaPlanner 9 is coming
    Tue 21 February 2023
    Lukáš Petrovický
  • Farewell - a new lead
    Tue 15 November 2022
    Geoffrey De Smet
  • Run OptaPlanner workloads on OpenShift, part II
    Wed 9 November 2022
    Radovan Synek
  • Bavet - A faster score engine for OptaPlanner
    Tue 6 September 2022
    Geoffrey De Smet
  • Run OptaPlanner workloads on OpenShift, part I.
    Thu 9 June 2022
    Radovan Synek
  • Blog archive
Latest videos
  • The Vehicle Routing Problem
    Fri 23 September 2022
    Geoffrey De Smet
  • Introduction to OptaPlanner AI constraint solver
    Thu 25 August 2022
    Anna Dupliak
  • On schedule: Artificial Intelligence plans that meet expectations
    Sat 23 July 2022
    Geoffrey De Smet
  • Host your OptaPlanner app on OpenShift (Kubernetes)
    Mon 7 February 2022
    Geoffrey De Smet
  • OptaPlanner - A fast, easy-to-use, open source AI constraint solver for software developers
    Mon 31 January 2022
  • Order picking planning with OptaPlanner
    Fri 31 December 2021
    Anna Dupliak
  • AI lesson scheduling on Quarkus with OptaPlanner
    Thu 18 November 2021
    Geoffrey De Smet
  • Video archive

OptaPlanner is open. All dependencies of this project are available under the Apache Software License 2.0 or a compatible license. OptaPlanner is trademarked.

This website was built with JBake and is open source.

Community

  • Blog
  • Get Help
  • Team
  • Governance
  • Academic research

Code

  • Build from source
  • Issue tracker
  • Release notes
  • Upgrade recipes
  • Logo and branding
CC by 3.0 | Privacy Policy
Sponsored by Red Hat