In this paper, we study an extension of the orienteering problem where travel times are random and time-dependent and service times are random. Additionally, the service at each selected customer is subject to a soft time window; that is, violation of the window is allowed but subject to a penalty that increases in the delay. A solution is a tour determined before the vehicle departs from the depot. The objective is to maximize the sum of the collected prizes net of the expected penalty. The randomness of the travel and service times is modeled by a set of scenarios based on historical data that can be collected from public geographical information services. We present an exact solution method for the problem based on a branch-and-bound algorithm enhanced by a local search procedure at the nodes. A numerical experiment demonstrates the merits of the proposed solution approach. This study is the first to consider an orienteering problem with stochastic travel times and soft time windows, which are more relevant than hard time windows in stochastic settings.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    The data-driven time-dependent orienteering problem with soft time windows


    Beteiligte:
    Edison Avraham (Autor:in) / Tal Raviv (Autor:in)


    Erscheinungsdatum :

    2023




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Unbekannt




    The Multiconstraint Team Orienteering Problem with Multiple Time Windows

    Souffriau, W. / Vansteenwegen, P. / Berghe, G.V. et al. | British Library Online Contents | 2013


    The Multiconstraint Team Orienteering Problem with Multiple Time Windows

    Souffriau, W. / Vansteenwegen, P. / Berghe, G.V. et al. | British Library Conference Proceedings | 2013



    Dubins orienteering problem with neighborhoods

    Penicka, Robert / Faigl, Jan / Vana, Petr et al. | IEEE | 2017


    The Correlated Arc Orienteering Problem

    Agarwal, Saurav / Akella, Srinivas | Springer Verlag | 2022