IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v42y2008i3p279-291.html
   My bibliography  Save this article

Per-Seat, On-Demand Air Transportation Part II: Parallel Local Search

Author

Listed:
  • D. Espinoza

    (School of Industrial Engineering, Universidad de Chile, Santiago, Chile)

  • R. Garcia

    (DayJet Corporation, Boca Raton, Florida 33431)

  • M. Goycoolea

    (School of Business, Universidad Adolfo Ibáñez, Santiago, Chile)

  • G. L. Nemhauser

    (H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332)

  • M. W. P. Savelsbergh

    (H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332)

Abstract

The availability of relatively cheap small jet aircrafts suggests a new air transportation business: dial-a-flight, an on-demand service in which travelers call a few days in advance to schedule transportation. A successful on-demand air transportation service requires an effective scheduling system to construct minimum-cost pilot and jet itineraries for a set of accepted transportation requests. In Part I, we introduced an integer multicommodity network flow model with side constraints for the dial-a-flight problem and showed that small instances can be solved effectively. Here, we demonstrate that high-quality solutions for large-scale real-life instances can be produced efficiently by embedding the core optimization technology in a local search scheme. To achieve the desired level of performance, metrics were devised to select neighborhoods intelligently, a variety of search diversification techniques were included, and an asynchronous parallel implementation was developed.

Suggested Citation

  • D. Espinoza & R. Garcia & M. Goycoolea & G. L. Nemhauser & M. W. P. Savelsbergh, 2008. "Per-Seat, On-Demand Air Transportation Part II: Parallel Local Search," Transportation Science, INFORMS, vol. 42(3), pages 279-291, August.
    • Handle: RePEc:inm:ortrsc:v:42:y:2008:i:3:p:279-291
    DOI: 10.1287/trsc.1070.0228
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.1070.0228
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.1070.0228?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Stefan Ropke & David Pisinger, 2006. "An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows," Transportation Science, INFORMS, vol. 40(4), pages 455-472, November.
    2. D. Espinoza & R. Garcia & M. Goycoolea & G. L. Nemhauser & M. W. P. Savelsbergh, 2008. "Per-Seat, On-Demand Air Transportation Part I: Problem Description and an Integer Multicommodity Flow Model," Transportation Science, INFORMS, vol. 42(3), pages 263-278, August.
    3. G. A. P. Kindervater & J. K. Lenstra & A. H. G. Rinnooy Kan, 1989. "OR Forum—Perspectives on Parallel Computing," Operations Research, INFORMS, vol. 37(6), pages 985-990, December.
    4. Claudia Archetti & M. Grazia Speranza & Martin W. P. Savelsbergh, 2008. "An Optimization-Based Heuristic for the Split Delivery Vehicle Routing Problem," Transportation Science, INFORMS, vol. 42(1), pages 22-31, February.
    5. Bernard Gendron & Teodor Gabriel Crainic, 1994. "Parallel Branch-and-Branch Algorithms: Survey and Synthesis," Operations Research, INFORMS, vol. 42(6), pages 1042-1066, December.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Timothy A. Carnes & Shane G. Henderson & David B. Shmoys & Mahvareh Ahghari & Russell D. MacDonald, 2013. "Mathematical Programming Guides Air-Ambulance Routing at Ornge," Interfaces, INFORMS, vol. 43(3), pages 232-239, May-June.
    2. Pillac, Victor & Gendreau, Michel & Guéret, Christelle & Medaglia, Andrés L., 2013. "A review of dynamic vehicle routing problems," European Journal of Operational Research, Elsevier, vol. 225(1), pages 1-11.
    3. Gizem Keysan & George L. Nemhauser & Martin W. P. Savelsbergh, 2010. "Tactical and Operational Planning of Scheduled Maintenance for Per-Seat, On-Demand Air Transportation," Transportation Science, INFORMS, vol. 44(3), pages 291-306, August.
    4. Sun, Xiaoqian & Wandelt, Sebastian & Stumpf, Eike, 2018. "Competitiveness of on-demand air taxis regarding door-to-door travel time: A race through Europe," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 119(C), pages 1-18.
    5. D. Espinoza & R. Garcia & M. Goycoolea & G. L. Nemhauser & M. W. P. Savelsbergh, 2008. "Per-Seat, On-Demand Air Transportation Part I: Problem Description and an Integer Multicommodity Flow Model," Transportation Science, INFORMS, vol. 42(3), pages 263-278, August.
    6. Munari, Pedro & Alvarez, Aldair, 2019. "Aircraft routing for on-demand air transportation with service upgrade and maintenance events: Compact model and case study," Journal of Air Transport Management, Elsevier, vol. 75(C), pages 75-84.
    7. Yves Molenbruch & Kris Braekers & An Caris, 2017. "Typology and literature review for dial-a-ride problems," Annals of Operations Research, Springer, vol. 259(1), pages 295-325, December.
    8. Gupta, Gautam & Goodchild, Anne & Hansen, Mark, 2011. "A competitive, charter air-service planning model for student athlete travel," Transportation Research Part B: Methodological, Elsevier, vol. 45(1), pages 128-149, January.
    9. Alan Erera & Michael Hewitt & Martin Savelsbergh & Yang Zhang, 2013. "Improved Load Plan Design Through Integer Programming Based Local Search," Transportation Science, INFORMS, vol. 47(3), pages 412-427, August.
    10. Rajendran, Suchithra & Srinivas, Sharan, 2020. "Air taxi service for urban mobility: A critical review of recent developments, future challenges, and opportunities," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 143(C).
    11. Shah, Nirav & Kumar, Subodha & Bastani, Farokh & Yen, I-Ling, 2012. "Optimization models for assessing the peak capacity utilization of intelligent transportation systems," European Journal of Operational Research, Elsevier, vol. 216(1), pages 239-251.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Dumez, Dorian & Tilk, Christian & Irnich, Stefan & Lehuédé, Fabien & Olkis, Katharina & Péton, Olivier, 2023. "A matheuristic for a 2-echelon vehicle routing problem with capacitated satellites and reverse flows," European Journal of Operational Research, Elsevier, vol. 305(1), pages 64-84.
    2. Mike Hewitt & George L. Nemhauser & Martin W. P. Savelsbergh, 2010. "Combining Exact and Heuristic Approaches for the Capacitated Fixed-Charge Network Flow Problem," INFORMS Journal on Computing, INFORMS, vol. 22(2), pages 314-325, May.
    3. Yves Molenbruch & Kris Braekers & An Caris, 2017. "Typology and literature review for dial-a-ride problems," Annals of Operations Research, Springer, vol. 259(1), pages 295-325, December.
    4. JANSSENS, Jochen & DE CORTE, Annelies & SÖRENSEN, Kenneth, 2016. "Water distribution network design optimisation with respect to reliability," Working Papers 2016007, University of Antwerp, Faculty of Business and Economics.
    5. Bach, Lukas & Hasle, Geir & Schulz, Christian, 2019. "Adaptive Large Neighborhood Search on the Graphics Processing Unit," European Journal of Operational Research, Elsevier, vol. 275(1), pages 53-66.
    6. Arpan Rijal & Marco Bijvank & Asvin Goel & René de Koster, 2021. "Workforce Scheduling with Order-Picking Assignments in Distribution Facilities," Transportation Science, INFORMS, vol. 55(3), pages 725-746, May.
    7. S Salhi & A Al-Khedhairi, 2010. "Integrating heuristic information into exact methods: The case of the vertex p-centre problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(11), pages 1619-1631, November.
    8. Martins, Sara & Ostermeier, Manuel & Amorim, Pedro & Hübner, Alexander & Almada-Lobo, Bernardo, 2019. "Product-oriented time window assignment for a multi-compartment vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 276(3), pages 893-909.
    9. Dessouky, Maged M & Shao, Yihuan E, 2017. "Routing Strategies for Efficient Deployment of Alternative Fuel Vehicles for Freight Delivery," Institute of Transportation Studies, Working Paper Series qt0nj024qn, Institute of Transportation Studies, UC Davis.
    10. Mo, Pengli & Yao, Yu & D’Ariano, Andrea & Liu, Zhiyuan, 2023. "The vehicle routing problem with underground logistics: Formulation and algorithm," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 179(C).
    11. SteadieSeifi, M. & Dellaert, N.P. & Nuijten, W. & Van Woensel, T., 2017. "A metaheuristic for the multimodal network flow problem with product quality preservation and empty repositioning," Transportation Research Part B: Methodological, Elsevier, vol. 106(C), pages 321-344.
    12. repec:dar:wpaper:62383 is not listed on IDEAS
    13. Parvez Farazi, Nahid & Zou, Bo & Tulabandhula, Theja, 2022. "Dynamic On-Demand Crowdshipping Using Constrained and Heuristics-Embedded Double Dueling Deep Q-Network," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 166(C).
    14. He, Dongdong & Guan, Wei, 2023. "Promoting service quality with incentive contracts in rural bus integrated passenger-freight service," Transportation Research Part A: Policy and Practice, Elsevier, vol. 175(C).
    15. Przybylski, Anthony & Gandibleux, Xavier, 2017. "Multi-objective branch and bound," European Journal of Operational Research, Elsevier, vol. 260(3), pages 856-872.
    16. Jeffrey W. Ohlmann & Michael J. Fry & Barrett W. Thomas, 2008. "Route Design for Lean Production Systems," Transportation Science, INFORMS, vol. 42(3), pages 352-370, August.
    17. Jone R. Hansen & Kjetil Fagerholt & Magnus Stålhane & Jørgen G. Rakke, 2020. "An adaptive large neighborhood search heuristic for the planar storage location assignment problem: application to stowage planning for Roll-on Roll-off ships," Journal of Heuristics, Springer, vol. 26(6), pages 885-912, December.
    18. Capelle, Thomas & Cortés, Cristián E. & Gendreau, Michel & Rey, Pablo A. & Rousseau, Louis-Martin, 2019. "A column generation approach for location-routing problems with pickup and delivery," European Journal of Operational Research, Elsevier, vol. 272(1), pages 121-131.
    19. Michelle Dunbar & Simon Belieres & Nagesh Shukla & Mehrdad Amirghasemi & Pascal Perez & Nishikant Mishra, 2020. "A genetic column generation algorithm for sustainable spare part delivery: application to the Sydney DropPoint network," Annals of Operations Research, Springer, vol. 290(1), pages 923-941, July.
    20. Arda, Yasemin & Cattaruzza, Diego & François, Véronique & Ogier, Maxime, 2024. "Home chemotherapy delivery: An integrated production scheduling and multi-trip vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 317(2), pages 468-486.
    21. İbrahim Muter & Ş. İlker Birbil & Güvenç Şahin, 2010. "Combination of Metaheuristic and Exact Algorithms for Solving Set Covering-Type Optimization Problems," INFORMS Journal on Computing, INFORMS, vol. 22(4), pages 603-619, November.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ortrsc:v:42:y:2008:i:3:p:279-291. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.