Multi-visit vehicle routing for earthwork hauling: Flow-based formulation and model-driven heuristic

Earthwork hauling in large-scale construction projects involves repeated vehicle movements between cut and fill nodes, with overall performance typically measured by the system makespan. We study a minimum-makespan cut-and-fill problem and formulate it as a multi-visit arc-flow (MVAF) mixed-integer linear program. The MVAF formulation explicitly captures repeated vehicle movements while avoiding node splitting for multi-unit supply and demand. To ensure global route connectivity under multi-visit routing, we propose two subtour elimination approaches tailored to the MVAF structure. Exploiting problem characteristics, we derive two lower bounds on the makespan that capture unavoidable time requirements imposed by supply–demand patterns and fleet size. For medium- and large-scale instances, we propose a model-driven bottleneck-based fix-and-optimize heuristic (BFOH), which iteratively re-optimizes a small, tightly coupled subset of vehicles centered on the bottleneck vehicle. Computational experiments indicate that the proposed MVAF formulation achieves favorable computational performance and that the proposed lower bounds are tight. BFOH achieves near-optimal solutions for small-scale instances and consistently outperforms the benchmark model in solution quality within limited computational time for medium- and large-scale instances.