This paper addresses the problem of optimally routing and scheduling airport shuttle vehicles that offer pickup and drop-off services to customers through ridesharing. This problem, which is a version of the dial-a-ride problem, is formulated as a mixed integer program. For the solution, an exact approach applying constraint programming in a column generation framework and the adaptation of two existing heuristics are proposed. Implementations of the mathematical program and proposed solution approaches for three operational policies are presented. The performance of the proposed approaches in regard to computational requirements and solution quality was evaluated in a real-world case study involving service records for one service day out of Washington, D.C., Dulles International Airport in Chantilly, Virginia, provided by an actual airport shuttle service provider. Results show that the heuristics provide good approximations to the exact solution.
Get full access to this article
View all access options for this article.
References
1.
JunkerU., KarischS. E., KohlN., VaabenB., FahleT., and SellmannM.A Framework for Constraint Programming Based Column Generation.Proc., 5th International Conference on Principles and Practice of Constraint Programming, Springer, 1999.
2.
JawJ. J., OdoniA. R., PsaraftisH. N., and WilsonN. H. M.A Heuristic Algorithm for the Multivehicle Advance Request Dial-a-Ride Problem with Time Windows.Transportation Research Part B: Methodological, Vol. 20, No. 3, 1986, pp. 243–257.
3.
SolomonM. M.Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints.Operations Research, Vol. 35, No. 2, 1987, pp. 254–265.
4.
KolenA. W., KanA. R., and TrienekensH.Vehicle Routing with Time Windows.Operations Research, Vol. 35, No. 2, 1987, pp. 266–273.
5.
DantzigG. B., and RamserJ. H.The Truck Dispatching Problem.Management Science, Vol. 6, No. 1, 1959, pp. 80–91.
6.
DesrochersM., DesrosiersJ., and SolomonM.A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows.Operations Research, Vol. 40, No. 2, 1992, pp. 342–354.
7.
Prescott-GagnonE., DesaulniersG., and RousseauL. M.A Branch-and-Price-Based Large Neighborhood Search Algorithm for the Vehicle Routing Problem with Time Windows.Networks, Vol. 54, No. 4, 2009, pp. 190–204.
8.
BraysyI., and GendreauM.Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms.Transportation Science, Vol. 39, No. 1, 2005, pp. 104–118.
9.
BraysyI., and GendreauM.Vehicle Routing Problem with Time Windows, Part Ii: Metaheuristics.Transportation Science, Vol. 39, No. 1, 2005, pp. 119–139.
10.
DumasY., DesrosiersJ., and SoumisF.The Pickup and Delivery Problem with Time Windows.European Journal of Operational Research, Vol. 54, No. 1, 1991, pp. 7–22.
11.
WallaceN. E.Optimization in Dial-a-Ride System Analysis: A Comparison of Recent Modelling and an Expected Value Model.Highway Research Institute, University of Michigan, Ann Arbor, 1978.
12.
CordeauJ. F., and LaporteG.The Dial-a-Ride Problem: Models and Algorithms.Annals of Operations Research, Vol. 153, No. 1, 2007, pp. 29–46.
13.
ParraghS., DoernerK., and HartlR.A Survey on Pickup and Delivery Problems Part Ii: Transportation Between Pickup and Delivery Locations.Journal für Betriebswirtschaft, Vol. 58, No. 2, 2008, pp. 81–117.
14.
BerbegliaG., CordeauJ. F., GribkovskaiaI., and LaporteG.Static Pickup and Delivery Problems: A Classification Scheme and Survey.Top, Vol. 15, No. 1, 2007, pp. 1–31.
15.
GribkovskaiaI., and LaporteG.One-to-Many-to-One Single Vehicle Pickup and Delivery Problems. In The Vehicle Routing Problem: Latest Advances and New Challenges (GoldenB., RaghavanS., and WasilE., eds.), Springer, New York, 2008, pp. 359–377.
16.
ParraghS., DoernerK., and HartlR.A Survey on Pickup and Delivery Problems Part I: Transportation Between Customers and Depot.Journal für Betriebswirtschaft, Vol. 58, No. 1, 2008, pp. 21–51.
17.
AngelelliE., and MansiniR.The Vehicle Routing Problem with Time Windows and Simultaneous Pick-up and Delivery. In Quantitative Approaches to Distribution Logistics and Supply Chain Management (KloseA., SperanzaM. G., and Van WassenhoveL. N., eds.), Springer-Verlag, Berlin, 2002, pp. 249–267.
18.
YanoC. A., ChanT. J., RichterL. K., CulterT., MurtyK. G., and McGettiganD.Vehicle Routing at Quality Stores.Interfaces, Vol. 17, No. 2, 1987, pp. 52–63.
19.
GélinasS., DesrochersM., DesrosiersJ., and SolomonM. M.A New Branching Strategy for Time Constrained Routing Problems with Application to Backhauling.Annals of Operations Research, Vol. 61, No. 1, 1995, pp. 91–109.
20.
DethloffJ.Vehicle Routing and Reverse Logistics: The Vehicle Routing Problem with Simultaneous Delivery and Pick-Up.Or Spektrum, Vol. 23, No. 1, 2001, pp. 79–96.
21.
ThangiahS. R., PotvinJ. Y., and SunT.Heuristic Approaches to Vehicle Routing with Backhauls and Time Windows.Computers and Operations Research, Vol. 23, No. 11, 1996, pp. 1043–1057.
22.
KontoravdisG., and BardJ. F.A Grasp for the Vehicle Routing Problem with Time Windows.ORSA Journal on Computing, Vol. 7, No. 1, 1995, pp. 10–23.
23.
DuhamelC., PotvinJ.-Y., and RousseauJ.-M.A Tabu Search Heuristic for the Vehicle Routing Problem with Backhauls and Time Windows.Transportation Science, Vol. 31, No. 1, 1997, pp. 49–59.
24.
ZhongY., and ColeM. H.A Vehicle Routing Problem with Backhauls and Time Windows: A Guided Local Search Solution.Transportation Research Part E: Logistics and Transportation Review, Vol. 41, No. 2, 2005, pp. 131–144.
25.
TasanA. S., and GenM.A Genetic Algorithm Based Approach to Vehicle Routing Problem with Simultaneous Pick-up and Deliveries.Computers and Industrial Engineering, Vol. 62, No. 3, 2012, pp. 755–761.
26.
ParaphantakulC., Miller-HooksE., and OpasanonS.Scheduling Deliveries with Backhauls in Thailand's Cement Industry. In Transportation Research Record: Journal of the Transportation Research Board, No. 2269, Transportation Research Board of the National Academies, Washington, D.C., 2012, pp. 73–82.
27.
RopkeS., and CordeauJ. F.Branch and Cut and Price for the Pickup and Delivery Problem with Time Windows.Transportation Science, Vol. 43, No. 3, 2009, pp. 267–286.
28.
IrnichS., and DesaulniersG.Shortest Path Problems with Resource Constraints. In Column Generation (DesaulniersG., DesrosiersJ., and SolomonM. M., eds.), Springer, New York, 2005, pp. 33–65.
