Abstract Time dependencies of travel speeds in time-dependent vehicle routing problems (TDVRPs) are usually accounted for by discretizing the planning horizon into several time periods. However, travel speeds usually change frequently in real road networks, so many time periods are needed to evaluate candidate solutions accurately in model and solution construction for practical TDVRPs, which increases substantially the computational complexity of TDVRPs. We develop two deep attention models with dimension-reduction and gate mechanisms to solve practical TDVRPs in real urban road networks. In the two models, a multi-head attention-based dimension-reduction mechanism is proposed to reduce the dimension of model inputs and obtain enhanced node representation, whereas a gate mechanism is introduced to obtain better information representation. On the basis of a travel speed dataset from an urban road network, we conduct extensive experiments to validate the effectiveness of the proposed models on practical TDVRPs with or without consideration of time windows. Experimental results show that our models can solve TDVRPs with 240 time periods and up to 250 customers effectively and efficiently and provide significantly superior overall performances over two representative heuristics and two state-of-the-art deep reinforcement learning models. Especially, compared with a recent tabu search method, our models can reduce the computation time by up to 3,540 times and improve the solution performance by up to 23%. Moreover, our models have an outstanding generalization performance. The model trained for the 30-customer TDVRP with time windows can be used directly to solve problems with up to 250 customers effectively by generating superior solutions over those generated by benchmarking methods.

    Highlights First work addressing practical VRPs with frequently changing travel times. First work developing DRL models to tackle realistic time-dependent VRPs. We develop multiple improvement mechanisms to improve existing DRL models. Our models outperform two representative heuristics and two novel DRL models.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Deep attention models with dimension-reduction and gate mechanisms for solving practical time-dependent vehicle routing problems


    Contributors:
    Guo, Feng (author) / Wei, Qu (author) / Wang, Miao (author) / Guo, Zhaoxia (author) / Wallace, Stein W. (author)


    Publication date :

    2023-03-08




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English




    Solving Multi-Agent Routing Problems Using Deep Attention Mechanisms

    Bono, Guillaume / Dibangoye, Jilles S. / Simonin, Olivier et al. | IEEE | 2021


    Solving Practical Vehicle Routing Problem with Time Windows Using Metaheuristic Algorithms

    Filip Taner / Ante Galić / Tonči Carić | DOAJ | 2012

    Free access

    Using Congestion Zones for Solving the Time Dependent Vehicle Routing Problem

    Tonči Carić / Juraj Fosin | DOAJ | 2020

    Free access

    Solving Full-Vehicle-Mode Vehicle Routing Problems Using ACO

    Liu, Yahui / Cao, Buyang | British Library Conference Proceedings | 2018


    Solving a Heterogeneous Fleet Vehicle Routing Model - A practical approach

    Panicker, Vinay V / Ihsan O, Mohammed | IEEE | 2018