Pierre Desport

Frédéric Lardeux

David Lesaint

Carla Di Cairano-Gilfedder

Anne Liret

Gilbert Owusu

A Sequence-Based Metaheuristic For Tactical Distribution Planning In Closed-Loop Supply Chains

Keywords: Supply Chain Planning, Metaheuristics, Distribution, Transport

We present a metaheuristic for planning the distribution of items in closed-loop supply chains. This metaheuristic composes sequences of transfer and repair actions to generate plans iteratively. It uses a local search algorithm based on an efficient data structure to construct and select improving sequences at each step. An experimental comparison with a mixed integer programming approach shows its scalability and robustness on a variety of instances. We also study and discuss the ability to support different distribution policies.

Introduction

Many organisations in equipment-intensive sectors (automotive, electronics, telecommunications, . . . ) implement closed-loop supply chains to recapture economic value from used or defective parts. Closed-loop supply chains (CLSC) extend the "forward flow" model of traditional supply chains by integrating reverse logistics operations including repair, recycling or disposal (????). In field service organisations for instance, CLSC typically combine two flows: the replenishment of field depots with spare parts, and the transfer of used parts back to warehouse centres before repair and possible reuse. Figure 1 illustrates a three-echelon CLSC in this context where a warehouse centre relies on a repair site to reinject repaired parts in the supply flow. Fig. 1. A 3-level closed-loop supply chain CLSC inventory systems control all repair and transfer activities (supply of spare parts and return of used parts) across the different sites of the supply chain (warehouse centres, repair centres, hubs, field depots . . . ). In some environments (e.g. field maintenance operations), the demand for spare parts for each site and each time period is known beforehand with certainty. In this case, a centralised proactive approach may be applied to plan these activities ahead of time and minimise costs relating to backordering, storage, transport and repair. ? propose a mixed integer program (MIP) to solve this tactical distribution planning problem (TDPP). The model uses a weighted objective function and combines conservationof-flow constraints with a priority rule that forbids backordering on a site in the presence of spares. This rule makes the problem NP-hard and the authors introduce a metaheuristic called BIS that compares favourably against a MIP method over pseudo-random instances.

BIS is a best-improvement local search algorithm using diversification. It builds plans iteratively by selecting and adding at each step a sequence of unitary actions (supply, return and/or repair of a single part). In this paper, we provide a detailed description of the two components of BIS, namely, the local search algorithm and the sequence construction and selection procedure which uses a dedicated data structure to efficiently update the set of feasible sequences and resulting gains. The rest of the paper is organised as follows. Section 2 gives a brief overview of the MIP model for TDPP. Section 3 introduces BIS and section 4 presents experimental results comparing BIS and MIP. Section 5 then discusses how different weightings of the objective function affect the distribution of items. Section 6 concludes.

Tactical Distribution Planning Problem

A TDPP instance is primarily defined by a CLSC network and a discrete planning horizon. As shown in Figure 1, a CLSC network consists of supply, return and repair routes connecting the different sites. Each route comes with a fixed schedule that defines the possible start and end times for actions planned along this route (e.g., 1-day long weekly shipments starting on Mondays). Each site initially holds a predefined number of spare parts (aka. healthy items) and used parts (aka. faulty items). The "demand" forecast then defines the number of healthy items that should be taken out of inventory on each site and at each point in time (stock permitting) and the number of faulty items that will be dropped on the site and enter the supply chain. These quantities are considered identical in some environments (e.g., field repair services) which is the assumption made here.

The objective is to determine an optimal and feasible plan of actions. Each action is defined by the choice of a route, a start time, and a quantity representing the number of healthy or faulty items acted upon (transfers or repairs). All actions must comply with the above mentioned topological and calendar constraints, and the conservation-offlow constraints enforced on each site over healthy and faulty items. To comply with standard practices, an additional rule applies that forbids backordering if spares are locally and readily available on a site, i.e., satisfying local demand takes priority. Lastly, the objective is cast as a weighted sum of linear cost functions on the total number of items that are backordered, held in inventory, transferred or repaired. No start-up penalty applies and the weights are used-defined to allow different prioritisation strategies.

: L × T → N storage unit costs µ s h , µ s f : L → R backordering unit costs µ b : L → R transfer unit costs µ m h , µ m f : L × L → R repair unit costs µ m r : L → R weights ω s , ω b , ω m hf , ω m r ∈ N Variables storage s h , s f : L × T → N backorders b : L × T → N transfers m h , m f : L × L × T × T → N repairs m r : L × T × T → N costs c, c s , c b , c m hf , c m r ∈ R
? propose a MIP to model this problem which we briefly introduce. L and T denote, respectively, the set of sites and the planning horizon viewed as an ordered set of time buckets. Table 1 introduces the constants and variables of the model. Constants include the demand forecast d, the unit costs µ * and the user-defined weights w * . Variables model the actions of the plan (in bold style) and the resulting state of the supply chain over the temporal horizon. For two sites l and l , and time buckets t and t , variable m h l,l ,t,t (respectively, m f l,l ,t,t ) denotes the number of healthy (resp., faulty) items transferred from l at t and reaching l at t . Likewise, variable m r l,t,t denotes the number of faulty items whose repair starts at t and ends at t on site l. The constraints (not shown here) link state and action variables to enforce the rules relating to routing, scheduling, flow preservation, and flow prioritisation. In particular, any action variable corresponding to a nonexistant route is set to 0. Note also that any assignment of the action variables completely determine the state variables. The equations below show the objective function c to minimise and its different components.

c s = l∈L,t∈T (s h l,t × µ s h l + s f l,t × µ s f l ) c b = l∈L,t∈T b l,t × µ b l c m hf = l,l ∈L, t,t ∈T (m h l,l ,t,t × µ m h l,l + m f l,l ,t,t × µ m f l,l ) c m r = l∈L, t,t ∈T (m r l,t,t × µ m r l ) c = ω s × c s + ω b × c b + ω m hf × c m hf + ω m r × c m r 3 Metaheuristic
This section presents the metaheuristic BIS (Best Improving Sequence) for solving TDPP. BIS does not operate on the solution representation of the MIP model. Rather, it constructs a plan by repeatedly adding sequences of unitary actions (i.e., actions that only involve a single item). As explained below, sequences are constructed over the space-time graph of the problem based on the current plan, filtered and scored using a dedicated data structure, and selected using a probabilistic diversification policy.

Solution representation and neighbourhood

The space-time graph of a TDPP instance, denoted G * , represents all the activity routes allowed at each point in time. Its nodes correspond to the pairings of sites and time buckets (L × T ) and its arcs link the nodes consistently with the network topology, schedule and lead time constraints. G * is the union of 3 subgraphs G h , G f and G r that represent the supply links, the return links and the repair links, respectively. Any planned action on n items (i.e., the assignment of value n to an action variable of the MIP that maps to a route) may be viewed as a labelling of an arc of G * with quantity n. Therefore, any plan (i.e., any set of actions) determines itself a particular labelling of G * with quantities.

Since every action on n items splits into n unitary actions, every plan is itself defined by a multiset of unitary actions.

A plan may also be defined as a set of sequences by clustering these actions into sequences consistently with G * (i.e., into chains of unit actions over G * ). BIS adopts this view to construct a plan by assembling sequences iteratively. At each iteration, it searches for a sequence amongst the set of feasible sequences and adds it to the current plan. This addition operation boils down to a set union operation between the multiset of actions defining the plan and the set of actions defining the sequence. Formally, the neighbourhood N of a plan P is the set N (P ) = {P ∪ S|S ∈ SEQ} where SEQ denotes the set of sequences consistent with P .

Algorithm 1 describes the global structure of BIS. BIS relies on Algorithm 2 for constructing and selecting a sequence at each step which we present in Section 3.2. By design, BIS cannot remove sequences to "undo" a plan. Every choice of sequence is therefore critical in the construction process and we choose to adopt a best improvement sequence selection approach. To avoid local optima, we introduce stochasticity in Algorithm 2 and we restart the search for a plan a predefined number of times. This process is inspired from Variable Neighbourhood Search (VNS) (?) which increases the size of the neighbourhood at each restart of the algorithm. It is also inspired by Simulated Annealing which, contrary to our approach, evolves from a large to a small neighbourhood (?). Another common issue with best improvement selection is the computational cost incurred by the evaluation of all neighbours. We make use of a specific data structure to this effect which is presented in Sections 3.3 and 3.4.

Algorithm 1 BIS Input: an initial plan P 0 , a number of restarts n max , an initial probability α 0 , a control parameter v Output: a plan 1: P * ← P 0 2: α ← α 0 3: n ← 1 4: while n ≤ n max do 5:

P ← P 0 ; 6:
Build sequence seq using Algorithm 2 with parameters P and α; end if

14: α ← 1 -((1 -v) n × (1 -α 0 )) 15:
n ← n + 1 16: end while 17: return P *

Sequence selection

Every sequence of SEQ is a tuple of unitary actions that corresponds to a path in G * . We shall denote by X l,l ,t,t a unit action of type X that starts at t from site l and ends at t on site l . Specifically, B l,l ,t,t ∈ G f (respectively, R l,l,t,t ∈ G r , A l,l ,t,t ∈ G h ) will denote a return (resp., repair, supply) action. We shall also use subscript symbol * to indicate any particular location or time bucket. For instance, A l, * ,t, * will denote any supply action starting from site l at t. We list below the chaining rules that prevail when constructing a sequence of SEQ:

(1) An action must start from the end site of the previous action, if any. (2) An action must not start before the end time bucket of the previous action, if any. (3) An item must be available on the site of an action when it starts. (4) The on-hand inventory on the site of the action initiating the sequence must be sufficient not to cancel subsequent unitary actions that are already planned.

Algorithm 2 describes the selection and construction of a sequence of unit actions. It is based on two functions, denoted gainC and gainI, which compute the improvement that a unit action could bring to a plan (see Section 3.3) and a variable corresponding to the best possible action following a given action (next(y) is the best action following action y). Algorithm 2 uses probability α to introduce stochasticity when selecting an improving sequence. Every time we select a unit action to extend the sequence, we might select another improving action than the best one or end the sequence with a probability equals to α. Probability α evolves at each restart in BIS following an arithmetico-geometric series. Given α 0 the initial probability and v a control parameter, probability α n at the n-th restart is defined as follows:

α n = 1 -((1 -v) n × (1 -α 0 )) Parameter v ranges in [0, 1]
and is used to control the range of values for α. Based on experiments, we deduced that α 0 should be set between 0 and 0.15 to ensure a good balance between intensification and diversification. Depending on the number of restarts, v is adjusted to make α range from 0 to 0.15.

Gain functions

We present here the definition of functions gainI and gainC and the set of variables they rely upon. Boolean variable a h l,t (resp. a f l,t ) denotes the possibility to send an healthy (resp. faulty) item from site l at time bucket t. This action is possible only if items are available at t and if it does not cancel another action planned later on. Note that in case of healthy items, sending an item might cause a backorder on a subsequent time bucket but must not cause a backorder on the current time bucket to remain consistent with the TDPP constraints.

∀l ∈ L, t ∈ T, a h l,t =      1 if s h l,t > 0 and ∀t ∈]t, T max], l ∈L, t >t m h l,l ,t ,t > 0 → s h l,t ≥ 1 0 otherwise ∀l ∈ L, t ∈ T, a f l,t =      1 if s f l,t > 0 and ∀t ∈]t, T max], l ∈L, t >t m f l,l ,t ,t > 0 → s f l,t ≥ 1 0 otherwise
We also define variables that represent the number of backorders generated or avoided by applying a supply action and its impact on storage for both the source and target sites of the action. ∀l ∈ L, t ∈ T, t > t, //number of backorders avoided -target site ddStr(l, t, t ) = |{t |t > t ≥ t and b l,t > 0}| //number of backorders generated -source site dd(l, t, t ) = |{t |t > t ≥ t and s h l,t = 0}| //impact on storage -target site dhs(l, t, t ) = |{t |t > t ≥ t and b l,t = 0}| //impact on storage -source site dhsStr(l, t, t ) = |{t |t > t ≥ t and s h l,t > 0}| Based on these variables, functions gainC and gainI compute the maximum gain a unitary action can bring to the current plan. gainC(x) computes the improvement that unitary action x can bring to a sequence. In other words, when building a sequence, gainC will help to decide which action should be chosen to continue the sequence, if any. This function is computed recursively and takes into account the improvement that could be brought by an action following the one we are evaluating.

gainC(A l,l ,t,t )= max( ddStr(l , t , T max + 1) * µ b l * ω b -µ m h l,l * ω m hf -dhs(l , t , T max + 1) * µ s h l * ω s , max({gainC(A l , * ,t , * ) -µ m h l,l * ω m hf -dhs(l , t , t ) * µ s h l * ω s +ddStr(l , t , t ) * µ b l * ω b |t ≥ t , b l ,t = 0})) gainC(R l,l,t,t )= max( ddStr(l, t , T max + 1) * µ b l * ω b -µ m r l * ω m r -dhs(l, t , T max + 1) * µ s h l * ω s , max({gainC(A l, * ,t , * ) -µ m r l * ω m r -dhs(l, t , t ) * µ s h l * ω s +ddStr(l, t , t ) * µ b l * ω b |t ≥ t , b l,t = 0})) gainC(B l,l ,t,t )= max( -µ m f l,l * ω m hf -(T max -t ) * µ s f l * ω s , max({gainC(B l , * ,t , * ) -µ m f l,l * ω m hf -(t -t ) * µ s f l * ω s |t ≥ t }) , max({gainC(R l ,l ,t , * ) -µ m f l,l * ω m hf -(t -t ) * µ s f l * ω s |t ≥ t }))
Note that to avoid multiple computation of the same action, we initialize variable next(x) when computing gainC. This variable returns the best action that could follow x or N U LL if no action could improve the sequence after applying x. gainI(x) defines the maximum gain that a sequence initialised with unitary action x could bring to the current solution. This function differs from gainC as gainC only refers to actions included in a sequence and not to actions initialising a sequence. Note that gainI assigns a negative value to actions which are inconsistent with the current plan so that they will never be selected to build a sequence.

gainI(A l,l ,t,t ) =      -1 if a h l,t = 0 gainC(A l,l ,t,t ) + dhsStr(l, t, T max + 1) * µ s h l * ω s -dd(l, t, T max + 1) * µ b l * ω b else gainI(R l,l,t,t ) = -1 if a f l,t = 0 gainC(R l,l,t,t ) + (T max -t + 1) * µ s f l * ω s else gainI(B l,l ,t,t ) = -1 if a f l,t = 0 gainC(B l,l ,t,t ) + (T max -t + 1) * µ s f l * ω s else

Efficient data structure

The evaluation of gainC being computationally expensive, it is important to avoid unnecessary evaluations. Adding a sequence to a plan updates variables and thus could impact gains associated with unitary actions. However, it is not necessary to recompute the gain for each unitary action but only for the ones impacted by the sequence.

We use a matrix M gainC that permits to directly obtain the value of gainC for a given sequence. Of course, the initialisation of this matrix has a cost but is very efficient afterwards. Algorithm 3 describes how matrix M gainC is updated when a sequence is applied to a plan. Note that to ease the understanding of the algorithm we do not detail the update of the next value but every time we update a M gainC value we also update its corresponding next action. Once M gainC values are up to date, it is necessary to update M gainI which is the associated matrix to gainI as M gainC is associated to gainC. This update is simpler. It has to be updated for all actions that are initiated from a site whose location appears in the last applied sequence.

It also has to be updated for all actions whose M gainC have been updated.

Algorithm 3 Update of M gainC

Input: a plan P , a sequence seq of size n 1: T oU p ← ∅ A set to store locations 2: forall X l,l ,t,t ∈ seq 3: Remove Y l,l ,t,t from m 15: end while This section presents experiments carried out to evaluate and compare BIS with the MIP model. Note that, due to space restrictions, we only report experiments on a subset of the instances that have been tested.

T oU p ← T oU p ∪ {l} ∪ {l } 4: end forall 5: m ← X * , * , * , * 6: while m = ∅ do 7: Y l,l ,t,t ← argmax X l ,l ,t ,t ∈m t reverse chronological 8: if l ∈ T oU p then 9: if gainC(Y l,l ,t,t ) = M gainC(Y l,l ,t,

Instances

Experiments are carried out on a set of pseudo-random instances that share the same supply chain network topology. This topology follows the 3-level tree structure presented in Figure 1 and consists of a single distribution centre (DC) which also acts as a repair centre, 33 intermediate hubs, and 66 peripheral stores. Schedules and lead times for supply, return and repair routes are also identical for all instances and so is the demand frequency. Instances also share the same unit cost values: a demand not met in time (a backorder) costs 1000, a repair costs 100 and storing an item costs 1 in the DC and 10 elsewhere. All these data have been extracted from a real-life problem instance developed for managing field service operations in the telecommunications sector. Note that in this instance, transfer costs are not taken into consideration and we thus set the unit transfer cost to 0.

We assume that the initial plan of actions is empty. However, we introduce variability in our instances by varying the initial volume of healthy items and their distribution across the sites. We use two configuration schemes to this effect. First, the initial number of healthy items is set as a proportion of the number of demands forecast over the time horizon and each instance is generated using one of the following ratios: 100% (category High), 50% (category Med) or 0% (category Low). Second, the initial volume of healthy items is either completely allocated to the DC (category DC), either randomly allocated to the peripheral stores (category Sites), or evenly distributed between the DC and the stores (category Mix). We thus get seven classes of instances since the initial distribution of healthy items is irrelevant for category Low (no healthy item is available).

Results

All computational experiments are carried out on a computer with an Intel Core i5-3380M processor (2.90GHz and 8GB of RAM). BIS is programmed in C++ and compiled using g++ for this architecture while the MIP model is solved using CPLEX 12.6. The cutoff time limit is set to 1 hour for MIP and 100 iterations for BIS.

Table 2 presents the results obtained by running MIP and BIS over the 7 classes of instances for all possible 0/1 weightings of the fitness function. For each instance and each weighting, we ran BIS 10 times and obtained the same best fitness value (i.e., the standard deviation is null). Each row corresponds to one instance of a specific classweighting pair. The first two columns identify each class of instances based on its initial inventory level (category High, Med or Low) and inventory distribution (category DC, Mix or Sites). The third column indicates the values used for the triplet of weights ω b , ω m r , ω s . We recall that a weight set to 0 cancels the corresponding cost component in the fitness function. Note that we omit transport weight ω m hf since the unit cost is set to 0 in the studied instances thus making it ineffective.

The remaining columns provide, respectively, the best bound returned by MIP (column MIP -Fitness), the run time of MIP in milliseconds (column MIP -Time), the best fitness score returned by BIS (column BIS -Fitness), and the average run time of BIS in milliseconds over the 10 runs (column BIS -Time). A dash symbol '-' indicates that MIP did not find a solution before the cutoff time limit. Values in bold indicate cases where the fitness score obtained with BIS is lower than the fitness score obtained with MIP.

Analysis

First, we point out that, in all cases, BIS always reaches the best fitness score found by MIP. In some cases, MIP cannot find the optimal solution and returns an upper bound or no bound at all. In 4 of these cases, BIS returns a solution that improves this bound. Note that when the only activated weight is repair weight ω m r , the fitness value is equal to 0, as expected. As for run time, BIS is generally faster than MIP except for category High and Sites. Besides, MIP reaches its time limit in 18 cases (1 hour) whereas BIS always returns a very good solution in less than 1 minute. Overall, these results confirm the scalability of BIS and its ability to attain optimal or nearoptimal solutions in a reasonable time.

5 Towards Distribution Policies Different weightings of the fitness function give rise to different behaviours in the way items get distributed over time in the supply chain. Figure 2 illustrates the temporal evolution of various supply chain metrics for two different weightings.

Weighting 1, 0, 1 aims at minimising both backordering and storage. As expected, all demands are met in time.

We also notice that all faulty items are sent back to the DC and repaired to avoid storage costs. Healthy items are kept in the DC as long as possible since storing items in other sites is more expensive. Thus, this weighting can be seen as a solve demands just-in-time and repair everything management policy.

Weighting 1, 1, 0 aims at minimising both backordering and repair. As expected, all demands are met in time.

The activation of repair objective implies that faulty parts are repaired only if needed to satisfy a demand later on. The deactivation of storage cost implies that items can be sent to sites at any time as it will not impact the fitness function. Thus, this weighting may be viewed as a solve demands and repair as less as possible management policy.

Conclusion

This article presented BIS, a metaheuristic based on sequences of unit actions to solve tactical distribution planning problems in closed-loop supply chains. We detailed the metaheuristic and the data structure used to limit the computational time. We also proposed an experimental analysis that shows the performances of BIS. Finally, we discussed the impact of the weights of the fitness function and the possibility of implementing different management policies.

As future work, we plan to investigate how to enforce distribution policies specified using indicators based on appropriate weightings of the fitness function. We also plan to investigate the robustness of our approach and to evaluate how it deals with uncertainties.

  7:while seq = seq ∅ do seq ∅ is the empty sequence 8:P ← P ∪ seq 9:Build sequence seq using Algorithm 2 with parameters P and α; 10: end while 11: if c(P ) ≤ c(P * ) then c is the cost function 12: P * ← P 13:

Algorithm 2

 2 Construction of a sequence Input: a plan P , a probability α Output: a sequence seq 1: seq ← seq ∅ 2: if max(gainI(X * , * , * , * ))

  (a) High, Mix, 1, 0, 1 , F itness = 33423. (b) High, Mix, 1, 1, 0 , F itness = 100.

Fig. 2 .

 2 Fig. 2. Impact of two different weightings

Table 1 .

 1 Constants and variables of a TDPP instance

		Constants
	demand forecast	d

  t ) then

	10:	Update M gainC(Y l,l ,t,t )
	11:	T oU p ← T oU p ∪ {l}
	12:	end if
	13:	end if
	14:

Table 2 .

 2 Comparison between MIP and BIS

			Weights	MIP Fitness	Time	BIS Fitness	Time
			<1,0,0>	0	57000	0 22002
			<0,1,0>	-	-	0 42343
		DC	<0,0,1> <0,1,1>	99990 101574	20500 23100	99990 12129 101574 8029
			<1,1,0>	0	32480	0 22126
			<1,0,1>	112200	-	112200 28040
			<1,1,1>	113784	-	113784 25625
			<1,0,0>	0	26220	0 14726
			<0,1,0>	0	10780	0	3986
	High	Mix	<0,0,1> <0,1,1> <1,1,0>	133862 135446 0	2980 2840 29500	133862 135446 0 14340 6979 4133
			<1,0,1>	143562	-	143562 19140
			<1,1,1>	145146	-	145146 16473
			<1,0,0>	27000	2730	27000	6922
			<0,1,0>	0	2070	0	4032
		Sites	<0,0,1> <0,1,1> <1,1,0>	256128 257712 35600	2030 2030 3430	256128 257712 35600	6282 3952 7171
			<1,0,1>	285983	3510	285983	9482
			<1,1,1>	295909	3930	295909	7805
			<1,0,0>	0	38000	0 22094
			<0,1,0>	-	-	0	3950
		DC	<0,0,1> <0,1,1>	80751 82335	35410 31500	80751 11040 82335 8250
			<1,1,0>	36300	-	36300 22150
			<1,0,1>	92961	-	92961 28457
			<1,1,1>	129756	-	129756 25190
			<1,0,0>	0	25680	0 18567
			<0,1,0>	0 120500	0	3985
	Med	Mix	<0,0,1> <0,1,1> <1,1,0>	88669 90253 36300	18250 14240 -	88669 90253 36300 18771 8497 5437
			<1,0,1>	100339	-	100339 23701
			<1,1,1>	-	-	137134 21512
			<1,0,0>	93000	11730	93000 14760
			<0,1,0>	0	4480	0	3984
		Sites	<0,0,1> <0,1,1> <1,1,0>	114648 116232 129300	6051 3900 -	114648 116232 129300 14068 6273 4338
			<1,0,1>	217263	19240	217263 17083
			<1,1,1>	254058	-	254058 16292
			<1,0,0>	11550000	-	11550000	9441
			<0,1,0>	0	2000	0	3993
	Low	-	<0,0,1> <0,1,1> <1,1,0>	66198 67782 11603200	8410 8140 -11596200 66198 67782	6536 4012 9649
			<1,0,1>	11623128	-	11623128 10388
			<1,1,1>	11669526	-	11669526 10233


Rosalee Wolfe

John C Mcdonald
email: jmcdonald@cs.depaul.edu

Eleni Efthimiou
email: eleni_e@athenarc.gr

Davy Van Landuyt
email: davy.van.landuyt@eud.eu

Tina Sioen
email: tina.sioen@eud.eu

Sarah Ebling
email: ebling@cl.uzh.ch

Thomas Hanke
email: thomas.hanke@uni-hamburg.de

The myth of signing avatars

Development of automatic translation between signed and spoken languages has lagged behind the development of automatic translation between spoken languages, but it is a common misperception that extending machine translation techniques to include signed languages should be a straightforward process. A contributing factor is the lack of an acceptable method for displaying sign language apart from interpreters on video. This position paper examines the challenges of displaying a signed language as a target in automatic translation, analyses the underlying causes and suggests strategies to develop display technologies that are acceptable to sign language communities.

Introduction

Deaf sign language users around the world face continual challenges in daily interaction with hearing, non-signing populations. The gold standard for translating between signed and spoken languages1 are certified sign language interpreters who are essential to facilitating communication for education, healthcare, and legal consultation among other situations. However, many transactions in daily living consist of short conversations over a hotel desk, at a store counter or in an office foyer. These interactions are so limited in scope and duration that hiring a qualified interpreter would be prohibitively expensive or quite unnecessary, or even impossible because in most countries there is a shortage of qualified interpreters. In such situations, an automatic translation system between spoken and signed language would ease communication barriers and improve inclusivity. For technology of this sort to be useful, it must display sign language in a way that is acceptable to members of the sign language community.

To be effective, an automated translation system or machine translation system must be able to produce legible, grammatically, and phonologically and phonetically correct, acceptable utterances in a desired target language with minimal or no human involvement. Researchers have made significant progress in translating between high-resource languages that have a written form and some have suggested that automatic translation has achieved human parity in some domains [START_REF] Hassan | Achieving Human Parity on Automatic Chinese to English News Translation[END_REF].

Progress in translating between signed and spoken languages has lagged significantly in comparison. Traditionally, this task has been conceived as one of text-to-text translation, involving written representations of sign languages. Since sign languages have no widely accepted written form, an additional required step in going from a spoken language to a sign language is that of displaying signed languages in their natural moving form, in the visual modality [START_REF] Ebling | Automatic Translation from German to Synthesized Swiss German Sign Language[END_REF]. This position paper examines the challenges of displaying signed language as a target in automatic translation, analyses the underlying impediments and suggests strategies to develop display technologies that are acceptable to deaf sign language users.

Background

Sign languages are distinct from their surrounding spoken languages. For example, in France, many deaf persons have Langue des Signes Française (LSF), not French, as their preferred language. Since French is a second language to them, even its written form poses a barrier. Many researchers have noted that written language poses barriers to members of the Deaf communities [START_REF] Traxler | The Stanford achievement test: National norming and performance standards for deaf and hard-of-hearing students[END_REF][START_REF] Gutjahr | Lesekompetenz Gehörloser: Ein Forschungsüberblick[END_REF][START_REF] Hennies | Lesekompetenz gehörloser und schwerhöriger SchülerInnen Ein Beitrag zur empirischen Bildungsforschung in der Hörgeschädigtenpädagogik[END_REF][START_REF] Konrad | Die lexikalische Struktur der Deutschen Gebärdensprache im Spiegel empirischer Fachgebärdenlexikographie[END_REF].

Deaf sign language users consider themselves members of a minority group, with a distinct language, culture, and shared experiences, rather than as simply persons with a disability [START_REF] De Meulder | Sign language communities[END_REF]. They continually struggle with the reality that policy makers in governmental departments, educational institutions and health care agencies consist primarily of hearing people who are not familiar with the values, goals and concerns of sign language communities [START_REF] Branson | Nationalism and the linguistic rights of Deaf communities: Linguistic imperialism and the recognition and development of sign languages[END_REF]. As a result, there is a history of disenfranchisement which adds a barrier of distrust to the barrier of language that exists between deaf and hearing communities. At present, current technology claiming to translate between spoken and signed languages are not viewed favourably by sign language communities. Rather, the technology is often perceived as a ploy to replace human interpreters (World Federation of the Deaf, 2018; European Union of the Deaf, 2018), or even as cultural appropriation by predominantly hearing researchers, who do not always have linguistic knowledge of these languages, and often have little connection with sign language communities [START_REF] Erard | Why sign-language gloves don't help deaf people[END_REF].

Linguists have noted that as long as avatars are only capable of artificial and flawed language, they are very likely to be counterproductive. (Austrian Association of Applied Linguistics, 2019).

This scepticism and often downright hostility towards automatic translation systems is exacerbated by the generally poor quality of their sign language [START_REF] Sayers | The dawn of the human-machine era: A forecast of new and emerging language technologies[END_REF]. To date these have exhibited robotic movement and are mostly unable to reproduce all of the multimodal articulation mechanisms necessary to be legible. They are comparable to early speech synthesis systems which featured robotic-sounding voices that chained words together with little regard to coarticulation and no attention to prosody.

Quality of the target language

Just as with text-to-text translation applications, users will judge the quality of the application by the quality of its output to the target language. The same is true when the target language is signed. Poor-quality signing is difficult to understand, just as poor-quality speech synthesis or egregious misspellings are difficult to understand. It undermines the viewer's confidence in the quality of the translation. Worse, poor quality signing alienates the sign language community. Being forced to struggle with the poor signing is no better than being forced to lip read or use captions in the second language. This is simply more evidence that reconfirms a continuing disenfranchisement. For these reasons, quality of the ultimate signed language display must be given highest priority in a spoken to signed translation system. The motion should be indistinguishable from that of a human signing the same utterance. This visual Turing Test should be the ultimate goal of any sign language display.

Sign language in automatic translation services

Among the challenges to acceptable sign language display as part of an automatic translation system, three issues stand out. These are 1) the difference of modalities between signed and spoken languages 2) the representation used to characterize sign languages and 3) the development of the technology required to display sign languages.

Modality

The modality of sign languages differs markedly from that of spoken languages, which utilize the vocal apparatus for production, and hearing for reception. Spoken languages use visible communicative behaviours like gestures as well, but listeners can comprehend audio-only sources. In contrast, signed languages use only visible actions for production, and vision for reception. Whereas speech utilizes a single vibrating column of air for producing utterances, signed languages use the configuration and movement of multiple body parts concurrently, including hands with all the fingers, head, face, eyes, and torso.

All sign languages have linguistic processes that are not linearly ordered. For example, in American Sign Language (ASL) the appearance of pursed lips in conjunction with the sign SMOOTH intensifies the degree of smoothness. In signed language, layers of processes ranging from the phonological to the prosodic can co-occur [START_REF] Crasborn | Nonmanual structures in sign language[END_REF]. Co-occurrence is a more general term than synchronized or simultaneous, as co-occurring events do not necessarily start or end at the same time, but they overlap in their duration.

Although there are many discrete lexical items in signed languages, much information is conveyed through forms with infinite variability and depiction, unlike fixed dictionary signs. A case in point are classifiers, which represent general categories or "classes" of objects. They can be used to describe the size and shape of an object, and they can also represent how an object moves or is utilized. Through the use of classifiers, a signer can describe a scenario with few discrete lexical items. The signer creates an image in space. This is not simply an informal gesture as there are well-documented linguistic rules governing classifier usage [START_REF] Lepic | A construction morphology approach to sign language analysis[END_REF]. These are evocative, not necessarily iconic, and are extremely powerful. In a story about a motorcycle ride [START_REF] Dudis | Body partitioning and real-space blends[END_REF], a signer can use an instrument classifier to indicate that the rider is revving the engine and a vehicle classifier to show the rider driving away on a hilly highway (Figure 1).

The motorcyclist driving up a hill

Figure 1. Classifier usage [START_REF] Dudis | Body partitioning and real-space blends[END_REF].

The presence of multiple articulators that can co-occur and classifier usage are examples of the stark difference between signed and spoken languages. For these reasons, it is essential to avoid the trap of casting the problem of signed/spoken translation as a case of simply retrieving lexical items or phrasal units from a dictionary and concatenating them.

Representation

The second of the three challenges is the question of representation. Languages commonly processed by automatic translation systems have a written form. Signed languages do not. They are languages and cultures that have been preserved and transmitted from generation to generation by "hand to eye to hand". Determining a standard transcription/annotation system that can capture all of the linguistic information contained in a signed message is still an open question. A linear stream of glosses, even with accompanying superscript strings to indicate prosody and syntax [START_REF] Adamo-Villani | ASL-Pro: American sign language animation with prosodic elements[END_REF], does not contain the entire semantic content of a signed utterance, in particular the depicting and spatialized linguistic structures. This is not analogous to the difference between reading printed text on a page and witnessing an actor perform the text. Less information is captured in a gloss stream than is conveyed in written text. A hearing person may argue that not all features of articulation are captured in a printed sentence of a spoken language, such as speed of delivery, but in languages where adverbs are not necessarily expressed as separate lexical items, the lack of a speed indication is losing semantic information, not just performance information.

Sign language display

The third challenge is the display of a sign language when it is the target. The most commonly used strategy for this purpose is avatar technology. Three-dimensional avatars have the advantages of consistency and flexibility. When recording a human signer with traditional video, special care must be taken to ensure consistency of the studio set up and the appearance of the signer between recording sessions. This requires additional time and money. When using an avatar, the lighting and camera set up can be fixed; the clothing can be chosen by the viewer as can the hair and makeup. No additional resources are required to ensure consistency.

In addition, avatars have the advantage of flexibility through the use of animation techniques. They can display co-occurring linguistic processes. Proper application of coarticulation can provide smooth transitions and can inflect signs according to syntactic rules. These properties are necessary for a translation system to produce novel utterances.

Avatars also have flexibility in appearance. They can be easily adapted to look like the shape of the original speaker/source, like a presenter or a cartoon character or a movie character. This flexibility in appearance can also anonymize a signer, so that the signer's identity will remain hidden.

Another advantage of this type of anonymization of content is that it covers one of the key properties of written language, which is inherently more anonymous than a live performance that is spoken or signed. With an anonymously presented avatar, content can be communicated without knowing the person who expressed it.

The promise and mythology of avatars

Given that there is a century's worth of development in animation, and nearly half that supporting video game technology, it would be tempting to dismiss the question of using avatars to display sign languages as a solved problem. However, a closer analysis shows that there are still significant challenges yet to be fully addressed.

Animation, the precursor to avatar technology, is powerfully communicative. Animation artists abstract and emphasize the salient features of a character for greater audience appeal and engagement. Simplification of a character's appearance is vital to maximizing emotional impact. This is the reason that the eyes of Disney cartoon characters are twice the size of those of a human and spaced more widely apart.

However, the requirements for sign language display are different from those for portraying cartoon characters. Beyond communicative power, display of sign language requires precision. It must adhere more closely to physical reality. For example, the hands of animation characters such as Mickey Mouse or Homer Simpson have only three fingers. For a hearing audience, this is perfectly acceptable, but three fingers aren't enough to distinguish between the fingerspelled letter W and the number 4 (Figure 2). Another consideration is that while character animation effectively uses the face and body to express emotion, the facial animation is typically at a lower quality than what would be required to portray a sign language legibly. Several ground-breaking animations have received attention and praise from sign language communities [START_REF] Stewart | The Forest -A story in ASL[END_REF]Fumdación Fesord CV, 2007). These were manually created by artists with the assistance of motion capture. The artists create underlying natural processes of coordinated muscle action, coarticulation at a biomechanical level and ambient movement. While creating the animation the artists are continually checking whether the animation draft effectively communicates the intended message and editing the draft when there are flaws. However, animations are intended for playback only and are not extensible without manual intervention. Once completed, they are archived, and without additional manual editing cannot be utilized for generating new utterances. In short, animations are not created in real time and are not interactive.

In contrast, video game characters move in response to player input in real time and are highly interactive. Thus, using video game technology might seem like an expedient approach to sign language display for a translation system. However, many game players continue to comment on the poor quality of the game characters. This is due to the effect of the uncanny valley [START_REF] Tinwell | The uncanny valley in games and animation[END_REF]. If a character appears more human-like, viewers expect the character to behave in a more human-like manner. But because the character's motion cannot be refined and edited by human animators before it is displayed, the results are unsatisfying. As explained by a professional animator [START_REF] Trentskiroonie | Let's talk about Animation Quality! Récupéré sur reddit[END_REF], For something like film or television, I could create a kickass animation of a monster jumping off a building and landing on the street below, but to do the same thing in a game, the movement has to be broken up into separate parts. This is because he probably won't do the exact same action every time. There may be buildings of different heights in the game, so I can't hard-code the height of the jump into the animation. I have to create an initial jump animation, then an idle hang-time animation to play while he's in the air, and then a landing animation. The programmer then strings the jump, hang-time, and landing together and decides the timing and trajectory of the hang-time part procedurally. ... That takes artistic control away from the animator and can result in some fugly animation.

Unfortunately, a "fugly" motion on a sign language avatar can destroy the legibility and even the meaning of the message, thus making the avatar bothersome or even useless for a deaf sign language user. Finally, the representation of signed languages through avatars will have an effect on the hearing perception of these minority languages. Hearing viewers should not be confronted with "fugly" signed texts and be misled into thinking that it is real sign language in all its beauty and richness.

The analysis of the requirements for a sign language avatar shows that it must have the expressivity of manual animation but the flexibility of a video game character. These two requirements are in conflict. It is still an open question as to how to reconcile these goals.

Moving forward

The establishment of a set of best practices would be a substantive step toward the development of better sign language displays in automatic translation systems, but it cannot happen without a mutual collaboration with sign language stakeholders [START_REF] Tupi | Sign language rights in the framework of the Council of Europe and its member states. Sign language rights in the framework of the Council of Europe and its member states[END_REF]. Deaf leadership is vital for the establishment of a validated methodology for user evaluation of avatar technology. Once created and reviewed, the methodology should be made publicly available to all researchers working in this area. Currently in Austria, there is a small research project aiming to create a Best Practice Protocol for the use of signing avatars [START_REF] Krausneker | Avatars and sign languages: Developing a best practice protocol on quality in accessibility[END_REF]. This is consistent with the World Federation of the Deaf's position paper on Sign Language Work (World Federation of the Deaf, 2014).

The WFD considers exclusion of Deaf Community and their national organizations from sign language work ... a violation of the linguistic human rights of deaf people. Decisions regarding sign languages should always remain within the linguistic community, in this case deaf people.

Best practice for reviewing research papers would include an awareness of the multidisciplinary qualification required. It is not enough to know about machine translation. Reviewers must also be aware of sign language linguistics, the deaf experience and previous work in sign language machine translation.

When reporting on an advance in sign language avatar technology, researchers should include a sample of the sign language produced by the technique outlined in a paper. Since the sample would necessarily contain motion, it could either take the form of a media file in a commonly available format such as MPEG-4, or a web application available online. Conference organizers and journal editors need to collaborate with academic and professional organizations to archive media accompanying research papers.

Conclusion

"Together, we are strong." --Lutz König, Hamburg, 14 November 2017 Together, machine translation (MT) researchers, sign language linguists and the deaf sign language community have the potential to form powerful partnerships to educate policy makers [START_REF] Bragg | Sign language recognition, generation, and translation: An interdisciplinary perspective[END_REF]. Ideally, Deaf professionals should be educated, supported, and actively sought to include in sign language relevant research projects.

To hearing researchers: Get to know members of sign language communities and learn about deaf culture.

• Take a class in the national sign language of your country. You already know several spoken languages --why not discover an entirely new world? Or if you don't feel you have time,

• Go to a deaf event --see a play in sign language, go to a deaf trade show.

• When writing grant proposals that include work relevant for sign languages, include the local and/or national deaf community. Most countries in the world have a National Association of the Deaf. Include budget for interpreters.

• Listen. Just because an idea or a result is incredibly appealing to an MT researcher does not mean that it will be useful or welcomed within the sign language community. Take feedback seriously and act on it.

Through exchange of ideas and concerns, the sign language community can inform MT researchers about their priorities, and MT researchers can clarify the capabilities and limitations of today's technologies. A clear understanding of priorities, expectations, potentials, and limitations will move the state of the art closer to realization of better inclusivity.

Figure 2 .

 2 Figure 2. The difference between the letter W and the digit 4 would disappear in a three-fingered character.

The term spoken language refers to any language that is not signed, whether represented as speech or as text.Proceedings of the 18th Biennial Machine Translation Summit, Virtual USA, August 16 -20,

1st International Workshop on Automatic Translation for Signed and Spoken Languages

Proceedings of the 18th Biennial Machine Translation Summit, Virtual USA, August16 -20, 2021 1st International Workshop on Automatic Translation for Signed and Spoken Languages

Acknowledgments

This work is supported in part by the EASIER (Intelligent Automatic Sign Language Translation) Project. EASIER has received funding from the European Union's Horizon 2020 research and innovation programme, grant agreement n° 101016982.