Minimal‐cost route planning via Fibonacci‐heap‐typed data structure

Abstract

Abstract Efficient route planning in transportation networks, particularly under stochastic conditions like severe weather (i.e. snow or hail), poses a significant computational challenge. This article addresses this challenge by modeling the route planning problem as a Markov decision process (MDP) problem, establishing reachability criteria, and identifying the minimum‐weight arborescence in the directed graph. To achieve this, the reachability determination algorithm is designed to assess the courier company's reachability to all junctions based on the queue‐typed data structure and breadth‐first search idea. Subsequently, the minimal‐cost route planning algorithm is developed to find a feasible transport route with the minimal cost of clearing obstacles by resorting to the Edmonds' algorithm and some feasible data structures. In particular, the article introduces a Fibonacci‐heap‐typed data structure to the minimal‐cost route planning algorithm, resulting in a remarkable reduction of the time complexity from O(mn) to O(m+nlogn), where m and n represent the cardinalities of the arc set and nodeset, respectively. Ultimately, the proposed method is applied to optimize route planning in a transportation network, providing a cost‐efficient solution for logistics and transportation planning.

Keywords

• graphs
• graph theory
• matrix algebra
• Markov processes
• network theory (graphs)