In this paper we study a dynamic vehicle routing problem in which there are multiple vehicles and multiple classes of demands. Demands of each class arrive in the environment randomly over time and require a random amount of on-site service that is characteristic of the class. To service a demand, one of the vehicles must travel to the demand location and remain there for the required on-site service time. The quality of service provided to each class is given by the expected delay between the arrival of a demand in the class, and that demand's service completion. The goal is to design a routing policy for the service vehicles which minimizes a convex combination of the delays for each class. First, we provide a lower bound on the achievable values of the convex combination of delays. Then, we propose a novel routing policy and analyze its performance under heavy load conditions (i.e., when the fraction of time the service vehicles spend performing on-site service approaches one). The policy performs within a constant factor of the lower bound (and thus the optimal), where the constant depends only on the number of classes, and is independent of the number of vehicles, the arrival rates of demands, the on-site service times, and the convex combination coefficients.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    Dynamic Multi-Vehicle Routing with Multiple Classes of Demands


    Beteiligte:
    Pavone, Marco (Autor:in) / Smith, Stephen L. (Autor:in) / Bullo, Francesco (Autor:in) / Frazzoli, Emilio (Autor:in)

    Erscheinungsdatum :

    2009


    Anmerkungen:

    Extended version of paper presented in American Control Conference 2009


    Medientyp :

    Preprint


    Format :

    Elektronische Ressource


    Sprache :

    Englisch





    Partial-route inequalities for the multi-vehicle routing problem with stochastic demands

    JABALI, OLA / Rei, Walter / Gendreau, Michel et al. | BASE | 2014

    Freier Zugriff


    Multidepot Vehicle Routing with Uncertain Demands: Chance Constrained Approach

    Miranda, Pablo A. / Garrido, Rodrigo A. | Transportation Research Record | 2004


    The Multi-period Fleet Size and Mix Vehicle Routing Problem with Stochastic Demands

    Pasha, Urooj / Hoff, Arild / Hvattum, Lars Magnus | Springer Verlag | 2017