EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

1465. An exact algorithm for the multi-level multi-trip capacitated arc routing problem

Invited abstract in session MC-25: Discrete, continuous or stochastic optimization and control in networks, transportation and design III, stream Combinatorial Optimization.

Monday, 12:30-14:00
Room: 011 (building: 208)

Authors (first author is the speaker)

1. Chenge Wei
School of Management, Northwestern Polytechnical University
2. Li Xue
Northwestern Polytechnical University
3. Ada Che
School of Management, Northwestern Polytechnical University

Abstract

This paper studies a real-life waste collection problem inspired by a waste collection system in China. In this system, manually operated vehicles (MV) collect small, dense forms of waste on streetsides and unload at waste collection huts. Meanwhile, vehicles with compressors (CV) collect larger waste demands from the huts and stores along the streets. The routing problems of MVs and CVs are regarded as an open multi-trip capacitated arc routing problem and a capacitated general routing problem, respectively. The multi-level problem aims to implement integrated optimisation of these two problems, which identify a set of routes for MVs and CVs with minimum travel costs that collect all waste.
We first build a mixed integer linear programming (MILP) model to solve this problem. Moreover, we propose a set covering model and a logic-based benders decomposition framework that embeds a branch and price (B&P) algorithm. Based on the feature of the two-level problem, this framework decomposes the set covering model into the master problem of MV routes and the sub-problem of CV routes. To solve the sub-problem, the B&P algorithm is then applied. We adopt three classic CARP branching schemes and extend the label-setting algorithm to generate CV routes with negative reduced costs. Preliminary experiments show that, compared with solving the MILP model with commercial optimisation software, the proposed framework can effectively improve the gap within the same time limitation.

Keywords

Status: accepted


Back to the list of papers