# Minimizing Cost Travel in Multimodal Transport Using Advanced Relation Transitive Closure

Authors: Rachid Oucheikh; Ismail Berrada; Lahcen Omari
Journal: Advances in Operations Research
 (2018)

---

## Abstract

The optimization computation is an essential transversal branch of operations research which is primordial in many technical fields: transport, finance, networks, energy, learning, etc. In fact, it aims to minimize the resource consumption and maximize the generated profits. This work provides a new method for cost optimization which can be applied either on path optimization for graphs or on binary constraint reduction for Constraint Satisfaction Problem (CSP). It is about the computing of the “transitive closure of a given binary relation with respect to a property.” Thus, this paper introduces the mathematical background for the transitive closure of binary relations. Then, it gives the algorithms for computing the closure of a binary relation according to another one. The elaborated algorithms are shown to be polynomial. Since this technique is of great interest, we show its applications in some important industrial fields.


---

## Body

## 1. Introduction

The optimization computation is an essential branch of operations research which aims to minimize the resource consumption and maximize the generated profits. It is primordial in many technical and industrial fields: system design, supply chain management, transport, energy, finance, networks, etc. This type of computation has enjoyed a great growth in the last century, and it presents the goal of many works in operations research and graph theory.This paper introduces a new method for cost optimization, applied either on path optimization for graphs or on binary constraint reduction for Constraint Satisfaction Problem (CSP). It is a problem-solving technique that is applied to improve decision-making and efficiency. This method aims to fill the gap in the binary constraints optimization, in particular where these constraints are of different structures. In addition, it has a low algorithmic complexity that is shown to be polynomial. Moreover, it can be widely used in many operations research application fields, namely, management, decision-making, network optimization, scheduling, etc.Before citing the related works and making the comparison with what is done in the literature, we start by describing the problem. First, we begin by defining the binary constraints on which the elaborated method is based. A binary constraint is a relation between two variables. Concretely, a relation can be, for example, an association of employees’ names and their salaries, or a pairing of calendar years with automobile production figures. In the case when we have relationships between just two elements, the relation is called a binary relation and it is represented by set of ordered pairs (x, y) where x and y are objects of sets A and B, respectively, and x bears a relation to y.Many binary relations display identifiable properties. For example, the relation “less than or equal to” has the property that if an object bears a relation to a second which further bears the same relation to a third then the first bears this relation to the third ( x < y and y < z and then x < z). Such relations are said to be transitive.Transitivity is an important property used in several domains. However, it is not satisfied by many relations. In fact, the transitive closure computation has been identified as an important and frequent problem in many computer science applications, we mention among others path optimization, redundant synchronization removal [1], reachability analysis of transition graphs in communication networks [2], construction of parsing automata in compilers [3], evaluation of recursive database queries, and iteration space slicing and code generation [4, 5].In this paper, we investigate a new extension of the transitive closure concept: “the transitive closure according to a given property.” That is, for a given property P, and a relation R, we are interested in computing the smallest transitive relation containing R such that the property P holds. To begin, we enumerate the main contributions of this paper:(i)
The introduction of the concept of transitive closure according to a given property.(ii)
The proposition of a new algorithm to compute this transitive closure.(iii)
The profit of our new concept in many research operations applications, especially those requiring the constraints reduction or path optimization.Related Works.Many efficient algorithms of transitive closure have been developed in the field of algorithmic graph theory: we mention Roy Warshal algorithm [6] and Warren algorithms [7] based on a matrix representation of the graph. We cite also the Schmitz algorithm [8] which takes benefit of Tarjan’s algorithm. Other interesting works in the same line are those of Ioannadis [9]. However, all these previous works consider only the computation of the transitive closure. To the best of our knowledge, the concept of transitive closure according to a given property has not been introduced before and there is no elaborated technique to solve this problem.In the case of many relations, Wlodzimierz, Verdoolaege, Cohen, and Beletska [10, 11] worked on transitive closure of the union of affine relations on integer tuples. The general form of a parameterized affine integer tuple relation is {x→y∣⋁i=1n∃αi,Aix,y,αi≥bi} where x, y, and αi are integer tuples, Ai is an integer matrix, and bi is a tuple of integers and symbolic value. They presented iterative algorithms to calculate the exact, the underapproximation, and the overapproximation transitive closure of such relations, within Presburger arithmetics. However, they consider only the union of integer tuple relations that are commutative and have the same dimensions.To show the insufficiency of their study, let us discuss an example of a closure case that is not included in their work. For this purpose, we begin by giving some definitions.Definition 1.
LetN be the set of nonnegative integers and k be a positive integer. A set S⊆Nk is alinear set if there exist vectors v0,v1,…,vt in Nk such that S={v∣v=v0+a1v1+⋯+atvt,fora1,a2,…,atinN}. V0 is constant vector and v0,v1,…,vt are called generators of the linear set S (called also periods).
A subset ofNk for k∈N issemilinear if it is a finite union of linear sets.Example. In N2 the set A={(x,y)∣x≥4} is a linear set, namely, the constant vector is (4,0), and the generators are (1,0) and (0,1).LetX=(x1,…,xk) be a vector of distinct variables and V(X)=(v(x1),…,v(xk)) be the vector which associates with each variable in the vector X its valuation.Definition 2.
A setS⊆Nk is said to be denoted by Φ(X) where Φ is Presburger formula with variables in x1,…,xk} if S={V(X)∣V⊨Φ}.S is called a Presburger set.Theorem 3.
Guinsburg and Spanier proved in [12] that the family of Presbureger sets of Nk is identical with the family of semilinear sets of Nk.From this theorem, we can deduce that the works above are insufficient since the nonsemilinear sets are not studied. To explain this, we give a concrete example where a set B is defined asB={ii∣i∈N}. This latter is not a Presburger set since it is not semilinear.Within Presburger logic, we consider a relation R overN defined as {x→y∣x=y+3∨x=y+4} where x,y∈N. Let A be the partition of singletons on R∗ (R∗ designate the transitive closure of R). We define the following mapping: for each x in B we associate (x1/x,x1/x+1) in N2∩A2. Take the following property on elements of B: Px=∃y,x=2y.Assuming this data, up to now, there is no elaborated method which computes the transitive closure of R according to a property P in this case.Other close techniques are hypergraph theory and linear programming. The hypergraphs do not express more than one relation. In fact, they present a simple generalization of the graphs in which an edge can join any number of vertices. This means that each hypergraph includes just one relation even if it is not binary.Moreover, linear programming (LP) aims to optimize a linear objective function subject to linear inequality constraints. In our case there is no objective function to optimize. In addition, computation complexity using LP is higher than the complexity of our method.The rest of this paper is organized as follows: In Section2, we present the basic definitions, concepts, and notations used in this paper. In Section 3, we show the properties of our closure and we elaborate the computation algorithm. In Section 4, we apply our method in multimodal transport by adapting the algorithm to minimize the cost travel. Finally, we conclude and draw perspectives in Section 5.


## 2. Background and Basic Definitions

In the following,R denotes the set of real numbers and ∧ (reps. ∨ ) logical conjunction (resp. disjunction).Definition 4.
Let A and B be two sets. A binary relation R from A (called domain of R) to B (called codomain of R) is defined by a subset G ofA∗B. If (x,y)∈G, we say that x is related to y and we write x R y.
When A = B, we say that R is a binary relation over A or defined on A. Some important properties of a binary relation R over A are as follows:(i)
Reflexivity:∀x∈A,xRx.(ii)
Symmetry:∀x,y∈A2,xRy⇒(yRx).(iii)
Transitivity:∀x,y,z∈A3,xRy∧yRx⇒(xRz).
A relation that is reflexive, symmetric, and transitive is called an equivalence relation. When R is an equivalence relation over A, the equivalence class of an elementx∈A is the subset of all elements in A that bear this relation to x. Note that the equivalence classes are disjoint. The quotient set of A by R is the set of the equivalence classes. Cr will denote the cardinal of this quotient set.Definition 5.
The transitive closure of a relation R on a set A is the smallest transitive relation R* over A containing R.
Directly from this definition, we can deduce the following properties:(i)
If R is transitive, thenR=R∗(ii)
Any transitive relationR′ defined on A, containing R, contains also R∗
In this paper, we will investigate the problem of computing the smallest transitive relation containing R such that a given property P holds. This problem may be viewed as an extension of the usual transitive closure problem: we are not looking only for the smallest transitive relation but a relation which satisfies also a given property. Formally, one has the following.Definition 6.
Let A and B be two sets, R be a relation over A,ϕ be a mapping from B to A2, and P be a logical formula on elements of B. The transitive closure of R with respect to P is the smallest transitive relation defined on A, noted Rp, containing R, such that, ∀x∈B,Px⇒ϕx∈Rp.
P expresses desired properties using a given logic.ϕ maps each element of B to an element of A2. In this case, Rp is the smallest transitive relation containing R such that if an element of B satisfies the property P then its image must be in Rp.
ComputingRpin general case can be hard and depends on the decidability of the used logic. So, in this paper we will consider only the following case:(i)
B=A2 and ϕx=x∀x∈B.(ii)
Px=∃x′∈Rp∧x′Sx, where S is a given relation over B.
In this case, Definition6 becomes as follows.Definition 7.
Let R (resp. S) be a relation over a set A (resp.A2). The transitive closure of R according to S is the smallest transitive relation over A, noted Rs, and containing R such that, ∀x,y,z,w∈A4,x,ySz,w∧xRsy⇒zRsw.Example 8.
To illustrate this concept, let us consider the following system of inequalities:(1)x1-x2≤12x3-x4≤8x3-x5≤4x5-x4≤2maxx1-x2≤maxx3-x4The system has two types of inequalities:(i)
Variable inequalities of the formxi-xj≤cij with (xi,xj,cij)∈R3.(ii)
Inequalities of maximal bound difference of the formmax(xk-xl)≤max(xp-xq with (xk,xl,xp,xq)∈R4.
The set of solutions of this system, when it is not empty, is included in the intersection of the half-planes defined by individual inequalities of type 1. It is therefore a convex set. Now, we have to check if this convex set is not empty and in this case compute its canonical form (the representation in which all inequalities are maximally tight). This problem may be expressed as transitive closure of a relation R according to a relation S as follows:(i)
R={xi,xj∣xi-xj≤cij}(ii)
S=xk,xl,xp,xq∣maxxk-xl≤maxxp-xq.
Firstly, we close transitively R. This gives usx3-x4≤6 instead of 8. As we have this implication x3,x4Sx1,x2∧x3Rx4⇒x1Rx2 then x1-x2≤6. Therefore, computing Rs will give us the canonical form of the previous system.
Since the closure is done in an iterative way, we will introduce the following additional notations: for a relation R (reps. S) over A (resp. A2).(i)
Completeness:Rs=R∪{z,w∣∃(x,y),x,ySz,w∧xRy}(ii)
Iteration: fori∈N,(2)Rs0=Rifi=0Rsi=Rsi-1∗sotherwiseSince R⊂R∗, it is easy to show that for all i∈N we have Rsi⊂Rsi+1 and Rs=⋃i=0∞Rsi.Example 9.
This example shows the utility of this closure in a state machine with variables.
Let G be a graph andA=(v1,…,vn) be the set of its edges. We assume that B=N2, the property on elements of B is Px,y:y+x=0mod3, and we suppose that the mapping ϕ(x,y) associates for each (x,y) in B an element (vx,vy). We affirm that for each two elements in B that satisfy property P, their images by the mapping ϕ are linked by the relation R.Figure1 shows the closure steps, in the first stage we have the graph presenting the relation R, and then, in the second step, we close transitively this graph. In the third step, we close the obtained graph according to the desired property. These last two steps are repeated iteratively until the graph is stationary.Figure 1
Illustration of the closure steps.
(a)
Graph with just  the relation R (b)
The transitive closure of R (c)
The transitive closure of R according to a property


## 3. Properties of the Transitive Closure of a Relation according to Another One

Let R (resp. S) be a relation over A (resp. A2). In this section, we will dress the fundamental properties of Rs.


### 3.1. Case of Equivalence Relation

The following theorem states the maximal number of iterations to achieve the transitive closure of a relation according to another equivalence relation.Theorem 10.
If S is an equivalence relation, then the transitive closure of R according to S is(3)Rs=⋃i=0NmaxRsi=RsNmaxwith Nmax=min(Cs,n2-Cs,n2-n/2).
Recall thatCs is the cardinal of the quotient set of S.
Intuitively, when S is an equivalence relation, this fundamental theorem gives a way to computeRs, by computing RsNmax.Proof.
In each step of the closure, we have at least a couple that has just been connected by S and which will connect all the pairs that belong to its class.
To prove thatNmax≤Cs it suffices to show that ∀j>Cs we have Rsj=RsCs.
First, we haveRsj=(⋃i=1CsRsi)∪(⋃i=Cs+1jRsi).
Since⋃i=1CsRsi=A, then we will have Rsj=A∪(⋃i=Cs+1jRsi)=A=RsCs.
However, when each class contains two couples, the maximal bound is a bit different; it is[n2/2] (we denote by [x] the entire part of x).
In addition, the relations of type(z,t) S (x,x), for x,y,z∈A3 (resp. (x,x) S (z,t)), are not useful since they no longer advance the process of the closure (i.e., they do not link any two elements by R). Thus, the classes of type [(x,x),(z,t)] should be eliminated; their minimum number that one can have is equal to n/2. Therefore, to have the final closure we can never exceed n2-n/2 iterations.
IfCs>(n2+1/2] then there are classes that contain only one pair. Each class of them reduces the number of iterations by one, since if the couple is linked in a step we will have no influence in the next steps. Hence, we deduce that if Cs>(n2+1/2] then Nmax=n2-Cs.
Based on all the above, the following results are deducted: When S is an equivalent relation, we have the maximal number of iterations as follows:(4)Nmax=minCs,n2-n2ifCs≤n2-n2Nmax=minn2-Cs,n2-n2otherwiseHence one has the desired result.


### 3.2. General Case of the Relation S

The following theorem determines the maximal number of iterations to achieve the transitive closure of a relation according to any other relation.Theorem 11.
Let C be the cardinal ofR∗. The transitive closure of R according to S is Rs=⋃i=0NmaxRsi=RsNmax with(5)Nmax=n2-n2ifC<nNmax=n2-C2otherwiseProof.
In each iterationi, we should have at least one couple (x,y) in A2 such that xRsi-1y (the transitive closure should at least bring this relation in the previous iteration) and which is in relation S with at least another couple (z,t): (x,y) S (z,t).
The relations of type(z,t) S (x,x) (resp. (x,x) S (z,t)) do not advance the process of closure. Then, the couples of type (x,x) should be deleted, and their minimum number that we can have is n. Hence the result is(6)Nmax=n2-n2
If we take into consideration the links closed in the first step (byR∗), noted C, we will ensure that if C>n, then Nmax=[n2-C/2].


### 3.3. Algorithm Skeleton of Transitive Closure (Rs) Computation

We have shown the maximal number of iterations we need to have the closure of a relation according to another one. We can give the closure computation algorithm as shown in Algorithm1.Algorithm 1:Algorithm skeleton of transitive closure computation (RS).
Input: R, S: Two binary relations, i: integer Output: RS: Transitive closure of the relation R according to S R s 0   ← R Do  Rsi←(Rsi-1)∗// Use of any algorithm which computes the simple transitive closure of Rsi (i.e. Floyd-Warshall algorithm) R s i ← ( R s i ) s // update Rsi using the relation S i ← i + 1 While  (i≤Nmax)


## 3.1. Case of Equivalence Relation

The following theorem states the maximal number of iterations to achieve the transitive closure of a relation according to another equivalence relation.Theorem 10.
If S is an equivalence relation, then the transitive closure of R according to S is(3)Rs=⋃i=0NmaxRsi=RsNmaxwith Nmax=min(Cs,n2-Cs,n2-n/2).
Recall thatCs is the cardinal of the quotient set of S.
Intuitively, when S is an equivalence relation, this fundamental theorem gives a way to computeRs, by computing RsNmax.Proof.
In each step of the closure, we have at least a couple that has just been connected by S and which will connect all the pairs that belong to its class.
To prove thatNmax≤Cs it suffices to show that ∀j>Cs we have Rsj=RsCs.
First, we haveRsj=(⋃i=1CsRsi)∪(⋃i=Cs+1jRsi).
Since⋃i=1CsRsi=A, then we will have Rsj=A∪(⋃i=Cs+1jRsi)=A=RsCs.
However, when each class contains two couples, the maximal bound is a bit different; it is[n2/2] (we denote by [x] the entire part of x).
In addition, the relations of type(z,t) S (x,x), for x,y,z∈A3 (resp. (x,x) S (z,t)), are not useful since they no longer advance the process of the closure (i.e., they do not link any two elements by R). Thus, the classes of type [(x,x),(z,t)] should be eliminated; their minimum number that one can have is equal to n/2. Therefore, to have the final closure we can never exceed n2-n/2 iterations.
IfCs>(n2+1/2] then there are classes that contain only one pair. Each class of them reduces the number of iterations by one, since if the couple is linked in a step we will have no influence in the next steps. Hence, we deduce that if Cs>(n2+1/2] then Nmax=n2-Cs.
Based on all the above, the following results are deducted: When S is an equivalent relation, we have the maximal number of iterations as follows:(4)Nmax=minCs,n2-n2ifCs≤n2-n2Nmax=minn2-Cs,n2-n2otherwiseHence one has the desired result.


## 3.2. General Case of the Relation S

The following theorem determines the maximal number of iterations to achieve the transitive closure of a relation according to any other relation.Theorem 11.
Let C be the cardinal ofR∗. The transitive closure of R according to S is Rs=⋃i=0NmaxRsi=RsNmax with(5)Nmax=n2-n2ifC<nNmax=n2-C2otherwiseProof.
In each iterationi, we should have at least one couple (x,y) in A2 such that xRsi-1y (the transitive closure should at least bring this relation in the previous iteration) and which is in relation S with at least another couple (z,t): (x,y) S (z,t).
The relations of type(z,t) S (x,x) (resp. (x,x) S (z,t)) do not advance the process of closure. Then, the couples of type (x,x) should be deleted, and their minimum number that we can have is n. Hence the result is(6)Nmax=n2-n2
If we take into consideration the links closed in the first step (byR∗), noted C, we will ensure that if C>n, then Nmax=[n2-C/2].


## 3.3. Algorithm Skeleton of Transitive Closure (Rs) Computation

We have shown the maximal number of iterations we need to have the closure of a relation according to another one. We can give the closure computation algorithm as shown in Algorithm1.Algorithm 1:Algorithm skeleton of transitive closure computation (RS).
Input: R, S: Two binary relations, i: integer Output: RS: Transitive closure of the relation R according to S R s 0   ← R Do  Rsi←(Rsi-1)∗// Use of any algorithm which computes the simple transitive closure of Rsi (i.e. Floyd-Warshall algorithm) R s i ← ( R s i ) s // update Rsi using the relation S i ← i + 1 While  (i≤Nmax)


## 4. Application on Minimizing Cost Travel in Multimodal Transport

Multimodal transport is a logistic problem in which a set of goods have to be transported to different places with the combination of at least two modes of transport, without a change of container for the goods. Thus, it consists of using in the same path or trip several modes of transport (truck,car,train,plane…). This technique has emerged to deal with problems such as pollution and energy consumption and especially for reason to reduce congestion.Several issues arise from this idea; we can cite planning of multimodal transportation tasks [13, 14] and modeling the multimodal transportation networks. A lot of algorithms have been elaborated to find the viable shortest path under objectives such as travel time and number of modal transfers [15, 16]. The most important among them remains the calculation of multimodal shortest path.


### 4.1. Case of Two Modes

#### 4.1.1. Formulation of the Problematic

Assume that we have a transport network as shown in Figure2. It is presented by a graph GM(V,E) constituted by two modes. The first mode is the roads (m1) and the second one presents the railways (m2). Each mode has its set of nodes Vmi⊂V (its cardinal noted ni) and its edges Emi⊂E. The graph contains also a set of transfer edges Et that allows the mode change. These edges are mostly directed; therefore we note the set of their heads H and the set of their tails T.Figure 2
Multimodal transport graph.During the transportation, we are facing constraints on mode changing, such as minimizing the number of transfers, viability, time of conveyance waiting, etc.For some reasons such as congestion, we can change the mode only if we will reduce the transport cost. For example, we can choose the pathy1y4 instead of x2x6 path only if the following condition is fulfilled: Costy1y4≤Costx2x6. In general, we have Costxixj≤Costxkxl, for (xi,xl)∈H2 and (xj,xk)∈T2.Given these data and flowing in both modes, the problem is to find the lowest cost between any two points of the graph.


#### 4.1.2. Lowest Cost in Multimodal Transport

We present the transport network by a binary relation noted R. Based on matrix representation, this relation will be represented by a matrix of dimension n (n is the number of nodes):MR=MijR0≤i,j≤n=cij0≤i,j≤n, with cij being the cost needed to achieve the node j from i. The transfer edges are not presented here. The constraints on mode changes are expressed by another binary relation, noted S, represented by a matrix of dimension n2.MS={MlkS0≤l,k≤n2∣MlkS=1ifCostxixj≤Costxkxl with l=ni-1+jandk=nq-1+p,0else}.The constraints on mode changes are expressed by another binary relation, noted S.


#### 4.1.3. The Applied Algorithm

Firstly, we accomplish the transitive closure of R. Afterwards, we scan the matrix updated ofR∗ looking for the coordinates which has noninfinite cost. Then, for every coordinate MijR≠∞ we point out to the line corresponding to xi,xj in MS in order to select the coordinates having the cost equal to 1. Assume, for instance, that Costxi,xj,xp,xq=1; this allows us to value the correspondent couples, xp,xq with minCostxp,xq,Costxi,xj.This operation will be repeated until the matrix is stationary, which corresponds toNmax iterations as showed in Theorem 10. Then, the algorithm complexity is Θ(n3Nmax) where n is the number of system variables.


#### 4.1.4. General Case

Sometimes, for reason of loading/unloading cost, we can change the mode only if we will earn at least a definite supplementary cost. This can be expressed asCostxixj-Costxkxl≤c for xi,xl∈H2 and xj,xk∈T2. This time, the binary relation S is represented by the following matrix: MS={MlkS0≤l,k≤n2∣MlkS=bpqijifCostxixj-Costxkxl≤bpqij with l=ni-1+jandk=nq-1+p,0else}, where bpqij presents the cost that should be earned in order to change the mode.It is the same as the previous example with some modifications. After finishing the transitive closure of R, we scan the matrix updated ofR∗ looking for the coordinates which have noninfinite cost. Then, for every coordinate MijR≠∞, we change the coordinates having the noninfinite costs in the line corresponding to xi,xj in MS. Take as an example Costxi,xj,xp,xq≠∞; this allows us to value the correspondent couples, xp,xq with minCostxp,xq,Costxi,xj+Costxi,xj,xp,xq.This operation will be repeated until the matrix is stationary. The algorithm is then like Algorithm2.Algorithm 2:Lowest cost in multimodal transport graph.
Input: Two matrices representing the two transport mode graphs Output: Canonical form of the matrix that represents the merge multimodal graph Do // Step1: Use any algorithm which computes the simple transitive closure of MR. Next, we use Floyd-Warshall. Fori: 1→n For  j: 1→n For  k: 1→n     MijR=minMijR,MikR+MkjR} // Step2: Update MR using MS Fori: 1 → n For  j: 1→n If M i j R ≠ ∞  then for  k: 1→n2 If M i - 1 n + j , k S = = 1 then M k / n + 1 ,  k - k / n ∗ n R = m i n M i j R ,   M k / n + 1 ,  k - k / n ∗ n R // k/n: entire part of k/n End if End if } a ← a + 1 } While  (a≤Nmax)


### 4.2. Case of More Than Two Modes

The previous algorithm provides the shortest path only if the following proposition is considered: between two crossings of the same mode we pass through an odd number of modes. This implies that the start point and the arrival point belong to the same mode. Consequently, to hold the same computation, the use order of modes in the general case should be as follows:mi,mj,mk,mj,mk,ml,mo,mp,mo,ml,mk,…,mi.In this way, we will have the lowest cost between each two points using the previous algorithm.


## 4.1. Case of Two Modes

### 4.1.1. Formulation of the Problematic

Assume that we have a transport network as shown in Figure2. It is presented by a graph GM(V,E) constituted by two modes. The first mode is the roads (m1) and the second one presents the railways (m2). Each mode has its set of nodes Vmi⊂V (its cardinal noted ni) and its edges Emi⊂E. The graph contains also a set of transfer edges Et that allows the mode change. These edges are mostly directed; therefore we note the set of their heads H and the set of their tails T.Figure 2
Multimodal transport graph.During the transportation, we are facing constraints on mode changing, such as minimizing the number of transfers, viability, time of conveyance waiting, etc.For some reasons such as congestion, we can change the mode only if we will reduce the transport cost. For example, we can choose the pathy1y4 instead of x2x6 path only if the following condition is fulfilled: Costy1y4≤Costx2x6. In general, we have Costxixj≤Costxkxl, for (xi,xl)∈H2 and (xj,xk)∈T2.Given these data and flowing in both modes, the problem is to find the lowest cost between any two points of the graph.


### 4.1.2. Lowest Cost in Multimodal Transport

We present the transport network by a binary relation noted R. Based on matrix representation, this relation will be represented by a matrix of dimension n (n is the number of nodes):MR=MijR0≤i,j≤n=cij0≤i,j≤n, with cij being the cost needed to achieve the node j from i. The transfer edges are not presented here. The constraints on mode changes are expressed by another binary relation, noted S, represented by a matrix of dimension n2.MS={MlkS0≤l,k≤n2∣MlkS=1ifCostxixj≤Costxkxl with l=ni-1+jandk=nq-1+p,0else}.The constraints on mode changes are expressed by another binary relation, noted S.


### 4.1.3. The Applied Algorithm

Firstly, we accomplish the transitive closure of R. Afterwards, we scan the matrix updated ofR∗ looking for the coordinates which has noninfinite cost. Then, for every coordinate MijR≠∞ we point out to the line corresponding to xi,xj in MS in order to select the coordinates having the cost equal to 1. Assume, for instance, that Costxi,xj,xp,xq=1; this allows us to value the correspondent couples, xp,xq with minCostxp,xq,Costxi,xj.This operation will be repeated until the matrix is stationary, which corresponds toNmax iterations as showed in Theorem 10. Then, the algorithm complexity is Θ(n3Nmax) where n is the number of system variables.


### 4.1.4. General Case

Sometimes, for reason of loading/unloading cost, we can change the mode only if we will earn at least a definite supplementary cost. This can be expressed asCostxixj-Costxkxl≤c for xi,xl∈H2 and xj,xk∈T2. This time, the binary relation S is represented by the following matrix: MS={MlkS0≤l,k≤n2∣MlkS=bpqijifCostxixj-Costxkxl≤bpqij with l=ni-1+jandk=nq-1+p,0else}, where bpqij presents the cost that should be earned in order to change the mode.It is the same as the previous example with some modifications. After finishing the transitive closure of R, we scan the matrix updated ofR∗ looking for the coordinates which have noninfinite cost. Then, for every coordinate MijR≠∞, we change the coordinates having the noninfinite costs in the line corresponding to xi,xj in MS. Take as an example Costxi,xj,xp,xq≠∞; this allows us to value the correspondent couples, xp,xq with minCostxp,xq,Costxi,xj+Costxi,xj,xp,xq.This operation will be repeated until the matrix is stationary. The algorithm is then like Algorithm2.Algorithm 2:Lowest cost in multimodal transport graph.
Input: Two matrices representing the two transport mode graphs Output: Canonical form of the matrix that represents the merge multimodal graph Do // Step1: Use any algorithm which computes the simple transitive closure of MR. Next, we use Floyd-Warshall. Fori: 1→n For  j: 1→n For  k: 1→n     MijR=minMijR,MikR+MkjR} // Step2: Update MR using MS Fori: 1 → n For  j: 1→n If M i j R ≠ ∞  then for  k: 1→n2 If M i - 1 n + j , k S = = 1 then M k / n + 1 ,  k - k / n ∗ n R = m i n M i j R ,   M k / n + 1 ,  k - k / n ∗ n R // k/n: entire part of k/n End if End if } a ← a + 1 } While  (a≤Nmax)


## 4.1.1. Formulation of the Problematic

Assume that we have a transport network as shown in Figure2. It is presented by a graph GM(V,E) constituted by two modes. The first mode is the roads (m1) and the second one presents the railways (m2). Each mode has its set of nodes Vmi⊂V (its cardinal noted ni) and its edges Emi⊂E. The graph contains also a set of transfer edges Et that allows the mode change. These edges are mostly directed; therefore we note the set of their heads H and the set of their tails T.Figure 2
Multimodal transport graph.During the transportation, we are facing constraints on mode changing, such as minimizing the number of transfers, viability, time of conveyance waiting, etc.For some reasons such as congestion, we can change the mode only if we will reduce the transport cost. For example, we can choose the pathy1y4 instead of x2x6 path only if the following condition is fulfilled: Costy1y4≤Costx2x6. In general, we have Costxixj≤Costxkxl, for (xi,xl)∈H2 and (xj,xk)∈T2.Given these data and flowing in both modes, the problem is to find the lowest cost between any two points of the graph.


## 4.1.2. Lowest Cost in Multimodal Transport

We present the transport network by a binary relation noted R. Based on matrix representation, this relation will be represented by a matrix of dimension n (n is the number of nodes):MR=MijR0≤i,j≤n=cij0≤i,j≤n, with cij being the cost needed to achieve the node j from i. The transfer edges are not presented here. The constraints on mode changes are expressed by another binary relation, noted S, represented by a matrix of dimension n2.MS={MlkS0≤l,k≤n2∣MlkS=1ifCostxixj≤Costxkxl with l=ni-1+jandk=nq-1+p,0else}.The constraints on mode changes are expressed by another binary relation, noted S.


## 4.1.3. The Applied Algorithm

Firstly, we accomplish the transitive closure of R. Afterwards, we scan the matrix updated ofR∗ looking for the coordinates which has noninfinite cost. Then, for every coordinate MijR≠∞ we point out to the line corresponding to xi,xj in MS in order to select the coordinates having the cost equal to 1. Assume, for instance, that Costxi,xj,xp,xq=1; this allows us to value the correspondent couples, xp,xq with minCostxp,xq,Costxi,xj.This operation will be repeated until the matrix is stationary, which corresponds toNmax iterations as showed in Theorem 10. Then, the algorithm complexity is Θ(n3Nmax) where n is the number of system variables.


## 4.1.4. General Case

Sometimes, for reason of loading/unloading cost, we can change the mode only if we will earn at least a definite supplementary cost. This can be expressed asCostxixj-Costxkxl≤c for xi,xl∈H2 and xj,xk∈T2. This time, the binary relation S is represented by the following matrix: MS={MlkS0≤l,k≤n2∣MlkS=bpqijifCostxixj-Costxkxl≤bpqij with l=ni-1+jandk=nq-1+p,0else}, where bpqij presents the cost that should be earned in order to change the mode.It is the same as the previous example with some modifications. After finishing the transitive closure of R, we scan the matrix updated ofR∗ looking for the coordinates which have noninfinite cost. Then, for every coordinate MijR≠∞, we change the coordinates having the noninfinite costs in the line corresponding to xi,xj in MS. Take as an example Costxi,xj,xp,xq≠∞; this allows us to value the correspondent couples, xp,xq with minCostxp,xq,Costxi,xj+Costxi,xj,xp,xq.This operation will be repeated until the matrix is stationary. The algorithm is then like Algorithm2.Algorithm 2:Lowest cost in multimodal transport graph.
Input: Two matrices representing the two transport mode graphs Output: Canonical form of the matrix that represents the merge multimodal graph Do // Step1: Use any algorithm which computes the simple transitive closure of MR. Next, we use Floyd-Warshall. Fori: 1→n For  j: 1→n For  k: 1→n     MijR=minMijR,MikR+MkjR} // Step2: Update MR using MS Fori: 1 → n For  j: 1→n If M i j R ≠ ∞  then for  k: 1→n2 If M i - 1 n + j , k S = = 1 then M k / n + 1 ,  k - k / n ∗ n R = m i n M i j R ,   M k / n + 1 ,  k - k / n ∗ n R // k/n: entire part of k/n End if End if } a ← a + 1 } While  (a≤Nmax)


## 4.2. Case of More Than Two Modes

The previous algorithm provides the shortest path only if the following proposition is considered: between two crossings of the same mode we pass through an odd number of modes. This implies that the start point and the arrival point belong to the same mode. Consequently, to hold the same computation, the use order of modes in the general case should be as follows:mi,mj,mk,mj,mk,ml,mo,mp,mo,ml,mk,…,mi.In this way, we will have the lowest cost between each two points using the previous algorithm.


## 5. Conclusion

This paper fits in the frame of the application of operations research in urban planning and transportation. It brought a new optimization method that consists in the concept of the “transitive closure of a given relation with respect to a property.” In the literature there is no work that addresses this issue; therefore we have cited the close works done on the transitive closure with many relations. Afterwards, we situated our technique vis-à-vis hypergraph theory and linear programming.The contributions of this paper are both theoretical and practical. We elaborated methods to compute the transitive closure of a relation according to a property and in particular the case where the property is another relation. After proving the completeness of the closure and the number of necessary iterations to achieve the solution, we design the applied algorithms. What is more interesting is the low algorithmic complexity that is shown to be polynomial. It is in the order ofΘ(n3) where n is the number of the constraint system variables, which presents also the number of nodes in the multimodal graph. These algorithms are also useful in many real world problems such as optimal solutions, Constraint Satisfaction Problem, graph optimization, search engines, and system verification.



---

*Source: 9579343-2018-08-23.xml*