题名

Algorithms for Linear Fractional Shortest Path Problem with Time Windows

DOI

10.30166/PPMR.200301.0004

作者

Jinshyang Roan

关键词

network flows ； shortest path ； algorithm ； time window

期刊名称

Pan-Pacific Management Review

卷期/出版年月

6卷1期（2003 / 01 / 01）

页次

75 - 83

内容语文

英文
英文摘要

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.
主题分类 社會科學 > 管理學
参考文献
  1. Bhatia, H. L.,K. Swamp,M. C. Puri.(1976).Time-Cost Trade-Off in a Transportation Problem.Operations Research,13,130-142.
  2. Bitran, G. R.,A. G. Novaes.(1973).Linear Programming with a Fractional Objective Function.Operations Research,21,22-29.
  3. Desrochers, M.,F. Soumis(1988).A Reoptimization Algorithm for The Shortest Path Problem with Time Windows.European Journal of Operational Research,35,242-254.
  4. Desrochers, M.,F. Soumis(1988).A generalized Permanent Labeling Algorithm for the Shortest Path Problem with Time Windows.INFOR,26,191-211.
  5. Desrosiers, J.,P. Pelletier,F. Soumis(1983).Plus Court Chemin Avec Contraints d`Horaires.RAIRO,17,357-377.
  6. Gallo, G.,S. Pallottino(1986).Shortest Path Methods: A Unifying Approach.Mathematical Programming Study,26,38-64.
  7. Gilsinn, J.,C. Witzgall(1973).NBS Technical Note 722.Washington, DC:Department of Commerce.
  8. Lindner-Dutton, L.,R. Batta,M. H. Karwan(1991).Equitable Sequencing of a Given Set of Hazardous Materials Shipment.Transportation Science,25,124-137.
  9. List, G. F.,P. B. Mirchandani,M. A. Turnquist,K. G. Zografos(1991).Modeling and Analysis for Hazardous Materials Transportation: Risk Analysis, Routing/Scheduling and Facility Location.Transportation Science,25,100-114.
print cancel