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.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

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


    Contributors:


    Publication date :

    2016-11-01


    Size :

    539379 byte





    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English




    Evaluation of the Kalanianaole Highway Carpool/Bus Lane

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


    CARPOOL UTILITY

    MOHAPATRA BIBHUDENDU / SINGH MANAVDEEP | European Patent Office | 2021

    Free access

    Evaluation of the Moanalua Freeway Carpool/Bus Bypass Lane

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


    CARPOOL REQUEST METHOD, CARPOOL REQUEST DEVICE, AND PROGRAM

    FUJITA TAKUSHI / KITAGAWA EIJI / IKEDA TAKURO | European Patent Office | 2015

    Free access