A hybrid algorithm for time-dependent vehicle routing problem with time windows. (April 2021)

• Record Type: Journal Article
• Authors: Pan, Binbin; Zhang, Zhenzhen; Lim, Andrew
• Is Part Of: Computers & operations research. Volume 128(2021)
• Publication Date: 2021-04
• Subjects: Time-dependent travel time -- Duration minimizing -- Vehicle routing -- Hybrid algorithm -- Segment-based evaluation; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2020.105193
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: Effective segment-based route evaluation with time dependent travel time and infeasible solutions. Hybrid meta-heuristic algorithm combining ALNS and TS. Dynamic control of diversification and intensification strengths. Automatic algorithm configuration with irace. New best-known solutions for DM-TDVRPTW. Abstract: In this paper, we study the duration-minimizing time-dependent vehicle routing problem with time windows (DM-TDVRPTW), where time-dependent travel times represent different levels of road congestion throughout the day. The departure time from depot becomes an important decision to reduce the route duration. We provide an alternative arc-based mixed-integer programming model with explicit arc time zone index. For larger scale instances, we extend the segment-based evaluation method to speed up the feasibility check of a given vehicle route. It is thereafter incorporated to implement an efficient hybrid adaptive large neighborhood search with tabu search (ALNS-TS) algorithm, to explore both feasible and infeasible solution spaces. The ALNS-TS exploits the strength of diversification in ALNS through adaptive control of neighborhood size, as well as the strength of intensification in TS by limiting the maximum number of steps allowed without improvement. Related parameters are tuned using an automatic configuration tool to determine the best set of configurations. The computational results demonstrate its excellent performance on the benchmark instances proposed by Dabia et al. (2013), obtaining optimal solutions for all instances with 25 customers and improving best-known solutions for 36 instances with 50 and 100 customers. Computational experiments are also conducted to evaluate the effectiveness of the algorithm on an extra set of large scale instances and on the simplified VRPTW instances.