Conventionally, vehicle routing problems are defined on a network in which the customer locations and arcs are given. Typically, these arcs somehow represent the distances or expected travel time derived from the underlying road network. When executed, the quality of the solutions obtained from the vehicle routing problem depends largely on the quality of the road network representation. This paper explicitly considers path selection in the road network as an integrated decision in the time-dependent vehicle routing problem, denoted as path flexibility (PF). This means that any arc between two customer nodes has multiple corresponding paths in the road network (geographical graph). Hence, the decisions to make are involving not only the routing decision but also the path selection decision depending upon the departure time at the customers and the congestion levels in the relevant road network. The corresponding routing problem is a time-dependent vehicle routing problem with path flexibility (TDVRP–PF). We formulate the TDVRP–PF models under deterministic and stochastic traffic conditions. We derive important insights, relationships, and solution structures. Based on a representative testbed of instances (inspired on the road network of Beijing), significant savings are obtained in terms of cost and fuel consumption, by explicitly considering path flexibility. Having both path flexibility and time-dependent travel time seems to be a good representation of a wide range of stochasticity and dynamics in the travel time, and path flexibility serves as a natural recourse under stochastic conditions. Exploiting this observation, we employ a Route-Path approximation method generating near-optimal solutions for the TDVRP–PF under stochastic traffic conditions.


    Access

    Download


    Export, share and cite



    Title :

    Time-dependent vehicle routing problem with path flexibility


    Contributors:
    Huang, Y. (author) / Zhao, L. (author) / van Woensel, T. (author) / Gross, J.-P. (author)

    Publication date :

    2017-01-01


    Remarks:

    Huang , Y , Zhao , L , van Woensel , T & Gross , J-P 2017 , ' Time-dependent vehicle routing problem with path flexibility ' , Transportation Research. Part B: Methodological , vol. 95 , pp. 169-195 . https://doi.org/10.1016/j.trb.2016.10.013



    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English



    Classification :

    DDC:    380 / 629



    Time-dependent vehicle routing problem with path flexibility

    Huang, Yixiao / Zhao, Lei / Van Woensel, Tom et al. | Elsevier | 2016



    Time-Dependent Electric Vehicle Routing Problem with Time Windows and Path Flexibility

    Li Wang / Shuai Gao / Kai Wang et al. | DOAJ | 2020

    Free access

    Time-Dependent Urban Customized Bus Routing With Path Flexibility

    Guo, Rongge / Zhang, Wenyi / Guan, Wei et al. | IEEE | 2021


    Time-Dependent Green Vehicle Routing Problem

    Masghati-Amoli, Golnush / Haghani, Ali | Springer Verlag | 2020