Solving large-scale dial-a-ride vehicle routing and scheduling problems
June 1984
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Technical Report |
| Published: |
Cambridge : Massachusetts Institute of Technology, Flight Transportation Laboratory, 1984
2012
|
| Online Access: | http://hdl.handle.net/1721.1/68045 |
| _version_ | 1811089155488219136 |
|---|---|
| author | Jaw, Jang-Jei |
| author2 | Massachusetts Institute of Technology. Flight Transportation Laboratory |
| author_facet | Massachusetts Institute of Technology. Flight Transportation Laboratory Jaw, Jang-Jei |
| author_sort | Jaw, Jang-Jei |
| collection | MIT |
| description | June 1984 |
| first_indexed | 2024-09-23T14:14:34Z |
| format | Technical Report |
| id | mit-1721.1/68045 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T14:14:34Z |
| publishDate | 2012 |
| publisher | Cambridge : Massachusetts Institute of Technology, Flight Transportation Laboratory, 1984 |
| record_format | dspace |
| spelling | mit-1721.1/680452019-04-10T10:00:33Z Solving large-scale dial-a-ride vehicle routing and scheduling problems Dial-a-ride vehicle routing and scheduling problems Jaw, Jang-Jei Massachusetts Institute of Technology. Flight Transportation Laboratory June 1984 Also issued as a Ph. D. thesis, Massachusetts Institute of Technology, Dept. of Aeronautics and Astronautics, 1984 Includes bibliographical references (p. 221-224) In this thesis we develop two heuristic algorithms for large-scale multi-vehicle advance-request version of the dial-a-ride problem. This problem is concerned with developing a set of routes for a fleet of vehicles serving customers who have to be picked up from specified origins and be delivered to specified destinations. In this thesis it is assumed that each customer has specified either a desired pick-up time or a desired delivery time and that customer requests for service as well as the number of available vehicles throughout the time period of interest are known well in advance of the time of actual vehicle dispatching. The first heuristic approach consists of three successive and distinct steps: "grouping", "clustering" and "routing". Grouping divides customers into "time groups" on the basis of their desired pick-up and delivery times. Clustering separates customers in each time group into "clusters" and assigns vehicles to serve each cluster. Finally routing generates routes for each individual vehicle to serve every cluster in turn and for every time group. The second algorithm, Advanced Dial-A-Ride with Time Windows (ADARTW), treats customers' desired service times as strict constraints and can guarantee prespecified standards of service quality. The service quality constraints refer to guarantees that (i) customer's ride time will not exceed a pre-specified maximum and (ii) the service time will not deviate from the most desired time by more than a pre-specified amount ("the time windows"). The algorithm builds up vehicle tours through sequential insertion of customers and uses a nonlinear objective function to guide such insertions. Variations of this basic approach are also discussed. We have tested the two algorithms on many simulated cases using computer-generated data. Computational experience with a large-scale real world dial-a-ride problem (2617 customers and 30 simultaneously operating vehicles) is also presented. 2012-01-06T22:03:31Z 2012-01-06T22:03:31Z 1984 Technical Report 13194976 http://hdl.handle.net/1721.1/68045 FTL report (Massachusetts Institute of Technology. Flight Transportation Laboratory) ; R84-3 224 p application/pdf Cambridge : Massachusetts Institute of Technology, Flight Transportation Laboratory, 1984 |
| spellingShingle | Jaw, Jang-Jei Solving large-scale dial-a-ride vehicle routing and scheduling problems |
| title | Solving large-scale dial-a-ride vehicle routing and scheduling problems |
| title_full | Solving large-scale dial-a-ride vehicle routing and scheduling problems |
| title_fullStr | Solving large-scale dial-a-ride vehicle routing and scheduling problems |
| title_full_unstemmed | Solving large-scale dial-a-ride vehicle routing and scheduling problems |
| title_short | Solving large-scale dial-a-ride vehicle routing and scheduling problems |
| title_sort | solving large scale dial a ride vehicle routing and scheduling problems |
| url | http://hdl.handle.net/1721.1/68045 |
| work_keys_str_mv | AT jawjangjei solvinglargescaledialaridevehicleroutingandschedulingproblems AT jawjangjei dialaridevehicleroutingandschedulingproblems |