Visual analysis of the collection : cross-examination and sense-making

Section four, introduces a selection of visualisations, designed as tools for cross-examination and questioning.

The section is organised as a sort of vis à vis dialogue between a common sense question or assertion (eg. "recent transformations are better understood than old ones") and a visual answer. The whole section should be understood as illustrative of a method, rather than as conclusive on this or that theory, hypothesis or scientific position.

Visual analysis of the collection : cross-examination and sensemaking

In a work entitled De Docta Ignorantia (On Learned Ignorance) and published in 1440 [START_REF] Aigner | Visualization of time-oriented data[END_REF], Nicolas Krebs (Nicolaus Cusanus) describes the inquiry process as an intellectual, cognitive process based on comparative relations that analysts draw between what is certain, and what is uncertain. Among the practical applications of Krebs's vision is the construct of universal concepts through a systematic comparison of individuals.

Infovis (Information visualisation) and its outgrowth visual analytics are scientific fields that strongly rely on this same vision: gaining insight into a phenomenon through an in-depth cross-examination of massive data and information sets. Within these fields, a large variety of visualisation methods have been introduced (before or after the computer age) that are based on this capacity of creation of comparative relations. Although not in today's mainstream research, visual solutions that could help analysts better compare what is considered as certain, with what is understood as uncertain, can be particularly fruitful in historical sciences.

Infovis is about visual thinking, and one of the particularities of visual thinking is its non-verbal character, its independence from ethnic languages. According to Kobrzycki the capacity of perception (and of abstraction) of humans is primarily organised in three non-verbal levels (silent, un-speakable levels: happenings, their nervous impacts and reactions such as feelings). Only then, as a fourth level, does language intervene, as a way to picture reality for ourselves, and to describe it for others. The way we "understand" on the non-verbal level differs from what we can "think" on the verbal level -because we then have to band reality to the structure of the language we use. [START_REF] Bertin | Semiology of Graphics: Diagrams, Networks, Maps[END_REF] Building a visualisation is, briefly said, trying to capitalise on our natural ability to use non-verbal thinking (not to say that there should be no verbal expression in a visualisation, naturally -a visualisation reflects a structure, and relations, explicated through comments, legends, etc.). Supporting the human capacity of non-verbal thinking implies designing adequate, efficient, distortion-free visualisations -and this is a challenge by itself.

As demonstrated by some major authors in the infovis community -E.R Tufte, R. Spence, M. Friendly, W. Kienreich (etc.) -different types of data require different visualisations -different problems, different questions necessitate distinct visual solutions. It is important to understand that an ineptly designed visualisation will not allow us to discover unsaid relations within the data [START_REF]On Learned Ignorance (De Docta Ignorantia)[END_REF]. When carelessly designed, or intentionally deceptive, a visualisation can even lead to faulty conclusions.

The first role of design in data/information visualisation is to improve cognition whilst providing certain aesthetic consistency. E.R Tufte [START_REF] Dudek | From artefact representation to information visualisation: genesis of informative modelling[END_REF] verbalised a set of "rules" that speak for themselves:

• Graphical excellence begins with telling the truth about the data,

•

Graphics must not quote data out of context,

• Graphics should draw the viewer's attention to the sense and substance of the data, not to something else,

•

Decorative elements lacking the content should be avoided, Note 2. … There is a tremendous difference between "thinking" in verbal terms, and "contemplating," inwardly silent, on nonverbal levels, and then searching for the proper structure of language to fit the supposedly discovered structure of the silent processes that modern science tries to find. If we "think" verbally, we act as biased observers and project onto the silent levels the structure of the language we use, so remaining in our rut of old orientations which make keen, unbiased observations ("perceptions"?) and creative work well-nigh impossible. In contrast, when we "think" without words, or in pictures or visualisations (which involve structure and, therefore, relations), we may discover new aspects and relations on silent levels, and so may formulate important theoretical results in the general search for a similarity of structure between the two levels, silent and verbal. Practically all important advances are made in that way. … cf. KOBRZYCKI A., The role of language in the perceptual process, [ The representation of numbers, as physically measured on the surface of the graphics, should be directly proportional to the numerical quantities represented,

• Greys, as opposed to colours, have a natural visual hierarchy,

• Graphical elegance is often found in simplicity of design and complexity of data.

Visualisations as we have defined them are tools meant to support analysts in their reasoning tasks. But the complexity of the tasks, the public targeted, the very objective of the visualisations can vary. As solutions to organise large collections of data and allow meaningful comparisons between different parts of data, visualisations may rather be intended at telling a story [START_REF] Dudek | 3D as a content, 3D as a metaphor[END_REF] (story visualisations -more of a teaching or communication tool than of an analysis tool) or be intended at cross examinations, in-depth answers to specific expert questions (data visualisation, infovis, visual analytics). This duality of purposes of graphics was already discussed in Bertin's Graphic Semiology -graphics used both for communication (presenting knowns) and as an exploratory tool (revealing unknowns).

In the following section the reader will find a selection of visualisations designed as the latter group : as tools for cross-examination and questioning. But in today's world a visualisation is rarely designed for paper. This is true also for those that we shall present and discuss. Accordingly, a number of classic features that computers allowzooming, selecting, highlighting, etc. -will not be available in the paper publication. Yet, although these printed versions are here still life images of interactive systems, we wish they can shed an unexpected light on some aspects of the collection of edifices. So with no interaction possible, we have chosen to comment on these visualisations, and more precisely to try and show in real terms what their possible benefits are, through examples showing how they can serve information discovery. The section is organised as a sort of vis à vis dialogue between a common sense question or assertion (e.g. "recent transformations are better understood than old ones") and a visual answer. The whole section should be understood as illustrative of a method, rather than as conclusive on this or that theory, hypothesis or scientific position. We therefore make no claim on the actual scientific relevance of the questions that are listed -our intent is basically to demonstrate that, when facing large amounts of information, when facing inquiry processes based on comparative relations, such visualisations can be fruitful (if not unavoidable). Yet it should be said that a visualisation does not provide sense-making answers if relevant questions have not been figured out in the context of an expert's analytical process on the long run. In that specific context, expected and unexpected relations among individuals inside a collection, among parameters that model an individual's behaviour, can be unveiled thanks to carefully designed visualisations. Thereby, our understanding of how a complex system -a city centre's evolution over time -can be amplified. 1 Note 6. Blue vertical bars mean that a "positive" transformation could have occurred, and not that it did occur. Dates being given as approximate intervals, there are overlapping effects. The height of the bars should not be understood as the number of transformations for each year, but as the maximum number of transformations for each year. The effects of raids by the Mongol army are less visible -a result of scarce information about that period. Still what can be noticed is a rise of the building activity after the second and the third raids (zoom 3, Fig. 2) [START_REF] Dudek | Identifying and Visualizing Universal Features for Architectural Mouldings[END_REF]. The siege and occupation of the Swedish army (1655-1657) appear as relatively consequence-free on the area of the Market Square (zoom 4, Fig. 2). This naturally calls for some important remarks:

• the spatial extent of our analysis is limited to the Market Square, and of course no conclusions should be drawn on the city as a whole from this information set, • the granularity we have chosen -architectural structures, i.e. the form of edifices -has consequences on the information taken into consideration: the plundering of interior spaces or the stealing of furniture do not appear on the visualisation, • In all cases a visualisation shows data -and thereby is limited to the data available. When an event is poorly documented, it may remain undetected on the graphics. This very absence, in historical sciences, is an outcome by itself.

It has to be stressed that the visualisation does not mention or establish causality : it barely puts facts that occurred at the same period side by side, as food for thinking. Actual conclusions remain under the sole responsibility of experts. Whether this or that occupation resulted in destructions and chaos can only be underlined as a possibility, and not proven by the visualisation. Casimir the Great inherited a country built of wood, but left it built of stone. This is far too general a saying to be confirmed by the only example of the Market Square, even though Krakow was the country's capital then.

However the historySkyline visualisation does confirm that a strong building activity (zoom 1-a) occurred during the reign of this famous King (1333-1370) (zoom 1-b), and this along with a noticeable level of maintenance works (zoom 1-c) during the early period of his reign, and a rather high level of destructions (zoom 1-d) during the last part of his reign that can be understood as "wood replaced by stone". Note however that the visualisation would tend to present Casimir the Great as a precursor rather than as an isolated builder: following his reign the activity in fact seems to intensify even more. But naturally, a visualisation's role is not to actually draw such conclusions. A visualisation is meant to re-examine data sets under a new light. Inferences and conclusions remain the responsibility of the analyst, who most probably will need far more than one single visualisation.

Can peaks of activity on the Market Square be related to other rulers?

A visualisation cannot prove this, it can only put facts before the eye of the analysts.

The historySkyline visualisation shows that a strong building activity (zoom 1-a) occurs during the short reign (1300-1305) of King Venceslas II. Coincidence or causal relation? Whether this strong building activity should be considered as part of King Venceslas II's legacy needs an argumentation based on historical analyses, and not only based on the visualisation. But the visualisation at least underlines a pattern that is specific to King Venceslas II's reign, and turns our attention to him.

To which ruler does the highest peak of activity correspond?

The historySkyline visualisation localises the most intense building activity (zoom 1, Fig. 5) during the reign of Queen Jadwiga of Poland (1384-1399). But when analysed in detail it also suggests that the reign of King Casimir the Great (zoom 2, Fig. 5) and Queen Jadwiga probably correspond to quite different situations as far as the layout and architecture of the Market Square is concerned. During Casimir the Great's reign, an intensive dismantling activity occurs (zoom 2-ablack line). During Queen Jadwiga's reign the activity is almost entirely a construction activity. In other words, what is highlighted here are different steps in the evolution of the Market Square -a will to build and transform there, and then a steady densification trend.

Do analyses of different types of transformations require the use of different types of documentary sources?

It can help, yes. For instance, when trying to depict morphological transformations (changes that have a consequence on the overall physical layout of the edifice), visual material can be of greater help than administrative listings of all kinds.

The top historySkyline (Fig. 6) correlates changes that occurred on the Grand Scales alone, and types and amount of sources used to document those changes -shown as "shadows" below the horizon. The lightest shadow represents the number of documents used to date transformations. The darkest shadows represent the amount of visual documents used to analyse and depict the consequences of changes.

Note that visual documents are massively used for morphological transformations (a), whereas they are rarely available for recurrent transformations in this case (b). Also note that for the Grand Scales no visual document is used to document the final destructive transformation (Fig. 6-c), unlike in the case of the Rich Stalls (Fig. 7-c), where numerous sources document the destruction process itself.

Finally, the respective sizes of the shadows, as well as the proportions of dark and light greys can also be used to compare types of documents for various moments in the lifeline of edifices.

How many fires or natural disasters impacted the development of the Market Square?

47 fires, 34 floods, 6 earthquakes according to the historySkyline visualisation (not counting harsh winters, famines, epidemics and plagues, etc.). But the second part of the answer is the most important here : what the visualisation shows is what its authors are aware of (it could even be what they chose to show). In other words, it is almost certain that a number of other fires and natural disasters (undocumented) occurred during the history of the city. What the visualisation sums up is what we managed to learn, and this could have impacted our vision of the development of the Market Square. Furthermore, the visualisation shows events that could have impacted its development, but not necessarily that did impact it: a number of events may have been localized (and kept under control) in other parts of the city centre.

In this visualisation, fires, plagues, floods and other events are represented in parallel horizontal lines (zoom 1, Fig. 9), using various shades of green. Events are localised in time (zoom 1, Fig. 9, the 1221 flood of the Vistula river), and can then be correlated with other events (e.g. epidemics with famine for instance), with other contextual information (e.g. fires with wars, or with battles), or with the building activity.

1 Fig. 8 The historySkyline visualisation used to correlate building activities with contextual information -overview of the visualisation, Fig. 9 The historySkyline zoom 1 -the 1221 flood of the Vistula river

The 1555 major fire on the Market Square (zoom 2, Fig. 10), or the 1680 lightning strike on the belfry (zoom 3, Fig. 10), are unsurprisingly followed by modifications, yet faster in the former case.

Left as a question mark for historians, six years of combined epidemics and famine during the 1312-1315 time interval (zoom 4, Fig. 11) are followed by a sharp decrease in the building activity. How long did it take to remove so many buildings from the Market Square ?

It took a little less than one century, when looking at it globally.

The concentric time visualisation below shows that most edifices located on the Market Square were destroyed during the 19 th century (black dots inside the greenish ring). However it also underlines "group behaviours" that need to be analysed with more detail : the town hall compound (south west corner), or trading facilities in the north west corner apparently are destroyed over a rather short period of time. In other words, this visualisation helps us spot general trends, and underlines specific behaviours that can be investigated by zooming inside the display. And so the 19 th century is a period of massive destruction on the Market Square?

Yes, but not primarily. The following visualisation capitalizes on the concept of time series. On the x axis are distributed even periods of time (50 years) starting from the "formal foundation" of Krakow in 1257. On the y axis, we represent the overall amount of changes and alternatives for the whole collection of edifices, counted at each period. Reddish rectangles represent (bottom to top), morphological transformations, episodic transformations and destructive transformations. Greenish rectangles represent confirmed (bottom) and potential (top, darker) alternatives (i.e. moments in the lifeline of the artefact when there are several alternative possibilities about what really occurred). Circles added below the x axis represents the elements that could potentially be the first chains of edifices' evolution for each 50 years period. An interesting point can be made concerning the first half of the 19 th century (1807-1857). The period is known as the period during which most of the buildings standing in the Market Square were destroyed. But the visualisation shows that episodic changes widely outnumber destructive changes. This indicates that before deciding to tear down these objects, a number of solutions were tried out to repair, transform, reuse them. In other words it clearly shows that the well-established "pattern of destruction" should rather be called "pattern of renunciation" in front of maintenance and repair difficulties. The visualisation also underlines some clear patterns in the time distribution of alternative scenarios (green rectangles), with unexpected peaks in the 16th century, needing further investigation. Finally, note the number of elements that could potentially be the first chains of edifices' evolution during the 15 th century, at a time of low construction activity when compared to the 1357-1407 period -a puzzling hint. At this stage, though, it is important to point out that with questionable underlying data, with prominent subjective choices (typically the time span), this graphic does not prove anything. We consider it as just providing question marks that may help analysts know where to 'dig' next. This common sense assertion can be true, but it should certainly not be considered as a rule. Confusion and doubts may occur all along an edifice's lifeline. Noticeably, a number of confusions or doubts may arise concerning its destruction, due to unclear processes of decay, or to ill-documented annexations.

On the following graphs of potential interactions (1 and 2), alternative paths are located mainly on the left part of the diagrams (i.e. the oldest transformations), with a strong pattern of doubt for the cloth hall [START_REF] Aigner | Visualization of time-oriented data[END_REF]. But in (3) an alternative should be considered concerning the period that follows destruction. In (4), alternatives are evenly distributed all along the edifice's lifeline. Finally, [START_REF] Dudek | 3D as a content, 3D as a metaphor[END_REF] shows that what is best known for this object is actually the construction phase. Incidentally, a ratio can be calculated on the collection of edifices so as to "quantify" chances to find more "alternative paths" for destruction time than for construction time. In Krakow's Main Square, this occurs in 52 % of cases (sic!). In other words there are more "alternative paths" during destruction than during construction. The more transformations we can document on a given edifice, the more complex its lifeline is.

Well that is not so. Complexity is primarily related to the amount and quality of the information we have on each transformation. Accordingly, the lifeline of a large, well-documented edifice, even if very often transformed, may be much easier to interpret and analyze than the lifeline of a smaller edifice, transformed only once or twice, but for which precise knowledge is missing.

On this visualisation, called visual measure of complexity, we show relative patterns of complexity for artefacts: (1) dedicated to private or semi-private trading; (2) dedicated to collective administration of trading, (3) dedicated to the administration of the town. The visualisation focuses on alternative paths (i.e. moments in the lifeline of the artefact when there are several alternative possibilities about what really occurred). When there are no such alternatives between two transformations, the two transformations are merged inside a single rectangle [START_REF] Dudek | Concentric Time: Enabling Context+Focus Visual Analysis of Architectural changes[END_REF]. Note on the bottom right the simplicity of the diagram for Krakow's Town Hall's tower. For this particular artefact 32 successive transformations are documented (plus 2 archaeological investigations). However since each of these transformations is rather well documented and does not call for interpretation, the artefact's visual measure of complexity is limited to one rectangle. Note also, that unsurprisingly artefacts dedicated to private or semi-private trading (1) appear harder to analyse. This is due notably to the fact that information related to public buildings were preserved in town archives, unlike accounts of changes concerning private buildings. The more transformations, the more chances to come across doubtful transformations.

If we were not talking about historical facts, or about the way they are reported and ultimately reach us, this could be a sound assertion.

But when aligning vertically several multi-hypothesis chronology diagrams the assertion is soon denied (compare for instance a -Grand Scales -to (b) -fish stalls -far more transformations in the former, far more doubts in the latter). This is primarily due to the heterogeneity of historical records, in terms of quantity, of exhaustiveness, of precision, of trustworthiness. But the way we, today, analyse and interpret historical evidence also plays a significant role in the emergence of doubts, when we for instance consider if a fire reported on edifice A could have spread to its neighbour edifice B (illustrated in c -baker's stalls -the 1445 fire reported in c is confirmed on the neighbouring salt stalls, but its actual impact on the bakers' stalls is not confirmed by sources), or when we investigate on parentage relations between edifices (illustrated in d, Rich stalls).

Recent transformations are better understood than old ones.

One could expect it, but it is not so. What does really make a difference is the quality of the documentation, and this is often a matter of ownership, status and importance of the edifice, more than a matter of moment in history. The following graphs of potential interactions confirm that what we actually understand about transformations cannot be strictly related to time, and that doubts about the evolution of minor constructions remain throughout their evolution (1). In addition, the visualisation shows that the extent to which we can understand transformations cannot be related to the type, function, size of the edifice: in the case of the hatters' stalls (2) a construction step is fairly well dated whereas the period of construction of the 'three stalls' (3) is simply un-localised in time, although the two edifices compare in terms of function.

Were they once, all of them, together on the Market Square ?

With a very quick look at this "zoom out" view of the concentric time visualisation the answer becomes straightforward: NO. And this can notably be due to a spatial overlapping: the bread benches are replaced by bakers' stalls (a). In one case though the situation is more arduous : the Cloth Hall (b) and the Rich Stalls (c) are built over an older structure called Boleslaus Stalls (d). Yet at this stage there is no consensus on whether or not one of them actually replaced the older structure, or inherited from it. Coming back to the question -Were they once, all of them, together on the Market Square -the no answer does win, but it is a narrow win : the visualisation clearly shows that most of the edifices did overlap in time. The visualisation gives a good indication on the density of occupation of the Market square, with a rather long-lasting peak between 1580-1589 (e) and 1820 (f) : between 18 and 22 buildings present at a time over the period.

On which object do owners repeatedly insist on introducing recurrent changes ?

We do not know. The concentric time visualisation does spot different densities of recurrent changes : a -the Cloth Hall, b -the Town Hall's tower and c -St. Adalbert church unsurprisingly compete for the overall title (maximum amount of recurrent changes); dguardhouse sets the density record (number of recurrent changes per century); while no recurrent change at all is reported for four edifices (e). The visualisation also spots densities in time: recurrent changes are intensive in period f -the Town Hall ensemble -over a period of 25 years, prior to the demolition of three of its components. But the visualisation does not show how many recurrent changes were introduced indeed, it only shows how many were reported, documented, and therefore available for us to comment on. And this makes a huge difference.

What relations existed between the components of the Town Hall compound?

Naturally, we shall not here comment on physical elements that materialise spatial relations, such as doors, stairs, shared walls, wall-walks, etc.. The concentric time visualisation helps unveiling temporal relations between the five components of the town hall ensemble : the town hall itself (a), the granary (b), the belfry (c), the dungeon (d) and the guardhouse (e). Among events and processes that affect the town hall and the granary, a majority coincide in time (black arrows). By contrast, changes that occur on the dungeon seem not to coincide in a number of cases with neighbours (red arrows). Finally, whereas changes on the first guardhouse correspond to changes on the belfry (green arrows), most changes on the next two evolutionary phases of the guardhouse seem unrelated to changes on the belfry (red arrows).

In other words, the visualisation can help confirming or uncovering relations of homogeneity (function, owner, etc.), and it can help spotting divergences as they appear in the lifeline of ensembles.

Was the Market Square's development impacted by the decision of transferring the status of capital city from Krakow to Warsaw?

Sigismund III Vasa moved the royal court to Warsaw in 1596 -and although most of his descendants and/or successors were still crowned and buried in Krakow, Warsaw became a sort of de-facto centre of the country, before ultimately acquiring the status of capital city in 1919. Still, no clear (or at least short-term) impact can be observed on the concentric time visualisation for the period concerned (a): the density of changes after 1596 does appear a little weaker, but there is no statistically significant impact.

Does an edifice last longer when it is bigger?

Considering the cost of dismantling large edifices, one could think so. But considering the maintenance cost of large edifices, one could think the opposite. We clearly do not have enough data, especially on early stages of evolution of the edifices located on the Market Square, to propose a robust visual analysis. But we do have some indications that may help us try to spot a possible trend, and to give a provisional answer. Inspired by C.J Minard's tableaux graphiques, the following visualisation is an attempt to measure the space-and-time impact of edifices.

On the x-axis we report the surface of edifices as they appear in Dominik Puck's 1787 plan (overall surfaces, all levels inclusive, and not only floor space, see for instance in (a) the surface of the town hall). Naturally, since surfaces of edifices changed over time, the visualisation does introduce a bias. On the y-axis we report the duration of life of edifices -with a dotted line when it is approximate (b).

The visualisation, tested here on the elements of the town hall's ensemble [START_REF] Dudek | Analysing Alternative Scenarios of Evolution in Heritage Architecture: Modelling and Visualization Challenges[END_REF] and three other edifices [START_REF] Friendly | A Brief History of Data Visualization[END_REF], confirms that parameters such as function, quality of construction, localisation, symbolic aspects or strategic and cultural importance play a major role in whether or not the edifice lasts long (most often a far greater role that the actual size of the edifice). For instance, rectangle (c) (corresponding to the Grand Scales) is higher than rectangle d (the granary), although d is much wider: the granary was larger than Grand Scales, but it did not last as long. [START_REF] Friendly | Visualizing Categorical Data[END_REF] Note 10. i.e. the town hall, the belfry, the granary, the dungeon and the guardhouse Note 11. i.e. St. Adalbert church, the Grand Scales and the Small Scales Note 12. In addition, the visualisation helps comparing how beneficial edifices have been in the development of the Market Square. The surface of rectangles represents a time-and-surface ratio corresponding to a concept that can be verbalised as "availability of square meters". A wide and flat rectangle is a large building that lasted not long -very useful when available, but not available long. A high and narrow rectangle is a smaller building that lasted longer -not a lot of space available but numerous generations benefited from it. In other words, the surface of rectangles measures the practical impact of the artefact.

Fig. 23

A re-vision of Minard's tableaux graphiques used to measure the space-and-time impact of 8 major edifices. a) the surface of the town hall, b) approximate duration of edifice's life, c) a time-and-surface ratio for the Grand Scales, d) a time-and-surface ratio for the granary.

Is the amount of transformations of an edifice related to its position inside the Market Square?

Apparently it is not, although on Krakow's Market Square most of the major edifices -and the better documented too -are localised in the south part. In this visualisation each square corresponds to a given number of transformations [START_REF] Friendly | Milestones in the History of Thematic Cartography, Statistical Graphics, and Data Visualization[END_REF]. Squares are sorted by increasing order, left to right, top to bottom (the actual number of transformations is written below each square). Inside each square, edifices for which the overall amount of transformations corresponds to the number written below the square are drawn inside a schematic map of the Market Square (cf. Fig. 33). The visualisation underlines higher numbers of transformations for edifices localised in the south part of the Market Square, and lower numbers for edifices localised in the north part. This however is not a rule, but rather a general pattern, with noticeable exceptions like the officer's house (south part, two transformations only) or the pottery and lard stalls (north part, 13 transformations).

Fig. 24

An analysis of the spatial distribution of transformations using a small multiples -like visual solution. Edifices the localisation of which is known are drawn in dark red filled polygons. Edifices drawn as yellow "clouds of probability" represent those for which archaeological findings only partly document the localisation. Finally, edifices for which we have access only to a descriptive approximate localisation are represented as reddish "clouds of probability". edifices the localisation of which is known edifices that cannot be localised at all due to lack of information Note 13. This number comprises all types of transformations, including potential ones.

How do construction techniques overlap in time?

In this visualisation each edifice is represented by a square icon, with a background colour indicating the construction technique used :

• deep-blue squares represents brick and stone edifices,

• light blue squares are buildings, that originally were wood structures later on were transformed into brick or stone built edifices, • brownish squares are wooden construction,

• white squares are those edifices for which nothing can be said in terms of morphology or of construction technique. Icons are then clustered along a timeline, century by century, at positions corresponding to their construction date. Thick pinkish outlines and black arrows point out problematic dating. These icons are so-called multidimensional icons, meaning that they pull together a variety of information, here including time (Fig. 26). This visualisation shows clear patterns:

• the most important building activity on the Market Square in Krakow takes place in the 14 th century, • brick and stone edifices tend to be built earlier, wooden structures appear as harder to date, and come in a second row, • the majority -four out of five -of edifices constructed in 13 th century did not last for a long time (Fig. 25).

In other words, what we can read here is a gradual process of densification of the Market Square, with key brick and stone major edifices erected first (two exceptions), and then little by little accompanied by minor trading facilities built of wood. Yet one should not jump to conclusions too fast. The amount of uncertain information can significantly influence the interpretation of the data. Besides, the visualisation's structure of time (discrete time -one century clusters) may overemphasise construction works during the 14 th century due to source effects. Figure 27, with a different time step, shows a slightly different picture for the same period (brick and stone major edifices erected successively, over time).

In fact, rather unsurprisingly, both visualisations (Fig. 25 and 27) show that construction techniques have more to do with the role, size and impact of the edifice than with the historic period.

Fig. 27

A visualisation on which the information encoded is reduced to the edifice's construction material and dating (colour codes for materials are the same than in the previous visualisation).

Note that a switch in the time granularity -from one century to 25 years -sheds a different light on the building activities during the 14 th century.

Fig. 26

Encoding of the time duration inside each multidimensional icon: the length of the deep blue arc indicates the object's duration of life (i.e. its presence on the Market Square). Dotted lines point out doubts concerning the dating (construction or destruction). In this example construction is likely to have happened between 1600 and 1750, and the object lasted until c 1830.

And so at the end of the day, which story [of an edifice] compares to which?

Naturally a number of parameters need to be cross-examined, if we intend to try and answer this question: duration of life, amount and nature of transformations, construction type, quality and quantity of information available, etc.. One way to visualise multidimensional data sets, dating back to the 19 th century, is what E.R Tufte calls small multiples. The following visualisation gives a synthetic, comparison- enabling overview of 8 parameters (Fig. 28), with a ninth parameter (construction type) represented through the background colour. Each square icon represents a given edifice's "knowledge pattern". Edifices are aligned by construction type, and then ordered by decreasing duration of life (Fig. 29).

At first glance, when analysing the visualisation, some edifices do clearly compare to others, in particular inside groups corresponding to a given construction type (colour of background) : observe for instance D1 and F1, E2 and F2, A3 and B3, D3 and D4, D6 and E6.

Similar patterns can also be spotted across groups: C3 compares to F2, D6 and E6, I3 compares to B6, B2 compares to D1 and F1, etc.. Beyond one to one comparisons, clusters can be observed in or across groups: (E3, G3, A4, E4); (A1, D1, F1, H1, B2), etc.. Groups as such do have particularities: typically the filled yellow triangle -corresponding to the overall amount of transformations vs. certain transformations -is significantly smaller in the case of wood constructions (brownish background). Observing the whole collection also underlines a pattern : the duration of life is apparently not the determining factor in the amount of information and of transformations : compare for instance B2 and D2 (B2 is older, but with less transformations than D2).

But besides helping to spot patterns inside a collection, such a visualisation can also be fruitful in underlining significant exceptions, "outliers" inside a group. C2 for instance shows significant differences with the other edifices on line 2 -an indication that the "knowledge pattern" for this object is slightly different. Values for the six parameters (a1 to a6) are reported along axes starting from the centre of the square (growing values outwards). On each axis, the maximum value for a parameter across the collection is reached when reaching the circle. In this example, value is zero for axes a1 to a4, axes which correspond to the expression of a doubt. By contrast, values for a5 and a6 are always positive, and a yellow triangle connecting them to the centre is drawn filled. The seventh parameter -duration of life (b) -is represented by an arc, with growing dating clockwise (midday is year 1000, 6 o'clock year 1600, cf. Fig. 26). A dotted line points out doubts concerning the dating. Finally, in the upper right comer of the square little black circles identify various possibilities concerning the first stage of the artefact's evolutionary chain (c).

Another interesting exception can be also noted in line 2 (originally wooden buildings, transformed later on into masonry structures). Inside this group edifice B2 is the only one for which the "knowledge pattern" contains no expression of doubt (axes a1 to a4 -Fig. 28). What to derive from this observation is the analyst's responsibility (Is the edifice really that well known? Were documents over-interpreted in an assertive way?) -the visualisation however does unveil an intriguing pattern.

Finally, comparisons can be a first step in a re-interpretation of the initial data : F3 and A6 show very similar patterns, suggesting implicitly that the latter (construction type not known) could belong to the former's group (wooden constructions). However the visualisation is a first step, and nothing more than that. It lays a question on the table, based on facts, a question that naturally needs an in-depth investigation.

Is there a relation of the construction type to the nature, amount and assertiveness of the pieces of information available?

The small multiples visualisation can help comparing the overall amount of transformations with the number of definite transformations (i.e. corroborated by enough trustworthy documents and/or testimonies). The more vertical the left side of the yellow triangle is, the more these numbers coincide -if the triangle's side is vertical (as in Fig. 28), all of its transformations are considered as certain. Once this is said, spotting group behaviours becomes straightforward: edifices built of brick and stone (lines 1 and 2) are obviously more (surface of the triangle) and better (verticality of the left side) documented.

In the bottom visualisation (Fig. 30) all the edifices on which a monograph (or a specific in-depth article) has been published are highlighted (green layer over the small multiples). Unsurprisingly, an overwhelming majority of edifices are brick and stone edifices. One interpretation of this observation is that the construction type does have an impact on the nature, amount and assertiveness of the pieces of information available. But another conclusion could also be drawna bit far-reached though: storytelling has a logic of its own, and a monograph being quite often by essence assertive, what we witness here might not necessarily be certainty (of transformations) but a thirst for definitive answers -a sort of horror vacui in the making of monographs.

Do edifices that cannot be precisely localised have something in common?

There are at least thirteen such edifices on the Market Square, known to have existed, but with not enough information to propose more than an approximate localisation (cf. section one). The fact that they do have something in common could be corroborated by the following visualisation, combining a schematic map of the Market Square, a visual measure of complexity for each edifice, and multidimensional icons (Fig. 31). Unsurprisingly, little being known about their evolution, the visual measures of complexity generally more or less compare to one anotherhardly a common point though, since related to the documentation rather than to the edifices. The visualisation also underlines that these edifices were quite evenly distributed all around the Market Square, with a low number of known transformations. No temporal pattern appears established, besides the fact that most of them were removed quite early. Finally, a majority of these edifices were wood constructions, but with the noticeable exception of the wooden cloth (?) chambers, (supposedly transformed into a masonry structure shortly before its dismantlement or annexation) and with five edifices for which construction type remains unclear.

Coming back to the initial question, the visualisation does underline some similarities (in particular a poor documentation), but cannot be considered as really conclusive: the issue will need further investigation. More important to state, the visualisation shows that there is room for comparisons and reasoning even when edifices cannot be precisely localised in space.

Fig. 31

The combination of three visual formalisms used to highlight possible similarities between edifices that cannot be precisely localised: a schematic map of the Market Square on which the localisation of the edifices is represented by reddish "clouds of probability" the visual measures of complexity for each edifice, with a line connecting them to the relevant "cloud of probability" -note the left arc, corresponding to the market hall for minor traders, supposedly translocated. Multidimensional icons summarising 9 parameters, among which the duration of life.

What can be said about an edifice's spatial layout when no documents comment on it ?

There should be nothing more in a visualisation than the data -no interpretation, no point of view. But in all cases a visualisation can help analysts spot meaningful patterns inside the data (Fig. 32). Documents give us almost no indication about the spatial layout of a number of edifices -in particular those that cannot be precisely localised. Yet the following visualisation does reveal that some stalls inside those edifices significantly stand out. The visualisation is based on a simple data set: an 18 th century inventory of commercial facilities describing stalls one by one (surface, tax level before 1760, tax level after 1760).

The visualisation is a re-vision of candlestick charts, a solution developed in the 18 th century by the Japanese rice trader Munehisa HommaHomma , in order to represent price movements over time. Each individual stall (in the example below each stall inside the cookshops) is represented by a candlestick. The candlestick's horizontal position corresponds to its order of appearance in the inventory: stall 1 is the first on the x axis. The candlestick's vertical position corresponds to the stall's tax levels before and after 1760. Colour is used to show differences in the tax increase (Fig. 32f) : the brighter the red is, the higher the increase is. Finally, brownish lines below and above the main rectangle show the tax/surface ratios before and after 1760. The visualisation shows, for instance, that ratios remain rather stable, and spots a catching up mechanisms for stall 9. What is striking here, is the way stalls 1 and 2 stand out -far higher taxes. This can be due to the specificity of the products that were sold in those two stalls, or to their profit. But it can also be a result of their position with regard to other stalls. a/a'-the tax level (amount), before 1760 (a) and after 1760 (a'). The higher the rectangle is positioned, the higher the tax is paid. The higher the rectangle is, the biggest the difference between tax levels before and after 1760 is. b/b' -short grey horizontal lines show the average tax per m 2 ratio across all the stalls (b -before 1760/ b' -after 1760) c/c' -slightly larger grey horizontal lines show the maximum tax per m 2 ratio across all the stalls (c -before 1760/ c' -after 1760) d/d' -tax per m2 ratio for this specific stall (d -before 1760 / d' -after 1760) e -this specific glyph is used when tax levels before and after 1760 remain unchanged.

Does is make a difference to be on the west or on the east side?

One could consider that wooden commercial facilities were probably rather evenly distributed on all sides of the Market Square -meaning in practical terms evenly distributed on the west and east sides of the Cloth Hall. (Fig. 33). On this schematic map of the Market Square (based on a 1803-1804 plan) and once one knows which edifices are wooden constructions, one could suppose that there are a little more edifices on the west side. But no indication is given here on the type and density of transformations, on how and when the edifices were built and destroyed, etc.. By contrast, the following visualisation, called evolution field (Fig. 34), helps weighing precisely the density of objects on both sides of the Cloth Hall (as well as the overall number of transformations and of alternatives, the durations of life, the temporal patterns for construction and destruction time). Wooden commercial facilities on the west side outnumber by far those on the east side, some emerge earlier in time, their process of decay and demolition stand out as harder to date precisely -in fact activity as such appears as far greater on the west side. The visualisation can also highlight specific events -here reports of fire are represented as little horizontal red lines, and distributed in time.

A spectacular dissymmetry appears between the two sides: a large number of fires on the west side, particularly during the 16 th century, only one fire suspected on the east side.

Fig. 33

The Cloth Hall, by its dimensions, implicitly splits the Market Square into two "halves" -that we name here by convention west and east. Quite often, in virtual reconstructions, simple commercial edifices are represented as regular rows of stalls, evenly distributed, all the same in size -or at least linked by simple ratios. Yet the correct answer to the question is actually no, and betting on regularity is certainly not a good choice here. Surfaces of stalls shown below are absolutely not regular, and neither surfaces nor dimensions can be systematically linked by a simple ratio. A simple and provisional conclusion can be drawn : we probably deal here with erratic groups of temporary constructions that mostly share a common name. But an interesting pattern can also be spotted: the surface of a majority of stalls differs only in a small proportion from a sort of medium value -and what is more from a medium value that can be observed across several different edifices. The answer remains no, but a door opens on further investigations about the medium value observation. These remarks can be made thanks to a 1760 inventory of commercial facilities [START_REF] Kienreich | Information and Knowledge Visualization -An oblique view[END_REF], inside which the surfaces of each individual stall is reported, along with its tax level before and after that date. This data set is used to build a visualisation inspired by Charles de Fourcroy's 18 th century tableaux poléométriques, a diagram invented to compare visually populations of various European towns. The surfaces of stalls are represented by squares of a size corresponding to the surface of the stall (Fig. 35a). Squares are then drawn one on top of the other, and their dimensions/owners available interactively (Fig. 35-c, d). Colours have no other role than helping to better distinguish squares from one another. When two stalls have the same surface, the square is divided in two right triangles. Each edifice can then be represented by a tableau poléométrique, and comparisons made. The following example shows four edifices of very different overall sizes. On each of them it appears quite clearly that surfaces of stalls inside each edifice widely differ -and in a way that could even be seen as totally chaotic. However, a closer look reveals that, in all of those four edifices, the majority of surfaces are grouped around the green line's value (more or less 3 square meters, or more or less 9 squares elks). Also noticeable, in each of the four edifices one stall stands out significantly as bigger in surface than the rest. Finally, the left tableau (Fig. 36a) -corresponding to the 'Lithuanian' stalls, shows a wider range of surfaces, which is quite understandable when knowing their overall number (33, far more than the others) and its approximate localisation, in the south and the east part of the Market Square (meaning most likely an edifice composed of several, spatially independent, groups of stalls).

Note 5 .

 5 The two visualisations recount a story for didactic purposes: this of the frontiers of Poland over time (16 key moments considered). Top, a temporal density map -the deeper the blue, the more often the area was part of Poland. Bottom, the ladybug race metaphor: the bigger the ladybug, the bigger the country's surface -the horizontal axis stands for time.[J.Y. Blaise, I.Dudek, 2006] Foreign occupation results in destructions and chaos.Yes, and no. In this visualisation, called historySkyline, the height of vertical bars represents the amount of transformations across the whole market square, year by year, since 1035. Blue bars (a) represent "positive" transformations[START_REF] Dudek | Understanding changes in historic architecture[END_REF] (creation / modification), red horizontal lines (b) represent episodic and recurrent changes (maintenance or equivalent), black horizontal lines (c) represent destructive changes. These indications are correlated with the number of documents available (grey "shadow"). In addition, they are also correlated with a variety of contextual information such as wars, natural disasters, lives of important people, new laws (d), etc.. Sieges, wars, invasion and occupations are represented on parallel lines (e-e) with colours identifying a given "invader". As can be seen on the visualisation (zoom 1, Fig 1) successive occupations by the Russian, Prussian and Austrian armies between 1836 and 1841 do correspond to a period of massive destructions on the Market Square. But by contrast (zoom 2, Fig 1) a strong and positive construction activity is visible during the Czech presence (1291-1306).

2

 2

Fig. 1

 1 Fig. 1 The historySkyline visualisation showing constructive and destructive building activities on the Market Square, together with some contextual information. top -overview of the visualisation, zoom 1 -successive occupations by the Russian, Prussian and Austrian armies between 1836 and 1841, zoom 2 -the Czech presence (1291-1306)

Fig. 2

 2 Fig. 2 The historySkyline zoom 3 -the second and the third raids of the Mongol army (1260, 1287), zoom 4 -the siege and occupation of the Swedish army (1655-1657),

1 Fig. 3

 13 Fig. 3 The historySkyline visualisation used to highlight the legacy of King Casimir the Great in terms of building activity : construction, maintenance and destruction during the 14th century. top -overview of the visualisation, bottom fragment -(zoom 1) a) building activity, b) the reign of King Casimir the Great (1333-1370), c) maintenance works, d) level of destructions.

1 Fig. 4

 14 Fig. 4 The historySkyline visualisation used to highlight the reign of King Venceslas II : construction, maintenance and destruction at the dawn of the 14th century. top -overview of the visualisation, bottom -fragment (zoom 1) -the reign of King Venceslas II (1300-1305),

2 1Fig. 5 A

 25 Fig. 5 A comparison of the impacts of two reigns in terms of building activity using the historySkyline visualisation. top -overview of the visualisation, zoom 1 -the reign of Queen Jadwiga of Poland (1384-1399), zoom 2 -the reign of King Casimir the Great (1333-1370)

Fig. 6

 6 Fig. 6 The historySkyline visualisation showing information gathered about constructive and destructive activities related to the Grand Scales, together with some contextual information. a) morphological transformations, b) recurrent transformations, c) destructive transformations.

Fig. 7

 7 Fig. 7 The historySkyline visualisation showing information gathered about constructive and destructive activities related to the Rich Stalls. a) morphological transformations, b) recurrent transformations, c) destructive transformations.

2 3 4 Fig. 10

 410 Fig. 10 The historySkyline zoom 2 -the 1555 major fire on the Market Square zoom 3 -the 1680 lightning strike on the Town Hall's belfry

  The concentric time visualisation[START_REF] Dudek | Visual assessment of heritage architecture life cycles[END_REF] is an attempt to combine time and space inside the same graphic. A 2D map is displayed inside the central circle, showing simplified outlines of the artefacts under scrutiny. Starting from the circle (a) (that stands for the current year -here 2012), concentric circles represent a move towards the past. Each edifice is connected (b) to a radial timeline (c) that distributes events related to its evolution in time. Only the timelines (d) corresponding to the three edifices that remain up to now on the Market Square reach the 2012 red circle. Note 8. Concentric time is a dynamic visualisation. Colours (yellow, blue, red) mach the conventions adopted for multihypothesis chronology diagram (cf. section one) The figure presented below shows the central part of the visualisation.

Fig. 12

 12 Fig. 12 Concentric time visualisation -a fragment covering the 1700-2012 period a) year 2012 b) connector between a timeline and an object's contour c) an object's timeline d) objects present on the Market Square in 2012

Fig. 13

 13 Fig. 13 An overview of changes and alternative paths, visualised as a time series (50 \years clusters).

Fig. 14 A

 14 Fig. 14 A comparison of five patterns of doubt concerning the construction and the destruction periods (graphs of potential interactions).

Note 9 . 3 Fig. 15

 9315 Fig. 15 Relative patterns of complexity of lifelines depending on the function and/or status of artefacts: (1) private or semi-private trading facilities (2) collective administration of trading (3) town administration

Fig. 16 A

 16 Fig. 16 A comparison of four multihypothesis chronology diagrams. The grey rectangle corresponds to a duration of one century. a) Grand Scales, b) fish stalls, c) bakers' stalls with the bread benches considered as the possible first element of bakers' stalls' evolution, d) Rich Stalls with several artefacts that can be considered as the possible first element of Rich Stall's evolution.

Fig. 17

 17 Fig. 17

  Three graphs of potential interactionsshowing that what we know of a particular transformation has no relationship with how far it goes back in time.

Fig. 18 The

 18 Fig. 18 The Concentric time visualisation helps underlining the overlapping (in time and space) of edifices within the Market Square. Note that not all the edifices in the catalogue are presented here : the visualisation corresponds to a 2011 analysis of major edifices. a) bread benches and bakers' stalls b) Cloth Hall c) Rich Stalls d) Boleslaus Stalls e-f) period corresponding to the most intensive occupation of the Market Square (1580-1820)

Fig. 19

 19 Fig. 19 The Concentric time visualisation used to spot densities of changes across the collection of edifices. a) Cloth Hall b) Town Hall's tower c) St. Adalbert church d) guardhouse e) edifices without any recurrent change f) period of intensive recurrent changes for the Town Hall ensemble

Fig. 20

 20 Fig. 20 The Concentric time visualisation (fragment) used to spot coinciding or divergent temporal behaviours inside a compound. a) town hall b) granary c) belfry d) dungeon e) guardhouse coinciding behaviours divergent behaviours

Fig. 21 The 1 Fig. 22

 21122 Fig. 21 The Concentric time visualisation used to question the impact of an event on the density of changes. a) year 1596

  Fig. 25 Time distribution of construction techniques, using multidimensional icons.

Fig. 28 A

 28 Fig.28A small multiples visualisation : parameters and encoding. Values for the six parameters (a1 to a6) are reported along axes starting from the centre of the square (growing values outwards). On each axis, the maximum value for a parameter across the collection is reached when reaching the circle. In this example, value is zero for axes a1 to a4, axes which correspond to the expression of a doubt. By contrast, values for a5 and a6 are always positive, and a yellow triangle connecting them to the centre is drawn filled. The seventh parameter -duration of life (b) -is represented by an arc, with growing dating clockwise (midday is year 1000, 6 o'clock year 1600, cf. Fig.26). A dotted line points out doubts concerning the dating. Finally, in the upper right comer of the square little black circles identify various possibilities concerning the first stage of the artefact's evolutionary chain (c).

Fig. 29

 29 Fig.29The combination of small multiples (ordered by type of construction and estimated duration of life).

Fig. 30

 30 Fig. 30 The combination of small multiples. A green layer over edifices on which a monograph or an in-depth article has been published. A dotted green line around edifices mentioned in those texts as part of the compound being discussed.

  Fig. 32A re-vision of M. Homma's candlestick charts, used to uncover how some stalls may stand out inside a commercial facility.

  Fig. 34 The evolution field visualisation underlines west/east density and 'knowledge patterns'. a -possible period of construction b -artefact's overall lifetime c -possible period of demolition/dismantling d/d' -confirmed/suspected fire e -definite morphological transformation f -definite recurrent transformation g -unknown results of a confirmed transformation h -potential transformation i -artefact identified during archaeological survey i' -archaeological remains not clearly attributed to the artefact

Fig. 35

 35 Fig. 35The tableau poleométrique for 'Lithuanian' stalls. Each stall (a) inside the tableau is interactively connected to a diagram showing its length/width proportions (b) and its owner (c). Stalls for which indications of surface or tax lack are also taken into consideration (d).

Fig. 36

 36 Fig. 36 Four tableaux poléométriques used to compare surfaces of individual stalls inside and across artefacts. A green line in the background is used to underline a sort of "medium value", corresponding to approximately 9 square elks. a) 'Lithuanian' stalls b) stalls near the minor traders hall c) cookshops d) stalls near the Town Hall

3 4

	Note 7. The historySkyline is a dynamic
	visualisation : the user can choose to
	show or hide various information sets
	when the readability of the whole graphic
	is at stake.
	Figures presented in this chapter are
	screen captures of	the original
	visualisation, with parts highlighted on
	demand .

V i s u a l a n a l y s i s o f t h e c o l l e c t i o n : c r o s s -e x a m i n a t i o n a n d s e n s e -m a k i n gJ.Y. Blaise, I. Dudek

J.Y. Blaise, I. Dudek

When lacking adequate information, tax levels can give an indication about the surface of stalls.

No, they can't. At least not as far as Krakow's Main Square unlocalised commercial facilities are concerned, in 1760. The following re-vision of Charles de Fourcroy's tableaux poléométriques demonstrates that neither the tax level, nor the tax increase at that time were proportional to the surfaces of the stalls. The visualisation is based, as the previous one, on an 1760 inventory of commercial facilities [START_REF] Kienreich | Visualising Knowledge Maps for Encyclopedia Articles[END_REF], inside which the surfaces of each individual stall is reported, along with its tax level before and after that date. Squares in the four top tableaux (Fig. 38a) represent surfaces of stalls, as in the previous example (cf. Fig. 36). Each square inside the top tableaux is then duplicated in the bottom part. But this time the colour used to fill a square is proportional to the tax level of the stall : the brighter the red is, the higher the tax is. Since the size of squares represents surfaces, if tax levels had been proportional to surfaces we would have bright red colours on the bigger squares, and progressively darker reds as the size of squares diminishes (Fig. 37 and38a). Interpreting the visualisation becomes straightforward: bright and dark reds are NOT organised progressively, taxes are NOT proportional to surfaces. But maybe the tax increase in 1760 was proportional? Or maybe the tax increase in 1760 was a sort of catching-up process? Both these possibilities are also denied, by the second visualisation (Fig. 38b), where the bottom squares show the tax increase ratio in 1760 (bright red = high tax increase rate, greenish = low tax increase rate). There is no simple and direct relation of surface to tax.

Fig. 37

In this re-vision of the tableaux poléométriques, various tints of red (a) are used to represent tax levels. Tax values and increase levels are available interactively (b). A shade of grey is used when the surface is known, but not the tax level (c). Incidentally, this is the case here ('Lithuanian' stalls) only for the largest of all the stalls (sic !).


Wenjuan Gu

Diego Cattaruzza

Maxime Ogier
email: maxime.ogier@centralelille.fr

Frédéric Semet

Adaptive large neighborhood search for multicommodity VRP

come

Introduction

In this work we study a vehicle routing problem where customers request multiple commodities. Different strategies to deliver a set of commodities to customers were presented in [START_REF] Archetti | Multicommodity vs. singlecommodity routing[END_REF]. Among these strategies, a new one, the commodity-constrained split-delivery mixed routing problem (C-SDVRP) is presented and compared with classical ways to deliver multiple products (allowing to split a commodity or using vehicles dedicated to each commodity). In the C-SDVRP, the vehicles are flexible and can deliver any set of commodities, and a customer who requests multiple commodities can be delivered by different vehicles.

When a commodity is delivered to a customer, the entire required amount is handed over. This, if the customer is visited more than once, the different vehicles will deliver different sets of commodities. This problem arises for example in delivery of fresh fruits and vegetables to catering.

In this case, products can easily be mixed into the same vehicle, and splitting the delivery of an individual commodity is not acceptable. This is also very relevant in the multi-depot case, where each each depot has a limited quantity of each commodity. A customer can then be delivered by vehicles coming from different depots.

The C-SDVRP has first been studied in [START_REF] Archetti | Multicommodity vs. singlecommodity routing[END_REF]. The authors proposed a branch-and-cut algorithm able to solve 25 out of 64 small instances (15 customers) to optimality within 30 minutes, and a heuristic method. The heuristic consists in (1) making copies of each customer, one for each commodity required by the customer, and (2) using a heuristic for the capacitated VRP. In [START_REF] Archetti | A branch-price-and-cut algorithm for the commodity constrained split delivery vehicle routing problem[END_REF], the authors proposed an extended formulation for the C-SDVRP and developed a branch-price-and-cut algorithm. They solved to optimality instances with up to 40 customers and 3 commodities per customer within 2 hours. This work proposes an adaptive large neighborhood search to solve the C-SDVRP, with the objective of obtaining very good solutions on small instances, and to be able to efficiently solve large instances.

The C-SDVRP can be defined based on a directed graph

G = (V, A) in which V = {0} V C
is the set of vertices, and A is the set of arcs. More precisely, V C = {1, ..., N C } represents the set of customer vertices, and 0 is the depot. A cost c ij is associated with each arc (i, j) ∈ A and represents the non-negative cost of travelling from i to j. Let M be the set of commodities that have to be delivered to the customers. Any customer i ∈ V C may request any set of commodities. The depot contains a fleet of identical vehicles with capacity Q, able to deliver any subset of commodities. The objective is to minimize the total travelling cost.

The problem involves two related decisions: (1) finding a set of vehicle routes serving all customers; (2) selecting commodities delivered to each customer. The constraints are:

(1) each route starts and ends at the depot; (2) the total quantity of commodities delivered by each vehicle does not exceed the vehicle capacity Q; (3) each commodity requested by each customer must be delivered by a single vehicle; (4) the demands of all customers need to be satisfied.

To solve the C-SDVRP, it is possible to duplicate the node associated with each customer by the number of commodities requested by the customer [START_REF] Archetti | Multicommodity vs. singlecommodity routing[END_REF]. To each duplicated node, we then associate the demand of the customer for the corresponding commodity. For the sake of clarity, in the following we will call the duplicated nodes customer commodity.

Adaptive large neighborhood search

In order to solve the C-SDVRP for large instances, we propose a heuristic method based on the ALNS framework of [START_REF] Ropke | An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows[END_REF]. Local search moves are also used in order to improve the solutions. A solution is represented as a set of routes. In order to take into account the specific features of C-SDVRP, a route can be represented: (1) as a sequence of customers, each customer having a set of commodities, or (2) as a sequence of customer commodities.

In the first case, removing a customer from a route implies to remove the customer with the set of commodities delivered in this route, while in the second case it is possible to remove only one commodity.

General framework

ALNS relies on a set of removal and insertion heuristics which iteratively destroy and repair solutions. The probability to select a heuristic at a given iteration is influenced by its performance during past iterations. A sketch of the method is outlined in Algorithm 1.

An initial solution is constructed as follows: (1) give a random sequence of customers commodities to construct a giant tour, (2) apply a split procedure [START_REF] Prins | A simple and effective evolutionary algorithm for the vehicle routing problem[END_REF] to get a solution,

(3) apply local search to improve this solution. Roulette wheel: select a removal heuristic h rem and an insertion heuristic h ins

4:

Destroy: s rem ← remove ρ customer commodities from s applying h rem

5:

Repair: s ins ← insert removed customer commodities into s rem applying h ins 6:

Improve: s ← improve solution s ins with local search

7: if f (s ) < f (s best ) then s best ← s end if 8: if accept(s , s) then s ← s , ρ ← 1 else ρ ← ρ + 1, or ρ min if ρ = ρ max end if 9: until stopping criterion is met 10: return s best
At each iteration, a simulated annealing criterion is used to determine if the new solution s is accepted. The number ρ of customer commodities to remove from the current solution s follows the scheme proposed in [START_REF] François | Large neighborhood search for multitrip vehicle routing[END_REF], with the aim of applying small moves when a new solution has just been accepted, while applying large move when no new solutions has been accepted in the most recent iterations.

Removal and insertion heuristics

Classical removal and insertion heuristics ( [START_REF] Ropke | An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows[END_REF]) have been implemented. Removal heuristics are: random removal, worst removal and Shaw removal with a relatedness measure based on distance. Insertion heuristics are: greedy insertion and regret insertion. Worst removal and Shaw removal work with customers, while random removal can be applied either with customers or customer commodities. Insertion heuristics work with customer commodities.

Local search moves

In order to improve a solution, we apply a set of local search moves. Seven different moves are implemented. In the first three moves routes are considered as a set of customers. These moves are: (1) insert customer, (2) swap customers, (3) 2-opt of customers.

Then, we propose two other classical moves adapted for customer commodities: (4) insert customer commodity, and (5) swap customer commodities. We also propose two other moves: (6) erase route: from a given route, remove the customer commodities until no other route has capacity to accept another customer commodity; and (7) reassign commodities: for a given customer we propose a Mixed Integer Program to optimally assign all the commodities of this customer to the routes of the solution.

Given a feasible solution, all 7 moves are iteratively applied one after the other, until no one improves the solution. Then, routes of the current solution are concatenated and split algorithm is applied. If this gives a better solution, the procedure is repeated.

  Algorithm 1 Adaptive large neighborhood search 1: generate an initial solution s ∈ {solutions}, ρ ← 1, s best ← s 2: repeat

	3:

Preliminary results

The algorithm is implemented in C++ and run on a Intel (R) Core(TM) i7-6500U, 2.50GHz and 8GB of RAM. The instances are the ones proposed in [START_REF] Archetti | Multicommodity vs. singlecommodity routing[END_REF], based on the R101 and C101 Solomon instances for the VRP. We consider 3 sets of instances with up to 3 commodities: small instances with 15 customers, mid-sized instances with 20 customers or 80 customers.

Global results are reported in Table 1. We report the average, minimum and maximum gap (gap%) between the value we obtained and the best known solution in literature [START_REF] Archetti | A branch-price-and-cut algorithm for the commodity constrained split delivery vehicle routing problem[END_REF], the number of optimal values we obtained and the average computational time in seconds. The prospects are to implement specific removal and insertion heuristics. Moreover, the proposed method can then be extended to other versions of the problems, like multidepot version with a limited capacity of each commodity at the each depot.