Multi-commodity vehicle routing problem with pickup and delivery for electric micromobility devices rebalancing and battery swapping

This study addresses a variant of the multi-commodity vehicle routing problem that arises in electric micromobility systems, where a fleet of capacitated vehicles is tasked with simultaneously performing device rebalancing and battery swapping operations. The objective is to satisfy station-level demands while minimizing total travel cost. We refer to this problem as the Electric Micromobility Device Rebalancing and Battery Swapping Problem (EMDRBS), which extends the classical pickup and delivery vehicle routing model by incorporating multi-commodity flows and battery replacement constraints. To solve EMDRBS, we propose four mixed-integer linear programming (MIP) formulations and evaluate their computational performance on a set of realistic benchmark instances derived from public bike-sharing data. While two formulations exhibit strong performance on medium-and large-scale instances, solving the largest cases to optimality remains computationally challenging. To address it, we develop a fix-and-optimize (FixOpt) matheuristic that dynamically adjusts its destruction strategies based on past performance and repairs partial solutions through restricted MIP reoptimization. Computational results show that among the four MIP formulations, F3 and F4 provide the best trade-off between strength and scalability, while the proposed FixOpt matheuristic delivers comparable solution quality with substantially shorter runtimes on large instances. Moreover, coordinated planning of rebalancing and battery swapping reduces total travel distance by up to 50% - particularly under high demand and limited vehicle capacity - without increasing depot resource requirements, demonstrating the practical value of integrated optimization.