LocalSolver sponsors OR 2023

LocalSolver Optimizer is a global optimization solver that combines exact and heuristic methods to find near-optimal solutions in minutes. LocalSolver Studio is a web application released in 2023 and built on top of LocalSolver Optimizer. It includes a code editor to write and debug optimization models and a graphical interface to visualize solutions. Model generators for routing and scheduling have been integrated to build a first model in just a few clicks. The generated model can be tuned to include specific business constraints and objectives using our modeling language. Dedicated widgets allow users to display tours on a map or activities on a Gantt chart. The optimization is done remotely on dedicated servers with the latest version of LocalSolver Optimizer. In this talk, we will give a demo of LocalSolver Studio and show how it can be used in industry or for teaching.

Read Julien’s presentation here.

A LocalSolver customer in charge of maintaining public assets needs to go through the entire road network within a defined area, minimizing the total travel time and considering various constraints such as traffic direction and speed limits, and ensuring that each road segment is processed only once. The problem is formulated as a Capacitated Arc Routing Problem (CARP), a well-known NP-hard problem, which offers a suitable modeling approach to address the unique challenges of this specific case using LocalSolver.

To model the given scenario, we represent the area to be surveyed as a directed graph, where arcs correspond to road segments (accounting for traffic direction), and vertices represent intersections between roads. In this specific project, there is no capacity constraint to consider, allowing us to focus on other problem aspects. The CARP is applied to determine an optimal route tour that satisfies all requirements while minimizing travel time and operational costs.

The talk will present a solution to this problem based on local search, one of LocalSolver competitive edge technologies. Modelling choices as well as other specific business rules and results on large size instances will also be shown.

Read Bienvenu’s presentation here.

A company specializing in gas production and transportation has to perform deliveries to its clients so that they never face any runout in their tanks. As the implemented solution has to manage both aspects of routing and inventory management, the corresponding problem falls in a particular version of the IRP problem. The size of the company instances (dozens of resources, hundreds of customers, and hourly forecasts on planning horizon up to fourteen days) as well as the frequency of use (up to several times per day), force the solution to be fast and scalable too.

Regarding resources, every driver can drive different tractors, which can be hitched to several trailers. Every “vehicle” is then a triplet of resources (driver, tractor, trailer). Each of these resources can have specific properties such as availability, time windows, speed, and capacity. The triplets are not pre-determined: the optimization has to decide which resources are put together.

The associated routing problem has a “many to many” structure, meaning several sources (to load trailers) and several customers (to perform deliveries) are taken into account. As all these places are not necessarily always open, they also have their own availability time windows.

Eventually, the underlying inventory problem is assumed to be deterministic. The telemetry measures sent from customers allow them to forecast precisely enough their tank levels. Deliveries must be made before these tanks run out of gas.

The talk will present a solution to this problem based on local search, one of LocalSolver’s competitive edge technologies. Modeling choices, as well as other specific business rules and results on large-size instances, will also be shown.

This talk will show how the algorithms implemented in LocalSolver, taking advantage of its set-based modeling, make it a solver of choice for solving the Assembly Line Balancing Problem, as well as other problems with similar structures.

We will present a new local move integrated into LocalSolver’s local search component, applicable to any packing problem: it is automatically activated when the model involves capacity constraints on set variables. This move is based on ejection chains: it consists in a series of element transfers from one set variable to another. It helps LocalSolver get out of local minima, in which the values of many set variables need to be modified for the solution to be improved, by rearranging the elements contained inside k set variables so as to empty one of them. It is particularly useful on the most combinatorial and most challenging packing instances.

We will show how the integration of this local move enables LocalSolver to obtain very good performance on the Assembly Line Balancing Problem. We will give numerical results on the “very large” benchmark from [1], comprising more than five hundred instances of one thousand tasks. We will show that LocalSolver not only clearly outperforms CP Optimizer and MIP solvers, but also improves the literature’s best known solution on 59% of these instances. We will also show that the integration of this new move into LocalSolver’s local search improves its performance on other problems, such as the Bin Packing Problem.

Read Léa’s presentation here.

Reference
[1] A. Otto, C. Otto, and A. Scholl. Systematic data generation and test design for solution algorithms on the example of SALBPGen for assembly line balancing. European Journal of Operational Research, 228(1) :33–45, 2013.

Optimizing the planning of the collection, storage, and delivery of agricultural goods is a crucial issue for actors in the agri-food supply chain. In order to limit losses and meet supply demands on time, a business proposes a platform to efficiently plan the transportation of grain between different locations and over multiple time periods.

The objective of the problem is to determine how much of each grain should be transported between each location and by which mode of transportation. It is also necessary to manage the storage of grain in the silos: the assignment of the type of grain to each cell in the silo must be decided. These decisions must be made for each period of the problem, a period corresponding to one or several months. The search for solutions to the problem is guided by 3 main criteria: maximizing the collection of produced grains, satisfying the customers’ demands, and minimizing the transportation costs.

The difficulty lies in the continuity between the different periods: indeed, as some types of grain can only be collected at the beginning of the horizon and can only be delivered at the end, it is necessary to be able to ensure the storage of these grains in the meantime. It is, therefore necessary to deal with the problem as a whole and not period by period in order to anticipate demand and manage stocks.

This initial problem being too complex to be solved in a direct way, the resolution is carried out by a heuristic approach consisting in splitting this problem into several successive sub-problems, including a flow problem and an allocation problem. Solved with LocalSolver, a mathematical optimization solver based on different operational research techniques mixing heuristics and exact methods, this approach allows to obtain high quality solutions.

Read Emeline’s presentation here.