Lower bounds for the mixed capacitated arc routing problem |
| |
Authors: | Luís Gouveia Maria Cndida Mouro Leonor Santiago Pinto |
| |
Affiliation: | aUniversidade de Lisboa, Faculdade de Ciências, DEIO, Lisboa, Portugal;bUniversidade Técnica de Lisboa, Instituto Superior de Economia e Gestão, Lisboa, Portugal;cCentro de Investigação Operacional, Portugal;dCEMAPRE – Centro de Matemática Aplicada à Previsão e Decisão Económica, Portugal |
| |
Abstract: | Capacitated arc routing problems (CARP) arise in distribution or collecting problems where activities are performed by vehicles, with limited capacity, and are continuously distributed along some pre-defined links of a network. The CARP is defined either as an undirected problem or as a directed problem depending on whether the required links are undirected or directed. The mixed capacitated arc routing problem (MCARP) models a more realistic scenario since it considers directed as well as undirected required links in the associated network. We present a compact flow based model for the MCARP. Due to its large number of variables and constraints, we have created an aggregated version of the original model. Although this model is no longer valid, we show that it provides the same linear programming bound than the original model. Different sets of valid inequalities are also derived. The quality of the models is tested on benchmark instances with quite promising results. |
| |
Keywords: | Mixed capacitated arc routing Formulations Lower bounds |
本文献已被 ScienceDirect 等数据库收录! |
|