The Active‐Passive Vehicle Routing Problem With Item Transshipments

ABSTRACT

This paper addresses a vehicle routing problem with synchronization constraints, in which pickup‐and‐delivery requests for single items are carried out using two types of vehicles: active and passive. The vehicles operate jointly, as passive vehicles, which are capacitated trailers, require active vehicles, which are autonomous trucks without stowing capacity, for repositioning. The problem features flexible transportation practices that allow active and passive vehicles to be coupled and decoupled at any pickup or delivery location, as well as the transshipment of items. This active‐passive vehicle routing problem with item transshipments (APVRPIT) involves interdependent precedence constraints: spatial dependencies between passive vehicles arising from item transshipments propagate to active vehicles, and exchanges of passive vehicles between active vehicles create further movement dependencies. This previously unexplored routing problem arises in steel plant logistics. We propose a metaheuristic algorithm based on a variant of the large neighborhood search (LNS), called nested‐LNS, and we evaluate its performance using test instances that replicate real‐world data. Since the APVRPIT generalizes the established active‐passive vehicle routing problem (APVRP), we demonstrate that the nested‐LNS algorithm attains new best results on several APVRP benchmark instances, outperforming state‐of‐the‐art APVRP methods.