1815. The Capacitated Arc Routing Problem with Zigzag Options
Invited abstract in session WA-56: Real-Life Applications in Routing, stream Vehicle Routing and Logistics.
Wednesday, 8:30-10:00Room: Liberty 1.11
Authors (first author is the speaker)
| 1. | Rafael Martinelli
|
| Industrial Engineering, Pontifícia Universidade Católica do Rio de Janeiro (PUC-Rio) | |
| 2. | Thibaut Vidal
|
| Mathematics and Industrial Engineering, Polytechnique Montréal |
Abstract
The Capacitated Arc Routing Problem with Zigzag Options (CARP-Z) arises in applications such as postal delivery, waste collection, and snow plowing, where some streets require service on both sides. Some streets need to be serviced only once, while others must be covered twice, either through separate traversals or a single zigzag pass. The goal of CARP-Z is to determine a set of minimum-cost vehicle routes where each route starts and ends at the depot, single-service streets are covered once, and double-service streets are serviced either twice or through a zigzag pass. Additionally, the total demand assigned to any vehicle must not exceed its capacity. CARP-Z is a challenging optimization problem that generalizes the classical capacitated arc routing problem. Despite its practical importance, it has received little attention in the literature. This work presents two solution approaches: a hybrid metaheuristic and an exact branch-cut-and-price algorithm. The metaheuristic extends a state-of-the-art framework by incorporating new modes to represent zigzag services and a dynamic programming approach to evaluate costs. The exact method generates high-quality solutions through a specialized pricing procedure and tailored cutting techniques. Computational experiments on benchmark instances demonstrate the strong performance of both methods and highlight promising directions for future research.
Keywords
- Vehicle Routing
- Column Generation
- Metaheuristics
Status: accepted
Back to the list of papers