Vehicle routing under time-dependent travel times: The impact of congestion avoidance

    Research output: Contribution to journalArticleAcademicpeer-review

    90 Citations (Scopus)

    Abstract

    Daily traffic congestion forms a major problem for businesses such as logistic service providers and distribution firms. It causes late arrivals at customers and additional costs for hiring the truck drivers. Such costs caused by traffic congestion can be reduced by taking into account and avoiding predictable traffic congestion within vehicle route plans. In the literature, various strategies are proposed to avoid traffic congestion, such as selecting alternative routes, changing the customer visit sequences, and changing the vehicle-customer assignments. We investigate the impact of these and other strategies in off-line vehicle routing on the performance of vehicle route plans in reality. For this purpose, we develop a set of vehicle routing problem instances on real road networks, and a speed model that reflects the key elements of peak hour traffic congestion. The instances are solved for different levels of congestion avoidance using a modified Dijkstra algorithm and a restricted dynamic programming heuristic. Computational experiments show that 99% of late arrivals at customers can be eliminated if traffic congestion is accounted for off-line. On top of that, about 87% of the extra duty time caused by traffic congestion can be eliminated by clever congestion avoidance strategies.
    Original languageEnglish
    Pages (from-to)910-918
    JournalComputers & operations research
    Volume39
    Issue number5
    DOIs
    Publication statusPublished - 2012

    Fingerprint

    Vehicle Routing
    Vehicle routing
    Traffic Congestion
    Traffic congestion
    Travel Time
    Travel time
    Congestion
    Customers
    Truck drivers
    Dijkstra Algorithm
    Line
    Vehicle Routing Problem
    Road Network
    Costs
    Avoidance
    Dynamic programming
    Computational Experiments
    Logistics
    Dynamic Programming
    Driver

    Keywords

    • Time-dependent VRP
    • Congestion avoidance
    • Speed model
    • IR-79709
    • METIS-278192
    • Time-dependent SPP

    Cite this

    @article{a303d2fba52c4d468ca9556a75e96d5f,
    title = "Vehicle routing under time-dependent travel times: The impact of congestion avoidance",
    abstract = "Daily traffic congestion forms a major problem for businesses such as logistic service providers and distribution firms. It causes late arrivals at customers and additional costs for hiring the truck drivers. Such costs caused by traffic congestion can be reduced by taking into account and avoiding predictable traffic congestion within vehicle route plans. In the literature, various strategies are proposed to avoid traffic congestion, such as selecting alternative routes, changing the customer visit sequences, and changing the vehicle-customer assignments. We investigate the impact of these and other strategies in off-line vehicle routing on the performance of vehicle route plans in reality. For this purpose, we develop a set of vehicle routing problem instances on real road networks, and a speed model that reflects the key elements of peak hour traffic congestion. The instances are solved for different levels of congestion avoidance using a modified Dijkstra algorithm and a restricted dynamic programming heuristic. Computational experiments show that 99{\%} of late arrivals at customers can be eliminated if traffic congestion is accounted for off-line. On top of that, about 87{\%} of the extra duty time caused by traffic congestion can be eliminated by clever congestion avoidance strategies.",
    keywords = "Time-dependent VRP, Congestion avoidance, Speed model, IR-79709, METIS-278192, Time-dependent SPP",
    author = "A.L. Kok and Hans, {Elias W.} and Schutten, {Johannes M.J.}",
    year = "2012",
    doi = "10.1016/j.cor.2011.05.027",
    language = "English",
    volume = "39",
    pages = "910--918",
    journal = "Computers & operations research",
    issn = "0305-0548",
    publisher = "Elsevier",
    number = "5",

    }

    Vehicle routing under time-dependent travel times: The impact of congestion avoidance. / Kok, A.L.; Hans, Elias W.; Schutten, Johannes M.J.

    In: Computers & operations research, Vol. 39, No. 5, 2012, p. 910-918.

    Research output: Contribution to journalArticleAcademicpeer-review

    TY - JOUR

    T1 - Vehicle routing under time-dependent travel times: The impact of congestion avoidance

    AU - Kok, A.L.

    AU - Hans, Elias W.

    AU - Schutten, Johannes M.J.

    PY - 2012

    Y1 - 2012

    N2 - Daily traffic congestion forms a major problem for businesses such as logistic service providers and distribution firms. It causes late arrivals at customers and additional costs for hiring the truck drivers. Such costs caused by traffic congestion can be reduced by taking into account and avoiding predictable traffic congestion within vehicle route plans. In the literature, various strategies are proposed to avoid traffic congestion, such as selecting alternative routes, changing the customer visit sequences, and changing the vehicle-customer assignments. We investigate the impact of these and other strategies in off-line vehicle routing on the performance of vehicle route plans in reality. For this purpose, we develop a set of vehicle routing problem instances on real road networks, and a speed model that reflects the key elements of peak hour traffic congestion. The instances are solved for different levels of congestion avoidance using a modified Dijkstra algorithm and a restricted dynamic programming heuristic. Computational experiments show that 99% of late arrivals at customers can be eliminated if traffic congestion is accounted for off-line. On top of that, about 87% of the extra duty time caused by traffic congestion can be eliminated by clever congestion avoidance strategies.

    AB - Daily traffic congestion forms a major problem for businesses such as logistic service providers and distribution firms. It causes late arrivals at customers and additional costs for hiring the truck drivers. Such costs caused by traffic congestion can be reduced by taking into account and avoiding predictable traffic congestion within vehicle route plans. In the literature, various strategies are proposed to avoid traffic congestion, such as selecting alternative routes, changing the customer visit sequences, and changing the vehicle-customer assignments. We investigate the impact of these and other strategies in off-line vehicle routing on the performance of vehicle route plans in reality. For this purpose, we develop a set of vehicle routing problem instances on real road networks, and a speed model that reflects the key elements of peak hour traffic congestion. The instances are solved for different levels of congestion avoidance using a modified Dijkstra algorithm and a restricted dynamic programming heuristic. Computational experiments show that 99% of late arrivals at customers can be eliminated if traffic congestion is accounted for off-line. On top of that, about 87% of the extra duty time caused by traffic congestion can be eliminated by clever congestion avoidance strategies.

    KW - Time-dependent VRP

    KW - Congestion avoidance

    KW - Speed model

    KW - IR-79709

    KW - METIS-278192

    KW - Time-dependent SPP

    U2 - 10.1016/j.cor.2011.05.027

    DO - 10.1016/j.cor.2011.05.027

    M3 - Article

    VL - 39

    SP - 910

    EP - 918

    JO - Computers & operations research

    JF - Computers & operations research

    SN - 0305-0548

    IS - 5

    ER -