Special Issue "Algorithms for Shortest Paths in Dynamic and Evolving Networks"

A special issue of Algorithms (ISSN 1999-4893). This special issue belongs to the section "Evolutionary Algorithms and Machine Learning".

Deadline for manuscript submissions: 15 May 2021.

Special Issue Editors

Prof. Dr. Christos D. Zaroliagis
E-Mail Website
Guest Editor
Department of Computer Engineering and Informatics, University of Patras, 26504 Patras, Greece
Interests: innovative algorithmic technology; data-driven and scalable computing; large-scale optimization; intelligent transportation systems and services; decentralized computing; mobility in smart cities; cryptography and information security
Dr. Daniel Delling
E-Mail Website
Guest Editor
Apple Inc.
Interests: design, analysis, and implementation of efficient algorithms and data structures

Special Issue Information

Dear Colleagues,

Contemporary technological infrastructures are dominated by a multitude of networks (transportation networks, social networks, communication networks, e-commerce networks, power networks, etc.) that are typically of a very large scale and impose as a routine task the computation of min-cost paths, while their characteristics usually evolve with time. The dynamicity and temporality of the network characteristics is often depicted by some kind of predetermined dependence of the metric on the actual time that each resource is used (e.g., traversal time of individual segments in road networks, packet-loss rate in IT networks, arc availability in social networks, etc.).

The aim of this Special Issue is to seek new algorithmic approaches for computing shortest paths in networks that change over time for several reasons. A typical (but nonexhaustive) list includes network changes either due to the nature of an underlying metric (time-dependent networks), or the insertion/deletion of nodes and arcs (dynamic networks), or the availability of arcs at specific time slots (temporal networks), or the uncertainty of arc costs (stochastic networks), or the fact that each arc is equipped with more than one arc-cost vector (parametric networks).

Original contributions are solicited on new shortest-path algorithms on dynamic and evolving networks, which can belong to the broad spectrum of design, analysis, and engineering of algorithms, and include theoretical design and analysis, extensive experimentation and algorithm engineering, and heuristics. Moreover, high-quality survey contributions will also be considered.

Topics of interest include (but are not limited to) the following:

  • Approximate shortest-path algorithms;
  • Algorithm engineering;
  • Multimodal route planning;
  • Uni- and multicriteria route planning;
  • Parametric shortest-path algorithms;
  • Shortest paths in dynamic networks;
  • Shortest-path heuristics;
  • Shortest paths in time-dependent networks;
  • Shortest-path oracles;
  • Shortest paths in temporal networks;
  • Shortest paths in social networks;
  • Centrality assessment in social networks;
  • Stochastic shortest paths.

Prof. Dr. Christos D. Zaroliagis
Dr. Daniel Delling
Guest Editors

Manuscript Submission Information

Manuscripts should be submitted online at www.mdpi.com by registering and logging in to this website. Once you are registered, click here to go to the submission form. Manuscripts can be submitted until the deadline. All papers will be peer-reviewed. Accepted papers will be published continuously in the journal (as soon as accepted) and will be listed together on the special issue website. Research articles, review articles as well as short communications are invited. For planned papers, a title and short abstract (about 100 words) can be sent to the Editorial Office for announcement on this website.

Submitted manuscripts should not have been published previously, nor be under consideration for publication elsewhere (except conference proceedings papers). All manuscripts are thoroughly refereed through a single-blind peer-review process. A guide for authors and other relevant information for submission of manuscripts is available on the Instructions for Authors page. Algorithms is an international peer-reviewed open access monthly journal published by MDPI.

Please visit the Instructions for Authors page before submitting a manuscript. The Article Processing Charge (APC) for publication in this open access journal is 1400 CHF (Swiss Francs). Submitted papers should be well formatted and use good English. Authors may use MDPI's English editing service prior to publication or during author revisions.

Keywords

  • Shortest-path algorithms
  • Route planning
  • Parametric shortest paths
  • Temporal networks
  • Dynamic networks
  • Time-dependent networks
  • Social networks
  • Stochastic shortest paths

Published Papers (5 papers)

Order results
Result details
Select all
Export citation of selected articles as:

Research

Open AccessArticle
Space-Efficient, Fast and Exact Routing in Time-Dependent Road Networks
Algorithms 2021, 14(3), 90; https://0-doi-org.brum.beds.ac.uk/10.3390/a14030090 - 16 Mar 2021
Viewed by 385
Abstract
We study the problem of quickly computing point-to-point shortest paths in massive road networks with traffic predictions. Incorporating traffic predictions into routing allows, for example, to avoid commuter traffic congestions. Existing techniques follow a two-phase approach: In a preprocessing step, an index is [...] Read more.
We study the problem of quickly computing point-to-point shortest paths in massive road networks with traffic predictions. Incorporating traffic predictions into routing allows, for example, to avoid commuter traffic congestions. Existing techniques follow a two-phase approach: In a preprocessing step, an index is built. The index depends on the road network and the traffic patterns but not on the path start and end. The latter are the input of the query phase, in which shortest paths are computed. All existing techniques have large index size, slow query running times or may compute suboptimal paths. In this work, we introduce CATCHUp (Customizable Approximated Time-dependent Contraction Hierarchies through Unpacking), the first algorithm that simultaneously achieves all three objectives. The core idea of CATCHUp is to store paths instead of travel times at shortcuts. Shortcut travel times are derived lazily from the stored paths. We perform an experimental study on a set of real world instances and compare our approach with state-of-the-art techniques. Our approach achieves the fastest preprocessing, competitive query running times and up to 38 times smaller indexes than competing approaches. Full article
(This article belongs to the Special Issue Algorithms for Shortest Paths in Dynamic and Evolving Networks)
Show Figures

Figure 1

Open AccessArticle
An FPTAS for Dynamic Multiobjective Shortest Path Problems
Algorithms 2021, 14(2), 43; https://0-doi-org.brum.beds.ac.uk/10.3390/a14020043 - 29 Jan 2021
Viewed by 691
Abstract
The Dynamic Multiobjective Shortest Path problem features multidimensional costs that can depend on several variables and not only on time; this setting is motivated by flight planning applications and the routing of electric vehicles. We give an exact algorithm for the FIFO case [...] Read more.
The Dynamic Multiobjective Shortest Path problem features multidimensional costs that can depend on several variables and not only on time; this setting is motivated by flight planning applications and the routing of electric vehicles. We give an exact algorithm for the FIFO case and derive from it an FPTAS for both, the static Multiobjective Shortest Path (MOSP) problems and, under mild assumptions, for the dynamic problem variant. The resulting FPTAS is computationally efficient and beats the known complexity bounds of other FPTAS for MOSP problems. Full article
(This article belongs to the Special Issue Algorithms for Shortest Paths in Dynamic and Evolving Networks)
Show Figures

Figure 1

Open AccessArticle
Dynamic Shortest Paths Methods for the Time-Dependent TSP
Algorithms 2021, 14(1), 21; https://0-doi-org.brum.beds.ac.uk/10.3390/a14010021 - 12 Jan 2021
Viewed by 557
Abstract
The time-dependent traveling salesman problem (TDTSP) asks for a shortest Hamiltonian tour in a directed graph where (asymmetric) arc-costs depend on the time the arc is entered. With traffic data abundantly available, methods to optimize routes with respect to time-dependent travel times are [...] Read more.
The time-dependent traveling salesman problem (TDTSP) asks for a shortest Hamiltonian tour in a directed graph where (asymmetric) arc-costs depend on the time the arc is entered. With traffic data abundantly available, methods to optimize routes with respect to time-dependent travel times are widely desired. This holds in particular for the traveling salesman problem, which is a corner stone of logistic planning. In this paper, we devise column-generation-based IP methods to solve the TDTSP in full generality, both for arc- and path-based formulations. The algorithmic key is a time-dependent shortest path problem, which arises from the pricing problem of the column generation and is of independent interest—namely, to find paths in a time-expanded graph that are acyclic in the underlying (non-expanded) graph. As this problem is computationally too costly, we price over the set of paths that contain no cycles of length k. In addition, we devise—tailored for the TDTSP—several families of valid inequalities, primal heuristics, a propagation method, and a branching rule. Combining these with the time-dependent shortest path pricing we provide—to our knowledge—the first elaborate method to solve the TDTSP in general and with fully general time-dependence. We also provide for results on complexity and approximability of the TDTSP. In computational experiments on randomly generated instances, we are able to solve the large majority of small instances (20 nodes) to optimality, while closing about two thirds of the remaining gap of the large instances (40 nodes) after one hour of computation. Full article
(This article belongs to the Special Issue Algorithms for Shortest Paths in Dynamic and Evolving Networks)
Show Figures

Figure 1

Open AccessArticle
A Discrete-Continuous Algorithm for Free Flight Planning
Algorithms 2021, 14(1), 4; https://0-doi-org.brum.beds.ac.uk/10.3390/a14010004 - 25 Dec 2020
Viewed by 582
Abstract
We propose a hybrid discrete-continuous algorithm for flight planning in free flight airspaces. In a first step, our discrete-continuous optimization for enhanced resolution (DisCOptER) method computes a globally optimal approximate flight path on a discretization of the problem using the A* method. This route initializes a Newton method that converges rapidly to the smooth optimum in a second step. The correctness, accuracy, and complexity of the method are governed by the choice of the crossover point that determines the coarseness of the discretization. We analyze the optimal choice of the crossover point and demonstrate the asymtotic superority of DisCOptER over a purely discrete approach. Full article
(This article belongs to the Special Issue Algorithms for Shortest Paths in Dynamic and Evolving Networks)
Show Figures

Graphical abstract

Open AccessArticle
A Dynamic Route-Planning System Based on Industry 4.0 Technology
Algorithms 2020, 13(12), 308; https://0-doi-org.brum.beds.ac.uk/10.3390/a13120308 - 25 Nov 2020
Viewed by 679
Abstract
Due to the availability of Industry 4.0 technology, the application of big data analytics to automated systems is possible. The distribution of products between warehouses or within a warehouse is an area that can benefit from automation based on Industry 4.0 technology. In [...] Read more.
Due to the availability of Industry 4.0 technology, the application of big data analytics to automated systems is possible. The distribution of products between warehouses or within a warehouse is an area that can benefit from automation based on Industry 4.0 technology. In this paper, the focus was on developing a dynamic route-planning system for automated guided vehicles within a warehouse. A dynamic routing problem with real-time obstacles was considered in this research. A key problem in this research area is the lack of a real-time route-planning algorithm that is suitable for the implementation on automated guided vehicles with limited computing resources. An optimization model, as well as machine learning methodologies for determining an operational route for the problem, is proposed. An internal layout of the warehouse of a large consumer product distributor was used to test the performance of the methodologies. A simulation environment based on Gazebo was developed and used for testing the implementation of the route-planning system. Computational results show that the proposed machine learning methodologies were able to generate routes with testing accuracy of up to 98% for a practical internal layout of a warehouse with 18 storage racks and 67 path segments. Managerial insights into how the machine learning configuration affects the prediction accuracy are also provided. Full article
(This article belongs to the Special Issue Algorithms for Shortest Paths in Dynamic and Evolving Networks)
Show Figures

Figure 1

Back to TopTop