Using OptaWeb Vehicle Routing

The main purpose of many types of businesses is to transport various types of cargo. The goal of these businesses is to deliver a piece of cargo from the loading point to a destination and use its vehicle fleet in the most efficient way. This type of optimization problem is referred to as the vehicle routing problem (VRP) and has many variations.

OptaPlanner can solve many of these vehicle routing variations and provides solution examples. OptaPlanner enables developers to focus on modeling business rules and requirements instead of learning constraint programming theory. OptaWeb Vehicle Routing expands OptaPlanner’s vehicle routing capabilities by providing a reference implementation that answers questions such as these:

Java SE 11 or higher must be installed on your system before you can use OptaWeb Vehicle Routing.

Download the OptaWeb Vehicle Routing distribution archive, available from the OptaPlanner website, to quickly evaluate OptaWeb Vehicle Routing without having to set up build tools.

After you download OptaWeb Vehicle Routing and extract the distribution archive, use the runLocally.sh script to run it.

Enter the following command:

The script will download an OSM file that is needed to work with the sample data set that is included with the application. The script also has an interactive mode you can use to download additional regions. See Run locally using the script to learn more about the script.

In quickstart mode, the script downloads the region that is required to work with the built-in data set. This is the easiest way to get started. To use the quickstart mode, run the script with no arguments.

The application starts after the OSM file is downloaded. Open http://localhost:8080 in a web browser to work with OptaWeb Vehicle Routing.

Using the interactive mode, you can see the list of downloaded OSM files and country codes assigned to each region. You can use the interactive mode to download additional OSM files from Geofabrik without visiting the website and choosing a destination for the download.

Use the non-interactive mode to specify an existing region and start OptaWeb Vehicle Routing with a single command. This is useful for switching between regions quickly or when doing a demo.

Run ./runLocally.sh <REGION>.

The routing engine requires geographical data to calculate the time it takes vehicles to travel between locations. You must download and store OSM (OpenStreetMap) data files on the local file system before you run OptaWeb Vehicle Routing.

OptaWeb Vehicle Routing reads and writes several types of data on the file system. It reads OSM (OpenStreetMap) files from the openstreetmap directory, writes a road network graph to the graphhopper directory, and persists user data in a directory called db. Create a new directory dedicated to storing all of these data to make it easier to upgrade to a newer version of OptaWeb Vehicle Routing in the future and continue working with the data you created previously.

The rest of the directory structure will be created by the OptaWeb Vehicle Routing application when it runs for the first time. After that, your directory structure will look similar to the following example:

Enter the following command:

Use Red Hat CodeReady Containers to easily set up a single-node OpenShift 4 cluster on your local computer.

You have successfully built the project with Maven.

To create an optimal route, use the Demo tab of the user interface.

Every time you add or remove a location or change the number of vehicles, the application creates and displays a new optimal route. If the solution uses several vehicles, the application shows the route for every vehicle in a different color.

You can use other tabs of the user interface to view and set additional details.

There is a built-in demo data set consisting of a several large Belgian cities. If you want to have more demos offered by the Load demo dropdown, you can prepare your own data sets. To do that, follow these steps:

After you restart the back end, files in the data set directory will be made available in the Load demo dropdown.

If the application behaves unexpectedly, review the back end terminal output log.

To resolve issues, remove the back end database:

The project is a multi-module Maven project.

At the bottom of the module tree there are the back end and front end modules, which contain the application source code.

The standalone module is an assembly module that combines the back end and front end into a single executable JAR file.

The distribution module represents the final assembly step. It takes the standalone application and the documentation and wraps them in an archive that is easy to distribute.

The back end and front end are separate projects that can be built and deployed separately. In fact, they are written in completely different languages and built with different tools. Both projects have tools that provide a modern developer experience with fast turn-around between code changes and the running application.

In the next sections you will learn how to run both back end and front end projects in development mode.

The back end module contains a server-side application that uses OptaPlanner to optimize vehicle routes. Optimization is a CPU-intensive computation that must avoid any I/O operations in order to perform to its full potential. Because one of the chief objectives is to minimize the travel cost, either time or distance, we need to keep the travel cost information in RAM memory. While solving, OptaPlanner needs to know the travel cost between every pair of locations entered by the user. This information is stored in a structure called the distance matrix.

When a new location is entered, we calculate the travel cost between the new location and every other location that has been entered so far, and store the travel cost in the distance matrix. The travel cost calculation is performed by a routing engine called GraphHopper.

Finally, the back end module implements additional supporting functionality, such as:

In the next sections you will learn how to configure and run the back end in development mode. To learn more about the back end code architecture, see Back end architecture.

The front end project was bootstrapped with Create React App. Create React App provides a number of scripts and dependencies that help with development and with building the application for production.

Run ./mvnw install or mvn install.

The OptaWeb Vehicle Routing back end has a strictly enforced code style. Code formatting is performed by the Eclipse code formatter, using configuration files from the OptaPlanner project.

By default, when you execute the ./mvnw install command, the code is formatted automatically. This is important because when you submit a pull request, the continuous integration (CI) build fails if running the formatter results in any code changes. Therefore, it is recommended that you always run a full Maven build before submitting a pull request.

You can use Eclipse IDE or IntelliJ IDEA to format the source code without having to invoke the Maven build. This allows you to make small changes and commit often while making sure that the source code is formatted properly and the Maven build is successful after each commit.

You must configure your IDE to use the Eclipse formatter plugin and select the formatter configuration used by the Maven plugin that formats the source code automatically during the Maven build. The formatter configuration files are stored in the build/optaplanner-ide-config/src/main/resources directory under the root of the OptaPlanner repository.

The back end code is organized in three layers outlined above.

The service package contains the application layer that implements use cases. The plugin package contains the infrastructure layer.

Code in each layer is further organized by function. This means that each service or plugin has its own package.

Compile-time dependencies are only allowed to point from outer layers towards the center. Following this rule helps to keep the domain model independent of underlying frameworks and other implementation details and model the behavior of business entities more precisely. With presentation and persistence being pushed out to the periphery, it is easier to test the behavior of business entities and use cases.

The domain has no dependencies.

Services only depend on the domain. If a service needs to send a result (for example to the database or to the client), it uses an output boundary interface. Its implementation is injected by the CDI container.

Plugins depend on services in two ways. Firstly, they invoke services based on events such as a user input or a route update coming from the optimization engine. Services are injected into plugins which moves the burden of their construction and dependency resolution to the IoC container. Secondly, plugins implement service output boundary interfaces to handle use case results, for example persisting changes to the database or sending a response to the web UI.

The domain package contains business objects that model the domain of this project, for example Location, Vehicle, Route. These objects are strictly business-oriented and must not be influenced by any tools and frameworks, for example object-relational mapping tools and web service frameworks.

The service package contains classes that implement use cases. A use case describes something that you want to do, for example adding new location, changing vehicle capacity, or finding coordinates for an address. The business rules that govern use cases are expressed using the domain objects.

Services often need to interact with plugins in the outer layer, such as persistence, web, and optimization. To satisfy the dependency rules between layers, the interaction between services and plugins is expressed in terms of interfaces that define the dependencies of a service. A plugin can satisfy a dependency of a service by providing a bean that implements the service’s boundary interface. The CDI container creates an instance of the plugin bean and injects it to the service at runtime. This is an example of the inversion of control principle.

The plugin package contains infrastructure functions such as optimization, persistence, routing, and network.