1771. A Metaheuristic to the Twin Rural Postman Problem: Asynchronous case
Invited abstract in session WA-20: Topics in Combinatorial Optimization 3, stream Combinatorial Optimization.
Wednesday, 8:30-10:00Room: Esther Simpson 2.11
Authors (first author is the speaker)
| 1. | Marcos José Negreiros
|
| Computer Science, Universitade Estadual do Ceara | |
| 2. | Augusto Wagner Palhano
|
| GRAPHVS Consultoria Ltda | |
| 3. | Nelson Maculan
|
| UFRJ-COPPE / PESC, Universidade Federal do Rio de Janeiro | |
| 4. | Claudio B. Cunha
|
| Dept. of Transportation Engineering, Escola Politecnica - University of Sao Paulo |
Abstract
This work proposes a metaheuristic procedure based on GRASP for a new multi-objective problem recently proposed to the arc routing related problems to waste collection, the twin rural postman problem. The twin rural postman problem is a problem where a strongly connected mixed network (i.e. street network) must be covered by two servers, a vehicle and a human. The vehicle departs from a garage and ends its route at a disposal site, while the human starts and ends its route in any of its required link. The vehicle may not pass by any required link covered by the human, and the human may traverse his assigned required links in such a way that the service (garbage collected) must be disposed in the corners where the vehicle may pass. The work of both servers must be done in such a way that the service is completed by the human before the vehicle passes by one of any corners. When the time the human starts and ends his route is significantly ahead of the vehicle’s time, or the constraint of service does not matter, it is called the asynchronous twin mode. The GRASP metaheuristic here proposed considers a previously well succeeded greedy strategy from maximum cover tour problem. We report its results in comparison to a column generation and semi-automatic route design procedures evaluated and implemented in the domiciliary waste collection of Andradina/SP.
Keywords
- Combinatorial Optimization
- Vehicle Routing
- Logistics
Status: accepted
Back to the list of papers