# An FPTAS for Dynamic Multiobjective Shortest Path Problems
## 3 The Multiobjective Dijkstra Algorithm for Dynamic MOSP Problems
### Description of the Algorithm
In total, the GRID - 3D instance set contains 300 One-to-One MOSP instances with varying \(L_{1}\) norm between the source and the target node. The last test instance is a Dyn-MOSP instance motivated by the Horizontal Flight Planning Problem (HFFPP) introduced in [26; 27]. The directed graph in this instance has \(410,387\) nodes and \(878,902\) arcs and is called an airway network. The arcs are the direct connections between pre-defined coordinates (the graph's nodes) along which commercial aircraft are allowed to fly (on www.skyvector.com Sky-Vector an airway network can be displayed). We define two cost functions on each arc. The first one encodes the duration of the traversal of an arc depending on the time point at which the tail of the arc is reached. The duration is influenced by weather conditions and we evaluate the weather information we have every 3h to get 10 data points per arc. The second function models the aircraft is fuel consumption along an arc depending on the aircraft is weight at the arc's tail node. In our model we get 171 initial weights per arc and the corresponding consumption for each weight. The difference between two consecutive weights is 500 kg. In both functions, datapoints are interpolated linearly, hence obtaining two continuous piecewise linear functions. The single pieces of the duration function can have positive or negative slopes depending on the wind but the FIFO property still holds as shown in [26]. The consumption function yields an always positive slope since clearly, a higher initial weight will cause a higher consumption. It is therefore also FIFO and, more importantly, the intercepts of its affine pieces are positive, hence fulfilling the requirements from Lemma 3. In total, we have randomly chosen 380 airports as the initial nodes \(s\) and compute the (pos)-efficient paths to all nodes reachable with the full tank of a long-haul aircraft. ### Results

The experiments were ran on a machine with an Intel Xeon CPU E5-2670 v2 @ 2.50 GHz processor. It has two CPUs per node and 10 cores per CPU. The available RAM was 128 GB. All algorithms were implemented in \(C\) and compiled with the version 7.5 of the GCC compiler with compiler optimization level set at 03. For the priority queues, we used our own implementation of a binary heap. The only difference between the heaps used for the implementations of [PERSON]'s algorithm and those used in the implementations of the MD algorithms is that in the former we took extra care of guaranteeing fast access to a node's

Figure 4: General EXP instance. Every path is efficient. heap labels. This is needed because every time a label for a node \(v\) is added to \(Q\), labels for \(v\) in \(Q\) that are dominated by the new one have to be removed. All lists of permanent labels are modelled as arrays, allowing all algorithms to share the code used for the dominance checks. We set a time limit of 5400 s for all algorithms. Whenever we report averages, we consider instances that were solved by all algorithms involved in the comparison. The min and max values consider only the results obtained by single algorithms. #### 5.2.1 Static Biobjective Results

Table 3 summarizes the results of the biobjective MOSP instances. On average, the BDA is 3450 times faster than [PERSON]'s algorithm in the EXP instance set. The average number of permanent labels on these instances is \(338,611\) and the maximum is \(1,572,862\). We computed \((1+\varepsilon)\)-covers for the EXP instances with different values for \(\varepsilon\) and the average speedup decreases steadily as \(\varepsilon\) grows: \(\times 30\) for \(\varepsilon=0.05\), \(\times 2.4\) for \(\varepsilon=0.5\), and \(\times 1,84\) for \(\varepsilon=1\). This is because 1.10%, 0.17%, and 0.11% of the labels from the exact solution sets are computed for the mentioned \(\varepsilon\) values.