TITLE:
Backward Dijkstra Algorithms for Finding the Departure Time Based on the Specified Arrival Time for Real-Life Time-Dependent Networks
AUTHORS:
Gelareh Bakhtyar, Vi Nguyen, Mecit Cetin, Duc Nguyen
KEYWORDS:
Backward Dijkstra, Dynamic Networks, Piece-Wise Linear Function, Specified Arrival Time
JOURNAL NAME:
Journal of Applied Mathematics and Physics,
Vol.4 No.1,
January
11,
2016
ABSTRACT:
A practical transportation problem for
finding the “departure” time at “all source nodes” in order to arrive at “some
destination nodes” at specified time for both FIFO (i.e., First In First Out)
and Non-FIFO “Dynamic ” Networks is considered in this study. Although shortest
path (SP) for dynamic networks have been studied/documented by various researchers,
contributions from this present work consists of a sparse matrix storage scheme
for efficiently storing large scale sparse network’s connectivity, a concept of
Time Delay Factor (TDF) combining with a “general piece- wise linear function”
to describe the link cost as a function of time for Non-FIFO links’ costs, and
Backward Dijkstra SP Algorithm with simple heuristic rules for rejecting
unwanted solutions during the backward search algorithm. Both small-scale
(academic) networks as well as large- scale (real-life) networks are
investigated in this work to explain and validate the proposed dynamic
algorithms. Numerical results obtained from this research work have indicated
that the newly proposed dynamic algorithm is reliable, and efficient. Based on
the numerical results, the calculated departure time at the source node(s), for
a given/specified arrival time at the destination node(s), can be non-unique,
for some Non-FIFO networks’ connectivity.