Algorithms for Linear Fractional Shortest Path Problem with Time Windows

The shortest path problem is one of the most important issues among network problems. In this paper, an extension of this problem is considered wherein each arc possesses two parameters (such as cost and time) and each node constrained by a time window. The object in this problem is to find a path between two specified nodes that minimizes cost per unit time without violating the time window constraints. Since such an objective involves minimizing the fraction of two linear objectives, it is called a linear fractional shortest path problem with time windows (LFSPTW). The time windows here are hard time windows. In order to avoid the encouragement of arriving early and wait to increase the denominator, there is a penalty Y will be charged to every unit waiting time. An optimal algorithm and a heuristic algorithm to solve the problem are proposed and compared. A sensitivity analysis is also carried out to study the effect of Y on the performance of these two algorithms.