Scheduling Method for Demand‐Responsive Transportation System
Publication: Journal of Transportation Engineering
Volume 115, Issue 6
Abstract
This paper offers an addition to a family of previously proposed vehicle‐scheduling models for a demand‐responsive transportation system. The assumed operating environment consists of many‐to‐many travel demand, multi‐vehicle, advanced reservation, and time‐window constraint for pickup and dropoff times. The model builds vehicle schedules one vehicle at a time, maximizing the number of trip requests to be handled by each vehicle. The method follows a two‐step approach: building of an initial route, and insertion of additional trips into the initial route. In inserting trips to the initial route, the model checks feasibility of insertion for each trip first, and then identifies the maximum number of trips that can be inserted using a tree‐structured search technique. The proposed method is evaluated for a set of specific examples by examining the sum of time differences between the original and actual pickup and drop‐off times, and the number of vehicles required. The model is relatively straightforward in its computational procedure and offers possibilities of other applications.
Get full access to this article
View all available purchase options and get full access to this article.
References
1.
Alfa, A. S. (1986). “Scheduling of vehicles for transportation of elderly.” Transp. Planning and Tech., 11(3), 203–212.
2.
Allison, J. D., and Terrell, M. P. (1987). “Balancing vehicle loads with route length in routing problem.” Proc., World Productivity and Int. Industrial Engrg. Conf., Washington, D.C.
3.
Bodin, L., et al. (1981a). “Routing and scheduling of vehicles and crews: The state of the art.” Computers and Operations Res., 10(2), 1–211.
4.
Bodin, L., et al. (1981b). “The state of the art in the routing and scheduling of vehicles and crews.” Report No. UMTA‐URT‐41‐81‐1. Urban Mass Transp. Admin., Washington, D.C.
5.
Hung, H. K., Hall, W. G., and Chapman, R. E. (1985). Paratransit advanced routing and scheduling system documentation: Routing and scheduling dial‐a‐ride sub‐system. U.S. Dept. of Commerce, Nat. Bureau of Standards, Nat. Engrg. Lab., Ctr. for Appl. Math.
6.
Jaw, J. J., et al. (1986). “A heuristic algorithm for the multi‐vehicle advance request dial‐a‐ride problem with time‐windows.” Transp. Res. “B”20B(3), 243–257.
7.
Mishkoff, H. C. (1985). Understanding artificial intelligence. Texas Instrument Inc., Dallas, Tex.
8.
Psaraftis, H. M. (1983). “An exact algorithm for the single vehicle many‐to‐many dial‐a‐ride problem with time‐window.” Transp. Sci., 17(3), 351–357.
9.
Rhee, J.‐H. (1987). “Vehicle routing and scheduling strategies for demand responsive transportation systems.” Thesis presented to the University of Delaware, at Newark, Del., in partial fulfillment of the requrements for the degree of Doctor of Philosophy.
10.
Roy, S., et al. (1983). “The construction of routes and schedules for the transportation of the handicapped.” Working Paper, Publication No. 308, Centre de recherche sur les transports, Univ. of Montreal, Montreal, Quebec, Canada.
11.
Sexton, T. R., and Bodin, L. D. (1985a). “Optimizing single vehicle many‐to‐many operations with desired delivery times: I: Scheduling.” Transp. Sci., 19(4), 378–410.
12.
Sexton, T. R., and Bodin, L. D. (1985b). “Optimizing single vehicle many‐to‐many operations with desired delivery times: II: Routing.” Transp. Science, 19(4).
13.
Sexton, T. R. (1979). “The single vehicle many‐to‐many routing and scheduling problem.” Thesis presented to the State University of New York, at Stony Brook, N.Y., in partial fulfillment of the requirements for the degree of Doctor of Philosophy.
14.
Shirai, Y., and Tsujii, J. (1982). Artificial intelligence concepts, techniques and applications. John Wiley and Sons, New York, N.Y.
15.
Slagle, J. R. (1971). Artificial intelligence: The heuristic programming approach. McGraw Hill, Inc., New York, N.Y.
16.
Solomon, M. M., and Desrosier, J. (1988). “Survey paper: Time‐window constrained routing and scheduling problems.” Transp. Sci., 22(1).
17.
Wilson, N. H. M., and Miller, E. (1977). “Advanced dial‐a‐ride algorithm research project phase II: Interim report. Report R77‐31, Dept. of Civ. Engrg., Massachusetts Inst. of Tech., Cambridge, Mass.
Information & Authors
Information
Published In
Journal of Transportation Engineering
Volume 115 • Issue 6 • November 1989
Pages: 630 - 645
Copyright
Copyright © 1989 ASCE.
History
Published online: Nov 1, 1989
Published in print: Nov 1989
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.