Carpooling has been long deemed a promising approach to better utilizing existing transportation infrastructure. However, there are several reasons carpooling is still not the preferred mode of commute in the United States: first, complex human factors, including time constraints and not having right incentive structures, discourage the sharing of rides; second, algorithmic and technical barriers inhibit the development of online services for matching riders. In this work, we study algorithms for 3+ high-occupancy vehicle (HOV) lanes, which permit vehicles that hold three or more people. We focus on the technical barriers but also address the aforementioned human factors. We formulate the HOV3 Carpool problem, and show that it is NP-Complete. We thus pose the relaxed problem HOV3- Carpool problem, allowing groups of up to size three, and propose several methods for solving the problem of finding globally optimal carpool groups that may utilize these 3- HOV lanes. Our methods include local search, integer programming, and dynamic programming. Our local search methods include sampling-based (hill-climbing and simulated annealing), classical neighborhood search, and a hybrid random neighborhood search. We assess the methods numerically in terms of objective value and scalability. Our findings show that our sampling-based local search methods scale up to 100K agents, thereby improving upon related previous work (which studies up to 1000 agents). The hill climbing local search method converges significantly closer and faster towards a naive lower bound on cumulative carpooling cost.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Optimizing the diamond lane: A more tractable carpool problem and algorithms


    Beteiligte:
    Wu, Cathy (Autor:in) / Shankari, K. (Autor:in) / Kamar, Ece (Autor:in) / Katz, Randy (Autor:in) / Culler, David (Autor:in) / Papadimitriou, Christos (Autor:in) / Horvitz, Eric (Autor:in) / Bayen, Alexandre (Autor:in)


    Erscheinungsdatum :

    2016-11-01


    Format / Umfang :

    539379 byte





    Medientyp :

    Aufsatz (Konferenz)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch




    Evaluation of the Kalanianaole Highway Carpool/Bus Lane

    D. Kaku / W. Yamamoto / F. Wagner et al. | NTIS | 1977


    Evaluation of the Moanalua Freeway Carpool/Bus Bypass Lane

    D. Kaku / W. Yamamoto / F. Wagner et al. | NTIS | 1977


    CARPOOL UTILITY

    MOHAPATRA BIBHUDENDU / SINGH MANAVDEEP | Europäisches Patentamt | 2021

    Freier Zugriff

    CARPOOL REQUEST METHOD, CARPOOL REQUEST DEVICE, AND PROGRAM

    FUJITA TAKUSHI / KITAGAWA EIJI / IKEDA TAKURO | Europäisches Patentamt | 2015

    Freier Zugriff