Abstract This paper seeks an analytical estimate of the expected distance for visiting an arbitrary subset of independently and uniformly distributed random points within a compact region. This problem has many real-world application contexts such as the emerging on-demand transportation and logistics services (e.g., ridesharing, customized buses). The lower bounds of the expected optimal tour length are analytically derived by considering a so-called “trapping effect”, which explicitly addresses probabilistically the situation that some of the tour legs must connect points that are not neighbors. A parametric approach is developed to estimate the expected optimal tour length for both Euclidean and rectilinear metrics. Numerical experiments demonstrate the validity of these bounds, as well as the closeness of the proposed estimator to simulated results.

    Highlights Parametric estimator of the expected minimum distance for visiting an arbitrary subset of random points in a compact region. Closed-form formulas to gauge the expected extra distance due to a “trapping effect.” Theoretical and numerical analysis of the impacts of the region’s shape and boundary. High accuracy of the proposed estimator under the Euclidean and rectilinear metrics.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Average minimum distance to visit a subset of random points in a compact region


    Contributors:
    Lei, Chao (author) / Ouyang, Yanfeng (author)


    Publication date :

    2024-02-06




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English




    VISIT MANAGEMENT DEVICE, VISIT MANAGEMENT METHOD, AND VISIT MANAGEMENT SYSTEM

    OYAMA TAKAHIRO | European Patent Office | 2020

    Free access

    The minimum barrier distance

    Strand, R. / Ciesielski, K. C. / Malmberg, F. et al. | British Library Online Contents | 2013


    VISIT MANAGEMENT DEVICE, VISIT MANAGEMENT METHOD, AND VISIT MANAGEMENT SYSTEM

    OYAMA TAKAHIRO | European Patent Office | 2021

    Free access

    Triton Visit

    Online Contents | 2001