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. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. 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.
    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. 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.

    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. Veaceslav Ghilas & Jean-François Cordeau & Emrah Demir & Tom Van Woensel, 2018. "Branch-and-Price for the Pickup and Delivery Problem with Time Windows and Scheduled Lines," Transportation Science, INFORMS, vol. 52(5), pages 1191-1210, October.
    7. Männel, Dirk & Bortfeldt, Andreas, 2018. "Solving the pickup and delivery problem with three-dimensional loading constraints and reloading ban," European Journal of Operational Research, Elsevier, vol. 264(1), pages 119-137.
    8. Velaga, Nagendra R. & Beecroft, Mark & Nelson, John D. & Corsar, David & Edwards, Peter, 2012. "Transport poverty meets the digital divide: accessibility and connectivity in rural communities," Journal of Transport Geography, Elsevier, vol. 21(C), pages 102-112.
    9. Worapot Sirirak & Rapeepan Pitakaso, 2018. "Marketplace Location Decision Making and Tourism Route Planning," Administrative Sciences, MDPI, vol. 8(4), pages 1-25, November.
    10. 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.
    11. Chen, Qingfeng & Li, Kunpeng & Liu, Zhixue, 2014. "Model and algorithm for an unpaired pickup and delivery vehicle routing problem with split loads," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 69(C), pages 218-235.
    12. 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.
    13. Koç, Çağrı & Bektaş, Tolga & Jabali, Ola & Laporte, Gilbert, 2016. "The fleet size and mix location-routing problem with time windows: Formulations and a heuristic algorithm," European Journal of Operational Research, Elsevier, vol. 248(1), pages 33-51.
    14. Keskin, Merve & Branke, Juergen & Deineko, Vladimir & Strauss, Arne K., 2023. "Dynamic multi-period vehicle routing with touting," European Journal of Operational Research, Elsevier, vol. 310(1), pages 168-184.
    15. Avraham, Edison & Raviv, Tal, 2020. "The data-driven time-dependent traveling salesperson problem," Transportation Research Part B: Methodological, Elsevier, vol. 134(C), pages 25-40.
    16. Schiffer, Maximilian & Walther, Grit, 2018. "Strategic planning of electric logistics fleet networks: A robust location-routing approach," Omega, Elsevier, vol. 80(C), pages 31-42.
    17. Martin-Iradi, Bernardo & Ropke, Stefan, 2022. "A column-generation-based matheuristic for periodic and symmetric train timetabling with integrated passenger routing," European Journal of Operational Research, Elsevier, vol. 297(2), pages 511-531.
    18. Braekers, Kris & Hartl, Richard F. & Parragh, Sophie N. & Tricoire, Fabien, 2016. "A bi-objective home care scheduling problem: Analyzing the trade-off between costs and client inconvenience," European Journal of Operational Research, Elsevier, vol. 248(2), pages 428-443.
    19. 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.
    20. Raidl, Günther R., 2015. "Decomposition based hybrid metaheuristics," European Journal of Operational Research, Elsevier, vol. 244(1), pages 66-76.

    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.