EURO 2025 Leeds
Abstract Submission

1212. Multi-visit Arc Routing Problem with Time Windows and Heterogeneous Manpower Groups in Automotive Terminal: Formulations and Heuristics

Invited abstract in session MC-32: Stowage Planning and Vessel Operations, stream Maritime and Port Logistics.

Monday, 12:30-14:00
Room: Maurice Keyworth 1.09

Authors (first author is the speaker)

1. Ziqiao Mei
Management Science and Engineering, Shanghai Jiao Tong University
2. Zhou Xu
Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University
3. Feng Chen
Shanghai Jiao Tong University

Abstract

This study addresses the Multi-visit Arc Routing Problem with Time Windows and Heterogeneous Manpower Groups (MVARPTWH), inspired by real-world operations at a large automotive terminal in China. Loading and unloading tasks are modeled as single arcs, visited multiple times by one group with time window constraints. Heterogeneous groups under dual-cycling operations are scheduled in one shift. We introduce a non-split-arc model that outperforms traditional split-arc models. Due to its NP-hard, we propose a hybrid bilevel memetic search algorithm that explores solutions at both group and arc levels for efficient solving. It begins with three constructive heuristics: a decomposition-based math-heuristic, a rule-based heuristic derived from manual experience, and a spring-based parallel insertion heuristic ensures population diversity. Then, a random and a directed crossover operators generate offspring solutions. To improve solution quality, we propose a bilevel variable neighborhood descent method combined with four efficient operators. Two diversification-based mutations and two quality-and-distance population management strategies are used to help the search escape from local optima. Computational experiments on 24 new instances show that our approach outperforms CPLEX, reducing CO2 emissions of groups by 50% compared to manual scheduling. Additionally, we test the sensitive parameters and assess the impact of key algorithmic components.

Keywords

Status: accepted

Back to the list of papers