Data processing: financial – business practice – management – or co – Automated electrical financial or business practice or... – Reservation – check-in – or booking display for reserved space
Reexamination Certificate
1998-04-01
2004-06-22
Hafiz, Tariq R. (Department: 3623)
Data processing: financial, business practice, management, or co
Automated electrical financial or business practice or...
Reservation, check-in, or booking display for reserved space
C705S005000, C705S001100
Reexamination Certificate
active
06754634
ABSTRACT:
MICROFICHE APPENDIX
This application includes a microfiche appendix including 2 sheets of microfiche and 163 frames of material.
TECHNICAL FIELD OF THE INVENTION
The present invention relates to the scheduling of transportation resources, and more particularly, to a method for heuristically constructing a schedule.
BACKGROUND OF THE INVENTION
Transportation scheduling is the process of planning how to move items from one location to another location using a fleet of carriers and under a set of restrictive constraints. One example is demand-response para-transit scheduling. In this example, wheelchair-bound and ambulatory customers make requests by telephone for round trip transportation from home to medical appointments, shopping, community centers, etc. . . . A fleet of vehicles must provide service under a multitude of constraints such as: (1) honoring a requested pick up time, (2) dropping the customer off before, but at most 60 minutes before, the appointment time, (3) and planning for much slower travel speed during rush hours.
Transportation scheduling takes a collection of trip requests as its set of subgoals, and a fleet of vehicles as its resources. The scheduling process constructs a set of manifests, one for each vehicle. A manifest is an ordered sequence of stop events. Each event has an associated location (either pickup or dropoff) and an assigned time.
The set of manifests or schedule must be realistic (known in the art as “streetability”), satisfy all domain constraints (known in the art as “correctness”), and be of high quality (known in the art as “goodness”).
Prior art attempts to solve the transportation scheduling problem have been varied and are exemplified by U.S. Pat. Nos. 5,715,165, 5,692,125, 5,623,413, 5,623,404, 5,619,695, 5,177,684, and 4,926,343. Although these prior art attempts have been moderately successful, some of these methods are computationally intensive. Thus, there is still a need for an easily implementable method for transportation scheduling that accurately models the problem and can be operated in real time.
SUMMARY OF THE INVENTION
An improved transportation scheduling method for scheduling a plurality of trips T
1
-T
n
using a plurality of vehicles V
1
-V
n
, each of said plurality of vehicles having a trip manifest is disclosed. The method comprises the steps of: (a) generating a usability matrix that determines which of said plurality of vehicles V
1
-V
n
is useable with each of said plurality of trips T
1
-T
n
; (b) determining a best trip of said plurality of trips T
1
-T
n
to be scheduled next; (c) determining a best vehicle from said plurality of vehicles V
1
-V
n
for accommodating said best trip; (d) determining a best insertion pair into said trip manifest of said best vehicle for said best trip and updating said trip manifest to include said best insertion pair; (e) updating said usability matrix to reflect the scheduling of said best trip on said best vehicle; and (f) repeating steps (a)-(e) until all of the trips in said plurality of trips T
1
-T
n
have been scheduled or determined to be unschedulable.
REFERENCES:
patent: 5832453 (1998-11-01), O'Brien
Hafiz Tariq R.
Perkins Coie LLP
Robinson-Boyce Akiba
LandOfFree
Method for scheduling transportation resources does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for scheduling transportation resources, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for scheduling transportation resources will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3362952