Multi-Layer Distributed Constraint Satisfaction for Multi-criteria Optimization Problem: Multimodal Transportation Network Planning Problem

Introduction

The constraint programming technique is combines techniques from artificial intelligence and operations research. This technique proves their efficiency to solve combinatorial optimization problems. The problems can include various areas as scheduling, timetable, planning, and assignment problems, etc. These problems can be composed of two or more sub-problems. The constraint satisfaction problem (CSP) formalism makes it possible to represent many problems in a simple and effective way.

A CSP is defined by a set of variables X, a set of domains D of definition framing values that includes these variables and a set of constraints C that shapes the values that will make the variables belonging to X. Formally, the CSP is defined by a triplet P = (X, D, C) where:

• •

  X is a finite set of n variables {X₁, ..., X_n}.

• •

  D = {D_x1, ..., D_xn}, is a set of n finite domains for the variables of X. The domain D_xi is the set of possible values of the variable x_i.

• •

  C = {C₁, C₂, ..., C_m}, is a constraints set, where a constraint C_i is defined by a subset of variables: C_i = {X_i1,X_{i2, ...,}X_in}. These constraints can be expressed in extension by a set of triples which respect the associated constraints, or by predicate or mathematical functions.

In order to solve these problems is interesting to apply the knowledge algorithmic to improve the performance of decision systems. The resolution of a CSP defined by the assigned values to the variables of the problem. The CSP solution is an instantiation that should satisfy all the set of constraints. The constraints can be expressed in different forms as mathematical formulation. These are relationships between variables that define the structure of the problem to be solved.

In a recent paper presented by (Li, Negenborn, & Lodewijks, 2016), authors treat a vessel rotation planning problem (VRPP) of the container as a distributed CSP. The resolution of this problem must plan and assign the rotation of the container using vessels, trains, or trucks. The main goal is to select the rotation plan depending on frequencies of terminals visits, and arrival and departure time of vessels to the terminals in the port area. The case study is characterized by a static data. They have formulated the VRPP as a layered distributed constraint optimization problem (DCOP) structure into two layers: an assignment layer and a scheduling layer. The upper layer defined as the assignment problem to select the sequence of different terminals visited by the vessels. The obtained solutions at the higher layer defined as the lower layer to explain the scheduling problem that plans the arrival and departure times and the waiting time at each terminal. There exists one DCOP in the upper layer that relates to each vessel. Moreover, there are multiple sub-COPs in the lower layer, each one is connected to a single vessel. After finding an optimal solution, the upper layer of the DCOP problem, and the lower layer DCOP solve each problem separately. The multi-layer approach significantly considered to improve the applicability of this approach.