Two-Stage Attention-Based Insertion Policy for the Dynamic Vehicle Routing Problem

Full abstract

Read the full abstract

This paper addresses dynamic vehicle routing with online requests, where insertion heuristics follow fixed rules ignoring the effect of each insertion on later requests. It proposes a two-stage attention-based insertion policy: a first stage selects a vehicle, and a second stage an insertion position within its route. Routes and fleet are encoded by attention, and the policy is trained with REINFORCE and a greedy rollout baseline on the final episode cost instead of immediate insertion costs. It is compared with cheapest, nearest and random insertion and with a single-stage policy over all vehicle–position pairs, on instances with 10 to 120 customers and degrees of dynamism from 10% to 90%. Both learned policies outperform nearest and random insertion and generalize to unseen sizes and degrees of dynamism. When most customers are dynamic on instances with up to 35 customers, the single-stage policy outperforms cheapest insertion by up to 3.1% and the two-stage policy matches it; otherwise, cheapest insertion remains better. The single-stage policy is cheaper in most settings, but the two-stage policy decides up to 2.7 and trains up to 5.7 times faster, for a cost at most 3.6% higher, and becomes cheaper on large, highly dynamic instances.