Traffic flow routing and scheduling in a food supply network

3.1 Modelling framework

A SCCP (see Figure 1) (Bocewicz and Banaszak, 2013) consists of a set of local processes P={P_i|i=1 … ln} which execute operations periodically, based on a set of shared resources R={R_k|k=1 … lk}. Each process P_i is characterised by a sequence of operations O_i=(o_i,1, o_i,2, …, o_i,j, …, o_{i, lr(i)}), where lr(i) stands for the number of process operations P_i. Operation o_i,j of process P_i is executed based on the resources specified by process route M_i=(r_i,1, …, r_i,j, …, r_i,lr(i)), where r_i,j∈R stands for the resource used to execute operation o_i,j. Local processes are executed in a cyclic manner, which means that after all operations O_i have been executed, the sequence is started again.

Figure 1 shows an example of an SCCP which incorporates three local processes P={P₁, P₂, P₃}, whose operations are executed along the following routes: M₁=(R₄, R₃, R₅), M₂=(R₂, R₃, R₁). The elements shown make up structure SC of the SCCP, which is an ordered pair:

Priority dispatching rules σ_k settle resource conflicts related to the order in which processes/streams can access shared resources. R_k (e.g. σ₁=(P₃, P₂) from Figure 1 is a sequence which determines the order of processes supported by resource R₁: …, P₃, P₂, P₃, P₂, P₃, P₂, …). These rules implement the process synchronization protocol which guarantees non-preemptive scheduling of resources, and the so-called mutual exclusion condition. Let 𝕊 stand for a set of admissible system states, i.e. states which specify the allocation of processes to resources. It is assumed that set S ′⊆ S is a set of states reachable from the initial state S⁰∈ S ′ if there is a sequence of states (S⁰, S^h, …, S^g, S^d, Sⁱ, S^k, …, S^w, S^r) of set S ′wherein each successive state is reachable, in accordance with Θ, from a state immediately preceding it, i.e. ∃S⁰, S^h, S^g …, S^w, S^r∈ S ′ such that S^h is reachable from S⁰ and S^g is reachable from S^h and … and S^r is reachable from S^w.

In this context, the behaviour of the SCCP can be defined as an ordered triple:

Fixed cyclic execution of a SCCP is reachable either directly from an initial state or as a consequence of reaching a state belonging to such a sequence. In other words, behaviour B described by fixed cyclic execution occurs when:

• it has a finite number of states S ′; and

• ∀Sⁱ∈ S ′, state Sⁱ is reachable from Sⁱ⁻¹ and state S⁰ is reachable from S^q∈ S ′ in accordance with the dispatching rules adopted and the principle of simultaneous local allocation.

Therefore, SCCPs belong to the class of discrete event dynamic systems. It is easy to observe that by introducing into the structure of local processes SL=(P, U, O, Ω) a set of execution time sequences for operation T={T_i=(t_i,1, …, t_i,j, …, t_i,lr(i))|i=1 … ln}, where t_i,j is the execution time of operation o_i,j, one can switch from event-driven to time-driven representation of the structure of local processes SL=(P, U, O, Ω, T). This means that by assigning to each operation o_i,j an associated execution time t_i,j ∈ ℕ⁺ and the starting time in each kth execution x_i,j(k)∈ ℕ, one can naturally move from qualitative to quantitative assessment of the performance of the SCCP.

The cyclic behaviour of the SCCP from Figure 1 is illustrated by the diagram in Figure 2, which shows states and events which connects them. An event is understood here as a transition between two successive admissible process allocations. Of course, the topology of the structure of local processes may, but need not, coincide with the layout of routes which allow actual implementation of local processes. Figure 1(b) illustrates a situation in which the graph of execution of transport processes from Figure 1(a) is a subgraph of a certain public transport structure.

In the discussion to follow, we will focus on regular-structure SCCPs with grid-like topologies such as those encountered in crystalline structures and mosaics. An example of such a structure (Figure 3(a)) with a highlighted repeating pattern is shown in Figure 3(b).

In the light of the above considerations, a question arises whether there exists an ordered pair: (initial process allocation, a set of dispatching rules) which ensures a cyclic behaviour of an SCCP, i.e. one that guarantees a return to the initial allocation, once a sequence of transition allocations has been completed.

The problem of whether such a pair exists is a computationally hard problem, which limits the analysis to small-scale cases, much smaller than those encountered in practice. This, in turn, means that the problem of congestion avoidance in networks modelled by SCCP is also computationally hard.

3.2 Solution methodology

The approach proposed in the present study assumes a solution methodology based on:

• the paradigm of regular (e.g. grid-like) topology of a SCCP structure, which posits that the structures in question are composed of a finite set of identical repeating substructures;

• the scale decomposition paradigm, which posits that the behaviour of a given SCCP structure can be predicted on the basis of the behaviour of its substructure. Examples of such structures, called elementary covering structures (ECS), are shown in Figure 3(b); and

• the problem decomposition paradigm, which posits that a supply problem can be divided into a layer of problems of synthesis and analysis of transport mode infrastructure of an SCCP and a layer of problems of synthesis and analysis of goods transport processes of an SCCMP executed in that infrastructure, defined, respectively, by (1)/(2) and (4)/(5).

An ECS is a digraph comprised of elementary substructures (modelling local cyclic processes) which occur in the regular structure of an SCCP such that:

• the graph is composed of elementary cyclic digraphs which model local processes; and

• it can be used to tessellate a given regular structure.

The images do not exhaust all possible cases of ECSs which may differ in shape and in scale (i.e. in the number of elementary structures they contain). However, their common feature is that they can be tessellated (like a mosaic) to form a pattern that recreates a given regular structure.

Each ECS has a corresponding covered form ECS that is formed by gluing together the vertices of the ECS that in the regular structure of the SCCP are joined with the corresponding fragments of the elementary structures of an adjacent ECS. An ECS extracted from the elementary structure is shown in Figure 4(a) and the relationships between the selected ECS and its covered form is presented in Figure 4(b).

The consequence of adopting the first two paradigms is the following theorem that relates the behaviour of a given regular structure to an elementary structure extracted from it.

Theorem: given are a regular-structure SCCP and its ECS. A cyclic behaviour of the covered form of the ECS entails a cyclic behaviour of the SCCP.

Proof. If, in accordance with the principle of decomposition of a regular structure, one replicates the same initial process allocation A⁰ and the same rule semaphores Z⁰ in all the remaining ECSs, the structure (see Figure 5(b)) will be free of collisions between processes that use the same resources. In summary, an initial allocation of local processes in a regular network will be followed in each individual ECS by a next allocation of local processes in compliance with the same priority selection rules. The new allocation in the regular structure concerns the processes and resources that are “copies” of the processes and resources of the contemplated ECS. This type of situation is illustrated in Figure 5.

This means that the successive process allocations that occur in cycles after each initial allocation in the ECS will have their counterparts in the overall regular structure – allocations of all the local processes of the structure. Thus, period α of the processes executed in the regular structure is equal to the period of processes executed in the ECS. This means that cyclic behaviour of the ECS implies cyclic behaviour of the regular-structure SCCP.

It follows from the theorem above that by solving a small-scale computationally hard problem (associated with an ECS), one can solve, online, a large-scale problem associated with a corresponding regular-structure SCCP. It is worth noting that the cycle period specified for the ECS determines an identical cycle period for the entire structure of the SCCP.

4.1 Multimodal processes

The concept of a multimodal process (Bocewicz et al., 2014) refers to a process that is executed using different modalities, e.g. associated with different transmission media enabling radio, fibre optics, or wire communication. Processes are multimodal when operations require for their execution, beside resources R, also other processes. A pertinent example is the route of a passenger who travels to his destination by various metro lines (see Figure 1(b)).

In the same way as for SCCP, one can also introduce a SCCP-driven system of concurrent cyclic multimodal processes (SCCMP). Accordingly, structure MSC of an SCCMP is an ordered pair:

Similarly to SCCPs, the behaviour of an SCCMP can be defined as an ordered triple:

Consequently, an SCCMP belongs to the class of discrete event dynamic systems. It is easy to observe that by introducing into the structure of multimodal processes MSL=(MP, MU, MO, MΩ) a set of sequences of execution times of operation MT={MT_i=(mt_i,1, …, mt_i,j, …, mt_i,lr(i))|i=1 … lm}, where mt_i,j is the execution time of operation mo_i,j, one can switch from event-driven to time-driven representation of the structure of local processes MSL′=(MP, MU, MO, MΩ, MT). This means that by assigning to each operation mo_i,j an associated execution time mt_i,j∈ℕ⁺ and the starting time for each kth execution mx_i,j(k)∈ℕ, one can naturally move from qualitative to quantitative assessment of the performance of a SCCMP, e.g. from the simple conclusion that the behaviour is periodic to an estimation of the specific value of the period of cyclically repeating events.

Cyclic behaviour of the SCCMP from Figure 1 is illustrated by the diagram in Figure 6. It is easy to demonstrate that cyclic behaviour of an SCCP implicates cyclic behaviour of the multimodal processes executed in it. Assuming that a SCCMP has a multi-level structure, an SCCMP based on an SCCP is indexed as a first-level SCCMP (SCCMP⁽¹⁾), a next system based on SCCMP⁽¹⁾ is indexed as SCCMP⁽²⁾, and so on. This also means that the behaviour of the successive layers SCCMP⁽ⁱ⁾ will also be cyclic. Due to the wide array of practical applications of multimodal processes (Bocewicz et al., 2014, 2015), these processes are characterised by many additional variables. In the context of the experiments conducted in this study (see Section 6), the following variables are found to be especially salient:

• takt time TC_i of process mP_i understood as the time between the moments of completion of successive executions of stream/process mP_i;

• lead time Tt_i of process mP_i understood as the time between the start of the first operation and completion of the last operation of this process;

• transport time Tt_i,(a−b) between resources R a , R b ∈ R ¯ of process mP_i understood as the time between the moments of completion of operations on resources R_a, R_b; and

• start time xs_i(k) of process mP_i defined as a function determining the starting moment of the first operation of process mP_i in the kth cycle.

The values of these variables for the processes executed in the system shown in Figure 1(a)) are presented in Figure 6.

4.2 Problem formulation

The problems of cyclic scheduling in the domain of integer variables can be discussed in the context of Diophantine equations (Bocewicz et al., 2009). This means that the problem of cyclic scheduling can be reduced to the problem of solvability of corresponding Diophantine equations, i.e. the problem of finding whether there exist solutions of these equations.

Because there are no general methods for solving such problems, each case requires an individualised approach taking into account the specific characteristic of the problem. For example, scheduling of SCCPs synchronized by the mutual exclusion protocol may result in deadlocks and starvation. In practice, this means that there are two problems to be solved. The first one is to determine the conditions which guarantee the existence of a non-empty set of feasible solutions. The second problem is to find in the set of feasible solutions, the optimum solution. It is worth noting that in a general case, both of these problems are NP-complete.

Cyclic scheduling problems, considered in the context of SCCP and SCCMP, are basically analysis and synthesis problems. Finding a solution to an analysis problem boils down to answering the question of whether in a given structure of a supply system, there is a way to transfer goods between selected points in a given period of time? On the other hand, an example of a synthesis problem can be reduced to the question of whether there exists a structure of the supply system which enables the transfer of goods between selected points in a selected way, in a given period of time? An example of synthesis problem is considered in Ahmed (2009), authors of which proposed a logistic plan design following customer requirements regarding a way of water distribution.

More formally speaking, in an analysis problem, given the structure of the SCCP SC (Equation (1)) which encompasses sets of process resources R and routes U, sets of operations O, as well as the number of streams Ω of processes executed along the individual routes in a fixed cyclic sequence B (Equation (2)), one seeks SCCMPs with structure MSC (Equation (4)) (encompassing a set of resources R ¯ , routes of processes MU connecting the given points of origin to their destinations, sets of operations MO, as well as the number of streams MΩ) which guarantee cyclic MB (Equation (5)) deliveries in specific time windows.

In a synthesis problem, on the other hand, given the structure MSC (Equation (4)) of an SCCMP, which guarantees cyclic MB (Equation (5)) deliveries in specific time windows, one seeks to find SCCPs with structure SC (Equation (1)) encompassing a set of resources R and routes of processes U, sets of operations O as well as the quantity of streams Ω of processes executed along the individual routes in a fixed cyclic sequence B (Equation (2)) which ensures cyclic MB (Equation (5)) supplies in specific time windows.

5.1 Declarative modelling

The formulations of the problems of analysis and synthesis introduced earlier in this text, which make a connection between SCCPs and SCCMPs, also find their reflection in the declarative model. This model encompasses declarative models of the structure and behaviour of SCCPs and SCCMPs. In particular, in the context of the CSP, this model includes sets of decision variables V, domains D which specify their values, and constraints C which relate them within the SCCPs and SCCMPs considered separately, as well as a set of constraints C^* which relate variables and domains between those systems.

The set of decision variables found in this model includes:

• sets of resources R and shared resources found in an SCCP and sets of resources R ¯ and shared resources present in an SCCMP;

• structures of local processes SL present in the SCCP and structures of multimodal processes MSL running in the SCCMP;

• a set of dispatching rules Θ governing the access of local processes/streams to shared resources of the SCCP and a set of dispatching rules Θ ¯ governing the access of multimodal processes/streams to the resources of set R ¯ in the SCCMP; and

• initial states: S⁰ in the SCCP (corresponding to the initial allocation of local processes) and S 0 ¯ in the SCCMP (corresponding to the initial allocation of multimodal processes to R ¯ ).

Sets of decision domains corresponding to the above-mentioned decision variables determine the integer values of resource availability, integer operation execution times, integer vectors specifying the number of local process streams (vehicles), permutation vectors of local processes sharing the resources, and binary-valued vectors that specify the values of initial states.

Sets of constraints imposing regularity of structure of an SCCP and the principle of mutual exclusion of local processes as well as constraints enforcing the principle of mutual exclusion of multimodal processes in SCCMP structures (Bocewicz et al., 2015) also include constraints which treat as identical resources of these structures, for example, R ¯ ⊂R, and times of goods transport operations with the travel times of the means of transport used for this purpose (Bocewicz et al., 2014). Additionally, it is assumed that there are constraints which relate routes of multimodal processes mP_i with fragments of routes of local processes (see: mp_i expression (4)).

A declarative model of the integrated supply model is represented as an ordered triple:

The method of formal implementation of this model in the CSP is discussed below.

5.2 CSP

Depending on the class of problem considered (analysis or synthesis), the declarative model proposed (6), expressed using CSP terminology, is simplified:

• in the case of the analysis problem to the form:

  (7) C S A = ( V S C C M P , D S C C M P , C S C C M P ∪ C S C C P − S C C M P ) ,

  according to which, what is being sought are the values of decision variables V_SCCMP characterizing an SCCMP (a set of resources R ¯ , routes of processes MU connecting the given points of origin to their destinations, sets of operations MO, the number of streams MΩ and behaviour MB (5)) which satisfy constraints C_SCCP−SCCMP characterizing a given structure of an SCCP (constraints entailed by structure SC (1)) and constraints on multimodal processes C_SCCMP.

• And in the case of the synthesis problem to the form:

  (8) C S S = ( V S C C P , D S C C P , C S C C P ∪ C S C C P − S C C M P ) ,

  according to which, what is being sought are the values of decision variables V_SCCP characterizing an SCCMP (a set of resources R, process routes U, sets of operations O, number of streams Ω, and behaviour B (2)) which satisfy constraints C_{SCCP − SCCMP} characterizing the given SCCMP (constraints entailed by structure MSC(4)) and constraints on local processes C_SCCP.

Among the constraints (7) and (8), special attention should be paid to those that guarantee deadlock-free and collision-free execution of local and multimodal processes. Bocewicz and Banaszak (2013) and Bocewicz et al. (2014) discuss constraints of this type in detail.

6.1 Food supply grids network

To illustrate the proposed approach, the transport network model shown in Figure 7(a) is considered. This is part of a food supply network shown in Figure 8, which is composed of autonomous grids, i.e. ECSs (see Figure 7(b)). In each ECS, there are two groups of recipients (resources R₆−R₉ and R₁₄−R₁₇), two groups of suppliers (R₁₀−R₁₃ and R₁₈−R₂₁), two groups of manufacturers (resources R₂, R₃ and R₄, R₅), and sets of warehouses (R₁, R₂₂−R₂₅) and distributors (resources R₂₆−R₂₉). Goods are delivered from suppliers to recipients by eight means of transport. The structure shown in Figure 7(a) and its ECS counterpart from Figure 7(b) corresponds to typical goods supply.

The ECS from Figure 7(b), marked out in the network of Figure 8, is characterised by the following variables:

• a set of resources R={R₁, R₂, … R₃₉} with unit availability C(R_k)=1 for R_k∈R;

• a set of single-stream local processes P={P₁, P₂, …, P₈}; and

• a set of routes of local processes.

p₁=(R₁, R₂₅, R₂₈, R₂₃, R₂₇), p₂=(R₁, R₂₄, R₂₆, R₂₂, R₂₉), p₃=(R₂, R₂₆, R₃, R₂₇), p₄=(R₄, R₂₉, R₅, R₂₈), p₅=(R₆, R₇, R₈, R₉, R₂₇), p₆=(R₁₀, R₁₁, R₁₂, R₁₃, R₂₈), p₇=(R₁₈, R₁₉, R₂₀, R₂₁, R₂₉), p₈=(R₁₇, R₁₈, R₁₉, R₂₀, R₂₆), number sequence of streams of local process Ω=(1, 1, 1, 1, 1, 1, 1, 1).

The resources of set R are non-preemptive, and the execution of local processes P is coordinated by the principle of mutual exclusion.

6.2 Delivery routing and scheduling

Computational experiments were conducted for the food supply network shown in Figure 8 to illustrate the proposed approach in the context of:

• the problems of analysis, in which delivery routes are being sought which can ensure the fulfilment of given customer expectations; and

• the problems of synthesis which seek to find an organisation of available transport modes which guarantees food deliveries in accordance with given customer expectations.