The Active-Passive Vehicle Routing Problem: A Large Neighborhood Search and Problem Extension

Aktivität: VorträgeVortragScience to Science


The active-passive vehicle routing problem (APVRP) is a variant of the vehicle routing problem in which pickup-and-delivery requests require a joint operation of two types of transport resources, namely, passive and active means of transport. The passive means are used for holding the cargo, representing a single unit that is to be shipped from pickup to delivery locations. The active means haul the passive means and carry them from one location to another. Accordingly, the vehicle movements have to be synchronized during the planning. The contribution of our work is twofold. First, we investigate the classical APVRP and provide a fast metaheuristic able to address large benchmark instances. Second, we introduce an extended version of the APVRP, where passive means of transport can hold multiple units of loads. This extension is motivated by a real-world problem setting in integrated
steel production, concerning the task of intra-facility steel slab routing. A characteristic of our extension is that we allow for a request to visit intermediate locations (pickup or delivery locations of other requests) during its journey from its pickup location to its delivery location. Additionally, we design our method such that we realize more opportunities for optimization by allowing the transshipment of passive means among active means at any location. We report computational results for the classical APVRP and show that our metaheuristic provides competitive performance on benchmark data sets. As for the extended
APVRP, we create new instance sets conforming to the specific problem characteristics. Our contributions are completed by a thorough analysis of the possibilities and limitations of transshipments within the scope of the extended APVRP.
Zeitraum10 Sep. 2019
EreignistitelSynchroTrans 2019: Second International Workshop on Synchronization in Transport
OrtNantes, FrankreichAuf Karte anzeigen