EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
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:00Room: 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
- Column Generation
- Logistics
- Vehicle Routing
Status: accepted
Back to the list of papers