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

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

Mouna Gargouri Mnif (ENSI, University of Manouba, Manouba, Tunisia) and Sadok Bouamama (Higher Colleges of Technology DMC, Dubai, UAE)
Copyright: © 2020 |Pages: 22
DOI: 10.4018/IJAMC.2020040107

Abstract

This article introduces a new approach to solve the multimodal transportation network planning problem (MTNP). In this problem, the commodities must be transported from an international network by at least two different transport modes. The main purpose is to identify the best multimodal transportation strategy. The present contribution focuses on efficient optimization methods to solve MTNP. This includes the assignment and the scheduling problems. The authors split the MTNP into layered. Each layer is presented by an agent. These agents interact, collaborate, and communicate together to solve the problem. This article defines MTNP as a distributed constraint satisfaction multi-criteria optimization problem (DCSMOP). This latter is a description of the constraint optimization problem (COP), where variables and constraints are distributed among a set of agents. Each agent can interact with other agents to share constraints and to distribute complementary tasks. Experimental results are the proof of this work efficiently.
Article Preview
Top

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 {X1, ..., Xn}.

  • D = {Dx1, ..., Dxn}, is a set of n finite domains for the variables of X. The domain Dxi is the set of possible values of the variable xi.

  • C = {C1, C2, ..., Cm}, is a constraints set, where a constraint Ci is defined by a subset of variables: Ci = {Xi1,Xi2, ...,Xin}. 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.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 11: 4 Issues (2020): 3 Released, 1 Forthcoming
Volume 10: 4 Issues (2019)
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing