{'fraction_non_alphanumeric': 0.03456513850247974, 'fraction_numerical': 0.009374621991048748, 'mean_word_length': 4.569984840828702, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Dynamic bi-objective routing of multiple vehicles

In practice, e.g. in delivery and service scenarios, Vehicle-Routing-Problems (VRPs) often imply repeated decision making on dynamic customer requests. As in classical VRPs, tours have to be planned short while the number of serviced customers has to be maximized at the same time resulting in a multi-objective problem. Beyond that, however, dynamic requests lead to the need for re-planning of not yet realized tour parts, while already realized tour parts are irreversible. In this paper we study this type of bi-objective dynamic VRP including sequential decision making and concurrent realization of decisions. We adopt a recently proposed Dynamic Evolutionary Multi-Objective Algorithm (DEMOA) for a related VRP problem and extend it to the more realistic (here considered) scenario of multiple vehicles. We empirically show that our DEMOA is competitive with a multi-vehicle offline and clairvoyant variant of the proposed DEMOA as well as with the dynamic single-vehicle approach proposed earlier.

At the same time, the number of vehicles is explicitly not considered as additional objective. To keep the scenario realistic, the number of vehicles can neither be changed during the optimization process nor in each era. A dynamic change in the number of used vehicles during the process would require most flexible (and thus costly) human resources and is therefore usually infeasible for a company. 1 Additionally, a third objective would turn the originally bi-objective problem in a more complex-to-handle decision scenario for the DM.
The goal and contribution of this work is twofold: 1. The dynamic multi-objective vehicle routing problem (MO-VRP) and the dynamic solution approach are extended towards a more realistic scenario by including multiple vehicles. We introduce a significantly changed algorithm within the interactive framework proposed in [3].
2. We analyze the benefit of multiple vehicles in dynamic vehicle routing and compare our approach to an (extended) version of an a-posteriori evolutionary solution approach for this problem [5]. This approach unrealistically knows of all service requests in advance (clairvoyant) and thus needs no dynamic decision making during optimization. Further, we compare the multi-vehicle approach to the dynamic approach by Bossek et al. [3] and investigate the activities of vehicles. The individual activities of vehicles provide information on whether each vehicle contributes to the solution or whether some vehicles stay idle. This evaluation can eventually justify our decision to not include the number of vehicles as third objective.
The work is structured as follows: the next section briefly reflects the related work, while Section 3 formally introduces the dynamic multi-objective problem as described by Bossek et al. [3]. Section 4 then details the algorithmic extensions. The experimental setup as well as empirical results are described and discussed in Sections 5 and 6. Section 7 finally concludes the work and highlights perspectives for future research.

Related work
As the traveling salesperson problem (TSP) is a major sub-problem of the here considered dynamic and multi-objective vehicle routing problem, this paper is naturally related to work on special TSPs, where not all customer locations (or cities) have to be visited. In research, these problems are sometimes referred to as orienteering problems [6], selective TSP [7,8], or as TSP with profits [9]. However, most of these problems are discussed as single-objective problems [10], although some early work already recognized the (at least) bi-objective character of these problems [11]. Only later work started to solve the orienteering problem in a bi-objective way using an -constraint approach [12] or approximation schemes [13] that produce Pareto-ε-approximations of the efficient solution set. While the both before mentioned approaches are based on repeated single-objective optimization, some authors [14,15,16,17,18] explicitly solve the bi-objective variants of the orienteering problem using an evolutionary algorithm, however, excluding service requests over time or considering the problem as a-posteriori (non-dynamic). Many of these approaches [14,16,17] introduce the number of vehicles as an objective to be minimized while simultaneously minimizing the tour length.
A related a-posteriori variant of the here considered dynamic problem is described by Grimme et al. [5], who propose an NSGA-II-based EMOA. This work has been extended later on by the integration of local search mechanisms [19] and the analysis of local search effects [4]. These works only allow one vehicle (like also described in [6,20]) but include the number of visited customers (revenue) as second objective besides tour length (costs).
While considering only one vehicle seems to be unrealistic, the inclusion of the number of vehicles as objective is only feasible in the a-posteriori and non-dynamic case. When problem instances change constantly due to customer requests (related examples from logistics and other domains can be found here: [21,22,23]) decision making is also a repetitive process over time. However, over time, decisions are constantly renewed building on past decisions which of course cannot be changed. In vehicle routing, one or more vehicles start at a depot and travel initially decided tours. Later on, new decisions have to take into account the current location as well as newly received or not yet serviced customer requests [3]. Rewinding of previous decisions (i.e. visits of customers) is impossible. As such, the initial decision for a fixed number of vehicles could only be changed by sending vehicles home or activating additional ones. This however, causes additional traveling costs and contradicts (in the real world) human resources' availability or labor regulations. Thus, it is most realistic not to consider the number of vehicles as additional objective in the dynamic case.
In general, dynamic vehicle routing is usually addressed by designing online decision rules, see e.g. [24,25]. According to Braekers et al. [26] only little work is available on dynamic multi-objective problems. In their sur-vey they mention authors who consider dynamics in service time windows and changing structures of the network [27,28,29,30,31].

Problem notation
The here considered dynamic multi-objective VRP can be denoted as follows: we consider a set of customer locations, which can be partitioned into three disjoint sets, The subset M contains all mandatory customers locations that are initially known and have to be visited, while the subset D contains all dynamic customers that appear over time and are not known to the algorithm beforehand. The third subset {N − 1, N } denotes the locations of the start and the end depot. Note that we consider the more general case here, in which start and end depot can be different. The more common special case of start and end depot being at the same location is of course included.
We consider two objectives in a minimization problem. The first objective aims for the minimization of the maximum tour length for all vehicles. Let n v be the number of vehicles and x a solution to the problem, then we denote the tour length for each vehicle i ∈ {1 . . . , n v } as L i (x) and determine f 1 (x) = max i L i (x). By using the maximum tour length as objective, we expect a balanced usage of vehicles in any solution. The second objective f 2 minimizes the number of unserved dynamic customers 2 .
Clearly, the objectives are in conflict and we need to adopt the notion of Pareto-optimality and dominance to describe compromise solutions for the resulting multi-objective optimization problem. For two solutions x and y, we denote x ≺ y (x dominates y), if x is not worse in any objective and better in at least one objective than y. The set of all non-dominated solutions in search space is called Pareto set; its image in objective space is called Pareto front [32].
As we consider a dynamic problem, anytime a dynamic customer requests service, the Pareto-set would have to be recomputed for the still unvisited mandatory and dynamic customers and a desired solution needs to be selected. As this is usually infeasible in practice, we discretize time and define n t intervals of length ∆ ∈ R ≥0 called eras that partition dynamic requests and subsequent decision making into phases [33].
At the onset t = (j − 1) · ∆ of each era j, new dynamic customer requests may have appeared. Based on this set and the remaining (not yet visited) mandatory customers in M , we can consider the problem as a static multi-objective optimization problem (MOP) and apply an EMOA to approximate the current Pareto-set. Then, a decision maker (DM) is provided with the compromises and allowed to pick a solution (i.e. a set of n v tours) which will be realized until the onset of the next era.
Note that in each era j > 0 the vehicle has started to realize a tour and possibly has already visited mandatory and/or dynamic customers. Naturally, already realized parts of earlier picked solutions are not reversible anymore. Thus, decisions made in earlier eras may have significant influence on later solutions. We address this challenge by introducing an automated decision making process as proposed in [3] and evaluating different configurations and decision chains, later on.

A Dynamic Multi-Objective Evolutionary Algorithm
Next we dive into the working principles and algorithmic details of the proposed DEMOA. The algorithm is a natural extension of the DEMOA proposed in [34] for the single-vehicle version of the considered bi-objective problem. The algorithmic steps are outlined in Alg. 1. The algorithm requires the following parameters: the problem instance comprising of the subsets M of mandatory and D of dynamic customers. Further parameters control the number and the length of eras (n t and ∆), the number of vehicles n v and EA-specific arguments like the population size µ and parameters controlling for the strength of mutation (details discussed later). We now describe the DEMOA procedure in general and discuss implementation details (initialization and variation) subsequently.

General (D)EMOA
Initialization steps (Alg. 1, lines 1-3) consist of declaring a population P and a list T where T v contains the tour of the corresponding vehicle v ∈ {1, . . . , n v }, i.e., T stores the solution the decision maker picked at the end of the previous era. Before the first era begins these tours are naturally empty since no planning was conducted at all. Line 4 iterates over the eras. Here, the actual optimization process starts. The first essential step in each era is -given the passed time t -to determine for each vehicle v ∈ {1, . . . , n v } the initial tour already realized by vehicle v. This Algorithm 1 DEMOA Require: a) Customer sets M , D, b) nr. of eras n t , c) era length ∆, d) nr. of vehicles n v , e) population size µ, f) prob. to swap p swap , g) nr. of swaps n swap 1: t ← 0 current time 2: P ← ∅ population (initialized below) 3: T ← list of tours empty at the beginning of 1st era 4: for i ← 1 to n t do era loop

5:
T ≤t ← list of n v partial tours already driven by vehicles at time t extracted from list T empty in 1st era 6: P ← INITIALIZE(µ, T ≤t , t, P ) see Alg. 2; pass last population of previous era as template 7: while stopping condition not met do EMOA loop 8: T ← CHOOSE(P ) DM makes choice list of n v tours 12: if P is empty then 1st era; no template given 4: x.v i ← random vehicle from {1, . . . , n v } for all i ∈ C 5: x.a i ← 1 for all i ∈ M 6: x.a i ← 0 for all i ∈ D 7: x.p ← random permutation of C = M ∪ D 8: else repair template 9: x ← P j ∈ P 10: x.a i ← 1 for all i ∈ T ≤t 11: x.v i ← vehicle nr. assigned to i in T ≤t

12:
In x.p move sub-sequence of driven tour in T ≤t at the beginning for each vehicle. 13: x.a i ← 1 for each i in random subset of D new 14: Q ← Q ∪ {x} return Q information is extracted from the list of tours T and stored in the list T ≤t . Note that again, in the first era the initial tours are empty, as is T , since the vehicles are all located at the start depot. Next, the population is initialized in line 6 and a static EMOA does his job in lines 7 − 10. Here, offspring solutions are generated by mutation followed by a sophisticated genetic local search procedure with the aim to reduce the tour lengths of solutions. Finally, following a (µ + λ)-strategy the population is updated. Therein, the algorithm relies on the survival selection mechanism of the NSGA-II algorithm [35]. Once a stopping condition is met, e.g., a maximum number of generations is reached, the era ends and the final solution set is presented to a decision maker who needs to choose exactly one solution (Alg. 1, line 11). This choice (the list T of n v tours) determines the (further) order of customers to be visited by the respective service vehicles.

Initialization
We strongly advice the reader to consult Alg. 2 and in particular Fig. 1 in the course of reading the following explanations for visual support. Each individual is built of three vectors x.v, x.a and x.p of length N − 2 each of which stores information on the vehicles assigned, the activation status of each customer and a permutation of all customers. In the first era there are no already visited customers, i.e. both P and T ≤t are empty, and the algorithm does not need to take these into account. Hence, in lines 4-7 each individual x ∈ P is created from scratch as follows: each customer i ∈ (M ∪ D) is assigned a vehicle v ∈ {1, . . . , n v } uniformly at random. This information is stored in the vector x.v. Next, all mandatory customers i ∈ M are activated by setting the value of a binary string x.a ∈ {0, 1} N −2 to 1 which means "active". In contrast, all dynamic customers i ∈ D are deactivated (x.a i = 0) since they did not ask 1: D av ← dyn. customers available at time t and not in T ≤t 2: C av ← all customers available at time t and not in T ≤t 3: Exchange n swap times each two nodes from C av in x.t return x for service so far. The final step is to store a random permutation of all customers in the permutation vector x.p. Note that during fitness function evaluation in order to calculate the individual tour lengths Initialization in later eras is different and more complex. Now, the parameter P passed to Alg. 2 -the final population of the previous era -is non-empty and its solutions serve as templates for the new population. We aim to transfer as much information as possible. However, usually the majority of individuals x ∈ P is in need of repair. This is because as time advances (note that additional ∆ time units have passed) further customers i ∈ C may already have been visited by the vehicle fleet, but it is possible that some of these are inactive in x (i.e., x.a i = 0). Hence, (a) all customers which have already been visited, stored in the list T ≤t , are activated and assigned to the responsible vehicle (here we use an overloaded element-of relation on lists in the pseudo-codes for convenience) and (b) furthermore their order in the permutation string x.p is repaired. The latter step is achieved by moving the sub-sequence of visited customers before the remaining customers assigned to the corresponding vehicle in the permutation string. This step completes the repair procedure and the resulting individual is guaranteed to be feasible. Subsequent steps involve randomly activating customers that asked for service within the last ∆ time units.

Offspring generation
The mutation operator (see Alg. 3) is designed to address all three combinatorial aspects of the underlying problem, i.e., vehicle re-assignment, customer (de)activation and tour permutation. Here, special attention has to be paid to not produce infeasible individuals. Therefore, mutation operates on the subset of customers which have asked for service until now and have not yet been visited. More precisely, each dynamic customer i ∈ D av = (D ≤t \ T ≤t ) which has not yet been visited is (de)activated with a small probability p a (note that we treat the list T ≤t as a set here for convenience). Likewise, each of the customers i ∈ C ≤t = (C ≤t \ T ≤t ) is assigned another vehicle independently with equal probability p v . The mutation probabilities p a and p v are set dynamically such that in expectation only one (de)activation or (re)assignment happens; small changes are preferred. Finally, with probability p swap the permutation vector x.p undergoes n swap sequential exchange/swap operations (limited to customers which are not fixed so far). Occasionally, at certain iterations, a local search (LS) procedure is applied to each individual x ∈ P (see line 9 in Alg. 1). The LS takes the vehicle mapping x.v and customer activation x.a as fixed and aims to improve the individual path length by means of the sophisticated solver EAX [36] for the Traveling-Salesperson-Problem (TSP).
To accomplish this goal, given a solution x ∈ P and a vehicle v ∈ {1, . . . , n v } all customers assigned to v in x (appending start and end depot) and their pairwise distances are extracted (nodes 1, 3, 5, 7, 8 for vehicle 1 in Fig. 1). Next, since the optimization of each vehicle tour is a Hamilton-Path-Problem (HPP) on the assigned customers (no round-trip tour), a sequence of distance matrix transformations is necessary such that the TSP solver EAX can be used to find an approximate solution to the HPP (see [37] for details). Again, since partial tours might already have been realized, the HPP-optimization starts at the last node visited by the corresponding vehicle (node 5 in Fig. 1 for vehicle 1, since T ≤t 1 = (1, 5) is fixed already and not subject to changes).

Experimental Methodology
Our benchmark set consists of in total 50 instances with each n = 100 customers taken from [19]. There are 10 instances with points spread uniformly at random in the Euclidean plane and each 10 clustered instances with the number of clusters n c ∈ {2, 3, 5, 10}. The cluster centers are placed by space-filling Latin-Hypercube-Sampling to ensure good spread. Subsequently, n/n c nodes are placed around each cluster center assuring cluster segregation with no overlap. We refer the reader to [19] for more details on the instance generation process. The proportion of dynamic customers is 50% and 75% for each half of the instance set enabling the study of highly dynamic scenarios.

Parameter Value
Nr. of function evaluations per era 65 000 Population size µ 100 Swap probability p swap 0.6 Nr. of swaps n swap 10 Local Search at generations first, half-time, last

Dynamic aspects and decision making
We fix n t = 7 eras and set the era-length to ∆ = max i∈D r(i)/n t where r(i) is the request time of customer i. ∆ is consistently ≈ 150 time units across all instances. Naturally, one could start a new epoch once a new customer requests for service. This would result in 50 and 75 eras respectively on our benchmark instances 3 . However, we argue that in a real-world scenario it is more realistic to make decisions after chunks of requests came in and not every single time.
For computational experimentation we automate the decision-making process by considering three different decision maker (DM) strategies. To do so, at the end of each era, we sort the final DEMOA population P in ascending order of the first objective (tour length), i.e. P (1) ≤ P (2) ≤ . . . ≤ P (µ) where the ≤-relation is with respect to f 1 . Note that in the bi-objective space this sorting results in a descending order with respect to the number of unvisited dynamic customers, our second objective (f 2 ). The automatic DM now picks the solution where increasing d-values correspond to stronger "customer-greediness", i.e. higher emphasis on keeping the number of unvisited customers low. In our study we cover d ∈ {0.25, 0.5, 0.75} to account for different levels of greediness and refer to such a policy as a d-strategy in the following. Certainly, in real-world scenarios, the DM might change his strategy throughout the day reacting to specific circumstances. However, for a systematic evaluation and to keep our study within feasible ranges, we stick to this subset of decision policies.

Further parameters
The further parameter settings of the DEMOA stem from preliminary experimentation and are gathered in Table 1. For each number of vehicles n v ∈ {1, 2, 3} and each DM strategy d ∈ {0.25, 0.5, 0.75} we run the DEMOA 30 times on each instance for n t eras following the d-strategy. Moreover, for a baseline comparison, we run the clairvoyant EMOA multiple times for each n v on each instance with a stopping condition of 20 000 000 function evaluations. The clairvoyant EMOA works the same way the DEMOA does. However, it has complete knowledge of the request times of dynamic customers a-priori and treats the problem as a static problem. 4 This idea was originally introduced in [5] for an a-posteriori evaluation of decision making for the single-vehicle variant of the considered problem. We use the Pareto-front approximations of the clairvoyant EMOA as a baseline for performance comparison. We provide the R implementation of our algorithm in an accompanying repository [38].

Experimental results
In the following, we analyze the proposed dynamic approach (DEMOA) for one to three vehicles with an adapted clairvoyant implementation of the original approach by Bossek et al. [4]. For a fair comparison, that approach has been extended to deal with multiple vehicles and is denoted as EMOA in the following results. In a first step, we show exemplary results of our dynamic approach to visually introduce the era concept. In continuation of the approach of Bossek et al. [3], we also briefly investigate the influence of decision making to final decision location, when different greediness preferences are considered. Then, we compare the performance of the EMOA and the proposed DEMOA with respect to three different performance measures. In detail, we investigate the overall performance with respect to problem type and fleet size, the performance with respect to different decision strategies, and the overall performance gain induced by using multiple vehicles. Finally, we zoom into dedicated solution instances (and their dynamic evolution process) to learn about the behavior of vehicles on clustered and uniform problem instances.

Pareto-front approximations and decisions in the dynamic scenario
The dynamic nature of the problem and online decision making imply that we do not have a single point in time at which the algorithm performance can be evaluated. In the beginning only mandatory customers are available and the tour planning task is equivalent to (multi-vehicle and open) TSP solving. However, as dynamic customer requests appear over time, the initially planned tour(s) must be modified to allow compromises between tour length and number of visited customers. From this point on, a Pareto-set of solutions has to be considered. Following the era concept of decision making, at a dedicated point in time, a compromise is chosen for realization by a DM. From that time onward, realization starts and vehicles travel the decided tour. Of course, new dynamic requests appear over time. These are considered at the end of the next era and form a set of new compromises. However, that set of compromises has to consider the already realized partial tour of the vehicles, which cannot be reverted. Consequently, already visited (formerly) dynamic customers reduce the upper bound of unserved customers in compromise sets for future decisions. The effect of repeated decision making and continuous realization of decisions is exemplarily shown in Figure 2. The non-dominated fronts for decisions in all seven eras are shown for a uniform and a clustered instance, respectively. For visual comparison, the clairvoyant EMOA results are also shown. Horizontal dashed lines denote the upper bound of unserved dynamic customers in each stage of decision making. Clearly, in the last era (7, brown points), more customers have been visited by the traveling vehicles than in the first era. Thus, the upper bound has decreased. The upper bound and the range of possible decisions is also depending on the decision strategy. A greedy strategy, which aims to reduce the number of unserved customers will favor solutions with many served customers and thus influence realization of longer tours. Less greedy strategies will favor realizations with shorter tours and less visited customers. This behavior was already observed by Bossek et al. [3] for a single vehicle. In Figure 3, we confirm an analogous behavior also for multiple vehicles and our algorithmic approach. Therein, visualizations of the results of different strategies (0.25, 0.5, and 0.75 priority of the second objective) and multiple runs for different topologies (uniform and clustered) as well as for different numbers of vehicles are shown. We find, that decision strategies are reflected in the final decision locations. The less greedy strategy produces solutions with more unserved customers than very greedy strategies -independent of the vehicle number.

Dynamic and clairvoyant performance and the influence of multiple vehicles
In order to evaluate the approximation quality of the DEMOA, the dynamic nature of the problem has to be respected. From the decision maker's perspective, the last era (and thus the last non-dominated front) includes all previous decisions and can be compared with the clairvoyant results. However, due to the continuously decreasing upper bounds of unserved customers during the optimization process (see 6.1), the EMOA approximation covers a wider range of solutions than the approximated Pareto-front of the final era. This is considered by our comparison of equivalent ranges of the DEMOA and EMOA results.
In Figure 4, we compare the Hypervolume indicator [39] of the DEMOA and EMOA by (1) determining instance-wise the minimal upper bound for the number of unserved customers (objective f 2 ) in the last approximated Pareto-front and for all independent runs of the DEMOA. Then (2), we reduce the solutions of the EMOA to those below the before determined upper bound for f 2 . From the union of the reduced EMOA results and the DEMOA results, we (3) compute a reference point for Hypervolume computation. Here we compare both algorithms for the medium greedy 0.5 strategy. We find, that the DEMOA results outperform the EMOA results for uniform problem instances with both 50% and 75% dynamic customers. For clustered instances, performance is in the same range but seemingly depending on the specific instance topology and dynamic customer ratio and service request times. However, we can conclude that the results of the DEMOA for the more realistic dynamic scenario are not necessarily worse than those of the clairvoyant approach. While the clairvoyant EMOA approach knows about the request times of all dynamic customers at t = 0 and considers all potential customers in compromise generation, the DEMOA optimizes tours of era i + 1 based on partially realized (and unchangeable) tours from era i. This often reduces the size of the tour planning problem significantly and allows to gain very good solutions -some of those even outperform the EMOA solutions in uniform instances.
Another observation from Figure 4 shows that the aforementioned advantage of problem complexity reduction due to dynamism becomes neglectable, when both algorithms consider multiple vehicles. With increasing number of vehicles, the EMOA tends to outperform the approximation quality of the DEMOA.
While we focused on a single decision strategy in the previous discussion, Figure 5 investigates multiple strategies together with tour length properties. Instead of the hypervolume, we now focus on the tour length objective (f 1 ) and  measure the distance of solutions to the clairvoyant solution. The idea behind this measure is, that (in the range of the common objective space of DEMOA and EMOA) usually any number of unvisited dynamic customers is covered by the approximated Pareto-front. The convergence quality of a solution set can thus also be expressed by the difference of DEMOA tour length and EMOA tour length. If DEMOA outperforms EMOA, the respective value is negative. The equilibrium of solution quality is denoted by a gray vertical line at 0 in Figure 5.
While we are able to confirm the general observations from above, we now have detailed insights into the effect of decision strategies. As a clear trend, we find better tour lengths per instance topology and dynamism, when greediness in decision making w.r.t. reduction of number of unserved customers (f 2 ) is increased. This holds for the single and Nr. of vehicles / algorithm Dominated Hypervolume Figure 7: Classical dominated hypervolume distributions (higher is better) of representative instances. The trend is the same for all 50 benchmark instances. multiple vehicle case. The reason for this observation is similar to the argument discussed before. The more customers have to be serviced, the more complex the tour planning problem becomes for the clairvoyant EMOA, while more and more customers are fixed in the dynamic scenario and do not have to be considered for tour planning anymore.
A dedicated view on the effect of using multiple vehicles in the scenario (online and offline) is provided in Figure 7. We find for all investigated cluster configurations and the uniform distribution of customers, that multiple vehicles are advantageous regarding classical hypervolume comparison 5 ; the results are statistically highly significant with respect to Wilcoxon-Mann-Whitney tests at significance level α = 0.001 in 100% of the cases, i.e. two vehicles are significantly better than one and three better than two. At the same time, we observe that the highest gain in solution quality is associated with the step from one to two vehicles. By including a third vehicle, only little is gained. This is probably rooted in the overhead associated with the distances travelled from the start depot to the first customer and from the last customer to the end depot. These distances occur for each vehicle and have to be travelled no matter how short the remaining tour becomes. Thus, this overhead will naturally bound the amount of reasonably applicable vehicles.

Exemplary analysis of vehicle tours
In this paragraph, we briefly investigate representative examples of generated solutions. Figure 6 details the evolution of tours for a single vehicle as well as two, and three vehicles for a uniform and clustered instance in eras one, three, and 7. In the single vehicle case, we can just observe the dynamic adaptation of the planned tour (thin line) towards the realized (and irreversible) tour (bold lines) over time. In the two and three vehicle scenarios, we can nicely observe, how the vehicles automatically partition the customers space. It is obvious, that no vehicle stays idle. Moreover, we find, that each vehicle is assigned similar workload. This behavior is partly rooted in the design of our algorithm. As objective f 1 minimizes the maximum tour length across all vehicles, selection pressure forces similar workload to each vehicle. Future research has to clarify, whether this desirable feature from a real-world application perspective is always advantageous from the optimization perspective.

Conclusion and Outlook
In this work, we successfully extended an already high-performing single-vehicle approach to the more realistic dynamic multiple vehicle scenario and we proposed two measures for comparing DEMOA quality to the performance of the related clairvoyant EMOA variant. We find that the algorithmic enhancements ensure a nice distribution of workload (in terms of tour lengths and number of customers served) between the involved vehicles without the necessity for explicitly optimizing for this kind of balance. At the same time and especially on instances with random uniformly distributed locations, the DEMOA can even outperform the offline EMOA variant with full knowledge of request times. Due to concurrent realization of planned tours, Pareto front approximations of the DEMOA's decision eras naturally concentrate on constantly shrinking problem sizes. These reduced problems can then be solved more effectively than the complete (offline) problem. Also, variations of decision makers' preferences and decision chains were investigated. With increasing degree of "greediness", i.e. a stronger focus on minimizing the number of unserved customers, of course overall tour lengths increase, both in the single-as well as in the multiple vehicle scenario. The informative and sophisticated visualization approaches presented here can possibly foster the facilitation of decision processes along the DEMOA run and may offer perspectives for future dynamic, tool-based decision support systems.